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:
DecompositionNodeBase class for
GraphicNode,CographicNode, andPlanarNodeIf
base_ringis \(\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._graphis the graph \(G = (V,E)\).self._forest_edgesis the edges of \(T\).self._coforest_edgesis the edges of \(E \setminus T\).
If
base_ringis \(\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._graphis the digraph \(D = (V,A)\).self._forest_edgesis the arcs of \(T\).self._coforest_edgesis 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. Ifself.base_ring()is \(\GF{3}\) or \(\ZZ\), then arcs.EXAMPLES:
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
>>> 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
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse 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]]) M.is_network_matrix() result, certificate = M.is_network_matrix(certificate=True) result, certificate digraph, forest_arcs, coforest_arcs = certificate result, certificate = M.is_totally_unimodular(certificate=True) certificate.graph() == digraph certificate.forest_edges() == forest_arcs certificate.coforest_edges() == coforest_arcs
- forest_edges()[source]¶
Return the forest edges of
self.If
self.base_ring()is \(\GF{2}\), then return edges. Ifself.base_ring()is \(\GF{3}\) or \(\ZZ\), then arcs.EXAMPLES:
Undirected graph:
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))
>>> 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))
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 2, sparse=True), [[1, 0], [1, 1], [0,1]]); M result, certificate = M._is_binary_linear_matroid_regular(certificate=True) result, certificate certificate.forest_edges() certificate.coforest_edges()Directed graph:
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))
>>> 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))
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 2, sparse=True), [[1, 0], [-1, 1], [0,-1]]); M result, certificate = M.is_totally_unimodular(certificate=True) result, certificate certificate.forest_edges() certificate.coforest_edges()Starting with a morphism:
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)
>>> 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)
from sage.matrix.seymour_decomposition import UnknownNode phi = matrix(ZZ, [[1, 0], [1, 1], [0, 1]], row_keys=['a', 'b', 'c'], column_keys=['v', 'w']) phi; phi._unicode_art_matrix() phi_node = UnknownNode(phi) is_graphic, rephined_node = phi_node._is_binary_linear_matroid_graphic(decomposition=True) is_graphic, rephined_node rephined_node.forest_edges() phi_node # still in the dark about graphicness
- graph()[source]¶
Return the graph representing
self.If
self.base_ring()is \(\GF{2}\), then return an undirected graph. Ifself.base_ring()is \(\GF{3}\) or \(\ZZ\), then return directed graph.EXAMPLES:
Undirected graph:
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)]
>>> 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)]
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 2, sparse=True), [[1, 0], [1, 1], [0,1]]); M result, certificate = M._is_binary_linear_matroid_regular(certificate=True) result, certificate G = certificate.graph(); G G.vertices(sort=True) G.edges(sort=True)Directed graph:
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)]
>>> 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)]
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 2, sparse=True), [[1, 0], [-1, 1], [0,-1]]); M result, certificate = M.is_totally_unimodular(certificate=True) result, certificate G = certificate.graph(); G G.vertices(sort=True) G.edges(sort=True)
- class sage.matrix.seymour_decomposition.CographicNode[source]¶
Bases:
BaseGraphicNode- forest_edges()[source]¶
Return the forest edges of the cograph of
self.EXAMPLES:
Undirected graph:
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))
>>> 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))
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse 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 result, certificate = M._is_binary_linear_matroid_regular(certificate=True) result, certificate certificate.forest_edges() certificate.coforest_edges()Directed graph:
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))
>>> 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))
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse 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 result, certificate = M.is_totally_unimodular(certificate=True) result, certificate certificate.forest_edges() certificate.coforest_edges()
- graph()[source]¶
Actually the cograph of matrix, in the case where it is not graphic.
EXAMPLES:
Undirected graph:
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)]
>>> 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)]
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse 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 result, certificate = M._is_binary_linear_matroid_regular(certificate=True) certificate certificate.base_ring() G = certificate.graph(); G G.vertices(sort=True) G.edges(sort=True)Directed graph:
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)]
>>> 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)]
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse 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 result, certificate = M.is_totally_unimodular(certificate=True) certificate G = certificate.graph(); G G.vertices(sort=True) G.edges(sort=True)
- class sage.matrix.seymour_decomposition.DecompositionNode[source]¶
Bases:
SageObjectBase class for nodes in Seymour’s decomposition
- as_ordered_tree()[source]¶
Return the decomposition tree rooted at
self.EXAMPLES:
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)
>>> 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)
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse M = matrix([[1, 0], [-1, 1], [0, 1]], sparse=True) M2 = block_diagonal_matrix([M, M], sparse=True) M2cmr = Matrix_cmr_chr_sparse(M2.parent(), M2); M2cmr result, certificate = M2cmr.is_totally_unimodular(certificate=True) T = certificate.as_ordered_tree(); T unicode_art(T)
- 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: 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() ()
>>> 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() ()
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 2, sparse=True), [[1, 0], [-1, 1], [0, 1]]); M result, certificate = M.is_totally_unimodular(certificate=True) certificate.child_keys() from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse M = matrix([[1, 0], [-1, 1], [0, 1]], sparse=True) M2 = block_diagonal_matrix([M, M], sparse=True) M2cmr = Matrix_cmr_chr_sparse(M2.parent(), M2); M2cmr result, certificate = M2cmr.is_totally_unimodular(certificate=True) result, certificate C = certificate.summands(); C certificate.child_keys()[0] certificate.child_keys()[1] from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse 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]]) 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()[0]; C C1, C2 = C.child_nodes() C1.matrix() C2.matrix() certificate.child_keys() C.matrix() C.child_keys() M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 2, 2, sparse=True), [[1, 1], [-1, 0]]); M2 result, certificate = M2.is_totally_unimodular(certificate=True); certificate 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 assummands().For graphic or leaf nodes, it returns the empty tuple.
EXAMPLES:
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() ()
>>> 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() ()
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse M = Matrix_cmr_chr_sparse.one_sum([[1, 0], [-1, 1]], [[1, 1], [-1, 0]], [[1, 0], [0,1]]); M result, certificate = M.is_totally_unimodular(certificate=True); certificate certificate.child_nodes() M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 2, 2, sparse=True), [[1, 1], [-1, 0]]); M2 result, certificate = M2.is_totally_unimodular(certificate=True); certificate certificate.child_nodes()
- column_keys()[source]¶
Return the column keys of this node.
OUTPUT: a tuple or
NoneEXAMPLES:
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)
>>> 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)
from sage.matrix.seymour_decomposition import UnknownNode node = UnknownNode(matrix(ZZ, [[1, 0, 1], [0, 1, 1]]), row_keys='ab', column_keys=range(3)); node node.column_keys()
- 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
selfover \(\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: 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]
>>> 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]
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse 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]]) from sage.matrix.seymour_decomposition import UnknownNode node = UnknownNode(M); node C0 = node.complete_decomposition() unicode_art(C0) C1, C2 = C0.child_nodes() C11 = C1.complete_decomposition(); C11 unicode_art(C11) C1.matrix() C11.matrix() C22 = C2.complete_decomposition(); C22 unicode_art(C22) C2.matrix() C22.matrix()
- dimensions()[source]¶
Return the number of rows and columns of this node.
EXAMPLES:
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)
>>> 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)
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 2, sparse=True), [[1, 0], [-1, 1], [0, 1]]); M result, certificate = M.is_totally_unimodular(certificate=True) result, certificate certificate.dimensions() from sage.matrix.seymour_decomposition import UnknownNode node = UnknownNode([[1, 1], [0, 1]]); node node.dimensions()
- is_conetwork_matrix(decomposition=False, **kwds)[source]¶
Return whether the matrix
selfover \(\GF{3}\) or \(\QQ\) is a conetwork matrix. If there is some entry not in \(\{-1, 0, 1\}\), returnFalse.This method is based on Seymour’s decomposition. The decomposition will stop once being nonconetwork is detected. For direct conetwork matrix check,
See also
EXAMPLES:
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
>>> 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
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse from sage.matrix.seymour_decomposition import DecompositionNode 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]]) M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 7, sparse=True), A) M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 7, 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(13)], column_keys=[f'c{i}' for i in range(13)]) node = DecompositionNode.one_sum(*certificate.child_nodes()) result, decomposition = node.is_conetwork_matrix(decomposition=True) unicode_art(decomposition) node._cographicness() 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]]) 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)]) node = DecompositionNode.one_sum(*certificate.child_nodes()) result, decomposition = node.is_conetwork_matrix(decomposition=True) result unicode_art(decomposition) decomposition.child_nodes()[1]._graphicness()
- is_network_matrix(decomposition=False, **kwds)[source]¶
Return whether the matrix
selfover \(\GF{3}\) or \(\QQ\) is a network matrix. If there is some entry not in \(\{-1, 0, 1\}\), returnFalse.This method is based on Seymour’s decomposition. The decomposition will stop once being nonnetwork is detected. For direct network matrix check,
See also
EXAMPLES:
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
>>> 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
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse from sage.matrix.seymour_decomposition import DecompositionNode 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]]) M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 7, sparse=True), A) M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 7, 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(13)], column_keys=[f'c{i}' for i in range(13)]) node = DecompositionNode.one_sum(*certificate.child_nodes()) result, decomposition = node.is_network_matrix(decomposition=True) unicode_art(decomposition) node._graphicness() 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]]) 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)]) node = DecompositionNode.one_sum(*certificate.child_nodes()) result, decomposition = node.is_network_matrix(decomposition=True) result unicode_art(decomposition) decomposition.child_nodes()[1]._graphicness()
- is_ternary()[source]¶
Return whether the decomposition is over \(\GF{3}\).
EXAMPLES:
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
>>> 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
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 2, sparse=True), [[1, 0], [-1, 1], [0, 1]]); M result, certificate = M.is_totally_unimodular(certificate=True) result, certificate certificate.is_ternary() M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 2, sparse=True), [[1, 0], [1, 1], [0, 1]]); M result, certificate = M._is_binary_linear_matroid_regular(certificate=True) result, certificate certificate.is_ternary()
- is_totally_unimodular(decomposition=False, **kwds)[source]¶
Return whether
selfis a totally unimodular matrix.A matrix is totally unimodular if every subdeterminant is \(0\), \(1\), or \(-1\).
See also
EXAMPLES:
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)
>>> 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)
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse from sage.matrix.seymour_decomposition import DecompositionNode 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]]) M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 7, sparse=True), A) M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 7, 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(13)], column_keys=[f'c{i}' for i in range(13)]) node = DecompositionNode.one_sum(*certificate.child_nodes()) result, decomposition = node.is_totally_unimodular(decomposition=True) unicode_art(decomposition) node._regularity() 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]]) 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)]) node = DecompositionNode.one_sum(*certificate.child_nodes()) result, decomposition = node.is_totally_unimodular(decomposition=True) result unicode_art(decomposition)
- matrix()[source]¶
Return a
Matrix.EXAMPLES:
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]
>>> 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]
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 2, sparse=True), [[1, 0], [-1, 1], [0, 1]]); M result, certificate = M.is_totally_unimodular(certificate=True) result, certificate certificate.matrix() from sage.matrix.seymour_decomposition import UnknownNode node = UnknownNode([[1, 1], [0, 1]]); node node.matrix()
- minors()[source]¶
Return a tuple of minors of
self.Currently, it only handles determinant 2 submatrix.
EXAMPLES:
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))),)
>>> 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))),)
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse 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]]) from sage.matrix.seymour_decomposition import UnknownNode C0 = UnknownNode(M).complete_decomposition() C1, C2 = C0.child_nodes() C1.minors() C2.minors()
- 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: 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⎠
>>> 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⎠
from sage.matrix.seymour_decomposition import UnknownNode node = UnknownNode(matrix(ZZ, [[1, 0, 1], [0, 1, 1]]), row_keys='ab', column_keys=range(3)); node node.matrix() node.morphism()._unicode_art_matrix()
- nchildren()[source]¶
Return the number of children of the node.
EXAMPLES:
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
>>> 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
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 2, sparse=True), [[1, 0], [-1, 1], [0, 1]]); M result, certificate = M.is_totally_unimodular(certificate=True) result, certificate certificate.nchildren()
- ncols()[source]¶
Return the number of columns of the internal matrix representing this node.
EXAMPLES:
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
>>> 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
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 2, sparse=True), [[1, 0], [-1, 1], [0, 1]]); M result, certificate = M.is_totally_unimodular(certificate=True) result, certificate certificate.nrows() certificate.ncols() from sage.matrix.seymour_decomposition import UnknownNode node = UnknownNode([[1, 1], [0, 1]]); node node.nrows() node.ncols()
- nrows()[source]¶
Return the number of rows of the internal matrix representing this node.
EXAMPLES:
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
>>> 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
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 2, sparse=True), [[1, 0], [-1, 1], [0, 1]]); M result, certificate = M.is_totally_unimodular(certificate=True) result, certificate certificate.nrows() certificate.ncols() from sage.matrix.seymour_decomposition import UnknownNode node = UnknownNode([[1, 1], [0, 1]]); node node.nrows() node.ncols()
- one_sum(*summands, **kwds)[source]¶
Return a
OneSumNodeconstructed from the given nodes (summands).INPUT:
summands– decomposition nodesDecompositionNodesummand_ids– a tuple or list of ids for summandsrow_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 summandscolumn_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_keysofsummandsare disjointOUTPUT: A
OneSumNodeThe 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: 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))))
>>> 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))))
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([[1, 0], [-1, 1]], [[1, 1], [-1, 0]]) result, certificate = M2.is_totally_unimodular(certificate=True, row_keys=range(4), column_keys='abcd') certificate certificate.summand_matrices() certificate.child_keys() node = DecompositionNode.one_sum(*certificate.child_nodes()) node.summand_matrices() node.child_keys() M3 = Matrix_cmr_chr_sparse.one_sum([[1, 0], [-1, 1]], [[1]], [[-1]]) result, certificate = M3.is_totally_unimodular(certificate=True, row_keys=range(4), column_keys='abcd') certificate certificate.summand_matrices() certificate.child_keys() node = DecompositionNode.one_sum(*certificate.child_nodes()) node.summand_matrices() node.child_keys() from sage.matrix.seymour_decomposition import UnknownNode node = UnknownNode(matrix(ZZ, [[1, 0, 1], [0, 1, 1]]), row_keys='ab', column_keys=range(3)); node node = DecompositionNode.one_sum(certificate, node, summand_ids=range(2)) node.summand_matrices() node.child_keys()row_keys,column_keysofsummandsare disjoint: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']
>>> 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']
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([[1, 0], [-1, 1]], [[1, 1], [-1, 0]]) result, certificate = M2.is_totally_unimodular(certificate=True, row_keys='aefg', column_keys='abcd') node = DecompositionNode.one_sum(*certificate.child_nodes()) result, certificate = M2.is_totally_unimodular(certificate=True, row_keys=range(4), column_keys='abcd') node = DecompositionNode.one_sum(*certificate.child_nodes(), row_keys=range(4), column_keys='abce')
- plot(**kwds)[source]¶
Plot the decomposition tree rooted at
self.EXAMPLES:
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
>>> 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
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse M = matrix([[1, 0], [-1, 1], [0, 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
- row_keys()[source]¶
Return the row keys of this node.
OUTPUT: a tuple or
NoneEXAMPLES:
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')
>>> 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')
from sage.matrix.seymour_decomposition import UnknownNode node = UnknownNode(matrix(ZZ, [[1, 0, 1], [0, 1, 1]]), row_keys='ab', column_keys=range(3)); node node.row_keys()
- set_default_keys()[source]¶
Set default row and column keys.
See also
EXAMPLES:
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)
>>> 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)
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 2, sparse=True), [[1, 0], [-1, 1], [0, 1]]); M result, certificate = M.is_totally_unimodular(certificate=True) result, certificate certificate.row_keys() is None certificate.set_default_keys() certificate.row_keys()
- class sage.matrix.seymour_decomposition.DeltaSumNode[source]¶
Bases:
SumNode- block_matrix_form()[source]¶
Return the block matrix constructed from the \(\Delta\)-sum of children.
EXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: R12 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 6, sparse=True), ....: [[1,0,1,1,0,0],[0,1,1,1,0,0],[1,0,1,0,1,1], ....: [0,-1,0,-1,1,1],[1,0,1,0,1,0],[0,-1,0,-1,0,1]]) sage: R12 [ 1 0 1 1 0 0] [ 0 1 1 1 0 0] [ 1 0 1 0 1 1] [ 0 -1 0 -1 1 1] [ 1 0 1 0 1 0] [ 0 -1 0 -1 0 1] sage: result, certificate = R12.is_totally_unimodular(certificate=True, ....: decompose_strategy="delta_pivot") sage: C = certificate.child_nodes()[0]; C DeltaSumNode (6×6) sage: C.matrix() [ 1 0 0 1 -1 -1] [ 0 1 1 1 0 0] [-1 0 1 0 1 1] [ 0 -1 0 -1 1 1] [ 1 0 0 0 0 -1] [ 0 -1 0 -1 0 1] sage: C.summand_matrices() ( [ 0 0 1 1 1] [-1 0 1 -1 -1] [ 1 1 1 0 0] [ 1 1 0 1 1] [ 0 1 0 -1 -1] [ 0 0 1 0 -1] [-1 0 -1 0 -1], [ 1 1 0 0 1] ) sage: C.row_keys() (r0, r1, c0, r3, r4, r5) sage: C.column_keys() (r2, c1, c2, c3, c4, c5) sage: C.child_keys() (((r0, r1, c0, r3), (c1, c2, c3, r2, +r2-r3)), ((r0, r3, r4, r5), (+c1-r0, c1, r2, c4, c5))) sage: C.block_matrix_form() [ 0 0 1 1 -1 -1] [ 1 1 1 0 0 0] [ 0 1 0 -1 1 1] [-1 0 -1 0 1 1] [ 0 0 0 1 0 -1] [-1 0 -1 0 0 1]
>>> from sage.all import * >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> R12 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(6), Integer(6), sparse=True), ... [[Integer(1),Integer(0),Integer(1),Integer(1),Integer(0),Integer(0)],[Integer(0),Integer(1),Integer(1),Integer(1),Integer(0),Integer(0)],[Integer(1),Integer(0),Integer(1),Integer(0),Integer(1),Integer(1)], ... [Integer(0),-Integer(1),Integer(0),-Integer(1),Integer(1),Integer(1)],[Integer(1),Integer(0),Integer(1),Integer(0),Integer(1),Integer(0)],[Integer(0),-Integer(1),Integer(0),-Integer(1),Integer(0),Integer(1)]]) >>> R12 [ 1 0 1 1 0 0] [ 0 1 1 1 0 0] [ 1 0 1 0 1 1] [ 0 -1 0 -1 1 1] [ 1 0 1 0 1 0] [ 0 -1 0 -1 0 1] >>> result, certificate = R12.is_totally_unimodular(certificate=True, ... decompose_strategy="delta_pivot") >>> C = certificate.child_nodes()[Integer(0)]; C DeltaSumNode (6×6) >>> C.matrix() [ 1 0 0 1 -1 -1] [ 0 1 1 1 0 0] [-1 0 1 0 1 1] [ 0 -1 0 -1 1 1] [ 1 0 0 0 0 -1] [ 0 -1 0 -1 0 1] >>> C.summand_matrices() ( [ 0 0 1 1 1] [-1 0 1 -1 -1] [ 1 1 1 0 0] [ 1 1 0 1 1] [ 0 1 0 -1 -1] [ 0 0 1 0 -1] [-1 0 -1 0 -1], [ 1 1 0 0 1] ) >>> C.row_keys() (r0, r1, c0, r3, r4, r5) >>> C.column_keys() (r2, c1, c2, c3, c4, c5) >>> C.child_keys() (((r0, r1, c0, r3), (c1, c2, c3, r2, +r2-r3)), ((r0, r3, r4, r5), (+c1-r0, c1, r2, c4, c5))) >>> C.block_matrix_form() [ 0 0 1 1 -1 -1] [ 1 1 1 0 0 0] [ 0 1 0 -1 1 1] [-1 0 -1 0 1 1] [ 0 0 0 1 0 -1] [-1 0 -1 0 0 1]
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse R12 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 6, sparse=True), [[1,0,1,1,0,0],[0,1,1,1,0,0],[1,0,1,0,1,1], [0,-1,0,-1,1,1],[1,0,1,0,1,0],[0,-1,0,-1,0,1]]) R12 result, certificate = R12.is_totally_unimodular(certificate=True, decompose_strategy="delta_pivot") C = certificate.child_nodes()[0]; C C.matrix() C.summand_matrices() C.row_keys() C.column_keys() C.child_keys() C.block_matrix_form()
- is_concentrated_rank()[source]¶
Return
Falsefor the \(\Delta\)-sum nodeself.concentrated_rankis named after the rank 2 and rank 0 off-diagonal blocks.
- is_distributed_ranks()[source]¶
Return
Truefor the \(\Delta\)-sum nodeself.distributed_ranksis named after the two rank 1 off-diagonal blocks.EXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: R12_large = 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_large.is_totally_unimodular(certificate=True, ....: decompose_strategy="delta_pivot") sage: C = certificate.child_nodes()[0]; C DeltaSumNode (9×12) sage: C.is_distributed_ranks() True sage: C.is_concentrated_rank() False
>>> from sage.all import * >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> R12_large = 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_large.is_totally_unimodular(certificate=True, ... decompose_strategy="delta_pivot") >>> C = certificate.child_nodes()[Integer(0)]; C DeltaSumNode (9×12) >>> C.is_distributed_ranks() True >>> C.is_concentrated_rank() False
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse R12_large = 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]]) result, certificate = R12_large.is_totally_unimodular(certificate=True, decompose_strategy="delta_pivot") C = certificate.child_nodes()[0]; C C.is_distributed_ranks() C.is_concentrated_rank()
- permuted_block_matrix()[source]¶
Return the permutation matrices between the matrix and the block matrix form.
OUTPUT: a tuple
(Prow, BlockMatrix, Pcolumn), whereself.matrix() == Prow * BlockMatrix * Pcolumn, andBlockMatrix == self.block_matrix_form().EXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: R12 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 6, sparse=True), ....: [[1,0,1,1,0,0],[0,1,1,1,0,0],[1,0,1,0,1,1], ....: [0,-1,0,-1,1,1],[1,0,1,0,1,0],[0,-1,0,-1,0,1]]) sage: R12 [ 1 0 1 1 0 0] [ 0 1 1 1 0 0] [ 1 0 1 0 1 1] [ 0 -1 0 -1 1 1] [ 1 0 1 0 1 0] [ 0 -1 0 -1 0 1] sage: result, certificate = R12.is_totally_unimodular(certificate=True, ....: decompose_strategy="delta_pivot") sage: C = certificate.child_nodes()[0]; C DeltaSumNode (6×6) sage: C.matrix() [ 1 0 0 1 -1 -1] [ 0 1 1 1 0 0] [-1 0 1 0 1 1] [ 0 -1 0 -1 1 1] [ 1 0 0 0 0 -1] [ 0 -1 0 -1 0 1] sage: C.block_matrix_form() [ 0 0 1 1 -1 -1] [ 1 1 1 0 0 0] [ 0 1 0 -1 1 1] [-1 0 -1 0 1 1] [ 0 0 0 1 0 -1] [-1 0 -1 0 0 1] sage: P_row, block_matrix, P_column = C.permuted_block_matrix() sage: P_row^(-1) * C.matrix() * P_column^(-1) == block_matrix True
>>> from sage.all import * >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> R12 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(6), Integer(6), sparse=True), ... [[Integer(1),Integer(0),Integer(1),Integer(1),Integer(0),Integer(0)],[Integer(0),Integer(1),Integer(1),Integer(1),Integer(0),Integer(0)],[Integer(1),Integer(0),Integer(1),Integer(0),Integer(1),Integer(1)], ... [Integer(0),-Integer(1),Integer(0),-Integer(1),Integer(1),Integer(1)],[Integer(1),Integer(0),Integer(1),Integer(0),Integer(1),Integer(0)],[Integer(0),-Integer(1),Integer(0),-Integer(1),Integer(0),Integer(1)]]) >>> R12 [ 1 0 1 1 0 0] [ 0 1 1 1 0 0] [ 1 0 1 0 1 1] [ 0 -1 0 -1 1 1] [ 1 0 1 0 1 0] [ 0 -1 0 -1 0 1] >>> result, certificate = R12.is_totally_unimodular(certificate=True, ... decompose_strategy="delta_pivot") >>> C = certificate.child_nodes()[Integer(0)]; C DeltaSumNode (6×6) >>> C.matrix() [ 1 0 0 1 -1 -1] [ 0 1 1 1 0 0] [-1 0 1 0 1 1] [ 0 -1 0 -1 1 1] [ 1 0 0 0 0 -1] [ 0 -1 0 -1 0 1] >>> C.block_matrix_form() [ 0 0 1 1 -1 -1] [ 1 1 1 0 0 0] [ 0 1 0 -1 1 1] [-1 0 -1 0 1 1] [ 0 0 0 1 0 -1] [-1 0 -1 0 0 1] >>> P_row, block_matrix, P_column = C.permuted_block_matrix() >>> P_row**(-Integer(1)) * C.matrix() * P_column**(-Integer(1)) == block_matrix True
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse R12 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 6, sparse=True), [[1,0,1,1,0,0],[0,1,1,1,0,0],[1,0,1,0,1,1], [0,-1,0,-1,1,1],[1,0,1,0,1,0],[0,-1,0,-1,0,1]]) R12 result, certificate = R12.is_totally_unimodular(certificate=True, decompose_strategy="delta_pivot") C = certificate.child_nodes()[0]; C C.matrix() C.block_matrix_form() P_row, block_matrix, P_column = C.permuted_block_matrix() P_row^(-1) * C.matrix() * P_column^(-1) == block_matrix
- class sage.matrix.seymour_decomposition.ElementKey[source]¶
Bases:
objectCreate the element key for a row or column index of
DecompositionNode.INPUT:
keys– a row/column key or a tuple (\(\pm 1\), row/column key, \(\pm 1\), row/column key).composition–TrueorFalse(default). whether the key is a composition key or not. IfFalse,self._keyis a frozenset with a row/column key. IfTrue,self._keyis a frozenset with two tuples, where each tuple has a sign value and a row/column key. For example,frozenset((1,'a'), (-1,'7')).
- key¶
- class sage.matrix.seymour_decomposition.GraphicNode[source]¶
Bases:
BaseGraphicNode
- class sage.matrix.seymour_decomposition.OneSumNode[source]¶
Bases:
SumNode- block_matrix_form()[source]¶
Return the block matrix representing the one sum node.
EXAMPLES:
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]]) sage: result, certificate = M.is_totally_unimodular(certificate=True); certificate OneSumNode (4×4) with 2 children sage: certificate.summand_matrices() ( [ 1 0] [ 1 1] [-1 1], [-1 0] ) sage: certificate.block_matrix_form() [ 1 0| 0 0] [-1 1| 0 0] [-----+-----] [ 0 0| 1 1] [ 0 0|-1 0] sage: M3 = Matrix_cmr_chr_sparse.one_sum([[1, 0], [-1, 1]], ....: [[1, 1], [-1, 0]], ....: [[1, 0], [0, 1]]); M3 [ 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 = M3.is_totally_unimodular(certificate=True); certificate OneSumNode (6×6) with 4 children sage: certificate.summand_matrices() ( [ 1 0] [ 1 1] [-1 1], [-1 0], [1], [1] ) sage: certificate.block_matrix_form() [ 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]
>>> 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)]]) >>> result, certificate = M.is_totally_unimodular(certificate=True); certificate OneSumNode (4×4) with 2 children >>> certificate.summand_matrices() ( [ 1 0] [ 1 1] [-1 1], [-1 0] ) >>> certificate.block_matrix_form() [ 1 0| 0 0] [-1 1| 0 0] [-----+-----] [ 0 0| 1 1] [ 0 0|-1 0] >>> M3 = 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)]]); M3 [ 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 = M3.is_totally_unimodular(certificate=True); certificate OneSumNode (6×6) with 4 children >>> certificate.summand_matrices() ( [ 1 0] [ 1 1] [-1 1], [-1 0], [1], [1] ) >>> certificate.block_matrix_form() [ 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]
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse M = Matrix_cmr_chr_sparse.one_sum([[1, 0], [-1, 1]], [[1, 1], [-1, 0]]) result, certificate = M.is_totally_unimodular(certificate=True); certificate certificate.summand_matrices() certificate.block_matrix_form() M3 = Matrix_cmr_chr_sparse.one_sum([[1, 0], [-1, 1]], [[1, 1], [-1, 0]], [[1, 0], [0, 1]]); M3 result, certificate = M3.is_totally_unimodular(certificate=True); certificate certificate.summand_matrices() certificate.block_matrix_form()
- static check(result_matrix, summand_matrices, summand_parent_rows_and_columns)[source]¶
Check that
result_matrixis a 1-sum ofsummand_matrices.EXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: from sage.matrix.seymour_decomposition import OneSumNode 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); certificate OneSumNode (4×4) with 2 children sage: OneSumNode.check(M2, ....: certificate.summand_matrices(), ....: certificate.child_keys())
>>> from sage.all import * >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> from sage.matrix.seymour_decomposition import OneSumNode >>> 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); certificate OneSumNode (4×4) with 2 children >>> OneSumNode.check(M2, ... certificate.summand_matrices(), ... certificate.child_keys())
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse from sage.matrix.seymour_decomposition import OneSumNode M2 = Matrix_cmr_chr_sparse.one_sum([[1, 0], [-1, 1]], [[1, 1], [-1, 0]]) result, certificate = M2.is_totally_unimodular(certificate=True); certificate OneSumNode.check(M2, certificate.summand_matrices(), certificate.child_keys())Symbolic identities:
sage: from sage.matrix.seymour_decomposition import OneSumNode sage: R.<x,y> = QQ[] sage: A = matrix([[x, 0], [-x, 1]]) sage: B = matrix([[x, y], [-x, 0]]) sage: A1B = block_diagonal_matrix([A, B]) sage: OneSumNode.check(A1B, [A, B], [([0, 1], [0, 1]), ....: ([2, 3], [2, 3])])
>>> from sage.all import * >>> from sage.matrix.seymour_decomposition import OneSumNode >>> R = QQ['x, y']; (x, y,) = R._first_ngens(2) >>> A = matrix([[x, Integer(0)], [-x, Integer(1)]]) >>> B = matrix([[x, y], [-x, Integer(0)]]) >>> A1B = block_diagonal_matrix([A, B]) >>> OneSumNode.check(A1B, [A, B], [([Integer(0), Integer(1)], [Integer(0), Integer(1)]), ... ([Integer(2), Integer(3)], [Integer(2), Integer(3)])])
from sage.matrix.seymour_decomposition import OneSumNode R.<x,y> = QQ[] A = matrix([[x, 0], [-x, 1]]) B = matrix([[x, y], [-x, 0]]) A1B = block_diagonal_matrix([A, B]) OneSumNode.check(A1B, [A, B], [([0, 1], [0, 1]), ([2, 3], [2, 3])])Using program analysis:
sage: # optional - cutgeneratingfunctionology sage: R.<x,y,z> = ParametricRealField({x: 1}, {y: -1}, {z: 0}) # true example sage: A = matrix([[x, 0], [-x, 1]]) sage: B = matrix([[x, y], [-x, 0]]) sage: A1B = matrix([[z, 0, 0, 0], [-x, z, 0, 0], [], []]) sage: OneSumNode.check(A1B, [A, B], [([0, 1], [0, 1]), ....: ([2, 3], [2, 3])]) sage: # side-effect: R stores polynomial identities
>>> from sage.all import * >>> # optional - cutgeneratingfunctionology >>> R = ParametricRealField({x: Integer(1)}, {y: -Integer(1)}, {z: Integer(0)}, names=('x', 'y', 'z',)); (x, y, z,) = R._first_ngens(3)# true example >>> A = matrix([[x, Integer(0)], [-x, Integer(1)]]) >>> B = matrix([[x, y], [-x, Integer(0)]]) >>> A1B = matrix([[z, Integer(0), Integer(0), Integer(0)], [-x, z, Integer(0), Integer(0)], [], []]) >>> OneSumNode.check(A1B, [A, B], [([Integer(0), Integer(1)], [Integer(0), Integer(1)]), ... ([Integer(2), Integer(3)], [Integer(2), Integer(3)])]) >>> # side-effect: R stores polynomial identities
# optional - cutgeneratingfunctionology R.<x,y,z> = ParametricRealField({x: 1}, {y: -1}, {z: 0}) # true example A = matrix([[x, 0], [-x, 1]]) B = matrix([[x, y], [-x, 0]]) A1B = matrix([[z, 0, 0, 0], [-x, z, 0, 0], [], []]) OneSumNode.check(A1B, [A, B], [([0, 1], [0, 1]), ([2, 3], [2, 3])]) # side-effect: R stores polynomial identities
- class sage.matrix.seymour_decomposition.PivotsNode[source]¶
Bases:
DecompositionNode- npivots()[source]¶
Return the number of pivots in
self.EXAMPLES:
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") sage: certificate PivotsNode (9×12) sage: certificate.npivots() 1
>>> from sage.all import * >>> 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") >>> certificate PivotsNode (9×12) >>> certificate.npivots() 1
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse 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]]) result, certificate = R12.is_totally_unimodular(certificate=True, decompose_strategy="delta_pivot") certificate certificate.npivots()
- pivot_rows_and_columns()[source]¶
Return a tuple of the row and column indices of all pivot entries.
EXAMPLES:
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") sage: certificate PivotsNode (9×12) sage: certificate.pivot_rows_and_columns() ((0, 8),)
>>> from sage.all import * >>> 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") >>> certificate PivotsNode (9×12) >>> certificate.pivot_rows_and_columns() ((0, 8),)
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse 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]]) result, certificate = R12.is_totally_unimodular(certificate=True, decompose_strategy="delta_pivot") certificate certificate.pivot_rows_and_columns()
- class sage.matrix.seymour_decomposition.PlanarNode[source]¶
Bases:
BaseGraphicNode- cograph()[source]¶
Return the cograph of matrix.
EXAMPLES:
Undirected graph:
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, ....: check_graphic_minors_planar=True) sage: result, certificate (True, PlanarNode (3×2)) sage: G = certificate.cograph(); G Graph on 3 vertices sage: G.vertices(sort=True) [1, 2, 7] sage: G.edges(sort=True) [(1, 2, None), (1, 7, None), (2, 7, None)] sage: certificate.cograph_forest_edges() ((1, 2), (7, 1)) sage: certificate.cograph_coforest_edges() ((1, 2), (2, 7), (7, 1))
>>> 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, ... check_graphic_minors_planar=True) >>> result, certificate (True, PlanarNode (3×2)) >>> G = certificate.cograph(); G Graph on 3 vertices >>> G.vertices(sort=True) [1, 2, 7] >>> G.edges(sort=True) [(1, 2, None), (1, 7, None), (2, 7, None)] >>> certificate.cograph_forest_edges() ((1, 2), (7, 1)) >>> certificate.cograph_coforest_edges() ((1, 2), (2, 7), (7, 1))
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 2, sparse=True), [[1, 0], [1, 1], [0,1]]); M result, certificate = M._is_binary_linear_matroid_regular(certificate=True, check_graphic_minors_planar=True) result, certificate G = certificate.cograph(); G G.vertices(sort=True) G.edges(sort=True) certificate.cograph_forest_edges() certificate.cograph_coforest_edges()Directed graph:
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, ....: check_graphic_minors_planar=True) sage: result, certificate (True, PlanarNode (3×2)) sage: G = certificate.cograph(); G Digraph on 3 vertices sage: G.vertices(sort=True) [1, 2, 7] sage: G.edges(sort=True) [(1, 2, None), (1, 7, None), (2, 7, None), (7, 1, None)] sage: certificate.cograph_forest_edges() ((1, 2), (1, 7)) sage: certificate.cograph_coforest_edges() ((1, 2), (2, 7), (7, 1))
>>> 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, ... check_graphic_minors_planar=True) >>> result, certificate (True, PlanarNode (3×2)) >>> G = certificate.cograph(); G Digraph on 3 vertices >>> G.vertices(sort=True) [1, 2, 7] >>> G.edges(sort=True) [(1, 2, None), (1, 7, None), (2, 7, None), (7, 1, None)] >>> certificate.cograph_forest_edges() ((1, 2), (1, 7)) >>> certificate.cograph_coforest_edges() ((1, 2), (2, 7), (7, 1))
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 2, sparse=True), [[1, 0], [-1, 1], [0,-1]]); M result, certificate = M.is_totally_unimodular(certificate=True, check_graphic_minors_planar=True) result, certificate G = certificate.cograph(); G G.vertices(sort=True) G.edges(sort=True) certificate.cograph_forest_edges() certificate.cograph_coforest_edges()
- class sage.matrix.seymour_decomposition.R10Node[source]¶
Bases:
DecompositionNodeSpecial R10 Node. Only two possible 5 by 5 matrices up to row and column permutations and negations.
EXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: R10 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 5, 5, sparse=True), ....: [[1, 0, 0, 1, 1], ....: [1, 1, 0, 0, 1], ....: [0, 1, 1, 0, 1], ....: [0, 0, 1, 1, 1], ....: [1, 1, 1, 1, 1]]); R10 [1 0 0 1 1] [1 1 0 0 1] [0 1 1 0 1] [0 0 1 1 1] [1 1 1 1 1] sage: result, certificate = R10.is_totally_unimodular(certificate=True) sage: result True sage: R10.is_network_matrix() False sage: R10.is_conetwork_matrix() False sage: result, certificate = R10._is_binary_linear_matroid_regular(certificate=True) sage: result True sage: certificate._is_binary_linear_matroid_graphic() False sage: certificate._is_binary_linear_matroid_cographic() False sage: R10 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 5, 5, sparse=True), ....: [[ 1,-1, 0, 0,-1], ....: [-1, 1,-1, 0, 0], ....: [ 0,-1, 1,-1, 0], ....: [ 0, 0,-1, 1,-1], ....: [-1, 0, 0,-1, 1]]); R10 [ 1 -1 0 0 -1] [-1 1 -1 0 0] [ 0 -1 1 -1 0] [ 0 0 -1 1 -1] [-1 0 0 -1 1] sage: result, certificate = R10.is_totally_unimodular(certificate=True) sage: result True sage: R10.is_network_matrix() False sage: R10.is_conetwork_matrix() False sage: R10 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 5, 5, sparse=True), ....: [[1, 1, 0, 0, 1], ....: [1, 1,-1, 0, 0], ....: [0, 1,-1,-1, 0], ....: [0, 0, 1, 1, 1], ....: [1, 0, 0, 1, 1]]); R10 [ 1 1 0 0 1] [ 1 1 -1 0 0] [ 0 1 -1 -1 0] [ 0 0 1 1 1] [ 1 0 0 1 1] sage: result, certificate = R10.is_totally_unimodular(certificate=True) sage: result True sage: R10.is_network_matrix() False sage: R10.is_conetwork_matrix() False sage: R10 = Matrix_cmr_chr_sparse(MatrixSpace(GF(2), 5, 5, sparse=True), ....: [[1, 1, 0, 0, 1], ....: [1, 1,-1, 0, 0], ....: [0, 1,-1,-1, 0], ....: [0, 0, 1, 1, 1], ....: [1, 0, 0, 1, 1]]); R10 [1 1 0 0 1] [1 1 1 0 0] [0 1 1 1 0] [0 0 1 1 1] [1 0 0 1 1] sage: result, certificate = R10._is_binary_linear_matroid_regular(certificate=True) sage: result True sage: certificate R10Node (5×5) a reduced matrix representation of R10 matroid sage: certificate._is_binary_linear_matroid_graphic() False sage: certificate._is_binary_linear_matroid_cographic() False
>>> from sage.all import * >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> R10 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(5), Integer(5), sparse=True), ... [[Integer(1), Integer(0), Integer(0), Integer(1), Integer(1)], ... [Integer(1), Integer(1), Integer(0), Integer(0), Integer(1)], ... [Integer(0), Integer(1), Integer(1), Integer(0), Integer(1)], ... [Integer(0), Integer(0), Integer(1), Integer(1), Integer(1)], ... [Integer(1), Integer(1), Integer(1), Integer(1), Integer(1)]]); R10 [1 0 0 1 1] [1 1 0 0 1] [0 1 1 0 1] [0 0 1 1 1] [1 1 1 1 1] >>> result, certificate = R10.is_totally_unimodular(certificate=True) >>> result True >>> R10.is_network_matrix() False >>> R10.is_conetwork_matrix() False >>> result, certificate = R10._is_binary_linear_matroid_regular(certificate=True) >>> result True >>> certificate._is_binary_linear_matroid_graphic() False >>> certificate._is_binary_linear_matroid_cographic() False >>> R10 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(5), Integer(5), sparse=True), ... [[ Integer(1),-Integer(1), Integer(0), Integer(0),-Integer(1)], ... [-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)]]); R10 [ 1 -1 0 0 -1] [-1 1 -1 0 0] [ 0 -1 1 -1 0] [ 0 0 -1 1 -1] [-1 0 0 -1 1] >>> result, certificate = R10.is_totally_unimodular(certificate=True) >>> result True >>> R10.is_network_matrix() False >>> R10.is_conetwork_matrix() False >>> R10 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(5), Integer(5), sparse=True), ... [[Integer(1), Integer(1), Integer(0), Integer(0), Integer(1)], ... [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)]]); R10 [ 1 1 0 0 1] [ 1 1 -1 0 0] [ 0 1 -1 -1 0] [ 0 0 1 1 1] [ 1 0 0 1 1] >>> result, certificate = R10.is_totally_unimodular(certificate=True) >>> result True >>> R10.is_network_matrix() False >>> R10.is_conetwork_matrix() False >>> R10 = Matrix_cmr_chr_sparse(MatrixSpace(GF(Integer(2)), Integer(5), Integer(5), sparse=True), ... [[Integer(1), Integer(1), Integer(0), Integer(0), Integer(1)], ... [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)]]); R10 [1 1 0 0 1] [1 1 1 0 0] [0 1 1 1 0] [0 0 1 1 1] [1 0 0 1 1] >>> result, certificate = R10._is_binary_linear_matroid_regular(certificate=True) >>> result True >>> certificate R10Node (5×5) a reduced matrix representation of R10 matroid >>> certificate._is_binary_linear_matroid_graphic() False >>> certificate._is_binary_linear_matroid_cographic() False
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse R10 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 5, 5, sparse=True), [[1, 0, 0, 1, 1], [1, 1, 0, 0, 1], [0, 1, 1, 0, 1], [0, 0, 1, 1, 1], [1, 1, 1, 1, 1]]); R10 result, certificate = R10.is_totally_unimodular(certificate=True) result R10.is_network_matrix() R10.is_conetwork_matrix() result, certificate = R10._is_binary_linear_matroid_regular(certificate=True) result certificate._is_binary_linear_matroid_graphic() certificate._is_binary_linear_matroid_cographic() R10 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 5, 5, sparse=True), [[ 1,-1, 0, 0,-1], [-1, 1,-1, 0, 0], [ 0,-1, 1,-1, 0], [ 0, 0,-1, 1,-1], [-1, 0, 0,-1, 1]]); R10 result, certificate = R10.is_totally_unimodular(certificate=True) result R10.is_network_matrix() R10.is_conetwork_matrix() R10 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 5, 5, sparse=True), [[1, 1, 0, 0, 1], [1, 1,-1, 0, 0], [0, 1,-1,-1, 0], [0, 0, 1, 1, 1], [1, 0, 0, 1, 1]]); R10 result, certificate = R10.is_totally_unimodular(certificate=True) result R10.is_network_matrix() R10.is_conetwork_matrix() R10 = Matrix_cmr_chr_sparse(MatrixSpace(GF(2), 5, 5, sparse=True), [[1, 1, 0, 0, 1], [1, 1,-1, 0, 0], [0, 1,-1,-1, 0], [0, 0, 1, 1, 1], [1, 0, 0, 1, 1]]); R10 result, certificate = R10._is_binary_linear_matroid_regular(certificate=True) result certificate certificate._is_binary_linear_matroid_graphic() certificate._is_binary_linear_matroid_cographic()
- class sage.matrix.seymour_decomposition.SeriesParallelReductionNode[source]¶
Bases:
DecompositionNode- core()[source]¶
Return the core of
self.A
SeriesParallelReductionNodeindicates that \(M\) arises from a smaller matrix \(M'\) (called the core) 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.
EXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 5, 6, sparse=True), ....: [[1, 1, 1, 1, 1, 0], [1, 1, 1, 0, 0, 0], ....: [1, 0, 1, 1, 0, 1], [1, 0, 0, 1, 1, 0], ....: [1, 1, 0, 0, 1, 0]]); M [1 1 1 1 1 0] [1 1 1 0 0 0] [1 0 1 1 0 1] [1 0 0 1 1 0] [1 1 0 0 1 0] sage: result, certificate = M.is_totally_unimodular(certificate=True) sage: result, certificate (True, SeriesParallelReductionNode (5×6)) sage: certificate.core() [1 1 1 1 1] [1 1 1 0 0] [1 0 1 1 0] [1 0 0 1 1] [1 1 0 0 1]
>>> from sage.all import * >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(5), Integer(6), sparse=True), ... [[Integer(1), Integer(1), Integer(1), Integer(1), Integer(1), Integer(0)], [Integer(1), Integer(1), Integer(1), Integer(0), Integer(0), Integer(0)], ... [Integer(1), Integer(0), Integer(1), Integer(1), Integer(0), Integer(1)], [Integer(1), Integer(0), Integer(0), Integer(1), Integer(1), Integer(0)], ... [Integer(1), Integer(1), Integer(0), Integer(0), Integer(1), Integer(0)]]); M [1 1 1 1 1 0] [1 1 1 0 0 0] [1 0 1 1 0 1] [1 0 0 1 1 0] [1 1 0 0 1 0] >>> result, certificate = M.is_totally_unimodular(certificate=True) >>> result, certificate (True, SeriesParallelReductionNode (5×6)) >>> certificate.core() [1 1 1 1 1] [1 1 1 0 0] [1 0 1 1 0] [1 0 0 1 1] [1 1 0 0 1]
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 5, 6, sparse=True), [[1, 1, 1, 1, 1, 0], [1, 1, 1, 0, 0, 0], [1, 0, 1, 1, 0, 1], [1, 0, 0, 1, 1, 0], [1, 1, 0, 0, 1, 0]]); M result, certificate = M.is_totally_unimodular(certificate=True) result, certificate certificate.core()
- class sage.matrix.seymour_decomposition.SumNode[source]¶
Bases:
DecompositionNodeBase class for 1-sum, 2-sum, and 3-sums (\(\Delta\)-sum, 3-sum, Y-sum) nodes in Seymour’s decomposition
- permuted_block_matrix()[source]¶
Return the permutation matrices between the matrix and the block matrix form.
OUTPUT: a tuple
(Prow, BlockMatrix, Pcolumn), whereself.matrix() == Prow * BlockMatrix * Pcolumn, andBlockMatrix == self.block_matrix_form().EXAMPLES:
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: M_perm = M.matrix_from_rows_and_columns([2, 4, 3, 0, 5, 1], ....: [0, 1, 3, 5, 4, 2]); M_perm [ 0 0 1 0 0 1] [ 0 0 0 0 1 0] [ 0 0 0 0 0 -1] [ 1 0 0 0 0 0] [ 0 0 0 1 0 0] [-1 1 0 0 0 0] sage: result, certificate = M_perm.is_totally_unimodular(certificate=True) sage: certificate OneSumNode (6×6) with 4 children sage: P_row, block_matrix, P_column = certificate.permuted_block_matrix() sage: P_row^(-1) * M_perm * P_column^(-1) == block_matrix True
>>> 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] >>> M_perm = M.matrix_from_rows_and_columns([Integer(2), Integer(4), Integer(3), Integer(0), Integer(5), Integer(1)], ... [Integer(0), Integer(1), Integer(3), Integer(5), Integer(4), Integer(2)]); M_perm [ 0 0 1 0 0 1] [ 0 0 0 0 1 0] [ 0 0 0 0 0 -1] [ 1 0 0 0 0 0] [ 0 0 0 1 0 0] [-1 1 0 0 0 0] >>> result, certificate = M_perm.is_totally_unimodular(certificate=True) >>> certificate OneSumNode (6×6) with 4 children >>> P_row, block_matrix, P_column = certificate.permuted_block_matrix() >>> P_row**(-Integer(1)) * M_perm * P_column**(-Integer(1)) == block_matrix True
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse M = Matrix_cmr_chr_sparse.one_sum([[1, 0], [-1, 1]], [[1, 1], [-1, 0]], [[1, 0], [0, 1]]); M M_perm = M.matrix_from_rows_and_columns([2, 4, 3, 0, 5, 1], [0, 1, 3, 5, 4, 2]); M_perm result, certificate = M_perm.is_totally_unimodular(certificate=True) certificate P_row, block_matrix, P_column = certificate.permuted_block_matrix() P_row^(-1) * M_perm * P_column^(-1) == block_matrix
- summand_matrices()[source]¶
Return a tuple of matrices representing the child nodes.
EXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse 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.summand_matrices() ( [ 1 0] [ 1 1] [-1 1], [-1 0] )
>>> from sage.all import * >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> 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.summand_matrices() ( [ 1 0] [ 1 1] [-1 1], [-1 0] )
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse M2 = Matrix_cmr_chr_sparse.one_sum([[1, 0], [-1, 1]], [[1, 1], [-1, 0]]) result, certificate = M2.is_totally_unimodular(certificate=True, row_keys=range(4), column_keys='abcd') certificate.summand_matrices()
- class sage.matrix.seymour_decomposition.ThreeConnectedIrregularNode[source]¶
Bases:
DecompositionNode
- class sage.matrix.seymour_decomposition.ThreeSumNode[source]¶
Bases:
SumNode- block_matrix_form()[source]¶
Return the block matrix constructed from the 3-sum of children.
EXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: R12 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 6, sparse=True), ....: [[1,0,1,1,0,0],[0,1,1,1,0,0],[1,0,1,0,1,1], ....: [0,-1,0,-1,1,1],[1,0,1,0,1,0],[0,-1,0,-1,0,1]]) sage: R12 [ 1 0 1 1 0 0] [ 0 1 1 1 0 0] [ 1 0 1 0 1 1] [ 0 -1 0 -1 1 1] [ 1 0 1 0 1 0] [ 0 -1 0 -1 0 1] sage: result, certificate = R12.is_totally_unimodular(certificate=True, ....: decompose_strategy="three_pivot") sage: C = certificate; C ThreeSumNode (6×6) sage: C.matrix() [ 1 0 1 1 0 0] [ 0 1 1 1 0 0] [ 1 0 1 0 1 1] [ 0 -1 0 -1 1 1] [ 1 0 1 0 1 0] [ 0 -1 0 -1 0 1] sage: C.summand_matrices() ( [ 1 1 0 0] [ 1 0 1 1 0] [ 1 0 1 1] [ 0 1 1 1 0] [ 0 -1 1 1] [ 1 0 1 0 1] [ 1 0 1 0] [ 0 -1 0 -1 1], [ 0 -1 0 1] ) sage: C.child_keys() (((r0, r1, r2, r3), (c0, c1, c2, c3, +r2+r3)), ((+c0+c3, r2, r3, r4, r5), (c0, c3, c4, c5))) sage: C.block_matrix_form() [ 1 0 1 1 0 0] [ 0 1 1 1 0 0] [ 1 0 1 0 1 1] [ 0 -1 0 -1 1 1] [ 1 0 1 0 1 0] [ 0 -1 0 -1 0 1]
>>> from sage.all import * >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> R12 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(6), Integer(6), sparse=True), ... [[Integer(1),Integer(0),Integer(1),Integer(1),Integer(0),Integer(0)],[Integer(0),Integer(1),Integer(1),Integer(1),Integer(0),Integer(0)],[Integer(1),Integer(0),Integer(1),Integer(0),Integer(1),Integer(1)], ... [Integer(0),-Integer(1),Integer(0),-Integer(1),Integer(1),Integer(1)],[Integer(1),Integer(0),Integer(1),Integer(0),Integer(1),Integer(0)],[Integer(0),-Integer(1),Integer(0),-Integer(1),Integer(0),Integer(1)]]) >>> R12 [ 1 0 1 1 0 0] [ 0 1 1 1 0 0] [ 1 0 1 0 1 1] [ 0 -1 0 -1 1 1] [ 1 0 1 0 1 0] [ 0 -1 0 -1 0 1] >>> result, certificate = R12.is_totally_unimodular(certificate=True, ... decompose_strategy="three_pivot") >>> C = certificate; C ThreeSumNode (6×6) >>> C.matrix() [ 1 0 1 1 0 0] [ 0 1 1 1 0 0] [ 1 0 1 0 1 1] [ 0 -1 0 -1 1 1] [ 1 0 1 0 1 0] [ 0 -1 0 -1 0 1] >>> C.summand_matrices() ( [ 1 1 0 0] [ 1 0 1 1 0] [ 1 0 1 1] [ 0 1 1 1 0] [ 0 -1 1 1] [ 1 0 1 0 1] [ 1 0 1 0] [ 0 -1 0 -1 1], [ 0 -1 0 1] ) >>> C.child_keys() (((r0, r1, r2, r3), (c0, c1, c2, c3, +r2+r3)), ((+c0+c3, r2, r3, r4, r5), (c0, c3, c4, c5))) >>> C.block_matrix_form() [ 1 0 1 1 0 0] [ 0 1 1 1 0 0] [ 1 0 1 0 1 1] [ 0 -1 0 -1 1 1] [ 1 0 1 0 1 0] [ 0 -1 0 -1 0 1]
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse R12 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 6, sparse=True), [[1,0,1,1,0,0],[0,1,1,1,0,0],[1,0,1,0,1,1], [0,-1,0,-1,1,1],[1,0,1,0,1,0],[0,-1,0,-1,0,1]]) R12 result, certificate = R12.is_totally_unimodular(certificate=True, decompose_strategy="three_pivot") C = certificate; C C.matrix() C.summand_matrices() C.child_keys() C.block_matrix_form()
- is_concentrated_rank()[source]¶
Return
Truefor the 3-sum nodeself.concentrated_rankis named after the rank 2 and rank 0 off-diagonal blocks.
- is_distributed_ranks()[source]¶
Return
Falsefor the 3-sum nodeself.distributed_ranksis named after the two rank 1 off-diagonal blocks.EXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: R12_large = 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_large.is_totally_unimodular(certificate=True, ....: decompose_strategy="three_pivot") sage: C = certificate; C ThreeSumNode (9×12) sage: C.is_distributed_ranks() False sage: C.is_concentrated_rank() True
>>> from sage.all import * >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> R12_large = 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_large.is_totally_unimodular(certificate=True, ... decompose_strategy="three_pivot") >>> C = certificate; C ThreeSumNode (9×12) >>> C.is_distributed_ranks() False >>> C.is_concentrated_rank() True
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse R12_large = 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]]) result, certificate = R12_large.is_totally_unimodular(certificate=True, decompose_strategy="three_pivot") C = certificate; C C.is_distributed_ranks() C.is_concentrated_rank()
- permuted_block_matrix()[source]¶
Return the permutation matrices between the matrix and the block matrix form.
OUTPUT: a tuple
(Prow, BlockMatrix, Pcolumn), whereself.matrix() == Prow * BlockMatrix * Pcolumn, andBlockMatrix == self.block_matrix_form().EXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: R12 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 6, sparse=True), ....: [[1,0,1,1,0,0],[0,1,1,1,0,0],[1,0,1,0,1,1], ....: [0,-1,0,-1,1,1],[1,0,1,0,1,0],[0,-1,0,-1,0,1]]) sage: R12 [ 1 0 1 1 0 0] [ 0 1 1 1 0 0] [ 1 0 1 0 1 1] [ 0 -1 0 -1 1 1] [ 1 0 1 0 1 0] [ 0 -1 0 -1 0 1] sage: result, certificate = R12.is_totally_unimodular(certificate=True, ....: decompose_strategy="three_pivot") sage: C = certificate; C ThreeSumNode (6×6) sage: C.matrix() [ 1 0 1 1 0 0] [ 0 1 1 1 0 0] [ 1 0 1 0 1 1] [ 0 -1 0 -1 1 1] [ 1 0 1 0 1 0] [ 0 -1 0 -1 0 1] sage: C.block_matrix_form() [ 1 0 1 1 0 0] [ 0 1 1 1 0 0] [ 1 0 1 0 1 1] [ 0 -1 0 -1 1 1] [ 1 0 1 0 1 0] [ 0 -1 0 -1 0 1] sage: P_row, block_matrix, P_column = C.permuted_block_matrix() sage: P_row^(-1) * C.matrix() * P_column^(-1) == block_matrix True
>>> from sage.all import * >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> R12 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(6), Integer(6), sparse=True), ... [[Integer(1),Integer(0),Integer(1),Integer(1),Integer(0),Integer(0)],[Integer(0),Integer(1),Integer(1),Integer(1),Integer(0),Integer(0)],[Integer(1),Integer(0),Integer(1),Integer(0),Integer(1),Integer(1)], ... [Integer(0),-Integer(1),Integer(0),-Integer(1),Integer(1),Integer(1)],[Integer(1),Integer(0),Integer(1),Integer(0),Integer(1),Integer(0)],[Integer(0),-Integer(1),Integer(0),-Integer(1),Integer(0),Integer(1)]]) >>> R12 [ 1 0 1 1 0 0] [ 0 1 1 1 0 0] [ 1 0 1 0 1 1] [ 0 -1 0 -1 1 1] [ 1 0 1 0 1 0] [ 0 -1 0 -1 0 1] >>> result, certificate = R12.is_totally_unimodular(certificate=True, ... decompose_strategy="three_pivot") >>> C = certificate; C ThreeSumNode (6×6) >>> C.matrix() [ 1 0 1 1 0 0] [ 0 1 1 1 0 0] [ 1 0 1 0 1 1] [ 0 -1 0 -1 1 1] [ 1 0 1 0 1 0] [ 0 -1 0 -1 0 1] >>> C.block_matrix_form() [ 1 0 1 1 0 0] [ 0 1 1 1 0 0] [ 1 0 1 0 1 1] [ 0 -1 0 -1 1 1] [ 1 0 1 0 1 0] [ 0 -1 0 -1 0 1] >>> P_row, block_matrix, P_column = C.permuted_block_matrix() >>> P_row**(-Integer(1)) * C.matrix() * P_column**(-Integer(1)) == block_matrix True
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse R12 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 6, sparse=True), [[1,0,1,1,0,0],[0,1,1,1,0,0],[1,0,1,0,1,1], [0,-1,0,-1,1,1],[1,0,1,0,1,0],[0,-1,0,-1,0,1]]) R12 result, certificate = R12.is_totally_unimodular(certificate=True, decompose_strategy="three_pivot") C = certificate; C C.matrix() C.block_matrix_form() P_row, block_matrix, P_column = C.permuted_block_matrix() P_row^(-1) * C.matrix() * P_column^(-1) == block_matrix
- class sage.matrix.seymour_decomposition.TwoSumNode[source]¶
Bases:
SumNode- block_matrix_form()[source]¶
Return the block matrix representing the two sum node.
EXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 5, 5, sparse=True), ....: [[1, 1, 1, 1, 1], [1, 1, 1, 0, 0], ....: [1, 0, 1, 1, 0], [1, 0, 0, 1, 1], ....: [1, 1, 0, 0, 1]]); M2 [1 1 1 1 1] [1 1 1 0 0] [1 0 1 1 0] [1 0 0 1 1] [1 1 0 0 1] sage: M3 = Matrix_cmr_chr_sparse.two_sum(M2, M2, 0, 1); M3 [1 1 1 1|1 1 1 0 0] [1 1 0 0|1 1 1 0 0] [0 1 1 0|1 1 1 0 0] [0 0 1 1|1 1 1 0 0] [1 0 0 1|1 1 1 0 0] [-------+---------] [0 0 0 0|1 1 1 1 1] [0 0 0 0|1 0 1 1 0] [0 0 0 0|1 0 0 1 1] [0 0 0 0|1 1 0 0 1] sage: result, certificate = M3.is_totally_unimodular(certificate=True); certificate TwoSumNode (9×9) sage: K33 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 5, 4, sparse=True), ....: [[1, 1, 0, 0], [1, 1, 1, 0], ....: [1, 0, 0,-1], [0, 1, 1, 1], ....: [0, 0, 1, 1]]); K33 [ 1 1 0 0] [ 1 1 1 0] [ 1 0 0 -1] [ 0 1 1 1] [ 0 0 1 1] sage: K33_dual = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 4, 5, sparse=True), ....: [[1, 1, 1, 0, 0], [1, 1, 0, 1, 0], ....: [0, 1, 0, 1, 1], [0, 0,-1, 1, 1]]); K33_dual [ 1 1 1 0 0] [ 1 1 0 1 0] [ 0 1 0 1 1] [ 0 0 -1 1 1] sage: M = Matrix_cmr_chr_sparse.two_sum(K33, K33_dual, 0, 0, ....: nonzero_block="bottom_left"); M [ 1 1 1 0| 0 0 0 0] [ 1 0 0 -1| 0 0 0 0] [ 0 1 1 1| 0 0 0 0] [ 0 0 1 1| 0 0 0 0] [-----------+-----------] [ 1 1 0 0| 1 1 0 0] [ 1 1 0 0| 1 0 1 0] [ 0 0 0 0| 1 0 1 1] [ 0 0 0 0| 0 -1 1 1] sage: result1, certificate1 = M.is_totally_unimodular(certificate=True); certificate1 TwoSumNode (8×8) sage: certificate1.summand_matrices() ( [ 1 1 1 0] [ 1 0 0 -1] [ 1 1 1 0 0] [ 0 1 1 1] [ 1 1 0 1 0] [ 0 0 1 1] [ 0 1 0 1 1] [ 1 1 0 0], [ 0 0 -1 1 1] ) sage: certificate1.block_matrix_form() [ 1 1 1 0| 0 0 0 0] [ 1 0 0 -1| 0 0 0 0] [ 0 1 1 1| 0 0 0 0] [ 0 0 1 1| 0 0 0 0] [-----------+-----------] [ 1 1 0 0| 1 1 0 0] [ 1 1 0 0| 1 0 1 0] [ 0 0 0 0| 1 0 1 1] [ 0 0 0 0| 0 -1 1 1] sage: certificate1.child_keys() (((0, 1, 2, 3, 4), (0, 1, 2, 3)), ((4, 5, 6, 7), (0, 4, 5, 6, 7))) sage: M_perm = M.matrix_from_rows_and_columns([4, 6, 5, 7, 0, 1, 2, 3], range(M.ncols())) sage: M_perm [ 1 1 0 0 1 1 0 0] [ 0 0 0 0 1 0 1 1] [ 1 1 0 0 1 0 1 0] [ 0 0 0 0 0 -1 1 1] [ 1 1 1 0 0 0 0 0] [ 1 0 0 -1 0 0 0 0] [ 0 1 1 1 0 0 0 0] [ 0 0 1 1 0 0 0 0] sage: result2, certificate2 = M_perm.is_totally_unimodular(certificate=True) sage: certificate2.summand_matrices() ( [ 1 1 1 0] [ 1 0 0 -1] [ 1 1 1 0 0] [ 0 1 1 1] [ 0 1 0 1 1] [ 0 0 1 1] [ 1 1 0 1 0] [ 1 1 0 0], [ 0 0 -1 1 1] ) sage: certificate2.block_matrix_form() [ 1 1 1 0| 0 0 0 0] [ 1 0 0 -1| 0 0 0 0] [ 0 1 1 1| 0 0 0 0] [ 0 0 1 1| 0 0 0 0] [-----------+-----------] [ 1 1 0 0| 1 1 0 0] [ 0 0 0 0| 1 0 1 1] [ 1 1 0 0| 1 0 1 0] [ 0 0 0 0| 0 -1 1 1] sage: certificate2.child_keys() (((4, 5, 6, 7, 0), (0, 1, 2, 3)), ((0, 1, 2, 3), (0, 4, 5, 6, 7)))
>>> from sage.all import * >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(5), Integer(5), sparse=True), ... [[Integer(1), Integer(1), Integer(1), Integer(1), Integer(1)], [Integer(1), Integer(1), Integer(1), Integer(0), Integer(0)], ... [Integer(1), Integer(0), Integer(1), Integer(1), Integer(0)], [Integer(1), Integer(0), Integer(0), Integer(1), Integer(1)], ... [Integer(1), Integer(1), Integer(0), Integer(0), Integer(1)]]); M2 [1 1 1 1 1] [1 1 1 0 0] [1 0 1 1 0] [1 0 0 1 1] [1 1 0 0 1] >>> M3 = Matrix_cmr_chr_sparse.two_sum(M2, M2, Integer(0), Integer(1)); M3 [1 1 1 1|1 1 1 0 0] [1 1 0 0|1 1 1 0 0] [0 1 1 0|1 1 1 0 0] [0 0 1 1|1 1 1 0 0] [1 0 0 1|1 1 1 0 0] [-------+---------] [0 0 0 0|1 1 1 1 1] [0 0 0 0|1 0 1 1 0] [0 0 0 0|1 0 0 1 1] [0 0 0 0|1 1 0 0 1] >>> result, certificate = M3.is_totally_unimodular(certificate=True); certificate TwoSumNode (9×9) >>> K33 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(5), Integer(4), sparse=True), ... [[Integer(1), Integer(1), Integer(0), Integer(0)], [Integer(1), Integer(1), Integer(1), Integer(0)], ... [Integer(1), Integer(0), Integer(0),-Integer(1)], [Integer(0), Integer(1), Integer(1), Integer(1)], ... [Integer(0), Integer(0), Integer(1), Integer(1)]]); K33 [ 1 1 0 0] [ 1 1 1 0] [ 1 0 0 -1] [ 0 1 1 1] [ 0 0 1 1] >>> K33_dual = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(4), Integer(5), sparse=True), ... [[Integer(1), Integer(1), Integer(1), Integer(0), Integer(0)], [Integer(1), Integer(1), Integer(0), Integer(1), Integer(0)], ... [Integer(0), Integer(1), Integer(0), Integer(1), Integer(1)], [Integer(0), Integer(0),-Integer(1), Integer(1), Integer(1)]]); K33_dual [ 1 1 1 0 0] [ 1 1 0 1 0] [ 0 1 0 1 1] [ 0 0 -1 1 1] >>> M = Matrix_cmr_chr_sparse.two_sum(K33, K33_dual, Integer(0), Integer(0), ... nonzero_block="bottom_left"); M [ 1 1 1 0| 0 0 0 0] [ 1 0 0 -1| 0 0 0 0] [ 0 1 1 1| 0 0 0 0] [ 0 0 1 1| 0 0 0 0] [-----------+-----------] [ 1 1 0 0| 1 1 0 0] [ 1 1 0 0| 1 0 1 0] [ 0 0 0 0| 1 0 1 1] [ 0 0 0 0| 0 -1 1 1] >>> result1, certificate1 = M.is_totally_unimodular(certificate=True); certificate1 TwoSumNode (8×8) >>> certificate1.summand_matrices() ( [ 1 1 1 0] [ 1 0 0 -1] [ 1 1 1 0 0] [ 0 1 1 1] [ 1 1 0 1 0] [ 0 0 1 1] [ 0 1 0 1 1] [ 1 1 0 0], [ 0 0 -1 1 1] ) >>> certificate1.block_matrix_form() [ 1 1 1 0| 0 0 0 0] [ 1 0 0 -1| 0 0 0 0] [ 0 1 1 1| 0 0 0 0] [ 0 0 1 1| 0 0 0 0] [-----------+-----------] [ 1 1 0 0| 1 1 0 0] [ 1 1 0 0| 1 0 1 0] [ 0 0 0 0| 1 0 1 1] [ 0 0 0 0| 0 -1 1 1] >>> certificate1.child_keys() (((0, 1, 2, 3, 4), (0, 1, 2, 3)), ((4, 5, 6, 7), (0, 4, 5, 6, 7))) >>> M_perm = M.matrix_from_rows_and_columns([Integer(4), Integer(6), Integer(5), Integer(7), Integer(0), Integer(1), Integer(2), Integer(3)], range(M.ncols())) >>> M_perm [ 1 1 0 0 1 1 0 0] [ 0 0 0 0 1 0 1 1] [ 1 1 0 0 1 0 1 0] [ 0 0 0 0 0 -1 1 1] [ 1 1 1 0 0 0 0 0] [ 1 0 0 -1 0 0 0 0] [ 0 1 1 1 0 0 0 0] [ 0 0 1 1 0 0 0 0] >>> result2, certificate2 = M_perm.is_totally_unimodular(certificate=True) >>> certificate2.summand_matrices() ( [ 1 1 1 0] [ 1 0 0 -1] [ 1 1 1 0 0] [ 0 1 1 1] [ 0 1 0 1 1] [ 0 0 1 1] [ 1 1 0 1 0] [ 1 1 0 0], [ 0 0 -1 1 1] ) >>> certificate2.block_matrix_form() [ 1 1 1 0| 0 0 0 0] [ 1 0 0 -1| 0 0 0 0] [ 0 1 1 1| 0 0 0 0] [ 0 0 1 1| 0 0 0 0] [-----------+-----------] [ 1 1 0 0| 1 1 0 0] [ 0 0 0 0| 1 0 1 1] [ 1 1 0 0| 1 0 1 0] [ 0 0 0 0| 0 -1 1 1] >>> certificate2.child_keys() (((4, 5, 6, 7, 0), (0, 1, 2, 3)), ((0, 1, 2, 3), (0, 4, 5, 6, 7)))
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 5, 5, sparse=True), [[1, 1, 1, 1, 1], [1, 1, 1, 0, 0], [1, 0, 1, 1, 0], [1, 0, 0, 1, 1], [1, 1, 0, 0, 1]]); M2 M3 = Matrix_cmr_chr_sparse.two_sum(M2, M2, 0, 1); M3 result, certificate = M3.is_totally_unimodular(certificate=True); certificate K33 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 5, 4, sparse=True), [[1, 1, 0, 0], [1, 1, 1, 0], [1, 0, 0,-1], [0, 1, 1, 1], [0, 0, 1, 1]]); K33 K33_dual = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 4, 5, sparse=True), [[1, 1, 1, 0, 0], [1, 1, 0, 1, 0], [0, 1, 0, 1, 1], [0, 0,-1, 1, 1]]); K33_dual M = Matrix_cmr_chr_sparse.two_sum(K33, K33_dual, 0, 0, nonzero_block="bottom_left"); M result1, certificate1 = M.is_totally_unimodular(certificate=True); certificate1 certificate1.summand_matrices() certificate1.block_matrix_form() certificate1.child_keys() M_perm = M.matrix_from_rows_and_columns([4, 6, 5, 7, 0, 1, 2, 3], range(M.ncols())) M_perm result2, certificate2 = M_perm.is_totally_unimodular(certificate=True) certificate2.summand_matrices() certificate2.block_matrix_form() certificate2.child_keys()
- class sage.matrix.seymour_decomposition.UnknownNode[source]¶
Bases:
DecompositionNodeEXAMPLES:
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] sage: node = UnknownNode(matrix(ZZ, [[1, 0, 1], [0, 1, 1]])); node UnknownNode (2×3) sage: node.matrix() [1 0 1] [0 1 1] 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⎠
>>> from sage.all import * >>> 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] >>> node = UnknownNode(matrix(ZZ, [[Integer(1), Integer(0), Integer(1)], [Integer(0), Integer(1), Integer(1)]])); node UnknownNode (2×3) >>> node.matrix() [1 0 1] [0 1 1] >>> 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⎠
from sage.matrix.seymour_decomposition import UnknownNode node = UnknownNode([[1, 1], [0, 1]]); node node.matrix() node = UnknownNode(matrix(ZZ, [[1, 0, 1], [0, 1, 1]])); node node.matrix() node = UnknownNode(matrix(ZZ, [[1, 0, 1], [0, 1, 1]]), row_keys='ab', column_keys=range(3)); node node.matrix() node.morphism()._unicode_art_matrix()From a module morphism:
sage: phi = matrix(ZZ, [[1, 0, 1], [0, 1, 1]], ....: row_keys='ab', column_keys=range(3)); phi Generic morphism: From: Free module generated by {0, 1, 2} over Integer Ring To: Free module generated by {'a', 'b'} over Integer Ring sage: node = UnknownNode(phi); node UnknownNode (2×3) sage: node.matrix() [1 0 1] [0 1 1]
>>> from sage.all import * >>> phi = matrix(ZZ, [[Integer(1), Integer(0), Integer(1)], [Integer(0), Integer(1), Integer(1)]], ... row_keys='ab', column_keys=range(Integer(3))); phi Generic morphism: From: Free module generated by {0, 1, 2} over Integer Ring To: Free module generated by {'a', 'b'} over Integer Ring >>> node = UnknownNode(phi); node UnknownNode (2×3) >>> node.matrix() [1 0 1] [0 1 1]
phi = matrix(ZZ, [[1, 0, 1], [0, 1, 1]], row_keys='ab', column_keys=range(3)); phi node = UnknownNode(phi); node node.matrix()- is_conetwork_matrix(decomposition=False, certificate=False, **kwds)[source]¶
Return whether the matrix
selfover \(\GF{3}\) or \(\QQ\) is a conetwork matrix. If there is some entry not in \(\{-1, 0, 1\}\), returnFalse.EXAMPLES:
sage: from sage.matrix.seymour_decomposition import UnknownNode sage: node = UnknownNode([[1, -1, 0], [0, 1, -1]]); node UnknownNode (2×3) sage: node.matrix() [ 1 -1 0] [ 0 1 -1] sage: node.is_conetwork_matrix() True sage: result, certificate = node.is_conetwork_matrix(certificate=True) sage: graph, forest_edges, coforest_edges = certificate sage: graph Digraph on 4 vertices sage: graph.vertices(sort=True) # the numbers have no meaning [1, 2, 7, 12] sage: graph.edges(sort=True, labels=False) [(2, 1), (2, 7), (7, 1), (7, 12), (12, 1)] sage: forest_edges # indexed by cols of M ((2, 1), (7, 1), (7, 12)) sage: coforest_edges # indexed by rows of M ((2, 7), (12, 1))
>>> from sage.all import * >>> from sage.matrix.seymour_decomposition import UnknownNode >>> node = UnknownNode([[Integer(1), -Integer(1), Integer(0)], [Integer(0), Integer(1), -Integer(1)]]); node UnknownNode (2×3) >>> node.matrix() [ 1 -1 0] [ 0 1 -1] >>> node.is_conetwork_matrix() True >>> result, certificate = node.is_conetwork_matrix(certificate=True) >>> graph, forest_edges, coforest_edges = certificate >>> graph Digraph on 4 vertices >>> graph.vertices(sort=True) # the numbers have no meaning [1, 2, 7, 12] >>> graph.edges(sort=True, labels=False) [(2, 1), (2, 7), (7, 1), (7, 12), (12, 1)] >>> forest_edges # indexed by cols of M ((2, 1), (7, 1), (7, 12)) >>> coforest_edges # indexed by rows of M ((2, 7), (12, 1))
from sage.matrix.seymour_decomposition import UnknownNode node = UnknownNode([[1, -1, 0], [0, 1, -1]]); node node.matrix() node.is_conetwork_matrix() result, certificate = node.is_conetwork_matrix(certificate=True) graph, forest_edges, coforest_edges = certificate graph graph.vertices(sort=True) # the numbers have no meaning graph.edges(sort=True, labels=False) forest_edges # indexed by cols of M coforest_edges # indexed by rows of M
- is_network_matrix(decomposition=False, certificate=False, **kwds)[source]¶
Return whether the matrix
selfover \(\GF{3}\) or \(\QQ\) is a network matrix. If there is some entry not in \(\{-1, 0, 1\}\), returnFalse.EXAMPLES:
sage: from sage.matrix.seymour_decomposition import UnknownNode sage: node = UnknownNode([[1, 0], [-1, 1], [0, -1]]); node UnknownNode (3×2) sage: node.matrix() [ 1 0] [-1 1] [ 0 -1] sage: node.is_network_matrix() True sage: result, certificate = node.is_network_matrix(certificate=True) sage: graph, forest_edges, coforest_edges = certificate sage: graph Digraph on 4 vertices sage: graph.vertices(sort=True) # the numbers have no meaning [1, 2, 7, 12] sage: graph.edges(sort=True, labels=False) [(2, 1), (2, 7), (7, 1), (7, 12), (12, 1)] sage: forest_edges # indexed by rows of M ((2, 1), (7, 1), (7, 12)) sage: coforest_edges # indexed by cols of M ((2, 7), (12, 1))
>>> from sage.all import * >>> from sage.matrix.seymour_decomposition import UnknownNode >>> node = UnknownNode([[Integer(1), Integer(0)], [-Integer(1), Integer(1)], [Integer(0), -Integer(1)]]); node UnknownNode (3×2) >>> node.matrix() [ 1 0] [-1 1] [ 0 -1] >>> node.is_network_matrix() True >>> result, certificate = node.is_network_matrix(certificate=True) >>> graph, forest_edges, coforest_edges = certificate >>> graph Digraph on 4 vertices >>> graph.vertices(sort=True) # the numbers have no meaning [1, 2, 7, 12] >>> graph.edges(sort=True, labels=False) [(2, 1), (2, 7), (7, 1), (7, 12), (12, 1)] >>> forest_edges # indexed by rows of M ((2, 1), (7, 1), (7, 12)) >>> coforest_edges # indexed by cols of M ((2, 7), (12, 1))
from sage.matrix.seymour_decomposition import UnknownNode node = UnknownNode([[1, 0], [-1, 1], [0, -1]]); node node.matrix() node.is_network_matrix() result, certificate = node.is_network_matrix(certificate=True) graph, forest_edges, coforest_edges = certificate graph graph.vertices(sort=True) # the numbers have no meaning graph.edges(sort=True, labels=False) forest_edges # indexed by rows of M coforest_edges # indexed by cols of M
- class sage.matrix.seymour_decomposition.YSumNode[source]¶
Bases:
SumNode- block_matrix_form()[source]¶
Return the block matrix constructed from the Y-sum of children.
EXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: R12 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 6, sparse=True), ....: [[1,0,1,1,0,0],[0,1,1,1,0,0],[1,0,1,0,1,1], ....: [0,-1,0,-1,1,1],[1,0,1,0,1,0],[0,-1,0,-1,0,1]]) sage: R12 [ 1 0 1 1 0 0] [ 0 1 1 1 0 0] [ 1 0 1 0 1 1] [ 0 -1 0 -1 1 1] [ 1 0 1 0 1 0] [ 0 -1 0 -1 0 1] sage: result, certificate = R12.is_totally_unimodular(certificate=True, ....: decompose_strategy="y_pivot") sage: C = certificate.child_nodes()[0]; C YSumNode (6×6) sage: C.matrix() [ 1 0 0 1 -1 -1] [ 0 1 1 1 0 0] [-1 0 1 0 1 1] [ 0 -1 0 -1 1 1] [ 1 0 0 0 0 -1] [ 0 -1 0 -1 0 1] sage: C.summand_matrices() ( [ 0 0 1 1] [-1 1 -1 -1] [ 1 1 1 0] [ 0 1 -1 -1] [ 0 1 0 -1] [ 1 0 1 1] [-1 0 -1 0] [ 0 1 0 -1] [-1 0 -1 -1], [ 1 0 0 1] ) sage: C.row_keys() (r0, r1, c0, r3, r4, r5) sage: C.column_keys() (r2, c1, c2, c3, c4, c5) sage: C.child_keys() (((r0, r1, c0, r3, -r2+r3), (c1, c2, c3, r2)), ((-c1+r0, r0, r3, r4, r5), (c1, r2, c4, c5))) sage: C.block_matrix_form() [ 0 0 1 1 -1 -1] [ 1 1 1 0 0 0] [ 0 1 0 -1 1 1] [-1 0 -1 0 1 1] [ 0 0 0 1 0 -1] [-1 0 -1 0 0 1]
>>> from sage.all import * >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> R12 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(6), Integer(6), sparse=True), ... [[Integer(1),Integer(0),Integer(1),Integer(1),Integer(0),Integer(0)],[Integer(0),Integer(1),Integer(1),Integer(1),Integer(0),Integer(0)],[Integer(1),Integer(0),Integer(1),Integer(0),Integer(1),Integer(1)], ... [Integer(0),-Integer(1),Integer(0),-Integer(1),Integer(1),Integer(1)],[Integer(1),Integer(0),Integer(1),Integer(0),Integer(1),Integer(0)],[Integer(0),-Integer(1),Integer(0),-Integer(1),Integer(0),Integer(1)]]) >>> R12 [ 1 0 1 1 0 0] [ 0 1 1 1 0 0] [ 1 0 1 0 1 1] [ 0 -1 0 -1 1 1] [ 1 0 1 0 1 0] [ 0 -1 0 -1 0 1] >>> result, certificate = R12.is_totally_unimodular(certificate=True, ... decompose_strategy="y_pivot") >>> C = certificate.child_nodes()[Integer(0)]; C YSumNode (6×6) >>> C.matrix() [ 1 0 0 1 -1 -1] [ 0 1 1 1 0 0] [-1 0 1 0 1 1] [ 0 -1 0 -1 1 1] [ 1 0 0 0 0 -1] [ 0 -1 0 -1 0 1] >>> C.summand_matrices() ( [ 0 0 1 1] [-1 1 -1 -1] [ 1 1 1 0] [ 0 1 -1 -1] [ 0 1 0 -1] [ 1 0 1 1] [-1 0 -1 0] [ 0 1 0 -1] [-1 0 -1 -1], [ 1 0 0 1] ) >>> C.row_keys() (r0, r1, c0, r3, r4, r5) >>> C.column_keys() (r2, c1, c2, c3, c4, c5) >>> C.child_keys() (((r0, r1, c0, r3, -r2+r3), (c1, c2, c3, r2)), ((-c1+r0, r0, r3, r4, r5), (c1, r2, c4, c5))) >>> C.block_matrix_form() [ 0 0 1 1 -1 -1] [ 1 1 1 0 0 0] [ 0 1 0 -1 1 1] [-1 0 -1 0 1 1] [ 0 0 0 1 0 -1] [-1 0 -1 0 0 1]
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse R12 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 6, sparse=True), [[1,0,1,1,0,0],[0,1,1,1,0,0],[1,0,1,0,1,1], [0,-1,0,-1,1,1],[1,0,1,0,1,0],[0,-1,0,-1,0,1]]) R12 result, certificate = R12.is_totally_unimodular(certificate=True, decompose_strategy="y_pivot") C = certificate.child_nodes()[0]; C C.matrix() C.summand_matrices() C.row_keys() C.column_keys() C.child_keys() C.block_matrix_form()
- is_concentrated_rank()[source]¶
Return
Falsefor the \(\Delta\)-sum nodeself.concentrated_rankis named after the rank 2 and rank 0 off-diagonal blocks.
- is_distributed_ranks()[source]¶
Return
Truefor the \(\Delta\)-sum nodeself.distributed_ranksis named after the two rank 1 off-diagonal blocks.EXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: R12_large = 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_large.is_totally_unimodular(certificate=True, ....: decompose_strategy="y_pivot") sage: C = certificate.child_nodes()[0]; C YSumNode (9×12) sage: C.is_distributed_ranks() True sage: C.is_concentrated_rank() False
>>> from sage.all import * >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> R12_large = 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_large.is_totally_unimodular(certificate=True, ... decompose_strategy="y_pivot") >>> C = certificate.child_nodes()[Integer(0)]; C YSumNode (9×12) >>> C.is_distributed_ranks() True >>> C.is_concentrated_rank() False
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse R12_large = 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]]) result, certificate = R12_large.is_totally_unimodular(certificate=True, decompose_strategy="y_pivot") C = certificate.child_nodes()[0]; C C.is_distributed_ranks() C.is_concentrated_rank()
- permuted_block_matrix()[source]¶
Return the permutation matrices between the matrix and the block matrix form.
OUTPUT: a tuple
(Prow, BlockMatrix, Pcolumn), whereself.matrix() == Prow * BlockMatrix * Pcolumn, andBlockMatrix == self.block_matrix_form().EXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: R12 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 6, sparse=True), ....: [[1,0,1,1,0,0],[0,1,1,1,0,0],[1,0,1,0,1,1], ....: [0,-1,0,-1,1,1],[1,0,1,0,1,0],[0,-1,0,-1,0,1]]) sage: R12 [ 1 0 1 1 0 0] [ 0 1 1 1 0 0] [ 1 0 1 0 1 1] [ 0 -1 0 -1 1 1] [ 1 0 1 0 1 0] [ 0 -1 0 -1 0 1] sage: result, certificate = R12.is_totally_unimodular(certificate=True, ....: decompose_strategy="y_pivot") sage: C = certificate.child_nodes()[0]; C YSumNode (6×6) sage: C.matrix() [ 1 0 0 1 -1 -1] [ 0 1 1 1 0 0] [-1 0 1 0 1 1] [ 0 -1 0 -1 1 1] [ 1 0 0 0 0 -1] [ 0 -1 0 -1 0 1] sage: C.block_matrix_form() [ 0 0 1 1 -1 -1] [ 1 1 1 0 0 0] [ 0 1 0 -1 1 1] [-1 0 -1 0 1 1] [ 0 0 0 1 0 -1] [-1 0 -1 0 0 1] sage: P_row, block_matrix, P_column = C.permuted_block_matrix() sage: P_row^(-1) * C.matrix() * P_column^(-1) == block_matrix True
>>> from sage.all import * >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> R12 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(6), Integer(6), sparse=True), ... [[Integer(1),Integer(0),Integer(1),Integer(1),Integer(0),Integer(0)],[Integer(0),Integer(1),Integer(1),Integer(1),Integer(0),Integer(0)],[Integer(1),Integer(0),Integer(1),Integer(0),Integer(1),Integer(1)], ... [Integer(0),-Integer(1),Integer(0),-Integer(1),Integer(1),Integer(1)],[Integer(1),Integer(0),Integer(1),Integer(0),Integer(1),Integer(0)],[Integer(0),-Integer(1),Integer(0),-Integer(1),Integer(0),Integer(1)]]) >>> R12 [ 1 0 1 1 0 0] [ 0 1 1 1 0 0] [ 1 0 1 0 1 1] [ 0 -1 0 -1 1 1] [ 1 0 1 0 1 0] [ 0 -1 0 -1 0 1] >>> result, certificate = R12.is_totally_unimodular(certificate=True, ... decompose_strategy="y_pivot") >>> C = certificate.child_nodes()[Integer(0)]; C YSumNode (6×6) >>> C.matrix() [ 1 0 0 1 -1 -1] [ 0 1 1 1 0 0] [-1 0 1 0 1 1] [ 0 -1 0 -1 1 1] [ 1 0 0 0 0 -1] [ 0 -1 0 -1 0 1] >>> C.block_matrix_form() [ 0 0 1 1 -1 -1] [ 1 1 1 0 0 0] [ 0 1 0 -1 1 1] [-1 0 -1 0 1 1] [ 0 0 0 1 0 -1] [-1 0 -1 0 0 1] >>> P_row, block_matrix, P_column = C.permuted_block_matrix() >>> P_row**(-Integer(1)) * C.matrix() * P_column**(-Integer(1)) == block_matrix True
from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse R12 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 6, sparse=True), [[1,0,1,1,0,0],[0,1,1,1,0,0],[1,0,1,0,1,1], [0,-1,0,-1,1,1],[1,0,1,0,1,0],[0,-1,0,-1,0,1]]) R12 result, certificate = R12.is_totally_unimodular(certificate=True, decompose_strategy="y_pivot") C = certificate.child_nodes()[0]; C C.matrix() C.block_matrix_form() P_row, block_matrix, P_column = C.permuted_block_matrix() P_row^(-1) * C.matrix() * P_column^(-1) == block_matrix