Assume a directed graph $G=(V,E)$ and that it is the graphical representation of a Markov Chain with transition matrix $P$.
Then, the graph vertices stand for the Markov Chain states and edges for valid transitions between states : \begin{equation} (i,j)\in E \;\Leftrightarrow\; P_{ij}>0 \end{equation} where $P_{ij}$ is the probability that next state is $j$ knowing current state is $i$. The transition matrix has then all its rows normalized.
I would like to prove that if $P$ admits $-1$ as eigenvalue, then $G$ is a bipartite graph.
If $-1$ is an eigenvalue of $P$, then there exists a vector $v$ such that : \begin{equation} vP=-v\;\Longleftrightarrow\; \forall\, k\;,\quad -v_{k} = \sum_{i=1}^{n}P_{ik}v_{i}\qquad (1) \end{equation}
I first assume the graph to be $d$ -regular : \begin{equation} P_{ij} = \begin{cases} \frac{1}{d}&,\text{if}\; (i,j)\in E\\ 0&,\text{otherwise} \end{cases} \end{equation} So (1) becomes : \begin{equation} \forall\, k\;,\quad -v_{k} d = \sum_{(i,k)\in E}v_{i} \end{equation}
Let $M$, $\mathcal{S}_{+}$ and $\mathcal{S}_{-}$ be : \begin{equation} \label{eq:33} M = \max_{k}\{\vert v_{k}\vert\}\;,\quad \mathcal{S}_{ + } = \{k\,/\; v_{k} = M \}\;,\quad \mathcal{S}_{-} = \{k\,/\; v_{k} = -M \} \end{equation} Then, for $k\in \mathcal{S}_{+}$ : \begin{equation} k\in \mathcal{S}_{+}\;\Rightarrow\; - Md = \sum_{(i,k)\in E}v_{i}\qquad (2) \end{equation} The only solution for (2) to hold is that \begin{equation} \forall\,i\,/\; (i,k)\in E\;,\quad v_{i} =- M \end{equation} that is to say $i\in\mathcal{S}_{-}$.
So far, this shows that for any vertex in $\mathcal{S}_{+}$, its sole edges are with $\mathcal{S}_{ -}$ vertices, and conversely. In other words, we created a vertex partition : \begin{equation} V = \mathcal{S}_{+ } \cup \mathcal{S}_{ -}\;,\quad \mathcal{S}_{+}\cap \mathcal{S}_{ -} = \emptyset \end{equation} so that \begin{equation} E = \biggl\{(i,j)\,/\; (i\in \mathcal{S}_{+ }\wedge j\in \mathcal{S}_{ -})\vee(i\in \mathcal{S}_{- }\wedge j\in \mathcal{S}_{ +}) \biggr\} \end{equation}
which is the definition of a bipartite graph.
I wonder if it is possible to extend this demonstration to the general case represented by (1) ?
\begin{equation} \forall\, k\;,\quad -v_{k} = \sum_{i=1}^{n}P_{ik}v_{i}\qquad (3) \end{equation} My intuition is that if $v_k$ is "positive enough" in (3), then given that $P_{ik}\ge 0$, all $v_i$ such that $(i,k)\in E$ should be "negative enough" for (3) to hold.
So, I redefine $\mathcal{S}_{+}$ and $\mathcal{S}_{-}$ this way : \begin{equation} m = \min_{k}\{\vert v_{k}\vert\}\;,\quad \mathcal{S}_{ + } = \{k\,/\; v_{k} \ge m \}\;,\quad \mathcal{S}_{-} = \{k\,/\; v_{k} \le -m \} \end{equation}
I should first exclude the case $m=0$, I assume for the moment that $m>0$.
Then, for $k\in\mathcal{S}_+$ : \begin{equation} v_k \ge m\;\Rightarrow\; -v_k \le -m\;\Rightarrow\;\sum_{i=1}^{n}P_{ik}v_{i}\le -m \qquad (4) \end{equation} So, whenever $P_{ik}>0$, $v_{i}$ should be "negative enough" for (4) to hold.
If there is only one $P_{ik}>0$, this clearly shows that $v_i \le -m$ and that $i\in \mathcal{S}_{-}$.
After that, I searched without success. Do you have any hint ?
