edited by
12,433 views
25 votes
25 votes

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$)

  1. $\text{power} \left(2, n\right)$
  2. $\text{power} \left(2, n^2\right)$
  3. $\text{power} \left(2,\frac{ \left(n^2+ n \right) }{2}\right)$
  4. $\text{power} \left(2, \frac{\left(n^2 - n\right)}{2}\right)$
edited by

7 Answers

Best answer
48 votes
48 votes
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 is $C.$
edited by
13 votes
13 votes

In this $4*4$ matrix, we only have choices for the elements enclosed in the red rectangle.

The corresponding blue rectangle would have same elements as of the red rectangle.

We got choices for $4+3+2+1$ elements.

We can extend this to $n*n$ matrix, in which we'd have choices for $n+(n-1)+(n-2)+...+1$ elements.

=> $1+2+3+...+n$ elements

=> $\frac{n(n+1)}{2}$ elements

 

Two choices for $\frac{n(n+1)}{2}$ elements means $2^{\frac{n(n+1)}{2}}$

Option C

12 votes
12 votes
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
5 votes
5 votes
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
Answer:

Related questions

35 votes
35 votes
4 answers
1
Kathleen asked Sep 18, 2014
9,512 views
In an $M \times N$ matrix all non-zero entries are covered in $a$ rows and $b$ columns. Then the maximum number of non-zero entries, such that no two are on the same row ...
35 votes
35 votes
4 answers
2
Kathleen asked Sep 18, 2014
9,979 views
Let $A, B, C, D$ be $n \times n$ matrices, each with non-zero determinant. If $ABCD = I$, then $B^{-1}$ is $D^{-1}C^{-1}A^{-1}$ $CDA$ $ADC$ Does not necessarily e...
28 votes
28 votes
4 answers
3
Kathleen asked Sep 18, 2014
8,280 views
How many solutions does the following system of linear equations have?$-x + 5y = -1$$x - y = 2$$x + 3y = 3$infinitely manytwo distinct solutionsuniquenone