Prove that $(i,j)$ entry in $A(X)^2$ is the number of length $2$ walk from vertex $i$ to vertex $j$

Question

I want to prove that the $(i,j)$ entry in $A(X)^2$ is the number of length $2$ walk from vertex $i$ to vertex $j$ and in general that $A(X)^k$ is the number of length $k$ walks from $i \to j$ where $A(X)$ is the adjacency matrix of a graph $G$.

First, I write $$A(X) = \begin{bmatrix} x_{11} & x_{12} & x_{13} & \dots & x_{1n} \\ x_{21} & x_{22} & x_{23} & \dots & x_{2n} \\ {.} \\ . \\ . \\ x_{n1} & x_{d2} & x_{d3} & \dots & x_{nn} \end{bmatrix}$$

where each $x_{ij} = 1$ or $0$ where $1 \leq i,j \leq n$
and $x_{ij} = 1$ if there is an edge $\{i,j\}$, else $x_{ij} = 0$

Now I am only considered with undirected graphs and so $x_{ij} = x_{ji}$ and so $A(X)^T = A(X)$

Now we take a look at the first entry in the matrix $A(X)^2$, It will be equal to $$x_{11}^2 + x_{12} \times x_{21} + x_{13} \times x_{31} + ... + x_{1n} \times x_{n1}$$

Now since we showed that $x_{ij} = x_{ji}$ then this is also equal to $$x_{11}^2 + x_{12}^2 + x_{13}^2 + ... + x_{1n}^2$$.

Now it's obvious that each of these terms is either $0$ or $1$, For instance $x_{11}^2 = 1 \iff x_{11} = 1$ and we notice that each of these terms also correspond to a length of walk $2$ for instance $x_{12}^2 = 1$ means that path of length $2$ that is $1 \to 2 \to 1$ and so summing all over is the total number of walks of length $2$, Now How can I generalise all this to all other entries. It seems very tedious and is there an easier to way to come up with the general case, Maybe induction of some kind.

Answer 1

Let $c_{ij}$ be the $(i,j) $-th entry of $A^2$. By definition $$c_{ij}=\sum_{k=1}^na_{ik}a_{kj},$$ where $a_{ik}$ and $a_{kj}$ are the $(i,k)$-th and $(k,j)$-th entry of $A$ respectively. Each of these entries are either $0$ or $1$ depending on the adjacency conditions. So each of the product $a_{ik}a_{kj}=1$ if and only if both $a_{ik}=a_{kj}=1$. But these entries are $1$ if and only if there is an edge between $i$ and $k$ and an edge between $k$ and $j$, which is equivalent to having a walk of length $2$ between $i$ and $j$ with interior vertice $k$.

Thus each product entry $a_{ik}a_{kj}=1$ contributes $1$ to the value of $c_{ij}$ if and only if there is a walk of length two between $i$ and $j$. Thus $c_{ij}$ counts the number of walks of length $2$.

Answer 2

It's exactly the same sort of reasoning. Choose any vertices $i, j \in \{1, \ldots, n\}$. Observe that we can partition the set of all length $2$ paths from $i$ to $j$ into $n$ exhaustive and mutually exclusive classes according to the middle vertex $v$. For each $v \in \{1, \ldots, n\}$, the number of paths of the form $i \to v \to n$ is precisely $x_{iv} \cdot x_{vn}$. Summing over all possible $v$, we obtain: $$ \sum_{v=1}^n x_{iv} x_{vj} $$ But this is precisely the $(i, j)$ entry in $A(x)^2$.