Proof of `Consecutive Ones Implies Total Unimodularity`
What this proof establishes
no assumptions
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
In the paper
- page 6 of this submission's paper
Description
Fulkerson–Gross. Sort the chosen columns, which changes the determinant only by a sign; each row of the sorted submatrix is then an interval of ones, and the determinant of such a matrix is , or by induction on subtracting consecutive rows.