DM-Graphs-Q8

+1 vote

A represents an adjacency matrix of Graph G

$\begin{bmatrix} 0& 1&0&0\\ 1 & 0 & 1 & 1\\ 0 & 1 & 0 & 0\\ 0 & 1 & 0 & 0 \end{bmatrix}$

The number of paths of length 8  from vertex 1 to vertex 4.

reshown Jul 13

Answer is 0   (I am not sure plz suggest)

answered Jul 13 by (1,100 points)
find A^8 matrix and entry (1,4) in A^8 is required answer.
answer should be 27 A^8 have to computed by taking adjacent matrix
Is there any shortcut to find the same? or do we need to calculate by multiplying it 8 times
how is A^8 soln of this question?
A^8 could be calculated by cayley hamilton theorem ,but not getting an idea why A^8 is soln of this question
In matrix a^n each (i,j) entry gives the no of paths of length n from i to j.
Yes, only 3 multiplications are necessary. A^2 = A*A, then  A^4 = A^2*A^2 then A^8 = A^4*A^4.
bro it given only simple matrix .so why you mutiply 8 times .i think ans should be 0 plz give valid reason