# How to form Matrix pairs of $m$ friends and to find common friend from all possible pairs.

The below is a problem given in entrance exam.

Problem: A golf club has $$m$$ members with serial numbers $$1, 2 . . . , m$$. If members with serial numbers $$i$$ and $$j$$ are friends, then $$A(i, j) = A(j, i) = 1$$, otherwise $$A(i, j) = A(j, i) = 0$$. By convention, $$A(i, i) = 0$$, i.e. a person is not considered a friend of himself or herself. Let $$A^k(i, j)$$ refer to the $$(i, j)$$th entry in the $$k^{th}$$ power of the matrix $$A$$. Suppose it is given that $$A^9(i, j) > 0$$ for all pairs $$i,j$$ where $$1 ≤ i,j ≤ m$$, $$A^2(1,2) > 0$$ and $$A^4(1, 3) = 0$$.

Suppose it is given that $$A^9(i,j) > 0$$ for all pairs $$i,j$$ where $$1 ≤ i,j ≤ m, A^2(1,2) > 0$$ and $$A^4(1,3) = 0$$.

Determine if below problem statements are necessarily true and please provide the reasons for it.

1. Does members $$1$$ and $$2$$ have at least one friend in common.
2. $$m≤9$$
3. $$m≥6$$
4. $$A^2(i,i)> 0$$ for all $$i$$, $$1≤i≤m.$$

$$\\$$

My approach: I tried to form the question in $$A(i, j)$$ pairs as per the question.

$$\begin{array}{c|lcr} (i, j) & \text{1} & \text{2} & \cdots \\ \hline 1 & 0 & 1 & \cdots \\ 2 & 1 & 0 & \cdots \\ \vdots & \vdots & \vdots \\ \end{array}$$

Given that $$A^2(1, 2) > 0$$ and $$A$$ gives the below matrix.

$$\left[ \begin{array}{cc|c} 0&1\\ 1&0 \end{array} \right]$$

And $$A^2$$ gives the below matrix.

$$\left[ \begin{array}{cc|c} 1&0\\ 0&1 \end{array} \right]$$

Determinant of this gives 1.

I could not proceed further as I am still not sure if my approach to this problem is correct or not.

Can someone please explain the approach to this problem and also let me know if there exists a book which contains these type of problems which would help me a lot.

• This is my first question so please correct my mistakes if there are any.
– Jyo
Mar 18 '19 at 19:16
• Could you explain more clearly what the question is? I.e, what is demanded in the problem? Mar 18 '19 at 19:42
• @MatijaSreckovic We need to find the least 'm' value and does members 1 and 2 have at least one friend in common.
– Jyo
Mar 18 '19 at 19:45
• This is another one. $A^2(i,i)>0, for all i,1≤i≤m.$
– Jyo
Mar 18 '19 at 19:47
• We need to tell if the given question is true or not and provide a reason for it.
– Jyo
Mar 18 '19 at 19:48

The well-known fact (you can easily prove it by induction) is that $$k$$th power of adjacency matrix $$A$$ is a matrix of pathes that have length $$k$$. Thus, $$A^{k}(i, j)$$ equals to number of pathes from $$i$$ to $$j$$ that have length $$k$$. In this terms, $$A^9(i, j) > 0$$ means there is a path from $$i$$ to $$j$$ of length 9, $$A^2(1, 2) > 0$$ means there is a path from $$1$$ to $$2$$ of length 2, and $$A^4(1, 3) = 0$$ means there is no path from $$1$$ to $$3$$ of length 4. Now, this
members $$1$$ and $$2$$ have at least one friend in common.
immediatly follows from $$A^2(1, 2) > 0$$ as you have a path $$1 \to x \to2$$ and $$x$$ is a common friend for $$1$$ and $$2$$.