# Sum of squares of column sums of an orthogonal matrix OR alternative method

This question pertains to finding the total number of walks of length $$l$$ in the complete graph $$K_p$$

The question is from Algebraic Combinatorics by Richard Stanley

I know that the number of walks of length $$l$$ from vertex $$v_i$$ to vertex $$v_j$$ is given by the $$(i,j)-th$$ entry of the matrix $$(A_G)^l$$ where $$A_G$$ denotes the adjacency matrix of a graph $$G$$

I also know that $$((A_G)^l)_{ij}=c_1\cdot(\lambda_1)^l+c_2\cdot(\lambda_2)^l+\dots+c_n\cdot(\lambda_n)^l$$ where all the $$\lambda_i's$$ denote the eigen values of the matrix $$A_G$$ and $$c_i's$$ are all real numbers which happen to be given by $$c_t=u_{it}\cdot u_{jt}$$ where $$U=(u)_{ij}$$ is the matrix which diagonalizes $$A=A_G$$ as $$U^{-1}AU=diag{\hspace{0.1cm}{ \lambda_1,\lambda_2,...,\lambda_n }}$$ by the spectral theorem and hence U contains the orthonormal eigen vectors of $$A$$

The p eigen values of $$A_{K_p}$$ are $$-1,-1,\dots,-1,(p-1)$$

So, I find that total number of length $$k$$ walks in $$G$$ will be $$\sum_{i=1}^p\sum_{j=1}^{p}\left[(-1)^l\left(u_{i1}u_{j1}+u_{i2}u_{j 2}+\dots+u_{i,(p-1)}u_{j,(p-1)}\right)+(p-1)u_{ip}u_{jp} \right]$$

Adding and subtracting, and doing few algebraic manipulations gives me $$\sum_{t=1}^p\sum_{i=1}^p\sum_{j=1}^{p}(-1)^lu_{it}u_{jt}+\sum_{i=1}^p\sum_{j=1}^{p}(p-1-(-1)^l)u_{ip}u_{jp}$$

I notice that $$\sum_{i=1}^p\sum_{j=1}^{p}u_{it}u_{jt}=\left(\sum_{i=1}^p u_{it}\right)^2$$

Thus, this corresponds to my original question of sum of squares of column sums.

Also, I dont feel like this is a good approach because even if I figure out the sum of squares of column sums, I will be stuck with the other part of the total sum. Could someone guide me and help me with the right approach ?

The right answer is

$$p(p-1)^l$$

Your argument is overkill. The total number of walks of length $$\ell$$ can be counted directly: there are $$p$$ choices for the starting vertex and then, at each step of the walk, $$p - 1$$ choices for the next vertex. So there are $$p(p - 1)^{\ell}$$ total walks.