Skip to main content
fixed error
Source Link
Chris Godsil
  • 12.1k
  • 5
  • 37
  • 61

The rank of the incidence matrix is $|V|$ minus the number of bipartite components. I assume the graph is connected. If it is not bipartite, it follows that the row space is $\mathbb{R}^{V}$ and hence it contains the all-ones vector. If the graph is bipartite, the vector that is 1 on the vertices in the first colour class and $-1$ on the other is orthogonal to each row. So the row space is the orthogonal complement to this vector.

[Edit to deal with Tony's point.] If the colour classes are of equal size, this signed vector is orthogonal to the all-ones vector, and thereforeso the all-ones vector is in the row space. Otherwise the all-ones vector is not orthogonal to our signed vector, and so it does not lie in the row space.

In summary if a connected graph is not bipartite, or bipartite with colour classes of equal size, the row space contains the all-ones vector. Otherwise it does not.

The rank of the incidence matrix is $|V|$ minus the number of bipartite components. I assume the graph is connected. If it is not bipartite, it follows that the row space is $\mathbb{R}^{V}$ and hence it contains the all-ones vector. If the graph is bipartite, the vector that is 1 on the vertices in the first colour class and $-1$ on the other is orthogonal to each row. So the row space is the orthogonal complement to this vector, and therefore it contains the all-ones vector.

The rank of the incidence matrix is $|V|$ minus the number of bipartite components. I assume the graph is connected. If it is not bipartite, it follows that the row space is $\mathbb{R}^{V}$ and hence it contains the all-ones vector. If the graph is bipartite, the vector that is 1 on the vertices in the first colour class and $-1$ on the other is orthogonal to each row. So the row space is the orthogonal complement to this vector.

[Edit to deal with Tony's point.] If the colour classes are of equal size, this signed vector is orthogonal to the all-ones vector, and so the all-ones vector is in the row space. Otherwise the all-ones vector is not orthogonal to our signed vector, and so it does not lie in the row space.

In summary if a connected graph is not bipartite, or bipartite with colour classes of equal size, the row space contains the all-ones vector. Otherwise it does not.

Source Link
Chris Godsil
  • 12.1k
  • 5
  • 37
  • 61

The rank of the incidence matrix is $|V|$ minus the number of bipartite components. I assume the graph is connected. If it is not bipartite, it follows that the row space is $\mathbb{R}^{V}$ and hence it contains the all-ones vector. If the graph is bipartite, the vector that is 1 on the vertices in the first colour class and $-1$ on the other is orthogonal to each row. So the row space is the orthogonal complement to this vector, and therefore it contains the all-ones vector.