8
$\begingroup$

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?

Thanks.

  • 3
    You must assume $G$ is connected. In (2.), $m=n$. I don't understand your point (3.).2012-10-27

3 Answers 3

4

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

  • 1
    @user844541: ok, I've filled out the answer a bit.2012-12-04
6

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.

5

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

  • 1
    @user366818: I added the requested details.2018-04-30