GATE CS 2004 Q26 — Linear Algebra: Matrices, Determinants, System of Linear Equations

For an $n \times n$ matrix $A$ to be symmetric, it must satisfy $A = A^T$, which means $a_{ij} = a_{ji}$ for all $1 \le i, j \le n$.

This symmetry constraint implies that the elements on the main diagonal and the elements in either the upper triangular or lower triangular part uniquely determine the entire matrix. The elements in the remaining part are automatically determined by symmetry.

Let's count the number of independent elements we can choose:

• Main diagonal elements: There are $n$ such elements ($a_{11}, a_{22}, \dots, a_{nn}$).
• Strictly upper triangular elements: There are $\frac{n^2 - n}{2}$ such elements.

The total number of independent elements is:

Since each of these $\frac{n^2 + n}{2}$ independent positions can be filled with either $0$ or $1$ (which gives $2$ choices per position), the total number of different symmetric matrices is:

Therefore, the correct option is C.