2
$\begingroup$

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$

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

No knowledge of the adjacency matrix or its eigenvalues is necessary, and in fact a slight variation of this argument (where we count closed walks) can be used to compute the eigenvalues of the adjacency matrix.

$\endgroup$
1
  • $\begingroup$ XD ! I wonder why I missed simple combinatorics and pushed for algebraic manipulations !! Thanks $\endgroup$
    – Snowflake
    Oct 7, 2023 at 20:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .