Base class for sparse matrices¶

class sage.matrix.matrix_sparse.Matrix_sparse[source]¶

Bases: Matrix

antitranspose()[source]¶

Return the antitranspose of self, without changing self.

This is the mirror image along the other diagonal.

EXAMPLES:

Sage

sage: M = MatrixSpace(QQ, 2, sparse=True)
sage: A = M([1,2,3,4]); A
[1 2]
[3 4]
sage: A.antitranspose()
[4 2]
[3 1]

Python

>>> from sage.all import *
>>> M = MatrixSpace(QQ, Integer(2), sparse=True)
>>> A = M([Integer(1),Integer(2),Integer(3),Integer(4)]); A
[1 2]
[3 4]
>>> A.antitranspose()
[4 2]
[3 1]

Sage Live

M = MatrixSpace(QQ, 2, sparse=True)
A = M([1,2,3,4]); A
A.antitranspose()

See also

transpose()

apply_map(phi, R=None, sparse=True)[source]¶

Apply the given map phi (an arbitrary Python function or callable object) to this matrix.

If R is not given, automatically determine the base ring of the resulting matrix.

INPUT:

phi – arbitrary Python function or callable object
R – (optional) ring
sparse – boolean (default: True); whether to return a sparse or a dense matrix

OUTPUT: a matrix over R

EXAMPLES:

Sage

sage: m = matrix(ZZ, 10000, {(1,2): 17}, sparse=True)

sage: k.<a> = GF(9)
sage: f = lambda x: k(x)
sage: n = m.apply_map(f)
sage: n.parent()
Full MatrixSpace of 10000 by 10000 sparse matrices
 over Finite Field in a of size 3^2
sage: n[1, 2]
2

Python

>>> from sage.all import *
>>> m = matrix(ZZ, Integer(10000), {(Integer(1),Integer(2)): Integer(17)}, sparse=True)

>>> k = GF(Integer(9), names=('a',)); (a,) = k._first_ngens(1)
>>> f = lambda x: k(x)
>>> n = m.apply_map(f)
>>> n.parent()
Full MatrixSpace of 10000 by 10000 sparse matrices
 over Finite Field in a of size 3^2
>>> n[Integer(1), Integer(2)]
2

Sage Live

m = matrix(ZZ, 10000, {(1,2): 17}, sparse=True)
k.<a> = GF(9)
f = lambda x: k(x)
n = m.apply_map(f)
n.parent()
n[1, 2]

An example where the codomain is explicitly specified.

Sage

sage: n = m.apply_map(lambda x: x%3, GF(3))
sage: n.parent()
Full MatrixSpace of 10000 by 10000 sparse matrices
 over Finite Field of size 3
sage: n[1, 2]
2

Python

>>> from sage.all import *
>>> n = m.apply_map(lambda x: x%Integer(3), GF(Integer(3)))
>>> n.parent()
Full MatrixSpace of 10000 by 10000 sparse matrices
 over Finite Field of size 3
>>> n[Integer(1), Integer(2)]
2

Sage Live

n = m.apply_map(lambda x: x%3, GF(3))
n.parent()
n[1, 2]

If we did not specify the codomain, the resulting matrix in the above case ends up over \(\ZZ\) again:

Sage

sage: n = m.apply_map(lambda x: x%3)
sage: n.parent()
Full MatrixSpace of 10000 by 10000 sparse matrices over Integer Ring
sage: n[1, 2]
2

Python

>>> from sage.all import *
>>> n = m.apply_map(lambda x: x%Integer(3))
>>> n.parent()
Full MatrixSpace of 10000 by 10000 sparse matrices over Integer Ring
>>> n[Integer(1), Integer(2)]
2

Sage Live

n = m.apply_map(lambda x: x%3)
n.parent()
n[1, 2]

If self is subdivided, the result will be as well:

Sage

sage: m = matrix(2, 2, [0, 0, 3, 0])
sage: m.subdivide(None, 1); m
[0|0]
[3|0]
sage: m.apply_map(lambda x: x*x)
[0|0]
[9|0]

Python

>>> from sage.all import *
>>> m = matrix(Integer(2), Integer(2), [Integer(0), Integer(0), Integer(3), Integer(0)])
>>> m.subdivide(None, Integer(1)); m
[0|0]
[3|0]
>>> m.apply_map(lambda x: x*x)
[0|0]
[9|0]

Sage Live

m = matrix(2, 2, [0, 0, 3, 0])
m.subdivide(None, 1); m
m.apply_map(lambda x: x*x)

If the map sends zero to a nonzero value, then it may be useful to get the result as a dense matrix.

Sage

sage: m = matrix(ZZ, 3, 3, [0] * 7 + [1,2], sparse=True); m
[0 0 0]
[0 0 0]
[0 1 2]
sage: parent(m)
Full MatrixSpace of 3 by 3 sparse matrices over Integer Ring
sage: n = m.apply_map(lambda x: x+polygen(QQ), sparse=False); n
[    x     x     x]
[    x     x     x]
[    x x + 1 x + 2]
sage: parent(n)
Full MatrixSpace of 3 by 3 dense matrices over Univariate Polynomial Ring in x over Rational Field

Python

>>> from sage.all import *
>>> m = matrix(ZZ, Integer(3), Integer(3), [Integer(0)] * Integer(7) + [Integer(1),Integer(2)], sparse=True); m
[0 0 0]
[0 0 0]
[0 1 2]
>>> parent(m)
Full MatrixSpace of 3 by 3 sparse matrices over Integer Ring
>>> n = m.apply_map(lambda x: x+polygen(QQ), sparse=False); n
[    x     x     x]
[    x     x     x]
[    x x + 1 x + 2]
>>> parent(n)
Full MatrixSpace of 3 by 3 dense matrices over Univariate Polynomial Ring in x over Rational Field

Sage Live

m = matrix(ZZ, 3, 3, [0] * 7 + [1,2], sparse=True); m
parent(m)
n = m.apply_map(lambda x: x+polygen(QQ), sparse=False); n
parent(n)

apply_morphism(phi)[source]¶

Apply the morphism phi to the coefficients of this sparse matrix.

The resulting matrix is over the codomain of phi.

INPUT:

phi – a morphism, so phi is callable and
phi.domain() and phi.codomain() are defined. The codomain must be a ring.

OUTPUT: a matrix over the codomain of phi

EXAMPLES:

Sage

sage: m = matrix(ZZ, 3, range(9), sparse=True)
sage: phi = ZZ.hom(GF(5))
sage: m.apply_morphism(phi)
[0 1 2]
[3 4 0]
[1 2 3]
sage: m.apply_morphism(phi).parent()
Full MatrixSpace of 3 by 3 sparse matrices
 over Finite Field of size 5

Python

>>> from sage.all import *
>>> m = matrix(ZZ, Integer(3), range(Integer(9)), sparse=True)
>>> phi = ZZ.hom(GF(Integer(5)))
>>> m.apply_morphism(phi)
[0 1 2]
[3 4 0]
[1 2 3]
>>> m.apply_morphism(phi).parent()
Full MatrixSpace of 3 by 3 sparse matrices
 over Finite Field of size 5

Sage Live

m = matrix(ZZ, 3, range(9), sparse=True)
phi = ZZ.hom(GF(5))
m.apply_morphism(phi)
m.apply_morphism(phi).parent()

augment(right, subdivide=False)[source]¶

Return the augmented matrix of the form:

[self | right].

EXAMPLES:

Sage

sage: M = MatrixSpace(QQ, 2, 2, sparse=True)
sage: A = M([1,2, 3,4])
sage: A
[1 2]
[3 4]
sage: N = MatrixSpace(QQ, 2, 1, sparse=True)
sage: B = N([9,8])
sage: B
[9]
[8]
sage: A.augment(B)
[1 2 9]
[3 4 8]
sage: B.augment(A)
[9 1 2]
[8 3 4]

Python

>>> from sage.all import *
>>> M = MatrixSpace(QQ, Integer(2), Integer(2), sparse=True)
>>> A = M([Integer(1),Integer(2), Integer(3),Integer(4)])
>>> A
[1 2]
[3 4]
>>> N = MatrixSpace(QQ, Integer(2), Integer(1), sparse=True)
>>> B = N([Integer(9),Integer(8)])
>>> B
[9]
[8]
>>> A.augment(B)
[1 2 9]
[3 4 8]
>>> B.augment(A)
[9 1 2]
[8 3 4]

Sage Live

M = MatrixSpace(QQ, 2, 2, sparse=True)
A = M([1,2, 3,4])
A
N = MatrixSpace(QQ, 2, 1, sparse=True)
B = N([9,8])
B
A.augment(B)
B.augment(A)

A vector may be augmented to a matrix.

Sage

sage: A = matrix(QQ, 3, 4, range(12), sparse=True)
sage: v = vector(QQ, 3, range(3), sparse=True)
sage: A.augment(v)
[ 0  1  2  3  0]
[ 4  5  6  7  1]
[ 8  9 10 11  2]

Python

>>> from sage.all import *
>>> A = matrix(QQ, Integer(3), Integer(4), range(Integer(12)), sparse=True)
>>> v = vector(QQ, Integer(3), range(Integer(3)), sparse=True)
>>> A.augment(v)
[ 0  1  2  3  0]
[ 4  5  6  7  1]
[ 8  9 10 11  2]

Sage Live

A = matrix(QQ, 3, 4, range(12), sparse=True)
v = vector(QQ, 3, range(3), sparse=True)
A.augment(v)

The subdivide option will add a natural subdivision between self and right. For more details about how subdivisions are managed when augmenting, see sage.matrix.matrix1.Matrix.augment().

Sage

sage: A = matrix(QQ, 3, 5, range(15), sparse=True)
sage: B = matrix(QQ, 3, 3, range(9), sparse=True)
sage: A.augment(B, subdivide=True)
[ 0  1  2  3  4| 0  1  2]
[ 5  6  7  8  9| 3  4  5]
[10 11 12 13 14| 6  7  8]

Python

>>> from sage.all import *
>>> A = matrix(QQ, Integer(3), Integer(5), range(Integer(15)), sparse=True)
>>> B = matrix(QQ, Integer(3), Integer(3), range(Integer(9)), sparse=True)
>>> A.augment(B, subdivide=True)
[ 0  1  2  3  4| 0  1  2]
[ 5  6  7  8  9| 3  4  5]
[10 11 12 13 14| 6  7  8]

Sage Live

A = matrix(QQ, 3, 5, range(15), sparse=True)
B = matrix(QQ, 3, 3, range(9), sparse=True)
A.augment(B, subdivide=True)

change_ring(ring)[source]¶

Return the matrix obtained by coercing the entries of this matrix into the given ring.

Always returns a copy (unless self is immutable, in which case returns self).

EXAMPLES:

Sage

sage: x = polygen(ZZ, 'x')
sage: A = matrix(QQ['x,y'], 2, [0,-1,2*x,-2], sparse=True); A
[  0  -1]
[2*x  -2]
sage: A.change_ring(QQ['x,y,z'])
[  0  -1]
[2*x  -2]

Python

>>> from sage.all import *
>>> x = polygen(ZZ, 'x')
>>> A = matrix(QQ['x,y'], Integer(2), [Integer(0),-Integer(1),Integer(2)*x,-Integer(2)], sparse=True); A
[  0  -1]
[2*x  -2]
>>> A.change_ring(QQ['x,y,z'])
[  0  -1]
[2*x  -2]

Sage Live

x = polygen(ZZ, 'x')
A = matrix(QQ['x,y'], 2, [0,-1,2*x,-2], sparse=True); A
A.change_ring(QQ['x,y,z'])

Subdivisions are preserved when changing rings:

Sage

sage: A.subdivide([2],[]); A
[  0  -1]
[2*x  -2]
[-------]
sage: A.change_ring(RR['x,y'])
[                 0  -1.00000000000000]
[2.00000000000000*x  -2.00000000000000]
[-------------------------------------]

Python

>>> from sage.all import *
>>> A.subdivide([Integer(2)],[]); A
[  0  -1]
[2*x  -2]
[-------]
>>> A.change_ring(RR['x,y'])
[                 0  -1.00000000000000]
[2.00000000000000*x  -2.00000000000000]
[-------------------------------------]

Sage Live

A.subdivide([2],[]); A
A.change_ring(RR['x,y'])

charpoly(var='x', **kwds)[source]¶

Return the characteristic polynomial of this matrix.

Note

the generic sparse charpoly implementation in Sage is to just compute the charpoly of the corresponding dense matrix, so this could use a lot of memory. In particular, for this matrix, the charpoly will be computed using a dense algorithm.

EXAMPLES:

Sage

sage: A = matrix(ZZ, 4, range(16), sparse=True)
sage: A.charpoly()
x^4 - 30*x^3 - 80*x^2
sage: A.charpoly('y')
y^4 - 30*y^3 - 80*y^2
sage: A.charpoly()
x^4 - 30*x^3 - 80*x^2

Python

>>> from sage.all import *
>>> A = matrix(ZZ, Integer(4), range(Integer(16)), sparse=True)
>>> A.charpoly()
x^4 - 30*x^3 - 80*x^2
>>> A.charpoly('y')
y^4 - 30*y^3 - 80*y^2
>>> A.charpoly()
x^4 - 30*x^3 - 80*x^2

Sage Live

A = matrix(ZZ, 4, range(16), sparse=True)
A.charpoly()
A.charpoly('y')
A.charpoly()

density()[source]¶

Return the density of the matrix.

By density we understand the ratio of the number of nonzero positions and the number self.nrows() * self.ncols(), i.e. the number of possible nonzero positions.

EXAMPLES:

Sage

sage: a = matrix([[],[],[],[]], sparse=True); a.density()
0
sage: a = matrix(5000,5000,{(1,2): 1}); a.density()
1/25000000

Python

>>> from sage.all import *
>>> a = matrix([[],[],[],[]], sparse=True); a.density()
0
>>> a = matrix(Integer(5000),Integer(5000),{(Integer(1),Integer(2)): Integer(1)}); a.density()
1/25000000

Sage Live

a = matrix([[],[],[],[]], sparse=True); a.density()
a = matrix(5000,5000,{(1,2): 1}); a.density()

determinant(**kwds)[source]¶

Return the determinant of this matrix.

Note

the generic sparse determinant implementation in Sage is to just compute the determinant of the corresponding dense matrix, so this could use a lot of memory. In particular, for this matrix, the determinant will be computed using a dense algorithm.

EXAMPLES:

Sage

sage: A = matrix(ZZ, 4, range(16), sparse=True)
sage: B = A + identity_matrix(ZZ, 4, sparse=True)
sage: B.det()
-49

Python

>>> from sage.all import *
>>> A = matrix(ZZ, Integer(4), range(Integer(16)), sparse=True)
>>> B = A + identity_matrix(ZZ, Integer(4), sparse=True)
>>> B.det()
-49

Sage Live

A = matrix(ZZ, 4, range(16), sparse=True)
B = A + identity_matrix(ZZ, 4, sparse=True)
B.det()

is_symmetric()[source]¶

Return whether this matrix is symmetric.

The generic implementation compares the \(n(n-1)/2\) pairs of off-diagonal entries and is therefore quadratic in the dimension of the matrix, even when almost all of those entries are zero. Here only the nonzero entries are visited, so the running time is linear in their number.

EXAMPLES:

Sage

sage: M = matrix(ZZ, 3, 3, {(0, 1): 1, (1, 0): 1}, sparse=True)
sage: M.is_symmetric()
True
sage: M[0, 2] = 5
sage: M.is_symmetric()
False

Python

>>> from sage.all import *
>>> M = matrix(ZZ, Integer(3), Integer(3), {(Integer(0), Integer(1)): Integer(1), (Integer(1), Integer(0)): Integer(1)}, sparse=True)
>>> M.is_symmetric()
True
>>> M[Integer(0), Integer(2)] = Integer(5)
>>> M.is_symmetric()
False

Sage Live

M = matrix(ZZ, 3, 3, {(0, 1): 1, (1, 0): 1}, sparse=True)
M.is_symmetric()
M[0, 2] = 5
M.is_symmetric()

A matrix that is not square is not symmetric:

Sage

sage: matrix(ZZ, 2, 3, sparse=True).is_symmetric()
False

Python

>>> from sage.all import *
>>> matrix(ZZ, Integer(2), Integer(3), sparse=True).is_symmetric()
False

Sage Live

matrix(ZZ, 2, 3, sparse=True).is_symmetric()

matrix_from_rows_and_columns(rows, columns)[source]¶

Return the matrix constructed from self from the given rows and columns.

EXAMPLES:

Sage

sage: M = MatrixSpace(Integers(8),3,3, sparse=True)
sage: A = 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]

Python

>>> from sage.all import *
>>> M = MatrixSpace(Integers(Integer(8)),Integer(3),Integer(3), sparse=True)
>>> A = 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]

Sage Live

M = MatrixSpace(Integers(8),3,3, sparse=True)
A = M(range(9)); A
A.matrix_from_rows_and_columns([1], [0,2])
A.matrix_from_rows_and_columns([1,2], [1,2])

Note that row and column indices can be reordered or repeated:

Sage

sage: A.matrix_from_rows_and_columns([2,1], [2,1])
[0 7]
[5 4]

Python

>>> from sage.all import *
>>> A.matrix_from_rows_and_columns([Integer(2),Integer(1)], [Integer(2),Integer(1)])
[0 7]
[5 4]

Sage Live

A.matrix_from_rows_and_columns([2,1], [2,1])

For example here we take from row 1 columns 2 then 0 twice, and do this 3 times.

Sage

sage: A.matrix_from_rows_and_columns([1,1,1],[2,0,0])
[5 3 3]
[5 3 3]
[5 3 3]

Python

>>> from sage.all import *
>>> A.matrix_from_rows_and_columns([Integer(1),Integer(1),Integer(1)],[Integer(2),Integer(0),Integer(0)])
[5 3 3]
[5 3 3]
[5 3 3]

Sage Live

A.matrix_from_rows_and_columns([1,1,1],[2,0,0])

We can efficiently extract large submatrices:

Sage

sage: A = random_matrix(ZZ, 100000, density=.00005, sparse=True)  # long time (4s on sage.math, 2012)
sage: B = A[50000:,:50000]        # long time
sage: count = 0
sage: for i, j in A.nonzero_positions():  # long time
....:     if i >= 50000 and j < 50000:
....:         assert B[i-50000, j] == A[i, j]
....:         count += 1
sage: count == sum(1 for _ in B.nonzero_positions())  # long time
True

Python

>>> from sage.all import *
>>> A = random_matrix(ZZ, Integer(100000), density=RealNumber('.00005'), sparse=True)  # long time (4s on sage.math, 2012)
>>> B = A[Integer(50000):,:Integer(50000)]        # long time
>>> count = Integer(0)
>>> for i, j in A.nonzero_positions():  # long time
...     if i >= Integer(50000) and j < Integer(50000):
...         assert B[i-Integer(50000), j] == A[i, j]
...         count += Integer(1)
>>> count == sum(Integer(1) for _ in B.nonzero_positions())  # long time
True

Sage Live

A = random_matrix(ZZ, 100000, density=.00005, sparse=True)  # long time (4s on sage.math, 2012)
B = A[50000:,:50000]        # long time
count = 0
for i, j in A.nonzero_positions():  # long time
    if i >= 50000 and j < 50000:
        assert B[i-50000, j] == A[i, j]
        count += 1
count == sum(1 for _ in B.nonzero_positions())  # long time

We must pass in a list of indices:

Sage

sage: A = random_matrix(ZZ,100,density=.02,sparse=True)
sage: A.matrix_from_rows_and_columns(1,[2,3])
Traceback (most recent call last):
...
TypeError: 'sage.rings.integer.Integer' object is not iterable

sage: A.matrix_from_rows_and_columns([1,2],3)
Traceback (most recent call last):
...
TypeError: 'sage.rings.integer.Integer' object is not iterable

Python

>>> from sage.all import *
>>> A = random_matrix(ZZ,Integer(100),density=RealNumber('.02'),sparse=True)
>>> A.matrix_from_rows_and_columns(Integer(1),[Integer(2),Integer(3)])
Traceback (most recent call last):
...
TypeError: 'sage.rings.integer.Integer' object is not iterable

>>> A.matrix_from_rows_and_columns([Integer(1),Integer(2)],Integer(3))
Traceback (most recent call last):
...
TypeError: 'sage.rings.integer.Integer' object is not iterable

Sage Live

A = random_matrix(ZZ,100,density=.02,sparse=True)
A.matrix_from_rows_and_columns(1,[2,3])
A.matrix_from_rows_and_columns([1,2],3)

AUTHORS:

Jaap Spies (2006-02-18)
Didier Deshommes: some Pyrex speedups implemented
Jason Grout: sparse matrix optimizations

transpose()[source]¶

Return the transpose of self, without changing self.

EXAMPLES: We create a matrix, compute its transpose, and note that the original matrix is not changed.

Sage

sage: M = MatrixSpace(QQ, 2, sparse=True)
sage: A = M([1,2,3,4]); A
[1 2]
[3 4]
sage: B = A.transpose(); B
[1 3]
[2 4]

Python

>>> from sage.all import *
>>> M = MatrixSpace(QQ, Integer(2), sparse=True)
>>> A = M([Integer(1),Integer(2),Integer(3),Integer(4)]); A
[1 2]
[3 4]
>>> B = A.transpose(); B
[1 3]
[2 4]

Sage Live

M = MatrixSpace(QQ, 2, sparse=True)
A = M([1,2,3,4]); A
B = A.transpose(); B

.T is a convenient shortcut for the transpose:

Sage

sage: A.T
[1 3]
[2 4]

Python

>>> from sage.all import *
>>> A.T
[1 3]
[2 4]

Sage Live

A.T