Probar que el polinomio característico de un bipartito gráfica tiene alternando positivos y negativos de los coeficientes de

Question

Es bien sabido que el polinomio característico de un bipartito gráfica es de la forma

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

Puedo demostrar por qué no puede ser cualquier extraño powered coeficientes del polinomio característico, pero no puede encontrar una forma de demostrar que los coeficientes de los términos restantes alternativas signo.

He tratado de trabajar con Sachs Teorema que establece que para un gráfico de $G$ los coeficientes $a_k$ están dadas por

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

donde $L_k$ denota el conjunto de subdiagramas de G se compone sólo de los ciclos y los separe de los bordes, $\omega(S)$ es el número de componentes conectados en S y $c(S)$ es el número de ciclos.

Sin embargo, el recuento de todos los posibles gráficos y sus contribuciones (particularmente con diferentes labellings) ha demostrado ser tedioso y complicado, y me pregunto si hay una mejor manera de acercarse a la prueba de que no he visto todavía.

Gracias!

Answer 1

En primer lugar, si las raíces de un polinomio son reales y positivos, a continuación, sus coeficientes se alternan en signo.

En segundo lugar, si $G$ es bipartita, podemos escribir su matriz de adyacencia en particiones de forma $$ A =\begin{pmatrix}0&B^T\\ B&0 \end{pmatrix}; $$ desde $$ \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} $$ vemos que $A$ $-A$ son similares. Por lo tanto, si $\lambda$ es un autovalor de a $A$ con la multiplicidad $k$, por lo que es $-\lambda$. De ello se desprende que el polinomio característico si el poder de la $x$ veces un producto de términos de la forma $x^2-\lambda^2$.

Su declaración acerca de los coeficientes del polinomio característico es una consecuencia de los dos hechos.