in Graph Theory edited by
2,541 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}$
in Graph Theory edited by
by
2.5k views

2 Answers

1 vote
1 vote

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

0 votes
0 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. 

2 Comments

@Deepak Poonia what they mean by saying "G is a perfect matching" ?

Should not it be "G has a perfect matching" ?

1
1

@ankitgupta.1729, Yes, it should be "$G$ has a perfect matching".

I think they have given "$G$ is a perfect matching" because $G$ actually will be disjoint union of $K_2$'s (visualization of such $G$ HERE). 

The statement "$G$ is a perfect matching" doesn't make sense in Graph Theory. 

Also, If $G$ has a perfect matching then it doesn't imply that $A = A^{-1}.$

But If $G$ is a union of $K_2$'s then it implies $A = A^{-1}$ and vice versa. 

1
1
Answer:

Related questions

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