I'm working on a simple Linear Algebra worksheet involving adjacency matrices
I'm given a list of related items, and told to derive the adjacency matrix $A$, which is trivially done.
I am then asked to compute and interpret $A^2$
It's pretty easy to observe and intuit that $A^2$ is all connections that can be made with exactly two "segments". But I am then told to
Use the definition of matrix multiplication to explain why the analogous general result holds for any (i,j)-entry of $A^2$.
Which i suppose means I need to prove why what I intuited is true in the general case, but I don't have the faintest Idea how to even start to do that.
For reference:
$$A=\left[ \begin{array}{ccc} 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\\end{array} \right] ~~~~~~~~~~ A^2=\left[ \begin{array}{ccc} 0 & 2 & 1 & 0 & 0 \\ 1 & 0 & 0 & 2 & 1 \\ 0 & 1 & 1 & 1 & 1 \\ 2 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 \\\end{array} \right]$$
I'll talk about the matrix multiplication, and leave it to you to make the graph-theoretic conclusions.
The $(i, j)$ entry of a matrix $AB$ is the dot product of row $i$ of $A$, and column $j$ of $B$. If we let $R_i(A)$ be the $i$th row of $A$ and $C_j(B)$ the $j$th column of $B$, then $(AB)_{i,j} = R_i(A) \cdot C_j(B)$, where $(M)_{i,j}$ is notation for the $(i, j)$ entry of $M$.
In the case of $A^2$, we're using rows and columns of $A$ both times; $(A^2)_{i,j} = R_i(A) \cdot C_j(A)$.
The dot product is a sum of products. More precisely, if the $(i, j)$ entry of $A$ is $a_{i,j}$, the $k$th term of $R_i(A) \cdot C_j(A)$ is $a_{i, k}a_{k, j}$: the $k$th entry in row $i$, times the $k$th entry in row $j$ (the full dot product being a sum from $k = 1$ to $n$, if $A$ has dimensions $n \times n$).
Since the entries in an adjacency matrix are $0$ or $1$, we only get terms $1$ in the dot product when $a_{i, k} a_{k, j} = 1$; when both $a_{i, k} = 1 = a_{k, j}$. Thus, the $(i, j)$ entry of $A^2$ counts $k$ such that $a_{i, k}$ and $a_{k, j}$ are both $1$.