Sparse integer matrices

AUTHORS:

  • William Stein (2007-02-21)

  • Soroosh Yazdani (2007-02-21)

class sage.matrix.matrix_integer_sparse.Matrix_integer_sparse[source]

Bases: Matrix_sparse

Create a sparse matrix over the integers.

INPUT:

  • parent – a matrix space over ZZ

  • entries – see matrix()

  • copy – ignored (for backwards compatibility)

  • coerce – if False, assume without checking that the entries are of type Integer

charpoly(var='x', algorithm=None)[source]

Return the characteristic polynomial of this matrix.

INPUT:

EXAMPLES:

sage: M = MatrixSpace(ZZ, 4, sparse=True)
sage: m = M()
sage: m[0,0] = m[1,2] = m[2,3] = m[3,3] = 1
sage: m[0,2] = m[1,3] = m[2,0] = m[3,0] = -3
sage: m[1,1] = 2
sage: m
[ 1  0 -3  0]
[ 0  2  1 -3]
[-3  0  0  1]
[-3  0  0  1]
sage: m.charpoly()
x^4 - 4*x^3 - 4*x^2 + 16*x

>>> from sage.all import *
>>> M = MatrixSpace(ZZ, Integer(4), sparse=True)
>>> m = M()
>>> m[Integer(0),Integer(0)] = m[Integer(1),Integer(2)] = m[Integer(2),Integer(3)] = m[Integer(3),Integer(3)] = Integer(1)
>>> m[Integer(0),Integer(2)] = m[Integer(1),Integer(3)] = m[Integer(2),Integer(0)] = m[Integer(3),Integer(0)] = -Integer(3)
>>> m[Integer(1),Integer(1)] = Integer(2)
>>> m
[ 1  0 -3  0]
[ 0  2  1 -3]
[-3  0  0  1]
[-3  0  0  1]
>>> m.charpoly()
x^4 - 4*x^3 - 4*x^2 + 16*x

M = MatrixSpace(ZZ, 4, sparse=True)
m = M()
m[0,0] = m[1,2] = m[2,3] = m[3,3] = 1
m[0,2] = m[1,3] = m[2,0] = m[3,0] = -3
m[1,1] = 2
m
m.charpoly()
elementary_divisors(algorithm='pari')[source]

Return the elementary divisors of self, in order.

The elementary divisors are the invariants of the finite abelian group that is the cokernel of left multiplication by this matrix. They are ordered in reverse by divisibility.

INPUT:

  • self – matrix

  • algorithm – (default: 'pari')

    • ‘pari’: works robustly, but is slower

    • ‘linbox’ – use linbox (currently off, broken)

OUTPUT: list of integers

EXAMPLES:

sage: matrix(3, range(9),sparse=True).elementary_divisors()
[1, 3, 0]
sage: M = matrix(ZZ, 3, [1,5,7, 3,6,9, 0,1,2], sparse=True)
sage: M.elementary_divisors()
[1, 1, 6]

>>> from sage.all import *
>>> matrix(Integer(3), range(Integer(9)),sparse=True).elementary_divisors()
[1, 3, 0]
>>> M = matrix(ZZ, Integer(3), [Integer(1),Integer(5),Integer(7), Integer(3),Integer(6),Integer(9), Integer(0),Integer(1),Integer(2)], sparse=True)
>>> M.elementary_divisors()
[1, 1, 6]

matrix(3, range(9),sparse=True).elementary_divisors()
M = matrix(ZZ, 3, [1,5,7, 3,6,9, 0,1,2], sparse=True)
M.elementary_divisors()

This returns a copy, which is safe to change:

sage: edivs = M.elementary_divisors()
sage: edivs.pop()
6
sage: M.elementary_divisors()
[1, 1, 6]

>>> from sage.all import *
>>> edivs = M.elementary_divisors()
>>> edivs.pop()
6
>>> M.elementary_divisors()
[1, 1, 6]

edivs = M.elementary_divisors()
edivs.pop()
M.elementary_divisors()

See also

smith_form()

hermite_form(algorithm='default', cutoff=0, **kwds)[source]

Return the echelon form of self.

Note

This row reduction does not use division if the matrix is not over a field (e.g., if the matrix is over the integers). If you want to calculate the echelon form using division, then use rref(), which assumes that the matrix entries are in a field (specifically, the field of fractions of the base ring of the matrix).

INPUT:

  • algorithm – string. Which algorithm to use. Choices are

    • 'default': Let Sage choose an algorithm (default).

    • 'classical': Gauss elimination.

    • 'partial_pivoting': Gauss elimination, using partial pivoting (if base ring has absolute value)

    • 'scaled_partial_pivoting' – Gauss elimination, using scaled partial pivoting (if base ring has absolute value)

    • 'scaled_partial_pivoting_valuation': Gauss elimination, using scaled partial pivoting (if base ring has valuation)

    • 'strassen': use a Strassen divide and conquer algorithm (if available)

  • cutoff – integer; only used if the Strassen algorithm is selected

  • transformation – boolean; whether to also return the transformation matrix. Some matrix backends do not provide this information, in which case this option is ignored.

OUTPUT:

The reduced row echelon form of self, as an immutable matrix. Note that self is not changed by this command. Use echelonize() to change self in place.

If the optional parameter transformation=True is specified, the output consists of a pair \((E,T)\) of matrices where \(E\) is the echelon form of self and \(T\) is the transformation matrix.

EXAMPLES:

sage: MS = MatrixSpace(GF(19), 2, 3)
sage: C = MS.matrix([1,2,3,4,5,6])
sage: C.rank()
2
sage: C.nullity()
0
sage: C.echelon_form()
[ 1  0 18]
[ 0  1  2]

>>> from sage.all import *
>>> MS = MatrixSpace(GF(Integer(19)), Integer(2), Integer(3))
>>> C = MS.matrix([Integer(1),Integer(2),Integer(3),Integer(4),Integer(5),Integer(6)])
>>> C.rank()
2
>>> C.nullity()
0
>>> C.echelon_form()
[ 1  0 18]
[ 0  1  2]

MS = MatrixSpace(GF(19), 2, 3)
C = MS.matrix([1,2,3,4,5,6])
C.rank()
C.nullity()
C.echelon_form()

The matrix library used for \(\ZZ/p\)-matrices does not return the transformation matrix, so the transformation option is ignored:

sage: C.echelon_form(transformation=True)
[ 1  0 18]
[ 0  1  2]

sage: D = matrix(ZZ, 2, 3, [1,2,3,4,5,6])
sage: D.echelon_form(transformation=True)
(
[1 2 3]  [ 1  0]
[0 3 6], [ 4 -1]
)
sage: E, T = D.echelon_form(transformation=True)
sage: T*D == E
True

>>> from sage.all import *
>>> C.echelon_form(transformation=True)
[ 1  0 18]
[ 0  1  2]

>>> D = matrix(ZZ, Integer(2), Integer(3), [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5),Integer(6)])
>>> D.echelon_form(transformation=True)
(
[1 2 3]  [ 1  0]
[0 3 6], [ 4 -1]
)
>>> E, T = D.echelon_form(transformation=True)
>>> T*D == E
True

C.echelon_form(transformation=True)
D = matrix(ZZ, 2, 3, [1,2,3,4,5,6])
D.echelon_form(transformation=True)
E, T = D.echelon_form(transformation=True)
T*D == E
minpoly(var='x', algorithm=None)[source]

Return the minimal polynomial of this matrix.

INPUT:

  • var – (default: 'x') the name of the variable of the polynomial

  • algorithm – (default: None) one of None, 'linbox', or an algorithm accepted by sage.matrix.matrix_sparse.Matrix_sparse.minpoly()

EXAMPLES:

sage: M = MatrixSpace(ZZ, 4, sparse=True)
sage: m = M({(0, 0):2, (1, 1):1, (2, 1):-8, (2, 2):2, (2, 3):-1, (3, 3):1})
sage: m
[ 2  0  0  0]
[ 0  1  0  0]
[ 0 -8  2 -1]
[ 0  0  0  1]
sage: m.minpoly()
x^2 - 3*x + 2

>>> from sage.all import *
>>> M = MatrixSpace(ZZ, Integer(4), sparse=True)
>>> m = M({(Integer(0), Integer(0)):Integer(2), (Integer(1), Integer(1)):Integer(1), (Integer(2), Integer(1)):-Integer(8), (Integer(2), Integer(2)):Integer(2), (Integer(2), Integer(3)):-Integer(1), (Integer(3), Integer(3)):Integer(1)})
>>> m
[ 2  0  0  0]
[ 0  1  0  0]
[ 0 -8  2 -1]
[ 0  0  0  1]
>>> m.minpoly()
x^2 - 3*x + 2

M = MatrixSpace(ZZ, 4, sparse=True)
m = M({(0, 0):2, (1, 1):1, (2, 1):-8, (2, 2):2, (2, 3):-1, (3, 3):1})
m
m.minpoly()
rank(algorithm=None)[source]

Compute the rank of this matrix.

INPUT:

  • algorithm – (optional) one of None, 'linbox' or 'generic'

EXAMPLES:

sage: M = MatrixSpace(ZZ, 3, 2, sparse=True)
sage: m = M([1, 0, 2, 3, -1, 0])
sage: m.rank()
2

>>> from sage.all import *
>>> M = MatrixSpace(ZZ, Integer(3), Integer(2), sparse=True)
>>> m = M([Integer(1), Integer(0), Integer(2), Integer(3), -Integer(1), Integer(0)])
>>> m.rank()
2

M = MatrixSpace(ZZ, 3, 2, sparse=True)
m = M([1, 0, 2, 3, -1, 0])
m.rank()
rational_reconstruction(N)[source]

Use rational reconstruction to lift self to a matrix over the rational numbers (if possible), where we view self as a matrix modulo \(N\).

EXAMPLES:

sage: A = matrix(ZZ, 3, 4, [(1/3)%500, 2, 3, (-4)%500,
....:                       7, 2, 2, 3,
....:                       4, 3, 4, (5/7)%500], sparse=True)
sage: A.rational_reconstruction(500)
[1/3   2   3  -4]
[  7   2   2   3]
[  4   3   4 5/7]

>>> from sage.all import *
>>> A = matrix(ZZ, Integer(3), Integer(4), [(Integer(1)/Integer(3))%Integer(500), Integer(2), Integer(3), (-Integer(4))%Integer(500),
...                       Integer(7), Integer(2), Integer(2), Integer(3),
...                       Integer(4), Integer(3), Integer(4), (Integer(5)/Integer(7))%Integer(500)], sparse=True)
>>> A.rational_reconstruction(Integer(500))
[1/3   2   3  -4]
[  7   2   2   3]
[  4   3   4 5/7]

A = matrix(ZZ, 3, 4, [(1/3)%500, 2, 3, (-4)%500,
                      7, 2, 2, 3,
                      4, 3, 4, (5/7)%500], sparse=True)
A.rational_reconstruction(500)
smith_form(transformation=True, integral=None)[source]

Return the smith normal form of this matrix, that is the diagonal matrix \(S\) with diagonal entries the ordered elementary divisors of this matrix.

INPUT:

  • transformation – boolean (default: True); whether to return the transformation matrices \(U\) and \(V\) such that \(S = U\cdot self\cdot V\)

  • integral – a subring of the base ring or True (default: None); ignored for matrices with integer entries

This version is for sparse matrices and simply makes the matrix dense and calls the version for dense integer matrices.

Note

The elementary_divisors() function, which returns the diagonal entries of S, is VASTLY faster than this function.

The elementary divisors are the invariants of the finite abelian group that is the cokernel of this matrix. They are ordered in reverse by divisibility.

EXAMPLES:

sage: A = MatrixSpace(IntegerRing(), 3, sparse=True)(range(9))
sage: D, U, V = A.smith_form()
sage: D
[1 0 0]
[0 3 0]
[0 0 0]
sage: U
[ 0  2 -1]
[ 0 -1  1]
[ 1 -2  1]
sage: V
[ 0  0  1]
[-1  2 -2]
[ 1 -1  1]
sage: U*A*V
[1 0 0]
[0 3 0]
[0 0 0]

>>> from sage.all import *
>>> A = MatrixSpace(IntegerRing(), Integer(3), sparse=True)(range(Integer(9)))
>>> D, U, V = A.smith_form()
>>> D
[1 0 0]
[0 3 0]
[0 0 0]
>>> U
[ 0  2 -1]
[ 0 -1  1]
[ 1 -2  1]
>>> V
[ 0  0  1]
[-1  2 -2]
[ 1 -1  1]
>>> U*A*V
[1 0 0]
[0 3 0]
[0 0 0]

A = MatrixSpace(IntegerRing(), 3, sparse=True)(range(9))
D, U, V = A.smith_form()
D
U
V
U*A*V

It also makes sense for nonsquare matrices:

sage: A = Matrix(ZZ,3,2,range(6), sparse=True)
sage: D, U, V = A.smith_form()
sage: D
[1 0]
[0 2]
[0 0]
sage: U
[ 0  2 -1]
[ 0 -1  1]
[ 1 -2  1]
sage: V
[-1  1]
[ 1  0]
sage: U * A * V
[1 0]
[0 2]
[0 0]

>>> from sage.all import *
>>> A = Matrix(ZZ,Integer(3),Integer(2),range(Integer(6)), sparse=True)
>>> D, U, V = A.smith_form()
>>> D
[1 0]
[0 2]
[0 0]
>>> U
[ 0  2 -1]
[ 0 -1  1]
[ 1 -2  1]
>>> V
[-1  1]
[ 1  0]
>>> U * A * V
[1 0]
[0 2]
[0 0]

A = Matrix(ZZ,3,2,range(6), sparse=True)
D, U, V = A.smith_form()
D
U
V
U * A * V

The examples above show that Issue #10626 has been implemented.

See also

elementary_divisors()