Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

It is well known that the characteristic polynomial of a bipartite graph is of the form

$\sum_{k=0}^n (-1)^kc_{2k} x^{2k}$ where $c_{2k} \geq 0$.

I can prove why there cannot be any odd powered coefficients in the characteristic polynomial but cannot find a way to prove that the coefficients of the remaining terms alternate sign.

I have tried working with Sachs Theorem which states that for a graph $G$ the coefficients $a_k$ are given by

$a_k(G) = \sum_{S \in L_k} (-1)^{\omega(S)}2^{c(S)}$

where $L_k$ denotes the set of subgraphs of G composed only of cycles and disjoint edges, $\omega(S)$ is the number of connected components in S and $c(S)$ is the number of cycles.

However, counting up all of the possible graphs and their contributions (particularly with different labellings) has proved tedious and tricky and I am wondering if there is a better way to approach the proof which I have not seen yet.

Thanks!

share|improve this question
    
The title is slightly misleading; the polynomial doesn't actually have alternating positive and negative coefficients; "alternating non-negative and non-positive even-numbered coefficients" would be correct, though slightly lengthy :-) –  joriki Dec 20 '12 at 11:59
1  
One thing you could try is use the fact that if $G$ is a bipartite graph and $\lambda$ is an eigenvalue with multiplicity $m$ then $-\lambda$ is also an eigenvalue of $G$ with same multiplicity $m$ along with the fact that the $k'$th coefficient of the charpoly is just the sum of the product of all possible choices of $k$-eigenvalues from the (multi)set of all eigenvalues. –  Jernej Dec 20 '12 at 12:46

1 Answer 1

up vote 4 down vote accepted

First, if the roots of a polynomial are real and positive, then its coefficients alternate in sign.

Second, if $G$ is bipartite we can write its adjacency matrix in partitioned form $$ A =\begin{pmatrix}0&B^T\\ B&0 \end{pmatrix}; $$ since $$ \begin{pmatrix}-I&0\\0&I\end{pmatrix}\begin{pmatrix}0&B^T\\ B&0 \end{pmatrix}\begin{pmatrix}-I&0\\0&I\end{pmatrix} =\begin{pmatrix}0&-B^T\\-B&0\end{pmatrix} $$ we see that $A$ and $-A$ are similar. Hence if $\lambda$ is an eigenvalue of $A$ with multiplicity $k$, so is $-\lambda$. It follows that the characteristic polynomial if a power of $x$ times a product of terms of the form $x^2-\lambda^2$.

Your statement about the coefficients of the characteristic polynomial is a consequence of the above two facts.

share|improve this answer
    
Awesome! Thanks so much –  Melissium Dec 21 '12 at 1:03
    
yes awesome +1... –  draks ... Dec 21 '12 at 9:30

Your Answer

 
discard

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.