Matrix and graph theory I have a question. I'm trying to find whether there is a connection between graphs and matrix.
I was given the next question:
$m$ is a square matrix that represents a graph that each entry has either a '0' or 
a '1'
-
if an entry $i,j$ has a '0' in it, it means that node number $j$ is not connected to node number $i$.
if an entry $i,j$ has a '1' in it, it means that node number $j$ is connected to node number $i$.
(the diagonal's entries contain '1's)
I was asked to find a method that determines whether there is a path between two given nodes $i$ and $j$.
I noticed that if I power the matrix then the entry $i,j$ doesn't equal to '0'. Does it always work like this? Is there a different way of solving this problem?
**This is a question I was asked to program, therefore I've heard of recursive solutions..but I'm trying to find a different answer 
 A: It's true that if you take the $k^{\text{th}}$ power of this matrix (the adjacency matrix of your graph), then its $(i,j)$ entry counts the number of paths of length $k$ from node number $i$ to node number $j$.
This is not an efficient method of testing if $(i,j)$ is connected by a path of any length, because you will have to do many matrix multiplications before you're sure. It's slightly improved by computing $(A+I)^k$ (where $A$ is your adjacency matrix); now the $(i,j)$ entry is $0$ if there are no paths from node $i$ to node $j$ of length $k$ or less, so $(A+I)^{n-1}$ is enough to test if there are any such paths. (And you can compute $(A+I)^{n-1}$ by repeated squaring, without having to compute all the powers in between.)
Better yet is to do a spectral analysis of the Laplacian. The Laplacian matrix $L$ has $L_{ij} = -1$ if there is an edge from node $i$ to node $j$ and $0$ otherwise; also, $L_{ii}$ is the degree of node $i$. This makes all row sums $0$, so $\lambda=0$ is an eigenvalue of $L$. In fact, if you let $C$ be a connected component of your graph, and let $v$ be its indicator vector ($v_i = 1$ if $i \in C$, and $0$ otherwise) then $Lv = 0$. 
So you can find the number of components by just finding the multiplicity of the eigenvalue $0$ (in other words, the dimension of the null space of $L$) and find the components themselves by finding the right eigenbasis: all eigenvectors will be constant on each component, so this is not too hard.
But a simple breadth-first search is better than all of these in general. Maybe you can do better by taking the matrix approach if you want to know the answer for all pairs of nodes $i$ and $j$ at the same time.
