Skip to main content
MathOverflow

Return to Answer

added 212 characters in body
Source Link
tweetie-bird
tweetie-bird
  • 196
  • 1
  • 12

A graph is bipartite iff the odd powers of the adjacency matrix have all 0's on the diagonal. So this implies that the sum of the $i$-th powers of the eigenvalues is 0 for each odd $i$. Since the adjacency matrix is symmetric, it has real eigenvalues. Thus, the eigenvalues are real numbers $\lambda_1,\dots ,\lambda_n $ with $\sum_{j=1}^n \lambda_j^i = 0$ for each odd $i$.

I am guessing this probably should mean that the nonzero eigenvalues come in pairs of equal magnitude and opposite sign. I wonder if there is a good trick for efficiently proving this sort of thing -- about collections of real numbers satisfying such an infinite family of relations? (If so, I don't know this trick.)

${\bf Edit:}$ Douglas Zare proved my above conjecture as a comment, so it is true for bipartite graphs that the nonzero eigenvalues of the adjacency matrix come in pairs of equal magnitude and opposite sign.

A graph is bipartite iff the odd powers of the adjacency matrix have all 0's on the diagonal. So this implies that the sum of the $i$-th powers of the eigenvalues is 0 for each odd $i$. Since the adjacency matrix is symmetric, it has real eigenvalues. Thus, the eigenvalues are real numbers $\lambda_1,\dots ,\lambda_n $ with $\sum_{j=1}^n \lambda_j^i = 0$ for each odd $i$.

I am guessing this probably should mean that the nonzero eigenvalues come in pairs of equal magnitude and opposite sign. I wonder if there is a good trick for efficiently proving this sort of thing -- about collections of real numbers satisfying such an infinite family of relations? (If so, I don't know this trick.)

A graph is bipartite iff the odd powers of the adjacency matrix have all 0's on the diagonal. So this implies that the sum of the $i$-th powers of the eigenvalues is 0 for each odd $i$. Since the adjacency matrix is symmetric, it has real eigenvalues. Thus, the eigenvalues are real numbers $\lambda_1,\dots ,\lambda_n $ with $\sum_{j=1}^n \lambda_j^i = 0$ for each odd $i$.

I am guessing this probably should mean that the nonzero eigenvalues come in pairs of equal magnitude and opposite sign. I wonder if there is a good trick for efficiently proving this sort of thing -- about collections of real numbers satisfying such an infinite family of relations? (If so, I don't know this trick.)

${\bf Edit:}$ Douglas Zare proved my above conjecture as a comment, so it is true for bipartite graphs that the nonzero eigenvalues of the adjacency matrix come in pairs of equal magnitude and opposite sign.

added 35 characters in body
Source Link
tweetie-bird
tweetie-bird
  • 196
  • 1
  • 12

TheA graph is bipartite iff the odd powers of the adjacency matrix have all 0's on the diagonal. So this meansimplies that the sum of the $i$-th powers of the eigenvalues is 0 for each odd $i$. Since the adjacency matrix is symmetric, it has real eigenvalues. So Thus, the eigenvalues are real numbers $\lambda_1,\dots ,\lambda_n $ with $\sum_{j=1}^n \lambda_j^i = 0$ for each odd $i$.

I am guessing this probably should mean that the nonzero eigenvalues come in pairs of equal magnitude and opposite sign. I wonder if there is a good trick for efficiently proving this sort of thing -- about collections of real numbers satisfying such an infinite family of relations? (If so, I don't know this trick.)

The odd powers of the adjacency matrix have all 0's on the diagonal. So this means the sum of the $i$-th powers of the eigenvalues is 0 for each odd $i$. Since the adjacency matrix is symmetric, it has real eigenvalues. So the eigenvalues are real numbers $\lambda_1,\dots ,\lambda_n $ with $\sum_{j=1}^n \lambda_j^i = 0$ for each odd $i$.

I am guessing this probably should mean that the nonzero eigenvalues come in pairs of equal magnitude and opposite sign. I wonder if there is a good trick for efficiently proving this sort of thing -- about collections of real numbers satisfying such an infinite family of relations? (If so, I don't know this trick.)

A graph is bipartite iff the odd powers of the adjacency matrix have all 0's on the diagonal. So this implies that the sum of the $i$-th powers of the eigenvalues is 0 for each odd $i$. Since the adjacency matrix is symmetric, it has real eigenvalues. Thus, the eigenvalues are real numbers $\lambda_1,\dots ,\lambda_n $ with $\sum_{j=1}^n \lambda_j^i = 0$ for each odd $i$.

I am guessing this probably should mean that the nonzero eigenvalues come in pairs of equal magnitude and opposite sign. I wonder if there is a good trick for efficiently proving this sort of thing -- about collections of real numbers satisfying such an infinite family of relations? (If so, I don't know this trick.)

Source Link
tweetie-bird
tweetie-bird
  • 196
  • 1
  • 12

The odd powers of the adjacency matrix have all 0's on the diagonal. So this means the sum of the $i$-th powers of the eigenvalues is 0 for each odd $i$. Since the adjacency matrix is symmetric, it has real eigenvalues. So the eigenvalues are real numbers $\lambda_1,\dots ,\lambda_n $ with $\sum_{j=1}^n \lambda_j^i = 0$ for each odd $i$.

I am guessing this probably should mean that the nonzero eigenvalues come in pairs of equal magnitude and opposite sign. I wonder if there is a good trick for efficiently proving this sort of thing -- about collections of real numbers satisfying such an infinite family of relations? (If so, I don't know this trick.)