Let $G$ be an undirected graph with $n$ vertices. $G$ may have loops, cycles or multiple edges.
Here is my question: is there an invariant defined only in terms of some matrix associated to $G$, which would tell whether the graph $G$ is bipartite?
I am looking forward to any comments.
EDIT: Theorem 8.2.1 of "Algebraic Graph Theory" by Chris Godsil and Gordon Royle yields an elementary answer:
Let $B$ be the incidence matrix of a simple graph $G$ with $n$ vertices. Assume for simplicity that $G$ is connected. Then $G$ is bipartite if and only if the rank of $B$ is $n-1$.
This statement generalizes directly to graphs of the form above (that is $G$ may have multiple edges or loops).