Seymour’s decomposition of totally unimodular matrices and regular matroids¶

This module is provided by the pip-installable package passagemath-cmr.

class sage.matrix.seymour_decomposition.BaseGraphicNode[source]¶

Bases: DecompositionNode

Base class for GraphicNode, CographicNode, and PlanarNode

If base_ring is \(\GF{2}\), then it represents a graphic/cographic/planar matroid.

Suppose that self.matrix() is a graphic matrix of a graph \(G\) with respect to \(T\), a spanning forest of the graph \(G\).

• self._graph is the graph \(G = (V,E)\).

• self._forest_edges is the edges of \(T\).

• self._coforest_edges is the edges of \(E \setminus T\).

If base_ring is \(\GF{3}\) or \(\ZZ\), then it represents a network/conetwork or a both network and conetwork matrix.

Suppose that self.matrix() is a network matrix of a digraph \(D\) with respect to \(T\), a directed spanning forest of the underlying undirected graph.

• self._graph is the digraph \(D = (V,A)\).

• self._forest_edges is the arcs of \(T\).

• self._coforest_edges is the arcs of \(A \setminus T\).

coforest_edges()[source]¶

Return the forest edges of self.

If self.base_ring() is \(\GF{2}\), then return edges. If self.base_ring() is \(\GF{3}\) or \(\ZZ\), then arcs.

EXAMPLES:

Sage

sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 7, sparse=True),
....:                           [[-1,  0,  0,  0,  1, -1,  0],
....:                            [ 1,  0,  0,  1, -1,  1,  0],
....:                            [ 0, -1,  0, -1,  1, -1,  0],
....:                            [ 0,  1,  0,  0,  0,  0,  1],
....:                            [ 0,  0,  1, -1,  1,  0,  1],
....:                            [ 0,  0, -1,  1, -1,  0,  0]])
sage: M.is_network_matrix()
True
sage: result, certificate = M.is_network_matrix(certificate=True)
sage: result, certificate
(True,
 (Digraph on 7 vertices,
  ((9, 8), (3, 8), (3, 4), (5, 4), (4, 6), (0, 6)),
  ((3, 9), (5, 3), (4, 0), (0, 8), (9, 0), (4, 9), (5, 6))))
sage: digraph, forest_arcs, coforest_arcs = certificate
sage: result, certificate = M.is_totally_unimodular(certificate=True)
sage: certificate.graph() == digraph
True
sage: certificate.forest_edges() == forest_arcs
True
sage: certificate.coforest_edges() == coforest_arcs
True

Python

>>> from sage.all import *
>>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
>>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(6), Integer(7), sparse=True),
...                           [[-Integer(1),  Integer(0),  Integer(0),  Integer(0),  Integer(1), -Integer(1),  Integer(0)],
...                            [ Integer(1),  Integer(0),  Integer(0),  Integer(1), -Integer(1),  Integer(1),  Integer(0)],
...                            [ Integer(0), -Integer(1),  Integer(0), -Integer(1),  Integer(1), -Integer(1),  Integer(0)],
...                            [ Integer(0),  Integer(1),  Integer(0),  Integer(0),  Integer(0),  Integer(0),  Integer(1)],
...                            [ Integer(0),  Integer(0),  Integer(1), -Integer(1),  Integer(1),  Integer(0),  Integer(1)],
...                            [ Integer(0),  Integer(0), -Integer(1),  Integer(1), -Integer(1),  Integer(0),  Integer(0)]])
>>> M.is_network_matrix()
True
>>> result, certificate = M.is_network_matrix(certificate=True)
>>> result, certificate
(True,
 (Digraph on 7 vertices,
  ((9, 8), (3, 8), (3, 4), (5, 4), (4, 6), (0, 6)),
  ((3, 9), (5, 3), (4, 0), (0, 8), (9, 0), (4, 9), (5, 6))))
>>> digraph, forest_arcs, coforest_arcs = certificate
>>> result, certificate = M.is_totally_unimodular(certificate=True)
>>> certificate.graph() == digraph
True
>>> certificate.forest_edges() == forest_arcs
True
>>> certificate.coforest_edges() == coforest_arcs
True

forest_edges()[source]¶

Return the forest edges of self.

If self.base_ring() is \(\GF{2}\), then return edges. If self.base_ring() is \(\GF{3}\) or \(\ZZ\), then arcs.

EXAMPLES:

Undirected graph:

Sage

sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 2, sparse=True),
....:                           [[1, 0], [1, 1], [0,1]]); M
[1 0]
[1 1]
[0 1]
sage: result, certificate = M._is_binary_linear_matroid_regular(certificate=True)
sage: result, certificate
(True, GraphicNode (3×2))
sage: certificate.forest_edges()
((1, 2), (7, 1), (12, 7))
sage: certificate.coforest_edges()
((2, 7), (1, 12))

Python

>>> from sage.all import *
>>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
>>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(3), Integer(2), sparse=True),
...                           [[Integer(1), Integer(0)], [Integer(1), Integer(1)], [Integer(0),Integer(1)]]); M
[1 0]
[1 1]
[0 1]
>>> result, certificate = M._is_binary_linear_matroid_regular(certificate=True)
>>> result, certificate
(True, GraphicNode (3×2))
>>> certificate.forest_edges()
((1, 2), (7, 1), (12, 7))
>>> certificate.coforest_edges()
((2, 7), (1, 12))

Directed graph:

Sage

sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 2, sparse=True),
....:                           [[1, 0], [-1, 1], [0,-1]]); M
[ 1  0]
[-1  1]
[ 0 -1]
sage: result, certificate = M.is_totally_unimodular(certificate=True)
sage: result, certificate
(True, GraphicNode (3×2))
sage: certificate.forest_edges()
((2, 1), (7, 1), (7, 12))
sage: certificate.coforest_edges()
((2, 7), (12, 1))

Python

>>> from sage.all import *
>>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
>>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(3), Integer(2), sparse=True),
...                           [[Integer(1), Integer(0)], [-Integer(1), Integer(1)], [Integer(0),-Integer(1)]]); M
[ 1  0]
[-1  1]
[ 0 -1]
>>> result, certificate = M.is_totally_unimodular(certificate=True)
>>> result, certificate
(True, GraphicNode (3×2))
>>> certificate.forest_edges()
((2, 1), (7, 1), (7, 12))
>>> certificate.coforest_edges()
((2, 7), (12, 1))

Starting with a morphism:

Sage

sage: from sage.matrix.seymour_decomposition import UnknownNode
sage: phi = matrix(ZZ, [[1, 0], [1, 1], [0, 1]],
....:              row_keys=['a', 'b', 'c'], column_keys=['v', 'w'])
sage: phi; phi._unicode_art_matrix()
Generic morphism:
From: Free module generated by {'v', 'w'} over Integer Ring
To:   Free module generated by {'a', 'b', 'c'} over Integer Ring
  v w
a⎛1 0⎞
b⎜1 1⎟
c⎝0 1⎠
sage: phi_node = UnknownNode(phi)
sage: is_graphic, rephined_node = phi_node._is_binary_linear_matroid_graphic(decomposition=True)
sage: is_graphic, rephined_node
(True, GraphicNode (3×2))
sage: rephined_node.forest_edges()
{'a': (1, 2), 'b': (7, 1), 'c': (12, 7)}
sage: phi_node  # still in the dark about graphicness
UnknownNode (3×2)

Python

>>> from sage.all import *
>>> from sage.matrix.seymour_decomposition import UnknownNode
>>> phi = matrix(ZZ, [[Integer(1), Integer(0)], [Integer(1), Integer(1)], [Integer(0), Integer(1)]],
...              row_keys=['a', 'b', 'c'], column_keys=['v', 'w'])
>>> phi; phi._unicode_art_matrix()
Generic morphism:
From: Free module generated by {'v', 'w'} over Integer Ring
To:   Free module generated by {'a', 'b', 'c'} over Integer Ring
  v w
a⎛1 0⎞
b⎜1 1⎟
c⎝0 1⎠
>>> phi_node = UnknownNode(phi)
>>> is_graphic, rephined_node = phi_node._is_binary_linear_matroid_graphic(decomposition=True)
>>> is_graphic, rephined_node
(True, GraphicNode (3×2))
>>> rephined_node.forest_edges()
{'a': (1, 2), 'b': (7, 1), 'c': (12, 7)}
>>> phi_node  # still in the dark about graphicness
UnknownNode (3×2)

graph()[source]¶

Return the graph representing self.

If self.base_ring() is \(\GF{2}\), then return an undirected graph. If self.base_ring() is \(\GF{3}\) or \(\ZZ\), then return directed graph.

EXAMPLES:

Undirected graph:

Sage

sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 2, sparse=True),
....:                           [[1, 0], [1, 1], [0,1]]); M
[1 0]
[1 1]
[0 1]
sage: result, certificate = M._is_binary_linear_matroid_regular(certificate=True)
sage: result, certificate
(True, GraphicNode (3×2))
sage: G = certificate.graph(); G
Graph on 4 vertices
sage: G.vertices(sort=True)
[1, 2, 7, 12]
sage: G.edges(sort=True)
[(1, 2, None), (1, 7, None), (1, 12, None), (2, 7, None), (7, 12, None)]

Python

>>> from sage.all import *
>>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
>>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(3), Integer(2), sparse=True),
...                           [[Integer(1), Integer(0)], [Integer(1), Integer(1)], [Integer(0),Integer(1)]]); M
[1 0]
[1 1]
[0 1]
>>> result, certificate = M._is_binary_linear_matroid_regular(certificate=True)
>>> result, certificate
(True, GraphicNode (3×2))
>>> G = certificate.graph(); G
Graph on 4 vertices
>>> G.vertices(sort=True)
[1, 2, 7, 12]
>>> G.edges(sort=True)
[(1, 2, None), (1, 7, None), (1, 12, None), (2, 7, None), (7, 12, None)]

Directed graph:

Sage

sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 2, sparse=True),
....:                           [[1, 0], [-1, 1], [0,-1]]); M
[ 1  0]
[-1  1]
[ 0 -1]
sage: result, certificate = M.is_totally_unimodular(certificate=True)
sage: result, certificate
(True, GraphicNode (3×2))
sage: G = certificate.graph(); G
Digraph on 4 vertices
sage: G.vertices(sort=True)
[1, 2, 7, 12]
sage: G.edges(sort=True)
[(2, 1, None), (2, 7, None), (7, 1, None), (7, 12, None), (12, 1, None)]

Python

>>> from sage.all import *
>>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
>>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(3), Integer(2), sparse=True),
...                           [[Integer(1), Integer(0)], [-Integer(1), Integer(1)], [Integer(0),-Integer(1)]]); M
[ 1  0]
[-1  1]
[ 0 -1]
>>> result, certificate = M.is_totally_unimodular(certificate=True)
>>> result, certificate
(True, GraphicNode (3×2))
>>> G = certificate.graph(); G
Digraph on 4 vertices
>>> G.vertices(sort=True)
[1, 2, 7, 12]
>>> G.edges(sort=True)
[(2, 1, None), (2, 7, None), (7, 1, None), (7, 12, None), (12, 1, None)]

class sage.matrix.seymour_decomposition.CographicNode[source]¶

Bases: BaseGraphicNode

coforest_edges()[source]¶

Return the forest edges of the cograph of self.

forest_edges()[source]¶

Return the forest edges of the cograph of self.

EXAMPLES:

Undirected graph:

Sage

sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 4, 5, sparse=True),
....:                           [[1, 1, 1, 0, 0],
....:                            [0, 1, 1, 1, 0],
....:                            [0, 0, 1, 1, 1],
....:                            [1, 0, 0, 1, 1]]); M
[1 1 1 0 0]
[0 1 1 1 0]
[0 0 1 1 1]
[1 0 0 1 1]
sage: result, certificate = M._is_binary_linear_matroid_regular(certificate=True)
sage: result, certificate
(True, CographicNode (4×5))
sage: certificate.forest_edges()
((7, 8), (5, 0), (0, 7), (1, 7), (2, 1))
sage: certificate.coforest_edges()
((5, 8), (5, 1), (0, 2), (2, 8))

Python

>>> from sage.all import *
>>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
>>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(4), Integer(5), sparse=True),
...                           [[Integer(1), Integer(1), Integer(1), Integer(0), Integer(0)],
...                            [Integer(0), Integer(1), Integer(1), Integer(1), Integer(0)],
...                            [Integer(0), Integer(0), Integer(1), Integer(1), Integer(1)],
...                            [Integer(1), Integer(0), Integer(0), Integer(1), Integer(1)]]); M
[1 1 1 0 0]
[0 1 1 1 0]
[0 0 1 1 1]
[1 0 0 1 1]
>>> result, certificate = M._is_binary_linear_matroid_regular(certificate=True)
>>> result, certificate
(True, CographicNode (4×5))
>>> certificate.forest_edges()
((7, 8), (5, 0), (0, 7), (1, 7), (2, 1))
>>> certificate.coforest_edges()
((5, 8), (5, 1), (0, 2), (2, 8))

Directed graph:

Sage

sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 4, 5, sparse=True),
....:                           [[1, -1, 1, 0, 0],
....:                            [0, 1, -1, 1, 0],
....:                            [0, 0, 1, -1, 1],
....:                            [1, 0, 0, 1, -1]]); M
[ 1 -1  1  0  0]
[ 0  1 -1  1  0]
[ 0  0  1 -1  1]
[ 1  0  0  1 -1]
sage: result, certificate = M.is_totally_unimodular(certificate=True)
sage: result, certificate
(True, CographicNode (4×5))
sage: certificate.forest_edges()
((7, 8), (0, 5), (0, 7), (1, 7), (1, 2))
sage: certificate.coforest_edges()
((5, 8), (1, 5), (0, 2), (2, 8))

Python

>>> from sage.all import *
>>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
>>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(4), Integer(5), sparse=True),
...                           [[Integer(1), -Integer(1), Integer(1), Integer(0), Integer(0)],
...                            [Integer(0), Integer(1), -Integer(1), Integer(1), Integer(0)],
...                            [Integer(0), Integer(0), Integer(1), -Integer(1), Integer(1)],
...                            [Integer(1), Integer(0), Integer(0), Integer(1), -Integer(1)]]); M
[ 1 -1  1  0  0]
[ 0  1 -1  1  0]
[ 0  0  1 -1  1]
[ 1  0  0  1 -1]
>>> result, certificate = M.is_totally_unimodular(certificate=True)
>>> result, certificate
(True, CographicNode (4×5))
>>> certificate.forest_edges()
((7, 8), (0, 5), (0, 7), (1, 7), (1, 2))
>>> certificate.coforest_edges()
((5, 8), (1, 5), (0, 2), (2, 8))

graph()[source]¶

Actually the cograph of matrix, in the case where it is not graphic.

EXAMPLES:

Undirected graph:

Sage

sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 4, 5, sparse=True),
....:                           [[1, 1, 1, 0, 0],
....:                            [0, 1, 1, 1, 0],
....:                            [0, 0, 1, 1, 1],
....:                            [1, 0, 0, 1, 1]]); M
[1 1 1 0 0]
[0 1 1 1 0]
[0 0 1 1 1]
[1 0 0 1 1]
sage: result, certificate = M._is_binary_linear_matroid_regular(certificate=True)
sage: certificate
CographicNode (4×5)
sage: certificate.base_ring()
Finite Field of size 2
sage: G = certificate.graph(); G
Graph on 6 vertices
sage: G.vertices(sort=True)
[0, 1, 2, 5, 7, 8]
sage: G.edges(sort=True)
[(0, 2, None), (0, 5, None), (0, 7, None), (1, 2, None), (1, 5, None),
 (1, 7, None), (2, 8, None), (5, 8, None), (7, 8, None)]

Python

>>> from sage.all import *
>>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
>>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(4), Integer(5), sparse=True),
...                           [[Integer(1), Integer(1), Integer(1), Integer(0), Integer(0)],
...                            [Integer(0), Integer(1), Integer(1), Integer(1), Integer(0)],
...                            [Integer(0), Integer(0), Integer(1), Integer(1), Integer(1)],
...                            [Integer(1), Integer(0), Integer(0), Integer(1), Integer(1)]]); M
[1 1 1 0 0]
[0 1 1 1 0]
[0 0 1 1 1]
[1 0 0 1 1]
>>> result, certificate = M._is_binary_linear_matroid_regular(certificate=True)
>>> certificate
CographicNode (4×5)
>>> certificate.base_ring()
Finite Field of size 2
>>> G = certificate.graph(); G
Graph on 6 vertices
>>> G.vertices(sort=True)
[0, 1, 2, 5, 7, 8]
>>> G.edges(sort=True)
[(0, 2, None), (0, 5, None), (0, 7, None), (1, 2, None), (1, 5, None),
 (1, 7, None), (2, 8, None), (5, 8, None), (7, 8, None)]

Directed graph:

Sage

sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 4, 5, sparse=True),
....:                           [[1, -1, 1, 0, 0],
....:                            [0, 1, -1, 1, 0],
....:                            [0, 0, 1, -1, 1],
....:                            [1, 0, 0, 1, -1]]); M
[ 1 -1  1  0  0]
[ 0  1 -1  1  0]
[ 0  0  1 -1  1]
[ 1  0  0  1 -1]
sage: result, certificate = M.is_totally_unimodular(certificate=True)
sage: certificate
CographicNode (4×5)
sage: G = certificate.graph(); G
Digraph on 6 vertices
sage: G.vertices(sort=True)
[0, 1, 2, 5, 7, 8]
sage: G.edges(sort=True)
[(0, 2, None), (0, 5, None), (0, 7, None), (1, 2, None), (1, 5, None),
 (1, 7, None), (2, 8, None), (5, 8, None), (7, 8, None)]

Python

>>> from sage.all import *
>>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
>>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(4), Integer(5), sparse=True),
...                           [[Integer(1), -Integer(1), Integer(1), Integer(0), Integer(0)],
...                            [Integer(0), Integer(1), -Integer(1), Integer(1), Integer(0)],
...                            [Integer(0), Integer(0), Integer(1), -Integer(1), Integer(1)],
...                            [Integer(1), Integer(0), Integer(0), Integer(1), -Integer(1)]]); M
[ 1 -1  1  0  0]
[ 0  1 -1  1  0]
[ 0  0  1 -1  1]
[ 1  0  0  1 -1]
>>> result, certificate = M.is_totally_unimodular(certificate=True)
>>> certificate
CographicNode (4×5)
>>> G = certificate.graph(); G
Digraph on 6 vertices
>>> G.vertices(sort=True)
[0, 1, 2, 5, 7, 8]
>>> G.edges(sort=True)
[(0, 2, None), (0, 5, None), (0, 7, None), (1, 2, None), (1, 5, None),
 (1, 7, None), (2, 8, None), (5, 8, None), (7, 8, None)]

class sage.matrix.seymour_decomposition.DecompositionNode[source]¶

Bases: SageObject

Base class for nodes in Seymour’s decomposition

as_ordered_tree()[source]¶

Return the decomposition tree rooted at self.

EXAMPLES:

Sage

sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
sage: M = matrix([[1, 0], [-1, 1], [0, 1]], sparse=True)
sage: M2 = block_diagonal_matrix([M, M], sparse=True)
sage: M2cmr = Matrix_cmr_chr_sparse(M2.parent(), M2); M2cmr
[ 1  0  0  0]
[-1  1  0  0]
[ 0  1  0  0]
[ 0  0  1  0]
[ 0  0 -1  1]
[ 0  0  0  1]
sage: result, certificate = M2cmr.is_totally_unimodular(certificate=True)
sage: T = certificate.as_ordered_tree(); T
OneSumNode (6×4) with 2 children[GraphicNode (3×2)[], GraphicNode (3×2)[]]
sage: unicode_art(T)
╭───────────OneSumNode (6×4) with 2 children
│                 │
GraphicNode (3×2) GraphicNode (3×2)

Python

>>> from sage.all import *
>>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
>>> M = matrix([[Integer(1), Integer(0)], [-Integer(1), Integer(1)], [Integer(0), Integer(1)]], sparse=True)
>>> M2 = block_diagonal_matrix([M, M], sparse=True)
>>> M2cmr = Matrix_cmr_chr_sparse(M2.parent(), M2); M2cmr
[ 1  0  0  0]
[-1  1  0  0]
[ 0  1  0  0]
[ 0  0  1  0]
[ 0  0 -1  1]
[ 0  0  0  1]
>>> result, certificate = M2cmr.is_totally_unimodular(certificate=True)
>>> T = certificate.as_ordered_tree(); T
OneSumNode (6×4) with 2 children[GraphicNode (3×2)[], GraphicNode (3×2)[]]
>>> unicode_art(T)
╭───────────OneSumNode (6×4) with 2 children
│                 │
GraphicNode (3×2) GraphicNode (3×2)

base_ring()[source]¶

Return the base ring of the matrix representing the node.

child_keys()[source]¶

Return a tuple of the tuples of the row and column keys of children in the parent node.

OUTPUT: a tuple of (row keys, column keys)

If the number of children is 1, then output (row keys, column keys).

EXAMPLES:

Sage

sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 2, sparse=True),
....:                           [[1, 0], [-1, 1], [0, 1]]); M
[ 1  0]
[-1  1]
[ 0  1]
sage: result, certificate = M.is_totally_unimodular(certificate=True)
sage: certificate.child_keys()
()

sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
sage: M = matrix([[1, 0], [-1, 1], [0, 1]], sparse=True)
sage: M2 = block_diagonal_matrix([M, M], sparse=True)
sage: M2cmr = Matrix_cmr_chr_sparse(M2.parent(), M2); M2cmr
[ 1  0  0  0]
[-1  1  0  0]
[ 0  1  0  0]
[ 0  0  1  0]
[ 0  0 -1  1]
[ 0  0  0  1]
sage: result, certificate = M2cmr.is_totally_unimodular(certificate=True)
sage: result, certificate
(True, OneSumNode (6×4) with 2 children)
sage: C = certificate.summands(); C
(GraphicNode (3×2), GraphicNode (3×2))
sage: certificate.child_keys()[0]
((0, 1, 2), (0, 1))
sage: certificate.child_keys()[1]
((3, 4, 5), (2, 3))

sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
sage: R12 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 9, 12, sparse=True),
....:           [[ 1, -1,  0,  0,  0,  0,  0,  0,  1,  1,  1,  1],
....:            [ 0,  0,  0,  1, -1,  0,  0,  0,  1,  1,  1,  1],
....:            [ 0,  0,  0,  0,  0,  0,  1,  1,  1,  1,  1,  1],
....:            [ 1,  0,  1,  0,  0,  0,  0,  0,  1,  1,  0,  0],
....:            [ 0,  1,  1,  0,  0,  0,  0,  0,  0,  0, -1, -1],
....:            [ 0,  0,  0,  1,  0,  1,  0,  0,  1,  1,  0,  0],
....:            [ 0,  0,  0,  0,  1,  1,  0,  0,  0,  0, -1, -1],
....:            [ 0,  0,  0,  0,  0,  0,  1,  0,  1,  0,  1,  0],
....:            [ 0,  0,  0,  0,  0,  0,  0,  1,  0,  1,  0,  1]])
sage: result, certificate = R12.is_totally_unimodular(certificate=True,
....:                           decompose_strategy="delta_pivot",
....:                           row_keys=['r1', 'r2', 'r3', 'r4', 'r5',
....:                                     'r6', 'r7', 'r8', 'r9'],
....:                           column_keys=['a','b','c','d','e','f',
....:                                        'g','h','i','j','k','l'])
sage: C = certificate.child_nodes()[0]; C
DeltaSumNode (9×12)
sage: C1, C2 = C.child_nodes()
sage: C1.matrix()
[ 0  0  1  1  1  1  1]
[ 1  1  0  0  0 -1 -1]
[ 1  0 -1  0 -1 -1 -1]
[ 0  1  1  0  1  0  0]
[ 0  0  0 -1 -1  0 -1]
sage: C2.matrix()
[-1  0  1 -1  0  0  0  0 -1]
[ 0  0 -1  1  0  1 -1  0  1]
[ 1  1  0  1  1  0  0  0  1]
[ 1  1  0  1  1  0  0  0  0]
[ 1  1 -1  1  0  1  0  1  1]
[ 1  1  0  0  0  0  1  1  0]
sage: certificate.child_keys()
((i, r2, r3, r4, r5, r6, r7, r8, r9), (a, b, c, d, e, f, g, h, r1, j, k, l))
sage: C.matrix()
[ 1 -1  0  0  0  0  0  0 -1  1  1  1]
[-1  1  0  1 -1  0  0  0  1  0  0  0]
[-1  1  0  0  0  0  1  1  1  0  0  0]
[ 0  1  1  0  0  0  0  0  1  0 -1 -1]
[ 0  1  1  0  0  0  0  0  0  0 -1 -1]
[-1  1  0  1  0  1  0  0  1  0 -1 -1]
[ 0  0  0  0  1  1  0  0  0  0 -1 -1]
[-1  1  0  0  0  0  1  0  1 -1  0 -1]
[ 0  0  0  0  0  0  0  1  0  1  0  1]
sage: C.child_keys()
(((i, r3, r8, r9, r4), (g, h, j, k, l, a, +a-r4)),
 ((i, r2, r4, r5, r6, r7), (-i+k, k, a, b, c, d, e, f, r1)))

sage: M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 2, 2, sparse=True),
....:                            [[1, 1], [-1, 0]]); M2
[ 1  1]
[-1  0]
sage: result, certificate = M2.is_totally_unimodular(certificate=True); certificate
GraphicNode (2×2)
sage: certificate.child_keys()
()

Python

>>> from sage.all import *
>>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
>>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(3), Integer(2), sparse=True),
...                           [[Integer(1), Integer(0)], [-Integer(1), Integer(1)], [Integer(0), Integer(1)]]); M
[ 1  0]
[-1  1]
[ 0  1]
>>> result, certificate = M.is_totally_unimodular(certificate=True)
>>> certificate.child_keys()
()

>>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
>>> M = matrix([[Integer(1), Integer(0)], [-Integer(1), Integer(1)], [Integer(0), Integer(1)]], sparse=True)
>>> M2 = block_diagonal_matrix([M, M], sparse=True)
>>> M2cmr = Matrix_cmr_chr_sparse(M2.parent(), M2); M2cmr
[ 1  0  0  0]
[-1  1  0  0]
[ 0  1  0  0]
[ 0  0  1  0]
[ 0  0 -1  1]
[ 0  0  0  1]
>>> result, certificate = M2cmr.is_totally_unimodular(certificate=True)
>>> result, certificate
(True, OneSumNode (6×4) with 2 children)
>>> C = certificate.summands(); C
(GraphicNode (3×2), GraphicNode (3×2))
>>> certificate.child_keys()[Integer(0)]
((0, 1, 2), (0, 1))
>>> certificate.child_keys()[Integer(1)]
((3, 4, 5), (2, 3))

>>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
>>> R12 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(9), Integer(12), sparse=True),
...           [[ Integer(1), -Integer(1),  Integer(0),  Integer(0),  Integer(0),  Integer(0),  Integer(0),  Integer(0),  Integer(1),  Integer(1),  Integer(1),  Integer(1)],
...            [ Integer(0),  Integer(0),  Integer(0),  Integer(1), -Integer(1),  Integer(0),  Integer(0),  Integer(0),  Integer(1),  Integer(1),  Integer(1),  Integer(1)],
...            [ Integer(0),  Integer(0),  Integer(0),  Integer(0),  Integer(0),  Integer(0),  Integer(1),  Integer(1),  Integer(1),  Integer(1),  Integer(1),  Integer(1)],
...            [ Integer(1),  Integer(0),  Integer(1),  Integer(0),  Integer(0),  Integer(0),  Integer(0),  Integer(0),  Integer(1),  Integer(1),  Integer(0),  Integer(0)],
...            [ Integer(0),  Integer(1),  Integer(1),  Integer(0),  Integer(0),  Integer(0),  Integer(0),  Integer(0),  Integer(0),  Integer(0), -Integer(1), -Integer(1)],
...            [ Integer(0),  Integer(0),  Integer(0),  Integer(1),  Integer(0),  Integer(1),  Integer(0),  Integer(0),  Integer(1),  Integer(1),  Integer(0),  Integer(0)],
...            [ Integer(0),  Integer(0),  Integer(0),  Integer(0),  Integer(1),  Integer(1),  Integer(0),  Integer(0),  Integer(0),  Integer(0), -Integer(1), -Integer(1)],
...            [ Integer(0),  Integer(0),  Integer(0),  Integer(0),  Integer(0),  Integer(0),  Integer(1),  Integer(0),  Integer(1),  Integer(0),  Integer(1),  Integer(0)],
...            [ Integer(0),  Integer(0),  Integer(0),  Integer(0),  Integer(0),  Integer(0),  Integer(0),  Integer(1),  Integer(0),  Integer(1),  Integer(0),  Integer(1)]])
>>> result, certificate = R12.is_totally_unimodular(certificate=True,
...                           decompose_strategy="delta_pivot",
...                           row_keys=['r1', 'r2', 'r3', 'r4', 'r5',
...                                     'r6', 'r7', 'r8', 'r9'],
...                           column_keys=['a','b','c','d','e','f',
...                                        'g','h','i','j','k','l'])
>>> C = certificate.child_nodes()[Integer(0)]; C
DeltaSumNode (9×12)
>>> C1, C2 = C.child_nodes()
>>> C1.matrix()
[ 0  0  1  1  1  1  1]
[ 1  1  0  0  0 -1 -1]
[ 1  0 -1  0 -1 -1 -1]
[ 0  1  1  0  1  0  0]
[ 0  0  0 -1 -1  0 -1]
>>> C2.matrix()
[-1  0  1 -1  0  0  0  0 -1]
[ 0  0 -1  1  0  1 -1  0  1]
[ 1  1  0  1  1  0  0  0  1]
[ 1  1  0  1  1  0  0  0  0]
[ 1  1 -1  1  0  1  0  1  1]
[ 1  1  0  0  0  0  1  1  0]
>>> certificate.child_keys()
((i, r2, r3, r4, r5, r6, r7, r8, r9), (a, b, c, d, e, f, g, h, r1, j, k, l))
>>> C.matrix()
[ 1 -1  0  0  0  0  0  0 -1  1  1  1]
[-1  1  0  1 -1  0  0  0  1  0  0  0]
[-1  1  0  0  0  0  1  1  1  0  0  0]
[ 0  1  1  0  0  0  0  0  1  0 -1 -1]
[ 0  1  1  0  0  0  0  0  0  0 -1 -1]
[-1  1  0  1  0  1  0  0  1  0 -1 -1]
[ 0  0  0  0  1  1  0  0  0  0 -1 -1]
[-1  1  0  0  0  0  1  0  1 -1  0 -1]
[ 0  0  0  0  0  0  0  1  0  1  0  1]
>>> C.child_keys()
(((i, r3, r8, r9, r4), (g, h, j, k, l, a, +a-r4)),
 ((i, r2, r4, r5, r6, r7), (-i+k, k, a, b, c, d, e, f, r1)))

>>> M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(2), Integer(2), sparse=True),
...                            [[Integer(1), Integer(1)], [-Integer(1), Integer(0)]]); M2
[ 1  1]
[-1  0]
>>> result, certificate = M2.is_totally_unimodular(certificate=True); certificate
GraphicNode (2×2)
>>> certificate.child_keys()
()

child_nodes()[source]¶

Return a tuple of the children.

The children are sorted by the ordering inherited from cmr, which is their appearance in the parent.

In the case of SumNode, this is the same as summands().

For graphic or leaf nodes, it returns the empty tuple.

EXAMPLES:

Sage

sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
sage: M = Matrix_cmr_chr_sparse.one_sum([[1, 0], [-1, 1]],
....:                                   [[1, 1], [-1, 0]],
....:                                   [[1, 0], [0,1]]); M
[ 1  0| 0  0| 0  0]
[-1  1| 0  0| 0  0]
[-----+-----+-----]
[ 0  0| 1  1| 0  0]
[ 0  0|-1  0| 0  0]
[-----+-----+-----]
[ 0  0| 0  0| 1  0]
[ 0  0| 0  0| 0  1]
sage: result, certificate = M.is_totally_unimodular(certificate=True); certificate
OneSumNode (6×6) with 4 children
sage: certificate.child_nodes()
(GraphicNode (2×2), GraphicNode (2×2), GraphicNode (1×1), GraphicNode (1×1))

sage: M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 2, 2, sparse=True),
....:                            [[1, 1], [-1, 0]]); M2
[ 1  1]
[-1  0]
sage: result, certificate = M2.is_totally_unimodular(certificate=True); certificate
GraphicNode (2×2)
sage: certificate.child_nodes()
()

Python

>>> from sage.all import *
>>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
>>> M = Matrix_cmr_chr_sparse.one_sum([[Integer(1), Integer(0)], [-Integer(1), Integer(1)]],
...                                   [[Integer(1), Integer(1)], [-Integer(1), Integer(0)]],
...                                   [[Integer(1), Integer(0)], [Integer(0),Integer(1)]]); M
[ 1  0| 0  0| 0  0]
[-1  1| 0  0| 0  0]
[-----+-----+-----]
[ 0  0| 1  1| 0  0]
[ 0  0|-1  0| 0  0]
[-----+-----+-----]
[ 0  0| 0  0| 1  0]
[ 0  0| 0  0| 0  1]
>>> result, certificate = M.is_totally_unimodular(certificate=True); certificate
OneSumNode (6×6) with 4 children
>>> certificate.child_nodes()
(GraphicNode (2×2), GraphicNode (2×2), GraphicNode (1×1), GraphicNode (1×1))

>>> M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(2), Integer(2), sparse=True),
...                            [[Integer(1), Integer(1)], [-Integer(1), Integer(0)]]); M2
[ 1  1]
[-1  0]
>>> result, certificate = M2.is_totally_unimodular(certificate=True); certificate
GraphicNode (2×2)
>>> certificate.child_nodes()
()

column_keys()[source]¶

Return the column keys of this node.

OUTPUT: a tuple or None

EXAMPLES:

Sage

sage: from sage.matrix.seymour_decomposition import UnknownNode
sage: node = UnknownNode(matrix(ZZ, [[1, 0, 1], [0, 1, 1]]),
....:                    row_keys='ab',
....:                    column_keys=range(3)); node
UnknownNode (2×3)
sage: node.column_keys()
(0, 1, 2)

Python

>>> from sage.all import *
>>> from sage.matrix.seymour_decomposition import UnknownNode
>>> node = UnknownNode(matrix(ZZ, [[Integer(1), Integer(0), Integer(1)], [Integer(0), Integer(1), Integer(1)]]),
...                    row_keys='ab',
...                    column_keys=range(Integer(3))); node
UnknownNode (2×3)
>>> node.column_keys()
(0, 1, 2)

complete_decomposition(time_limit=60.0, use_direct_graphicness_test=True, prefer_graphicness=True, series_parallel_ok=True, check_graphic_minors_planar=False, stop_when_nonTU=False, stop_when_nonnetwork=False, stop_when_nonconetwork=False, stop_when_nonnetwork_and_nonconetwork=False, decompose_strategy='delta_three', construct_leaf_graphs=False, construct_all_graphs=False)[source]¶

Complete the Seymour’s decomposition of self over \(\GF{3}\) or \(\ZZ\).

INPUT:

• stop_when_nonTU – boolean; whether to stop decomposing once being non-TU is determined.

• stop_when_nonnetwork – boolean; whether to stop decomposing once being non-network is determined.

• stop_when_nonconetwork – boolean; whether to stop decomposing once being non-conetwork is determined.

• stop_when_nonnetwork_and_nonconetwork – boolean; whether to stop decomposing once not being network and not being conetwork is determined.

For a description of other parameters, see sage.matrix.matrix_cmr_sparse._set_cmr_seymour_parameters().

EXAMPLES:

Sage

sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 9, 9, sparse=True),
....:                           [[1, 1, 0, 0, 0, 0, 0, 0, 0],
....:                            [1, 1, 1, 0, 0, 0, 0, 0, 0],
....:                            [1, 0, 0, 1, 0, 0, 0, 0, 0],
....:                            [0, 1, 1, 1, 0, 0, 0, 0, 0],
....:                            [0, 0, 1, 1, 0, 0, 0, 0, 0],
....:                            [0, 0, 0, 0, 1, 1, 1, 0, 0],
....:                            [0, 0, 0, 0, 1, 1, 0, 1, 0],
....:                            [0, 0, 0, 0, 0, 1, 0, 1, 1],
....:                            [0, 0, 0, 0, 0, 0, 1, 1, 1]])
sage: from sage.matrix.seymour_decomposition import UnknownNode
sage: node = UnknownNode(M); node
UnknownNode (9×9)
sage: C0 = node.complete_decomposition()
sage: unicode_art(C0)
╭OneSumNode (9×9) with 2 children─╮
│                                 │
ThreeConnectedIrregularNode (5×4) ThreeConnectedIrregularNode (4×5)
sage: C1, C2 = C0.child_nodes()
sage: C11 = C1.complete_decomposition(); C11
ThreeConnectedIrregularNode (5×4)
sage: unicode_art(C11)
ThreeConnectedIrregularNode (5×4)
sage: C1.matrix()
[1 1 0 0]
[1 1 1 0]
[0 1 1 1]
[1 0 0 1]
[0 0 1 1]
sage: C11.matrix()
[1 1 0 0]
[1 1 1 0]
[0 1 1 1]
[1 0 0 1]
[0 0 1 1]
sage: C22 = C2.complete_decomposition(); C22
ThreeConnectedIrregularNode (4×5)
sage: unicode_art(C22)
ThreeConnectedIrregularNode (4×5)
sage: C2.matrix()
[1 1 1 0 0]
[0 0 1 1 1]
[0 1 0 1 1]
[1 1 0 1 0]
sage: C22.matrix()
[1 1 1 0 0]
[0 0 1 1 1]
[0 1 0 1 1]
[1 1 0 1 0]

Python

>>> from sage.all import *
>>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
>>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(9), Integer(9), sparse=True),
...                           [[Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...                            [Integer(1), Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...                            [Integer(1), Integer(0), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...                            [Integer(0), Integer(1), Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...                            [Integer(0), Integer(0), Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...                            [Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(1), Integer(1), Integer(0), Integer(0)],
...                            [Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(1), Integer(0), Integer(1), Integer(0)],
...                            [Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0), Integer(1), Integer(1)],
...                            [Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(1), Integer(1)]])
>>> from sage.matrix.seymour_decomposition import UnknownNode
>>> node = UnknownNode(M); node
UnknownNode (9×9)
>>> C0 = node.complete_decomposition()
>>> unicode_art(C0)
╭OneSumNode (9×9) with 2 children─╮
│                                 │
ThreeConnectedIrregularNode (5×4) ThreeConnectedIrregularNode (4×5)
>>> C1, C2 = C0.child_nodes()
>>> C11 = C1.complete_decomposition(); C11
ThreeConnectedIrregularNode (5×4)
>>> unicode_art(C11)
ThreeConnectedIrregularNode (5×4)
>>> C1.matrix()
[1 1 0 0]
[1 1 1 0]
[0 1 1 1]
[1 0 0 1]
[0 0 1 1]
>>> C11.matrix()
[1 1 0 0]
[1 1 1 0]
[0 1 1 1]
[1 0 0 1]
[0 0 1 1]
>>> C22 = C2.complete_decomposition(); C22
ThreeConnectedIrregularNode (4×5)
>>> unicode_art(C22)
ThreeConnectedIrregularNode (4×5)
>>> C2.matrix()
[1 1 1 0 0]
[0 0 1 1 1]
[0 1 0 1 1]
[1 1 0 1 0]
>>> C22.matrix()
[1 1 1 0 0]
[0 0 1 1 1]
[0 1 0 1 1]
[1 1 0 1 0]

dimensions()[source]¶

Return the number of rows and columns of this node.

EXAMPLES:

Sage

sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 2, sparse=True),
....:                           [[1, 0], [-1, 1], [0, 1]]); M
[ 1  0]
[-1  1]
[ 0  1]
sage: result, certificate = M.is_totally_unimodular(certificate=True)
sage: result, certificate
(True, GraphicNode (3×2))
sage: certificate.dimensions()
(3, 2)

sage: from sage.matrix.seymour_decomposition import UnknownNode
sage: node = UnknownNode([[1, 1], [0, 1]]); node
UnknownNode (2×2)
sage: node.dimensions()
(2, 2)

Python

>>> from sage.all import *
>>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
>>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(3), Integer(2), sparse=True),
...                           [[Integer(1), Integer(0)], [-Integer(1), Integer(1)], [Integer(0), Integer(1)]]); M
[ 1  0]
[-1  1]
[ 0  1]
>>> result, certificate = M.is_totally_unimodular(certificate=True)
>>> result, certificate
(True, GraphicNode (3×2))
>>> certificate.dimensions()
(3, 2)

>>> from sage.matrix.seymour_decomposition import UnknownNode
>>> node = UnknownNode([[Integer(1), Integer(1)], [Integer(0), Integer(1)]]); node
UnknownNode (2×2)
>>> node.dimensions()
(2, 2)

is_conetwork_matrix(decomposition=False, **kwds)[source]¶

Return whether the matrix self over \(\GF{3}\) or \(\QQ\) is a conetwork matrix. If there is some entry not in \(\{-1, 0, 1\}\), return False.

This method is based on Seymour’s decomposition. The decomposition will stop once being nonconetwork is detected. For direct conetwork matrix check,

See also

• sage.matrix.matrix_cmr_sparse.Matrix_cmr_chr_sparse.is_conetwork_matrix()

• UnknownNode.is_conetwork_matrix()

• complete_decomposition()

EXAMPLES:

Sage

sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
sage: from sage.matrix.seymour_decomposition import DecompositionNode
sage: A = matrix(ZZ, [[-1, 0, 0, 0, 1,-1, 0],
....:                 [ 1, 0, 0, 1,-1, 1, 0],
....:                 [ 0,-1, 0,-1, 1,-1, 0],
....:                 [ 0, 1, 0, 0, 0, 0, 1],
....:                 [ 0, 0, 1,-1, 1, 0, 1],
....:                 [ 0, 0,-1, 1,-1, 0, 0]])
sage: M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 7, sparse=True), A)
sage: M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 7, 6, sparse=True), A.transpose())
sage: M = Matrix_cmr_chr_sparse.one_sum(M1, M2)
sage: result, certificate = M.is_totally_unimodular(certificate=True,
....:                         row_keys=[f'r{i}' for i in range(13)],
....:                         column_keys=[f'c{i}' for i in range(13)])
sage: node = DecompositionNode.one_sum(*certificate.child_nodes())

sage: result, decomposition = node.is_conetwork_matrix(decomposition=True)
sage: unicode_art(decomposition)
╭─────────OneSumNode (13×13) with 2 children
│                │
PlanarNode (6×7) PlanarNode (7×6)
sage: node._cographicness()
Traceback (most recent call last):
...
ValueError: It is not determined whether the decomposition node is cographic/conetwork

sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 9, 9, sparse=True),
....:                           [[1, 1, 0, 0, 0, 0, 0, 0, 0],
....:                            [-1,-1, 1, 0, 0, 0, 0, 0, 0],
....:                            [1, 0, 0, 1, 0, 0, 0, 0, 0],
....:                            [0, 1,-1,-1, 0, 0, 0, 0, 0],
....:                            [0, 0, 1, 1, 0, 0, 0, 0, 0],
....:                            [0, 0, 0, 0, 1,-1, 1, 0, 0],
....:                            [0, 0, 0, 0, 1,-1, 0, 1, 0],
....:                            [0, 0, 0, 0, 0, 1, 0,-1, 1],
....:                            [0, 0, 0, 0, 0, 0, 1,-1, 1]])
sage: result, certificate = M.is_totally_unimodular(certificate=True,
....:                         row_keys=[f'r{i}' for i in range(9)],
....:                         column_keys=[f'c{i}' for i in range(9)])
sage: node = DecompositionNode.one_sum(*certificate.child_nodes())
sage: result, decomposition = node.is_conetwork_matrix(decomposition=True)
sage: result
False
sage: unicode_art(decomposition)
╭───────────OneSumNode (9×9) with 2 children
│                 │
GraphicNode (5×4) UnknownNode (4×5)
sage: decomposition.child_nodes()[1]._graphicness()
Traceback (most recent call last):
...
ValueError: It is not determined whether the decomposition node is graphic/network

Python

>>> from sage.all import *
>>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
>>> from sage.matrix.seymour_decomposition import DecompositionNode
>>> A = matrix(ZZ, [[-Integer(1), Integer(0), Integer(0), Integer(0), Integer(1),-Integer(1), Integer(0)],
...                 [ Integer(1), Integer(0), Integer(0), Integer(1),-Integer(1), Integer(1), Integer(0)],
...                 [ Integer(0),-Integer(1), Integer(0),-Integer(1), Integer(1),-Integer(1), Integer(0)],
...                 [ Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1)],
...                 [ Integer(0), Integer(0), Integer(1),-Integer(1), Integer(1), Integer(0), Integer(1)],
...                 [ Integer(0), Integer(0),-Integer(1), Integer(1),-Integer(1), Integer(0), Integer(0)]])
>>> M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(6), Integer(7), sparse=True), A)
>>> M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(7), Integer(6), sparse=True), A.transpose())
>>> M = Matrix_cmr_chr_sparse.one_sum(M1, M2)
>>> result, certificate = M.is_totally_unimodular(certificate=True,
...                         row_keys=[f'r{i}' for i in range(Integer(13))],
...                         column_keys=[f'c{i}' for i in range(Integer(13))])
>>> node = DecompositionNode.one_sum(*certificate.child_nodes())

>>> result, decomposition = node.is_conetwork_matrix(decomposition=True)
>>> unicode_art(decomposition)
╭─────────OneSumNode (13×13) with 2 children
│                │
PlanarNode (6×7) PlanarNode (7×6)
>>> node._cographicness()
Traceback (most recent call last):
...
ValueError: It is not determined whether the decomposition node is cographic/conetwork

>>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(9), Integer(9), sparse=True),
...                           [[Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...                            [-Integer(1),-Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...                            [Integer(1), Integer(0), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...                            [Integer(0), Integer(1),-Integer(1),-Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...                            [Integer(0), Integer(0), Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...                            [Integer(0), Integer(0), Integer(0), Integer(0), Integer(1),-Integer(1), Integer(1), Integer(0), Integer(0)],
...                            [Integer(0), Integer(0), Integer(0), Integer(0), Integer(1),-Integer(1), Integer(0), Integer(1), Integer(0)],
...                            [Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0),-Integer(1), Integer(1)],
...                            [Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1),-Integer(1), Integer(1)]])
>>> result, certificate = M.is_totally_unimodular(certificate=True,
...                         row_keys=[f'r{i}' for i in range(Integer(9))],
...                         column_keys=[f'c{i}' for i in range(Integer(9))])
>>> node = DecompositionNode.one_sum(*certificate.child_nodes())
>>> result, decomposition = node.is_conetwork_matrix(decomposition=True)
>>> result
False
>>> unicode_art(decomposition)
╭───────────OneSumNode (9×9) with 2 children
│                 │
GraphicNode (5×4) UnknownNode (4×5)
>>> decomposition.child_nodes()[Integer(1)]._graphicness()
Traceback (most recent call last):
...
ValueError: It is not determined whether the decomposition node is graphic/network

is_network_matrix(decomposition=False, **kwds)[source]¶

Return whether the matrix self over \(\GF{3}\) or \(\QQ\) is a network matrix. If there is some entry not in \(\{-1, 0, 1\}\), return False.

This method is based on Seymour’s decomposition. The decomposition will stop once being nonnetwork is detected. For direct network matrix check,

See also

• sage.matrix.matrix_cmr_sparse.Matrix_cmr_chr_sparse.is_network_matrix()

• UnknownNode.is_network_matrix()

• complete_decomposition()

EXAMPLES:

Sage

sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
sage: from sage.matrix.seymour_decomposition import DecompositionNode
sage: A = matrix(ZZ, [[-1, 0, 0, 0, 1,-1, 0],
....:                 [ 1, 0, 0, 1,-1, 1, 0],
....:                 [ 0,-1, 0,-1, 1,-1, 0],
....:                 [ 0, 1, 0, 0, 0, 0, 1],
....:                 [ 0, 0, 1,-1, 1, 0, 1],
....:                 [ 0, 0,-1, 1,-1, 0, 0]])
sage: M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 7, sparse=True), A)
sage: M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 7, 6, sparse=True), A.transpose())
sage: M = Matrix_cmr_chr_sparse.one_sum(M1, M2)
sage: result, certificate = M.is_totally_unimodular(certificate=True,
....:                         row_keys=[f'r{i}' for i in range(13)],
....:                         column_keys=[f'c{i}' for i in range(13)])
sage: node = DecompositionNode.one_sum(*certificate.child_nodes())

sage: result, decomposition = node.is_network_matrix(decomposition=True)
sage: unicode_art(decomposition)
╭─────────OneSumNode (13×13) with 2 children
│                │
PlanarNode (6×7) PlanarNode (7×6)
sage: node._graphicness()
Traceback (most recent call last):
...
ValueError: It is not determined whether the decomposition node is graphic/network

sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 9, 9, sparse=True),
....:                           [[1, 1, 0, 0, 0, 0, 0, 0, 0],
....:                            [-1,-1, 1, 0, 0, 0, 0, 0, 0],
....:                            [1, 0, 0, 1, 0, 0, 0, 0, 0],
....:                            [0, 1,-1,-1, 0, 0, 0, 0, 0],
....:                            [0, 0, 1, 1, 0, 0, 0, 0, 0],
....:                            [0, 0, 0, 0, 1,-1, 1, 0, 0],
....:                            [0, 0, 0, 0, 1,-1, 0, 1, 0],
....:                            [0, 0, 0, 0, 0, 1, 0,-1, 1],
....:                            [0, 0, 0, 0, 0, 0, 1,-1, 1]])
sage: result, certificate = M.is_totally_unimodular(certificate=True,
....:                         row_keys=[f'r{i}' for i in range(9)],
....:                         column_keys=[f'c{i}' for i in range(9)])
sage: node = DecompositionNode.one_sum(*certificate.child_nodes())
sage: result, decomposition = node.is_network_matrix(decomposition=True)
sage: result
False
sage: unicode_art(decomposition)
╭───────────OneSumNode (9×9) with 2 children
│                 │
GraphicNode (5×4) UnknownNode (4×5)
sage: decomposition.child_nodes()[1]._graphicness()
False

Python

>>> from sage.all import *
>>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
>>> from sage.matrix.seymour_decomposition import DecompositionNode
>>> A = matrix(ZZ, [[-Integer(1), Integer(0), Integer(0), Integer(0), Integer(1),-Integer(1), Integer(0)],
...                 [ Integer(1), Integer(0), Integer(0), Integer(1),-Integer(1), Integer(1), Integer(0)],
...                 [ Integer(0),-Integer(1), Integer(0),-Integer(1), Integer(1),-Integer(1), Integer(0)],
...                 [ Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1)],
...                 [ Integer(0), Integer(0), Integer(1),-Integer(1), Integer(1), Integer(0), Integer(1)],
...                 [ Integer(0), Integer(0),-Integer(1), Integer(1),-Integer(1), Integer(0), Integer(0)]])
>>> M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(6), Integer(7), sparse=True), A)
>>> M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(7), Integer(6), sparse=True), A.transpose())
>>> M = Matrix_cmr_chr_sparse.one_sum(M1, M2)
>>> result, certificate = M.is_totally_unimodular(certificate=True,
...                         row_keys=[f'r{i}' for i in range(Integer(13))],
...                         column_keys=[f'c{i}' for i in range(Integer(13))])
>>> node = DecompositionNode.one_sum(*certificate.child_nodes())

>>> result, decomposition = node.is_network_matrix(decomposition=True)
>>> unicode_art(decomposition)
╭─────────OneSumNode (13×13) with 2 children
│                │
PlanarNode (6×7) PlanarNode (7×6)
>>> node._graphicness()
Traceback (most recent call last):
...
ValueError: It is not determined whether the decomposition node is graphic/network

>>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(9), Integer(9), sparse=True),
...                           [[Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...                            [-Integer(1),-Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...                            [Integer(1), Integer(0), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...                            [Integer(0), Integer(1),-Integer(1),-Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...                            [Integer(0), Integer(0), Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...                            [Integer(0), Integer(0), Integer(0), Integer(0), Integer(1),-Integer(1), Integer(1), Integer(0), Integer(0)],
...                            [Integer(0), Integer(0), Integer(0), Integer(0), Integer(1),-Integer(1), Integer(0), Integer(1), Integer(0)],
...                            [Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0),-Integer(1), Integer(1)],
...                            [Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1),-Integer(1), Integer(1)]])
>>> result, certificate = M.is_totally_unimodular(certificate=True,
...                         row_keys=[f'r{i}' for i in range(Integer(9))],
...                         column_keys=[f'c{i}' for i in range(Integer(9))])
>>> node = DecompositionNode.one_sum(*certificate.child_nodes())
>>> result, decomposition = node.is_network_matrix(decomposition=True)
>>> result
False
>>> unicode_art(decomposition)
╭───────────OneSumNode (9×9) with 2 children
│                 │
GraphicNode (5×4) UnknownNode (4×5)
>>> decomposition.child_nodes()[Integer(1)]._graphicness()
False

is_ternary()[source]¶

Return whether the decomposition is over \(\GF{3}\).

EXAMPLES:

Sage

sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 2, sparse=True),
....:                           [[1, 0], [-1, 1], [0, 1]]); M
[ 1  0]
[-1  1]
[ 0  1]
sage: result, certificate = M.is_totally_unimodular(certificate=True)
sage: result, certificate
(True, GraphicNode (3×2))
sage: certificate.is_ternary()
True

sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 2, sparse=True),
....:                           [[1, 0], [1, 1], [0, 1]]); M
[1  0]
[1  1]
[0  1]
sage: result, certificate = M._is_binary_linear_matroid_regular(certificate=True)
sage: result, certificate
(True, GraphicNode (3×2))
sage: certificate.is_ternary()
False

Python

>>> from sage.all import *
>>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
>>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(3), Integer(2), sparse=True),
...                           [[Integer(1), Integer(0)], [-Integer(1), Integer(1)], [Integer(0), Integer(1)]]); M
[ 1  0]
[-1  1]
[ 0  1]
>>> result, certificate = M.is_totally_unimodular(certificate=True)
>>> result, certificate
(True, GraphicNode (3×2))
>>> certificate.is_ternary()
True

>>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(3), Integer(2), sparse=True),
...                           [[Integer(1), Integer(0)], [Integer(1), Integer(1)], [Integer(0), Integer(1)]]); M
[1  0]
[1  1]
[0  1]
>>> result, certificate = M._is_binary_linear_matroid_regular(certificate=True)
>>> result, certificate
(True, GraphicNode (3×2))
>>> certificate.is_ternary()
False

is_totally_unimodular(decomposition=False, **kwds)[source]¶

Return whether self is a totally unimodular matrix.

A matrix is totally unimodular if every subdeterminant is \(0\), \(1\), or \(-1\).

See also

• sage.matrix.matrix_cmr_sparse.Matrix_cmr_chr_sparse.is_totally_unimodular()

• complete_decomposition()

EXAMPLES:

Sage

sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
sage: from sage.matrix.seymour_decomposition import DecompositionNode
sage: A = matrix(ZZ, [[-1, 0, 0, 0, 1,-1, 0],
....:                 [ 1, 0, 0, 1,-1, 1, 0],
....:                 [ 0,-1, 0,-1, 1,-1, 0],
....:                 [ 0, 1, 0, 0, 0, 0, 1],
....:                 [ 0, 0, 1,-1, 1, 0, 1],
....:                 [ 0, 0,-1, 1,-1, 0, 0]])
sage: M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 7, sparse=True), A)
sage: M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 7, 6, sparse=True), A.transpose())
sage: M = Matrix_cmr_chr_sparse.one_sum(M1, M2)
sage: result, certificate = M.is_totally_unimodular(certificate=True,
....:                         row_keys=[f'r{i}' for i in range(13)],
....:                         column_keys=[f'c{i}' for i in range(13)])
sage: node = DecompositionNode.one_sum(*certificate.child_nodes())

sage: result, decomposition = node.is_totally_unimodular(decomposition=True)
sage: unicode_art(decomposition)
╭─────────OneSumNode (13×13) with 2 children
│                │
PlanarNode (6×7) PlanarNode (7×6)
sage: node._regularity()
Traceback (most recent call last):
...
ValueError: It is not determined whether the decomposition node is regular/TU

sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 9, 9, sparse=True),
....:                           [[1, 1, 0, 0, 0, 0, 0, 0, 0],
....:                            [-1,-1, 1, 0, 0, 0, 0, 0, 0],
....:                            [1, 0, 0, 1, 0, 0, 0, 0, 0],
....:                            [0, 1,-1,-1, 0, 0, 0, 0, 0],
....:                            [0, 0, 1, 1, 0, 0, 0, 0, 0],
....:                            [0, 0, 0, 0, 1,-1, 1, 0, 0],
....:                            [0, 0, 0, 0, 1,-1, 0, 1, 0],
....:                            [0, 0, 0, 0, 0, 1, 0,-1, 1],
....:                            [0, 0, 0, 0, 0, 0, 1,-1, 1]])
sage: result, certificate = M.is_totally_unimodular(certificate=True,
....:                         row_keys=[f'r{i}' for i in range(9)],
....:                         column_keys=[f'c{i}' for i in range(9)])
sage: node = DecompositionNode.one_sum(*certificate.child_nodes())
sage: result, decomposition = node.is_totally_unimodular(decomposition=True)
sage: result
True
sage: unicode_art(decomposition)
╭───────────OneSumNode (9×9) with 2 children
│                 │
GraphicNode (5×4) CographicNode (4×5)

Python

>>> from sage.all import *
>>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
>>> from sage.matrix.seymour_decomposition import DecompositionNode
>>> A = matrix(ZZ, [[-Integer(1), Integer(0), Integer(0), Integer(0), Integer(1),-Integer(1), Integer(0)],
...                 [ Integer(1), Integer(0), Integer(0), Integer(1),-Integer(1), Integer(1), Integer(0)],
...                 [ Integer(0),-Integer(1), Integer(0),-Integer(1), Integer(1),-Integer(1), Integer(0)],
...                 [ Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1)],
...                 [ Integer(0), Integer(0), Integer(1),-Integer(1), Integer(1), Integer(0), Integer(1)],
...                 [ Integer(0), Integer(0),-Integer(1), Integer(1),-Integer(1), Integer(0), Integer(0)]])
>>> M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(6), Integer(7), sparse=True), A)
>>> M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(7), Integer(6), sparse=True), A.transpose())
>>> M = Matrix_cmr_chr_sparse.one_sum(M1, M2)
>>> result, certificate = M.is_totally_unimodular(certificate=True,
...                         row_keys=[f'r{i}' for i in range(Integer(13))],
...                         column_keys=[f'c{i}' for i in range(Integer(13))])
>>> node = DecompositionNode.one_sum(*certificate.child_nodes())

>>> result, decomposition = node.is_totally_unimodular(decomposition=True)
>>> unicode_art(decomposition)
╭─────────OneSumNode (13×13) with 2 children
│                │
PlanarNode (6×7) PlanarNode (7×6)
>>> node._regularity()
Traceback (most recent call last):
...
ValueError: It is not determined whether the decomposition node is regular/TU

>>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(9), Integer(9), sparse=True),
...                           [[Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...                            [-Integer(1),-Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...                            [Integer(1), Integer(0), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...                            [Integer(0), Integer(1),-Integer(1),-Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...                            [Integer(0), Integer(0), Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...                            [Integer(0), Integer(0), Integer(0), Integer(0), Integer(1),-Integer(1), Integer(1), Integer(0), Integer(0)],
...                            [Integer(0), Integer(0), Integer(0), Integer(0), Integer(1),-Integer(1), Integer(0), Integer(1), Integer(0)],
...                            [Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0),-Integer(1), Integer(1)],
...                            [Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1),-Integer(1), Integer(1)]])
>>> result, certificate = M.is_totally_unimodular(certificate=True,
...                         row_keys=[f'r{i}' for i in range(Integer(9))],
...                         column_keys=[f'c{i}' for i in range(Integer(9))])
>>> node = DecompositionNode.one_sum(*certificate.child_nodes())
>>> result, decomposition = node.is_totally_unimodular(decomposition=True)
>>> result
True
>>> unicode_art(decomposition)
╭───────────OneSumNode (9×9) with 2 children
│                 │
GraphicNode (5×4) CographicNode (4×5)

matrix()[source]¶

Return a Matrix.

EXAMPLES:

Sage

sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 2, sparse=True),
....:                           [[1, 0], [-1, 1], [0, 1]]); M
[ 1  0]
[-1  1]
[ 0  1]
sage: result, certificate = M.is_totally_unimodular(certificate=True)
sage: result, certificate
(True, GraphicNode (3×2))
sage: certificate.matrix()
[ 1  0]
[-1  1]
[ 0  1]

sage: from sage.matrix.seymour_decomposition import UnknownNode
sage: node = UnknownNode([[1, 1], [0, 1]]); node
UnknownNode (2×2)
sage: node.matrix()
[1 1]
[0 1]

Python

>>> from sage.all import *
>>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
>>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(3), Integer(2), sparse=True),
...                           [[Integer(1), Integer(0)], [-Integer(1), Integer(1)], [Integer(0), Integer(1)]]); M
[ 1  0]
[-1  1]
[ 0  1]
>>> result, certificate = M.is_totally_unimodular(certificate=True)
>>> result, certificate
(True, GraphicNode (3×2))
>>> certificate.matrix()
[ 1  0]
[-1  1]
[ 0  1]

>>> from sage.matrix.seymour_decomposition import UnknownNode
>>> node = UnknownNode([[Integer(1), Integer(1)], [Integer(0), Integer(1)]]); node
UnknownNode (2×2)
>>> node.matrix()
[1 1]
[0 1]

minors()[source]¶

Return a tuple of minors of self.

Currently, it only handles determinant 2 submatrix.

EXAMPLES:

Sage

sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 9, 9, sparse=True),
....:                           [[1, 1, 0, 0, 0, 0, 0, 0, 0],
....:                            [1, 1, 1, 0, 0, 0, 0, 0, 0],
....:                            [1, 0, 0, 1, 0, 0, 0, 0, 0],
....:                            [0, 1, 1, 1, 0, 0, 0, 0, 0],
....:                            [0, 0, 1, 1, 0, 0, 0, 0, 0],
....:                            [0, 0, 0, 0, 1, 1, 1, 0, 0],
....:                            [0, 0, 0, 0, 1, 1, 0, 1, 0],
....:                            [0, 0, 0, 0, 0, 1, 0, 1, 1],
....:                            [0, 0, 0, 0, 0, 0, 1, 1, 1]])
sage: from sage.matrix.seymour_decomposition import UnknownNode
sage: C0 = UnknownNode(M).complete_decomposition()
sage: C1, C2 = C0.child_nodes()
sage: C1.minors()
(('|det| = 2 submatrix', ((4, 3, 1), (2, 3, 0))),)
sage: C2.minors()
(('|det| = 2 submatrix', ((2, 1, 0), (4, 2, 1))),)

Python

>>> from sage.all import *
>>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
>>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(9), Integer(9), sparse=True),
...                           [[Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...                            [Integer(1), Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...                            [Integer(1), Integer(0), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...                            [Integer(0), Integer(1), Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...                            [Integer(0), Integer(0), Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...                            [Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(1), Integer(1), Integer(0), Integer(0)],
...                            [Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(1), Integer(0), Integer(1), Integer(0)],
...                            [Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0), Integer(1), Integer(1)],
...                            [Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(1), Integer(1)]])
>>> from sage.matrix.seymour_decomposition import UnknownNode
>>> C0 = UnknownNode(M).complete_decomposition()
>>> C1, C2 = C0.child_nodes()
>>> C1.minors()
(('|det| = 2 submatrix', ((4, 3, 1), (2, 3, 0))),)
>>> C2.minors()
(('|det| = 2 submatrix', ((2, 1, 0), (4, 2, 1))),)

morphism()[source]¶

Create the matrix in the distinguished bases of the domain and codomain to build the module morphism.

See also: sage.modules.with_basis.morphism.ModuleMorphismFromMatrix.

EXAMPLES:

Sage

sage: from sage.matrix.seymour_decomposition import UnknownNode
sage: node = UnknownNode(matrix(ZZ, [[1, 0, 1], [0, 1, 1]]),
....:                    row_keys='ab',
....:                    column_keys=range(3)); node
UnknownNode (2×3)
sage: node.matrix()
[1 0 1]
[0 1 1]
sage: node.morphism()._unicode_art_matrix()
  0 1 2
a⎛1 0 1⎞
b⎝0 1 1⎠

Python

>>> from sage.all import *
>>> from sage.matrix.seymour_decomposition import UnknownNode
>>> node = UnknownNode(matrix(ZZ, [[Integer(1), Integer(0), Integer(1)], [Integer(0), Integer(1), Integer(1)]]),
...                    row_keys='ab',
...                    column_keys=range(Integer(3))); node
UnknownNode (2×3)
>>> node.matrix()
[1 0 1]
[0 1 1]
>>> node.morphism()._unicode_art_matrix()
  0 1 2
a⎛1 0 1⎞
b⎝0 1 1⎠

nchildren()[source]¶

Return the number of children of the node.

EXAMPLES:

Sage

sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 2, sparse=True),
....:                           [[1, 0], [-1, 1], [0, 1]]); M
[ 1  0]
[-1  1]
[ 0  1]
sage: result, certificate = M.is_totally_unimodular(certificate=True)
sage: result, certificate
(True, GraphicNode (3×2))
sage: certificate.nchildren()
0

Python

>>> from sage.all import *
>>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
>>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(3), Integer(2), sparse=True),
...                           [[Integer(1), Integer(0)], [-Integer(1), Integer(1)], [Integer(0), Integer(1)]]); M
[ 1  0]
[-1  1]
[ 0  1]
>>> result, certificate = M.is_totally_unimodular(certificate=True)
>>> result, certificate
(True, GraphicNode (3×2))
>>> certificate.nchildren()
0

ncols()[source]¶

Return the number of columns of the internal matrix representing this node.

EXAMPLES:

Sage

sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 2, sparse=True),
....:                           [[1, 0], [-1, 1], [0, 1]]); M
[ 1  0]
[-1  1]
[ 0  1]
sage: result, certificate = M.is_totally_unimodular(certificate=True)
sage: result, certificate
(True, GraphicNode (3×2))
sage: certificate.nrows()
3
sage: certificate.ncols()
2

sage: from sage.matrix.seymour_decomposition import UnknownNode
sage: node = UnknownNode([[1, 1], [0, 1]]); node
UnknownNode (2×2)
sage: node.nrows()
2
sage: node.ncols()
2

Python

>>> from sage.all import *
>>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
>>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(3), Integer(2), sparse=True),
...                           [[Integer(1), Integer(0)], [-Integer(1), Integer(1)], [Integer(0), Integer(1)]]); M
[ 1  0]
[-1  1]
[ 0  1]
>>> result, certificate = M.is_totally_unimodular(certificate=True)
>>> result, certificate
(True, GraphicNode (3×2))
>>> certificate.nrows()
3
>>> certificate.ncols()
2

>>> from sage.matrix.seymour_decomposition import UnknownNode
>>> node = UnknownNode([[Integer(1), Integer(1)], [Integer(0), Integer(1)]]); node
UnknownNode (2×2)
>>> node.nrows()
2
>>> node.ncols()
2

nminors()[source]¶

Return the number of minors of the node.

nrows()[source]¶

Return the number of rows of the internal matrix representing this node.

EXAMPLES:

Sage

sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 2, sparse=True),
....:                           [[1, 0], [-1, 1], [0, 1]]); M
[ 1  0]
[-1  1]
[ 0  1]
sage: result, certificate = M.is_totally_unimodular(certificate=True)
sage: result, certificate
(True, GraphicNode (3×2))
sage: certificate.nrows()
3
sage: certificate.ncols()
2

sage: from sage.matrix.seymour_decomposition import UnknownNode
sage: node = UnknownNode([[1, 1], [0, 1]]); node
UnknownNode (2×2)
sage: node.nrows()
2
sage: node.ncols()
2

Python

>>> from sage.all import *
>>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
>>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(3), Integer(2), sparse=True),
...                           [[Integer(1), Integer(0)], [-Integer(1), Integer(1)], [Integer(0), Integer(1)]]); M
[ 1  0]
[-1  1]
[ 0  1]
>>> result, certificate = M.is_totally_unimodular(certificate=True)
>>> result, certificate
(True, GraphicNode (3×2))
>>> certificate.nrows()
3
>>> certificate.ncols()
2

>>> from sage.matrix.seymour_decomposition import UnknownNode
>>> node = UnknownNode([[Integer(1), Integer(1)], [Integer(0), Integer(1)]]); node
UnknownNode (2×2)
>>> node.nrows()
2
>>> node.ncols()
2

one_sum(*summands, **kwds)[source]¶

Return a OneSumNode constructed from the given nodes (summands).

INPUT:

• summands – decomposition nodes DecompositionNode

• summand_ids – a tuple or list of ids for summands

• row_keys – a finite or enumerated family of arbitrary objects that index the rows of the result. Must be consistent with the row keys of the summands

• column_keys – a finite or enumerated family of arbitrary objects that index the columns of the result. Must be consistent with the column keys of the summands

Note that row_keys, column_keys of summands are disjoint

OUTPUT: A OneSumNode

The terminology “1-sum” is used in the context of Seymour’s decomposition of totally unimodular matrices and regular matroids, see [Sch1986].

See also

two_sum() delta_sum(), three_sum(), y_sum()

EXAMPLES:

Sage

sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
sage: from sage.matrix.seymour_decomposition import DecompositionNode
sage: M2 = Matrix_cmr_chr_sparse.one_sum([[1, 0], [-1, 1]],
....:                                    [[1, 1], [-1, 0]])
sage: result, certificate = M2.is_totally_unimodular(certificate=True,
....:                                                row_keys=range(4),
....:                                                column_keys='abcd')
sage: certificate
OneSumNode (4×4) with 2 children
sage: certificate.summand_matrices()
(
[ 1  0]  [ 1  1]
[-1  1], [-1  0]
)
sage: certificate.child_keys()
(((0, 1), ('a', 'b')), ((2, 3), ('c', 'd')))
sage: node = DecompositionNode.one_sum(*certificate.child_nodes())
sage: node.summand_matrices()
(
[ 1  0]  [ 1  1]
[-1  1], [-1  0]
)
sage: node.child_keys()
(((0, 1), ('a', 'b')), ((2, 3), ('c', 'd')))

sage: M3 = Matrix_cmr_chr_sparse.one_sum([[1, 0], [-1, 1]],
....:                                    [[1]], [[-1]])
sage: result, certificate = M3.is_totally_unimodular(certificate=True,
....:                                                row_keys=range(4),
....:                                                column_keys='abcd')
sage: certificate
OneSumNode (4×4) with 3 children
sage: certificate.summand_matrices()
(
[ 1  0]
[-1  1], [1], [-1]
)
sage: certificate.child_keys()
(((0, 1), ('a', 'b')), ((2,), ('c',)), ((3,), ('d',)))
sage: node = DecompositionNode.one_sum(*certificate.child_nodes())
sage: node.summand_matrices()
(
[ 1  0]
[-1  1], [1], [-1]
)
sage: node.child_keys()
(((0, 1), ('a', 'b')), ((2,), ('c',)), ((3,), ('d',)))

sage: from sage.matrix.seymour_decomposition import UnknownNode
sage: node = UnknownNode(matrix(ZZ, [[1, 0, 1], [0, 1, 1]]),
....:                    row_keys='ab',
....:                    column_keys=range(3)); node
UnknownNode (2×3)
sage: node = DecompositionNode.one_sum(certificate, node, summand_ids=range(2))
sage: node.summand_matrices()
(
[ 1  0| 0| 0]
[-1  1| 0| 0]
[-----+--+--]
[ 0  0| 1| 0]
[-----+--+--]  [1 0 1]
[ 0  0| 0|-1], [0 1 1]
)
sage: node.child_keys()
((((0, 0), (0, 1), (0, 2), (0, 3)), ((0, 'a'), (0, 'b'), (0, 'c'), (0, 'd'))),
 (((1, 'a'), (1, 'b')), ((1, 0), (1, 1), (1, 2))))

Python

>>> from sage.all import *
>>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
>>> from sage.matrix.seymour_decomposition import DecompositionNode
>>> M2 = Matrix_cmr_chr_sparse.one_sum([[Integer(1), Integer(0)], [-Integer(1), Integer(1)]],
...                                    [[Integer(1), Integer(1)], [-Integer(1), Integer(0)]])
>>> result, certificate = M2.is_totally_unimodular(certificate=True,
...                                                row_keys=range(Integer(4)),
...                                                column_keys='abcd')
>>> certificate
OneSumNode (4×4) with 2 children
>>> certificate.summand_matrices()
(
[ 1  0]  [ 1  1]
[-1  1], [-1  0]
)
>>> certificate.child_keys()
(((0, 1), ('a', 'b')), ((2, 3), ('c', 'd')))
>>> node = DecompositionNode.one_sum(*certificate.child_nodes())
>>> node.summand_matrices()
(
[ 1  0]  [ 1  1]
[-1  1], [-1  0]
)
>>> node.child_keys()
(((0, 1), ('a', 'b')), ((2, 3), ('c', 'd')))

>>> M3 = Matrix_cmr_chr_sparse.one_sum([[Integer(1), Integer(0)], [-Integer(1), Integer(1)]],
...                                    [[Integer(1)]], [[-Integer(1)]])
>>> result, certificate = M3.is_totally_unimodular(certificate=True,
...                                                row_keys=range(Integer(4)),
...                                                column_keys='abcd')
>>> certificate
OneSumNode (4×4) with 3 children
>>> certificate.summand_matrices()
(
[ 1  0]
[-1  1], [1], [-1]
)
>>> certificate.child_keys()
(((0, 1), ('a', 'b')), ((2,), ('c',)), ((3,), ('d',)))
>>> node = DecompositionNode.one_sum(*certificate.child_nodes())
>>> node.summand_matrices()
(
[ 1  0]
[-1  1], [1], [-1]
)
>>> node.child_keys()
(((0, 1), ('a', 'b')), ((2,), ('c',)), ((3,), ('d',)))

>>> from sage.matrix.seymour_decomposition import UnknownNode
>>> node = UnknownNode(matrix(ZZ, [[Integer(1), Integer(0), Integer(1)], [Integer(0), Integer(1), Integer(1)]]),
...                    row_keys='ab',
...                    column_keys=range(Integer(3))); node
UnknownNode (2×3)
>>> node = DecompositionNode.one_sum(certificate, node, summand_ids=range(Integer(2)))
>>> node.summand_matrices()
(
[ 1  0| 0| 0]
[-1  1| 0| 0]
[-----+--+--]
[ 0  0| 1| 0]
[-----+--+--]  [1 0 1]
[ 0  0| 0|-1], [0 1 1]
)
>>> node.child_keys()
((((0, 0), (0, 1), (0, 2), (0, 3)), ((0, 'a'), (0, 'b'), (0, 'c'), (0, 'd'))),
 (((1, 'a'), (1, 'b')), ((1, 0), (1, 1), (1, 2))))

row_keys, column_keys of summands are disjoint:

Sage

sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
sage: from sage.matrix.seymour_decomposition import DecompositionNode
sage: M2 = Matrix_cmr_chr_sparse.one_sum([[1, 0], [-1, 1]],
....:                                    [[1, 1], [-1, 0]])
sage: result, certificate = M2.is_totally_unimodular(certificate=True,
....:                                                row_keys='aefg',
....:                                                column_keys='abcd')
sage: node = DecompositionNode.one_sum(*certificate.child_nodes())
Traceback (most recent call last):
...
ValueError: keys must be disjoint, got
summand_row_keys=('a', 'e'), summand_column_keys=('a', 'b')

sage: result, certificate = M2.is_totally_unimodular(certificate=True,
....:                                                row_keys=range(4),
....:                                                column_keys='abcd')
sage: node = DecompositionNode.one_sum(*certificate.child_nodes(),
....:                                  row_keys=range(4),
....:                                  column_keys='abce')
Traceback (most recent call last):
...
ValueError: inconsistent column_keys, got column_keys=('a', 'b', 'c', 'e'),
should be a permutation of ['a', 'b', 'c', 'd']

Python

>>> from sage.all import *
>>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
>>> from sage.matrix.seymour_decomposition import DecompositionNode
>>> M2 = Matrix_cmr_chr_sparse.one_sum([[Integer(1), Integer(0)], [-Integer(1), Integer(1)]],
...                                    [[Integer(1), Integer(1)], [-Integer(1), Integer(0)]])
>>> result, certificate = M2.is_totally_unimodular(certificate=True,
...                                                row_keys='aefg',
...                                                column_keys='abcd')
>>> node = DecompositionNode.one_sum(*certificate.child_nodes())
Traceback (most recent call last):
...
ValueError: keys must be disjoint, got
summand_row_keys=('a', 'e'), summand_column_keys=('a', 'b')

>>> result, certificate = M2.is_totally_unimodular(certificate=True,
...                                                row_keys=range(Integer(4)),
...                                                column_keys='abcd')
>>> node = DecompositionNode.one_sum(*certificate.child_nodes(),
...                                  row_keys=range(Integer(4)),
...                                  column_keys='abce')
Traceback (most recent call last):
...
ValueError: inconsistent column_keys, got column_keys=('a', 'b', 'c', 'e'),
should be a permutation of ['a', 'b', 'c', 'd']

plot(**kwds)[source]¶

Plot the decomposition tree rooted at self.

EXAMPLES:

Sage

sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
sage: M = matrix([[1, 0], [-1, 1], [0, 1]], sparse=True)
sage: M2MT = block_diagonal_matrix([M, M, M.T], sparse=True)
sage: M2MTcmr = Matrix_cmr_chr_sparse(M2MT.parent(), M2MT)
sage: result, certificate = M2MTcmr.is_totally_unimodular(certificate=True)
sage: T = certificate.as_ordered_tree()
sage: T.plot()                                                              # needs sage.plot
Graphics object consisting of 8 graphics primitives

Python

>>> from sage.all import *
>>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
>>> M = matrix([[Integer(1), Integer(0)], [-Integer(1), Integer(1)], [Integer(0), Integer(1)]], sparse=True)
>>> M2MT = block_diagonal_matrix([M, M, M.T], sparse=True)
>>> M2MTcmr = Matrix_cmr_chr_sparse(M2MT.parent(), M2MT)
>>> result, certificate = M2MTcmr.is_totally_unimodular(certificate=True)
>>> T = certificate.as_ordered_tree()
>>> T.plot()                                                              # needs sage.plot
Graphics object consisting of 8 graphics primitives

row_keys()[source]¶

Return the row keys of this node.

OUTPUT: a tuple or None

EXAMPLES:

Sage

sage: from sage.matrix.seymour_decomposition import UnknownNode
sage: node = UnknownNode(matrix(ZZ, [[1, 0, 1], [0, 1, 1]]),
....:                    row_keys='ab',
....:                    column_keys=range(3)); node
UnknownNode (2×3)
sage: node.row_keys()
('a', 'b')

Python

>>> from sage.all import *
>>> from sage.matrix.seymour_decomposition import UnknownNode
>>> node = UnknownNode(matrix(ZZ, [[Integer(1), Integer(0), Integer(1)], [Integer(0), Integer(1), Integer(1)]]),
...                    row_keys='ab',
...                    column_keys=range(Integer(3))); node
UnknownNode (2×3)
>>> node.row_keys()
('a', 'b')

set_default_keys()[source]¶

Set default row and column keys.

See also

ElementKey

EXAMPLES:

Sage

sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 2, sparse=True),
....:                           [[1, 0], [-1, 1], [0, 1]]); M
[ 1  0]
[-1  1]
[ 0  1]
sage: result, certificate = M.is_totally_unimodular(certificate=True)
sage: result, certificate
(True, GraphicNode (3×2))
sage: certificate.row_keys() is None
True
sage: certificate.set_default_keys()
sage: certificate.row_keys()
(r0, r1, r2)

Python

>>> from sage.all import *
>>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
>>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(3), Integer(2), sparse=True),
...                           [[Integer(1), Integer(0)], [-Integer(1), Integer(1)], [Integer(0), Integer(1)]]); M
[ 1  0]
[-1  1]
[ 0  1]
>>> result, certificate = M.is_totally_unimodular(certificate=True)
>>> result, certificate
(True, GraphicNode (3×2))
>>> certificate.row_keys() is None
True
>>> certificate.set_default_keys()
>>> certificate.row_keys()
(r0, r1, r2)