Number of Walks in a graph in terms of the eigenvalues and eigenvectors of the adjacency matrix I am reading "Algebraic Combinatorics" by Richard Stanley and had a question about one of the corollaries.
It states that given the adjacency matrix, $A(G)$ of the graph $G$, denote $\lambda_1, \lambda_2, \cdots \lambda_n$ as the eigenvalues and $v_1, v_2, \cdots v_n$ as the corresponding eigenvectors.
Then, if we set up the orthogonal matrix, $U$, with its columns being the eigenvectors, the value of the $(i, j)$ input in $A(G)^{\ell}$ can be expressed as: $$[A(G)^{\ell}]_{i,j} = \sum_{k=1}^n (u_{ik}u_{jk}\lambda_k^{\ell}).$$
However, when I tried to follow the proof, I got something a little different, namely: $$[A(G)^{\ell}]_{i,j} = \sum_{k=1}^n (u_{ki}u_{kj}\lambda_k^{\ell})$$ and cannot figure out where I went wrong.
Here is my work:
From basic linear algebra, we know that $U$ diagonalizes $A(G)$.
Hence, $$U^{-1} \cdot A(G) \cdot U = diag( \lambda_1, \lambda_2 \cdots \lambda_n).$$
Rewriting, we get: $$A(G) = U \cdot diag( \lambda_1, \lambda_2 \cdots \lambda_n) \cdot U^{-1}.$$
Now, we need $A(G)^{\ell}.$ It is a known fact that we can rewrite the above equation to: $$A(G)^{\ell} = U \cdot diag( \lambda_1^{\ell}, \lambda_2^{\ell} \cdots \lambda_n^{\ell}) \cdot U^{-1}.$$
Now, we need to do matrix multiplication to get the $(i, j)$ index.
When we do $U \cdot  diag( \lambda_1^{\ell}, \lambda_2^{\ell} \cdots \lambda_n^{\ell})$, the result is a matrix where the value at $(i, j)$ is: $$u_{i, j} \cdot \lambda_i^{\ell}.$$
Now, we must multiply this matrix by $U^{-1}.$ Since $U$ is orthogonal (this is another known fact that the matrix with columns being the eigenvectors are orthogonal), $U^t = U^{-1}.$
If we let matrix $W = U \cdot diag( \lambda_1^{\ell}, \lambda_2^{\ell} \cdots \lambda_n^{\ell})$, then we can write the $(i, j)$ index of $W \cdot U^{-1}$ as: $$\sum_{k=1}^n (W_{k, j} \cdot U^t_{i, k}) = \sum_{k=1}^n (W_{k, j} \cdot U_{k, i}) = \sum_{k=1}^n (u_{k, j} \cdot \lambda_k^{\ell} \cdot u_{k, i}).$$
The textbook didn't show any work for these computations but got: $$\sum_{k=1}^n (u_{j, k} \cdot \lambda_k^{\ell} \cdot u_{i, k}).$$
Where did I go wrong?
 A: In general, both of your mistakes seem to stem from an incorrect definition of matrix multiplication. The correct definition is that $$(AB)_{ij} = a_{i1}b_{1j} + a_{i2} b_{2j} + \dots + a_{in} b_{nj} = \sum_{k=1}^n a_{ik} b_{kj}.$$
Here's the computation in more detail. Let $\Lambda = \text{diag}(\lambda_1, \dots, \lambda_n)$.
If we multiply $U \Lambda^\ell$, the $(i,j)$ entry of the result is actually $$\sum_{k=1}^n u_{ik} (\Lambda^\ell)_{kj} = u_{ij} (\Lambda^\ell)_{jj} = u_{ij} \lambda_j^\ell$$ and not $u_{ij} \lambda_i^\ell$. The first expression is the definition of matrix multiplication. To go from the first expression to the second, note that $\Lambda^\ell$ is a diagonal matrix, and therefore $(\Lambda^\ell)_{kj} = 0$ unless $k=j$. The third is just simplification.
From there, the $(i,j)$ entry of $U \Lambda^\ell U^{-1} = U \Lambda^\ell U^{\mathsf T}$ can be found as
$$
    \sum_{k=1}^n (U \Lambda^\ell)_{ik} (U^{\mathsf T})_{kj} = \sum_{k=1}^n (U \Lambda^\ell)_{ik} u_{jk} = \sum_{k=1}^n (u_{ik} \lambda_k^\ell) u_{jk}
$$
which is what the book states. The first expression is the definition of matrix multiplication. To go from the first to the second, we replace the $(k,j)$ entry of $U^{\mathsf T}$ by the $(j,k)$ entry of $U$. To go from the second to the third, we substitute the expression obtained earlier.

There's another way to do the whole operation at once:
$$
    (U \Lambda^\ell U^{\mathsf T})_{ij} = \sum_{a=1}^n \sum_{b=1}^n u_{ia} (\Lambda^\ell)_{ab} (U^{\mathsf T})_{bj}.
$$
Here, $(\Lambda^\ell)_{ab}$ is $0$ unless $a=b$, so we can set $a=b=k$ and rewrite this as
$$
    \sum_{k=1}^n u_{ik} (\Lambda^\ell)_{kk} (U^{\mathsf T})_{kj} = \sum_{k=1}^n u_{ik} \lambda_k^\ell u_{jk}.
$$
