Sparse rational matrices

AUTHORS:

• William Stein (2007-02-21)

• Soroosh Yazdani (2007-02-21)

class sage.matrix.matrix_rational_sparse.Matrix_rational_sparse

Bases: Matrix_sparse

_right_kernel_matrix(algorithm='default', proof=None)

Return a pair that includes a matrix of basis vectors for the right kernel of self.

INPUT:

• algorithm – (default: 'default') a keyword that selects the algorithm employed. Allowable values are:

  • 'default' – equivalent to 'padic'

  • 'padic' – \(p\)-adic algorithm from the IML library for matrices over the rationals and integers

  • 'linbox' – LinBox library code for sparse matrices over the rationals

OUTPUT:

Returns a pair. First item is a string that identifies the nature of the basis vectors, either ‘computed-iml-rational’ or ‘computed-linbox-rational’.

Second item is a matrix whose nonzero rows are a basis for the right kernel, over the rationals, as computed by the IML library or the LinBox library.

EXAMPLES:

Sage

sage: A = matrix(QQ, [
....:                 [1, 0, 1, -3, 1],
....:                 [-5, 1, 0, 7, -3],
....:                 [0, -1, -4, 6, -2],
....:                 [4, -1, 0, -6, 2]],
....:             sparse=True)
sage: result = A._right_kernel_matrix()
sage: result[0]
'computed-iml-rational'
sage: result[1]
[-1  2 -2 -1  0]
[ 1  2  0  0 -1]
sage: X = result[1].transpose()
sage: A*X == zero_matrix(QQ, 4, 2)
True
sage: result = A._right_kernel_matrix(algorithm='linbox')
sage: result[0]
'computed-linbox-rational'
sage: result[1]
[ 1 -2  2  1  0]
[-1 -2  0  0  1]
sage: X = result[1].transpose()
sage: A*X == zero_matrix(QQ, 4, 2)
True

Python

>>> from sage.all import *
>>> A = matrix(QQ, [
...                 [Integer(1), Integer(0), Integer(1), -Integer(3), Integer(1)],
...                 [-Integer(5), Integer(1), Integer(0), Integer(7), -Integer(3)],
...                 [Integer(0), -Integer(1), -Integer(4), Integer(6), -Integer(2)],
...                 [Integer(4), -Integer(1), Integer(0), -Integer(6), Integer(2)]],
...             sparse=True)
>>> result = A._right_kernel_matrix()
>>> result[Integer(0)]
'computed-iml-rational'
>>> result[Integer(1)]
[-1  2 -2 -1  0]
[ 1  2  0  0 -1]
>>> X = result[Integer(1)].transpose()
>>> A*X == zero_matrix(QQ, Integer(4), Integer(2))
True
>>> result = A._right_kernel_matrix(algorithm='linbox')
>>> result[Integer(0)]
'computed-linbox-rational'
>>> result[Integer(1)]
[ 1 -2  2  1  0]
[-1 -2  0  0  1]
>>> X = result[Integer(1)].transpose()
>>> A*X == zero_matrix(QQ, Integer(4), Integer(2))
True

Sage Live

A = matrix(QQ, [
                [1, 0, 1, -3, 1],
                [-5, 1, 0, 7, -3],
                [0, -1, -4, 6, -2],
                [4, -1, 0, -6, 2]],
            sparse=True)
result = A._right_kernel_matrix()
result[0]
result[1]
X = result[1].transpose()
A*X == zero_matrix(QQ, 4, 2)
result = A._right_kernel_matrix(algorithm='linbox')
result[0]
result[1]
X = result[1].transpose()
A*X == zero_matrix(QQ, 4, 2)

See also

_right_kernel_matrix()

_right_kernel_matrix_linbox()

Return a pair that includes a matrix of basis vectors for the right kernel of self.

OUTPUT:

Returns a pair. First item is the string ‘computed-linbox-rational’ that identifies the nature of the basis vectors.

Second item is a matrix whose rows are a basis for the right kernel, over the rationals, as computed by the LinBox library.

add_to_entry(i, j, elt)

Add elt to the entry at position (i, j).

EXAMPLES:

Sage

sage: m = matrix(QQ, 2, 2, sparse=True)
sage: m.add_to_entry(0, 0, -1/3)
sage: m
[-1/3    0]
[   0    0]
sage: m.add_to_entry(0, 0, 1/3)
sage: m
[0 0]
[0 0]
sage: m.nonzero_positions()
[]

Python

>>> from sage.all import *
>>> m = matrix(QQ, Integer(2), Integer(2), sparse=True)
>>> m.add_to_entry(Integer(0), Integer(0), -Integer(1)/Integer(3))
>>> m
[-1/3    0]
[   0    0]
>>> m.add_to_entry(Integer(0), Integer(0), Integer(1)/Integer(3))
>>> m
[0 0]
[0 0]
>>> m.nonzero_positions()
[]

Sage Live

m = matrix(QQ, 2, 2, sparse=True)
m.add_to_entry(0, 0, -1/3)
m
m.add_to_entry(0, 0, 1/3)
m
m.nonzero_positions()

The cache is cleared and immutable matrices cannot be changed (Issue #42532):

Sage

sage: m = matrix(QQ, [[1, 2], [3, 4]], sparse=True)
sage: m.det()
-2
sage: m.add_to_entry(0, 0, 10)
sage: m.det()
38
sage: m.set_immutable()
sage: m.add_to_entry(0, 0, 1)
Traceback (most recent call last):
...
ValueError: matrix is immutable; please change a copy instead (i.e., use copy(M) to change a copy of M).

Python

>>> from sage.all import *
>>> m = matrix(QQ, [[Integer(1), Integer(2)], [Integer(3), Integer(4)]], sparse=True)
>>> m.det()
-2
>>> m.add_to_entry(Integer(0), Integer(0), Integer(10))
>>> m.det()
38
>>> m.set_immutable()
>>> m.add_to_entry(Integer(0), Integer(0), Integer(1))
Traceback (most recent call last):
...
ValueError: matrix is immutable; please change a copy instead (i.e., use copy(M) to change a copy of M).

Sage Live

m = matrix(QQ, [[1, 2], [3, 4]], sparse=True)
m.det()
m.add_to_entry(0, 0, 10)
m.det()
m.set_immutable()
m.add_to_entry(0, 0, 1)

denominator()

Return the denominator of this matrix.

OUTPUT: Sage Integer

EXAMPLES:

Sage

sage: b = matrix(QQ,2,range(6)); b[0,0]=-5007/293; b
[-5007/293         1         2]
[        3         4         5]
sage: b.denominator()
293

Python

>>> from sage.all import *
>>> b = matrix(QQ,Integer(2),range(Integer(6))); b[Integer(0),Integer(0)]=-Integer(5007)/Integer(293); b
[-5007/293         1         2]
[        3         4         5]
>>> b.denominator()
293

Sage Live

b = matrix(QQ,2,range(6)); b[0,0]=-5007/293; b
b.denominator()

dense_matrix()

Return dense version of this matrix.

EXAMPLES:

Sage

sage: a = matrix(QQ,2,[1..4],sparse=True); type(a)
<class 'sage.matrix.matrix_rational_sparse.Matrix_rational_sparse'>
sage: type(a.dense_matrix())
<class 'sage.matrix.matrix_rational_dense.Matrix_rational_dense'>
sage: a.dense_matrix()
[1 2]
[3 4]

Python

>>> from sage.all import *
>>> a = matrix(QQ,Integer(2),(ellipsis_range(Integer(1),Ellipsis,Integer(4))),sparse=True); type(a)
<class 'sage.matrix.matrix_rational_sparse.Matrix_rational_sparse'>
>>> type(a.dense_matrix())
<class 'sage.matrix.matrix_rational_dense.Matrix_rational_dense'>
>>> a.dense_matrix()
[1 2]
[3 4]

Sage Live

a = matrix(QQ,2,[1..4],sparse=True); type(a)
type(a.dense_matrix())
a.dense_matrix()

Check that subdivisions are preserved when converting between dense and sparse matrices:

Sage

sage: a.subdivide([1,1], [2])
sage: b = a.dense_matrix().sparse_matrix().dense_matrix()
sage: b.subdivisions() == a.subdivisions()
True

Python

>>> from sage.all import *
>>> a.subdivide([Integer(1),Integer(1)], [Integer(2)])
>>> b = a.dense_matrix().sparse_matrix().dense_matrix()
>>> b.subdivisions() == a.subdivisions()
True

Sage Live

a.subdivide([1,1], [2])
b = a.dense_matrix().sparse_matrix().dense_matrix()
b.subdivisions() == a.subdivisions()

echelon_form(algorithm='default', height_guess=None, proof=True, **kwds)

INPUT:

• height_guess, proof, **kwds – all passed to the multimodular algorithm; ignored by the \(p\)-adic algorithm

OUTPUT: self is no in reduced row echelon form

EXAMPLES:

Sage

sage: a = matrix(QQ, 4, range(16), sparse=True); a[0,0] = 1/19; a[0,1] = 1/5; a
[1/19  1/5    2    3]
[   4    5    6    7]
[   8    9   10   11]
[  12   13   14   15]
sage: a.echelon_form()
[      1       0       0 -76/157]
[      0       1       0  -5/157]
[      0       0       1 238/157]
[      0       0       0       0]

Python

>>> from sage.all import *
>>> a = matrix(QQ, Integer(4), range(Integer(16)), sparse=True); a[Integer(0),Integer(0)] = Integer(1)/Integer(19); a[Integer(0),Integer(1)] = Integer(1)/Integer(5); a
[1/19  1/5    2    3]
[   4    5    6    7]
[   8    9   10   11]
[  12   13   14   15]
>>> a.echelon_form()
[      1       0       0 -76/157]
[      0       1       0  -5/157]
[      0       0       1 238/157]
[      0       0       0       0]

Sage Live

a = matrix(QQ, 4, range(16), sparse=True); a[0,0] = 1/19; a[0,1] = 1/5; a
a.echelon_form()

echelonize(height_guess=None, proof=True, **kwds)

Transform the matrix self into reduced row echelon form in place.

INPUT:

• height_guess, proof, **kwds – all passed to the multimodular algorithm; ignored by the \(p\)-adic algorithm

OUTPUT:

Nothing. The matrix self is transformed into reduced row echelon form in place.

ALGORITHM: a multimodular algorithm.

EXAMPLES:

Sage

sage: a = matrix(QQ, 4, range(16), sparse=True); a[0,0] = 1/19; a[0,1] = 1/5; a
[1/19  1/5    2    3]
[   4    5    6    7]
[   8    9   10   11]
[  12   13   14   15]
sage: a.echelonize(); a
[      1       0       0 -76/157]
[      0       1       0  -5/157]
[      0       0       1 238/157]
[      0       0       0       0]

Python

>>> from sage.all import *
>>> a = matrix(QQ, Integer(4), range(Integer(16)), sparse=True); a[Integer(0),Integer(0)] = Integer(1)/Integer(19); a[Integer(0),Integer(1)] = Integer(1)/Integer(5); a
[1/19  1/5    2    3]
[   4    5    6    7]
[   8    9   10   11]
[  12   13   14   15]
>>> a.echelonize(); a
[      1       0       0 -76/157]
[      0       1       0  -5/157]
[      0       0       1 238/157]
[      0       0       0       0]

Sage Live

a = matrix(QQ, 4, range(16), sparse=True); a[0,0] = 1/19; a[0,1] = 1/5; a
a.echelonize(); a

Issue #10319 has been fixed:

Sage

sage: m = Matrix(QQ, [1], sparse=True); m.echelonize()
sage: m = Matrix(QQ, [1], sparse=True); m.echelonize(); m
[1]

Python

>>> from sage.all import *
>>> m = Matrix(QQ, [Integer(1)], sparse=True); m.echelonize()
>>> m = Matrix(QQ, [Integer(1)], sparse=True); m.echelonize(); m
[1]

Sage Live

m = Matrix(QQ, [1], sparse=True); m.echelonize()
m = Matrix(QQ, [1], sparse=True); m.echelonize(); m

height()

Return the height of this matrix, which is the least common multiple of all numerators and denominators of elements of this matrix.

OUTPUT: integer

EXAMPLES:

Sage

sage: b = matrix(QQ,2,range(6), sparse=True); b[0,0]=-5007/293; b
[-5007/293         1         2]
[        3         4         5]
sage: b.height()
5007

Python

>>> from sage.all import *
>>> b = matrix(QQ,Integer(2),range(Integer(6)), sparse=True); b[Integer(0),Integer(0)]=-Integer(5007)/Integer(293); b
[-5007/293         1         2]
[        3         4         5]
>>> b.height()
5007

Sage Live

b = matrix(QQ,2,range(6), sparse=True); b[0,0]=-5007/293; b
b.height()

set_row_to_multiple_of_row(i, j, s)

Set row i equal to s times row j.

EXAMPLES:

Sage

sage: a = matrix(QQ,2,3,range(6), sparse=True); a
[0 1 2]
[3 4 5]
sage: a.set_row_to_multiple_of_row(1,0,-3)
sage: a
[ 0  1  2]
[ 0 -3 -6]

Python

>>> from sage.all import *
>>> a = matrix(QQ,Integer(2),Integer(3),range(Integer(6)), sparse=True); a
[0 1 2]
[3 4 5]
>>> a.set_row_to_multiple_of_row(Integer(1),Integer(0),-Integer(3))
>>> a
[ 0  1  2]
[ 0 -3 -6]

Sage Live

a = matrix(QQ,2,3,range(6), sparse=True); a
a.set_row_to_multiple_of_row(1,0,-3)
a

Make live