Question

the number of different nxn symmetric matrices with each element being either 0 or 1 is ______
a. 2^n
b. 2^(n^2)
c.2^((n^2+n)/2)
d.2^((n^2-n)/2) @IIT study group

Answer 1

Imagine that each element in the matrix is put together in one binary word.
The number of possible binary numbers would be 2^(number of elements) where the number of elements is nxn or n^2.

Answer 2

The answer should be \(2^{\frac{n^2+n}{2}}\): (c). You can think of this as raising 2 to the number of independent entries (ones that can be what ever they want), so our goal is to find which entries are independent. We choose either the bottom left or top right corners, but then the diagonal is always independent, because when the matrix is transposed it stays the same. So every time \(n\) increases, you are adding another row to a triangle of independent entries (the ones filled in). The formula for the \(n\)th triangle number is \(\frac{n^2+n}{2}\).