It is well known that a $\{0, \pm 1\}$ matrix $A$ is totally unimodular (TUM) if and only if matrix $A'$ obtained from $A$ by pivoting operation is totally unimodular.
Here pivoting an element $a_{ij}\neq 0$ is defined as first multiplying the row $a_i$ by $1/a_{ij}$ to make $a_{ij}'=1$, and then add row $a_i'$ to the other rows $a_k, k\neq i$ such that $a_{kj}=0$ (same as the elementary row operation).
My question is that for the following matrix, it seems that TUM is not preserved under pivoting.
$A=\begin{pmatrix}
1 &1&1 \\
1&-1&0\\
1&0&0\\
\end{pmatrix}.$
Here $A$ is not TUM since $\begin{pmatrix}
1 &1 \\
1&-1\\
\end{pmatrix}$ has determinant of $-2$.
On the other hand, if we pick $a_{31}$ as the pivot, then after pivoting the first two rows, the matrix reduces to
$A'=\begin{pmatrix}
0 &1&1 \\
0&-1&0\\
1&0&0\\
\end{pmatrix},$
which is TUM.
I think there must be some mistakes in my understanding but I didn't figure out where.
Thanks.
Best Answer
Interesting. I can confirm your calculations ($A$ is not TU, $A'$ is the result of the named pivot, $A'$ is TU).
The source of the confusion may be Proposition 2.1 of section III.2 of "Integer and Combinatorial Optimization" by Nemhauser and Wolsey. The proposition lists eight statements that is says are equivalent, the first being that "$A$ is TU" and the eighth being that "[a] matrix obtained by a pivot operation on $A$ is TU". The only portion for which they offer a proof is that pivoting in a TUM matrix yields a TUM matrix.
The fourth of their eight "equivalent" statements is that "[a] matrix obtained by deleting a row (column) of $A$ is TU". Deleting the second column of your $A$ results in $$ A^{\prime\prime}=\left(\begin{array}{cc} 1 & 1\\ 1 & 0\\ 1 & 0 \end{array}\right), $$ which is clearly TU (the $2\times 2$ determinants being -1, -1 and 0). So, again, we have implication in one direction (dropping a row/column from a TU matrix leaves a TU matrix) but not in the reverse direction (getting a TU matrix does not imply starting from a TU matrix).
I looked around but could not find a published errata for "Integer and Combinatorial Optimization".