# A multiple-part question about interpreting powers of the adjacency matrix of a graph

Suppose that we have a group of six people, each of whom owns a communication device. We define a $6\times 6$ matrix $A$ as follows: For $1\le i\le 6$, let $a_{ii}=0$; and for $i\ne j$, $$a_{ij}=\begin{cases}1&\text{if person }i\text{ can send a message to person }j\\0&\text{otherwise}\;.\end{cases}$$
(a) Show that $A$ is a $(0,1)$-matrix.
(b) Give an interpretation of what it means for the term $a_{32}a_{21}$ to equal $0$.
(c) Show that the $(3,1)$-entry of $A^2$ represents the number of ways that person $3$ can send a message to person $1$ in two stages $-$ that is, the number of people to whom person $3$ can send a message and who in turn can send a message to person $1$. Hint: Consider the number of terms that are not equal to zero in the expression $$a_{31}a_{11}+a_{32}a_{21}+\ldots+a_{36}a_{61}\;.$$
(d) Generalize your result in (c) to the $(i,j)$-entry of $A^2$.
(e) Generalize your result in (d) to the $(i,j)$-entry of $A^n$.
Now suppose $$A=\begin{bmatrix}0&0&0&1&0&1\\1&0&1&1&0&0\\0&1&0&1&0&0\\1&0&1&0&0&0\\1&1&1&0&0&1\\0&0&1&1&0&0\end{bmatrix}$$
(f) Is there any person who cannot receive a message from anyone else in one stage? Justify your answer.
(g) How many ways can person $1$ send a message to person $4$ in $1,2,3$, and $4$ stages?
(h) The $(i,j)$-entry of $A+A^2+\dots+A^m$ can be shown to equal the number of ways in which person $i$ can send a message to person $j$ in at most $m$ stages. Use this result to determine the number of ways in which person $3$ can send a message to person $4$ in at most $4$ stages.

Also, i have tried making a directed graph of a 6x6 matrix but still confused how to do this problem.

Help is really appreciated, thanks.

-
You can find some good starting points on how to format mathematics on the site here. This AMS reference is very useful. If you need to format more advanced things, there are many excellent references on LaTeX on the internet, including StackExchange's own TeX.SE site. – Zev Chonoles Feb 17 '13 at 0:57
Lastly, using all caps is considered shouting on the internet, and is quite rude. Don't do it again. – Zev Chonoles Feb 17 '13 at 1:03
Ok won't since I am new to this that's why. – First Feb 17 '13 at 1:08

Part (a) is obvious, and parts (b), (f), (g), and (h) are computational. The parts that you’re most likely to have real trouble with are (c), (d), and (e).

(c) The $(3,1)$-entry of $A^2$ is

$$a_{31}a_{11}+a_{32}a_{21}+a_{33}a_{31}+a_{34}a_{41}+a_{35}a_{51}+a_{36}a_{61}\;.\tag{1}$$

Each term has the form $a_{3k}a_{k1}$ for some $k\in\{1,2,3,4,5,6\}$. Each entry in $A$ is either $0$ or $1$, so each $a_{3k}a_{k1}$ is either $0\cdot0$, $0\cdot1$, $1\cdot0$, or $1\cdot1$. All of these are $0$ except the last, which is $1$. Thus, the sum $(1)$ is simply the number of non-zero terms in $(1)$. And $a_{3k}a_{k1}=1$ if and only if $a_{3k}=a_{k1}=1$, i.e., if and only if person $3$ can pass a message to person $k$ and person $k$ can pass a message to person $1$. In short, $a_{3k}a_{k1}=1$ if and only if person $3$ can pass a message to person $1$ in two steps with person $k$ as the middleman, and $(1)$ is therefore the total number of ways in which person $3$ can pass a message to person $1$ in two steps.

(d) There was nothing special about persons $3$ and $1$ in part (c); just change $3$ to $i$ and $1$ to $j$ throughout.

(e) To get started, consider the case $n=3$. The $(i,j)$-entry of $A^3$ is

$$a_{i1}^{(2)}a_{1j}+a_{i2}^{(2)}a_{2j}+a_{i3}^{(2)}a_{3j}+a_{i4}^{(2)}a_{4j}+a_{i5}^{(2)}a_{5j}+a_{i6}^{(2)}a_{6j}\;,\tag{2}$$

where $a_{ij}^{(2)}$ denotes the $(i,j)$-entry of $A^2$. Now how many ways are there for person $i$ to pass a message to person $j$ in exactly $3$ steps? The first two steps have to take the message to some person $k$, and then person $k$ has to be able to pass it to person $j$. Thus, we need to have $a_{kj}=1$. We know from (d) that there are $a_{ik}^{(2)}$ different ways for person $i$ to pass a message to person $k$ in two steps, so there are $a_{ik}^{(2)}a_{kj}$ ways for person $1$ to get the message to person $k$ in $2$ steps and have it then transmitted directly to person $j$. Adding up those way over all possible middlemen $k$ gives us the sum $(2)$, and we see that the $(i,j)$-entry of $A^3$ is indeed the number of ways to get a message from person $i$ to person $j$ in exactly $3$ steps.

The same reasoning can be repeated to show that the $(i,j)$-entry of $A^4$, which is

$$a_{ij}^{(4)}=a_{i1}^{(3)}a_{1j}+a_{i2}^{(3)}a_{2j}+a_{i3}^{(3)}a_{3j}+a_{i4}^{(3)}a_{4j}+a_{i5}^{(3)}a_{5j}+a_{i6}^{(3)}a_{6j}$$

is the number of ways to get a message from person $i$ to person $j$ in exactly $4$ steps. In fact, it’s clear that if $a_{ij}^{(n)}$ is the number of ways to get a message from person $i$ to person $j$ in exactly $n$ steps, the same basic argument shows that

$$a_{ij}^{(n+1)}=a_{i1}^{(n)}a_{1j}+a_{i2}^{(n)}a_{2j}+a_{i3}^{(n)}a_{3j}+a_{i4}^{(n)}a_{4j}+a_{i5}^{(n)}a_{5j}+a_{i6}^{(n)}a_{6j}$$

is the number of ways to get a message from person $i$ to person $j$ in exactly $n+1$ steps. That’s the induction step in a proof that for all $n\ge 1$, $a_{ij}^{(n)}$ is the number of ways to get a message from person $i$ to person $j$ in exactly $n$ steps.

-
Thanks for the help. Really appreciated – First Feb 17 '13 at 15:20
@First: You’re welcome. – Brian M. Scott Feb 18 '13 at 2:59

Really not an interesting question - also seems that you haven't tried much on it. Is this homework? Anyway:

Part a is obvious.

Part b means that $a_{3,2} = 0$ or $a_{2,1} = 0$ (i.e. person $3$ cannot send a message to $1$ in two steps through person $2$).

Part c is clear: just multiply to get $(A^2)_{3,1} = a_{3,1}a_{1,1} + \ldots + a_{3,6} a_{6,1}.$ Use part b.

Part d - again, just multiply. Part e is an easy generalization.

Part f - $a_{i,j} = 0$ means $j$ cannot receive a message from $i$ in one step. Simply look for a column of all $0$'s.

Part g, use part e. Part h, it tells you how to do.

-
lyj helps those who help themselves, which you have not shown much inclination to do. If you need more help, be specific about what you need. But first try to follow through on what lyj has told you. – Gerry Myerson Feb 17 '13 at 5:39
I'd like to think I do that! It really depends on the problem, though. Some are actually nontrivial and a full solution is often more helpful than giving hints that basically tell the solution anyway. This one, however, is really a basic exercise – cats Feb 17 '13 at 8:30