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 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 binary 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 CMRseymourThreeSumDistributedRanks. 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 binary 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 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 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.