GATE2004-26

Question

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

• A. $\text{power} \left(2, n\right)$
• B. $\text{power} \left(2, n^2\right)$
• C. $\text{power} \left(2,\frac{ \left(n^2+ n \right) }{2}\right)$
• D. $\text{power} \left(2, \frac{\left(n^2 - n\right)}{2}\right)$

Comments

This might help ...

Answer 1

In symmetric matrix, $A[i][j] = A[j][i]$. So, we have choice only for either the upper triangular elements or the lower triangular elements. Number of such elements will be $n + (n-1) + (n-2) + \cdots + 1 = n\frac{(n+1)}{2} = \frac{(n^2+n)}{2}$. Now, each element being either 0 or 1 means, we have 2 choices for each element and thus for $\frac{(n^2+n)}{2}$ elements we have $2^{\frac{(n^2+n)}{2}}$ possibilities.

Choice C.

Comments

The problem is similar to finding the number of symmetric relations possible on an n element set.
Now if we consider the n pairs of reflexive relation, those n pairs also satisfy the property of symmetric relation and each of these n pair may or may not be present in a symmetric relation.

Moreover there are (n²  - n)/2 diagonal pairs in an nxn matrix each of which should be present to have relation symmetric.
Means if we have pair (x,y) we need to have pair (y,x)

So, total symmetric relations possible on an n element set :

2ⁿ . 2 ^(n2-n)/2  = 2 ^n(n+1)/2  

Answer 2

Matrices with 0 or 1 can be viewed as adjacency matrix of an undirected graph. There can be at max $n(n-1)/2$ edges in such graph.

So each edge can either be present or not. That gives total of $2^{(n^{2}-n)/2}$ , but this does not include n combination of self loops. so the total number of combincation is $2^{(n^{2}+n)/2}$.
Answer C

Answer 3

for diagnol elements we have 2 choices either 0 or 1 So , 2^n  for rest of the elements we can pair which will have 2 choices either 0 or 1  total pairs =(n^2-n)/2

2^n * 2^((n^2-n)/2)  = Option C