Question

Given an adjacency matrix $A=[[0,1,1],[101],[110]]$ The total no. of ways in which every vertex can walk to itself using 2 edges is
A. 2
B. 4
C. 6
D. 8

Answer 1

So here in this question For this we have to first calculate the ${{\text{A}}^{2}}$ then on compare the corresponding vertex of $\text{A}$and ${{\text{A}}^{2}}$, now after comparing both vertexes we can apply simple permutation to find the total no. of ways in which every vertex can walk to itself using 2 edges

Complete step-by-step solution:
We are given an adjacency matrix $A=[[0,1,1],[1,0,1],[1,1,0]]$ and we are asked to finds total no. of ways in which every vertex can walk to itself using 2 edges is
So first we have to calculate ${{\text{A}}^{2}}$,

0 & 1 & 1 \\\ 1 & 0 & 1 \\\ 1 & 1 & 0 \\\ \end{matrix} \right)$$ so $${{\text{A}}^{2}}$$ can be written as $${{A}^{2}}=\left( \begin{matrix} 0 & 1 & 1 \\\ 1 & 0 & 1 \\\ 1 & 1 & 0 \\\ \end{matrix} \right)\left( \begin{matrix} 0 & 1 & 1 \\\ 1 & 0 & 1 \\\ 1 & 1 & 0 \\\ \end{matrix} \right)$$ Now we can apply property which is $${{B}^{2}}=\left( \begin{matrix} a & b & c \\\ d & e & f \\\ g & h & i \\\ \end{matrix} \right)\left( \begin{matrix} a & b & c \\\ d & e & f \\\ g & h & i \\\ \end{matrix} \right)=\left( \begin{matrix} {{a}^{2}}+bd+cg & ab+be+ch & ac+bf+ci \\\ ad+ed+fg & bd+{{e}^{2}}+hf & cd+ef+if \\\ ag+hd+ig & bg+eh+ih & cg+hf+{{i}^{2}} \\\ \end{matrix} \right)$$ So, using this property on Our $${{\text{A}}^{2}}$$ matrix will look like $${{A}^{2}}=\left( \begin{matrix} 0+1+1 & 0+0+1 & 0+1+0 \\\ 0+0+1 & 1+0+1 & 1+0+0 \\\ 0+1+0 & 1+0+0 & 1+1+0 \\\ \end{matrix} \right)$$ Which on further solving comes out to be $${{A}^{2}}=\left( \begin{matrix} 2 & 1 & 1 \\\ 1 & 2 & 1 \\\ 1 & 1 & 2 \\\ \end{matrix} \right)$$ This matrix can also be written as $${{A}^{2}}=[[2,1,1],[1,2,1],[1,1,2]]$$ and matrix $$A=[[0,1,1],[1,0,1],[1,1,0]]$$ is given. So we can see that for every vertex to walk to itself using 2 edges is 2 because compare first vertex of both matrix $$\text{A}$$ and $${{\text{A}}^{2}}$$ one point is $$[0,1,1]$$ other one is $$[2,1,1]$$ which means $$2-0,1-1,1-1=2,0,0$$ so it means there are two ways and for 3 vertices can reach to themselves in 2 ways, hence a total of $$3\times 2=6$$ ways. **Hence Answer is 6 option (b)** **Note:** $${{B}^{2}}=\left( \begin{matrix} a & b & c \\\ d & e & f \\\ g & h & i \\\ \end{matrix} \right)\left( \begin{matrix} a & b & c \\\ d & e & f \\\ g & h & i \\\ \end{matrix} \right)=\left( \begin{matrix} {{a}^{2}}+bd+cg & ab+be+ch & ac+bf+ci \\\ ad+ed+fg & bd+{{e}^{2}}+hf & cd+ef+if \\\ ag+hd+ig & bg+eh+ih & cg+hf+{{i}^{2}} \\\ \end{matrix} \right)$$ here we have applied this property for two same matrices but we can also apply on multiply two different matrices. Square or any power of identity matrix is equals to identity matrix only.