If $A$ is the adjacency matrix for the Graph $G$ and $D$ is the diagonal matrix of degrees, $D-A$ is the laplacian of the graph and $D+A$ is sometimes called the signless laplacian.
I want to prove that a connected graph is bipartite iff $D-A$ is similar to $D+A$.
Note: For the if part I know that if those two are similar, the spectrum of those graphs are the same. Since the graph is connected so the laplacian has just one zero eigenvector and there is a vector $x \neq 0$ with so that:
$$ x^T(D+A)x = \sum_{(i,j) \in E(G)} (x_i+x_j)^2 = 0$$
so $x_i \neq 0$ for all $i$ and using negative and positive elements of this vector I can form the bipartition. I would appreciate your hints on the "only if" part of the proof and also other ways of proving the "if" part.
Best Answer
If the graph is bipartite, choose a bipartition and let $P = P^{-1}$ be the diagonal matrix with $+1$ or $-1$ in the diagonal entries depending on which side of the bipartition we're on.
Because diagonal matrices commute, $PDP^{-1} = PP^{-1}D = D$.
On the other hand, $PAP^{-1} = PAP = -A$: left-multiplying by $P$ negates all the rows corresponding to the $-1$ side of the bipartition, and right-multiplying by $P$ negates all the columns corresponding to the $-1$ side of the bipartition. Each $1$ entry in $A$ corresponds to an edge from the $+1$ side to the $-1$ side, so it gets negated once: either due to its row, or due to its column.
Therefore $P(D+A)P^{-1} = D-A$, and the two matrices are similar.
For the reverse direction, you already have the idea, but I just want to point out that if $$\sum_{(i,j) \in E(G)} (x_i+x_j)^2 = 0$$ then we must have $x_i + x_j = 0$ for all $(i,j) \in E(G)$.
This forces each $x_i$ to be equal to either $x_1$ or $-x_1$, by applying this identity along a path from vertex $1$ to vertex $i$; in particular, we get $x_1$ if the path has even length and $-x_1$ if the path has odd length. We can take the vertices $i$ with $x_1 = x_i$ to be one side of the bipartition, and the other vertices to be the other side; since $x_i + x_j = 0$ for all $(i,j) \in E(G)$, all edges go from one side to the other.
(Alternatively, we can use the $x_i + x_j = 0$ condition to show that if any vertex $i$ is contained in an odd walk, then $x_i = 0$; if the graph is not bipartite, every vertex is contained in such a walk, so $x=0$ and we don't get an eigenvector.)