Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question
You must assume $G$ is connected. In (2.), $m=n$. I don't understand your point (3.). – Colin McQuillan Oct 27 '12 at 7:28
up vote 4 down vote accepted

$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$ and $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}$, 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$. This 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.

share|cite|improve this answer
I do not follow why $ku'|x|=u'A|x|$ implies that $|x|$ is an eigenvector. Can you explain please? – Shahab Nov 13 '12 at 6:28
@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. – Arnold Neumaier Nov 13 '12 at 10:14

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.

share|cite|improve this answer

(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.

share|cite|improve this answer
Could you please complete the proof or give some more hints? – user844541 Dec 3 '12 at 22:54
@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. – Colin McQuillan Dec 4 '12 at 0:30
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.. – user844541 Dec 4 '12 at 8:06
@user844541: ok, I've filled out the answer a bit. – Colin McQuillan Dec 4 '12 at 11:57
Thanks a lot!!! – user844541 Dec 4 '12 at 18:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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