2
$\begingroup$

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.

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

Not a complete solution, but some thoughts.

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$.

$\endgroup$
1
  • $\begingroup$ Thanks a lot. I have no idea about Graph Theory. Now I will learn. $\endgroup$
    – Jyo
    Mar 20 '19 at 15:16

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.