Sparse matrices over \(\ZZ/n\ZZ\) for \(n\) small

This is a compiled implementation of sparse matrices over \(\ZZ/n\ZZ\) for \(n\) small.

TODO: - move vectors into a Cython vector class - add _add_ and _mul_ methods.

EXAMPLES:

sage: a = matrix(Integers(37),3,3,range(9),sparse=True); a
[0 1 2]
[3 4 5]
[6 7 8]
sage: type(a)
<type 'sage.matrix.matrix_modn_sparse.Matrix_modn_sparse'>
sage: parent(a)
Full MatrixSpace of 3 by 3 sparse matrices over Ring of integers modulo 37
sage: a^2
[15 18 21]
[ 5 17 29]
[32 16  0]
sage: a+a
[ 0  2  4]
[ 6  8 10]
[12 14 16]
sage: b = a.new_matrix(2,3,range(6)); b
[0 1 2]
[3 4 5]
sage: a*b
Traceback (most recent call last):
...
TypeError: unsupported operand parent(s) for *: 'Full MatrixSpace of 3 by 3 sparse matrices over Ring of integers modulo 37' and 'Full MatrixSpace of 2 by 3 sparse matrices over Ring of integers modulo 37'
sage: b*a
[15 18 21]
[ 5 17 29]

sage: TestSuite(a).run()
sage: TestSuite(b).run()

sage: a.echelonize(); a
[ 1  0 36]
[ 0  1  2]
[ 0  0  0]
sage: b.echelonize(); b
[ 1  0 36]
[ 0  1  2]
sage: a.pivots()
(0, 1)
sage: b.pivots()
(0, 1)
sage: a.rank()
2
sage: b.rank()
2
sage: a[2,2] = 5
sage: a.rank()
3
class sage.matrix.matrix_modn_sparse.Matrix_modn_sparse

Bases: sage.matrix.matrix_sparse.Matrix_sparse

Create a sparse matrix over the integers modulo n.

INPUT:

  • parent – a matrix space
  • entries – can be one of the following:
    • a Python dictionary whose items have the form (i, j): x, where 0 <= i < nrows, 0 <= j < ncols, and x is coercible to an element of the integers modulo n. The i,j entry of self is set to x. The x‘s can be 0.
    • Alternatively, entries can be a list of all the entries of the sparse matrix, read row-by-row from top to bottom (so they would be mostly 0).
  • copy – ignored
  • coerce – ignored
density()

Return the density of self, i.e., the ratio of the number of nonzero entries of self to the total size of self.

EXAMPLES:

sage: A = matrix(QQ,3,3,[0,1,2,3,0,0,6,7,8],sparse=True)
sage: A.density()
2/3

Notice that the density parameter does not ensure the density of a matrix; it is only an upper bound.

sage: A = random_matrix(GF(127),200,200,density=0.3, sparse=True)
sage: A.density()
2073/8000
lift()

Return lift of this matrix to a sparse matrix over the integers.

EXAMPLES:
sage: a = matrix(GF(7),2,3,[1..6], sparse=True) sage: a.lift() [1 2 3] [4 5 6] sage: a.lift().parent() Full MatrixSpace of 2 by 3 sparse matrices over Integer Ring

Subdivisions are preserved when lifting:

sage: a.subdivide([], [1,1]); a
[1||2 3]
[4||5 6]
sage: a.lift()
[1||2 3]
[4||5 6]
matrix_from_columns(cols)

Return the matrix constructed from self using columns with indices in the columns list.

EXAMPLES:

sage: M = MatrixSpace(GF(127),3,3,sparse=True)
sage: A = M(range(9)); A
[0 1 2]
[3 4 5]
[6 7 8]
sage: A.matrix_from_columns([2,1])
[2 1]
[5 4]
[8 7]
matrix_from_rows(rows)

Return the matrix constructed from self using rows with indices in the rows list.

INPUT:

  • rows - list or tuple of row indices

EXAMPLES:

sage: M = MatrixSpace(GF(127),3,3,sparse=True)
sage: A = M(range(9)); A
[0 1 2]
[3 4 5]
[6 7 8]
sage: A.matrix_from_rows([2,1])
[6 7 8]
[3 4 5]
p
rank(gauss=False)

Compute the rank of self.

INPUT:

  • gauss - if True LinBox’ Gaussian elimination is used. If False ‘Symbolic Reordering’ as implemented in LinBox is used. If ‘native’ the native Sage implementation is used. (default: False)

EXAMPLES:

sage: A = random_matrix(GF(127),200,200,density=0.01,sparse=True)
sage: r1 = A.rank(gauss=False)
sage: r2 = A.rank(gauss=True)
sage: r3 = A.rank(gauss='native')
sage: r1 == r2 == r3
True
sage: r1
155

ALGORITHM: Uses LinBox or native implementation.

REFERENCES:

Note

For very sparse matrices Gaussian elimination is faster because it barly has anything to do. If the fill in needs to be considered, ‘Symbolic Reordering’ is usually much faster.

swap_rows(r1, r2)
transpose()

Return the transpose of self.

EXAMPLES:

sage: A = matrix(GF(127),3,3,[0,1,0,2,0,0,3,0,0],sparse=True)
sage: A
[0 1 0]
[2 0 0]
[3 0 0]
sage: A.transpose()
[0 2 3]
[1 0 0]
[0 0 0]

.T is a convenient shortcut for the transpose:

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