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.
  • $\begingroup$ Isn't the connectivity matrix same as the adjacency matrix? $\endgroup$ – Omar Shehab Jul 17 '14 at 18:52

I think your answers are correct.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.