Every entry is a square submatrix of size \(1\), and therefore has determinant (and value) \(0\) or \(\pm 1\).

Any square submatrix of \(B\) is a submatrix of \(A\), so its determinant is \(0\) or \(\pm 1\). Thus, \(B\) is TU.

A submatrix \(T\) of \(A^{T}\) is a transpose of a submatrix of \(A\), so \(\det T \in \{ 0, \pm 1\} \).

Let \(T\) be a square submatrix of \(C\), and suppose \(A\) is TU. If \(T\) contains a zero row, then \(\det T = 0\). Otherwise \(T\) is a submatrix of \(A\), so \(\det T \in \{ 0, \pm 1\} \). For the other direction, because \(A\) is a submatrix of \(C\), we can apply lemma 3.

Let \(T\) be a square submatrix of \(C\), and suppose \(A\) is TU. If \(T\) contains the \(\pm 1\) entry of the unit row, then \(\det T\) equals the determinant of some submatrix of \(A\) times \(\pm 1\), so \(\det T \in \{ 0, \pm 1\} \). If \(T\) contains some entries of the unit row except the \(\pm 1\), then \(\det T = 0\). Otherwise \(T\) is a submatrix of \(A\), so \(\det T \in \{ 0, \pm 1\} \). For the other direction, simply note that \(A\) is a submatrix of \(C\), and use lemma 3.

Gaussian elimination. Basis submatrix: its columns form a basis of all columns, its rows form a basis of all rows.

Any square submatrix \(T\) of \(A\) has the form

where \(T_{1}\) and \(T_{2}\) are submatrices of \(A_{1}\) and \(A_{2}\), respectively.

• If \(T_{1}\) is square, then \(T_{2}\) is also square, and \(\det T = \det T_{1} \cdot \det T_{2} \in \{ 0, \pm 1\} \).

• If \(T_{1}\) has more rows than columns, then the rows of \(T\) containing \(T_{1}\) are linearly dependent, so \(\det T = 0\).

• Similar if \(T_{1}\) has more columns than rows.

Let \(T\) be a square submatrix of \(C\). If \(T\) contains the same row twice, then the rows are \(\mathbb {Z}_2\)-dependent, so \(\det T = 0\). Otherwise \(T\) is a submatrix of \(A\), so \(\det T \in \{ 0, \pm 1\} \).

Either repeatedly apply Lemmas 5, 6, and 9 or perform a similar case analysis directly.

\(C^{T}\) is TU by Lemma 10 and construction, so \(C\) is TU by Lemma 4.

• By Lemma 7 \(A\) is TU iff every basis matrix of \(\left[ I \mid A \right]\) has determinant \(\pm 1\). The same holds for \(A'\) and \(\left[ I \mid A' \right]\).

• Determinants of the basis matrices are preserved under elementary row operations in \(\left[ I \mid A \right]\) corresponding to the pivot in \(A\), under scaling by \(\pm 1\) factors, and under column exchange, all of which together convert \(\left[ I \mid A \right]\) to \(\left[ I \mid A' \right]\).

Reverse the row operations, scaling, and column exchange in the proof of Lemma 13.

• If \(A\) is not square, then since all its proper submatrices are TU, \(A\) is TU, contradiction.

• If \(\det A \in \{ 0, \pm 1\} \), then all subdeterminants of \(A\) are \(0\) or \(\pm 1\), so \(A\) is TU, contradiction.

• If \(A\) is \(2 \times 2\) and it contains a \(0\), then \(\det A \in \{ \pm 1\} \), which contradicts the previous item.

• Let \(A''\) denote matrix \(A\) after the pivot, but before the pivot row and column are deleted.

• Since \(A\) is not TU, Lemma 14 implies that \(A''\) is not TU. Thus \(A'\) is not TU by Lemma 8.

• Let \(T'\) be a proper square submatrix of \(A'\). Let \(T''\) be the submatrix of \(A''\) consisting of \(T'\) plus the pivot row and the pivot column, and let \(T\) be the corresponding submatrix of \(A\) (defined by the same row and column indices as \(T''\)).

• \(T\) is TU as a proper submatrix of \(A\). Then Lemma 13 implies that \(T''\) is TU. Thus \(T'\) is TU by Lemma 3.

todo: extract into lemmas about TU matrices Let \(B\), \(B_{1}\), and \(B_{2}\) be the representation matrices of \(M\), \(M_{1}\), and \(M_{2}\), respectively.

• Converse direction. Let \(B'\) be a TU signing of \(B\). Let \(B_{1}'\) and \(B_{2}'\) be signings of \(B_{1}\) and \(B_{2}\), respectively, obtained from \(B\). By Lemma 3, \(B_{1}'\) and \(B_{2}'\) are both TU, so \(M_{1}\) and \(M_{2}\) are both regular.

• Forward direction. Let \(B_{1}'\) and \(B_{2}'\) be TU signings of \(B_{1}\) and \(B_{2}\), respectively. Let \(B'\) be the corresponding signing of \(B\). By Lemma 8, \(B'\) is TU, so \(M\) is regular.

Let \(B_{1}'\) and \(B_{2}'\) be TU signings of \(B_{1}\) and \(B_{2}\), respectively. In particular, let \(A_{1}'\), \(x'\), \(A_{2}'\), and \(y'\) be the signed versions of \(A_{1}\), \(x\), \(A_{2}\), and \(y\), respectively. Let \(B'\) be the signing of \(B\) where the blocks of \(A_{1}\) and \(A_{2}\) are signed as \(A_{1}'\) and \(A_{2}'\), respectively, and the block of \(D\) is signed as \(D' = y' \cdot x'\) (outer product).

Note that \(\left[ A_{1}' / D' \right]\) is TU by Lemma 10, as every row of \(D'\) is either zero or a copy of \(x'\). Similarly, \(\left[D' \mid A_{2}' \right]\) is TU by Corollary 11, as every column of \(D'\) is either zero or a copy of \(y'\). Additionally, \(\left[ A_{1}' \mid 0 \right]\) is TU by Corollary 11, and \(\left[ 0 / A_{2}' \right]\) is TU by Lemma 10.

todo: prove lemma below, separate into statement about TU matrices

Lemma: Let \(T\) be a square submatrix of \(B'\). Then \(\det T \in \{ 0, \pm 1\} \).

Proof: Induction on the size of \(T\). Base: If \(T\) consists of only \(1\) element, then this element is \(0\) or \(\pm 1\), so \(\det T \in \{ 0, \pm 1\} \). Step: Let \(T\) have size \(t\) and suppose all square submatrices of \(B'\) of size \(\leq t - 1\) are TU.

• Suppose \(T\) contains no rows of \(X_{1}\). Then \(T\) is a submatrix of \(\left[D' \mid A_{2}' \right]\), so \(\det T \in \{ 0, \pm 1\} \).

• Suppose \(T\) contains no rows of \(X_{2}\). Then \(T\) is a submatrix of \(\left[A_{1}' \mid 0 \right]\), so \(\det T \in \{ 0, \pm 1\} \).

• Suppose \(T\) contains no columns of \(Y_{1}\). Then \(T\) is a submatrix of \(\left[0 / A_{2}' \right]\), so \(\det T \in \{ 0, \pm 1\} \).

• Suppose \(T\) contains no columns of \(Y_{2}\). Then \(T\) is a submatrix of \(\left[ A_{1}' / D' \right]\), so \(\det T \in \{ 0, \pm 1\} \).

• Remaining case: \(T\) contains rows of \(X_{1}\) and \(X_{2}\) and columns of \(Y_{1}\) and \(Y_{2}\).

• If \(T\) is \(2 \times 2\), then \(T\) is TU. Indeed, all proper submatrices of \(T\) are of size \(\leq 1\), which are \(\{ 0, \pm 1\} \) entries of \(A'\), and \(T\) contains a zero entry (in the row of \(X_{2}\) and column of \(Y_{2}\)), so it cannot be a minimal violation matrix by Lemma 16. Thus, assume \(T\) has size \(\geq 3\).

• . todo: complete proof, see last paragraph of Lemma 11.2.1 in Truemper

Let \(B\), \(B_{1}\), and \(B_{2}\) be the representation matrices of \(M\), \(M_{1}\), and \(M_{2}\), respectively. Apply Lemma 33.