# Characterize graph by its connectivity matrix

Let $A$ be an $n\times n$ symmetric matrix, all of whose entries are $1$ or zero. Such a matrix is associated with an undirected graph $G$ with $n$ nodes, in which there is an edge between nodes $i$ and $j$ if and only if $A_{ij}=1$.

If $A_{ii}=1$, there is an edge connecting node $i$ to itself; such an edge is called a "self-loop". In the following we assume that all nodes have self-loops, that is, that $A_{ii}=1$ for all $i$. Keep this in mind as you answer the following questions!

1. In terms of the graph $G$, what is the interpretation of the $ij$ element of the matrix $A^m$, where $m$ is any positive integer.
2. Considering the above, how can the matrix $A^m$ be used to determine the set of nodes of $G$ within $m$ steps along the edges of $G$ from any given node?
3. How can the matrix $A^{n-1}$ be used to tell whether the graph $G$ is connected or not? (Recall that $n$ is the number of nodes of $G$.)

Here are my answers, perhaps you could comment on whether they are correct:

1. It is the number of distinct methods of starting at $i$, moving $m$ times, and winding up at $j$.
2. These are all $j$ such that $(A^m)_{ij}\neq 0$.
3. $A$ is not connected $iff$ $A^{n-1}$ has any zero entries.
• Isn't the connectivity matrix same as the adjacency matrix? – Omar Shehab Jul 17 '14 at 18:52