Dense matrices over \ZZ/n\ZZ for n small.

AUTHORS:

  • William Stein
  • Robert Bradshaw

This is a compiled implementation of dense matrices over \ZZ/n\ZZ for n small.

EXAMPLES:

sage: a = matrix(Integers(37),3,range(9),sparse=False); a
[0 1 2]
[3 4 5]
[6 7 8]
sage: a.rank()
2
sage: type(a)
<type 'sage.matrix.matrix_modn_dense.Matrix_modn_dense'>
sage: a[0,0] = 5
sage: a.rank()
3
sage: parent(a)
Full MatrixSpace of 3 by 3 dense matrices over Ring of integers modulo 37
sage: a^2
[ 3 23 31]
[20 17 29]
[25 16  0]
sage: a+a
[10  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
...
TypeError: unsupported operand parent(s) for '*': 'Full MatrixSpace of 3 by 3 dense matrices over Ring of integers modulo 37' and 'Full MatrixSpace of 2 by 3 dense matrices over Ring of integers modulo 37'
sage: b*a
[15 18 21]
[20 17 29]
sage: a == loads(dumps(a))
True
sage: b == loads(dumps(b))
True
sage: a.echelonize(); a
[1 0 0]
[0 1 0]
[0 0 1]
sage: b.echelonize(); b
[ 1  0 36]
[ 0  1  2]

We create a matrix group and coerce it to GAP:

sage: M = MatrixSpace(GF(3),3,3)
sage: G = MatrixGroup([M([[0,1,0],[0,0,1],[1,0,0]]), M([[0,1,0],[1,0,0],[0,0,1]])])
sage: G
Matrix group over Finite Field of size 3 with 2 generators: 
 [[[0, 1, 0], [0, 0, 1], [1, 0, 0]], [[0, 1, 0], [1, 0, 0], [0, 0, 1]]]
sage: gap(G)
Group(
[ [ [ 0*Z(3), Z(3)^0, 0*Z(3) ], [ 0*Z(3), 0*Z(3), Z(3)^0 ], [ Z(3)^0, 0*Z(3),
           0*Z(3) ] ], 
  [ [ 0*Z(3), Z(3)^0, 0*Z(3) ], [ Z(3)^0, 0*Z(3), 0*Z(3) ], 
      [ 0*Z(3), 0*Z(3), Z(3)^0 ] ] ])

TESTS:

sage: M = MatrixSpace(GF(5),2,2)
sage: A = M([1,0,0,1])
sage: A - int(-1)
[2 0]
[0 2]
sage: B = M([4,0,0,1])
sage: B - int(-1)
[0 0]
[0 2]
sage: Matrix(GF(5),0,0, sparse=False).inverse()
[]
class sage.matrix.matrix_modn_dense.Matrix_modn_dense
__copy__()
__eq__()
x.__eq__(y) <==> x==y
__ge__()
x.__ge__(y) <==> x>=y
__gt__()
x.__gt__(y) <==> x>y
__hash__()
x.__hash__() <==> hash(x)
__init__()
x.__init__(...) initializes x; see x.__class__.__doc__ for signature
__le__()
x.__le__(y) <==> x<=y
__lt__()
x.__lt__(y) <==> x<y
__ne__()
x.__ne__(y) <==> x!=y
__neg__()

EXAMPLES:

sage: m = matrix(GF(19), 3, 3, range(9)); m
[0 1 2]
[3 4 5]
[6 7 8]
sage: -m
[ 0 18 17]
[16 15 14]
[13 12 11]
static __new__()
T.__new__(S, ...) -> a new object with type S, a subtype of T
_add_()

Add two dense matrices over Z/nZ

EXAMPLES:

sage: a = MatrixSpace(GF(19),3)(range(9))
sage: a+a
[ 0  2  4]
[ 6  8 10]
[12 14 16]
sage: b = MatrixSpace(GF(19),3)(range(9))
sage: b.swap_rows(1,2)
sage: a+b
[ 0  2  4]
[ 9 11 13]
[ 9 11 13]
sage: b+a
[ 0  2  4]
[ 9 11 13]
[ 9 11 13]
_charpoly_hessenberg()

Transforms self in place to its Hessenberg form then computes and returns the coefficients of the characteristic polynomial of this matrix.

INPUT:

  • var - name of the indeterminate of the charpoly.

The characteristic polynomial is represented as a vector of ints, where the constant term of the characteristic polynomial is the 0th coefficient of the vector.

_charpoly_linbox()
Computes the characteristic polynomial using LinBox. No checks are performed.
_echelon_in_place_classical()
_echelonize_linbox()
Puts self in row echelon form using LinBox.
_export_as_string()

Return space separated string of the entries in this matrix.

EXAMPLES:

sage: w = matrix(GF(997),2,3,[1,2,5,-3,8,2]); w
[  1   2   5]
[994   8   2]
sage: w._export_as_string()
'1 2 5 994 8 2'
_lmul_()

EXAMPLES:

sage: a = random_matrix(Integers(60), 400, 500)
sage: 3*a + 9*a == 12*a
True
_magma_init_()

Returns a string representation of self in Magma form.

INPUT:

  • magma - a Magma session

OUTPUT: string

EXAMPLES:

sage: a = matrix(GF(389),2,2,[1..4])
sage: magma(a)                                         # optional - magma
[  1   2]
[  3   4]
sage: a._magma_init_(magma)                            # optional - magma
'Matrix(GF(389),2,2,StringToIntegerSequence("1 2 3 4"))'

A consistency check:

sage: a = random_matrix(GF(13),50); b = random_matrix(GF(13),50)
sage: magma(a*b) == magma(a)*magma(b)                  # optional - magma
True
_matrices_from_rows()

Make a list of matrix from the rows of this matrix. This is a fairly technical function which is used internally, e.g., by the cyclotomic field linear algebra code.

INPUT:

  • nrows, ncols - integers

OUTPUT:

  • list - a list of matrices
_minpoly_linbox()
Computes the minimal polynomial using LinBox. No checks are performed.
_multiply_classical()
_multiply_linbox()

Multiply matrices using LinBox.

INPUT:

  • right - Matrix
_pickle()

Utility function for pickling.

If the prime is small enough to fit in a byte, then it is stored as a contiguous string of bytes (to save space). Otherwise, memcpy is used to copy the raw data in the platforms native format. Any byte-swapping or word size difference is taken care of in unpickling (optimizing for unpickling on the same platform things were pickled on).

The upcoming buffer protocol would be useful to not have to do any copying.

EXAMPLES:

sage: m = matrix(Integers(128), 3, 3, [ord(c) for c in "Hi there!"]); m
[ 72 105  32]
[116 104 101]
[114 101  33]
sage: m._pickle()
((1, ..., 'Hi there!'), 10)
_pivots()
_poly_linbox()

Computes either the minimal or the characteristic polynomial using LinBox. No checks are performed.

INPUT:

  • var - ‘x’
  • typ - ‘minpoly’ or ‘charpoly’
_rmul_()

EXAMPLES:

sage: a = matrix(GF(101), 3, 3, range(9)); a
[0 1 2]
[3 4 5]
[6 7 8]
sage: a * 5
[ 0  5 10]
[15 20 25]
[30 35 40]
sage: a * 50
[  0  50 100]
[ 49  99  48]
[ 98  47  97]
_sub_()

Subtract two dense matrices over Z/nZ

EXAMPLES:

sage: a = matrix(GF(11), 3, 3, range(9)); a
[0 1 2]
[3 4 5]
[6 7 8]
sage: a - 4
[7 1 2]
[3 0 5]
[6 7 4]
sage: a - matrix(GF(11), 3, 3, range(1, 19, 2))
[10  9  8]
[ 7  6  5]
[ 4  3  2]
_unpickle()

TESTS:

Test for char-sized modulus:

sage: A = random_matrix(GF(7), 5, 9)
sage: data, version = A._pickle()
sage: B = A.parent()(0)
sage: B._unpickle(data, version)
sage: B == A
True

And for larger modulus:

sage: A = random_matrix(GF(1009), 51, 5)
sage: data, version = A._pickle()
sage: B = A.parent()(0)
sage: B._unpickle(data, version)
sage: B == A
True

Now test all the bit-packing options:

sage: A = matrix(Integers(1000), 2, 2)
sage: A._unpickle((1, True, '\x01\x02\xFF\x00'), 10)
sage: A
[  1   2]
[255   0]
sage: A = matrix(Integers(1000), 1, 2)
sage: A._unpickle((4, True, '\x02\x01\x00\x00\x01\x00\x00\x00'), 10)
sage: A
[258   1]
sage: A._unpickle((4, False, '\x00\x00\x02\x01\x00\x00\x01\x03'), 10)
sage: A
[513 259]
sage: A._unpickle((8, True, '\x03\x01\x00\x00\x00\x00\x00\x00\x05\x00\x00\x00\x00\x00\x00\x00'), 10)
sage: A
[259   5]
sage: A._unpickle((8, False, '\x00\x00\x00\x00\x00\x00\x02\x08\x00\x00\x00\x00\x00\x00\x01\x04'), 10)
sage: A
[520 260]

Now make sure it works in context:

sage: A = random_matrix(Integers(33), 31, 31)
sage: loads(dumps(A)) == A
True
sage: A = random_matrix(Integers(3333), 31, 31)
sage: loads(dumps(A)) == A
True
charpoly()

Returns the characteristic polynomial of self.

INPUT:

  • var - a variable name
  • algorithm - ‘generic’ ‘linbox’ (default)

EXAMPLES:

sage: A = Mat(GF(7),3,3)(range(3)*3)
sage: A.charpoly()
x^3 + 4*x^2
sage: A = Mat(Integers(6),3,3)(range(9))
sage: A.charpoly()
x^3

ALGORITHM: Uses LinBox if self.base_ring() is a field, otherwise use Hessenberg form algorithm.

determinant()

Return the determinant of this matrix.

EXAMPLES:

sage: m = matrix(GF(101),5,range(25))      
sage: m.det()                              
0
sage: m = matrix(Integers(4), 2, [2,2,2,2])           
sage: m.det()                              
0

TESTS:

sage: m = random_matrix(GF(3), 3, 4)
sage: m.determinant()
...
ArithmeticError: self must be a square matrix
echelonize()

Puts self in row echelon form.

INPUT:

  • self - a mutable matrix
  • algorithm - ‘linbox’ - uses the C++ linbox library
  • 'gauss' - uses a custom slower O(n^3) Gauss elimination implemented in Sage.
  • 'all' - compute using both algorithms and verify that the results are the same (for the paranoid).
  • **kwds - these are all ignored

OUTPUT:

  • self is put in reduced row echelon form.
  • the rank of self is computed and cached
  • the pivot columns of self are computed and cached.
  • the fact that self is now in echelon form is recorded and cached so future calls to echelonize return immediately.

EXAMPLES:

sage: a = matrix(GF(97),3,4,range(12))
sage: a.echelonize(); a
[ 1  0 96 95]
[ 0  1  2  3]
[ 0  0  0  0]            
sage: a.pivots()
[0, 1]
hessenbergize()
Transforms self in place to its Hessenberg form.
lift()

Return the lift of this matrix to the integers.

EXAMPLES:

sage: a = matrix(GF(7),2,3,[1..6])
sage: a.lift()
[1 2 3]
[4 5 6]
sage: a.lift().parent()
Full MatrixSpace of 2 by 3 dense 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]
list()

Return list of elements of self.

EXAMPLES:

sage: w = matrix(GF(19), 2, 3, [1..6])
sage: w.list()
[1, 2, 3, 4, 5, 6]
sage: w.list()[0].parent()
Finite Field of size 19

TESTS:

sage: w = random_matrix(GF(3),100)
sage: w.parent()(w.list()) == w
True
matrix_window()

Return the requested matrix window.

EXAMPLES:

sage: a = matrix(GF(7),3,range(9)); a
[0 1 2]
[3 4 5]
[6 0 1]
sage: type(a)
<type 'sage.matrix.matrix_modn_dense.Matrix_modn_dense'>

We test the optional check flag.

sage: matrix(GF(7),[1]).matrix_window(0,1,1,1)
...
IndexError: matrix window index out of range
sage: matrix(GF(7),[1]).matrix_window(0,1,1,1, check=False)
Matrix window of size 1 x 1 at (0,1):
[1]
minpoly()

Returns the minimal polynomial of self.

INPUT:

  • var - a variable name
  • algorithm - ‘generic’ ‘linbox’ (default)
randomize()

Randomize density proportion of the entries of this matrix, leaving the rest unchanged.

EXAMPLES:

sage: A = matrix(GF(5), 5, 5, 0)
sage: A.randomize(0.5); A
[0 0 0 2 0]
[0 3 0 0 2]
[4 0 0 0 0]
[4 0 0 0 0]
[0 1 0 0 0]
sage: A.randomize(); A
[3 3 2 1 2]
[4 3 3 2 2]
[0 3 3 3 3]
[3 3 2 2 4]
[2 2 2 1 4]
rank()

Return the rank of this matrix.

EXAMPLES:

sage: m = matrix(GF(7),5,range(25))
sage: m.rank()
2

Rank is not implemented over the integers modulo a composite yet.

sage: m = matrix(Integers(4), 2, [2,2,2,2])
sage: m.rank()
...
NotImplementedError: Echelon form not implemented over 'Ring of integers modulo 4'.
sage.matrix.matrix_modn_dense._matrix_from_rows_of_matrices()

INPUT:

  • X - a nonempty list of matrices of the same size mod a single prime p

OUTPUT: A single matrix mod p whose ith row is X[i].list().

Previous topic

Sparse Matrices over a general ring

Next topic

Sparse matrices over \ZZ/n\ZZ for n small.

This Page