Question 4d)
Consider the adjacency matrix $M_{D}$ shown below that represents a graph $G_{D}$. The products of the matrix multiplication $M_{D}^{2}$ and $M_{D}^{3}$ are also given. Unfortunately, you spilled coffee on your notes and some entries in the matrices are unreadable (marked with ?) and so you will not be able to draw the graph (but you realise that doing so is not necessary and, in fact, would be too time consuming and error-prone!)
i. What is the total number of walks starting at node $d$ and ending at node $d$ of length 1 in graph $\mathrm{G}_{\mathrm{D}}$ ?
ii. What is the total number of walks of length 2 in graph $G_{D}$ ?
iii. What is the total number of walks starting at node $b$ and ending at node $c$ of length 3 or less in $G_{D}$ ?
iv. What is the total number of walks starting and ending at node c of length 4 in graph $G_{D}$ ? (You should need to perform less than 5 multiplications.)
Answer
iv. To find the total number of walks starting and ending at node c of length 4 in graph \(G_D\), we need to compute the (3,3) entry of \(M_D^4\). We can use the fact that the (3,3) entry of \(M_D^2\) is 3 and the (3,3) entry of \(M_D^3\) is 6. Then, the (3,3) entry of \(M_D^4\) is \(3^2+2^2+2^2+2^2=\boxed{20}\).
Step 1 ：\(M_D = \begin{pmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & ? \end{pmatrix}\)
Step 2 ：\(M_D^2 = \begin{pmatrix} 3 & 2 & 2 & 2 \\ 2 & 3 & 2 & 2 \\ 2 & 2 & 3 & 2 \\ 2 & 2 & 2 & ? \end{pmatrix}\)
Step 3 ：\(M_D^3 = \begin{pmatrix} 6 & 6 & 6 & ? \\ 6 & 6 & 6 & ? \\ 6 & 6 & 6 & ? \\ ? & ? & ? & ? \end{pmatrix}\)
Step 4 ：i. The total number of walks starting at node d and ending at node d of length 1 is the (4,4) entry of \(M_D\), so the answer is \(\boxed{0}\).
Step 5 ：ii. The total number of walks of length 2 in graph \(G_D\) is the sum of the diagonal entries of \(M_D^2\), so the answer is \(3+3+3+2=\boxed{11}\).
Step 6 ：iii. The total number of walks starting at node b and ending at node c of length 3 or less in \(G_D\) is the sum of the (2,3) entries of \(M_D\), \(M_D^2\), and \(M_D^3\), so the answer is \(1+2+6=\boxed{9}\).
Step 7 ：iv. To find the total number of walks starting and ending at node c of length 4 in graph \(G_D\), we need to compute the (3,3) entry of \(M_D^4\). We can use the fact that the (3,3) entry of \(M_D^2\) is 3 and the (3,3) entry of \(M_D^3\) is 6. Then, the (3,3) entry of \(M_D^4\) is \(3^2+2^2+2^2+2^2=\boxed{20}\).
