Prove that $(i,j)$ entry in $A(X)^2$ is the number of length $2$ walk from vertex $i$ to vertex $j$ 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.
 A: 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$.
A: 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$.
