Is the matrix by appending all 1 row to the transport coefficient matrix still totally unimodular?

Question

It is already known that the transport flow coefficient matrix (4 sources to 3 targets in this particular example) $$ \begin{bmatrix} 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \end{bmatrix}. $$

My question is after appending an all 1 row to it is it still totally unimodular? $$ \begin{bmatrix} 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{bmatrix}. $$

The problem originates from adding a total transport capacity constraint to the standard transport flow problem. Is it true for a general case of $N$ sources and $M$ targets?

Answer 1

It is still totally unimodular. Here are two proofs.

The direct proof

Here, we are going to work straight from the definition: we look at arbitrary submatrices, and prove that their determinant is $-1$, $0$, or $1$. There is one twist: it's enough if we can say that the determinant of a submatrix is equal (up to sign) to the determinant of a smaller matrix. This works because we can repeat the argument on that smaller matrix - and if we keep going like this, eventually we either stop, or we get to a $1 \times 1$ matrix (and all $1\times 1$ matrices here have determinant $0$ or $1$).

Suppose we are looking at a submatrix where the rows corresponds to sources $s_1, s_2, \dots, s_k$, sinks $t_1, t_2, \dots, t_m$, and the special row: $k+m+1$ rows total. (It must include the special row, because otherwise we have a submatrix of the matrix without the special row, and that matrix is known to be totally unimodular.)

If we do not choose the columns so that every row has at least two $1$'s in it, then we can use cofactor expansion to reduce to a smaller matrix with the same determinant (up to sign). However, two rows both corresponding to sinks or both to sources cannot have $1$'s in the same column. So we need at least $2k$ distinct columns for $s_1, \dots, s_k$, and at least $2m$ distinct columns for $t_1,\dots, t_m$. In order to have $k+m+1 \ge 2k$ and $k+m+1 \ge 2m$, we must have $k=m$, $k=m+1$, or $k=m-1$.

If $k=m+1$, then we have exactly $2k$ columns, so each of the rows corresponding to $s_1, \dots, s_k$ must have exactly two $1$'s in it. That means that those $k$ rows add up to the special row! So the determinant is $0$. Similarly if $k=m-1$, for the rows corresponding to the sinks.

The remaining case is $k=m$: a $2k+1$ by $2k+1$ submatrix. Every row except the special row must still have at least two $1$'s in it. In fact, if a row had three $1$'s in it, then together with the other rows of the same type, it would add up to the special row, and we'd once again get a determinant of $0$. So suppose that every row except the special row has exactly two $1$'s in it. Now there are two cases:

1. If there is a column which is all $0$'s except for the special row, then we can do cofactor expansion along this column to reduce to a smaller matrix.
2. Otherwise, there is a column which has a $1$ in the row corresponding to a source $s_i$, but a $0$ in every row corresponding to a sink (and a $1$ in the special row). Cofactor expansion along this column gives us a sum of two smaller determinants. However, one of those, the minor corresponding to the $1$ in $s_i$'s row, is a $2k \times 2k$ matrix where the rows corresponding to $t_1, \dots, t_k$ add up to the special row - so its determinant is $0$. So the determinant of the $(2k+1)\times (2k+1)$ matrix is equal to the determinant of just one smaller $2k \times 2k$ matrix.

The proof via equitable bi-colorings

Here is a result originally due to Ghouila and Houri; I am taking it from Corollary 4.7 in Integer Programming by Conforti, Cornuéjols, and Zambelli.

Theorem. A matrix $A$ is totally unimodular if and only if every row submatrix $A'$ admits an "equitable bi-coloring": a partition of its rows into "red rows" and "blue rows" such that the sum of all red rows, minus the sum of all blue rows, is a vector whose entries are $0, \pm 1$.

Using this theorem, the proof is quick. Note that the sum of all the rows corresponding to sources is the all-ones vector; the sum of all the rows corresponding to sinks is also the all-ones vector. So for every row submatrix of the matrix in this question:

• If the special row is not included, color all rows red when they correspond to sources and blue when they correspond to sinks. The sum of all red rows has $0,1$ entries, and so does the sum of all blue rows; therefore their difference has $0, \pm1$ entries.
• If the special row is included, color it blue, and color all other rows red. The sum of all red rows has $0,1,2$ entries, so when we subtract the special row, we get $0,\pm1$ entries.