Prove the the given matrix is totally unimodular

matricestotal-unimodularityunimodular-matrices

I need to prove following matrix is totally unimodular:
first matrix

I know that I can delete the second, sixth and ninth columns, and then the sixth row, since each of them contains only one non-zero number, and I got to this matrix:

$\hskip 1.7 in$second matrix

I don't know how to continue from here: The matrix is too big tin order to use the definition, and in each row and column there are more then two non-zero numbers, so I can't use the row/column partition method.

How can I show it?

Best Answer

The following result is mentioned in section 8 of Fulkerson and Gross and also in Wikipedia:

The consecutive-ones property: if $A$ is (or can be permuted into) a 0-1 matrix in which for every row, the 1s appear consecutively, then $A$ is TU. (The same holds for columns since the transpose of a TU matrix is also TU.)

Related Question