Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Since you are new, I want to give you some advice about the site: To get the best possible answers, you should explain what your thoughts on the problem are so far. That way, people won't tell you things you already know, and they can write answers at an appropriate level; also, people are much more willing to help you if you show that you've tried the problem yourself. If this is homework, please add the [homework] tag; people will still help, so don't worry. –  Zev Chonoles Feb 17 '13 at 0:48
    
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
    
"OK WONT SINCE I AM KNEW TO THIS THATS WHY" - You're kidding, right? I am going to edit your comment for you to remove your obnoxious use of all caps. –  Zev Chonoles Feb 17 '13 at 1:09
show 1 more comment

2 Answers

up vote 1 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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 –  lyj Feb 17 '13 at 8:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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