A matroid is called regular if can be represented over every field, which is equivalent to representability over the binary field \( \mathbb{F} = \mathbb{F}_2 \) or the ternary field \( \mathbb{F} = \mathbb{F}_3 \). In particular, there exist binary regular and a totally unimodular representation matrices, both of which linearly represent that matroid over the respective field. Such a regular matroid can be decomposed, which is essential for testing regularity. The internal representation is a Seymour decomposition tree whose nodes are pointers to CMR_SEYMOUR_NODE.

Each such decomposition node has a matrix over the field \( \mathbb{F} \) to which it corresponds, which is indicated by CMRseymourIsTernary. While each node has an explicit matrix (see CMRseymourGetMatrix), its transpose need not be stored explicitly (see CMRseymourHasTranspose and CMRseymourGetTranspose). If the matrix is totally unimodular then its support matrix of such a ternary matrix is then also binary regular.

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

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

An unknown node indicates that the Seymour 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 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 CMRseymourGraph and CMRseymourGraphArcsReversed, the spanning tree \( T \) via CMRseymourGraphSizeForest, CMRseymourGraphForest, and its complement via CMRseymourGraphSizeCoforest and CMRseymourGraphCoforest. Note that network matrices are totally unimodularity and graphic matrices are binaryregular. It is either a leaf.
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 CMRseymourCograph and CMRseymourCographArcsReversed, the spanning tree \( T^\star \) via CMRseymourCographSizeForest, CMRseymourCographForest, and its complement via CMRseymourCographSizeCoforest and CMRseymourCographCoforest. Note that conetwork matrices are totally unimodularity and cographic matrices are binary regular. It is a leaf.
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 CMRseymourGraph and CMRseymourGraphArcsReversed, the spanning tree \( T \) via CMRseymourGraphSizeForest, CMRseymourGraphForest, and its complement via CMRseymourGraphSizeCoforest and CMRseymourGraphCoforest. The cograph \( G^\star \) can be accessed via CMRseymourCograph and CMRseymourCographArcsReversed, the spanning tree \( T^\star \) via CMRseymourCographSizeForest, CMRseymourCographForest, and its complement via CMRseymourCographSizeCoforest and CMRseymourCographCoforest. 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 binary regularity. A 1-sum can be created using the function CMRonesumCompose.
A 2-sum node indicates that \( M \) is (up to row and column permutations) of the form
\[ M = \begin{pmatrix} A & \mathbb{O} \\ d c^{\textsf{T}} & D \end{pmatrix}. \]
Such a node has exactly two children corresponding to the matrices
\[ M_1 = \begin{pmatrix} A \\ c^{\textsf{T}} \end{pmatrix} \qquad \text{and} \qquad M_2 = \begin{pmatrix} d & D \end{pmatrix}, \]
respectively. Note that any such decomposition preserves total unimodularity and binary regularity. A 2-sum can be composed using the function CMRtwosumCompose and decomposed using CMRtwosumDecomposeFirst and CMRtwosumDecomposeSecond.
A \( \Delta \)-sum node indicates that \( M \) is (up to row and column permutations) of the form
\[ M = \begin{pmatrix} A & B \\ C & D \end{pmatrix}, \]
where \( \mathop{rank}(B) = \mathop{rank}(C) = 1 \) holds. We define
\[ M_1 := \begin{pmatrix} A & a & a \\ c^{\textsf{T}} & 0 & \varepsilon \end{pmatrix} \qquad \text{and} \qquad M_2 := \begin{pmatrix} \varepsilon & 0 & b^{\textsf{T}} \\ d & d & D \end{pmatrix}, \]
where \( \varepsilon \in \{-1, +1\} \) and where \( a b^{\textsf{T}} = B \) and \( d c^{\textsf{T}} = C \) hold. Then \( M \) is the \( \Delta \)-sum of \( M_1 \) and \( M_2 \). Note that any such composition preserves total unimodularity and binary regularity, while decomposition preserves both properties for the right choice of \( \varepsilon \).
A 3-sum node indicates that \( M \) is (up to row and column permutations) of the form
\[ M = \begin{pmatrix} A & B \\ C & D \end{pmatrix}, \]
where \( \mathop{rank}(B) = 0 \) and \( \mathop{rank}(C) = 2 \) hold. We define
\[ M_1 := \begin{pmatrix} A & \mathbb{O} \\ C_{i,\star} & \alpha \\ C_{j,\star} & \beta \end{pmatrix}, \qquad M_2 := \begin{pmatrix} \gamma & \delta & \mathbb{O}^{\textsf{T}} \\ C_{\star,k} & C_{\star,\ell} & D \end{pmatrix} \qquad \text{and} \qquad N := \begin{pmatrix} \gamma & \delta & 0 \\ C_{i,k} & C_{i,\ell} & \alpha \\ C_{j,k} & C_{j,\ell} & \beta \end{pmatrix}. \]
where \( \mathop{rank}(C_{\{i,j\},\{k,\ell\}}) = 2 \) and where \( \alpha, \beta, \gamma, \delta \in \{-1,+1\} \) are chosen such that \( N \) is totally unimodular. Then \( M \) is the \( 3 \)-sum of \( M_1 \) and \( M_2 \). Note that any such composition preserves total unimodularity and binary regularity, while decomposition preserves both properties for the right choice of \( \alpha, \beta, \gamma, \delta \).
A Y-sum node indicates that \( M \) is (up to row and column permutations) of the form
\[ M = \begin{pmatrix} A & B \\ C & D \end{pmatrix}, \]
where \( \mathop{rank}(B) = \mathop{rank}(C) = 1 \) holds. We define
\[ M_1 := \begin{pmatrix} A & a \\ c^{\textsf{T}} & 0 \\ c^{\textsf{T}} & \varepsilon \end{pmatrix} \qquad \text{and} \qquad M_2 := \begin{pmatrix} \varepsilon & b^{\textsf{T}} \\ 0 & b^{\textsf{T}} \\ d & D \end{pmatrix}, \]
where \( \varepsilon \in \{-1, +1\} \) and where \( a b^{\textsf{T}} = B \) and \( d c^{\textsf{T}} = C \) hold. Then \( M \) is the \( \Delta \)-sum of \( M_1 \) and \( M_2 \). Note that any such composition preserves total unimodularity and binary regularity, while decomposition preserves both properties for the right choice of \( \varepsilon \).
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 binary 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, a Delta-sum or a 3-sum The pivots are carried out over the corresponding field \( \mathbb{F} \).
An irregular node indicates a matrix \( M \) that is irregular. It is a leaf.

The following restrictions apply:

Additional information

Additional data may be associated with each decomposition node. Information about specific submatrices/minors can be obtained via CMRseymourNumMinors and CMRseymourMinor, which returns the associated CMR_MINOR objects.