Sparse Matrices from the Combinatorial Matrix Recognition Library¶
This module is provided by the pip-installable package passagemath-cmr.
- class sage.matrix.matrix_cmr_sparse.Matrix_cmr_chr_sparse[source]¶
Bases:
Matrix_cmr_sparseSparse matrices with 8-bit integer entries implemented in CMR
EXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 2, 3, sparse=True), ....: [[1, 2, 3], [4, 0, 6]]); M [1 2 3] [4 0 6] sage: M.dict() {(0, 0): 1, (0, 1): 2, (0, 2): 3, (1, 0): 4, (1, 2): 6}
>>> from sage.all import * >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(2), Integer(3), sparse=True), ... [[Integer(1), Integer(2), Integer(3)], [Integer(4), Integer(0), Integer(6)]]); M [1 2 3] [4 0 6] >>> M.dict() {(0, 0): 1, (0, 1): 2, (0, 2): 3, (1, 0): 4, (1, 2): 6}
Matrices of this class are always immutable:
sage: M.is_immutable() True sage: copy(M) is M True sage: deepcopy(M) is M True
>>> from sage.all import * >>> M.is_immutable() True >>> copy(M) is M True >>> deepcopy(M) is M True
This matrix class can only store very small integers:
sage: Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 1, 3, sparse=True), [-128, 0, 127]) [-128 0 127] sage: Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 1, 3, sparse=True), [126, 127, 128]) Traceback (most recent call last): ... OverflowError: value too large to convert to signed char
>>> from sage.all import * >>> Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(1), Integer(3), sparse=True), [-Integer(128), Integer(0), Integer(127)]) [-128 0 127] >>> Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(1), Integer(3), sparse=True), [Integer(126), Integer(127), Integer(128)]) Traceback (most recent call last): ... OverflowError: value too large to convert to signed char
Arithmetic does not preserve the implementation class (even if the numbers would fit):
sage: M2 = M + M; M2 [ 2 4 6] [ 8 0 12] sage: type(M2) <class 'sage.matrix.matrix_integer_sparse.Matrix_integer_sparse'> sage: M * 100 [100 200 300] [400 0 600]
>>> from sage.all import * >>> M2 = M + M; M2 [ 2 4 6] [ 8 0 12] >>> type(M2) <class 'sage.matrix.matrix_integer_sparse.Matrix_integer_sparse'> >>> M * Integer(100) [100 200 300] [400 0 600]
- binary_pivot(row, column)[source]¶
Apply a pivot to
selfand return the resulting matrix.Calculations are done over the binary field.
Suppose a matrix is of the form \(\begin{bmatrix} 1 & c^T \\ b & D\end{bmatrix}\). Then the pivot of the matrix with respect to \(1\) is \(\begin{bmatrix} 1 & c^T \\ b & D - bc^T\end{bmatrix}\).
The terminology “pivot” is defined in [Sch1986], Ch. 19.4.
See also
EXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 10, 10, sparse=True), [ ....: [1, 1, 0, 0, 0, 1, 0, 1, 0, 0], ....: [1, 0, 0, 0, 0, 1, 1, 0, 1, 0], ....: [0, 0, 0, 0, 1, 1, 0, 0, 0, 0], ....: [0, 0, 0, 1, 1, 0, 0, 0, 0, 0], ....: [0, 0, 1, 1, 0, 0, 0, 0, 0, 0], ....: [0, 1, 1, 0, 0, 0, 0, 0, 0, 0], ....: [0, 0, 0, 0, 0, 0, 0, 0, 1, 0], ....: [0, 0, 0, 0, 0, 1, 0, 0, 0, 1], ....: [1, 0, 0, 0, 0, 0, 1, 0, 1, 1], ....: [1, 1, 0, 0, 0, 1, 0, 0, 0, 0] ....: ]); M [1 1 0 0 0 1 0 1 0 0] [1 0 0 0 0 1 1 0 1 0] [0 0 0 0 1 1 0 0 0 0] [0 0 0 1 1 0 0 0 0 0] [0 0 1 1 0 0 0 0 0 0] [0 1 1 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 1 0] [0 0 0 0 0 1 0 0 0 1] [1 0 0 0 0 0 1 0 1 1] [1 1 0 0 0 1 0 0 0 0] sage: M.binary_pivot(0, 0) [1 1 0 0 0 1 0 1 0 0] [1 1 0 0 0 0 1 1 1 0] [0 0 0 0 1 1 0 0 0 0] [0 0 0 1 1 0 0 0 0 0] [0 0 1 1 0 0 0 0 0 0] [0 1 1 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 1 0] [0 0 0 0 0 1 0 0 0 1] [1 1 0 0 0 1 1 1 1 1] [1 0 0 0 0 0 0 1 0 0]
>>> from sage.all import * >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(10), Integer(10), sparse=True), [ ... [Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0), Integer(1), Integer(0), Integer(0)], ... [Integer(1), 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(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(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(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0)], ... [Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(1)], ... [Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0), Integer(1), Integer(1)], ... [Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0)] ... ]); M [1 1 0 0 0 1 0 1 0 0] [1 0 0 0 0 1 1 0 1 0] [0 0 0 0 1 1 0 0 0 0] [0 0 0 1 1 0 0 0 0 0] [0 0 1 1 0 0 0 0 0 0] [0 1 1 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 1 0] [0 0 0 0 0 1 0 0 0 1] [1 0 0 0 0 0 1 0 1 1] [1 1 0 0 0 1 0 0 0 0] >>> M.binary_pivot(Integer(0), Integer(0)) [1 1 0 0 0 1 0 1 0 0] [1 1 0 0 0 0 1 1 1 0] [0 0 0 0 1 1 0 0 0 0] [0 0 0 1 1 0 0 0 0 0] [0 0 1 1 0 0 0 0 0 0] [0 1 1 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 1 0] [0 0 0 0 0 1 0 0 0 1] [1 1 0 0 0 1 1 1 1 1] [1 0 0 0 0 0 0 1 0 0]
- binary_pivots(rows, columns)[source]¶
Apply a sequence of pivots to
selfand return the resulting matrix.Calculations are done over the binary field.
See also
EXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 10, 10, sparse=True), [ ....: [1, 1, 0, 0, 0, 1, 0, 1, 0, 0], ....: [1, 0, 0, 0, 0, 1, 1, 0, 1, 0], ....: [0, 0, 0, 0, 1, 1, 0, 0, 0, 0], ....: [0, 0, 0, 1, 1, 0, 0, 0, 0, 0], ....: [0, 0, 1, 1, 0, 0, 0, 0, 0, 0], ....: [0, 1, 1, 0, 0, 0, 0, 0, 0, 0], ....: [0, 0, 0, 0, 0, 0, 0, 0, 1, 0], ....: [0, 0, 0, 0, 0, 1, 0, 0, 0, 1], ....: [1, 0, 0, 0, 0, 0, 1, 0, 1, 1], ....: [1, 1, 0, 0, 0, 1, 0, 0, 0, 0] ....: ]); M [1 1 0 0 0 1 0 1 0 0] [1 0 0 0 0 1 1 0 1 0] [0 0 0 0 1 1 0 0 0 0] [0 0 0 1 1 0 0 0 0 0] [0 0 1 1 0 0 0 0 0 0] [0 1 1 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 1 0] [0 0 0 0 0 1 0 0 0 1] [1 0 0 0 0 0 1 0 1 1] [1 1 0 0 0 1 0 0 0 0] sage: M.binary_pivots([5, 4, 3, 2], [2, 3, 4, 5]) [1 0 1 1 1 1 0 1 0 0] [1 1 1 1 1 1 1 0 1 0] [0 1 1 1 1 1 0 0 0 0] [0 1 1 1 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 0 0 0 0 0 0 1 0] [0 1 1 1 1 1 0 0 0 1] [1 0 0 0 0 0 1 0 1 1] [1 0 1 1 1 1 0 0 0 0]
>>> from sage.all import * >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(10), Integer(10), sparse=True), [ ... [Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0), Integer(1), Integer(0), Integer(0)], ... [Integer(1), 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(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(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(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0)], ... [Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(1)], ... [Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0), Integer(1), Integer(1)], ... [Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0)] ... ]); M [1 1 0 0 0 1 0 1 0 0] [1 0 0 0 0 1 1 0 1 0] [0 0 0 0 1 1 0 0 0 0] [0 0 0 1 1 0 0 0 0 0] [0 0 1 1 0 0 0 0 0 0] [0 1 1 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 1 0] [0 0 0 0 0 1 0 0 0 1] [1 0 0 0 0 0 1 0 1 1] [1 1 0 0 0 1 0 0 0 0] >>> M.binary_pivots([Integer(5), Integer(4), Integer(3), Integer(2)], [Integer(2), Integer(3), Integer(4), Integer(5)]) [1 0 1 1 1 1 0 1 0 0] [1 1 1 1 1 1 1 0 1 0] [0 1 1 1 1 1 0 0 0 0] [0 1 1 1 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 0 0 0 0 0 0 1 0] [0 1 1 1 1 1 0 0 0 1] [1 0 0 0 0 0 1 0 1 1] [1 0 1 1 1 1 0 0 0 0]
- delta_sum(first_mat, second_mat, first_row=-1, first_columns=[-2, -1], second_row=0, second_columns=[0, 1], algorithm='cmr', sign_verify=False)[source]¶
Return the \(\Delta\)-sum matrix constructed from the two matrices
first_matandsecond_mat.Let \(M_1\) and \(M_2\) denote the matrices given by
first_matandsecond_mat. Iffirst_rowindexes a row vector \(c^T\) andfirst_columnsindexes two column vectors \(a\) offirst_mat, thensecond_rowindexes a row vector \(b\) andsecond_columnsindexes two column vectors \(d\) ofsecond_mat. In this case, the two matrices are\[\begin{split}M_1 = \begin{bmatrix} A & a & a \\ c^T & 0 & \varepsilon \end{bmatrix}, \qquad M_2 = \begin{bmatrix} \varepsilon & 0 & b^T \\ d & d & D \end{bmatrix}.\end{split}\]Then the Seymour/Schrijver 3-sum is the matrix
\[\begin{split}M_1 \oplus_3 M_2 = \begin{bmatrix} A & a b^T \\ d c^T & D \end{bmatrix}.\end{split}\]The terminology “3-sum” originates from Seymour’s decomposition of regular matroids. In the context of totally unimodular matrices, there are different interpretations in the form of matrix operations for \(\begin{bmatrix} A & B \\ C & D \end{bmatrix}\) satisfying \(\rank(B) + \rank(C) = 2\). Three types of 3-sum operations are implemented in CMR: \(\Delta\)-sum, 3-sum, and Y-sum. The \(\Delta\)-sum is referenced in [Sch1986], Chapter 19.4.
For 3-sum, one of \(B\) and \(C\) is a zero matrix, also known as “concentrated_rank”.
For \(\Delta\)-sum and Y-sum, both \(B\) and \(C\) are of rank 1, also known as “distributed_ranks”.
See also
_delta_sum_cmr(),delta_sum_decomposition(),is_delta_sum(),one_sum(),two_sum(),three_sum(),y_sum()INPUT:
first_mat– the first integer matrix \(M_1\)second_mat– the second integer matrix \(M_2\)first_row– the row index of \(c^T\) in \(M_1\)first_columns– the column indices of \(a\) in \(M_1\)second_row– the row index of \(b^T\) in \(M_2\)second_columns– the column indices of \(d\) in \(M_2\)algorithm–"cmr"or"direct"Ifalgorithm="cmr", then use_delta_sum_cmr(); Ifalgorithm="direct", then construct three sum directly. Both options will check the given two matrices and the related indices satisfying the requirements of \(\Delta\)-sum.sign_verify– boolean (default:False); whether to check the sign consistency of \(\varepsilon\). Seeis_delta_sum(),delta_sum_decomposition().
OUTPUT: A
Matrix_cmr_chr_sparseEXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 5, 6, sparse=True), ....: [[1, 1, 0, 0, 0, 0], ....: [0,-1, 0,-1, 1, 1], ....: [0, 0, 1, 0,-1,-1], ....: [0, 1, 0, 1, 1, 1], ....: [1, 0,-1, 1, 0, 1],]); M1 [ 1 1 0 0 0 0] [ 0 -1 0 -1 1 1] [ 0 0 1 0 -1 -1] [ 0 1 0 1 1 1] [ 1 0 -1 1 0 1] sage: M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 5, 6, sparse=True), ....: [[ 1, 0, 1, 1, 1,-1], ....: [-1,-1, 1, 1, 0, 0], ....: [ 0, 0, 0,-1, 0, 1], ....: [ 0, 0, 1, 0,-1, 0], ....: [ 1, 1, 0, 0, 0, 1]]); M2 [ 1 0 1 1 1 -1] [-1 -1 1 1 0 0] [ 0 0 0 -1 0 1] [ 0 0 1 0 -1 0] [ 1 1 0 0 0 1] sage: Matrix_cmr_chr_sparse.delta_sum(M1, M2) [ 1 1 0 0 0 0 0 0] [ 0 -1 0 -1 1 1 1 -1] [ 0 0 1 0 -1 -1 -1 1] [ 0 1 0 1 1 1 1 -1] [-1 0 1 -1 1 1 0 0] [ 0 0 0 0 0 -1 0 1] [ 0 0 0 0 1 0 -1 0] [ 1 0 -1 1 0 0 0 1]
>>> from sage.all import * >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(5), Integer(6), sparse=True), ... [[Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0)], ... [Integer(0),-Integer(1), Integer(0),-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(1), Integer(1), Integer(1)], ... [Integer(1), Integer(0),-Integer(1), Integer(1), Integer(0), Integer(1)],]); M1 [ 1 1 0 0 0 0] [ 0 -1 0 -1 1 1] [ 0 0 1 0 -1 -1] [ 0 1 0 1 1 1] [ 1 0 -1 1 0 1] >>> M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(5), Integer(6), sparse=True), ... [[ Integer(1), Integer(0), Integer(1), Integer(1), Integer(1),-Integer(1)], ... [-Integer(1),-Integer(1), Integer(1), Integer(1), Integer(0), Integer(0)], ... [ Integer(0), Integer(0), Integer(0),-Integer(1), Integer(0), Integer(1)], ... [ Integer(0), Integer(0), Integer(1), Integer(0),-Integer(1), Integer(0)], ... [ Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(1)]]); M2 [ 1 0 1 1 1 -1] [-1 -1 1 1 0 0] [ 0 0 0 -1 0 1] [ 0 0 1 0 -1 0] [ 1 1 0 0 0 1] >>> Matrix_cmr_chr_sparse.delta_sum(M1, M2) [ 1 1 0 0 0 0 0 0] [ 0 -1 0 -1 1 1 1 -1] [ 0 0 1 0 -1 -1 -1 1] [ 0 1 0 1 1 1 1 -1] [-1 0 1 -1 1 1 0 0] [ 0 0 0 0 0 -1 0 1] [ 0 0 0 0 1 0 -1 0] [ 1 0 -1 1 0 0 0 1]
The \(\Delta\)-sum can be computed for any row and column indices:
sage: M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 5, 6, sparse=True), ....: [[1, 1, 0, 0, 0, 0], ....: [1, 0, 1,-1, 1, 0], ....: [0,-1, 1, 0,-1, 1], ....: [0, 0,-1, 1, 0,-1], ....: [0, 1, 1, 0, 1, 1]]); M1 [ 1 1 0 0 0 0] [ 1 0 1 -1 1 0] [ 0 -1 1 0 -1 1] [ 0 0 -1 1 0 -1] [ 0 1 1 0 1 1] sage: M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 5, 6, sparse=True), ....: [[1,-1, 1, 0, 0,-1], ....: [1, 1, 1, 1,-1, 0], ....: [0, 0,-1, 0, 1, 0], ....: [1, 0, 0,-1, 0, 0], ....: [0, 1, 0, 0, 1, 1]]); M2 [ 1 -1 1 0 0 -1] [ 1 1 1 1 -1 0] [ 0 0 -1 0 1 0] [ 1 0 0 -1 0 0] [ 0 1 0 0 1 1] sage: M = M1.delta_sum(M2, 1, [-1, 2], 1, [1, -1]); M [ 1 1 0 0 0 0 0 0] [ 0 -1 0 -1 1 1 1 -1] [ 0 0 1 0 -1 -1 -1 1] [ 0 1 0 1 1 1 1 -1] [-1 0 1 -1 1 1 0 0] [ 0 0 0 0 0 -1 0 1] [ 0 0 0 0 1 0 -1 0] [ 1 0 -1 1 0 0 0 1] sage: N = M1.delta_sum(M2, 1, [-1, 2], 1, [1, -1], algorithm="direct") sage: M == N True
>>> from sage.all import * >>> M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(5), Integer(6), sparse=True), ... [[Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0)], ... [Integer(1), Integer(0), Integer(1),-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(1), Integer(0),-Integer(1)], ... [Integer(0), Integer(1), Integer(1), Integer(0), Integer(1), Integer(1)]]); M1 [ 1 1 0 0 0 0] [ 1 0 1 -1 1 0] [ 0 -1 1 0 -1 1] [ 0 0 -1 1 0 -1] [ 0 1 1 0 1 1] >>> M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(5), Integer(6), sparse=True), ... [[Integer(1),-Integer(1), Integer(1), Integer(0), Integer(0),-Integer(1)], ... [Integer(1), Integer(1), Integer(1), Integer(1),-Integer(1), Integer(0)], ... [Integer(0), Integer(0),-Integer(1), Integer(0), Integer(1), Integer(0)], ... [Integer(1), Integer(0), Integer(0),-Integer(1), Integer(0), Integer(0)], ... [Integer(0), Integer(1), Integer(0), Integer(0), Integer(1), Integer(1)]]); M2 [ 1 -1 1 0 0 -1] [ 1 1 1 1 -1 0] [ 0 0 -1 0 1 0] [ 1 0 0 -1 0 0] [ 0 1 0 0 1 1] >>> M = M1.delta_sum(M2, Integer(1), [-Integer(1), Integer(2)], Integer(1), [Integer(1), -Integer(1)]); M [ 1 1 0 0 0 0 0 0] [ 0 -1 0 -1 1 1 1 -1] [ 0 0 1 0 -1 -1 -1 1] [ 0 1 0 1 1 1 1 -1] [-1 0 1 -1 1 1 0 0] [ 0 0 0 0 0 -1 0 1] [ 0 0 0 0 1 0 -1 0] [ 1 0 -1 1 0 0 0 1] >>> N = M1.delta_sum(M2, Integer(1), [-Integer(1), Integer(2)], Integer(1), [Integer(1), -Integer(1)], algorithm="direct") >>> M == N True
Both algorithm options will check the given two matrices and the related indices satisfying the requirements of \(\Delta\)-sum:
sage: M1.delta_sum(M2, 1, [2, 3], 1, [1, -1]) Traceback (most recent call last): ... RuntimeError: Invalid matrix structure sage: M1.delta_sum(M2, 1, [2, 3], 1, [1, -1], algorithm="direct") Traceback (most recent call last): ... ValueError: The given two matrices and related indices do not satisfy the rule for delta sum! sage: M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 5, 6, sparse=True), ....: [[1,-1, 1, 0, 0,-1], ....: [1,-1, 1, 1,-1, 0], ....: [0, 0,-1, 0, 1, 0], ....: [1, 0, 0,-1, 0, 0], ....: [0, 1, 0, 0, 1, 1]]); M2 [ 1 -1 1 0 0 -1] [ 1 -1 1 1 -1 0] [ 0 0 -1 0 1 0] [ 1 0 0 -1 0 0] [ 0 1 0 0 1 1] sage: M1.delta_sum(M2, 1, [-1, 2], 1, [1, -1]) Traceback (most recent call last): ... RuntimeError: Inconsistent pieces of input sage: M1.delta_sum(M2, 1, [-1, 2], 1, [1, -1], algorithm="direct") Traceback (most recent call last): ... ValueError: the epsilon in the two matrices are inconsistent
>>> from sage.all import * >>> M1.delta_sum(M2, Integer(1), [Integer(2), Integer(3)], Integer(1), [Integer(1), -Integer(1)]) Traceback (most recent call last): ... RuntimeError: Invalid matrix structure >>> M1.delta_sum(M2, Integer(1), [Integer(2), Integer(3)], Integer(1), [Integer(1), -Integer(1)], algorithm="direct") Traceback (most recent call last): ... ValueError: The given two matrices and related indices do not satisfy the rule for delta sum! >>> M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(5), Integer(6), sparse=True), ... [[Integer(1),-Integer(1), Integer(1), Integer(0), Integer(0),-Integer(1)], ... [Integer(1),-Integer(1), Integer(1), Integer(1),-Integer(1), Integer(0)], ... [Integer(0), Integer(0),-Integer(1), Integer(0), Integer(1), Integer(0)], ... [Integer(1), Integer(0), Integer(0),-Integer(1), Integer(0), Integer(0)], ... [Integer(0), Integer(1), Integer(0), Integer(0), Integer(1), Integer(1)]]); M2 [ 1 -1 1 0 0 -1] [ 1 -1 1 1 -1 0] [ 0 0 -1 0 1 0] [ 1 0 0 -1 0 0] [ 0 1 0 0 1 1] >>> M1.delta_sum(M2, Integer(1), [-Integer(1), Integer(2)], Integer(1), [Integer(1), -Integer(1)]) Traceback (most recent call last): ... RuntimeError: Inconsistent pieces of input >>> M1.delta_sum(M2, Integer(1), [-Integer(1), Integer(2)], Integer(1), [Integer(1), -Integer(1)], algorithm="direct") Traceback (most recent call last): ... ValueError: the epsilon in the two matrices are inconsistent
sign_verify=Truewill check the sign consistency:sage: M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 4, sparse=True), ....: [[ 1, 1, 0, 0], ....: [ 1, 0, 1, 1], ....: [ 0, 1, 0, -1]]); sage: M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 4, sparse=True), ....: [[-1, 0, 1, 0], ....: [ 1, 1, 0, 1], ....: [ 0, 0, 1, 1]]); sage: M1.delta_sum(M2, sign_verify=True) [1 1 0 0] [1 0 1 0] [0 1 0 1] [0 0 1 1] sage: M1.delta_sum(M2, algorithm="direct", sign_verify=True) [1 1 0 0] [1 0 1 0] [0 1 0 1] [0 0 1 1] sage: M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 4, sparse=True), ....: [[ 1, 1, 0, 0], ....: [ 1, 0, 1, 1], ....: [ 0, 1, 0, 1]]); sage: M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 4, sparse=True), ....: [[ 1, 0, 1, 0], ....: [ 1, 1, 0, 1], ....: [ 0, 0, 1, 1]]); sage: M1.delta_sum(M2, sign_verify=True) Traceback (most recent call last): ... ValueError: epsilon in first_mat should be -1. epsilon in second_mat should be -1. sage: M1.delta_sum(M2, algorithm="direct", sign_verify=True) Traceback (most recent call last): ... ValueError: epsilon in first_mat should be -1. epsilon in second_mat should be -1.
>>> from sage.all import * >>> M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(3), Integer(4), sparse=True), ... [[ Integer(1), Integer(1), Integer(0), Integer(0)], ... [ Integer(1), Integer(0), Integer(1), Integer(1)], ... [ Integer(0), Integer(1), Integer(0), -Integer(1)]]); >>> M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(3), Integer(4), sparse=True), ... [[-Integer(1), Integer(0), Integer(1), Integer(0)], ... [ Integer(1), Integer(1), Integer(0), Integer(1)], ... [ Integer(0), Integer(0), Integer(1), Integer(1)]]); >>> M1.delta_sum(M2, sign_verify=True) [1 1 0 0] [1 0 1 0] [0 1 0 1] [0 0 1 1] >>> M1.delta_sum(M2, algorithm="direct", sign_verify=True) [1 1 0 0] [1 0 1 0] [0 1 0 1] [0 0 1 1] >>> M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(3), Integer(4), sparse=True), ... [[ Integer(1), Integer(1), Integer(0), Integer(0)], ... [ Integer(1), Integer(0), Integer(1), Integer(1)], ... [ Integer(0), Integer(1), Integer(0), Integer(1)]]); >>> M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(3), Integer(4), sparse=True), ... [[ Integer(1), Integer(0), Integer(1), Integer(0)], ... [ Integer(1), Integer(1), Integer(0), Integer(1)], ... [ Integer(0), Integer(0), Integer(1), Integer(1)]]); >>> M1.delta_sum(M2, sign_verify=True) Traceback (most recent call last): ... ValueError: epsilon in first_mat should be -1. epsilon in second_mat should be -1. >>> M1.delta_sum(M2, algorithm="direct", sign_verify=True) Traceback (most recent call last): ... ValueError: epsilon in first_mat should be -1. epsilon in second_mat should be -1.
- delta_sum_decomposition(A_rows, A_columns)[source]¶
Decompose the matrix into two child matrices using the \(\Delta\)-sum decomposition with specified indices.
Let \(M\) denote the matrix given by
self. Then\[\begin{split}M = \begin{bmatrix} A & a b^T \\ d c^T & D \end{bmatrix},\end{split}\]where \(a, b, c, d\) are vectors and \(A, D\) are submatrices. The two components of the delta sum \(M_1\) and \(M_2\), given by
first_matandsecond_mat, must be of the form\[\begin{split}M_1 = \begin{bmatrix} A & a & a \\ c^T & 0 & \varepsilon \end{bmatrix}, \qquad M_2 = \begin{bmatrix} \varepsilon & 0 & b^T \\ d & d & D \end{bmatrix}.\end{split}\]The value of \(\varepsilon \in \{-1,+1\}\) must be so that there exists a singular submatrix of \(M_1\) with exactly two nonzeros per row and per column that covers the top-left \(\varepsilon\)-entry. Therefore, \(M\) is totally unimodular if and only if both \(M_1\) and \(M_2\) are totally unimodular.
If \(M\) is not totally unimodular, then \(\varepsilon\) may not be unique and the algorithm just finds one such that at least one of \(M_1\) and \(M_2\) is not totally unimodular.
See also
INPUT:
A_rows– list of row indices for the submatrix \(A\)A_columns– list of column indices for the submatrix \(A\)
OUTPUT: A tuple of two
Matrix_cmr_chr_sparseEXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 6, sparse=True), ....: [[1, 1, 0, 0, 0, 0], ....: [0,-1, 0,-1, 1, 1], ....: [0, 0, 1, 0,-1,-1], ....: [0, 1, 0, 1, 1, 1], ....: [1, 0,-1, 1, 0, 1], ....: [1, 0,-1, 1, 1, 1]]); M [ 1 1 0 0 0 0] [ 0 -1 0 -1 1 1] [ 0 0 1 0 -1 -1] [ 0 1 0 1 1 1] [ 1 0 -1 1 0 1] [ 1 0 -1 1 1 1] sage: M1, M2 = M.delta_sum_decomposition([0, 1, 2, 3], [0, 1, 2, 3]); M1 [ 1 1 0 0 0 0] [ 0 -1 0 -1 1 1] [ 0 0 1 0 -1 -1] [ 0 1 0 1 1 1] [ 1 0 -1 1 0 -1] sage: M2 [-1 0 1 1] [ 1 1 0 1] [ 1 1 1 1]
>>> 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(6), sparse=True), ... [[Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0)], ... [Integer(0),-Integer(1), Integer(0),-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(1), Integer(1), Integer(1)], ... [Integer(1), Integer(0),-Integer(1), Integer(1), Integer(0), Integer(1)], ... [Integer(1), Integer(0),-Integer(1), Integer(1), Integer(1), Integer(1)]]); M [ 1 1 0 0 0 0] [ 0 -1 0 -1 1 1] [ 0 0 1 0 -1 -1] [ 0 1 0 1 1 1] [ 1 0 -1 1 0 1] [ 1 0 -1 1 1 1] >>> M1, M2 = M.delta_sum_decomposition([Integer(0), Integer(1), Integer(2), Integer(3)], [Integer(0), Integer(1), Integer(2), Integer(3)]); M1 [ 1 1 0 0 0 0] [ 0 -1 0 -1 1 1] [ 0 0 1 0 -1 -1] [ 0 1 0 1 1 1] [ 1 0 -1 1 0 -1] >>> M2 [-1 0 1 1] [ 1 1 0 1] [ 1 1 1 1]
This is test
DeltasumDecompositionin CMR’stest_separation.cpp:sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 4, 4, sparse=True), ....: [[ 1, 1, 0, 0], ....: [ 1, 0, 1, 0], ....: [ 0, 1, 0, 1], ....: [ 0, 0, 1, 1]]); sage: M1, M2 = M.delta_sum_decomposition([0, 1], [0, 1]); M1 [ 1 1 0 0] [ 1 0 1 1] [ 0 1 0 -1] sage: M2 [-1 0 1 0] [ 1 1 0 1] [ 0 0 1 1] sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 4, 4, sparse=True), ....: [[ 1, 1, 0, 0], ....: [ 1, 0, -1, 0], ....: [ 0, 1, 0, 1], ....: [ 0, 0, 1, 1]]); sage: M1, M2 = M.delta_sum_decomposition([0, 1], [0, 1]); M1 [ 1 1 0 0] [ 1 0 -1 -1] [ 0 1 0 1] sage: M2 [1 0 1 0] [1 1 0 1] [0 0 1 1] sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 4, 4, sparse=True), ....: [[ 1, 1, 0, 0], ....: [ 1, 0, 1, 0], ....: [ 0, -1, 0, 1], ....: [ 0, 0, 1, 1]]); sage: M1, M2 = M.delta_sum_decomposition([0, 1], [0, 1]); M1 [ 1 1 0 0] [ 1 0 1 1] [ 0 -1 0 1] sage: M2 [1 0 1 0] [1 1 0 1] [0 0 1 1] sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 4, 4, sparse=True), ....: [[ 1, 1, 0, 0], ....: [ 1, 0, -1, 0], ....: [ 0, -1, 0, 1], ....: [ 0, 0, 1, 1]]); sage: M1, M2 = M.delta_sum_decomposition([0, 1], [0, 1]); M1 [ 1 1 0 0] [ 1 0 -1 -1] [ 0 -1 0 -1] sage: M2 [-1 0 1 0] [ 1 1 0 1] [ 0 0 1 1]
>>> from sage.all import * >>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(4), Integer(4), sparse=True), ... [[ Integer(1), Integer(1), Integer(0), Integer(0)], ... [ Integer(1), Integer(0), Integer(1), Integer(0)], ... [ Integer(0), Integer(1), Integer(0), Integer(1)], ... [ Integer(0), Integer(0), Integer(1), Integer(1)]]); >>> M1, M2 = M.delta_sum_decomposition([Integer(0), Integer(1)], [Integer(0), Integer(1)]); M1 [ 1 1 0 0] [ 1 0 1 1] [ 0 1 0 -1] >>> M2 [-1 0 1 0] [ 1 1 0 1] [ 0 0 1 1] >>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(4), Integer(4), sparse=True), ... [[ Integer(1), Integer(1), Integer(0), Integer(0)], ... [ Integer(1), Integer(0), -Integer(1), Integer(0)], ... [ Integer(0), Integer(1), Integer(0), Integer(1)], ... [ Integer(0), Integer(0), Integer(1), Integer(1)]]); >>> M1, M2 = M.delta_sum_decomposition([Integer(0), Integer(1)], [Integer(0), Integer(1)]); M1 [ 1 1 0 0] [ 1 0 -1 -1] [ 0 1 0 1] >>> M2 [1 0 1 0] [1 1 0 1] [0 0 1 1] >>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(4), Integer(4), sparse=True), ... [[ Integer(1), Integer(1), Integer(0), Integer(0)], ... [ Integer(1), Integer(0), Integer(1), Integer(0)], ... [ Integer(0), -Integer(1), Integer(0), Integer(1)], ... [ Integer(0), Integer(0), Integer(1), Integer(1)]]); >>> M1, M2 = M.delta_sum_decomposition([Integer(0), Integer(1)], [Integer(0), Integer(1)]); M1 [ 1 1 0 0] [ 1 0 1 1] [ 0 -1 0 1] >>> M2 [1 0 1 0] [1 1 0 1] [0 0 1 1] >>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(4), Integer(4), sparse=True), ... [[ Integer(1), Integer(1), Integer(0), Integer(0)], ... [ Integer(1), Integer(0), -Integer(1), Integer(0)], ... [ Integer(0), -Integer(1), Integer(0), Integer(1)], ... [ Integer(0), Integer(0), Integer(1), Integer(1)]]); >>> M1, M2 = M.delta_sum_decomposition([Integer(0), Integer(1)], [Integer(0), Integer(1)]); M1 [ 1 1 0 0] [ 1 0 -1 -1] [ 0 -1 0 -1] >>> M2 [-1 0 1 0] [ 1 1 0 1] [ 0 0 1 1]
- equimodulus(time_limit=60.0)[source]¶
Return the integer \(k\) such that
selfis equimodular with determinant gcd \(k\).A matrix \(M\) of rank \(r\) is equimodular with determinant gcd \(k\) if the following two conditions are satisfied:
for some column basis \(B\) of \(M\), the greatest common divisor of the determinants of all \(r\)-by-\(r\) submatrices of \(B\) is \(k\);
the matrix \(X\) such that \(M=BX\) is totally unimodular.
OUTPUT:
k:selfis equimodular with determinant gcd \(k\)None:selfis not equimodular for any \(k\)
See also
EXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 3, sparse=True), ....: [[1, 0, 1], [0, 1, 1], [1, 2, 3]]); M [1 0 1] [0 1 1] [1 2 3] sage: M.equimodulus() 1 sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 2, 3, sparse=True), ....: [[1, 1, 1], [0, 1, 3]]); M [1 1 1] [0 1 3] sage: M.equimodulus()
>>> 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(3), sparse=True), ... [[Integer(1), Integer(0), Integer(1)], [Integer(0), Integer(1), Integer(1)], [Integer(1), Integer(2), Integer(3)]]); M [1 0 1] [0 1 1] [1 2 3] >>> M.equimodulus() 1 >>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(2), Integer(3), sparse=True), ... [[Integer(1), Integer(1), Integer(1)], [Integer(0), Integer(1), Integer(3)]]); M [1 1 1] [0 1 3] >>> M.equimodulus()
- is_conetwork_matrix(time_limit=60.0, certificate=False, row_keys=None, column_keys=None)[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.A matrix is conetwork if and only if its transpose is network.
See also
EXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 4, 9, sparse=True), ....: [[1, 0, 0, 0, 1, -1, 1, 0, 0], ....: [0, 1, 0, 0, 0, 1, -1, 1, 0], ....: [0, 0, 1, 0, 0, 0, 1, -1, 1], ....: [0, 0, 0, 1, 1, 0, 0, 1, -1]]); M [ 1 0 0 0 1 -1 1 0 0] [ 0 1 0 0 0 1 -1 1 0] [ 0 0 1 0 0 0 1 -1 1] [ 0 0 0 1 1 0 0 1 -1] sage: M.is_conetwork_matrix() True sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: K33 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 5, 4, sparse=True), ....: [[-1, -1, -1, -1], ....: [ 1, 1, 0, 0], ....: [ 0, 0, 1, 1], ....: [ 1, 0, 1, 0], ....: [ 0, 1, 0, 1]]); K33 [-1 -1 -1 -1] [ 1 1 0 0] [ 0 0 1 1] [ 1 0 1 0] [ 0 1 0 1] sage: K33.is_conetwork_matrix() False sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: C1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 4, 5, sparse=True), ....: [[1, 0, 1, 0, 0], ....: [0, 1, 0, 1, 0], ....: [1, 1, 0, 0, 1], ....: [0, 0,-1,-1, 1]]) sage: C1.is_conetwork_matrix(certificate=True) (True, (Digraph on 6 vertices, ((4, 5), (2, 3), (5, 0), (1, 2), (5, 2)), ((4, 0), (1, 3), (4, 3), (0, 1)))) sage: C2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 5, 4, sparse=True), ....: [[1, 1, 0, 0], ....: [1, 0, 1, 0], ....: [1, 0, 0, 1], ....: [0,-1, 1, 0], ....: [0,-1, 0, 1]]) sage: C2.is_conetwork_matrix(certificate=True) (True, (Digraph on 5 vertices, ((3, 4), (4, 0), (4, 1), (4, 2)), ((3, 0), (3, 1), (3, 2), (0, 1), (0, 2)))) sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: C3 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 3, sparse=True), ....: [[1, 1, 0], ....: [1, 0, 1], ....: [0, 1, 1]]); C3 [1 1 0] [1 0 1] [0 1 1] sage: result, certificate = C3.is_conetwork_matrix(certificate=True) sage: result False
>>> 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(9), sparse=True), ... [[Integer(1), Integer(0), Integer(0), Integer(0), Integer(1), -Integer(1), Integer(1), Integer(0), Integer(0)], ... [Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(1), -Integer(1), Integer(1), Integer(0)], ... [Integer(0), Integer(0), 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(0), Integer(0), Integer(1), -Integer(1)]]); M [ 1 0 0 0 1 -1 1 0 0] [ 0 1 0 0 0 1 -1 1 0] [ 0 0 1 0 0 0 1 -1 1] [ 0 0 0 1 1 0 0 1 -1] >>> M.is_conetwork_matrix() True >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> K33 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(5), Integer(4), sparse=True), ... [[-Integer(1), -Integer(1), -Integer(1), -Integer(1)], ... [ Integer(1), Integer(1), Integer(0), Integer(0)], ... [ Integer(0), Integer(0), Integer(1), Integer(1)], ... [ Integer(1), Integer(0), Integer(1), Integer(0)], ... [ Integer(0), Integer(1), Integer(0), Integer(1)]]); K33 [-1 -1 -1 -1] [ 1 1 0 0] [ 0 0 1 1] [ 1 0 1 0] [ 0 1 0 1] >>> K33.is_conetwork_matrix() False >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> C1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(4), Integer(5), sparse=True), ... [[Integer(1), Integer(0), Integer(1), Integer(0), Integer(0)], ... [Integer(0), Integer(1), Integer(0), Integer(1), Integer(0)], ... [Integer(1), Integer(1), Integer(0), Integer(0), Integer(1)], ... [Integer(0), Integer(0),-Integer(1),-Integer(1), Integer(1)]]) >>> C1.is_conetwork_matrix(certificate=True) (True, (Digraph on 6 vertices, ((4, 5), (2, 3), (5, 0), (1, 2), (5, 2)), ((4, 0), (1, 3), (4, 3), (0, 1)))) >>> C2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(5), Integer(4), sparse=True), ... [[Integer(1), Integer(1), Integer(0), Integer(0)], ... [Integer(1), Integer(0), 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(0), Integer(1)]]) >>> C2.is_conetwork_matrix(certificate=True) (True, (Digraph on 5 vertices, ((3, 4), (4, 0), (4, 1), (4, 2)), ((3, 0), (3, 1), (3, 2), (0, 1), (0, 2)))) >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> C3 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(3), Integer(3), sparse=True), ... [[Integer(1), Integer(1), Integer(0)], ... [Integer(1), Integer(0), Integer(1)], ... [Integer(0), Integer(1), Integer(1)]]); C3 [1 1 0] [1 0 1] [0 1 1] >>> result, certificate = C3.is_conetwork_matrix(certificate=True) >>> result False
- is_delta_sum(three_sum_mat, first_mat, second_mat, first_row=-1, first_columns=[-2, -1], second_row=0, second_columns=[0, 1], sign_verify=True)[source]¶
Check whether
first_matandsecond_matformthree_sum_matvia the \(\Delta\)-sum operation. Ifsign_verify=True, also check whether the \(\Delta\)-sum satisfies thatthree_sum_matis totally unimodular, if and only if,first_matandsecond_matare both totally unimodular.Let \(M_1\) and \(M_2\) denote the matrices given by
first_matandsecond_mat. Iffirst_rowindexes a row vector \(c^T\) andfirst_columnsindexes two column vectors \(a\) offirst_mat, thensecond_rowindexes a row vector \(b\) andsecond_columnsindexes two column vectors \(d\) ofsecond_mat. In this case, the matrices are\[\begin{split}M_1 = \begin{bmatrix} A & a & a \\ c^T & 0 & \varepsilon \end{bmatrix}, \qquad M_2 = \begin{bmatrix} \varepsilon & 0 & b^T \\ d & d & D \end{bmatrix}.\end{split}\]Then the Seymour/Schrijver 3-sum is the matrix
\[\begin{split}M_1 \oplus_3 M_2 = \begin{bmatrix} A & a b^T \\ d c^T & D \end{bmatrix}.\end{split}\]The value of \(\varepsilon \in \{-1,+1\}\) must be so that there exists a singular submatrix of \(M_1\) with exactly two nonzeros per row and per column that covers the top-left \(\varepsilon\)-entry.
The signs of \(\varepsilon\) are determined by a shortest path between two sets of vertices in the bipartite graph, where the sets of vertices corresponding to the nonzero row and column indices of \(c^T\), \(a\), and the bipartite graph consists of vertices corresponding to the rows and columns of \(M\), and edges corresponding to the nonzero entry. between the rows and columns of \(M\), see [Sch1986], Ch. 20.3.
If you don’t know the indices, please use
is_totally_unimodular().INPUT:
three_sum_mat– the large integer matrix \(M\)first_mat– the first integer matrix \(M_1\)second_mat– the second integer matrix \(M_2\)first_row– the row index of \(c^T\) in \(M_1\)first_columns– the column indices of \(a\) in \(M_1\)second_row– the row index of \(b^T\) in \(M_2\)second_columns– the column indices of \(d\) in \(M_2\)sign_verify– boolean (default:True); whether to check the sign correctness of \(\varepsilon\).
OUTPUT: boolean, or (boolean, string)
If it is
Falseonly because of the sign, then also output the correct sign.EXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 5, 6, sparse=True), ....: [[1, 1, 0, 0, 0, 0], ....: [0,-1, 0,-1, 1, 1], ....: [0, 0, 1, 0,-1,-1], ....: [0, 1, 0, 1, 1, 1], ....: [1, 0,-1, 1, 0, 1],]); M1 [ 1 1 0 0 0 0] [ 0 -1 0 -1 1 1] [ 0 0 1 0 -1 -1] [ 0 1 0 1 1 1] [ 1 0 -1 1 0 1] sage: M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 5, 6, sparse=True), ....: [[ 1, 0, 1, 1, 1,-1], ....: [-1,-1, 1, 1, 0, 0], ....: [ 0, 0, 0,-1, 0, 1], ....: [ 0, 0, 1, 0,-1, 0], ....: [ 1, 1, 0, 0, 0, 1]]); M2 [ 1 0 1 1 1 -1] [-1 -1 1 1 0 0] [ 0 0 0 -1 0 1] [ 0 0 1 0 -1 0] [ 1 1 0 0 0 1] sage: M = Matrix_cmr_chr_sparse.delta_sum(M1, M2); M [ 1 1 0 0 0 0 0 0] [ 0 -1 0 -1 1 1 1 -1] [ 0 0 1 0 -1 -1 -1 1] [ 0 1 0 1 1 1 1 -1] [-1 0 1 -1 1 1 0 0] [ 0 0 0 0 0 -1 0 1] [ 0 0 0 0 1 0 -1 0] [ 1 0 -1 1 0 0 0 1] sage: M.is_delta_sum(M1, M2, sign_verify=False) True sage: M.is_delta_sum(M1, M2) True sage: M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 4, 5, sparse=True), ....: [[ 0, 0, 1,-1,-1], ....: [ 1, 1, 1, 0, 0], ....: [ 0, 1, 0, 1, 1], ....: [-1, 0,-1, 0, 1]]); M1 [ 0 0 1 -1 -1] [ 1 1 1 0 0] [ 0 1 0 1 1] [-1 0 -1 0 1] sage: M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 4, 5, sparse=True), ....: [[ 1, 0, 1,-1, 0], ....: [ 0, 0, 1, 0, 1], ....: [-1,-1, 0, 1, 1], ....: [-1,-1, 0, 0, 1]]); M2 [ 1 0 1 -1 0] [ 0 0 1 0 1] [-1 -1 0 1 1] [-1 -1 0 0 1] sage: M = Matrix_cmr_chr_sparse.delta_sum(M1, M2); M [ 0 0 1 -1 1 0] [ 1 1 1 0 0 0] [ 0 1 0 1 -1 0] [ 0 0 0 1 0 1] [ 1 0 1 0 1 1] [ 1 0 1 0 0 1] sage: M.is_delta_sum(M1, M2, sign_verify=False) True sage: Matrix_cmr_chr_sparse.is_delta_sum(M, M1, M2) (False, 'epsilon in first_mat should be -1. epsilon in second_mat should be -1. ') sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 4, 4, sparse=True), ....: [[ 1, 1, 0, 0], ....: [ 1, 0, 1, 0], ....: [ 0, 1, 0, 1], ....: [ 0, 0, 1, 1]]); sage: M1, M2 = M.delta_sum_decomposition([0, 1], [0, 1]); M1 [ 1 1 0 0] [ 1 0 1 1] [ 0 1 0 -1] sage: M2 [-1 0 1 0] [ 1 1 0 1] [ 0 0 1 1] sage: Matrix_cmr_chr_sparse.is_delta_sum(M, M1, M2) True
>>> from sage.all import * >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(5), Integer(6), sparse=True), ... [[Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0)], ... [Integer(0),-Integer(1), Integer(0),-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(1), Integer(1), Integer(1)], ... [Integer(1), Integer(0),-Integer(1), Integer(1), Integer(0), Integer(1)],]); M1 [ 1 1 0 0 0 0] [ 0 -1 0 -1 1 1] [ 0 0 1 0 -1 -1] [ 0 1 0 1 1 1] [ 1 0 -1 1 0 1] >>> M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(5), Integer(6), sparse=True), ... [[ Integer(1), Integer(0), Integer(1), Integer(1), Integer(1),-Integer(1)], ... [-Integer(1),-Integer(1), Integer(1), Integer(1), Integer(0), Integer(0)], ... [ Integer(0), Integer(0), Integer(0),-Integer(1), Integer(0), Integer(1)], ... [ Integer(0), Integer(0), Integer(1), Integer(0),-Integer(1), Integer(0)], ... [ Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(1)]]); M2 [ 1 0 1 1 1 -1] [-1 -1 1 1 0 0] [ 0 0 0 -1 0 1] [ 0 0 1 0 -1 0] [ 1 1 0 0 0 1] >>> M = Matrix_cmr_chr_sparse.delta_sum(M1, M2); M [ 1 1 0 0 0 0 0 0] [ 0 -1 0 -1 1 1 1 -1] [ 0 0 1 0 -1 -1 -1 1] [ 0 1 0 1 1 1 1 -1] [-1 0 1 -1 1 1 0 0] [ 0 0 0 0 0 -1 0 1] [ 0 0 0 0 1 0 -1 0] [ 1 0 -1 1 0 0 0 1] >>> M.is_delta_sum(M1, M2, sign_verify=False) True >>> M.is_delta_sum(M1, M2) True >>> M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(4), Integer(5), sparse=True), ... [[ Integer(0), Integer(0), Integer(1),-Integer(1),-Integer(1)], ... [ Integer(1), Integer(1), Integer(1), Integer(0), Integer(0)], ... [ Integer(0), Integer(1), Integer(0), Integer(1), Integer(1)], ... [-Integer(1), Integer(0),-Integer(1), Integer(0), Integer(1)]]); M1 [ 0 0 1 -1 -1] [ 1 1 1 0 0] [ 0 1 0 1 1] [-1 0 -1 0 1] >>> M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(4), Integer(5), sparse=True), ... [[ Integer(1), Integer(0), Integer(1),-Integer(1), Integer(0)], ... [ Integer(0), Integer(0), Integer(1), Integer(0), Integer(1)], ... [-Integer(1),-Integer(1), Integer(0), Integer(1), Integer(1)], ... [-Integer(1),-Integer(1), Integer(0), Integer(0), Integer(1)]]); M2 [ 1 0 1 -1 0] [ 0 0 1 0 1] [-1 -1 0 1 1] [-1 -1 0 0 1] >>> M = Matrix_cmr_chr_sparse.delta_sum(M1, M2); M [ 0 0 1 -1 1 0] [ 1 1 1 0 0 0] [ 0 1 0 1 -1 0] [ 0 0 0 1 0 1] [ 1 0 1 0 1 1] [ 1 0 1 0 0 1] >>> M.is_delta_sum(M1, M2, sign_verify=False) True >>> Matrix_cmr_chr_sparse.is_delta_sum(M, M1, M2) (False, 'epsilon in first_mat should be -1. epsilon in second_mat should be -1. ') >>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(4), Integer(4), sparse=True), ... [[ Integer(1), Integer(1), Integer(0), Integer(0)], ... [ Integer(1), Integer(0), Integer(1), Integer(0)], ... [ Integer(0), Integer(1), Integer(0), Integer(1)], ... [ Integer(0), Integer(0), Integer(1), Integer(1)]]); >>> M1, M2 = M.delta_sum_decomposition([Integer(0), Integer(1)], [Integer(0), Integer(1)]); M1 [ 1 1 0 0] [ 1 0 1 1] [ 0 1 0 -1] >>> M2 [-1 0 1 0] [ 1 1 0 1] [ 0 0 1 1] >>> Matrix_cmr_chr_sparse.is_delta_sum(M, M1, M2) True
- is_k_equimodular(k, time_limit=60.0)[source]¶
Return whether
selfis equimodular with determinant gcd \(k\).A matrix \(M\) of rank \(r\) is \(k\)-equimodular if the following two conditions are satisfied:
for some column basis \(B\) of \(M\), the greatest common divisor of the determinants of all \(r\)-by-\(r\) submatrices of \(B\) is \(k\);
the matrix \(X\) such that \(M=BX\) is totally unimodular.
If the matrix has full row rank, it is \(k\)-equimodular if every full rank minor of the matrix has determinant \(0,\pm k\).
Note
In parts of the literature, a matrix with the above properties is called strictly \(k\)-modular.
EXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 3, sparse=True), ....: [[1, 0, 1], [0, 1, 1], [1, 2, 3]]); M [1 0 1] [0 1 1] [1 2 3] sage: M.is_k_equimodular(1) True sage: M.is_k_equimodular(2) False sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 2, 3, sparse=True), ....: [[1, 1, 1], [0, 1, 3]]); M [1 1 1] [0 1 3] sage: M.is_k_equimodular(1) 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(3), sparse=True), ... [[Integer(1), Integer(0), Integer(1)], [Integer(0), Integer(1), Integer(1)], [Integer(1), Integer(2), Integer(3)]]); M [1 0 1] [0 1 1] [1 2 3] >>> M.is_k_equimodular(Integer(1)) True >>> M.is_k_equimodular(Integer(2)) False >>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(2), Integer(3), sparse=True), ... [[Integer(1), Integer(1), Integer(1)], [Integer(0), Integer(1), Integer(3)]]); M [1 1 1] [0 1 3] >>> M.is_k_equimodular(Integer(1)) False
- is_network_matrix(time_limit=60.0, certificate=False, row_keys=None, column_keys=None)[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.Let \(D = (V,A)\) be a digraph and let \(T\) be an (arbitrarily) directed spanning forest of the underlying undirected graph. The matrix \(M(D,T) \in \{-1,0,1\}^{T \times (A \setminus T)}\) defined via
\[\begin{split}M(D,T)_{a,(v,w)} := \begin{cases} +1 & \text{if the unique $v$-$w$-path in $T$ passes through $a$ forwardly}, \\ -1 & \text{if the unique $v$-$w$-path in $T$ passes through $a$ backwardly}, \\ 0 & \text{otherwise} \end{cases}\end{split}\]is called the network matrix of \(D\) with respect to \(T\). A matrix \(M\) is called network matrix if there exists a digraph \(D\) with a directed spanning forest \(T\) such that \(M = M(D,T)\). Moreover, \(M\) is called conetwork matrix if \(M^T\) is a network matrix.
ALGORITHM:
The implemented recognition algorithm first tests the binary matroid of the support matrix of \(M\) for being graphic and uses camion for testing whether \(M\) is signed correctly.
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], [2, 1], [0, -1]]); M [ 1 0] [ 2 1] [ 0 -1] sage: M.is_network_matrix() False 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: M.is_network_matrix() True sage: result, certificate = M.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)) sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: K33 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 5, 4, sparse=True), ....: [[-1, -1, -1, -1], ....: [ 1, 1, 0, 0], ....: [ 0, 0, 1, 1], ....: [ 1, 0, 1, 0], ....: [ 0, 1, 0, 1]]); K33 [-1 -1 -1 -1] [ 1 1 0 0] [ 0 0 1 1] [ 1 0 1 0] [ 0 1 0 1] sage: K33.is_network_matrix() True
>>> 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(2), Integer(1)], [Integer(0), -Integer(1)]]); M [ 1 0] [ 2 1] [ 0 -1] >>> M.is_network_matrix() False >>> 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] >>> M.is_network_matrix() True >>> result, certificate = M.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.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> K33 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(5), Integer(4), sparse=True), ... [[-Integer(1), -Integer(1), -Integer(1), -Integer(1)], ... [ Integer(1), Integer(1), Integer(0), Integer(0)], ... [ Integer(0), Integer(0), Integer(1), Integer(1)], ... [ Integer(1), Integer(0), Integer(1), Integer(0)], ... [ Integer(0), Integer(1), Integer(0), Integer(1)]]); K33 [-1 -1 -1 -1] [ 1 1 0 0] [ 0 0 1 1] [ 1 0 1 0] [ 0 1 0 1] >>> K33.is_network_matrix() True
This is test
Basicin CMR’stest_network.cpp: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: list(digraph.edges(sort=True)) [(0, 6, None), (0, 8, None), (3, 4, None), (3, 8, None), (3, 9, None), (4, 0, None), (4, 6, None), (4, 9, None), (5, 3, None), (5, 4, None), (5, 6, None), (9, 0, None), (9, 8, None)] sage: digraph.plot(edge_colors={'red': forest_arcs}) # needs sage.plot Graphics object consisting of 21 graphics primitives
>>> 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 >>> list(digraph.edges(sort=True)) [(0, 6, None), (0, 8, None), (3, 4, None), (3, 8, None), (3, 9, None), (4, 0, None), (4, 6, None), (4, 9, None), (5, 3, None), (5, 4, None), (5, 6, None), (9, 0, None), (9, 8, None)] >>> digraph.plot(edge_colors={'red': forest_arcs}) # needs sage.plot Graphics object consisting of 21 graphics primitives
- is_strongly_k_equimodular(k, time_limit=60.0)[source]¶
Return whether
selfis strongly \(k\)-equimodular.A matrix is strongly \(k\)-equimodular if
selfandself.transpose()are both \(k\)-equimodular.EXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 3, sparse=True), ....: [[1, 0, 1], [0, 1, 1], [1, 2, 3]]); M [1 0 1] [0 1 1] [1 2 3] sage: M.is_strongly_k_equimodular(1) False sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 2, 3, sparse=True), ....: [[1, 0, 0], [0, 1, 0]]); M [1 0 0] [0 1 0] sage: M.is_strongly_k_equimodular(1) True
>>> 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(3), sparse=True), ... [[Integer(1), Integer(0), Integer(1)], [Integer(0), Integer(1), Integer(1)], [Integer(1), Integer(2), Integer(3)]]); M [1 0 1] [0 1 1] [1 2 3] >>> M.is_strongly_k_equimodular(Integer(1)) False >>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(2), Integer(3), sparse=True), ... [[Integer(1), Integer(0), Integer(0)], [Integer(0), Integer(1), Integer(0)]]); M [1 0 0] [0 1 0] >>> M.is_strongly_k_equimodular(Integer(1)) True
- is_strongly_unimodular(time_limit=60.0)[source]¶
Return whether
selfis a strongly unimodular matrix.A matrix is strongly unimodular if
selfandself.transpose()are both unimodular.See also
EXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 3, sparse=True), ....: [[1, 0, 1], [0, 1, 1], [1, 2, 3]]); M [1 0 1] [0 1 1] [1 2 3] sage: M.is_unimodular() True sage: M.is_strongly_unimodular() False sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 2, 3, sparse=True), ....: [[1, 0, 0], [0, 1, 0]]); M [1 0 0] [0 1 0] sage: M.is_strongly_unimodular() True
>>> 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(3), sparse=True), ... [[Integer(1), Integer(0), Integer(1)], [Integer(0), Integer(1), Integer(1)], [Integer(1), Integer(2), Integer(3)]]); M [1 0 1] [0 1 1] [1 2 3] >>> M.is_unimodular() True >>> M.is_strongly_unimodular() False >>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(2), Integer(3), sparse=True), ... [[Integer(1), Integer(0), Integer(0)], [Integer(0), Integer(1), Integer(0)]]); M [1 0 0] [0 1 0] >>> M.is_strongly_unimodular() True
- is_three_sum(three_sum_mat, first_mat, second_mat, first_rows=[-2, -1], first_column=-1, first_intersection_columns=[-3, -2], second_row=0, second_columns=[0, 1], second_intersection_rows=[1, 2], sign_verify=True)[source]¶
Check whether
first_matandsecond_matformthree_sum_matvia the 3-sum operation with the given special rows and columns. Ifsign_verify=True, also check whether the 3-sum satisfies thatthree_sum_matis totally unimodular, if and only if,first_matandsecond_matare both totally unimodular.Let \(M\) denote the matrix given by
three_sum_mat. Then\[\begin{split}M = \begin{bmatrix} A & 0 \\ C & D \end{bmatrix},\end{split}\]where \(\rank(C) = 2\). The two components \(M_1\) and \(M_2\) of the 3-sum, given by
first_matandsecond_mat, must be of the form\[\begin{split}M_1 = \begin{bmatrix} A & 0 \\ C_{i,\star} & 1 \\ C_{j,\star} & \beta \end{bmatrix}, \qquad M_2 = \begin{bmatrix} \gamma & 1 & 0^T \\ C_{\star,k} & C_{\star,\ell} & D \end{bmatrix},\end{split}\]where \(\beta \in \{-1,+1 \}\) and \(\gamma \in \{ -1,+1 \}\) such that the matrix
\[\begin{split}N = \begin{bmatrix} \gamma & 1 & 0 \\ C_{i,k} & C_{i,\ell} & 1 \\ C_{j,k} & C_{j,\ell} & \beta \end{bmatrix}\end{split}\]is totally unimodular.
The indices in
first_intersection_columnsindicate the columns of \(M_1\) that shall correspond to \(C_{\star,k}\) and \(C_{\star,\ell}\), respectively. Similarly, the indices insecond_intersection_rowsindicate the rows of \(M_2\) that shall correspond to \(C_{i,\star}\) and \(C_{j,\star}\), respectively.The value of \(\beta \in \{-1,+1\}\) must be so that there exists a singular submatrix of \(M_1\) with exactly two nonzeros per row and per column that covers the bottom-right \(\beta\)-entry.
If you don’t know the indices, please use
is_totally_unimodular().INPUT:
three_sum_mat– the large integer matrix \(M\)first_mat– the first integer matrix \(M_1\)second_mat– the second integer matrix \(M_2\)first_rows– the indices of rows \(a_1^T\) and \(a_2^T\) in \(M_1\)first_column– the index of the extra column in \(M_1\)first_intersection_columns– the indices of columns \(k\) and \(\ell\)second_row– the index of the extra row in \(M_2\)second_columns– the indices of columns \(b_1\) and \(b_2\) in \(M_2\)second_intersection_rows– the indices of rows \(i\) and \(j\)sign_verify– boolean (default:True); whether to check the sign consistency of \(\beta\) and \(\gamma\).
OUTPUT: boolean, or (boolean, string)
The string is the error message.
EXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 5, 6, sparse=True), ....: [[1, 1, 0, 0, 0, 0], ....: [0, 0,-1, 1, 0, 0], ....: [0, 1, 1, 0, 1, 0], ....: [1, 0, 1,-1, 1, 1], ....: [0,-1, 1, 0,-1, 1]]); M1 [ 1 1 0 0 0 0] [ 0 0 -1 1 0 0] [ 0 1 1 0 1 0] [ 1 0 1 -1 1 1] [ 0 -1 1 0 -1 1] sage: M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 5, sparse=True), ....: [[ 1,-1, 0, 0, 0], ....: [ 1, 0, 1,-1, 0], ....: [ 1,-1, 1, 1, 1], ....: [-1, 1, 0, 0, 0], ....: [ 0, 0, 1, 0,-1], ....: [ 0, 1, 0, 1, 0]]); M2 [ 1 -1 0 0 0] [ 1 0 1 -1 0] [ 1 -1 1 1 1] [-1 1 0 0 0] [ 0 0 1 0 -1] [ 0 1 0 1 0] sage: M = Matrix_cmr_chr_sparse.three_sum(M1, M2, first_intersection_columns=[2,1]); M [ 1 1 0 0 0 0 0 0] [ 0 0 -1 1 0 0 0 0] [ 0 1 1 0 1 0 0 0] [ 1 0 1 -1 1 1 -1 0] [ 0 -1 1 0 -1 1 1 1] [ 0 1 -1 0 1 0 0 0] [ 0 0 0 0 0 1 0 -1] [ 1 1 0 -1 2 0 1 0] sage: M.is_three_sum(M1, M2, first_intersection_columns=[2, 1], sign_verify=False) True sage: M.is_three_sum(M1, M2, first_intersection_columns=[2, 1]) True sage: M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 4, 5, sparse=True), ....: [[ 1, 0, 1, 1, 0], ....: [ 0, 1, 1, 1, 0], ....: [ 1, 0, 1, 0, 1], ....: [ 0,-1, 0,-1, 1]]); M1 [ 1 0 1 1 0] [ 0 1 1 1 0] [ 1 0 1 0 1] [ 0 -1 0 -1 1] sage: M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 5, 4, sparse=True), ....: [[ 1, 1, 0, 0], ....: [ 1, 0, 1, 1], ....: [ 0,-1, 1, 1], ....: [ 1, 0, 1, 0], ....: [ 0,-1, 0, 1]]); M2 [ 1 1 0 0] [ 1 0 1 1] [ 0 -1 1 1] [ 1 0 1 0] [ 0 -1 0 1] sage: M = Matrix_cmr_chr_sparse.three_sum(M1, M2); M [ 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: Matrix_cmr_chr_sparse.is_three_sum(M, M1, M2) True sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 6, sparse=True), ....: [[ 0, 1, -1, 0, 0, 0], ....: [ 0, 0, 1, 1, 0, 0], ....: [ 1, 0, 0, 1, 0, 0], ....: [ 0, 0, 0, 0, 1, 1], ....: [ 1, -1, 1, 0, 1, 0], ....: [ 0, -1, -1, 0, 0, 1]]) sage: C1, C2 = M.three_sum_decomposition(first_rows=[0, 1, 2, 4, 5], ....: first_columns=[0, 1, 2, 3], ....: special_columns=[0, 1]); (C1, C2) ( [ 0 1 -1 0 0] [ 0 0 1 1 0] [-1 1 0 0] [ 1 0 0 1 0] [ 0 0 1 1] [ 1 -1 1 0 1] [ 1 -1 1 0] [ 0 -1 -1 0 1], [ 0 -1 0 1] ) sage: M.is_three_sum(C1, C2, [3, 4], -1, [0, 1], 0, [0, 1], [2, 3]) True sage: M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 4, 4, sparse=True), ....: [[ 1, 0,-1, 0], ....: [ 1, 1, 0, 0], ....: [ 0, 1, 0, 1], ....: [ 1, 1,-1, 1]]) sage: M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 3, sparse=True), ....: [[ 1,-1, 0], ....: [ 1, 0, 1], ....: [ 1,-1, 1]]) sage: M = Matrix_cmr_chr_sparse.three_sum(M1, M2); M [ 1 0 -1 0] [ 1 1 0 0] [ 0 1 0 1] [ 1 1 -1 1] sage: Matrix_cmr_chr_sparse.is_three_sum(M, M1, M2) True sage: M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 3, sparse=True), ....: [[ 1, 1, 0], ....: [ 1, 0, 1], ....: [ 1,-1, 1]]) sage: Matrix_cmr_chr_sparse.is_three_sum(M, M1, M2, sign_verify=False) (False, 'the connecting matrix N should be totally unimodular') sage: M.three_sum_decomposition([0, 1, 2, 3], [0, 1, 2], [2, 3], [1, 2]) ( [ 1 0 -1 0] [ 1 1 0 0] [-1 1 0] [ 0 1 0 1] [ 1 0 1] [ 1 1 -1 1], [ 1 -1 1] )
>>> from sage.all import * >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(5), Integer(6), sparse=True), ... [[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(1), Integer(1), Integer(0), Integer(1), Integer(0)], ... [Integer(1), Integer(0), Integer(1),-Integer(1), Integer(1), Integer(1)], ... [Integer(0),-Integer(1), Integer(1), Integer(0),-Integer(1), Integer(1)]]); M1 [ 1 1 0 0 0 0] [ 0 0 -1 1 0 0] [ 0 1 1 0 1 0] [ 1 0 1 -1 1 1] [ 0 -1 1 0 -1 1] >>> M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(6), Integer(5), sparse=True), ... [[ 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(1), Integer(1), Integer(1)], ... [-Integer(1), Integer(1), Integer(0), Integer(0), Integer(0)], ... [ Integer(0), Integer(0), Integer(1), Integer(0),-Integer(1)], ... [ Integer(0), Integer(1), Integer(0), Integer(1), Integer(0)]]); M2 [ 1 -1 0 0 0] [ 1 0 1 -1 0] [ 1 -1 1 1 1] [-1 1 0 0 0] [ 0 0 1 0 -1] [ 0 1 0 1 0] >>> M = Matrix_cmr_chr_sparse.three_sum(M1, M2, first_intersection_columns=[Integer(2),Integer(1)]); M [ 1 1 0 0 0 0 0 0] [ 0 0 -1 1 0 0 0 0] [ 0 1 1 0 1 0 0 0] [ 1 0 1 -1 1 1 -1 0] [ 0 -1 1 0 -1 1 1 1] [ 0 1 -1 0 1 0 0 0] [ 0 0 0 0 0 1 0 -1] [ 1 1 0 -1 2 0 1 0] >>> M.is_three_sum(M1, M2, first_intersection_columns=[Integer(2), Integer(1)], sign_verify=False) True >>> M.is_three_sum(M1, M2, first_intersection_columns=[Integer(2), Integer(1)]) True >>> M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(4), Integer(5), sparse=True), ... [[ Integer(1), Integer(0), Integer(1), Integer(1), Integer(0)], ... [ Integer(0), Integer(1), Integer(1), Integer(1), Integer(0)], ... [ Integer(1), Integer(0), Integer(1), Integer(0), Integer(1)], ... [ Integer(0),-Integer(1), Integer(0),-Integer(1), Integer(1)]]); M1 [ 1 0 1 1 0] [ 0 1 1 1 0] [ 1 0 1 0 1] [ 0 -1 0 -1 1] >>> M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(5), Integer(4), sparse=True), ... [[ Integer(1), Integer(1), Integer(0), Integer(0)], ... [ Integer(1), Integer(0), Integer(1), Integer(1)], ... [ Integer(0),-Integer(1), Integer(1), Integer(1)], ... [ Integer(1), Integer(0), Integer(1), Integer(0)], ... [ Integer(0),-Integer(1), Integer(0), Integer(1)]]); M2 [ 1 1 0 0] [ 1 0 1 1] [ 0 -1 1 1] [ 1 0 1 0] [ 0 -1 0 1] >>> M = Matrix_cmr_chr_sparse.three_sum(M1, M2); M [ 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] >>> Matrix_cmr_chr_sparse.is_three_sum(M, M1, M2) True >>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(6), Integer(6), sparse=True), ... [[ Integer(0), Integer(1), -Integer(1), Integer(0), Integer(0), Integer(0)], ... [ Integer(0), Integer(0), Integer(1), Integer(1), 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(1), Integer(1), Integer(0), Integer(1), Integer(0)], ... [ Integer(0), -Integer(1), -Integer(1), Integer(0), Integer(0), Integer(1)]]) >>> C1, C2 = M.three_sum_decomposition(first_rows=[Integer(0), Integer(1), Integer(2), Integer(4), Integer(5)], ... first_columns=[Integer(0), Integer(1), Integer(2), Integer(3)], ... special_columns=[Integer(0), Integer(1)]); (C1, C2) ( [ 0 1 -1 0 0] [ 0 0 1 1 0] [-1 1 0 0] [ 1 0 0 1 0] [ 0 0 1 1] [ 1 -1 1 0 1] [ 1 -1 1 0] [ 0 -1 -1 0 1], [ 0 -1 0 1] ) >>> M.is_three_sum(C1, C2, [Integer(3), Integer(4)], -Integer(1), [Integer(0), Integer(1)], Integer(0), [Integer(0), Integer(1)], [Integer(2), Integer(3)]) True >>> M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(4), Integer(4), sparse=True), ... [[ Integer(1), Integer(0),-Integer(1), Integer(0)], ... [ Integer(1), Integer(1), Integer(0), Integer(0)], ... [ Integer(0), Integer(1), Integer(0), Integer(1)], ... [ Integer(1), Integer(1),-Integer(1), Integer(1)]]) >>> M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(3), Integer(3), sparse=True), ... [[ Integer(1),-Integer(1), Integer(0)], ... [ Integer(1), Integer(0), Integer(1)], ... [ Integer(1),-Integer(1), Integer(1)]]) >>> M = Matrix_cmr_chr_sparse.three_sum(M1, M2); M [ 1 0 -1 0] [ 1 1 0 0] [ 0 1 0 1] [ 1 1 -1 1] >>> Matrix_cmr_chr_sparse.is_three_sum(M, M1, M2) True >>> M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(3), Integer(3), sparse=True), ... [[ Integer(1), Integer(1), Integer(0)], ... [ Integer(1), Integer(0), Integer(1)], ... [ Integer(1),-Integer(1), Integer(1)]]) >>> Matrix_cmr_chr_sparse.is_three_sum(M, M1, M2, sign_verify=False) (False, 'the connecting matrix N should be totally unimodular') >>> M.three_sum_decomposition([Integer(0), Integer(1), Integer(2), Integer(3)], [Integer(0), Integer(1), Integer(2)], [Integer(2), Integer(3)], [Integer(1), Integer(2)]) ( [ 1 0 -1 0] [ 1 1 0 0] [-1 1 0] [ 0 1 0 1] [ 1 0 1] [ 1 1 -1 1], [ 1 -1 1] )
- is_totally_unimodular(time_limit=60.0, certificate=False, use_direct_graphicness_test=True, prefer_graphicness=True, series_parallel_ok=True, check_graphic_minors_planar=False, stop_when_nonTU=True, decompose_strategy='delta_three', construct_leaf_graphs=False, construct_all_graphs=False, row_keys=None, column_keys=None)[source]¶
Return whether
selfis a totally unimodular matrix.A matrix is totally unimodular if every subdeterminant is \(0\), \(1\), or \(-1\).
REFERENCES:
[Sch1986], Chapter 19
INPUT:
certificate– boolean (default:False); ifTrue, then return aDecompositionNodeifselfis totally unimodular; a submatrix with determinant not in \(\{0, \pm1\}\) if not.stop_when_nonTU– boolean (default:True); whether to stop decomposing once not TU is determined.For a description of other parameters, see
_set_cmr_seymour_parameters()row_keys– a finite or enumerated family of arbitrary objects that index the rows of the matrixcolumn_keys– a finite or enumerated family of arbitrary objects that index the columns of the 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], [2, 1], [0, 1]]); M [1 0] [2 1] [0 1] sage: M.is_totally_unimodular() False 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: M.is_totally_unimodular() True sage: M.is_totally_unimodular(certificate=True) (True, GraphicNode (3×2)) sage: MF = matroids.catalog.Fano(); MF Fano: Binary matroid of rank 3 on 7 elements, type (3, 0) sage: MFR = MF.representation().change_ring(ZZ); MFR [1 0 0 0 1 1 1] [0 1 0 1 0 1 1] [0 0 1 1 1 0 1] sage: MFR2 = block_diagonal_matrix(MFR, MFR, sparse=True); MFR2 [1 0 0 0 1 1 1|0 0 0 0 0 0 0] [0 1 0 1 0 1 1|0 0 0 0 0 0 0] [0 0 1 1 1 0 1|0 0 0 0 0 0 0] [-------------+-------------] [0 0 0 0 0 0 0|1 0 0 0 1 1 1] [0 0 0 0 0 0 0|0 1 0 1 0 1 1] [0 0 0 0 0 0 0|0 0 1 1 1 0 1] sage: MS2 = MFR2.parent(); MS2 Full MatrixSpace of 6 by 14 sparse matrices over Integer Ring sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: MFR2cmr = Matrix_cmr_chr_sparse(MS2, MFR2) sage: MFR2cmr.is_totally_unimodular(certificate=True) (False, (OneSumNode (6×14) with 2 children, ((2, 1, 0), (5, 4, 3)))) sage: result, certificate = MFR2cmr.is_totally_unimodular(certificate=True, ....: stop_when_nonTU=True) sage: result, certificate (False, (OneSumNode (6×14) with 2 children, ((2, 1, 0), (5, 4, 3)))) sage: submatrix = MFR2.matrix_from_rows_and_columns(*certificate[1]); submatrix [0 1 1] [1 0 1] [1 1 0] sage: submatrix.determinant() 2 sage: submatrix = MFR2cmr.matrix_from_rows_and_columns(*certificate[1]); submatrix [0 1 1] [1 0 1] [1 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(3), Integer(2), sparse=True), ... [[Integer(1), Integer(0)], [Integer(2), Integer(1)], [Integer(0), Integer(1)]]); M [1 0] [2 1] [0 1] >>> M.is_totally_unimodular() False >>> 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] >>> M.is_totally_unimodular() True >>> M.is_totally_unimodular(certificate=True) (True, GraphicNode (3×2)) >>> MF = matroids.catalog.Fano(); MF Fano: Binary matroid of rank 3 on 7 elements, type (3, 0) >>> MFR = MF.representation().change_ring(ZZ); MFR [1 0 0 0 1 1 1] [0 1 0 1 0 1 1] [0 0 1 1 1 0 1] >>> MFR2 = block_diagonal_matrix(MFR, MFR, sparse=True); MFR2 [1 0 0 0 1 1 1|0 0 0 0 0 0 0] [0 1 0 1 0 1 1|0 0 0 0 0 0 0] [0 0 1 1 1 0 1|0 0 0 0 0 0 0] [-------------+-------------] [0 0 0 0 0 0 0|1 0 0 0 1 1 1] [0 0 0 0 0 0 0|0 1 0 1 0 1 1] [0 0 0 0 0 0 0|0 0 1 1 1 0 1] >>> MS2 = MFR2.parent(); MS2 Full MatrixSpace of 6 by 14 sparse matrices over Integer Ring >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> MFR2cmr = Matrix_cmr_chr_sparse(MS2, MFR2) >>> MFR2cmr.is_totally_unimodular(certificate=True) (False, (OneSumNode (6×14) with 2 children, ((2, 1, 0), (5, 4, 3)))) >>> result, certificate = MFR2cmr.is_totally_unimodular(certificate=True, ... stop_when_nonTU=True) >>> result, certificate (False, (OneSumNode (6×14) with 2 children, ((2, 1, 0), (5, 4, 3)))) >>> submatrix = MFR2.matrix_from_rows_and_columns(*certificate[Integer(1)]); submatrix [0 1 1] [1 0 1] [1 1 0] >>> submatrix.determinant() 2 >>> submatrix = MFR2cmr.matrix_from_rows_and_columns(*certificate[Integer(1)]); submatrix [0 1 1] [1 0 1] [1 1 0]
If the matrix is totally unimodular, it always returns a full decomposition as a certificate:
sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 9, 9, sparse=True), ....: [[-1,-1,-1,-1, 0, 0, 0, 0, 0], ....: [1, 1, 0, 0, 0, 0, 0, 0, 0], ....: [0, 0, 1, 1, 0, 0, 0, 0, 0], ....: [1, 0, 1, 0, 0, 0, 0, 0, 0], ....: [0, 1, 0, 1, 0, 0, 0, 0, 0], ....: [0, 0, 0, 0,-1, 1, 0, 1, 0], ....: [0, 0, 0, 0,-1, 1, 0, 0, 1], ....: [0, 0, 0, 0,-1, 0, 1, 1, 0], ....: [0, 0, 0, 0,-1, 0, 1, 0, 1]]) sage: result, certificate = M.is_totally_unimodular( ....: certificate=True) sage: result, certificate (True, OneSumNode (9×9) with 2 children) sage: unicode_art(certificate) ╭───────────OneSumNode (9×9) with 2 children │ │ GraphicNode (5×4) CographicNode (4×5) sage: result, certificate = M.is_totally_unimodular( ....: certificate=True, stop_when_nonTU=False) sage: result, certificate (True, OneSumNode (9×9) with 2 children) sage: unicode_art(certificate) ╭───────────OneSumNode (9×9) with 2 children │ │ GraphicNode (5×4) CographicNode (4×5)
>>> from sage.all import * >>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(9), Integer(9), sparse=True), ... [[-Integer(1),-Integer(1),-Integer(1),-Integer(1), 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(0), Integer(0), Integer(0), Integer(0), Integer(0)], ... [Integer(1), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)], ... [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(0),-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(1)], ... [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(1), Integer(0), Integer(1), Integer(0), Integer(1)]]) >>> result, certificate = M.is_totally_unimodular( ... certificate=True) >>> result, certificate (True, OneSumNode (9×9) with 2 children) >>> unicode_art(certificate) ╭───────────OneSumNode (9×9) with 2 children │ │ GraphicNode (5×4) CographicNode (4×5) >>> result, certificate = M.is_totally_unimodular( ... certificate=True, stop_when_nonTU=False) >>> result, certificate (True, OneSumNode (9×9) with 2 children) >>> unicode_art(certificate) ╭───────────OneSumNode (9×9) with 2 children │ │ GraphicNode (5×4) CographicNode (4×5)
This is test
TreeFlagsNorecurse,TreeFlagsStopNoncographic, andTreeFlagsStopNongraphicin CMR’stest_regular.cpp, the underlying binary linear matroid is regular, but the matrix is not totally unimodular: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) sage: result, certificate (False, (OneSumNode (9×9) with 2 children, ((3, 2, 0), (3, 1, 0)))) sage: unicode_art(certificate[0]) ╭OneSumNode (9×9) with 2 children─╮ │ │ ThreeConnectedIrregularNode (5×4) UnknownNode (4×5) sage: result, certificate = M.is_totally_unimodular( ....: certificate=True, ....: stop_when_nonTU=False) sage: result, certificate (False, (OneSumNode (9×9) with 2 children, ((3, 2, 0), (3, 1, 0)))) sage: unicode_art(certificate[0]) ╭OneSumNode (9×9) with 2 children─╮ │ │ ThreeConnectedIrregularNode (5×4) ThreeConnectedIrregularNode (4×5)
>>> from sage.all import * >>> 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) >>> result, certificate (False, (OneSumNode (9×9) with 2 children, ((3, 2, 0), (3, 1, 0)))) >>> unicode_art(certificate[Integer(0)]) ╭OneSumNode (9×9) with 2 children─╮ │ │ ThreeConnectedIrregularNode (5×4) UnknownNode (4×5) >>> result, certificate = M.is_totally_unimodular( ... certificate=True, ... stop_when_nonTU=False) >>> result, certificate (False, (OneSumNode (9×9) with 2 children, ((3, 2, 0), (3, 1, 0)))) >>> unicode_art(certificate[Integer(0)]) ╭OneSumNode (9×9) with 2 children─╮ │ │ ThreeConnectedIrregularNode (5×4) ThreeConnectedIrregularNode (4×5)
- is_unimodular(time_limit=60.0)[source]¶
Return whether
selfis a unimodular matrix.A nonsingular square matrix \(A\) is called unimodular if it is integral and has determinant \(\pm1\), i.e., an element of \(\mathop{\operatorname{GL}}_n(\ZZ)\) [Sch1986], Ch. 4.3.
A rectangular matrix \(A\) of full row rank is called unimodular if it is integral and every basis \(B\) of \(A\) has determinant \(\pm1\). [Sch1986], Ch. 19.1.
More generally, a matrix \(A\) of rank \(r\) is called unimodular if it is integral and for every submatrix \(B\) formed by \(r\) linearly independent columns, the greatest common divisor of the determinants of all \(r\)-by-\(r\) submatrices of \(B\) is \(1\). [Sch1986], Ch. 21.4.
EXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 2, 3, sparse=True), ....: [[1, 0, 0], [0, 1, 0]]); M [1 0 0] [0 1 0] sage: M.is_unimodular() True sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 2, 3, sparse=True), ....: [[1, 1, 0], [-1, 1, 1]]); M [ 1 1 0] [-1 1 1] sage: M.is_unimodular() False
>>> from sage.all import * >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(2), Integer(3), sparse=True), ... [[Integer(1), Integer(0), Integer(0)], [Integer(0), Integer(1), Integer(0)]]); M [1 0 0] [0 1 0] >>> M.is_unimodular() True >>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(2), Integer(3), sparse=True), ... [[Integer(1), Integer(1), Integer(0)], [-Integer(1), Integer(1), Integer(1)]]); M [ 1 1 0] [-1 1 1] >>> M.is_unimodular() False
- is_y_sum(three_sum_mat, first_mat, second_mat, first_rows=[-2, -1], first_column=-1, second_rows=[0, 1], second_column=0, sign_verify=True)[source]¶
Check whether
first_matandsecond_matformthree_sum_matvia the Y-sum operation.Let \(M_1\) and \(M_2\) denote the matrices given by
first_matandsecond_mat. Iffirst_rowsindexes row vectors \(c^T\) infirst_matandfirst_columnindexes a column vector \(a\) infirst_mat, thensecond_rowsindexes row vectors \(b^T\) andsecond_columnindexes a column vector \(d\) insecond_mat. In this case, the matrices are\[\begin{split}M_1 = \begin{bmatrix} A & a \\ c^T & 0 \\ c^T & \varepsilon \end{bmatrix}, \qquad M_2 = \begin{bmatrix} \varepsilon & b^T \\ 0 & b^T \\ d & D \end{bmatrix}.\end{split}\]Then the Y-sum is the matrix
\[\begin{split}M_1 \oplus_3 M_2 = \begin{bmatrix} A & a b^T \\ d c^T & D \end{bmatrix}.\end{split}\]The value of \(\varepsilon \in \{-1,+1\}\) must be so that there exists a singular submatrix of \(M_1\) with exactly two nonzeros per row and per column that covers the top-left \(\varepsilon\)-entry.
If you don’t know the indices, please use
is_totally_unimodular().See also
INPUT:
three_sum_mat– the large integer matrix \(M\)first_mat– the first integer matrix \(M_1\)second_mat– the second integer matrix \(M_2\)first_rows– the row indices of \(c^T\) in \(M_1\)first_column– the column index of \(a\) in \(M_1\)second_rows– the row indices of \(b^T\) in \(M_2\)second_column– the column index of \(d\) in \(M_2\)sign_verify– boolean (default:True); whether to check the sign consistency of \(\varepsilon\).
OUTPUT: boolean, or (boolean, string)
If it is
Falseonly because of the sign, then also output the correct sign.EXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 5, sparse=True), ....: [[1, 1, 0, 0, 0], ....: [0,-1, 0,-1, 1], ....: [0, 0, 1, 0,-1], ....: [0, 1, 0, 1, 1], ....: [1, 0,-1, 1, 0], ....: [1, 0,-1, 1, 1],]); M1 [ 1 1 0 0 0] [ 0 -1 0 -1 1] [ 0 0 1 0 -1] [ 0 1 0 1 1] [ 1 0 -1 1 0] [ 1 0 -1 1 1] sage: M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 5, sparse=True), ....: [[ 1, 1, 1, 1,-1], ....: [ 0, 1, 1, 1,-1], ....: [-1, 1, 1, 0, 0], ....: [ 0, 0,-1, 0, 1], ....: [ 0, 1, 0,-1, 0], ....: [ 1, 0, 0, 0, 1]]); M2 [ 1 1 1 1 -1] [ 0 1 1 1 -1] [-1 1 1 0 0] [ 0 0 -1 0 1] [ 0 1 0 -1 0] [ 1 0 0 0 1] sage: M = Matrix_cmr_chr_sparse.y_sum(M1, M2); M [ 1 1 0 0 0 0 0 0] [ 0 -1 0 -1 1 1 1 -1] [ 0 0 1 0 -1 -1 -1 1] [ 0 1 0 1 1 1 1 -1] [-1 0 1 -1 1 1 0 0] [ 0 0 0 0 0 -1 0 1] [ 0 0 0 0 1 0 -1 0] [ 1 0 -1 1 0 0 0 1] sage: M.is_y_sum(M1, M2, sign_verify=False) True sage: M.is_y_sum(M1, M2) (False, 'epsilon in first_mat should be -1. epsilon in second_mat should be -1. ') sage: M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 5, sparse=True), ....: [[1, 1, 0, 0, 0], ....: [0,-1, 0,-1, 1], ....: [0, 0, 1, 0,-1], ....: [0, 1, 0, 1, 1], ....: [1, 0,-1, 1, 0], ....: [1, 0,-1, 1, 1],]); M1 [ 1 1 0 0 0] [ 0 -1 0 -1 1] [ 0 0 1 0 -1] [ 0 1 0 1 1] [ 1 0 -1 1 0] [ 1 0 -1 1 1] sage: M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 5, sparse=True), ....: [[-1, 1, 1, 1,-1], ....: [ 0, 1, 1, 1,-1], ....: [-1, 1, 1, 0, 0], ....: [ 0, 0,-1, 0, 1], ....: [ 0, 1, 0,-1, 0], ....: [ 1, 0, 0, 0, 1]]); M2 [-1 1 1 1 -1] [ 0 1 1 1 -1] [-1 1 1 0 0] [ 0 0 -1 0 1] [ 0 1 0 -1 0] [ 1 0 0 0 1] sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 8, 8, sparse=True), [ ....: [ 1, 1, 0, 0, 0, 0, 0, 0], ....: [ 0, -1, 0, -1, 1, 1, 1, -1], ....: [ 0, 0, 1, 0, -1, -1, -1, 1], ....: [ 0, 1, 0, 1, 1, 1, 1, -1], ....: [-1, 0, 1, -1, 1, 1, 0, 0], ....: [ 0, 0, 0, 0, 0, -1, 0, 1], ....: [ 0, 0, 0, 0, 1, 0, -1, 0], ....: [ 1, 0, -1, 1, 0, 0, 0, 1]]) sage: Matrix_cmr_chr_sparse.is_y_sum(M, M1, M2) (False, 'the epsilon in the two matrices are inconsistent') sage: M.y_sum_decomposition([0, 1, 2, 3], [0, 1, 2, 3]) ( [ 1 1 0 0 0] [-1 1 1 1 -1] [ 0 -1 0 -1 1] [ 0 1 1 1 -1] [ 0 0 1 0 -1] [ 1 1 1 0 0] [ 0 1 0 1 1] [ 0 0 -1 0 1] [-1 0 1 -1 0] [ 0 1 0 -1 0] [-1 0 1 -1 -1], [-1 0 0 0 1] ) sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 4, 4, sparse=True), ....: [[ 1, 1, 0, 0], ....: [ 1, 0, 1, 0], ....: [ 0, 1, 0, 1], ....: [ 0, 0, 1, 1]]); sage: M1, M2 = M.y_sum_decomposition([0, 1], [0, 1]); M1 [ 1 1 0] [ 1 0 1] [ 0 1 0] [ 0 1 -1] sage: M2 [-1 1 0] [ 0 1 0] [ 1 0 1] [ 0 1 1] sage: Matrix_cmr_chr_sparse.is_y_sum(M, M1, M2) True
>>> from sage.all import * >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(6), Integer(5), sparse=True), ... [[Integer(1), Integer(1), Integer(0), Integer(0), Integer(0)], ... [Integer(0),-Integer(1), Integer(0),-Integer(1), Integer(1)], ... [Integer(0), Integer(0), Integer(1), Integer(0),-Integer(1)], ... [Integer(0), Integer(1), Integer(0), Integer(1), Integer(1)], ... [Integer(1), Integer(0),-Integer(1), Integer(1), Integer(0)], ... [Integer(1), Integer(0),-Integer(1), Integer(1), Integer(1)],]); M1 [ 1 1 0 0 0] [ 0 -1 0 -1 1] [ 0 0 1 0 -1] [ 0 1 0 1 1] [ 1 0 -1 1 0] [ 1 0 -1 1 1] >>> M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(6), Integer(5), sparse=True), ... [[ Integer(1), Integer(1), Integer(1), Integer(1),-Integer(1)], ... [ Integer(0), Integer(1), Integer(1), Integer(1),-Integer(1)], ... [-Integer(1), Integer(1), Integer(1), Integer(0), Integer(0)], ... [ Integer(0), Integer(0),-Integer(1), Integer(0), Integer(1)], ... [ Integer(0), Integer(1), Integer(0),-Integer(1), Integer(0)], ... [ Integer(1), Integer(0), Integer(0), Integer(0), Integer(1)]]); M2 [ 1 1 1 1 -1] [ 0 1 1 1 -1] [-1 1 1 0 0] [ 0 0 -1 0 1] [ 0 1 0 -1 0] [ 1 0 0 0 1] >>> M = Matrix_cmr_chr_sparse.y_sum(M1, M2); M [ 1 1 0 0 0 0 0 0] [ 0 -1 0 -1 1 1 1 -1] [ 0 0 1 0 -1 -1 -1 1] [ 0 1 0 1 1 1 1 -1] [-1 0 1 -1 1 1 0 0] [ 0 0 0 0 0 -1 0 1] [ 0 0 0 0 1 0 -1 0] [ 1 0 -1 1 0 0 0 1] >>> M.is_y_sum(M1, M2, sign_verify=False) True >>> M.is_y_sum(M1, M2) (False, 'epsilon in first_mat should be -1. epsilon in second_mat should be -1. ') >>> M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(6), Integer(5), sparse=True), ... [[Integer(1), Integer(1), Integer(0), Integer(0), Integer(0)], ... [Integer(0),-Integer(1), Integer(0),-Integer(1), Integer(1)], ... [Integer(0), Integer(0), Integer(1), Integer(0),-Integer(1)], ... [Integer(0), Integer(1), Integer(0), Integer(1), Integer(1)], ... [Integer(1), Integer(0),-Integer(1), Integer(1), Integer(0)], ... [Integer(1), Integer(0),-Integer(1), Integer(1), Integer(1)],]); M1 [ 1 1 0 0 0] [ 0 -1 0 -1 1] [ 0 0 1 0 -1] [ 0 1 0 1 1] [ 1 0 -1 1 0] [ 1 0 -1 1 1] >>> M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(6), Integer(5), sparse=True), ... [[-Integer(1), Integer(1), Integer(1), Integer(1),-Integer(1)], ... [ Integer(0), Integer(1), Integer(1), Integer(1),-Integer(1)], ... [-Integer(1), Integer(1), Integer(1), Integer(0), Integer(0)], ... [ Integer(0), Integer(0),-Integer(1), Integer(0), Integer(1)], ... [ Integer(0), Integer(1), Integer(0),-Integer(1), Integer(0)], ... [ Integer(1), Integer(0), Integer(0), Integer(0), Integer(1)]]); M2 [-1 1 1 1 -1] [ 0 1 1 1 -1] [-1 1 1 0 0] [ 0 0 -1 0 1] [ 0 1 0 -1 0] [ 1 0 0 0 1] >>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(8), Integer(8), sparse=True), [ ... [ Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)], ... [ Integer(0), -Integer(1), Integer(0), -Integer(1), Integer(1), Integer(1), Integer(1), -Integer(1)], ... [ Integer(0), Integer(0), Integer(1), Integer(0), -Integer(1), -Integer(1), -Integer(1), Integer(1)], ... [ Integer(0), Integer(1), Integer(0), Integer(1), Integer(1), Integer(1), Integer(1), -Integer(1)], ... [-Integer(1), Integer(0), Integer(1), -Integer(1), Integer(1), Integer(1), Integer(0), Integer(0)], ... [ Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), -Integer(1), Integer(0), Integer(1)], ... [ Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0), -Integer(1), Integer(0)], ... [ Integer(1), Integer(0), -Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(1)]]) >>> Matrix_cmr_chr_sparse.is_y_sum(M, M1, M2) (False, 'the epsilon in the two matrices are inconsistent') >>> M.y_sum_decomposition([Integer(0), Integer(1), Integer(2), Integer(3)], [Integer(0), Integer(1), Integer(2), Integer(3)]) ( [ 1 1 0 0 0] [-1 1 1 1 -1] [ 0 -1 0 -1 1] [ 0 1 1 1 -1] [ 0 0 1 0 -1] [ 1 1 1 0 0] [ 0 1 0 1 1] [ 0 0 -1 0 1] [-1 0 1 -1 0] [ 0 1 0 -1 0] [-1 0 1 -1 -1], [-1 0 0 0 1] ) >>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(4), Integer(4), sparse=True), ... [[ Integer(1), Integer(1), Integer(0), Integer(0)], ... [ Integer(1), Integer(0), Integer(1), Integer(0)], ... [ Integer(0), Integer(1), Integer(0), Integer(1)], ... [ Integer(0), Integer(0), Integer(1), Integer(1)]]); >>> M1, M2 = M.y_sum_decomposition([Integer(0), Integer(1)], [Integer(0), Integer(1)]); M1 [ 1 1 0] [ 1 0 1] [ 0 1 0] [ 0 1 -1] >>> M2 [-1 1 0] [ 0 1 0] [ 1 0 1] [ 0 1 1] >>> Matrix_cmr_chr_sparse.is_y_sum(M, M1, M2) True
- matrix_from_rows_and_columns(rows, columns)[source]¶
Return the matrix constructed from
selffrom the given rows and columns.OUTPUT: A
Matrix_cmr_chr_sparseEXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: M = MatrixSpace(Integers(8),3,3) sage: A = Matrix_cmr_chr_sparse(M, range(9)); A [0 1 2] [3 4 5] [6 7 0] sage: A.matrix_from_rows_and_columns([1], [0,2]) [3 5] sage: A.matrix_from_rows_and_columns([1,2], [1,2]) [4 5] [7 0]
>>> from sage.all import * >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> M = MatrixSpace(Integers(Integer(8)),Integer(3),Integer(3)) >>> A = Matrix_cmr_chr_sparse(M, range(Integer(9))); A [0 1 2] [3 4 5] [6 7 0] >>> A.matrix_from_rows_and_columns([Integer(1)], [Integer(0),Integer(2)]) [3 5] >>> A.matrix_from_rows_and_columns([Integer(1),Integer(2)], [Integer(1),Integer(2)]) [4 5] [7 0]
Note that row and column indices can be reordered:
sage: A.matrix_from_rows_and_columns([2,1], [2,1]) [0 7] [5 4]
>>> from sage.all import * >>> A.matrix_from_rows_and_columns([Integer(2),Integer(1)], [Integer(2),Integer(1)]) [0 7] [5 4]
But the column indices can not be repeated:
sage: A.matrix_from_rows_and_columns([1,1,1],[2,0]) [5 3] [5 3] [5 3] sage: A.matrix_from_rows_and_columns([1,1,1],[2,0,0]) Traceback (most recent call last): ... ValueError: The column indices can not be repeated
>>> from sage.all import * >>> A.matrix_from_rows_and_columns([Integer(1),Integer(1),Integer(1)],[Integer(2),Integer(0)]) [5 3] [5 3] [5 3] >>> A.matrix_from_rows_and_columns([Integer(1),Integer(1),Integer(1)],[Integer(2),Integer(0),Integer(0)]) Traceback (most recent call last): ... ValueError: The column indices can not be repeated
- static one_sum(*summands)[source]¶
Return a block-diagonal matrix constructed from the given matrices (summands).
INPUT:
summands– integer matrices or data from which integer matrices can be constructed
OUTPUT: A
Matrix_cmr_chr_sparseThe terminology “1-sum” is used in the context of Seymour’s decomposition of totally unimodular matrices and regular matroids, see [Sch1986].
See also
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: unicode_art(M) ⎛ 1 0│ 0 0⎞ ⎜-1 1│ 0 0⎟ ⎜─────┼─────⎟ ⎜ 0 0│ 1 1⎟ ⎝ 0 0│-1 0⎠ sage: M = Matrix_cmr_chr_sparse.one_sum([[1, 0], [-1, 1]], [[1]], [[-1]]) sage: unicode_art(M) ⎛ 1 0│ 0│ 0⎞ ⎜-1 1│ 0│ 0⎟ ⎜─────┼──┼──⎟ ⎜ 0 0│ 1│ 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)]]) >>> unicode_art(M) ⎛ 1 0│ 0 0⎞ ⎜-1 1│ 0 0⎟ ⎜─────┼─────⎟ ⎜ 0 0│ 1 1⎟ ⎝ 0 0│-1 0⎠ >>> M = Matrix_cmr_chr_sparse.one_sum([[Integer(1), Integer(0)], [-Integer(1), Integer(1)]], [[Integer(1)]], [[-Integer(1)]]) >>> unicode_art(M) ⎛ 1 0│ 0│ 0⎞ ⎜-1 1│ 0│ 0⎟ ⎜─────┼──┼──⎟ ⎜ 0 0│ 1│ 0⎟ ⎜─────┼──┼──⎟ ⎝ 0 0│ 0│-1⎠
- strong_equimodulus(time_limit=60.0)[source]¶
Return the integer \(k\) such that
selfis strongly equimodular with determinant gcd \(k\).Return whether
selfis strongly \(k\)-equimodular.A matrix is strongly equimodular if
selfandself.transpose()are both equimodular, which implies that they are equimodular for the same determinant gcd \(k\). A matrix \(M\) of rank \(r\) is \(k\)-equimodular if the following two conditions are satisfied:for some column basis \(B\) of \(M\), the greatest common divisor of the determinants of all \(r\)-by-\(r\) submatrices of \(B\) is \(k\);
the matrix \(X\) such that \(M=BX\) is totally unimodular.
OUTPUT:
k:selfis \(k\)-equimodularNone:selfis not \(k\)-equimodular for any \(k\)
See also
EXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 3, sparse=True), ....: [[1, 0, 1], [0, 1, 1], [1, 2, 3]]); M [1 0 1] [0 1 1] [1 2 3] sage: M.strong_equimodulus() sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 2, 3, sparse=True), ....: [[1, 0, 0], [0, 1, 0]]); M [1 0 0] [0 1 0] sage: M.strong_equimodulus() 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(3), sparse=True), ... [[Integer(1), Integer(0), Integer(1)], [Integer(0), Integer(1), Integer(1)], [Integer(1), Integer(2), Integer(3)]]); M [1 0 1] [0 1 1] [1 2 3] >>> M.strong_equimodulus() >>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(2), Integer(3), sparse=True), ... [[Integer(1), Integer(0), Integer(0)], [Integer(0), Integer(1), Integer(0)]]); M [1 0 0] [0 1 0] >>> M.strong_equimodulus() 1
- ternary_pivot(row, column)[source]¶
Apply a pivot to
selfand return the resulting matrix.Calculations are done over the ternary field.
Suppose a matrix is of the form \(\begin{bmatrix} \epsilon & c^T \\ b & D\end{bmatrix}\), where \(\epsilon\in\{\pm 1\}\). Then the pivot of the matrix with respect to \(\epsilon\) is \(\begin{bmatrix} -\epsilon & \epsilon c^T \\ \epsilon b & D-\epsilon bc^T\end{bmatrix}\).
The terminology “pivot” is defined in [Sch1986], Ch. 19.4.
See also
EXAMPLES:
Single pivot on a \(1\)-entry:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 10, 10, sparse=True), [ ....: [ 1, 1, 0, 0, 0, -1, 0, 1, 0, 0], ....: [-1, 0, 0, 0, 0, 1, 1, 0, 1, 0], ....: [ 0, 0, 0, 0, 1, 1, 0, 0, 0, 0], ....: [ 0, 0, 0, 1, 1, 0, 0, 0, 0, 0], ....: [ 0, 0, 1, 1, 0, 0, 0, 0, 0, 0], ....: [ 0, 1, 1, 0, 0, 0, 0, 0, 0, 0], ....: [ 0, 0, 0, 0, 0, 0, 0, 0, 1, 0], ....: [ 0, 0, 0, 0, 0, 1, 0, 0, 0, 1], ....: [ 1, 0, 0, 0, 0, 0, 1, 0, 1, 1], ....: [ 1, 1, 0, 0, 0, 1, 0, 0, 0, 0] ....: ]); M [ 1 1 0 0 0 -1 0 1 0 0] [-1 0 0 0 0 1 1 0 1 0] [ 0 0 0 0 1 1 0 0 0 0] [ 0 0 0 1 1 0 0 0 0 0] [ 0 0 1 1 0 0 0 0 0 0] [ 0 1 1 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0 1 0] [ 0 0 0 0 0 1 0 0 0 1] [ 1 0 0 0 0 0 1 0 1 1] [ 1 1 0 0 0 1 0 0 0 0] sage: M.ternary_pivot(0, 0) [-1 1 0 0 0 -1 0 1 0 0] [-1 1 0 0 0 0 1 1 1 0] [ 0 0 0 0 1 1 0 0 0 0] [ 0 0 0 1 1 0 0 0 0 0] [ 0 0 1 1 0 0 0 0 0 0] [ 0 1 1 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0 1 0] [ 0 0 0 0 0 1 0 0 0 1] [ 1 -1 0 0 0 1 1 -1 1 1] [ 1 0 0 0 0 -1 0 -1 0 0]
>>> from sage.all import * >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(10), Integer(10), sparse=True), [ ... [ Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), -Integer(1), Integer(0), Integer(1), Integer(0), Integer(0)], ... [-Integer(1), 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(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(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(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0)], ... [ Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(1)], ... [ Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0), Integer(1), Integer(1)], ... [ Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0)] ... ]); M [ 1 1 0 0 0 -1 0 1 0 0] [-1 0 0 0 0 1 1 0 1 0] [ 0 0 0 0 1 1 0 0 0 0] [ 0 0 0 1 1 0 0 0 0 0] [ 0 0 1 1 0 0 0 0 0 0] [ 0 1 1 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0 1 0] [ 0 0 0 0 0 1 0 0 0 1] [ 1 0 0 0 0 0 1 0 1 1] [ 1 1 0 0 0 1 0 0 0 0] >>> M.ternary_pivot(Integer(0), Integer(0)) [-1 1 0 0 0 -1 0 1 0 0] [-1 1 0 0 0 0 1 1 1 0] [ 0 0 0 0 1 1 0 0 0 0] [ 0 0 0 1 1 0 0 0 0 0] [ 0 0 1 1 0 0 0 0 0 0] [ 0 1 1 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0 1 0] [ 0 0 0 0 0 1 0 0 0 1] [ 1 -1 0 0 0 1 1 -1 1 1] [ 1 0 0 0 0 -1 0 -1 0 0]
Single pivot on a \(-1\)-entry:
sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 10, 10, sparse=True), [ ....: [-1, 1, 0, 0, 0, -1, 0, 1, 0, 0], ....: [-1, 0, 0, 0, 0, 1, 1, 0, 1, 0], ....: [ 0, 0, 0, 0, 1, 1, 0, 0, 0, 0], ....: [ 0, 0, 0, 1, 1, 0, 0, 0, 0, 0], ....: [ 0, 0, 1, 1, 0, 0, 0, 0, 0, 0], ....: [ 0, 1, 1, 0, 0, 0, 0, 0, 0, 0], ....: [ 0, 0, 0, 0, 0, 0, 0, 0, 1, 0], ....: [ 0, 0, 0, 0, 0, 1, 0, 0, 0, 1], ....: [ 1, 0, 0, 0, 0, 0, 1, 0, 1, 1], ....: [ 1, 1, 0, 0, 0, 1, 0, 0, 0, 0] ....: ]); M [-1 1 0 0 0 -1 0 1 0 0] [-1 0 0 0 0 1 1 0 1 0] [ 0 0 0 0 1 1 0 0 0 0] [ 0 0 0 1 1 0 0 0 0 0] [ 0 0 1 1 0 0 0 0 0 0] [ 0 1 1 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0 1 0] [ 0 0 0 0 0 1 0 0 0 1] [ 1 0 0 0 0 0 1 0 1 1] [ 1 1 0 0 0 1 0 0 0 0] sage: M.ternary_pivot(0, 0) [ 1 -1 0 0 0 1 0 -1 0 0] [ 1 -1 0 0 0 -1 1 -1 1 0] [ 0 0 0 0 1 1 0 0 0 0] [ 0 0 0 1 1 0 0 0 0 0] [ 0 0 1 1 0 0 0 0 0 0] [ 0 1 1 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0 1 0] [ 0 0 0 0 0 1 0 0 0 1] [-1 1 0 0 0 -1 1 1 1 1] [-1 -1 0 0 0 0 0 1 0 0]
>>> from sage.all import * >>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(10), Integer(10), sparse=True), [ ... [-Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), -Integer(1), Integer(0), Integer(1), Integer(0), Integer(0)], ... [-Integer(1), 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(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(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(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0)], ... [ Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(1)], ... [ Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0), Integer(1), Integer(1)], ... [ Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0)] ... ]); M [-1 1 0 0 0 -1 0 1 0 0] [-1 0 0 0 0 1 1 0 1 0] [ 0 0 0 0 1 1 0 0 0 0] [ 0 0 0 1 1 0 0 0 0 0] [ 0 0 1 1 0 0 0 0 0 0] [ 0 1 1 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0 1 0] [ 0 0 0 0 0 1 0 0 0 1] [ 1 0 0 0 0 0 1 0 1 1] [ 1 1 0 0 0 1 0 0 0 0] >>> M.ternary_pivot(Integer(0), Integer(0)) [ 1 -1 0 0 0 1 0 -1 0 0] [ 1 -1 0 0 0 -1 1 -1 1 0] [ 0 0 0 0 1 1 0 0 0 0] [ 0 0 0 1 1 0 0 0 0 0] [ 0 0 1 1 0 0 0 0 0 0] [ 0 1 1 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0 1 0] [ 0 0 0 0 0 1 0 0 0 1] [-1 1 0 0 0 -1 1 1 1 1] [-1 -1 0 0 0 0 0 1 0 0]
- ternary_pivots(rows, columns)[source]¶
Apply a sequence of pivots to
selfand return the resulting matrix.Calculations are done over the ternary field.
See also
- three_sum(first_mat, second_mat, first_rows=[-2, -1], first_column=-1, first_intersection_columns=[-3, -2], second_row=0, second_columns=[0, 1], second_intersection_rows=[1, 2], algorithm='cmr', sign_verify=False)[source]¶
Return the 3-sum matrix constructed from the given matrices
first_matandsecond_mat.In this case, the two matrices are of the form
\[\begin{split}M_1 = \begin{bmatrix} A & 0 \\ C_{i,\star} & \alpha \\ C_{j,\star} & \beta \end{bmatrix}, \qquad M_2 = \begin{bmatrix} \gamma & \delta & 0^T \\ C_{\star,k} & C_{\star,\ell} & D \end{bmatrix},\end{split}\]where \(\alpha, \beta \in \{-1,+1 \}\) and \(\gamma, \delta \in \{ -1,+1 \}\) such that the matrix
\[\begin{split}N = \begin{bmatrix} \gamma & \delta & 0 \\ C_{i,k} & C_{i,\ell} & \alpha \\ C_{j,k} & C_{j,\ell} & \beta \end{bmatrix}\end{split}\]is totally unimodular. Then the 3-sum of \(M_1\) and \(M_2\) (at these rows/columns) is the matrix
\[\begin{split}M = \begin{bmatrix} A & 0 \\ C & D \end{bmatrix},\end{split}\]where \(C\) is the unique rank-2 matrix having linearly independent rows \(C_{i,\star}\) and \(C_{j,\star}\) and linearly independent columns \(C_{\star,k}\) and \(C_{\star,\ell}\).
The terminology “3-sum” originates from Seymour’s decomposition of regular matroids. In the context of totally unimodular matrices, there are different interpretations in the form of matrix operations for \(\begin{bmatrix} A & B \\ C & D \end{bmatrix}\) satisfying \(\rank(B) + \rank(C) = 2\). Three types of 3-sum operations are implemented in CMR: \(\Delta\)-sum, 3-sum, and Y-sum.
For 3-sum, one of \(B\) and \(C\) is a zero matrix, also known as “concentrated_rank”.
For \(\Delta\)-sum and Y-sum, both \(B\) and \(C\) are of rank 1, also known as “distributed_ranks”.
See also
_three_sum_cmr(),three_sum_decomposition(),is_three_sum(),one_sum(),two_sum(),delta_sum(),y_sum()INPUT:
first_mat– the first integer matrix \(M_1\)second_mat– the second integer matrix \(M_2\)first_rows– the indices of rows \(a_1^T\) and \(a_2^T\) in \(M_1\)first_column– the index of the extra column in \(M_1\)first_intersection_columns– the indices of columns \(k\) and \(\ell\)second_row– the index of the extra row in \(M_2\)second_columns– the indices of columns \(b_1\) and \(b_2\) in \(M_2\)second_intersection_rows– the indices of rows \(i\) and \(j\)algorithm–"cmr"or"direct"Ifalgorithm="cmr", then use_three_sum_cmr(); Ifalgorithm="direct", then construct three sum directly. Both options will check the give two matrices and the related indices satisfying the requirements of 3-sum.sign_verify– boolean (default:False); whether to check the sign consistency of \(\alpha, \beta, \gamma, \delta\). Seeis_three_sum(),three_sum_decomposition().
OUTPUT: A
Matrix_cmr_chr_sparseEXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 5, 6, sparse=True), ....: [[1, 1, 0, 0, 0, 0], ....: [0, 0,-1, 1, 0, 0], ....: [0, 1, 1, 0, 1, 0], ....: [1, 0, 1,-1, 1, 1], ....: [0,-1, 1, 0,-1, 1]]); M1 [ 1 1 0 0 0 0] [ 0 0 -1 1 0 0] [ 0 1 1 0 1 0] [ 1 0 1 -1 1 1] [ 0 -1 1 0 -1 1] sage: M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 5, sparse=True), ....: [[-1, 1, 0, 0, 0], ....: [ 1, 0, 1,-1, 0], ....: [ 1,-1, 1, 1, 1], ....: [-1, 1, 0, 0, 0], ....: [ 0, 0, 1, 0,-1], ....: [ 0, 1, 0, 1, 0]]); M2 [-1 1 0 0 0] [ 1 0 1 -1 0] [ 1 -1 1 1 1] [-1 1 0 0 0] [ 0 0 1 0 -1] [ 0 1 0 1 0] sage: Matrix_cmr_chr_sparse.three_sum(M1, M2, [-2,-1], -1, [2, 3], 0, [1,0], [3,5]) [ 1 1 0 0 0 0 0 0] [ 0 0 -1 1 0 0 0 0] [ 0 1 1 0 1 0 0 0] [-1 -1 0 1 -2 1 -1 0] [-1 0 -1 1 -1 1 1 1] [ 1 0 1 -1 1 0 0 0] [ 0 0 0 0 0 1 0 -1] [ 0 -1 1 0 -1 0 1 0] sage: Matrix_cmr_chr_sparse.three_sum(M1, M2, first_intersection_columns=[2, 1]) [ 1 1 0 0 0 0 0 0] [ 0 0 -1 1 0 0 0 0] [ 0 1 1 0 1 0 0 0] [ 1 0 1 -1 1 1 -1 0] [ 0 -1 1 0 -1 1 1 1] [ 0 1 -1 0 1 0 0 0] [ 0 0 0 0 0 1 0 -1] [ 1 1 0 -1 2 0 1 0] sage: M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 5, 6, sparse=True), ....: [[1, 1, 0, 0, 0, 0], ....: [1, 0, 1,-1, 1, 1], ....: [0,-1, 1, 0,-1, 1], ....: [0, 0,-1, 1, 0, 0], ....: [0, 1, 1, 0, 1, 0]]); M1 [ 1 1 0 0 0 0] [ 1 0 1 -1 1 1] [ 0 -1 1 0 -1 1] [ 0 0 -1 1 0 0] [ 0 1 1 0 1 0] sage: M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 5, sparse=True), ....: [[0, 0, 1, 0,-1], ....: [1,-1, 1, 0, 0], ....: [1, 1, 1, 1,-1], ....: [0, 0,-1, 0, 1], ....: [1, 0, 0,-1, 0], ....: [0, 1, 0, 0, 1]]); M2 [ 0 0 1 0 -1] [ 1 -1 1 0 0] [ 1 1 1 1 -1] [ 0 0 -1 0 1] [ 1 0 0 -1 0] [ 0 1 0 0 1] sage: M = M1.three_sum(M2, first_rows=[1, 2], ....: first_intersection_columns=[2, 3], ....: second_columns=[4, 2], ....: second_intersection_rows=[3, 5]); M [ 1 1 0 0 0 0 0 0] [ 0 0 -1 1 0 0 0 0] [ 0 1 1 0 1 0 0 0] [-1 -1 0 1 -2 1 -1 0] [-1 0 -1 1 -1 1 1 1] [ 1 0 1 -1 1 0 0 0] [ 0 0 0 0 0 1 0 -1] [ 0 -1 1 0 -1 0 1 0] sage: M = M1.three_sum(M2, first_rows=[1, 2], ....: first_intersection_columns=[1, 2], ....: second_columns=[4, 2]); M [ 1 1 0 0 0 0 0 0] [ 0 0 -1 1 0 0 0 0] [ 0 1 1 0 1 0 0 0] [ 1 0 1 -1 1 1 -1 0] [ 0 -1 1 0 -1 1 1 1] [ 0 1 -1 0 1 0 0 0] [ 0 0 0 0 0 1 0 -1] [ 1 1 0 -1 2 0 1 0] sage: M1.three_sum(M2, first_rows=[1, 2], ....: first_column=1, ....: second_columns=[2, 4]) Traceback (most recent call last): ... RuntimeError: Invalid matrix structure sage: M1.three_sum(M2, first_rows=[1, 2], ....: first_intersection_columns=[1, 2], ....: second_columns=[2, 4], algorithm="direct") Traceback (most recent call last): ... ValueError: The intersection matrix is not the same!
>>> from sage.all import * >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(5), Integer(6), sparse=True), ... [[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(1), Integer(1), Integer(0), Integer(1), Integer(0)], ... [Integer(1), Integer(0), Integer(1),-Integer(1), Integer(1), Integer(1)], ... [Integer(0),-Integer(1), Integer(1), Integer(0),-Integer(1), Integer(1)]]); M1 [ 1 1 0 0 0 0] [ 0 0 -1 1 0 0] [ 0 1 1 0 1 0] [ 1 0 1 -1 1 1] [ 0 -1 1 0 -1 1] >>> M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(6), Integer(5), sparse=True), ... [[-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(1), Integer(1), Integer(1)], ... [-Integer(1), Integer(1), Integer(0), Integer(0), Integer(0)], ... [ Integer(0), Integer(0), Integer(1), Integer(0),-Integer(1)], ... [ Integer(0), Integer(1), Integer(0), Integer(1), Integer(0)]]); M2 [-1 1 0 0 0] [ 1 0 1 -1 0] [ 1 -1 1 1 1] [-1 1 0 0 0] [ 0 0 1 0 -1] [ 0 1 0 1 0] >>> Matrix_cmr_chr_sparse.three_sum(M1, M2, [-Integer(2),-Integer(1)], -Integer(1), [Integer(2), Integer(3)], Integer(0), [Integer(1),Integer(0)], [Integer(3),Integer(5)]) [ 1 1 0 0 0 0 0 0] [ 0 0 -1 1 0 0 0 0] [ 0 1 1 0 1 0 0 0] [-1 -1 0 1 -2 1 -1 0] [-1 0 -1 1 -1 1 1 1] [ 1 0 1 -1 1 0 0 0] [ 0 0 0 0 0 1 0 -1] [ 0 -1 1 0 -1 0 1 0] >>> Matrix_cmr_chr_sparse.three_sum(M1, M2, first_intersection_columns=[Integer(2), Integer(1)]) [ 1 1 0 0 0 0 0 0] [ 0 0 -1 1 0 0 0 0] [ 0 1 1 0 1 0 0 0] [ 1 0 1 -1 1 1 -1 0] [ 0 -1 1 0 -1 1 1 1] [ 0 1 -1 0 1 0 0 0] [ 0 0 0 0 0 1 0 -1] [ 1 1 0 -1 2 0 1 0] >>> M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(5), Integer(6), sparse=True), ... [[Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0)], ... [Integer(1), Integer(0), Integer(1),-Integer(1), Integer(1), 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(0)], ... [Integer(0), Integer(1), Integer(1), Integer(0), Integer(1), Integer(0)]]); M1 [ 1 1 0 0 0 0] [ 1 0 1 -1 1 1] [ 0 -1 1 0 -1 1] [ 0 0 -1 1 0 0] [ 0 1 1 0 1 0] >>> M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(6), Integer(5), sparse=True), ... [[Integer(0), Integer(0), Integer(1), Integer(0),-Integer(1)], ... [Integer(1),-Integer(1), Integer(1), Integer(0), Integer(0)], ... [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(0),-Integer(1), Integer(0)], ... [Integer(0), Integer(1), Integer(0), Integer(0), Integer(1)]]); M2 [ 0 0 1 0 -1] [ 1 -1 1 0 0] [ 1 1 1 1 -1] [ 0 0 -1 0 1] [ 1 0 0 -1 0] [ 0 1 0 0 1] >>> M = M1.three_sum(M2, first_rows=[Integer(1), Integer(2)], ... first_intersection_columns=[Integer(2), Integer(3)], ... second_columns=[Integer(4), Integer(2)], ... second_intersection_rows=[Integer(3), Integer(5)]); M [ 1 1 0 0 0 0 0 0] [ 0 0 -1 1 0 0 0 0] [ 0 1 1 0 1 0 0 0] [-1 -1 0 1 -2 1 -1 0] [-1 0 -1 1 -1 1 1 1] [ 1 0 1 -1 1 0 0 0] [ 0 0 0 0 0 1 0 -1] [ 0 -1 1 0 -1 0 1 0] >>> M = M1.three_sum(M2, first_rows=[Integer(1), Integer(2)], ... first_intersection_columns=[Integer(1), Integer(2)], ... second_columns=[Integer(4), Integer(2)]); M [ 1 1 0 0 0 0 0 0] [ 0 0 -1 1 0 0 0 0] [ 0 1 1 0 1 0 0 0] [ 1 0 1 -1 1 1 -1 0] [ 0 -1 1 0 -1 1 1 1] [ 0 1 -1 0 1 0 0 0] [ 0 0 0 0 0 1 0 -1] [ 1 1 0 -1 2 0 1 0] >>> M1.three_sum(M2, first_rows=[Integer(1), Integer(2)], ... first_column=Integer(1), ... second_columns=[Integer(2), Integer(4)]) Traceback (most recent call last): ... RuntimeError: Invalid matrix structure >>> M1.three_sum(M2, first_rows=[Integer(1), Integer(2)], ... first_intersection_columns=[Integer(1), Integer(2)], ... second_columns=[Integer(2), Integer(4)], algorithm="direct") Traceback (most recent call last): ... ValueError: The intersection matrix is not the same!
The connecting matrix \(N\) should be totally unimodular:
sage: M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 5, sparse=True), ....: [[0, 0, 1, 0, 1], ....: [1,-1, 1, 0, 0], ....: [1, 1, 1, 1,-1], ....: [0, 0,-1, 0, 1], ....: [1, 0, 0,-1, 0], ....: [0, 1, 0, 0, 1]]); M2 [ 0 0 1 0 1] [ 1 -1 1 0 0] [ 1 1 1 1 -1] [ 0 0 -1 0 1] [ 1 0 0 -1 0] [ 0 1 0 0 1] sage: M = M1.three_sum(M2, first_rows=[1, 2], ....: first_intersection_columns=[1, 2], ....: second_columns=[4, 2]) Traceback (most recent call last): ... RuntimeError: Inconsistent pieces of input sage: M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 4, 4, sparse=True), ....: [[ 1, 0,-1, 0], ....: [ 1, 1, 0, 0], ....: [ 0, 1, 0, 1], ....: [ 1, 1,-1, 1]]) sage: M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 3, sparse=True), ....: [[ 1, 1, 0], ....: [ 1, 0, 1], ....: [ 1,-1, 1]]) sage: M = Matrix_cmr_chr_sparse.three_sum(M1, M2) Traceback (most recent call last): ... RuntimeError: Inconsistent pieces of input sage: M = Matrix_cmr_chr_sparse.three_sum(M1, M2, algorithm='direct'); M Traceback (most recent call last): ... ValueError: the connecting matrix N should be totally unimodular sage: M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 3, 3, sparse=True), ....: [[ 1,-1, 0], ....: [ 1, 0, 1], ....: [ 1,-1, 1]]) sage: M = Matrix_cmr_chr_sparse.three_sum(M1, M2); M [ 1 0 -1 0] [ 1 1 0 0] [ 0 1 0 1] [ 1 1 -1 1] sage: M.three_sum_decomposition(first_rows=[0,1,2,3], ....: first_columns=[0,1,2], ....: special_columns=[1,2]) ( [ 1 0 -1 0] [ 1 1 0 0] [-1 1 0] [ 0 1 0 1] [ 1 0 1] [ 1 1 -1 1], [ 1 -1 1] )
>>> from sage.all import * >>> M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(6), Integer(5), sparse=True), ... [[Integer(0), Integer(0), Integer(1), Integer(0), Integer(1)], ... [Integer(1),-Integer(1), Integer(1), Integer(0), Integer(0)], ... [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(0),-Integer(1), Integer(0)], ... [Integer(0), Integer(1), Integer(0), Integer(0), Integer(1)]]); M2 [ 0 0 1 0 1] [ 1 -1 1 0 0] [ 1 1 1 1 -1] [ 0 0 -1 0 1] [ 1 0 0 -1 0] [ 0 1 0 0 1] >>> M = M1.three_sum(M2, first_rows=[Integer(1), Integer(2)], ... first_intersection_columns=[Integer(1), Integer(2)], ... second_columns=[Integer(4), Integer(2)]) Traceback (most recent call last): ... RuntimeError: Inconsistent pieces of input >>> M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(4), Integer(4), sparse=True), ... [[ Integer(1), Integer(0),-Integer(1), Integer(0)], ... [ Integer(1), Integer(1), Integer(0), Integer(0)], ... [ Integer(0), Integer(1), Integer(0), Integer(1)], ... [ Integer(1), Integer(1),-Integer(1), Integer(1)]]) >>> M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(3), Integer(3), sparse=True), ... [[ Integer(1), Integer(1), Integer(0)], ... [ Integer(1), Integer(0), Integer(1)], ... [ Integer(1),-Integer(1), Integer(1)]]) >>> M = Matrix_cmr_chr_sparse.three_sum(M1, M2) Traceback (most recent call last): ... RuntimeError: Inconsistent pieces of input >>> M = Matrix_cmr_chr_sparse.three_sum(M1, M2, algorithm='direct'); M Traceback (most recent call last): ... ValueError: the connecting matrix N should be totally unimodular >>> M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(3), Integer(3), sparse=True), ... [[ Integer(1),-Integer(1), Integer(0)], ... [ Integer(1), Integer(0), Integer(1)], ... [ Integer(1),-Integer(1), Integer(1)]]) >>> M = Matrix_cmr_chr_sparse.three_sum(M1, M2); M [ 1 0 -1 0] [ 1 1 0 0] [ 0 1 0 1] [ 1 1 -1 1] >>> M.three_sum_decomposition(first_rows=[Integer(0),Integer(1),Integer(2),Integer(3)], ... first_columns=[Integer(0),Integer(1),Integer(2)], ... special_columns=[Integer(1),Integer(2)]) ( [ 1 0 -1 0] [ 1 1 0 0] [-1 1 0] [ 0 1 0 1] [ 1 0 1] [ 1 1 -1 1], [ 1 -1 1] )
- three_sum_decomposition(first_rows, first_columns, special_rows=None, special_columns=None)[source]¶
Decompose the matrix into two child matrices using the 3-sum decomposition with specified sepa.
Let \(M\) denote the matrix given by
three_sum_mat. Then\[\begin{split}M = \begin{bmatrix} A & 0 \\ C & D \end{bmatrix},\end{split}\]where \(\rank(C) = 2\). The two components of the 3-sum \(M_1\) and \(M_2\), given by
first_matandsecond_mat, must be of the form\[\begin{split}M_1 = \begin{bmatrix} A & 0 \\ C_{i,\star} & 1 \\ C_{j,\star} & \beta \end{bmatrix}, \qquad M_2 = \begin{bmatrix} \gamma & 1 & 0^T \\ C_{\star,k} & C_{\star,\ell} & D \end{bmatrix},\end{split}\]where \(\beta \in \{-1,+1 \}\) and \(\gamma \in \{ -1,+1 \}\) such that the matrix
\[\begin{split}N = \begin{bmatrix} \gamma & 1 & 0 \\ C_{i,k} & C_{i,\ell} & 1 \\ C_{j,k} & C_{j,\ell} & \beta \end{bmatrix}\end{split}\]is totally unimodular. The indices
first_special_columns[0]andfirst_special_columns[1]indicate the columns of \(M_1\) that shall correspond to \(C_{\star,k}\) and \(C_{\star,\ell}\), respectively. Similarly, the indicessecond_special_rows[1]andsecond_special_rows[2]indicate the rows of \(M_2\) that shall correspond to \(C_{i,\star}\) and \(C_{j,\star}\), respectively.The value of \(\beta \in \{-1,+1\}\) must be so that there exists a singular submatrix of \(M_1\) with exactly two nonzeros per row and per column that covers the bottom-right \(\beta\)-entry.
Note
If the matrix is instead in the form
\[\begin{split}M = \begin{bmatrix} A & B \\ 0 & D \end{bmatrix},\end{split}\]then by permutating the rows and columns, it can be viewed as
\[\begin{split}\begin{bmatrix} D & 0 \\ B & A \end{bmatrix}.\end{split}\]Thus, the 3-sum decomposition as described above can be applied.
INPUT:
first_rows– list of row indices for the first matrixfirst_columns– list of column indices for the first matrixspecial_rows– list of two special row indices (default: last two rows)special_columns– list of two special column indices (default: last two columns)
OUTPUT: A tuple of two
Matrix_cmr_chr_sparseEXAMPLES:
This is test
ThreesumDecompositionin CMR’stest_separation.cpp:sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: M = 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]]); M [ 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: M1, M2 = M.three_sum_decomposition([0, 1, 2, 3], [0, 1, 2, 3], ....: [2, 3], [2, 3]); M1 [ 1 0 1 1 0] [ 0 1 1 1 0] [ 1 0 1 0 1] [ 0 -1 0 -1 1] sage: M2 [ 1 1 0 0] [ 1 0 1 1] [ 0 -1 1 1] [ 1 0 1 0] [ 0 -1 0 1] sage: M = 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]]); M [-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: M1, M2 = M.three_sum_decomposition([0, 1, 2, 3], [0, 1, 2, 3], ....: [2, 3], [2, 3]); M1 [-1 0 -1 1 0] [ 0 -1 1 -1 0] [-1 0 -1 0 1] [ 0 -1 0 -1 1] sage: M2 [-1 1 0 0] [-1 0 1 1] [ 0 -1 1 1] [-1 0 1 0] [ 0 -1 0 1] sage: M = 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]]); M [ 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: M1, M2 = M.three_sum_decomposition([0, 1, 2, 3], [0, 1, 2, 3], ....: [2, 3], [2, 3]); M1 [ 1 0 1 1 0] [ 0 1 1 1 0] [ 1 0 1 0 1] [ 0 1 0 1 -1] sage: M2 [ 1 1 0 0] [ 1 0 1 -1] [ 0 1 -1 1] [ 1 0 1 0] [ 0 1 0 1] sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 6, sparse=True), ....: [[ 0, 1, -1, 0, 0, 0], ....: [ 0, 0, 1, 1, 0, 0], ....: [ 1, 0, 0, 1, 0, 0], ....: [ 0, 0, 0, 0, 1, 1], ....: [ 1, -1, 0, 0, 1, 0], ....: [ 0, -1, 0, 0, 0, 1]]); M [ 0 1 -1 0 0 0] [ 0 0 1 1 0 0] [ 1 0 0 1 0 0] [ 0 0 0 0 1 1] [ 1 -1 0 0 1 0] [ 0 -1 0 0 0 1] sage: M1, M2 = M.three_sum_decomposition([0, 1, 2, 4, 5], [0, 1, 2, 3], ....: [4, 5], [0, 1]); M1 [ 0 1 -1 0 0] [ 0 0 1 1 0] [ 1 0 0 1 0] [ 1 -1 0 0 1] [ 0 -1 0 0 1] sage: M2 [-1 1 0 0] [ 0 0 1 1] [ 1 -1 1 0] [ 0 -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(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)]]); M [ 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] >>> M1, M2 = M.three_sum_decomposition([Integer(0), Integer(1), Integer(2), Integer(3)], [Integer(0), Integer(1), Integer(2), Integer(3)], ... [Integer(2), Integer(3)], [Integer(2), Integer(3)]); M1 [ 1 0 1 1 0] [ 0 1 1 1 0] [ 1 0 1 0 1] [ 0 -1 0 -1 1] >>> M2 [ 1 1 0 0] [ 1 0 1 1] [ 0 -1 1 1] [ 1 0 1 0] [ 0 -1 0 1] >>> M = 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)]]); M [-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] >>> M1, M2 = M.three_sum_decomposition([Integer(0), Integer(1), Integer(2), Integer(3)], [Integer(0), Integer(1), Integer(2), Integer(3)], ... [Integer(2), Integer(3)], [Integer(2), Integer(3)]); M1 [-1 0 -1 1 0] [ 0 -1 1 -1 0] [-1 0 -1 0 1] [ 0 -1 0 -1 1] >>> M2 [-1 1 0 0] [-1 0 1 1] [ 0 -1 1 1] [-1 0 1 0] [ 0 -1 0 1] >>> M = 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)]]); M [ 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] >>> M1, M2 = M.three_sum_decomposition([Integer(0), Integer(1), Integer(2), Integer(3)], [Integer(0), Integer(1), Integer(2), Integer(3)], ... [Integer(2), Integer(3)], [Integer(2), Integer(3)]); M1 [ 1 0 1 1 0] [ 0 1 1 1 0] [ 1 0 1 0 1] [ 0 1 0 1 -1] >>> M2 [ 1 1 0 0] [ 1 0 1 -1] [ 0 1 -1 1] [ 1 0 1 0] [ 0 1 0 1] >>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(6), Integer(6), sparse=True), ... [[ Integer(0), Integer(1), -Integer(1), Integer(0), Integer(0), Integer(0)], ... [ Integer(0), Integer(0), Integer(1), Integer(1), 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(1), Integer(0), Integer(0), Integer(1), Integer(0)], ... [ Integer(0), -Integer(1), Integer(0), Integer(0), Integer(0), Integer(1)]]); M [ 0 1 -1 0 0 0] [ 0 0 1 1 0 0] [ 1 0 0 1 0 0] [ 0 0 0 0 1 1] [ 1 -1 0 0 1 0] [ 0 -1 0 0 0 1] >>> M1, M2 = M.three_sum_decomposition([Integer(0), Integer(1), Integer(2), Integer(4), Integer(5)], [Integer(0), Integer(1), Integer(2), Integer(3)], ... [Integer(4), Integer(5)], [Integer(0), Integer(1)]); M1 [ 0 1 -1 0 0] [ 0 0 1 1 0] [ 1 0 0 1 0] [ 1 -1 0 0 1] [ 0 -1 0 0 1] >>> M2 [-1 1 0 0] [ 0 0 1 1] [ 1 -1 1 0] [ 0 -1 0 1]
The given 2-by-2 submatrix should have rank 2:
sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 6, sparse=True), ....: [[ 0, 1, -1, 0, 0, 0], ....: [ 0, 0, 1, 1, 0, 0], ....: [ 1, 0, 0, 1, 0, 0], ....: [ 0, 0, 0, 0, 1, 1], ....: [ 1, 0, -1, 0, 1, 0], ....: [ 0, -1, 0, 0, 0, 1]]) sage: M.three_sum_decomposition(first_rows=[0, 1, 2, 4, 5], ....: first_columns=[0, 1, 2, 3], ....: special_columns=[0, 1]) Traceback (most recent call last): ... RuntimeError: User input error
>>> from sage.all import * >>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(6), Integer(6), sparse=True), ... [[ Integer(0), Integer(1), -Integer(1), Integer(0), Integer(0), Integer(0)], ... [ Integer(0), Integer(0), Integer(1), Integer(1), 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(1), Integer(0), Integer(1), Integer(0)], ... [ Integer(0), -Integer(1), Integer(0), Integer(0), Integer(0), Integer(1)]]) >>> M.three_sum_decomposition(first_rows=[Integer(0), Integer(1), Integer(2), Integer(4), Integer(5)], ... first_columns=[Integer(0), Integer(1), Integer(2), Integer(3)], ... special_columns=[Integer(0), Integer(1)]) Traceback (most recent call last): ... RuntimeError: User input error
For \(\rank(B) = 2\), we can still compute three_sum_decomposition:
sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 6, sparse=True), ....: [[ 1, 1, 0, 0, 0, 0], ....: [ 1, 0, 1, -1, 0, 0], ....: [ 0, 1, 0, -1, 0, 0], ....: [ 0, 0, 0, 1, -1, 0], ....: [ 0, 0, 0, 0, 1, 1], ....: [ 0, 0, 1, 0, 0, 1]]); M [ 1 1 0 0 0 0] [ 1 0 1 -1 0 0] [ 0 1 0 -1 0 0] [ 0 0 0 1 -1 0] [ 0 0 0 0 1 1] [ 0 0 1 0 0 1] sage: M1, M2 = M.three_sum_decomposition([3, 4, 5, 1, 2], [2, 3, 4, 5], ....: [1, 2], [2, 3]); M1 [ 0 1 -1 0 0] [ 0 0 1 1 0] [ 1 0 0 1 0] [ 1 -1 0 0 1] [ 0 -1 0 0 1] sage: M2 [-1 1 0 0] [ 0 0 1 1] [ 1 -1 1 0] [ 0 -1 0 1]
>>> from sage.all import * >>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(6), Integer(6), sparse=True), ... [[ Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0)], ... [ Integer(1), Integer(0), Integer(1), -Integer(1), Integer(0), Integer(0)], ... [ Integer(0), 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(0), Integer(0), Integer(1), Integer(1)], ... [ Integer(0), Integer(0), Integer(1), Integer(0), Integer(0), Integer(1)]]); M [ 1 1 0 0 0 0] [ 1 0 1 -1 0 0] [ 0 1 0 -1 0 0] [ 0 0 0 1 -1 0] [ 0 0 0 0 1 1] [ 0 0 1 0 0 1] >>> M1, M2 = M.three_sum_decomposition([Integer(3), Integer(4), Integer(5), Integer(1), Integer(2)], [Integer(2), Integer(3), Integer(4), Integer(5)], ... [Integer(1), Integer(2)], [Integer(2), Integer(3)]); M1 [ 0 1 -1 0 0] [ 0 0 1 1 0] [ 1 0 0 1 0] [ 1 -1 0 0 1] [ 0 -1 0 0 1] >>> M2 [-1 1 0 0] [ 0 0 1 1] [ 1 -1 1 0] [ 0 -1 0 1]
- two_sum(first_mat, second_mat, first_index, second_index, nonzero_block='top_right')[source]¶
Return the 2-sum matrix constructed from the given matrices
first_matandsecond_mat, with index of the first matrixfirst_indexand index of the second matrixsecond_index.Suppose that
first_indexindicates the last column offirst_matandsecond_indexindicates the first row ofsecond_mat, i.e., the two matrices are\[\begin{split}M_1=\begin{bmatrix} A & a\end{bmatrix}, \qquad M_2=\begin{bmatrix} b^T \\ D\end{bmatrix}.\end{split}\]Then the 2-sum is
\[\begin{split}M_1 \oplus_2 M_2 = \begin{bmatrix} A & ab^T \\ 0 & D \end{bmatrix}.\end{split}\]Suppose that
first_indexindicates the last row offirst_matandsecond_indexindicates the first column ofsecond_mat, i.e., the two matrices are\[\begin{split}M_1=\begin{bmatrix} A \\ c^T\end{bmatrix}, \qquad M_2=\begin{bmatrix} d & D\end{bmatrix}.\end{split}\]Then the 2-sum is
\[\begin{split}M_1 \oplus_2 M_2 = \begin{bmatrix} A & 0 \\ dc^T & D \end{bmatrix}.\end{split}\]The terminology “2-sum” is used in the context of Seymour’s decomposition of totally unimodular matrices and regular matroids, see [Sch1986], Ch. 19.4.
See also
one_sum(),delta_sum(),three_sum(),y_sum(),two_sum_decomposition()INPUT:
first_mat– the first integer matrixsecond_mat– the second integer matrixfirst_index– the column/row index of the first integer matrixsecond_index– the row/column index of the second integer matrixnonzero_block– either"top_right"(default) or"bottom_left"; whether the nonzero block in the 2-sum matrix is located in the top right or bottom left. Ifnonzero_block="top_right",first_indexis the column index of the first integer matrix,second_indexis the row index of the second integer matrix. The outer product of the corresponding column and row form the nonzero top right block of the 2-sum matrix. Ifnonzero_block="bottom_left",first_indexis the row index of the first integer matrix,second_indexis the column index of the second integer matrix. The outer product of the corresponding row and column form the nonzero bottom left block of the 2-sum matrix.
OUTPUT: A
Matrix_cmr_chr_sparseEXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse 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: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 2, 3, sparse=True), ....: [[1, 2, 3], [4, 5, 6]]); M1 [1 2 3] [4 5 6] sage: M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 2, 3, sparse=True), ....: [[7, 8, 9], [-1, -2, -3]]); M2 [ 7 8 9] [-1 -2 -3] sage: Matrix_cmr_chr_sparse.two_sum(M1, M2, 2, 0) [ 1 2|21 24 27] [ 4 5|42 48 54] [-----+--------] [ 0 0|-1 -2 -3] sage: M1.two_sum(M2, 1, 1) [ 1 3| -2 -4 -6] [ 4 6| -5 -10 -15] [-------+-----------] [ 0 0| 7 8 9] sage: M1.two_sum(M2, 1, 1, nonzero_block="bottom_right") Traceback (most recent call last): ... ValueError: ('Unknown two sum mode', 'bottom_right') sage: M1.two_sum(M2, 1, 1, nonzero_block="bottom_left") [ 1 2 3| 0 0] [-----------+-------] [ 32 40 48| 7 9] [ -8 -10 -12| -1 -3] sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 5, 5, sparse=True), ....: [[1, 1, 0, 0, 0], ....: [1, 0, 1,-1, 1], ....: [0,-1, 1, 0,-1], ....: [0, 0,-1, 1, 0], ....: [0, 1, 1, 0, 1]]); M1 [ 1 1 0 0 0] [ 1 0 1 -1 1] [ 0 -1 1 0 -1] [ 0 0 -1 1 0] [ 0 1 1 0 1] sage: M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 5, 5, sparse=True), ....: [[1,-1, 1, 0, 0], ....: [1, 1, 1, 1,-1], ....: [0, 0,-1, 0, 1], ....: [1, 0, 0,-1, 0], ....: [0, 1, 0, 0, 1]]); M2 [ 1 -1 1 0 0] [ 1 1 1 1 -1] [ 0 0 -1 0 1] [ 1 0 0 -1 0] [ 0 1 0 0 1] sage: M1.two_sum(M2, 1, 2, nonzero_block="bottom_left") [ 1 1 0 0 0| 0 0 0 0] [ 0 -1 1 0 -1| 0 0 0 0] [ 0 0 -1 1 0| 0 0 0 0] [ 0 1 1 0 1| 0 0 0 0] [--------------+-----------] [ 1 0 1 -1 1| 1 -1 0 0] [ 1 0 1 -1 1| 1 1 1 -1] [-1 0 -1 1 -1| 0 0 0 1] [ 0 0 0 0 0| 1 0 -1 0] [ 0 0 0 0 0| 0 1 0 1] sage: M1.two_sum(M2, 4, 0) [ 1 1 0 0| 0 0 0 0 0] [ 1 0 1 -1| 1 -1 1 0 0] [ 0 -1 1 0|-1 1 -1 0 0] [ 0 0 -1 1| 0 0 0 0 0] [ 0 1 1 0| 1 -1 1 0 0] [-----------+--------------] [ 0 0 0 0| 1 1 1 1 -1] [ 0 0 0 0| 0 0 -1 0 1] [ 0 0 0 0| 1 0 0 -1 0] [ 0 0 0 0| 0 1 0 0 1]
>>> from sage.all import * >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> 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] >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(2), Integer(3), sparse=True), ... [[Integer(1), Integer(2), Integer(3)], [Integer(4), Integer(5), Integer(6)]]); M1 [1 2 3] [4 5 6] >>> M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(2), Integer(3), sparse=True), ... [[Integer(7), Integer(8), Integer(9)], [-Integer(1), -Integer(2), -Integer(3)]]); M2 [ 7 8 9] [-1 -2 -3] >>> Matrix_cmr_chr_sparse.two_sum(M1, M2, Integer(2), Integer(0)) [ 1 2|21 24 27] [ 4 5|42 48 54] [-----+--------] [ 0 0|-1 -2 -3] >>> M1.two_sum(M2, Integer(1), Integer(1)) [ 1 3| -2 -4 -6] [ 4 6| -5 -10 -15] [-------+-----------] [ 0 0| 7 8 9] >>> M1.two_sum(M2, Integer(1), Integer(1), nonzero_block="bottom_right") Traceback (most recent call last): ... ValueError: ('Unknown two sum mode', 'bottom_right') >>> M1.two_sum(M2, Integer(1), Integer(1), nonzero_block="bottom_left") [ 1 2 3| 0 0] [-----------+-------] [ 32 40 48| 7 9] [ -8 -10 -12| -1 -3] >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(5), Integer(5), sparse=True), ... [[Integer(1), Integer(1), Integer(0), Integer(0), Integer(0)], ... [Integer(1), Integer(0), Integer(1),-Integer(1), Integer(1)], ... [Integer(0),-Integer(1), Integer(1), Integer(0),-Integer(1)], ... [Integer(0), Integer(0),-Integer(1), Integer(1), Integer(0)], ... [Integer(0), Integer(1), Integer(1), Integer(0), Integer(1)]]); M1 [ 1 1 0 0 0] [ 1 0 1 -1 1] [ 0 -1 1 0 -1] [ 0 0 -1 1 0] [ 0 1 1 0 1] >>> M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(5), Integer(5), sparse=True), ... [[Integer(1),-Integer(1), Integer(1), Integer(0), Integer(0)], ... [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(0),-Integer(1), Integer(0)], ... [Integer(0), Integer(1), Integer(0), Integer(0), Integer(1)]]); M2 [ 1 -1 1 0 0] [ 1 1 1 1 -1] [ 0 0 -1 0 1] [ 1 0 0 -1 0] [ 0 1 0 0 1] >>> M1.two_sum(M2, Integer(1), Integer(2), nonzero_block="bottom_left") [ 1 1 0 0 0| 0 0 0 0] [ 0 -1 1 0 -1| 0 0 0 0] [ 0 0 -1 1 0| 0 0 0 0] [ 0 1 1 0 1| 0 0 0 0] [--------------+-----------] [ 1 0 1 -1 1| 1 -1 0 0] [ 1 0 1 -1 1| 1 1 1 -1] [-1 0 -1 1 -1| 0 0 0 1] [ 0 0 0 0 0| 1 0 -1 0] [ 0 0 0 0 0| 0 1 0 1] >>> M1.two_sum(M2, Integer(4), Integer(0)) [ 1 1 0 0| 0 0 0 0 0] [ 1 0 1 -1| 1 -1 1 0 0] [ 0 -1 1 0|-1 1 -1 0 0] [ 0 0 -1 1| 0 0 0 0 0] [ 0 1 1 0| 1 -1 1 0 0] [-----------+--------------] [ 0 0 0 0| 1 1 1 1 -1] [ 0 0 0 0| 0 0 -1 0 1] [ 0 0 0 0| 1 0 0 -1 0] [ 0 0 0 0| 0 1 0 0 1]
- two_sum_decomposition(A_rows, A_columns)[source]¶
Decompose the matrix into two child matrices using the two sum decomposition with specified indices.
The input matrix \(M\) must have a 2-separation that can be reordered to look like \(M = \begin{bmatrix} A & B \\ C & D \end{bmatrix}\), where \(\rank(B) + \rank(C) = 1\).
If \(\rank(B) = 0\), then the two components of the 2-sum are matrices
\[\begin{split}M_1 = \begin{bmatrix} A \\ c^T \end{bmatrix}, \qquad M_2 = \begin{bmatrix} d & D \end{bmatrix}\end{split}\]such that \(C = d c^T\) holds and such that \(c^T\) is an actual row of \(M\).
Otherwise, the two components of the 2-sum are matrices
\[\begin{split}M_1 = \begin{bmatrix} A & a \end{bmatrix}, \qquad M_2 = \begin{bmatrix} b^T \\ D \end{bmatrix}\end{split}\]such that \(B = a b^T\) holds and such that \(a\) is an actual column of \(M\).
See also
INPUT:
A_rows– list of row indices for the submatrix AA_columns– list of column indices for the submatrix A
OUTPUT: A tuple of two
Matrix_cmr_chr_sparseEXAMPLES:
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, 0, 1, -1, -1, 1, 1, 0, 0], ....: [ 0, -1, 1, 0, 1, -1, -1, 0, 0], ....: [ 0, 0, -1, 1, 0, 0, 0, 0, 0], ....: [ 0, 1, 1, 0, -1, 1, 1, 0, 0], ....: [ 0, 0, 0, 0, 1, 1, 1, 1, -1], ....: [ 0, 0, 0, 0, 0, 0, -1, 0, 1], ....: [ 0, 0, 0, 0, 1, 0, 0, -1, 0], ....: [ 0, 0, 0, 0, 0, 1, 0, 0, 1]]); M [ 1 1 0 0 0 0 0 0 0] [ 1 0 1 -1 -1 1 1 0 0] [ 0 -1 1 0 1 -1 -1 0 0] [ 0 0 -1 1 0 0 0 0 0] [ 0 1 1 0 -1 1 1 0 0] [ 0 0 0 0 1 1 1 1 -1] [ 0 0 0 0 0 0 -1 0 1] [ 0 0 0 0 1 0 0 -1 0] [ 0 0 0 0 0 1 0 0 1] sage: M1, M2 = M.two_sum_decomposition([0, 1, 2, 3, 4], [0, 1, 2, 3]); M1 [ 1 1 0 0 0] [ 1 0 1 -1 -1] [ 0 -1 1 0 1] [ 0 0 -1 1 0] [ 0 1 1 0 -1] sage: M2 [ 1 -1 -1 0 0] [ 1 1 1 1 -1] [ 0 0 -1 0 1] [ 1 0 0 -1 0] [ 0 1 0 0 1] sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 9, 9, sparse=True), ....: [[ 1, 1, 0, 0, 0, 0, 0, 0, 0], ....: [ 1, 0, 1, -1, -1, 1, 1, 0, 0], ....: [ 0, -1, 1, 0, 1, -1, -1, 0, 0], ....: [ 0, 0, -1, 1, 0, 0, 0, 0, 0], ....: [ 0, 1, 1, 0, -1, 1, 1, 0, 0], ....: [ 0, 0, 0, 0, 1, 1, 1, 1, -1], ....: [ 0, 0, 0, 0, 0, 0, -1, 0, 1], ....: [ 0, 0, 0, 0, 1, 0, 0, -1, 0], ....: [ 0, 0, 0, 0, 0, 1, 0, 0, 1]]); M [ 1 1 0 0 0 0 0 0 0] [ 1 0 1 -1 -1 1 1 0 0] [ 0 -1 1 0 1 -1 -1 0 0] [ 0 0 -1 1 0 0 0 0 0] [ 0 1 1 0 -1 1 1 0 0] [ 0 0 0 0 1 1 1 1 -1] [ 0 0 0 0 0 0 -1 0 1] [ 0 0 0 0 1 0 0 -1 0] [ 0 0 0 0 0 1 0 0 1] sage: M1, M2 = M.two_sum_decomposition([5, 6, 7, 8], [4, 5, 6, 7, 8]); M1 [ 1 1 1 1 -1] [ 0 0 -1 0 1] [ 1 0 0 -1 0] [ 0 1 0 0 1] [-1 1 1 0 0] sage: M2 [ 0 1 1 0 0] [ 1 1 0 1 -1] [-1 0 -1 1 0] [ 0 0 0 -1 1] [ 1 0 1 1 0] sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 9, 9, sparse=True), ....: [[ 1, 1, 0, 0, 0, 0, 0, 0, 0], ....: [ 0,-1, 1, 0,-1, 0, 0, 0, 0], ....: [ 0, 0,-1, 1, 0, 0, 0, 0, 0], ....: [ 0, 1, 1, 0, 1, 0, 0, 0, 0], ....: [ 1, 0, 1,-1, 1, 1,-1, 0, 0], ....: [ 1, 0, 1,-1, 1, 1, 1, 1,-1], ....: [-1, 0,-1, 1,-1, 0, 0, 0, 1], ....: [ 0, 0, 0, 0, 0, 1, 0,-1, 0], ....: [ 0, 0, 0, 0, 0, 0, 1, 0, 1]]); M [ 1 1 0 0 0 0 0 0 0] [ 0 -1 1 0 -1 0 0 0 0] [ 0 0 -1 1 0 0 0 0 0] [ 0 1 1 0 1 0 0 0 0] [ 1 0 1 -1 1 1 -1 0 0] [ 1 0 1 -1 1 1 1 1 -1] [-1 0 -1 1 -1 0 0 0 1] [ 0 0 0 0 0 1 0 -1 0] [ 0 0 0 0 0 0 1 0 1] sage: M1, M2 = M.two_sum_decomposition([0, 1, 2, 3], [0, 1, 2, 3, 4]); M1 [ 1 1 0 0 0] [ 0 -1 1 0 -1] [ 0 0 -1 1 0] [ 0 1 1 0 1] [ 1 0 1 -1 1] sage: M2 [ 1 1 -1 0 0] [ 1 1 1 1 -1] [-1 0 0 0 1] [ 0 1 0 -1 0] [ 0 0 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(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(0), Integer(1), -Integer(1), -Integer(1), Integer(1), Integer(1), Integer(0), Integer(0)], ... [ Integer(0), -Integer(1), Integer(1), Integer(0), Integer(1), -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(1), 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(1), 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(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(0), Integer(0), Integer(1)]]); M [ 1 1 0 0 0 0 0 0 0] [ 1 0 1 -1 -1 1 1 0 0] [ 0 -1 1 0 1 -1 -1 0 0] [ 0 0 -1 1 0 0 0 0 0] [ 0 1 1 0 -1 1 1 0 0] [ 0 0 0 0 1 1 1 1 -1] [ 0 0 0 0 0 0 -1 0 1] [ 0 0 0 0 1 0 0 -1 0] [ 0 0 0 0 0 1 0 0 1] >>> M1, M2 = M.two_sum_decomposition([Integer(0), Integer(1), Integer(2), Integer(3), Integer(4)], [Integer(0), Integer(1), Integer(2), Integer(3)]); M1 [ 1 1 0 0 0] [ 1 0 1 -1 -1] [ 0 -1 1 0 1] [ 0 0 -1 1 0] [ 0 1 1 0 -1] >>> M2 [ 1 -1 -1 0 0] [ 1 1 1 1 -1] [ 0 0 -1 0 1] [ 1 0 0 -1 0] [ 0 1 0 0 1] >>> 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(0), Integer(1), -Integer(1), -Integer(1), Integer(1), Integer(1), Integer(0), Integer(0)], ... [ Integer(0), -Integer(1), Integer(1), Integer(0), Integer(1), -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(1), 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(1), 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(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(0), Integer(0), Integer(1)]]); M [ 1 1 0 0 0 0 0 0 0] [ 1 0 1 -1 -1 1 1 0 0] [ 0 -1 1 0 1 -1 -1 0 0] [ 0 0 -1 1 0 0 0 0 0] [ 0 1 1 0 -1 1 1 0 0] [ 0 0 0 0 1 1 1 1 -1] [ 0 0 0 0 0 0 -1 0 1] [ 0 0 0 0 1 0 0 -1 0] [ 0 0 0 0 0 1 0 0 1] >>> M1, M2 = M.two_sum_decomposition([Integer(5), Integer(6), Integer(7), Integer(8)], [Integer(4), Integer(5), Integer(6), Integer(7), Integer(8)]); M1 [ 1 1 1 1 -1] [ 0 0 -1 0 1] [ 1 0 0 -1 0] [ 0 1 0 0 1] [-1 1 1 0 0] >>> M2 [ 0 1 1 0 0] [ 1 1 0 1 -1] [-1 0 -1 1 0] [ 0 0 0 -1 1] [ 1 0 1 1 0] >>> 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(0),-Integer(1), Integer(1), Integer(0),-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(0)], ... [ Integer(0), Integer(1), Integer(1), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0)], ... [ Integer(1), Integer(0), Integer(1),-Integer(1), Integer(1), Integer(1),-Integer(1), Integer(0), Integer(0)], ... [ Integer(1), Integer(0), Integer(1),-Integer(1), Integer(1), 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(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0),-Integer(1), Integer(0)], ... [ Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0), Integer(1)]]); M [ 1 1 0 0 0 0 0 0 0] [ 0 -1 1 0 -1 0 0 0 0] [ 0 0 -1 1 0 0 0 0 0] [ 0 1 1 0 1 0 0 0 0] [ 1 0 1 -1 1 1 -1 0 0] [ 1 0 1 -1 1 1 1 1 -1] [-1 0 -1 1 -1 0 0 0 1] [ 0 0 0 0 0 1 0 -1 0] [ 0 0 0 0 0 0 1 0 1] >>> M1, M2 = M.two_sum_decomposition([Integer(0), Integer(1), Integer(2), Integer(3)], [Integer(0), Integer(1), Integer(2), Integer(3), Integer(4)]); M1 [ 1 1 0 0 0] [ 0 -1 1 0 -1] [ 0 0 -1 1 0] [ 0 1 1 0 1] [ 1 0 1 -1 1] >>> M2 [ 1 1 -1 0 0] [ 1 1 1 1 -1] [-1 0 0 0 1] [ 0 1 0 -1 0] [ 0 0 1 0 1]
- y_sum(first_mat, second_mat, first_rows=[-2, -1], first_column=-1, second_rows=[0, 1], second_column=0, algorithm='cmr', sign_verify=False)[source]¶
Return the Y-sum matrix constructed from the given matrices
first_matandsecond_mat. In this case, the matrices are\[\begin{split}M_1 = \begin{bmatrix} A & a \\ c^T & 0 \\ c^T & \varepsilon \end{bmatrix}, \qquad M_2 = \begin{bmatrix} \varepsilon & b^T \\ 0 & b^T \\ d & D \end{bmatrix}.\end{split}\]Then the Y-sum is the matrix
\[\begin{split}M_1 \oplus_3 M_2 = \begin{bmatrix} A & a b^T \\ d c^T & D \end{bmatrix}.\end{split}\]The terminology “3-sum” originates from Seymour’s decomposition of regular matroids. In the context of totally unimodular matrices, there are different interpretations in the form of matrix operations for \(\begin{bmatrix} A & B \\ C & D \end{bmatrix}\) satisfying \(\rank(B) + \rank(C) = 2\). Three types of 3-sum operations are implemented in CMR: \(\Delta\)-sum, 3-sum, and Y-sum. The Y-sum can be derived from the \(\Delta\)-sum of the transpose of the matrices.
For 3-sum, one of \(B\) and \(C\) is a zero matrix, also known as “concentrated_rank”.
For \(\Delta\)-sum and Y-sum, both \(B\) and \(C\) are of rank 1, also known as “distributed_ranks”.
See also
_y_sum_cmr(),y_sum_decomposition(),is_y_sum(),one_sum(),two_sum(),delta_sum(),three_sum()INPUT:
first_mat– the first integer matrix \(M_1\)second_mat– the second integer matrix \(M_2\)first_rows– the row indices of \(c^T\) in \(M_1\)first_column– the column index of \(a\) in \(M_1\)second_rows– the row indices of \(b^T\) in \(M_2\)second_column– the column index of \(d\) in \(M_2\)algorithm–"cmr"or"direct"Ifalgorithm="cmr", then use_y_sum_cmr(); Ifalgorithm="direct", then construct three sum directly. Both options will check the given two matrices and the related indices satisfying the requirements of Y-sum.sign_verify– boolean (default:False); whether to check the sign consistency of \(\varepsilon\). Seeis_y_sum(),y_sum_decomposition().
OUTPUT: A
Matrix_cmr_chr_sparseEXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 5, sparse=True), ....: [[1, 1, 0, 0, 0], ....: [0,-1, 0,-1, 1], ....: [0, 0, 1, 0,-1], ....: [0, 1, 0, 1, 1], ....: [1, 0,-1, 1, 0], ....: [1, 0,-1, 1, 1],]); M1 [ 1 1 0 0 0] [ 0 -1 0 -1 1] [ 0 0 1 0 -1] [ 0 1 0 1 1] [ 1 0 -1 1 0] [ 1 0 -1 1 1] sage: M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 5, sparse=True), ....: [[ 1, 1, 1, 1,-1], ....: [ 0, 1, 1, 1,-1], ....: [-1, 1, 1, 0, 0], ....: [ 0, 0,-1, 0, 1], ....: [ 0, 1, 0,-1, 0], ....: [ 1, 0, 0, 0, 1]]); M2 [ 1 1 1 1 -1] [ 0 1 1 1 -1] [-1 1 1 0 0] [ 0 0 -1 0 1] [ 0 1 0 -1 0] [ 1 0 0 0 1] sage: Matrix_cmr_chr_sparse.y_sum(M1, M2) [ 1 1 0 0 0 0 0 0] [ 0 -1 0 -1 1 1 1 -1] [ 0 0 1 0 -1 -1 -1 1] [ 0 1 0 1 1 1 1 -1] [-1 0 1 -1 1 1 0 0] [ 0 0 0 0 0 -1 0 1] [ 0 0 0 0 1 0 -1 0] [ 1 0 -1 1 0 0 0 1] sage: M1.y_sum(M2, [-2, -1], 4, [0, 1], 1) Traceback (most recent call last): ... RuntimeError: Invalid matrix structure sage: M1.y_sum(M2, [-2, -1], 4, [0, 1], 1, algorithm="direct") Traceback (most recent call last): ... ValueError: The given two matrices and related indices do not satisfy the rule for y sum!
>>> from sage.all import * >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse >>> M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(6), Integer(5), sparse=True), ... [[Integer(1), Integer(1), Integer(0), Integer(0), Integer(0)], ... [Integer(0),-Integer(1), Integer(0),-Integer(1), Integer(1)], ... [Integer(0), Integer(0), Integer(1), Integer(0),-Integer(1)], ... [Integer(0), Integer(1), Integer(0), Integer(1), Integer(1)], ... [Integer(1), Integer(0),-Integer(1), Integer(1), Integer(0)], ... [Integer(1), Integer(0),-Integer(1), Integer(1), Integer(1)],]); M1 [ 1 1 0 0 0] [ 0 -1 0 -1 1] [ 0 0 1 0 -1] [ 0 1 0 1 1] [ 1 0 -1 1 0] [ 1 0 -1 1 1] >>> M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(6), Integer(5), sparse=True), ... [[ Integer(1), Integer(1), Integer(1), Integer(1),-Integer(1)], ... [ Integer(0), Integer(1), Integer(1), Integer(1),-Integer(1)], ... [-Integer(1), Integer(1), Integer(1), Integer(0), Integer(0)], ... [ Integer(0), Integer(0),-Integer(1), Integer(0), Integer(1)], ... [ Integer(0), Integer(1), Integer(0),-Integer(1), Integer(0)], ... [ Integer(1), Integer(0), Integer(0), Integer(0), Integer(1)]]); M2 [ 1 1 1 1 -1] [ 0 1 1 1 -1] [-1 1 1 0 0] [ 0 0 -1 0 1] [ 0 1 0 -1 0] [ 1 0 0 0 1] >>> Matrix_cmr_chr_sparse.y_sum(M1, M2) [ 1 1 0 0 0 0 0 0] [ 0 -1 0 -1 1 1 1 -1] [ 0 0 1 0 -1 -1 -1 1] [ 0 1 0 1 1 1 1 -1] [-1 0 1 -1 1 1 0 0] [ 0 0 0 0 0 -1 0 1] [ 0 0 0 0 1 0 -1 0] [ 1 0 -1 1 0 0 0 1] >>> M1.y_sum(M2, [-Integer(2), -Integer(1)], Integer(4), [Integer(0), Integer(1)], Integer(1)) Traceback (most recent call last): ... RuntimeError: Invalid matrix structure >>> M1.y_sum(M2, [-Integer(2), -Integer(1)], Integer(4), [Integer(0), Integer(1)], Integer(1), algorithm="direct") Traceback (most recent call last): ... ValueError: The given two matrices and related indices do not satisfy the rule for y sum!
sign_verify=Truewill check the sign consistency:sage: M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 4, 3, sparse=True), ....: [[1, 1, 0], ....: [1, 0, 1], ....: [0, 1, 0], ....: [0, 1,-1]]); sage: M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 4, 3, sparse=True), ....: [[-1, 1, 0], ....: [ 0, 1, 0], ....: [ 1, 0, 1], ....: [ 0, 1, 1]]); sage: M1.y_sum(M2, sign_verify=True) [1 1 0 0] [1 0 1 0] [0 1 0 1] [0 0 1 1] sage: M1.y_sum(M2, algorithm="direct", sign_verify=True) [1 1 0 0] [1 0 1 0] [0 1 0 1] [0 0 1 1] sage: M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 4, 3, sparse=True), ....: [[1, 1, 0], ....: [1, 0, 1], ....: [0, 1, 0], ....: [0, 1, 1]]); sage: M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 4, 3, sparse=True), ....: [[1, 1, 0], ....: [0, 1, 0], ....: [1, 0, 1], ....: [0, 1, 1]]); sage: M1.y_sum(M2, sign_verify=True) Traceback (most recent call last): ... ValueError: epsilon in first_mat should be -1. epsilon in second_mat should be -1. sage: M1.y_sum(M2, algorithm="direct", sign_verify=True) Traceback (most recent call last): ... ValueError: epsilon in first_mat should be -1. epsilon in second_mat should be -1.
>>> from sage.all import * >>> M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(4), Integer(3), sparse=True), ... [[Integer(1), Integer(1), Integer(0)], ... [Integer(1), Integer(0), Integer(1)], ... [Integer(0), Integer(1), Integer(0)], ... [Integer(0), Integer(1),-Integer(1)]]); >>> M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(4), Integer(3), sparse=True), ... [[-Integer(1), Integer(1), Integer(0)], ... [ Integer(0), Integer(1), Integer(0)], ... [ Integer(1), Integer(0), Integer(1)], ... [ Integer(0), Integer(1), Integer(1)]]); >>> M1.y_sum(M2, sign_verify=True) [1 1 0 0] [1 0 1 0] [0 1 0 1] [0 0 1 1] >>> M1.y_sum(M2, algorithm="direct", sign_verify=True) [1 1 0 0] [1 0 1 0] [0 1 0 1] [0 0 1 1] >>> M1 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(4), Integer(3), sparse=True), ... [[Integer(1), Integer(1), Integer(0)], ... [Integer(1), Integer(0), Integer(1)], ... [Integer(0), Integer(1), Integer(0)], ... [Integer(0), Integer(1), Integer(1)]]); >>> M2 = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(4), Integer(3), sparse=True), ... [[Integer(1), Integer(1), Integer(0)], ... [Integer(0), Integer(1), Integer(0)], ... [Integer(1), Integer(0), Integer(1)], ... [Integer(0), Integer(1), Integer(1)]]); >>> M1.y_sum(M2, sign_verify=True) Traceback (most recent call last): ... ValueError: epsilon in first_mat should be -1. epsilon in second_mat should be -1. >>> M1.y_sum(M2, algorithm="direct", sign_verify=True) Traceback (most recent call last): ... ValueError: epsilon in first_mat should be -1. epsilon in second_mat should be -1.
- y_sum_decomposition(A_rows, A_columns)[source]¶
Decompose the matrix into two child matrices using the Y-sum decomposition with specified indices.
Let \(M\) denote the matrix given by
self. Then\[\begin{split}M = \begin{bmatrix} A & a b^T \\ d c^T & D \end{bmatrix},\end{split}\]where \(a, b, c, d\) are vectors and \(A, D\) are submatrices. The two components \(M_1\) and \(M_2\) of the Y-sum, given by
first_matandsecond_mat, must be of the form\[\begin{split}M_1 = \begin{bmatrix} A & a \\ c^T & 0 \\ c^T & \varepsilon \end{bmatrix}, \qquad M_2 = \begin{bmatrix} \varepsilon & b^T \\ 0 & b^T \\ d & D \end{bmatrix}.\end{split}\]The value of \(\varepsilon \in \{-1,+1\}\) must be so that there exists a singular submatrix of \(M_1\) with exactly two nonzeros per row and per column that covers the top-left \(\varepsilon\)-entry. Therefore, \(M\) is totally unimodular if and only if both \(M_1\) and \(M_2\) are totally unimodular.
If \(M\) is not totally unimodular, then \(\varepsilon\) may not be unique, and the algorithm just finds one choice such that at least one of \(M_1\) and \(M_2\) is not totally unimodular.
See also
INPUT:
A_rows– list of row indices for the submatrix \(A\)A_columns– list of column indices for the submatrix \(A\)
OUTPUT: A tuple of two
Matrix_cmr_chr_sparseEXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 6, 6, sparse=True), ....: [[1, 1, 0, 0, 0, 0], ....: [0,-1, 0,-1, 1, 1], ....: [0, 0, 1, 0,-1,-1], ....: [0, 1, 0, 1, 1, 1], ....: [1, 0,-1, 1, 0, 1], ....: [1, 0,-1, 1, 1, 1]]); M [ 1 1 0 0 0 0] [ 0 -1 0 -1 1 1] [ 0 0 1 0 -1 -1] [ 0 1 0 1 1 1] [ 1 0 -1 1 0 1] [ 1 0 -1 1 1 1] sage: M1, M2 = M.y_sum_decomposition([0, 1, 2, 3], [0, 1, 2, 3]); M1 [ 1 1 0 0 0] [ 0 -1 0 -1 1] [ 0 0 1 0 -1] [ 0 1 0 1 1] [ 1 0 -1 1 0] [ 1 0 -1 1 1] sage: M2 [1 1 1] [0 1 1] [1 0 1] [1 1 1]
>>> 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(6), sparse=True), ... [[Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0)], ... [Integer(0),-Integer(1), Integer(0),-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(1), Integer(1), Integer(1)], ... [Integer(1), Integer(0),-Integer(1), Integer(1), Integer(0), Integer(1)], ... [Integer(1), Integer(0),-Integer(1), Integer(1), Integer(1), Integer(1)]]); M [ 1 1 0 0 0 0] [ 0 -1 0 -1 1 1] [ 0 0 1 0 -1 -1] [ 0 1 0 1 1 1] [ 1 0 -1 1 0 1] [ 1 0 -1 1 1 1] >>> M1, M2 = M.y_sum_decomposition([Integer(0), Integer(1), Integer(2), Integer(3)], [Integer(0), Integer(1), Integer(2), Integer(3)]); M1 [ 1 1 0 0 0] [ 0 -1 0 -1 1] [ 0 0 1 0 -1] [ 0 1 0 1 1] [ 1 0 -1 1 0] [ 1 0 -1 1 1] >>> M2 [1 1 1] [0 1 1] [1 0 1] [1 1 1]
- class sage.matrix.matrix_cmr_sparse.Matrix_cmr_sparse[source]¶
Bases:
Matrix_sparseBase class for sparse matrices implemented in CMR
EXAMPLES:
sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_sparse, Matrix_cmr_chr_sparse sage: M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 2, 3, sparse=True), ....: [[1, 2, 3], [4, 0, 6]]) sage: isinstance(M, Matrix_cmr_sparse) True
>>> from sage.all import * >>> from sage.matrix.matrix_cmr_sparse import Matrix_cmr_sparse, Matrix_cmr_chr_sparse >>> M = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, Integer(2), Integer(3), sparse=True), ... [[Integer(1), Integer(2), Integer(3)], [Integer(4), Integer(0), Integer(6)]]) >>> isinstance(M, Matrix_cmr_sparse) True