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

Module: sage.matrix.matrix_modn_dense

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

Author Log:

This is a compiled implementation of dense matrices over $ \mathbf{Z}/n\mathbf{Z}$ for $ n$ 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 $ 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.

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__,$ \,$ _charpoly_hessenberg,$ \,$ _charpoly_linbox,$ \,$ _echelon_in_place_classical,$ \,$ _echelonize_linbox,$ \,$ _magma_init_,$ \,$ _matrices_from_rows,$ \,$ _minpoly_linbox,$ \,$ _multiply_classical,$ \,$ _multiply_linbox,$ \,$ _pivots,$ \,$ _poly_linbox

__copy__( )

_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

_pivots( )

_poly_linbox( )

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

Input:

var
- 'x'
typ
- 'minpoly' or 'charpoly'

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