34.14 Dense matrices over $\mathbf{Z}/n\mathbf{Z}$ for small

Module: sage.matrix.matrix_modn_dense

Dense matrices over $\mathbf{Z}/n\mathbf{Z}$ for small.

Author Log:

William Stein
Robert Bradshaw

This is a compiled implementation of dense matrices over $\mathbf{Z}/n\mathbf{Z}$ for small.

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
Traceback (most recent call last):
...
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]

Module-level Functions

Class: Matrix_modn_dense

class Matrix_modn_dense

Functions: charpoly, $\,$ determinant, $\,$ echelonize, $\,$ hessenbergize, $\,$ minpoly, $\,$ randomize, $\,$ rank

charpoly( )

Returns the characteristic polynomial of self.

Input:

var: - a variable name
algorithm: - 'generic' 'linbox' (default)

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.

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

echelonize( )

Puts self in row echelon form.

Input:

self: - a mutable matrix
algorithm: - 'linbox' - uses the C++ linbox library
'gauss': - uses a custom slower 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.

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.

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.

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.

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()
Traceback (most recent call last):
...
NotImplementedError: Echelon form not implemented over 'Ring of integers
modulo 4'.

Special Functions: __copy__, $\,$ __eq__, $\,$ __ge__, $\,$ __gt__, $\,$ __init__, $\,$ __le__, $\,$ __lt__, $\,$ __ne__, $\,$ __neg__, $\,$ _charpoly_hessenberg, $\,$ _charpoly_linbox, $\,$ _echelon_in_place_classical, $\,$ _echelonize_linbox, $\,$ _magma_init_, $\,$ _matrices_from_rows, $\,$ _minpoly_linbox, $\,$ _multiply_classical, $\,$ _multiply_linbox, $\,$ _pickle, $\,$ _pivots, $\,$ _poly_linbox, $\,$ _unpickle

__copy__( )

__neg__( )

sage: m = matrix(GF(19), 3, 3, range(9)); m
[0 1 2]
[3 4 5]
[6 7 8]
sage: -m
[19 18 17]
[16 15 14]
[13 12 11]

_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.

_magma_init_( )

Returns a string of self in MAGMA form.

NOTE: Does not return MAGMA object but string.

_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: - 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.

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'

_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

See About this document... for information on suggesting changes.

34.14 Dense matrices over for small

34.14 Dense matrices over $\mathbf{Z}/n\mathbf{Z}$ for small