The matroid represented by a matrix \( M \in \mathbb{F}^{m \times n} \) has \( m + n \) elements that correspond to the columns of \( [ \mathbb{I} \mid M ] \). A subset of these columns is independent if and only if it is linearly independent over the field \( \mathbb{F} \).

Decomposition of matroids

In CMR, the matroid represented by a matrix can be decomposed, which is essential for testing for total unimodularity and regularity. The internal representation is a decomposition tree whose nodes are references to CMR_MATROID_DEC.

Each such decomposition node belongs to a matrix, either of the ternary field \( \mathbb{F} = \mathbb{F}_3 \) or over the binary field \( \mathbb{F} = \mathbb{F}_2 \). This is indicated by CMRmatroiddecIsTernary. While each node has an explicit matrix (see CMRmatroiddecGetMatrix), its transpose need not be stored explicitly (see CMRmatroiddecHasTranspose and CMRmatroiddecGetTranspose). If the matroid is regular then the support matrix of such a ternary matrix is then also a binary representation matrix.

A decomposition node may have children, which are (references to) other decomposition nodes. Their number can be queried via CMRmatroiddecNumChildren and each child via CMRmatroiddecChild.

Moreover, it has (exactly) one of the following types:

An unknown node indicates that the matroid decomposition of the corresponding matrix was not carried out, yet. It is considered a leaf node.
An R10 node indicates that \( M \) represents the (regular) matroid \( R_{10} \) over \( \mathbb{F} \). It is a leaf.
A Fano node indicates that \( M \) represents the (irregular) Fano matroid \( F_7 \) over \( \mathbb{F} \). It is a leaf.
A Fano-dual node indicates that \( M \) represents the dual \( F_7^\star \) of the (irregular) Fano matroid. It is a leaf.
A K5 node indicates that \( M \) represents the graphic matroid \( M(K_5) \) of the complete graph \( K_5 \) over \( \mathbb{F} \). It is a leaf.
A K5-dual node indicates that \( M \) represents the dual matroid \( M(K_5)^\star \) of the complete graph \( K_5 \) over \( \mathbb{F} \). It is a leaf.
A K33 node indicates that \( M \) represents the graphic matroid \( M(K_{3,3}) \) of the complete bipartite graph \( K_{3,3} \) over \( \mathbb{F} \). It is a leaf.
A K33-dual node indicates that \( M \) represents the dual matroid \( M(K_{3,3})^\star \) of the complete bipartite graph \( K_{3,3} \) over \( \mathbb{F} \). It is a leaf.
A determinant node indicates that \( M \) has \( |\det(M)| = 2 \). It is a leaf.
A graphic node indicates that the matrix \( M \) is graphic (if \( \mathbb{F} = \mathbb{F}_2 \)) or network (if \( \mathbb{F} = \mathbb{F}_3 \)) and that a corresponding (directed) graph \( G \) with spanning tree \( T \) is stored. The graph \( G \) can be accessed via CMRmatroiddecGraph and CMRmatroiddecGraphArcsReversed, the spanning tree \( T \) via CMRmatroiddecGraphSizeForest, CMRmatroiddecGraphForest, and its complement via CMRmatroiddecGraphSizeCoforest and CMRmatroiddecGraphCoforest. Note that network matrices are totally unimodularity and graphic matrices are regular. It is either a leaf or it has one submatrix or pivot child node.
A cographic node indicates that the matrix \( M \) is cographic (if \( \mathbb{F} = \mathbb{F}_2 \)) or conetwork (if \( \mathbb{F} = \mathbb{F}_3 \)) and that a corresponding (directed) graph \( G^\star \) with spanning tree \( T^\star \) stored. The cograph \( G^\star \) can be accessed via CMRmatroiddecCograph and CMRmatroiddecCographArcsReversed, the spanning tree \( T^\star \) via CMRmatroiddecCographSizeForest, CMRmatroiddecCographForest, and its complement via CMRmatroiddecCographSizeCoforest and CMRmatroiddecCographCoforest. Note that conetwork matrices are totally unimodularity and cographic matrices are regular. It is either a leaf or it has one submatrix or pivot child node.
A planar node indicates that the matrix \( M \) is graphic and cographic (if \( \mathbb{F} = \mathbb{F}_2 \)) or network and conetwork (if \( \mathbb{F} = \mathbb{F}_3 \)) at the same time. The graph \( G \) can be accessed via CMRmatroiddecGraph and CMRmatroiddecGraphArcsReversed, the spanning tree \( T \) via CMRmatroiddecGraphSizeForest, CMRmatroiddecGraphForest, and its complement via CMRmatroiddecGraphSizeCoforest and CMRmatroiddecGraphCoforest. The cograph \( G^\star \) can be accessed via CMRmatroiddecCograph and CMRmatroiddecCographArcsReversed, the spanning tree \( T^\star \) via CMRmatroiddecCographSizeForest, CMRmatroiddecCographForest, and its complement via CMRmatroiddecCographSizeCoforest and CMRmatroiddecCographCoforest. It is a leaf.
A 1-sum node indicates that \( M \) is (up to row and column permutations) of the form
\[ M = \begin{pmatrix} A_1 & \mathbb{O} & \dotsb & \mathbb{O} \\ \mathbb{O} & A_2 & & \vdots \\ \vdots & & \ddots & \mathbb{O} \\ \mathbb{O} & \dotsb & \mathbb{O} & A_k \end{pmatrix}. \]
Such a node has at least two children that belong to the matrices \( M_1 := A_1 \), \( M_2 := A_2 \), up to \( M_k := A_k \). Note that any such decomposition preserves total unimodularity and regularity.
A 2-sum node indicates that \( M \) is (up to row and column permutations) of the form
\[ M = \begin{pmatrix} A_1 & \mathbb{O} \\ a_2 a_1^{\textsf{T}} & A_2 \end{pmatrix}. \]
Such a node has exactly two children that belong to the matrices
\[ M_1 = \begin{pmatrix} A_1 \\ a_1^{\textsf{T}} \end{pmatrix} \qquad \text{and} \qquad M_2 = \begin{pmatrix} a_2 & A_2 \end{pmatrix}, \]
respectively. Note that any such decomposition preserves total unimodularity and regularity.
A 3-sum node indicates that \( M \) is (up to row and column permutations) of the form
\[ M = \begin{pmatrix} A_1 & C \\ D & A_2 \end{pmatrix}, \]
where \( (\mathop{rank}(C), \mathop{rank}(D)) \in \{ (1,1), (0,2) \} \) holds. We refer to the first case as distributed ranks, which is indicated by CMRmatroiddecThreeSumRanksDistributed. The other case is that of concentrated rank. In each case, there are two variants per child node, and we first consider the case of distributed ranks. Then the matrix \( M \) is of the form
\[ M = \begin{pmatrix} A_1 & c_1 c_2^{\textsf{T}} \\ d_2 d_1^{\textsf{T}} & A_2 \end{pmatrix}. \]
The first child is of one of the forms
\[ M_1^{\text{wide}} = \begin{pmatrix} A_1 & c_1 & c_1 \\ d_1^{\textsf{T}} & 0 & \pm 1 \end{pmatrix}, \qquad M_1^{\text{tall}} = \begin{pmatrix} A_1 & c_1 \\ d_1^{\textsf{T}} & 0 \\ d_1^{\textsf{T}} & \pm 1 \end{pmatrix}. \]
The second child is of one of the forms
\[ M_2^{\text{wide}} = \begin{pmatrix} \pm 1 & 0 & c_2^{\textsf{T}} \\ d_2 & d_2 & A_2 \end{pmatrix}, \qquad M_2^{\text{tall}} = \begin{pmatrix} \pm 1 & c_2^{\textsf{T}} \\ 0 & c_2^{\textsf{T}} \\ d_2 & A_2 \end{pmatrix}. \]
In case of concentrated rank the matrix \( M \) is of the form
\[ M = \begin{pmatrix} A_1 & \mathbb{O} \\ D & A_2 \end{pmatrix}, \]
where \( \mathop{rank}(D) = 2 \). The first child is of one of the forms
\[ M_1^{\text{mixed}} = \begin{pmatrix} A_1 & \mathbb{O} \\ d_1^{\textsf{T}} & 1 \\ d_2^{\textsf{T}} & \pm 1 \end{pmatrix}, \qquad M_1^{\text{all-repr}} = \begin{pmatrix} A_1 \\ d_1^{\textsf{T}} \\ d_2^{\textsf{T}} \\ d_3^{\textsf{T}} \end{pmatrix}, \]
where any pair of \( d_1, d_2, d_3 \) spans the row-space of \( D \). The second child is of one of the forms
\[ M_2^{\text{mixed}} = \begin{pmatrix} A_1 & d_1 & d_2 \\ \mathbb{O} & 1 & \pm 1 \end{pmatrix}, \qquad M_2^{\text{all-repr}} = \begin{pmatrix} A_1 & d_1 & d_2 & d_3 \end{pmatrix}, \]
where any pair of \( d_1, d_2, d_3 \) spans the column-space of \( D \). The sign of the entries marked as \( \pm 1 \) is determined such that a certain submatrix involving that entry has the right determinant. Note that any such decomposition preserves total unimodularity and regularity.
A series-parallel node indicates that \( M \) arises from a smaller matrix \( M' \) by successively adding zero rows/columns, unit rows/columns or duplicates of existing rows/columns (potentially scaled with \( -1 \)). Note that such series-parallel reductions preserve total unimodularity and regularity. It has one child node that corresponds to \( M' \).
A pivot node indicates a sequence of pivot operations on entries whose rows and columns are pairwise distinct, which turn matrix \( M \) into another matrix \( M' \) that represent the same matroid. The unique child must either be a leaf node or a 3-sum. The pivots are carried out over the corresponding field \( \mathbb{F} \).
A submatrix node indicates a submatrix \( M' \) of \( M \). The unique child must either be a leaf node or a pivot.
An irregular node indicates a matrix \( M \) that is irregular. It is either a leaf or it has one submatrix or pivot child node.

The following restrictions apply: