I'm working on a 2 part problem that reads as follows:
Let Π be the transition matrix corresponding to simple random walk on a connected graph G.
(a) Prove that 1 is an eigenvalue of Π.
(b) Prove that if G is bipartite (and each partition class contains at least one vertex) then -1 is an eigenvalue of Π.
I've proven part a by using an argument based on the existence of a stationary distribution for such a transition matrix.
For part b I think i want to make an argument about a distribution that moves between the 2 sets of vertices V and W of G in such a way that it returns to itself after 2 steps. However the issue I am having is that any non-zero eigenvector yields after 1 step a distribution vector with negative entries, which we cant have.
Am I at least approaching the problem in the right way or am I completely off the mark? Help very much appreciated.
for part 1
$\Pi \mathbf 1 = \mathbf 1$
so there is an eigenvalue of 1 (which is dominant root for stochastic matrix). Perron Frobenius theory says that the multiplicity of this (simple) root tells you the number of communicating classes; the graph is connected so the multiplicity is one. Call this $\lambda_1 = 1$
for part 2
consider $C:= \Pi^2$
Show that being $\Pi$ Bipartite means $C$ is the transition matrix for two distinct communicating classes, thus the Perron root multiplicity is 2. But $\Pi$ only had a single root equal to one.
So if
$\Pi^2 \mathbf x =\lambda_2 \Pi \mathbf x= \lambda_2^2 \cdot \mathbf x= 1 \cdot \mathbf x$
i.e. $\lambda_2^2 -1 =0$ so what must $\lambda_2$ be?
addendum:
if you are less familiar with some of the details of Perron Frobenius theory, here's another way to approach part 2:
reason that since you are doing a simple random walk on a connected graph, your markov chain is reversible, which implies that all eigenvalues are real. See e.g. here
If $P$ is the transition matrix of a reversible Markov chain, why are its eigenvalues real?
but since this graph is bipartite, there are no same 'color' visits (i.e. bipartite graph being 2 colored) on odd powers of your transition matrix, and in particular there are no cycles then, so
$\text{trace}\big(\Pi^{2k+1}\big)=0$ for all k.
(You can make the following precise if you are comfortable with analytic arguments...)
recalling that $\text{trace}\big(\Pi^{2k+1}\big) = \sum_{j=1}^n \lambda_j^{2k+1}$
but for $k$ large enough, contributions from eigenvalues who absolute value is less than one tends to zero, so the only way the trace can be zero for very large powers of k is if there is something to 'offset' +1, and that is -1, because $1^{2k+1} +(-1)^{2k+1} = 0$