Question

The number of different n$\times$n symmetric matrices with each element being either 0 or 1 is: (Note: power (2, x) is same as $2^x$)

• A. $Power(2,\frac{n^2-n}{2})$
• B. $Power(2,n)$
• C. $Power(2,\frac{(n^2+n)}{2})$
• D. $Power(2,n^2)$

Answer 1

The correct option is C $Power(2,\frac{(n^2+n)}{2})$

In a symmetric matrix, the lower triangle must be the mirror image of upper triangle using the diagonal as mirror. Diagonal elements may be anything. Therefore, when we are counting symmetric matrices we count how many way are there to fill the upper triangle and diagonal elements. Since the first row has n element second (n - 1) elements, third row (n - 2) element and so on upto last row, one element.
Total number of elements in diagonal + upper triangle
$=n+(n—1)+(n—2)+\dots \dots +1$
$=n\frac{n+1}{2}$
Now, each one of these elements can be either or 1. So total number of ways we can fill the elements is
$2^{\frac{n(n+1)}{2}}$
$=power(2,\frac{(n^2+n)}{2})$.
Since there is no choice for lower triangle elements the answer is power
$(2,\frac{(n^2+n)}{2})$
which is choice (c).