Let $K_{r,s}$ denote the complete bipartite graph, defined on $r + s$ vertices $\{v_1,v_2,...,v_r,w_1,...,w_s\}$, with an edge between $v_i$ and $w_j$ for $1 ≤ i ≤ r$ and $1 ≤ j ≤ s$.
- By combinatorial reasoning, give a closed formula for the number of closed walks of length $k$ in $K_{r,s}$.
- Deduce from this formula the eigenvalues for the adjancency matrix of $K_{r,s}$.
Please help me out with this problem. I am new to Combinatorics and I am not so sure of where to start. Thank you in advance!
The number of closed walks of length $k$ in a graph is given by $tr(A^{k})$, where $tr$ represents the trace of the matrix (in this case, the adjacency matrix is $A$). Consider $tr(A) = 0$, as $K_{r, s}$ is a simple graph. So we have no loops.
Now let's diagonalize $A = QDQ^{-1}$, where $Q$ is the eigenbasis matrix and $D$ is the diagonal eigenvalue matrix. The trace function has the property that cyclic permutations of the matrices preserve trace. So $tr(A) = tr(QDQ^{-1}) = tr(Q^{-1}QD) = tr(DQ^{-1}Q)$. As $Q^{-1}Q = I_{n}$, we have $tr(A) = tr(D) = \sum_{i=1}^{n} \lambda_{i}$.
Now what happens if you square $A$? So $tr(A^{2}) = tr(QDQ^{-1} * QDQ^{-1})$. This gives you $tr(A^{2}) = \sum_{i=1}^{n} \lambda_{i}^{2}$, which is the number of closed two-walks in the graph, and also twice the number of edges.
Note as well that $\sum_{i=1}^{n} \lambda_{i}^{k}$ is called the $kth$ spectral moment. It gives you the number of closed walks of length $k$ in the given graph.
Also, note that bipartite graphs have eigenvalues symmetric to the origin. So $\lambda_{i} = -\lambda_{n-i}$.
Now let's look at (1). Since $K_{r, s}$ is bipartite, we have no closed walks of odd length. Otherwise, if we did, it would give us a cycle of odd length, which we can't have. So let's start at $v_{1}$. We can choose $s$ vertices to visit. If we have a two-walk, we must return to $v_{1}$, and so there is only one vertex to choose for the second choice in the two walk. So we have $\sum_{i=1}^{r} s = rs$ closed walks total for vertices in set $V$. Now apply similar reasoning for vertices in set $w$.
So in generalizing this, you want to think about it this way. Given a length $k = 2m$, an even integer, we must end at the vertex we began, so we have $k-1$ selections. Start at your vertex. How many ways can you move to a vertex in the other set? Apply this reasoning recursively. It's pretty clear if we start at a vertex in set $V$, we alternate between choosing $s$ vertices in set $W$, and then $r$ vertices in set $V$. So we get $s^{m}r^{m-1}$ closed walks for a given vertex in $V$. Adding that up for $r$ vertices gives you $s^{m}r^{m}$ closed walks for vertices in $V$. The argument is symmetrical for vertices in $W$.