= Total unimodularity of directed incidence matrices
{title2=$B_{ve}=\mathbf1_{v=\mathrm{head}(e)}-\mathbf1_{v=\mathrm{tail}(e)}$}
The directed vertex-edge <incidence matrix> has one $+1$ and one $-1$ per nonloop column and a zero column for a loop. Every square subdeterminant belongs to $\{0,1,-1\}$. Induct on its size: a column with no nonzero entries makes the <determinant> zero; a column with one nonzero entry permits a cofactor expansion to a smaller <determinant>; and if every column has two nonzero entries, their opposite signs make the column sums zero, giving linearly dependent rows. Negating rows preserves absolute subdeterminants. Consequently the unsigned vertex-edge incidence <matrix> of a <bipartite graph> is totally unimodular: negate all rows in one part. The <assignment problem> is an instance, with row vertices and column vertices forming the two parts.
Back to article page
