3 Regularity of 2-Sum
Let \(R\) be a semiring (we will use \(R = \mathbb {Z}_{2}\) and \(R = \mathbb {Q}\)). Let \(B_{\ell } \in R^{X_{\ell } \times Y_{\ell }}\) and \(B_{r} \in R^{X_{r} \times Y_{r}}\) where \(X_{\ell } \cap X_{r} = \{ x\} \), \(Y_{\ell } \cap Y_{r} = \{ y\} \), \(X_{\ell }\) is disjoint with \(Y_{\ell }\) and \(Y_{r}\), and \(X_{r}\) is disjoint with \(Y_{\ell }\) and \(Y_{r}\). Additionally, let \(A_{\ell } = B_{\ell } (X_{\ell } \setminus \{ x\} , Y_{\ell })\) and \(A_{r} = B_{r} (X_{r}, Y_{r} \setminus \{ y\} )\), and suppose \(r = B_{\ell } (x, Y_{\ell }) \neq 0\) and \(c = B_{r} (X_{r}, y) \neq 0\). Then the \(2\)-sum \(B = B_{\ell } \oplus _{2, x, y} B_{r}\) of \(B_{\ell }\) and \(B_{r}\) is defined as
Here \(D \in R^{X_{r} \times Y_{\ell }}\), and the indexing is consistent everywhere.
A matroid \(M\) is a \(2\)-sum of matroids \(M_{\ell }\) and \(M_{r}\) if there exist standard \(\mathbb {Z}_{2}\) representation matrices \(B_{\ell }\), \(B_{r}\), and \(B\) (for \(M_{\ell }\), \(M_{r}\), and \(M\), respectively) of the form given in Definition 40.
Let \(B_{\ell }\) and \(B_{r}\) from Definition 40 be TU matrices (over \(\mathbb {Q}\)). Then \(C = \begin{bmatrix} D & A_{r} \end{bmatrix}\) is TU.
Since \(B_{\ell }\) is TU, all its entries are in \(\{ 0, \pm 1\} \). In particular, \(r\) is a \(\{ 0, \pm 1\} \) vector. Therefore, every column of \(D\) is a copy of \(y\), \(-y\), or the zero column. Thus, \(C\) can be obtained from \(B_{r}\) by adjoining zero columns, duplicating the \(y\) column, and multiplying some columns by \(-1\). Since all these operations preserve TUess and since \(B_{r}\) is TU, \(C\) is also TU.
Let \(B_{\ell }\) and \(B_{r}\) be matrices from Definition 40. Let \(B_{\ell }'\) and \(B'\) be the matrices obtained by performing a short tableau pivot on \((x_{\ell }, y_{\ell }) \in X_{\ell } \times Y_{\ell }\) in \(B_{\ell }\) and \(B\), respectively. Then \(B' = B_{\ell }' \oplus _{2, x, y} B_{r}\).
Let
where the blocks have the same dimensions as in \(B_{\ell }\) and \(B\), respectively. By Lemma 13, \(B_{11}' = A_{\ell }'\), \(B_{12}' = 0\), and \(B_{22}' = A_{r}\). Equality \(B_{21}' = c \otimes r'\) can be verified via a direct calculation. Thus, \(B' = B_{\ell }' \oplus _{2, x, y} B_{r}\).
Let \(B_{\ell }\) and \(B_{r}\) from Definition 40 be TU matrices (over \(\mathbb {Q}\)). Then \(B_{\ell } \oplus _{2, x, y} B_{r}\) is TU.
By Lemma 7, it suffices to show that \(B_{\ell } \oplus _{2, x, y} B_{r}\) 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 all entries of \(B_{\ell } \oplus _{2, x, y} B_{r}\) are in \(\{ 0, \pm 1\} \) by construction.
Suppose that for some \(k \in \mathbb {N}\) we know that for any TU matrices \(B_{\ell }'\) and \(B_{r}'\) (from Definition 40) their \(2\)-sum \(B_{\ell }' \oplus _{2, x, y} B_{r}'\) is \(k\)-PU. Now, given TU matrices \(B_{\ell }\) and \(B_{r}\) (from Definition 40), our goal is to show that \(B = B_{\ell } \oplus _{2, x, y} B_{r}\) is \((k + 1)\)-PU, i.e., that every \((k + 1) \times (k + 1)\) submatrix \(T\) of \(B\) has \(\det T \in \{ 0, \pm 1\} \).
First, suppose that \(T\) has no rows in \(X_{\ell }\). Then \(T\) is a submatrix of \(\begin{bmatrix} D & A_{r} \end{bmatrix}\), which is TU by Lemma 42, so \(\det T \in \{ 0, \pm 1\} \). Thus, we may assume that \(T\) 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 \(T (x_{\ell }, y_{\ell }) \neq 0\). Indeed, if \(T (x_{\ell }, y) = 0\) for all \(y\), then \(\det T = 0\) and we are done, and \(T (x_{\ell }, y) = 0\) holds whenever \(y \in Y_{r}\).
Since \(B\) is \(1\)-PU, all entries of \(T\) are in \(\{ 0, \pm 1\} \), and hence \(T (x_{\ell }, y_{\ell }) \in \{ \pm 1\} \). Thus, by Lemma 14, performing a short tableau pivot in \(T\) on \((x_{\ell }, y_{\ell })\) yields a matrix that contains a \(k \times k\) submatrix \(T''\) such that \(|\det T| = |\det T''|\). Since \(T\) is a submatrix of \(B\), matrix \(T''\) is a submatrix of the matrix \(B'\) resulting from performing a short tableau pivot in \(B\) on the same entry \((x_{\ell }, y_{\ell })\). By Lemma 43, we have \(B' = B_{\ell }' \oplus _{2, x, y} B_{r}\) where \(B_{\ell }'\) is the result of performing a short tableau pivot in \(B_{\ell }\) on \((x_{\ell }, y_{\ell })\). Since \(B_{\ell }\) is TU, by Lemma 15, \(B_{\ell }'\) is also TU. Thus, by the inductive hypothesis applied to \(T''\) and \(B_{\ell }' \oplus _{2, x, y} B_{r}\), we have \(\det T'' \in \{ 0, \pm 1\} \). Since \(|\det T| = |\det T''|\), we conclude that \(\det T \in \{ 0, \pm 1\} \).
Let \(M\) be a \(2\)-sum of regular matroids \(M_{\ell }\) and \(M_{r}\). Then \(M\) is also regular.
Let \(B_{\ell }\), \(B_{r}\), and \(B\) be standard \(\mathbb {Z}_{2}\) representation matrices from Definition 41. Since \(M_{\ell }\) and \(M_{r}\) are regular, by Lemma 34, \(B_{\ell }\) and \(B_{r}\) have TU signings \(B_{\ell }'\) and \(B_{r}'\), respectively. Then \(B' = B_{\ell }' \oplus _{2, x, y} B_{r}'\) is a TU signing of \(B\). Indeed, \(B'\) is TU by Lemma 44, and a direct calculation verifies that \(B'\) is a signing of \(B\). Thus, \(M\) is regular by Lemma 34.