If A = a_{ij} and B=b_{ij} are any m X n matrices, the matrix A + B is the mXn m
ID: 3659926 • Letter: I
Question
If A = a_{ij} and B=b_{ij} are any m X n matrices, the matrix A + B is the mXn matrix whose ijth entry is a_{ij} + b_{ij} for all i= 1, 2, ... m and j= 1,2,.... n. Let G be a graph with n vertices where n>1, and let A be the adjacency matrix of G. Prove that G is connected if, and only if, every entry of A + A^{2} + ... A^{n-1} is positive.
Explanation / Answer
consider A^n => an entry in A^n gives the number of paths of length "n" example : consider A^1 if the entry is >= 1 it implies that there is an edge or there is a path of length 1 therefore A + A^{2} + ... A^{n-1} gives the sum of number of paths of length 1 ,2 3 ,4 5...n-1 if the entry a[ij]= 0 ,it implies that there is no path of any length between i,j and these are not connected so if a[ij] is positive then there is path between them and they are connected