number of possible $n\times n$ symmetric matrices with each entry either $o$ or unity

Question

question:

number of different $n\times n $ symmetric matrices with each element either 0 or 1 is

$(a)2^n$

$(b)2^{n^{2}}$

$(c)2^{\frac{n(n+1)}{2}}$

$(d)2^{\frac{n(n-1)}{2}}$

my attempt:

first every digonal matrix is symmetric so, answer should not be $2^n$ it should be greater than that . .....i also know if i choose elements of upper triangular matrix then ,since matrix is symmetric ,elements of lower triangular matrix is automatically fixed ...but i don't know how to do it using permuatations ....answer should be between $ b$ and $c $ . please help

Answer 1

As you say, there are $n$ elements along the diagonal. Each of them can be anything. That leaves $n^2-n$ elements, which occur in pairs symmetric across the diagonal. The entries of each pair must agree, but different pairs can have different values. There are $\frac 12(n^2-n)$ pairs. That gives $n+\frac 12(n^2-n)=\frac 12n(n+1)$ free elements in an $n \times n$ symmetric matrix.

Answer 2

Hint. What is the total number of entries on and above the principal diagonal of an $n\times n$ matrix? You have $n$ entries on the diagonal, $n-1$ immediately above the diagonal, $n-2$ above that and so on till you only have $1$ entry in the upper-right corner of the matrix. What is the sum $1+2+...+(n-1)+n$?

Answer 3

For $n\times n$ matrix there is $n^2$ places to put 0 or 1 .Because of symmetry places below diagonal are already determined by elements above diagonal.

Totally there are $n^2 $ entries,below principal diagonal entries are already determined by above. Entries above diagonal is $ \cfrac{n^2-n}{2}$ .now add diagonal places which gives you $\cfrac{n(n+1)}{2}$