The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+14 votes
2.3k views

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)$
asked in Linear Algebra by Veteran (59.5k points)
edited by | 2.3k views
0

This might help ...

4 Answers

+26 votes
Best answer
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.$
answered by Veteran (355k points)
edited by
+6

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 (n2  - 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 :

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

+5 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
answered by Active (1.8k points)
+3 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
answered by Active (4.5k points)
0 votes
objective approach ->

some properties of a symmetric matrix

diagonal elements will not impact on a matrix being a symmetric .

now we have 2 elements  1 and 0

so diagonals could be

00

01

10

11

and two non diagonal elements should must be same bcz symmetric  thus they can be either 00 or 11

so lets construct the matrices fast

case 1 :  diagonal elements = 00

0    0                                           0     1

0    0                                           1     0

since other elements must be same thus we have filled it with 00 and 11

case 2:   diagonal elements = 01

0    0                                           0     1

0    1                                           1     1

 

case 3:   diagonal elements = 10

1    0                                           1     1

0    0                                           1     0

 

case 4:   diagonal elements = 11

1    0                                           1     1

0    1                                           1     1

 

thus total 8 matrices we able to construct

now put n=3  in the options  only c will satisfy

i have solved this question in less than a minute but for explaining it took time , anyway with practise can be done fastly.

 

 

 

 

subjective approach->

from above examples it should be clear that if it is an  n*n matrix then there will be exactly n diagonal position(11,22)

and they will have 2 choices (either filled with 0 or filled with 1)  thus total   2^n choices

total elements = n*n=n^2

diagonal elements= n

thus non diagonal elements= n^2-n

now as from above we have found that selecting one will automatically select the other thus basically we have (n^2-n)/2

positions to select and we have two choices (to be filled with 0or 1) thus total    2^((n^2-n)/2)  choices

thus total  2^n * 2^((n^2-n)/2)  choices

now about non diagonal elements
answered by (357 points)
edited by


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

38,058 questions
45,554 answers
131,889 comments
48,909 users