retagged by
3,193 views
2 votes
2 votes

​​​​Let $\text{A}$ be the adjacency matrix of a simple undirected graph $\text{G}$. Suppose $\text{A}$ is its own inverse. Which one of the following statements is always TRUE?

  1. $\text{G}$ is a cycle
  2. $\text{G}$ is a perfect matching
  3. $\text{G}$ is a complete graph
  4. There is no such graph $\text{G}$
retagged by

2 Answers

2 votes
2 votes

Since, every adjacency matrix is also a symmetric matrix and so $A=A^T=A^{-1}$ implies $A^2=AA^T=A^TA=I_n.$  

 

So $A_{n \times n}$ is an orthogonal matrix because both the row and column spaces of this matrix form an orthonormal basis of $\mathbb{R}^n$

(each row and column should be mutually perpendicular).   

  

It simply means that $a_{ii}^{th}$ entry in $A^2$ is the dot/inner product of $i^{th}$ row and $i^{th}$ column. For example, $a_{11}$ in $A^2$ is the dot product of first row and first column.    

  

Here, graph is simple and so $A$ is a matrix of 0s and 1s. Since the result of dot product is 1, it means there should be only one entry of 1 in each row and each column with the same position so that $v^Tv=\Sigma_{i=1}^nv_{i}^2=1$ for each row/column vector $v$ of 0s and 1s in $A.$ It simply means if $k^{th}$ entry of $1^{st}$ row is $1$ then the $k^{th}$ entry should also be $1$ in the $1^{st}$ column.

  

So, here, we can say that if $v_i$ is connected to $v_j$ then $v_j$ should also be connected to $v_i$ and there should not be any other connection for both $v_i$ and $v_j.$ In this way we can form the set of independent edges that cover the whole graph and So, $G$ will definitely have a perfect matching.

   

So, Answer is B.

  

Counter-example for other options can be $K_3.$

  

One more way to prove the statement is using the fact that every $(i,j)^{th}$ entry of $A^k$ is the number of $v_i,v_j-walks$ of length $k$ in $G.$

1 votes
1 votes

Video Solution: Graphs whose Adjacency Matrix is Self-Inverse.

Let $A$ be the adjacency matrix of a simple undirected graph $G.$

  • For a simple undirected graph $G,$ $A = A^{-1}$ if and only if $G$ is disjoint union of $K_2$'s. Explained HERE.

Proof is easy. Will add the proof soon. 

So, the answer is Option B. 

Answer:

Related questions

1 votes
1 votes
3 answers
2
Arjun asked Feb 16
2,174 views
The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph is __________.
2 votes
2 votes
2 answers
3
Arjun asked Feb 16
2,285 views
The number of spanning trees in a complete graph of $4$ vertices labelled $\text{A, B, C,}$ and $\text{D}$ is _________.