The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+17 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)$
asked in Linear Algebra by Veteran (52k points)
edited by | 3.2k views

This might help ...


4 Answers

+35 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 (406k points)
edited by

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  


why not twice of this ?How about if matrix diagonal is from upper right to lower left.Would not that be one more case?

Didn't get you :(

what about counting case (ii) ?

Your second matrix is an invalid lower triangular matrix, as some elements below the main diagonal are zero.

A triangular matrix is upper or lower by the fact that the elements above or below the main diagonal respectively, are non-zero.

@ Ayush Upadhyaya The got the concept of no. of symmetric relation possible but i cannot understand how you relate it with matrix.

+9 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)
+4 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.4k points)
0 votes
consider a 5*5 square matrix, where entries in each cell represent the number of ways we can fill it. Since only 0 or 1 can be inserted therefore 2 ways.

$\bigl(\begin{smallmatrix} 2& 1 & 1& 1 &1\\ 2& 2 &1 &1 &1 \\ 2&2 &2 &1 & 1\\ 2&2 & 2 &2 &1 \\ 2&2 &2 & 2 & 2 \end{smallmatrix}\bigr)$

Now diagonal entries can be filled by any of 0 or 1 , so 2 ways for diagonal elements

but for non-diagonal we need to fix the elements in either upper/lower triangle of matrix, Because its a symmetric matrix hence it will be mirror image about diagonal.

for e.g. if A[2,1]= 1, then A[1,2]=1 OR  if A[2,1]= 0, then A[1,2]=0

fixing lower triangle: number of ways to fill   A[2,1] is 2 , so number of ways to fill   A[1,2] is 1

otherwise fixing upper triangle: number of ways to fill A[1,2] is 2, so number of ways to fill A[2,1] is 1

number of n*n symmetric = $2^{n}*2^{n-1}*2^{n-1}$............$2^{1}$

answered by Active (2.2k points)

Related questions

+22 votes
3 answers
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
49,541 questions
54,084 answers
70,994 users