Dependencies

Matrix is a function that takes a row index and returns a vector, which is a function that takes a column index and returns a value. The former aforementioned identity is definitional, the latter is syntactical. By abuse of notation \(\left(R^Y\right)^X \equiv R^{X \times Y}\) we do not curry functions in this text. When a matrix happens to be finite (that is, both \(X\) and \(Y\) are finite) and its entries are numeric, we like to represent it by a table of numbers.

Let \(A\) be a square matrix over a commutative ring. Determinant of \(A\) is the sum over all permutations, sign of the permutation times the product of ... . (Todo: complete definition).

Let \(A\) be a square matrix of the form \(A = \begin{bmatrix} A_{11} & A_{12} \\ 0 & A_{22} \end{bmatrix}\). Then \(\det A = \det A_{11} \cdot \det A_{22}\).

Matrix made of 4 blocks (2x2).

Let \(B_{\ell }\) and \(B_{r}\) from Definition 35 be TU matrices (over \(\mathbb {Q}\)). Then \(B = B_{\ell } \oplus _{1} B_{r}\) is TU.

Adding extra zero rows to a full representation matrix of a vector matroid does not change the matroid.

Let \(X\) and \(Y\) be sets with \(\{ x_{0}, x_{1}, x_{2}\} \subseteq X\) and \(\{ y_{0}, y_{1}, y_{2}\} \subseteq Y\). Let \(Q \in \mathbb {Q}^{X \times Y}\) be a TU signing of \(Q_{0} \in \mathbb {Z}_{2}^{X \times Y}\) such that \(Q_{0} (\{ x_{0}, x_{1}, x_{2}\} , \{ y_{0}, y_{1}, y_{2}\} ) = S\) (from Definition 48). Then the canonical re-signing \(Q'\) of \(Q\) (from Definition 50) is a TU signing of \(Q_{0}\) and \(Q' (\{ x_{0}, x_{1}, x_{2}\} , \{ y_{0}, y_{1}, y_{2}\} ) = S'\) (from Definition 48).

Let \(Q\) be a TU signing of \(S\) (from Definition 48). Let \(u \in \{ 0, \pm 1\} ^{\{ x_{0}, x_{1}, x_{2}\} }\), \(v \in \{ 0, \pm 1\} ^{\{ y_{0}, y_{1}, y_{2}\} }\), and \(Q'\) be defined as follows:

Then \(Q' = S'\) (from Definition 48).

Given \(k \in \mathbb {N}\), we say that a matrix \(A\) is \(k\)-partially unimodular, or \(k\)-PU for short, if every (not necessarily contiguous, not necessarily injective) \(k \times k\) submatrix \(T\) of \(A\) has \(\det T \in \{ 0, \pm 1\} \).

Let \(R\) be a commutative ring. We say that a matrix \(A \in R^{X \times Y}\) is totally unimodular, or TU for short, if for every \(k \in \mathbb {N}\), every (not necessarily contiguous) \(k \times k\) submatrix \(T\) of \(A\) has \(\det T \in \{ 0, \pm 1\} \).

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.

Let \(A\) be a rational TU matrix. Its rows are linearly independent iff the rows of its support matrix are linearly independent.

Let \(A\) be a rational TU matrix with finite number of rows. Its rows are linearly independent iff the rows of its support matrix are linearly independent.

Let \(A\) be a rational TU matrix with finite number of rows and finite number of columns. Its rows are linearly independent iff the rows of its support matrix are linearly independent.

Let \(A \in \mathbb {Q}^{X \times Y}\) be a TU matrix and let \((x, y) \in X \times Y\) be such that \(A (x, y) \neq 0\). Then performing the long tableau pivot in \(A\) on \((x, y)\) yields a TU matrix.

Let \(A\) be a TU matrix. Suppose columns of \(A\) are multiplied by \(\{ 0, \pm 1\} \) factors. Then the resulting matrix \(A'\) is also TU.

Let \(A\) be a TU matrix. Suppose rows of \(A\) are multiplied by \(\{ 0, \pm 1\} \) factors. Then the resulting matrix \(A'\) is also TU.

Let \(A \in \mathbb {Q}^{X \times Y}\) be a TU matrix and let \((x, y) \in X \times Y\) be such that \(A (x, y) \neq 0\). Then performing the short tableau pivot in \(A\) on \((x, y)\) yields a TU matrix.

Let \(A\) be a TU matrix.

1. If a matroid is represented by \(A\), then it is also represented by \(A^{\# }\).

2. If a matroid is represented by \(A^{\# }\), then it is also represented by \(A\).

A matrix \(A\) is TU if and only if \(A\) is \(k\)-PU for every \(k \in \mathbb {N}\).

We say that \(A' \in \mathbb {Q}^{X \times Y}\) is a TU signing of \(A \in \mathbb {Z}_{2}^{X \times Y}\) if \(A'\) is TU and

A square matrix is invertible iff its determinant is invertible.

Let \(A \in R^{X \times Y}\) be a matrix and let \((x, y) \in X \times Y\) be such that \(A (x, y) \neq 0\). A long tableau pivot in \(A\) on \((x, y)\) is the operation that maps \(A\) to the matrix \(A'\) where

Let \(A \in R^{X \times Y}\) be a matrix and let \((x, y) \in X \times Y\) be such that \(A (x, y) \neq 0\). Perform the following sequence of operations.

1. Adjoin the identity matrix \(1 \in R^{X \times X}\) to \(A\), resulting in the matrix \(B = \begin{bmatrix} 1 & A \end{bmatrix} \in R^{X \times (X \oplus Y)}\).

2. Perform a long tableau pivot in \(B\) on \((x, y)\), and let \(C\) denote the result.

3. Swap columns \(x\) and \(y\) in \(C\), and let \(D\) be the resulting matrix.

4. Finally, remove columns indexed by \(X\) from \(D\), and let \(A'\) be the resulting matrix.

A short tableau pivot in \(A\) on \((x, y)\) is the operation that maps \(A\) to the matrix \(A'\) defined above.

Let \(A \in R^{X \times Y}\) be a matrix and let \((x, y) \in X \times Y\) be such that \(A (x, y) \neq 0\). Then the short tableau pivot in \(A\) on \((x, y)\) maps \(A\) to \(A'\) with

Let \(B = \begin{bmatrix} B_{11} & 0 \\ B_{21} & B_{22} \end{bmatrix} \in \mathbb {Q}^{\{ X_{1} \cup X_{2}\} \times \{ Y_{1} \times Y_{2}\} }\). Let \(B' = \begin{bmatrix} B_{11}’ & B_{12}’ \\ B_{21}’ & B_{22}’ \end{bmatrix}\) be the result of performing a short tableau pivot on \((x, y) \in X_{1} \times Y_{1}\) in \(B\). Then \(B_{12}' = 0\), \(B_{22}' = B_{22}\), and \(\begin{bmatrix} B_{11}’ \\ B_{21}’ \end{bmatrix}\) is the matrix resulting from performing a short tableau pivot on \((x, y)\) in \(\begin{bmatrix} B_{11} \\ B_{21} \end{bmatrix}\).

Let \(R\) be a magma containing zero. The support of matrix \(A \in R^{X \times Y}\) is \(A^{\# } \in \{ 0, 1\} ^{X \times Y}\) given by

Submatrix of a support matrix is equal to a support matrix of the submatrix.

Transpose of a support matrix is equal to a support of the transposed matrix.

If \(A\) is a matrix over \(\mathbb {Z}_{2}\), then \(A^{\# } = A\).

Let \(X\) and \(Y\) be sets with \(\{ x_{0}, x_{1}, x_{2}\} \subseteq X\) and \(\{ y_{0}, y_{1}, y_{2}\} \subseteq Y\). Let \(Q \in \mathbb {Q}^{X \times Y}\) be a TU matrix. Define \(u \in \{ 0, \pm 1\} ^{X}\), \(v \in \{ 0, \pm 1\} ^{Y}\), and \(Q'\) as follows:

We call \(Q'\) the canonical re-signing of \(Q\).

We call \(D_{0}' \in \mathbb {Q}^{\{ x_{0}, x_{1}\} \times \{ y_{0}, y_{1}\} }\) the canonical signing of \(D_{0} \in \mathbb {Z}_{2}^{\{ x_{0}, x_{1}\} \times \{ y_{0}, y_{1}\} }\) if

Similarly, we call \(S' \in \mathbb {Q}^{\{ x_{0}, x_{1}, x_{2}\} \times \{ y_{0}, y_{1}, y_{2}\} }\) the canonical signing of \(S \in \mathbb {Z}_{2}^{\{ x_{0}, x_{1}, x_{2}\} \times \{ y_{0}, y_{1}, y_{2}\} }\) if

To simplify notation, going forward we use \(D_{0}\), \(D_{0}'\), \(S\), and \(S'\) to refer to the matrices of the form above. BTW, the canonical signing \(S'\) of \(S\) (from Definition 48) is TU.

Let \(X_{\ell }\), \(Y_{\ell }\), \(X_{r}\), \(Y_{r}\) be sets and let \(c_{0}, c_{1} \in \mathbb {Q}^{X_{r}}\) be column vectors such that for every \(i \in X_{r}\) we have \(c_{0} (i), \ c_{1} (i), \ c_{0} (i) - c_{1} (i) \in \{ 0, \pm 1\} \). Define \(\mathcal{C} (X_{\ell }, Y_{\ell }, X_{r}, Y_{r}; c_{0}, c_{1})\) to be the family of matrices of the form \(\begin{bmatrix} A_{\ell } & 0 \\ D & A_{r} \end{bmatrix}\) where \(A_{\ell } \in \mathbb {Q}^{X_{\ell } \times Y_{\ell }}\), \(A_{r} \in \mathbb {Q}^{X_{r} \times Y_{r}}\), and \(D \in \mathbb {Q}^{X_{r} \times Y_{\ell }}\) are such that:

1. for every \(j \in Y_{\ell }\), \(D (X_{r}, j) \in \{ 0, \pm c_{0}, \pm c_{1}, \pm (c_{0} - c_{1})\} \),

2. \(\begin{bmatrix} c_{0} & c_{1} & c_{0} - c_{1} & A_{r} \end{bmatrix}\) is TU,

3. \(\begin{bmatrix} A_{\ell } \\ D \end{bmatrix}\) is TU.

Let \(C \in \mathcal{C} (X_{\ell }, Y_{\ell }, X_{r}, Y_{r}; c_{0}, c_{1})\) from Definition 57. Then \(C\) is TU.

Let \(C \in \mathcal{C} (X_{\ell }, Y_{\ell }, X_{r}, Y_{r}; c_{0}, c_{1})\) from Definition 57. Let \(x \in X_{\ell }\) and \(y \in Y_{\ell }\) be such that \(A_{\ell } (x, y) \neq 0\), and let \(C'\) be the result of performing a short tableau pivot in \(C\) on \((x, y)\). Then \(C' \in \mathcal{C} (X_{\ell }, Y_{\ell }, X_{r}, Y_{r}; c_{0}, c_{1})\).

\(B''\) from Definition 52 is a signing of \(B\).

Suppose that \(B_{r}\) from Definition 46 has a TU signing \(B_{r}'\). Let \(B_{r}''\) be the canonical re-signing (from Definition 50) of \(B_{r}'\). Let \(c_{0}'' = B_{r}'' (X_{r}, y_{0})\), \(c_{1}'' = B_{r}'' (X_{r}, y_{1})\), and \(c_{2}'' = c_{0}'' - c_{1}''\). Then the following statements hold.

1. For every \(i \in X_{r}\), \(\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\} \).

2. For every \(i \in X_{r}\), \(c_{2}'' (i) \in \{ 0, \pm 1\} \).

3. \(\begin{bmatrix} c_{0}” & c_{2}” & A_{r}” \end{bmatrix}\) is TU.

4. \(\begin{bmatrix} c_{1}” & c_{2}” & A_{r}” \end{bmatrix}\) is TU.

5. \(\begin{bmatrix} c_{0}” & c_{1}” & c_{2}” & A_{r}” \end{bmatrix}\) is TU.

Suppose that \(B_{\ell }\) from Definition 46 has a TU signing \(B_{\ell }'\). Let \(B_{\ell }''\) be the canonical re-signing (from Definition 50) of \(B_{\ell }'\). Let \(d_{0}'' = B_{\ell }'' (x_{0}, Y_{\ell })\), \(d_{1}'' = B_{\ell }'' (x_{1}, Y_{\ell })\), and \(d_{2}'' = d_{0}'' - d_{1}''\). Then the following statements hold.

1. For every \(j \in Y_{\ell }\), \(\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\} \).

2. For every \(j \in Y_{\ell }\), \(d_{2}'' (j) \in \{ 0, \pm 1\} \).

3. \(\begin{bmatrix} A_{\ell }” \\ d_{0}” \\ d_{2}” \end{bmatrix}\) is TU.

4. \(\begin{bmatrix} A_{\ell }” \\ d_{1}” \\ d_{2}” \end{bmatrix}\) is TU.

5. \(\begin{bmatrix} A_{\ell }” \\ d_{0}” \\ d_{1}” \\ d_{2}” \end{bmatrix}\) is TU.

Let \(B''\) be from Definition 52. Let \(c_{0}'' = B'' (X_{r}, y_{0})\), \(c_{1}'' = B'' (X_{r}, y_{1})\), and \(c_{2}'' = c_{0}'' - c_{1}''\). Similarly, let \(d_{0}'' = B'' (x_{0}, Y_{\ell })\), \(d_{1}'' = B'' (x_{1}, Y_{\ell })\), and \(d_{2}'' = d_{0}'' - d_{1}''\). Then the following statements hold.

1. For every \(i \in X_{r}\), \(c_{2}'' (i) \in \{ 0, \pm 1\} \).

2. If \(D_{0}'' = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}\), then \(D'' = c_{0}'' \otimes d_{0}'' - c_{1}'' \otimes d_{1}''\). If \(D_{0}'' = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\), then \(D'' = c_{0}'' \otimes d_{0}'' - c_{0}'' \otimes d_{1}'' + c_{1}'' \otimes d_{1}''\).

3. For every \(j \in Y_{\ell }\), \(D'' (X_{r}, j) \in \{ 0, \pm c_{0}'', \pm c_{1}'', \pm c_{2}''\} \).

4. For every \(i \in X_{r}\), \(D'' (i, Y_{\ell }) \in \{ 0, \pm d_{0}'', \pm d_{1}'', \pm d_{2}''\} \).

5. \(\begin{bmatrix} A_{\ell }” \\ D” \end{bmatrix}\) is TU.

\(B''\) from Definition 52 is TU.

Let \(B''\) be from Definition 52. Then \(B'' \in \mathcal{C} (X_{\ell }, Y_{\ell }, X_{r}, Y_{r}; c_{0}'', c_{1}'')\) where \(c_{0}'' = B'' (X_{r}, y_{0})\) and \(c_{1}'' = B'' (X_{r}, y_{1})\).

Let \(B_{\ell } \in \mathbb {Z}_{2}^{(X_{\ell } \cup \{ x_{0}, x_{1}\} ) \times (Y_{\ell } \cup \{ y_{2}\} )}, B_{r} \in \mathbb {Z}_{2}^{(X_{r} \cup \{ x_{2}\} ) \times (Y_{r} \cup \{ y_{0}, y_{1}\} )}\) be matrices of the form

The \(3\)-sum \(B = B_{\ell } \oplus _{3} B_{r} \in \mathbb {Z}_{2}^{(X_{\ell } \cup X_{r}) \times (Y_{\ell } \cup Y_{r})}\) of \(B_{\ell }\) and \(B_{r}\) is defined as

Here \(x_{2} \in X_{\ell }\), \(x_{0}, x_{1} \in X_{r}\), \(y_{0}, y_{1} \in Y_{\ell }\), \(y_{2} \in Y_{r}\), \(A_{\ell } \in \mathbb {Z}_{2}^{X_{\ell } \times Y_{\ell }}\), \(A_{r} \in \mathbb {Z}_{2}^{X_{r} \times Y_{r}}\), \(D_{\ell } \in \mathbb {Z}_{2}^{\{ x_{0}, x_{1}\} \times (Y_{\ell } \setminus \{ y_{0}, y_{1}\} )}\), \(D_{r} \in \mathbb {Z}_{2}^{(X_{r} \setminus \{ x_{0}, x_{1}\} ) \times \{ y_{0}, y_{1}\} }\), \(D_{\ell r} \in \mathbb {Z}_{2}^{(X_{r} \setminus \{ x_{0}, x_{1}\} ) \times (Y_{\ell } \setminus \{ y_{0}, y_{1}\} )}\), \(D_{0} \in \mathbb {Z}_{2}^{\{ x_{0}, x_{1}\} \times \{ y_{0}, y_{1}\} }\). The indexing is consistent everywhere.

Note that \(D_{0}\) is non-singular by construction, so \(D_{\ell r}\) and \(B\) are well-defined. Moreover, a non-singular \(\mathbb {Z}_{2}^{2 \times 2}\) matrix is either \(\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\) or \(\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\) up to re-indexing. Thus, Definition 46 can be equivalently restated with \(D_{0}\) required to be non-singular and \(B_{\ell }\), \(B_{r}\), and \(B\) re-indexed appropriately.

Suppose that \(B_{\ell }\) and \(B_{r}\) from Definition 46 have TU signings \(B_{\ell }'\) and \(B_{r}'\), respectively. Let \(B_{\ell }''\) and \(B_{r}''\) be the canonical re-signings (from Definition 50) of \(B_{\ell }'\) and \(B_{r}'\), respectively. Let \(A_{\ell }''\), \(A_{r}''\), \(D_{\ell }''\), \(D_{r}''\), and \(D_{0}''\) be blocks of \(B_{\ell }''\) and \(B_{r}''\) analogous to blocks \(A_{\ell }\), \(A_{r}\), \(D_{\ell }\), \(D_{r}\), and \(D_{0}\) of \(B_{\ell }\) and \(B_{r}\). The canonical signing \(B''\) of \(B\) is defined as

Note that \(D_{0}''\) is non-singular by construction, so \(D_{\ell r}''\) and hence \(B''\) are well-defined.

(Todo: Add definition of matroids)

A matroid \(M\) is a \(1\)-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 35.

Let \(M\) be a \(1\)-sum of regular matroids \(M_{\ell }\) and \(M_{r}\). Then \(M\) is also regular.

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 \(M\) be a \(2\)-sum of regular matroids \(M_{\ell }\) and \(M_{r}\). Then \(M\) is also regular.

A matroid \(M\) is a \(3\)-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 46.

Let \(M\) be a \(3\)-sum of regular matroids \(M_{\ell }\) and \(M_{r}\). Then \(M\) is also regular.

Regular matroid is good. Any 1-sum of good matroids is a good matroid. Any 2-sum of good matroids is a good matroid. Any 3-sum of good matroids is a good matroid.

Any good matroid is regular. This is the easy direction of the Seymour theorem.

A matroid \(M\) is regular if there exists a TU matrix \(A \in \mathbb {Q}^{X \times Y}\) such that \(M\) is a vector matroid of \(A\).

Let \(k \in \mathbb {N}\), let \(A \in \mathbb {Q}^{k \times k}\), and let \(A'\) be the result of performing a short tableau pivot in \(A\) on \((x, y)\) with \(x, y \in \{ 1, \dots , k\} \) such that \(A (x, y) \neq 0\). Then \(A'\) contains a submatrix \(A''\) of size \((k - 1) \times (k - 1)\) with \(|\det A''| = |\det A| / |A (x, y)|\).

Let \(R\) be a division ring, let \(X\) and \(Y\) be disjoint sets, and let \(S \in R^{X \times Y}\) be a matrix. Let \(A = \begin{bmatrix} 1 & S \end{bmatrix} \in R^{X \times (X \cup Y)}\) be the matrix obtained from \(S\) by adjoining the identity matrix as columns, and let \(M\) be the vector matroid of \(A\). Then \(S\) is called the standard representation of \(M\).

Let \(S \in R^{X \times Y}\) be a standard representation of a vector matroid \(M\). Then \(X\) is a base in \(M\).

Let \(B \in \mathbb {Z}_{2}^{X \times Y}\) be a standard representation matrix of a matroid \(M\). Then \(M\) is regular if and only if \(B\) has a TU signing.

Let \(R\) be a magma containing zero (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}}\) be matrices where \(X_{\ell }, Y_{\ell }, X_{r}, Y_{r}\) are pairwise disjoint sets. The \(1\)-sum \(B = B_{\ell } \oplus _{1} B_{r}\) of \(B_{\ell }\) and \(B_{r}\) is

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.

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.

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}\).

If two standard representation matrices of the same matroid have the same base, then they have the same support.

Let \(R\) be a division ring, let \(X\) and \(Y\) be sets, and let \(A \in R^{X \times Y}\) be a matrix. The vector matroid of \(A\) is the matroid \(M = (Y, \mathcal{I})\) where a set \(I \subset Y\) is independent in \(M\) if and only if the columns of \(A\) indexed by \(I\) are linearly independent.

Let \(A \in \mathbb {Q}^{X \times Y}\) be a TU matrix, let \(M\) be the vector matroid of \(A\), and let \(B\) be a base of \(M\). Then there exists a matrix \(S \in \mathbb {Q}^{B \times (Y \setminus B)}\) such that \(S\) is TU and \(S\) is a standard representation of \(M\).