Since \(Q\) is a TU signing of \(S\) and \(Q'\) is obtained from \(Q\) by multiplying rows and columns by \(\pm 1\) factors, \(Q'\) is also a TU signing of \(S\). By construction, we have

Thus, it remains to show that \(Q' (x_{0}, y_{1}) = S' (x_{0}, y_{1})\) and \(Q' (x_{1}, y_{1}) = S' (x_{1}, y_{1})\).

Consider the entry \(Q' (x_{0}, y_{1})\). If \(D_{0} (x_{0}, y_{1}) = 0\), then \(Q' (x_{0}, y_{1}) = 0 = S' (x_{0}, y_{1})\). Otherwise, we have \(D_{0} (x_{0}, y_{1}) = 1\), and so \(Q' (x_{0}, y_{1}) \in \{ \pm 1\} \), as \(Q'\) is a signing of \(S\). If \(Q' (x_{0}, y_{1}) = -1\), then

which contradicts TUness of \(Q'\). Thus, \(Q' (x_{0}, y_{1}) = 1 = S' (x_{0}, y_{1})\).

Consider the entry \(Q' (x_{1}, y_{1})\). Since \(Q'\) is a signing of \(S\), we have \(Q' (x_{1}, y_{1}) \in \{ \pm 1\} \). Consider two cases.

1. Suppose that \(D_{0} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\). If \(Q' (x_{1}, y_{1}) = 1\), then \( \det Q = \det \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix} = -2 \notin \{ 0, \pm 1\} , \) which contradicts TUness of \(Q'\). Thus, \(Q' (x_{1}, y_{1}) = -1 = S' (x_{1}, y_{1})\).

2. Suppose that \(D_{0} = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\). If \(Q' (x_{1}, y_{1}) = -1\), then \( \det Q (\{ x_{0}, x_{1}\} , \{ y_{1}, y_{2}\} ) = \det \begin{bmatrix} 1 & 1 \\ -1 & 1 \end{bmatrix} = 2 \notin \{ 0, \pm 1\} , \) which contradicts TUness of \(Q'\). Thus, \(Q' (x_{1}, y_{1}) = 1 = S' (x_{1}, y_{1})\).

Since \(Q\) is a TU signing of \(Q_{0}\) and \(Q'\) is obtained from \(Q\) by multiplying some rows and columns by \(\pm 1\) factors, \(Q'\) is also a TU signing of \(Q_{0}\). Equality \(Q' (\{ x_{0}, x_{1}, x_{2}\} , \{ y_{0}, y_{1}, y_{2}\} ) = S'\) follows from Lemma 49.

By Lemma 51, \(B_{\ell }''\) and \(B_{r}''\) are TU signings of \(B_{\ell }\) and \(B_{r}\), respectively. As a result, blocks \(A_{\ell }''\), \(A_{r}''\), \(D_{\ell }''\), \(D_{r}''\), and \(D_{0}''\) in \(B''\) are signings of the corresponding blocks in \(B\). Thus, it remains to show that \(D_{\ell r}''\) is a signing of \(D_{\ell r}\). This can be verified via a direct calculation. (Todo: Need details?)

Throughout the proof we use that \(B_{r}''\) is TU, which holds by Lemma 51.

1. Since \(B_{r}''\) is TU, all its entries are in \(\{ 0, \pm 1\} \), and in particular \(\begin{bmatrix} c_{0}” (i) & c_{1}” (i) \end{bmatrix} \in \{ 0, \pm 1\} ^{\{ y_{0}, y_{1}\} }\). If \(\begin{bmatrix} c_{0}’ (i) & c_{1}” (i) \end{bmatrix} = \begin{bmatrix} 1 & -1 \end{bmatrix}\), then

   \[ \det B_{r}'' (\{ x_{2}, i\} , \{ y_{0}, y_{1}\} ) = \det \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} = -2 \notin \{ 0, \pm 1\} , \]

   which contradicts TUness of \(B_{r}''\). Similarly, if \(\begin{bmatrix} c_{0}” (i) & c_{1}” (i) \end{bmatrix} = \begin{bmatrix} -1 & 1 \end{bmatrix} \), then

   \[ \det B_{r}'' (\{ x_{2}, i\} , \{ y_{0}, y_{1}\} ) = \det \begin{bmatrix} 1 & 1 \\ -1 & 1 \end{bmatrix} = 2 \notin \{ 0, \pm 1\} , \]

   which contradicts TUness of \(B_{r}''\). Thus, the desired statement holds.

2. Follows from item 1 and a direct calculation.

3. Performing a short tableau pivot in \(B_{r}''\) on \((x_{2}, y_{0})\) yields:

   \[ B_{r}'' = \begin{bmatrix} \fbox{1} & 1 & 0 \\ c_{0} & c_{1} & A_{r} \end{bmatrix} \quad \to \quad \begin{bmatrix} 1 & 1 & 0 \\ -c_{0} & c_{1}” - c_{0} & A_{r} \end{bmatrix} \]

   The resulting matrix can be transformed into \(\begin{bmatrix} c_{0}” & c_{2}” & A_{r}” \end{bmatrix}\) by removing row \(x_{2}\) and multiplying columns \(y_{0}\) and \(y_{1}\) by \(-1\). Since \(B_{r}''\) is TU and since TUness is preserved under pivoting, taking submatrices, multiplying columns by \({\pm 1}\) factors, we conclude that \(\begin{bmatrix} c_{0}” & c_{2}” & A_{r}” \end{bmatrix}\) is TU.

4. Similar to item 4, performing a short tableau pivot in \(B_{r}''\) on \((x_{2}, y_{1})\) yields:

   \[ B_{r}'' = \begin{bmatrix} 1 & \fbox{1} & 0 \\ c_{0} & c_{1} & A_{r} \end{bmatrix} \quad \to \quad \begin{bmatrix} 1 & 1 & 0 \\ c_{0}” - c_{1} & -c_{1} & A_{r} \end{bmatrix} \]

   The resulting matrix can be transformed into \(\begin{bmatrix} c_{1}” & c_{2}” & A_{r}” \end{bmatrix}\) by removing row \(x_{2}\), multiplying column \(y_{1}\) by \(-1\), and swapping the order of columns \(y_{0}\) and \(y_{1}\). Since \(B_{r}''\) is TU and since TUness is preserved under pivoting, taking submatrices, multiplying columns by \({\pm 1}\) factors, and re-ordering columns, we conclude that \(\begin{bmatrix} c_{1}” & c_{2}” & A_{r}” \end{bmatrix}\) is TU.

5. Let \(V\) be a square submatrix of \(\begin{bmatrix} c_{0}” & c_{1}” & c_{2}” & A_{r}” \end{bmatrix}\). Our goal is to show that \(\det V \in \{ 0, \pm 1\} \).

   Suppose that column \(c_{2}''\) is not in \(V\). Then \(V\) is a submatrix of \(B_{r}''\), which is TU. Thus, \(\det V \in \{ 0, \pm 1\} \). Going forward we assume that column \(z\) is in \(V\).

   Suppose that columns \(c_{0}''\) and \(c_{1}''\) are both in \(V\). Then \(V\) contains columns \(c_{0}''\), \(c_{1}''\), and \(c_{2}'' = c_{0}'' - c_{1}''\), which are linearly. Thus, \(\det V = 0\). Going forward we assume that at least one of the columns \(c_{0}''\) and \(c_{1}''\) is not in \(V\).

   Suppose that column \(c_{1}''\) is not in \(V\). Then \(V\) is a submatrix of \(\begin{bmatrix} c_{0}” & c_{2}” & A_{r}” \end{bmatrix}\), which is TU by item 3. Thus, \(\det V \in \{ 0, \pm 1\} \). Similarly, if column \(c_{0}''\) is not in \(V\), then \(V\) is a submatrix of \(\begin{bmatrix} c_{1}” & c_{2}” & A_{r}” \end{bmatrix}\), which is TU by item 4. Thus, \(\det V \in \{ 0, \pm 1\} \).

Apply Lemma 54 to \(B_{\ell }^{\top }\), or repeat the same arguments up to transposition.

1. Holds by Lemma 54.2.

2. Note that

   \[ \begin{bmatrix} D_{\ell }” \\ D_{\ell r}” \end{bmatrix} = \begin{bmatrix} D_{0}” \\ D_{r}” \end{bmatrix} \cdot (D_{0}'')^{-1} \cdot D_{\ell }'', \quad \begin{bmatrix} D_{0}” \\ D_{r}” \end{bmatrix} = \begin{bmatrix} D_{0}” \\ D_{r}” \end{bmatrix} \cdot (D_{0}'')^{-1} \cdot D_{0}'', \quad \begin{bmatrix} D_{0}” \\ D_{r}” \end{bmatrix} = \begin{bmatrix} c_{0}” & c_{1}” \end{bmatrix}, \quad \begin{bmatrix} D_{\ell }” & D_{0}” \end{bmatrix} = \begin{bmatrix} d_{0}” \\ d_{1}” \end{bmatrix}. \]

   Thus,

   \[ D'' = \begin{bmatrix} D_{\ell }” & D_{0}” \\ D_{\ell r}” & D_{r}” \end{bmatrix} = \begin{bmatrix} D_{0}” \\ D_{r}” \end{bmatrix} \cdot (D_{0}'')^{-1} \cdot \begin{bmatrix} D_{\ell }” & D_{0}” \end{bmatrix} = \begin{bmatrix} c_{0}” & c_{1}” \end{bmatrix} \cdot (D_{0}'')^{-1} \cdot \begin{bmatrix} d_{0}” \\ d_{1}” \end{bmatrix}. \]

   Considering the two cases for \(D_{0}''\) and performing the calculations yields the desired results.

3. Let \(j \in Y_{\ell }\). By Lemma 55.1, \(\begin{bmatrix} d_{0}” (i) \\ d_{1}” (j) \end{bmatrix} \in \{ 0, \pm 1\} ^{\{ x_{0}, x_{1}\} } \setminus \left\{ \begin{bmatrix} 1 \\ -1 \end{bmatrix}, \begin{bmatrix} -1 \\ 1 \end{bmatrix} \right\} \). Consider two cases.

   1. If \(D_{0}'' = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}\), then by item 2 we have \(D'' (X_{r}, j) = d_{0}'' (j) \cdot c_{0}'' + (-d_{1}'' (j)) \cdot c_{1}''\). By considering all possible cases for \(d_{0}'' (j)\) and \(d_{1}'' (j)\), we conclude that \(D'' (X_{r}, j) \in \{ 0, \pm c_{0}'', \pm c_{1}'', \pm (c_{0}'' - c_{1}'')\} \).

   2. If \(D_{0}'' = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\), then by item 2 we have \(D'' (X_{r}, j) = (d_{0}'' (j) - d_{1}'' (j)) \cdot c_{0}'' + d_{1}'' (j) \cdot c_{1}''\). By considering all possible cases for \(d_{0}'' (j)\) and \(d_{1}'' (j)\), we conclude that \(D'' (X_{r}, j) \in \{ 0, \pm c_{0}'', \pm c_{1}'', \pm (c_{0}'' - c_{1}'')\} \).

4. Let \(i \in X_{r}\). By Lemma 54.1, \(\begin{bmatrix} c_{0}” (i) & c_{1}” (i) \end{bmatrix} \in \{ 0, \pm 1\} ^{\{ y_{0}, y_{1}\} } \setminus \left\{ \begin{bmatrix} 1 & -1 \end{bmatrix}, \begin{bmatrix} -1 & 1 \end{bmatrix} \right\} \). Consider two cases.

   1. If \(D_{0}'' = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}\), then by item 2 we have \(D'' (i, Y_{\ell }) = c_{0}'' (i) \cdot d_{0}'' + (-c_{1}'' (i)) \cdot d_{1}''\). By considering all possible cases for \(c_{0}'' (i)\) and \(c_{1}'' (i)\), we conclude that \(D'' (i, Y_{\ell }) \in \{ 0, \pm d_{0}'', \pm d_{1}'', \pm d_{2}''\} \).

   2. If \(D_{0}'' = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\), then by item 2 we have \(D'' (i, Y_{\ell }) = c_{0}'' (i) \cdot d_{0}'' + (c_{1}'' (i) - c_{0}'' (i)) \cdot d_{1}''\). By considering all possible cases for \(c_{0}'' (i)\) and \(c_{1}'' (i)\), we conclude that \(D'' (i, Y_{\ell }) \in \{ 0, \pm d_{0}'', \pm d_{1}'', \pm d_{2}''\} \).

5. By Lemma 55.5, \(\begin{bmatrix} A_{\ell }” \\ d_{0}” \\ d_{1}” \\ d_{2}” \end{bmatrix}\) is TU. Since TUness is preserved under adjoining zero rows, copies of existing rows, and multiplying rows by \(\pm 1\) factors, \(\begin{bmatrix} A_{\ell }” \\ 0 \\ \pm d_{0}” \\ \pm d_{1}” \\ \pm d_{2}” \end{bmatrix}\) is also TU. By item 4, \(\begin{bmatrix} A_{\ell }” \\ D” \end{bmatrix}\) is a submatrix of the latter matrix, hence it is also TU.

Recall that \(c_{0}'' - c_{1}'' \in \{ 0, \pm 1\} ^{X_{r}}\) by Lemma 56.1, so \(\mathcal{C} (X_{\ell }, Y_{\ell }, X_{r}, Y_{r}; c_{0}'', c_{1}'')\) is well-defined. To see that \(B'' \in \mathcal{C} (X_{\ell }, Y_{\ell }, X_{r}, Y_{r}; c_{0}'', c_{1}'')\), note that all properties from Definition 57 are satisfied: property 1 holds by Lemma 56.3, property 2 holds by Lemma 54.5, and property 3 holds by Lemma 56.5.

Our goal is to show that \(C'\) satisfies all properties from Definition 57. Let \(C' = \begin{bmatrix} C_{11}’ & C_{12}’ \\ C_{21}’ & C_{22}’ \end{bmatrix}\), and let \(\begin{bmatrix} A_{\ell }’ \\ D’ \end{bmatrix}\) be the result of performing a short tableau pivot on \((x, y)\) in \(\begin{bmatrix} A_{\ell } \\ D \end{bmatrix}\). Observe the following.

• By Lemma 13, \(C_{11}' = A_{\ell }'\), \(C_{12}' = 0\), \(C_{21}' = D'\), and \(C_{22}' = A_{r}\).

• Since \(\begin{bmatrix} A_{\ell } \\ D \end{bmatrix}\) is TU by property 3 for \(C\), all entries of \(A_{\ell }\) are in \(\{ 0, \pm 1\} \).

• \(A_{\ell } (x, y) \in \{ \pm 1\} \), as \(A_{\ell } (x, y) \in \{ 0, \pm 1\} \) by the above observation and \(A_{\ell } (x, y) \neq 0\) by the assumption.

• Since \(\begin{bmatrix} A_{\ell } \\ D \end{bmatrix}\) is TU by property 3 for \(C\), and since pivoting preserves TUness, \(\begin{bmatrix} A_{\ell }’ \\ D’ \end{bmatrix}\) is also TU.

These observations immediately imply properties 2 and 3 for \(C'\). Indeed, property 2 holds for \(C'\), since \(C_{22}' = A_{r}\) and \(\begin{bmatrix} c_{0} & c_{1} & c_{0} - c_{1} & A_{r} \end{bmatrix}\) is TU by property 2 for \(C\). On the other hand, property 3 follows from \(C_{11}' = A_{\ell }'\), \(C_{21}' = D'\), and \(\begin{bmatrix} A_{\ell }’ \\ D’ \end{bmatrix}\) being TU. Thus, it only remains to show that \(C'\) satisfies property 1. Let \(j \in Y_{r}\). Our goal is to prove that \(D' (X_{r}, j) \in \{ 0, \pm c_{0}, \pm c_{1}, \pm (c_{0} - c_{1})\} \).

Suppose \(j = y\). By the pivot formula, \(D' (X_{r}, y) = -\frac{D (X_{r}, y)}{A_{\ell } (x, y)}\). Since \(D (X_{r}, y) \in \{ 0, \pm c_{0}, \pm c_{1}, \pm (c_{0} - c_{1})\} \) by property 1 for \(C\) and since \(A_{\ell } (x, y) \in \{ \pm 1\} \), we get \(D' (X_{r}, y) \in \{ 0, \pm c_{0}, \pm c_{1}, \pm (c_{0} - c_{1})\} \).

Now suppose \(j \in Y_{\ell } \setminus \{ y\} \). By the pivot formula, \(D' (X_{r}, j) = D (X_{r}, j) - \frac{A_{\ell } (x, j)}{A_{\ell } (x, y)} \cdot D (X_{r}, y)\). Here \(D (X_{r}, j), \ D (X_{r}, y) \in \{ 0, \pm c_{0}, \pm c_{1}, \pm (c_{0} - c_{1})\} \) by property 1 for \(C\), and \(A_{\ell } (x, j) \in \{ 0, \pm 1\} \) and \(A_{\ell } (x, y) \in \{ \pm 1\} \) by the prior observations. Perform an exhaustive case distinction on \(D (X_{r}, j)\), \(D (X_{r}, y)\), \(A_{\ell } (x, j)\), and \(A_{\ell } (x, y)\). In every case, we can show that either \(\begin{bmatrix} A_{\ell } (x, y) & A_{\ell } (x, j) \\ D (X_{r}, y) & D (X_{r}, j) \end{bmatrix}\) contains a submatrix with determinant not in \(\{ 0, \pm 1\} \), which contradicts TUness of \(\begin{bmatrix} A_{\ell } \\ D \end{bmatrix}\), or that \(D' (X_{r}, j) \in \{ 0, \pm c_{0}, \pm c_{1}, \pm (c_{0} - c_{1})\} \), as desired. (Todo: need details?)

By Lemma 7, it suffices to show that \(C\) is \(k\)-PU for every \(k \in \mathbb {N}\). We prove this claim by induction on \(k\). The base case with \(k = 1\) holds, since properties 2 and 3 in Definition 57 imply that \(A_{\ell }\), \(A_{r}\), and \(D\) are TU, so all their entries of \(C = \begin{bmatrix} A_{\ell } & 0 \\ D & A_{r} \end{bmatrix}\) are in \(\{ 0, \pm 1\} \), as desired.

Suppose that for some \(k \in \mathbb {N}\) we know that every \(C' \in \mathcal{C} (X_{\ell }, Y_{\ell }, X_{r}, Y_{r}; c_{0}, c_{1})\) is \(k\)-PU. Our goal is to show that \(C\) is \((k + 1)\)-PU, i.e., that every \((k + 1) \times (k + 1)\) submatrix \(S\) of \(C\) has \(\det V \in \{ 0, \pm 1\} \).

First, suppose that \(V\) has no rows in \(X_{\ell }\). Then \(V\) is a submatrix of \(\begin{bmatrix} D & A_{r} \end{bmatrix}\), which is TU by property 2 in Definition 57, so \(\det V \in \{ 0, \pm 1\} \). Thus, we may assume that \(S\) contains a row \(x_{\ell } \in X_{\ell }\).

Next, note that without loss of generality we may assume that there exists \(y_{\ell } \in Y_{\ell }\) such that \(V (x_{\ell }, y_{\ell }) \neq 0\). Indeed, if \(V (x_{\ell }, y) = 0\) for all \(y\), then \(\det V = 0\) and we are done, and \(V (x_{\ell }, y) = 0\) holds whenever \(y \in Y_{r}\).

Since \(C\) is \(1\)-PU, all entries of \(V\) are in \(\{ 0, \pm 1\} \), and hence \(V (x_{\ell }, y_{\ell }) \in \{ \pm 1\} \). Thus, by Lemma 14, performing a short tableau pivot in \(V\) on \((x_{\ell }, y_{\ell })\) yields a matrix that contains a \(k \times k\) submatrix \(S''\) such that \(|\det V| = |\det V''|\). Since \(V\) is a submatrix of \(C\), matrix \(V''\) is a submatrix of the matrix \(C'\) resulting from performing a short tableau pivot in \(C\) on the same entry \((x_{\ell }, y_{\ell })\). By Lemma 59, we have \(C' \in \mathcal{C} (X_{\ell }, Y_{\ell }, X_{r}, Y_{r}; c_{0}, c_{1})\). Thus, by the inductive hypothesis applied to \(V''\) and \(C'\), we have \(\det V'' \in \{ 0, \pm 1\} \). Since \(|\det V| = |\det V''|\), we conclude that \(\det V \in \{ 0, \pm 1\} \).

Combine the results of Lemmas 58 and 60.

Let \(B_{\ell }\), \(B_{r}\), and \(B\) be standard \(\mathbb {Z}_{2}\) representation matrices from Definition 47. Since \(M_{\ell }\) and \(M_{r}\) are regular, by Lemma 34, \(B_{\ell }\) and \(B_{r}\) have TU signings. Then the canonical signing \(B''\) from Definition 52 is a TU signing of \(B\). Indeed, \(B''\) is a signing of \(B\) by Lemma 53, and \(B''\) is TU by Lemma 61. Thus, \(M\) is regular by Lemma 34.