Let $X$ be a connected graph with maximum eigenvalue $k$. Assume that $-k$ is also an eigenvalue. I wish to prove that $X$ is bipartite.

Now if $\vec{x}=(x_1,\cdots ,x_n)$ is the eigenvector for $-k$ then I can show that for the vector $\vec{y}$ whose entries are $(|x_1|,\cdots ,|x_n|)$ we have $y'Ay=ky'y$. From here can I conclude that $\vec{y}$ is an eigenvector with eigenvalue $k$?

How to proceed to prove this result?


  • 3
    $\begingroup$ You must assume $G$ is connected. In (2.), $m=n$. I don't understand your point (3.). $\endgroup$ – Colin McQuillan Oct 27 '12 at 7:28

$A$ is symmetric, nonnegative, and irreducible. By a theorem of Perron and Frobenius, $k$ is a simple eigenvalue with a positive eigenvector $u$. Now with componentwise absolute value, $k|x|=|-kx|=|Ax|\le A|x|$. Multiplication with $u^T$ shows that we must have equality. Hence $|x|$ is an eigenvector, hence a multiple of $u$. Therefore $x$ has no zero component.

Partition the nodes into $P$ (of size $p$) and $N$ (of size $n$), where $x_i>0$ if $i\in P$ and $x_i<0$ if $i\in N$. Then $v=x_P>0$ and $w=-x_N>0$. Partition $A$ conformally as $A=\pmatrix{B & C\\C^T & D}$ (of size $p+n\times p+n$, with $B$ of size $p\times p$, and note that $B,C,D$ are nonnegative. Then the equation $|Ax|= A|x|$ implies $|Bv-Cw|=Bv+Cw$ and $|C^Tv-Dw|=C^Tv+Dw$. Taking the squared norm and simplifying yields $(Bv)_i(Cw)_i=0$ for $i\in P$ and $(C^Tv)_k(Dw)_k=0$ for $k\in N$. Since $v,w>0$, $C_{ik}=1$ implies that $B_{ij}=0$ for $j\in P$ and $D_{kj}=0$ for $j\in N$.

This means that for every edge $ik$ with $i\in P$ and $k\in N$, the neighbors of $i$ must lie in $N$ and the neighbors of $k$ must lie in $P$. Growing the graph starting with some such edge implies that its connected component is bipartite. On the other hand, if there is no such edge then $P$ and $N$ are unions of connected components. Since the graph was assumed connected, it follows that it is bipartite.

  • $\begingroup$ I do not follow why $ku'|x|=u'A|x|$ implies that $|x|$ is an eigenvector. Can you explain please? $\endgroup$ – Shahab Nov 13 '12 at 6:28
  • 1
    $\begingroup$ @Shahab: It implies that $k|x|=A|x|$. For if this fails then there is strict inequality in at least one component, and multiplication by $u^T>0$ gives a strict inequality, contradiction. $\endgroup$ – Arnold Neumaier Nov 13 '12 at 10:14
  • $\begingroup$ @ArnoldNeumaier I don't understand how you get the condition $(Bv)_i(Cw)_i = 0$ and additionally what are the dimensions of $B,C,D,v,w$ that this makes sense? It seems to me that it doesn't quite make sense. $\endgroup$ – user366818 Apr 29 '18 at 19:51
  • 1
    $\begingroup$ @user366818: I added the requested details. $\endgroup$ – Arnold Neumaier Apr 30 '18 at 9:34

As Colin noted in a comment, you need to assume that $G$ is connected.

For a $k$-regular graph, $\mathbf A/k$ is the transition matrix of a random walk that uniformly selects one of the $k$ neighbours in each step. If $\mathbf A$ has eigenvalue $-k$, then $\mathbf A/k$ has eigenvalue $-1$. Thus the random walk does not necessarily converge to a stationary distribution. Since $G$ is connected, the Markov chain is irreducible, so there must be a periodic state. In an undirected graph, the only possible period is $2$. Thus the graph decomposes into the sets of vertices that are even and odd with respect to that period, and is thus bipartite.


(This answer is for an older version of the question where the graph is assumed to be $k$-regular.)

Let $(v_1,\dots,v_n)$ be an eigenvector of the adjacency matrix, with eigenvalue $-k$. This means that $$-kv_i = \sum_{j\sim i} v_j$$ for all $i\in V$, where $j\sim i$ means that $i$ and $j$ are adjacent. Let $M=\max_i|v_i|$ and $P=\{i\mid v_i=M\}$ and $N=\{i\mid v_i=-M\}$.

For every $i\in P$ we have $-kM=-kv_i=\sum_{j\sim i} v_j$. But, because $v_j\geq -M$ for all $j$, the only way to achieve $\sum_{j\sim i} v_j = -kM$ is if $v_j=-M$ for all $j\sim i$, or in other words $j\in N$. Similarly for every $i\in N$ we have $j\in P$ for all $j\sim i$. The graph induced by $P\cup N$ is therefore a bipartite connected component.

  • $\begingroup$ Could you please complete the proof or give some more hints? $\endgroup$ – user844541 Dec 3 '12 at 22:54
  • $\begingroup$ @user844541: my answer is for an older version of the question where the graph is assumed to be $k$-regular. For this special case, we can argue that set $\{i\mid |v_i|=\max_j |v_j|\}$ is connected because $-kv_i= \sum_{i\sim j} v_j$, so we can avoid Perron--Frobenius as used in the other answers. $\endgroup$ – Colin McQuillan Dec 4 '12 at 0:30
  • $\begingroup$ I am working with a d-regular graph. I was able to complete the proof based on the assumption that |v1|= |v2|=...=|vn|, but I wasn't able to prove that.. $\endgroup$ – user844541 Dec 4 '12 at 8:06
  • 1
    $\begingroup$ @user844541: ok, I've filled out the answer a bit. $\endgroup$ – Colin McQuillan Dec 4 '12 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.