32.17 Dense matrices over the rational field

Module: sage.matrix.matrix_rational_dense

Dense matrices over the rational field.

We create a 3x3 matrix with rational entries and do some operations with it.

sage: a = matrix(QQ, 3,3, [1,2/3, -4/5, 1,1,1, 8,2, -3/19]); a
[    1   2/3  -4/5]
[    1     1     1]
[    8     2 -3/19]
sage: a.det()
2303/285
sage: a.charpoly()
x^3 - 35/19*x^2 + 1259/285*x - 2303/285
sage: b = a^(-1); b
[ -615/2303  -426/2303   418/2303]
[ 2325/2303  1779/2303  -513/2303]
[-1710/2303   950/2303    95/2303]
sage: b.det()
285/2303
sage: a == b
False
sage: a < b
False
sage: b < a
True
sage: a > b
True
sage: a*b
[1 0 0]
[0 1 0]
[0 0 1]

TESTS:

sage: a = matrix(QQ,2,range(4), sparse=False)
sage: loads(dumps(a)) == a
True

Module-level Functions

clear_mpz_globals( )

gmp_randrange( )

init_mpz_globals( )

Class: Matrix_rational_dense

class Matrix_rational_dense

Functions: change_ring,$ \,$ charpoly,$ \,$ decomposition,$ \,$ denominator,$ \,$ determinant,$ \,$ echelon_form,$ \,$ echelonize,$ \,$ height,$ \,$ invert,$ \,$ kernel,$ \,$ minpoly,$ \,$ prod_of_row_sums,$ \,$ randomize,$ \,$ rank,$ \,$ set_row_to_multiple_of_row

change_ring( )

Create the matrix over R with entries the entries of self coerced into R.

sage: a = matrix(QQ,2,[1/2,-1,2,3])
sage: a.change_ring(GF(3))
[2 2]
[2 0]
sage: a.change_ring(ZZ)
Traceback (most recent call last):
...
TypeError: matrix has denominators so can't change to ZZ.
sage: b = a.change_ring(QQ['x']); b
[1/2  -1]
[  2   3]
sage: b.parent()
Full MatrixSpace of 2 by 2 dense matrices over Univariate Polynomial Ring
in x over Rational Field

charpoly( )

Return the characteristic polynomial of this matrix.

Input:

var
- 'x' (string)
algorithm
- 'linbox' (default) 'generic'

Output: a polynomial over the rational numbers.

sage: a = matrix(QQ, 3, [4/3, 2/5, 1/5, 4, -3/2, 0, 0, -2/3, 3/4])
sage: f = a.charpoly(); f
x^3 - 7/12*x^2 - 149/40*x + 97/30
sage: f(a)
[0 0 0]
[0 0 0]
[0 0 0]

decomposition( )

Returns the decomposition of the free module on which this matrix A acts from the right (i.e., the action is x goes to x A), along with whether this matrix acts irreducibly on each factor. The factors are guaranteed to be sorted in the same way as the corresponding factors of the characteristic polynomial.

Let A be the matrix acting from the on the vector space V of column vectors. Assume that A is square. This function computes maximal subspaces W_1, ..., W_n corresponding to Galois conjugacy classes of eigenvalues of A. More precisely, let f(X) be the characteristic polynomial of A. This function computes the subspace $ W_i = ker(g_(A)^n)$ , where g_i(X) is an irreducible factor of f(X) and g_i(X) exactly divides f(X). If the optional parameter is_diagonalizable is True, then we let W_i = ker(g(A)), since then we know that ker(g(A)) = $ ker(g(A)^n)$ .

If dual is True, also returns the corresponding decomposition of V under the action of the transpose of A. The factors are guarenteed to correspond.

Input:

is_diagonizalible
- ignored
dual
- whether to also return decompositions for the dual
algorithm
- 'default': use default algorithm for computing Echelon forms, 'multimodular': much better if the answers factors have small height
height_guess
- positive integer; only used by the multimodular algorithm
proof
- bool or None (default: None, see proof.linear_algebra or sage.structure.proof); only used by the multimodular algorithm. Note that the Sage global default is proof=True.

IMPORTANT NOTE: If you expect that the subspaces in the answer are spanned by vectors with small height coordinates, use algorithm='multimodular' and height_guess=1; this is potentially much faster than the default. If you know for a fact the answer will be very small, use algorithm='multimodular', height_guess=bound on height, proof=False

You can get very very fast decomposition with proof=False.

denominator( )

Return the denominator of this matrix.

Output:

- SAGE Integer

sage: b = matrix(QQ,2,range(6)); b[0,0]=-5007/293; b
[-5007/293         1         2]
[        3         4         5]
sage: b.denominator()
293

determinant( )

Return the determinant of this matrix.

Input:

proof
- bool or None; if None use proof.linear_algebra(); only relevant for the padic algorithm. NOTE: It would be *VERY VERY* hard for det to fail even with proof=False.

ALGORITHM: Clear denominators and call the integer determinant function.

sage: m = matrix(QQ,3,[1,2/3,4/5, 2,2,2, 5,3,2/5])
sage: m.determinant()
-34/15
sage: m.charpoly()
x^3 - 17/5*x^2 - 122/15*x + 34/15

echelon_form( )

Input:

algorithm
- 'default' (default): use heuristic choice 'padic': an algorithm based on the IML p-adic solver. 'multimodular': uses a multimodular algorithm the uses linbox modulo many primes.
height_guess, **kwds
- all passed to the multimodular algorithm; ignored by the p-adic algorithm.
proof
- bool or None (default: None, see proof.linear_algebra or sage.structure.proof). Passed to the multimodular algorithm. Note that the Sage global default is proof=True.

Output: self is no in reduced row echelon form.

sage: a = matrix(QQ, 4, range(16)); a[0,0] = 1/19; a[0,1] = 1/5; a
[1/19  1/5    2    3]
[   4    5    6    7]
[   8    9   10   11]
[  12   13   14   15]
sage: a.echelon_form()
[      1       0       0 -76/157]
[      0       1       0  -5/157]
[      0       0       1 238/157]
[      0       0       0       0]
sage: a.echelon_form(algorithm='multimodular')
[      1       0       0 -76/157]
[      0       1       0  -5/157]
[      0       0       1 238/157]
[      0       0       0       0]

echelonize( )

Input:

algorithm
- 'default' (default): use heuristic choice 'padic': an algorithm based on the IML p-adic solver. 'multimodular': uses a multimodular algorithm the uses linbox modulo many primes.
height_guess, **kwds
- all passed to the multimodular algorithm; ignored by the p-adic algorithm.
proof
- bool or None (default: None, see proof.linear_algebra or sage.structure.proof). Passed to the multimodular algorithm. Note that the Sage global default is proof=True.

Output:
matrix
- the reduced row echelon for of self.

sage: a = matrix(QQ, 4, range(16)); a[0,0] = 1/19; a[0,1] = 1/5; a
[1/19  1/5    2    3]
[   4    5    6    7]
[   8    9   10   11]
[  12   13   14   15]
sage: a.echelonize(); a
[      1       0       0 -76/157]
[      0       1       0  -5/157]
[      0       0       1 238/157]
[      0       0       0       0]

sage: a = matrix(QQ, 4, range(16)); a[0,0] = 1/19; a[0,1] = 1/5
sage: a.echelonize(algorithm='multimodular'); a
[      1       0       0 -76/157]
[      0       1       0  -5/157]
[      0       0       1 238/157]
[      0       0       0       0]

height( )

Return the height of this matrix, which is the maximum of the absolute values of all numerators and denominators of entries in this matrix.

Output:

- Integer

sage: b = matrix(QQ,2,range(6)); b[0,0]=-5007/293; b
[-5007/293         1         2]
[        3         4         5]
sage: b.height()
5007

invert( )

Input:

check_invertible
- default: True (whether to check that matrix is invertible) algorithm -"iml" (only option right now)

Output:
- the inverse of self

NOTES: * If self is not invertible, a ZeroDivisionError is raised. * The n x n cases for n <= 2 are handcoded for speed.

sage: a = matrix(QQ,3,[1,2,5,3,2,1,1,1,1,])
sage: a.invert(check_invertible=False)
[1/2 3/2  -4]
[ -1  -2   7]
[1/2 1/2  -2]

A 1x1 matrix (a special case):

sage: a = matrix(QQ, 1, [390284089234])
sage: a.invert()
[1/390284089234]

A 2x2 matrix (a special hand-coded case):

sage: a = matrix(QQ, 2, [1, 5, 17, 3]); a
[ 1  5]
[17  3]
sage: a.invert() 
[-3/82  5/82]
[17/82 -1/82]
sage: a.invert()  * a
[1 0]
[0 1]

kernel( )

Return the kernel of this matrix, as a vector space over QQ.

Input:

algorithm
- 'padic' (or 'default'): use IML's p-adic nullspace algorithm
anything else
- passed on to the generic echelon-form based algorithm.
**kwds
- passed onto to echelon form algorithm in the echelon case.

minpoly( )

Return the minimal polynomial of this matrix.

Input:

var
- 'x' (string)
algorithm
- 'linbox' (default) 'generic'

Output: a polynomial over the rational numbers.

sage: a = matrix(QQ, 3, [4/3, 2/5, 1/5, 4, -3/2, 0, 0, -2/3, 3/4])
sage: f = a.minpoly(); f           
x^3 - 7/12*x^2 - 149/40*x + 97/30
sage: a = Mat(ZZ,4)(range(16))
sage: f = a.minpoly(); f.factor()  
x * (x^2 - 30*x - 80)
sage: f(a) == 0                    
True

sage: a = matrix(QQ, 4, [1..4^2])
sage: factor(a.minpoly())
x * (x^2 - 34*x - 80)
sage: factor(a.minpoly('y'))
y * (y^2 - 34*y - 80)
sage: factor(a.charpoly())
x^2 * (x^2 - 34*x - 80)
sage: b = matrix(QQ, 4, [-1, 2, 2, 0, 0, 4, 2, 2, 0, 0, -1, -2, 0, -4, 0, 4])
sage: a = matrix(QQ, 4, [1, 1, 0,0, 0,1,0,0, 0,0,5,0, 0,0,0,5])
sage: c = b^(-1)*a*b
sage: factor(c.minpoly())
(x - 5) * (x - 1)^2
sage: factor(c.charpoly())
(x - 5)^2 * (x - 1)^2

randomize( )

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

If x and y are given, randomized entries of this matrix have numerators and denominators bounded by x and y and have density 1.

rank( )

Return the rank of this matrix.

set_row_to_multiple_of_row( )

Set row i equal to s times row j.

sage: a = matrix(QQ,2,3,range(6)); a
[0 1 2]
[3 4 5]
sage: a.set_row_to_multiple_of_row(1,0,-3)
sage: a
[ 0  1  2]
[ 0 -3 -6]

Special Functions: __copy__,$ \,$ __eq__,$ \,$ __ge__,$ \,$ __gt__,$ \,$ __init__,$ \,$ __invert__,$ \,$ __le__,$ \,$ __lt__,$ \,$ __ne__,$ \,$ __neg__,$ \,$ _adjoint,$ \,$ _clear_denom,$ \,$ _decomposition_rational,$ \,$ _echelon_form_multimodular,$ \,$ _echelon_form_padic,$ \,$ _echelonize_multimodular,$ \,$ _echelonize_padic,$ \,$ _lift_crt_rr,$ \,$ _lift_crt_rr_with_lcm,$ \,$ _multiply_over_integers,$ \,$ _pickle,$ \,$ _set_row_to_negative_of_row_of_A_using_subset_of_columns,$ \,$ _unpickle

__copy__( )

Copy a matrix over QQ.

sage: a = MatrixSpace(QQ,3)([1/n for n in range(1,10)])
sage: -a
[  -1 -1/2 -1/3]
[-1/4 -1/5 -1/6]
[-1/7 -1/8 -1/9]

__invert__( )

sage: a = matrix(QQ,3,range(9))
sage: a^(-1)
Traceback (most recent call last):
...
ZeroDivisionError: input matrix must be nonsingular

__neg__( )

Negate a matrix over QQ.

sage: a = MatrixSpace(QQ,3)([1/n for n in range(1,10)])
sage: -a
[  -1 -1/2 -1/3]
[-1/4 -1/5 -1/6]
[-1/7 -1/8 -1/9]

_adjoint( )

Return the adjoint of this matrix.

Assumes self is a square matrix (checked in adjoint).

_clear_denom( )

Input:

self
- a matrix
Output: D*self, D

The product is a matrix over ZZ

sage: a = matrix(QQ,2,[-1/6,-7,3,5/4]); a
[-1/6   -7]
[   3  5/4]
sage: a._clear_denom()
([ -2 -84]
[ 36  15], 12)

_decomposition_rational( )

Returns the decomposition of the free module on which this matrix A acts from the right (i.e., the action is x goes to x A), along with whether this matrix acts irreducibly on each factor. The factors are guaranteed to be sorted in the same way as the corresponding factors of the characteristic polynomial.

Input:

self
- a square matrix over the rational numbers
echelon_algorithm
- 'default'
'multimodular'
- use this if the answers have small height
**kwds
- passed on to echelon function.

IMPORTANT NOTE: If you expect that the subspaces in the answer are spanned by vectors with small height coordinates, use algorithm='multimodular' and height_guess=1; this is potentially much faster than the default. If you know for a fact the answer will be very small, use algorithm='multimodular', height_guess=bound on height, proof=False

Output:
Sequence
- list of tuples (V,t), where V is a vector spaces and t is True if and only if the charpoly of self on V is irreducible. The tuples are in order corresponding to the elements of the sorted list self.charpoly().factor().

_echelon_form_multimodular( )

Returns reduced row-echelon form using a multi-modular algorithm. Does not change self.

REFERENCE: Chapter 7 of Stein's "Explicitly Computing Modular Forms".

Input:

height_guess
- integer or None
proof
- boolean (default: None, see proof.linear_algebra or sage.structure.proof) Note that the Sage global default is proof=True.

_echelon_form_padic( )

Compute and return the echelon form of self using a p-adic nullspace algorithm.

_echelonize_multimodular( )

_echelonize_padic( )

Echelonize self using a p-adic nullspace algorithm.

_lift_crt_rr( )

_lift_crt_rr_with_lcm( )

Optimizations: When doing the rational_recon lift of a (mod m) first see if |a| < sqrt(m/2) in which case it lifts to an integer (often a=0 or 1).

If that fails, keep track of the lcm d of denominators found so far, and check to see if z = a*d lifts to an integer with |z| <= sqrt(m/2). If so, no need to do rational recon. This should be the case for most a after a while, and should saves substantial time!

_multiply_over_integers( )

Multiply this matrix by right using a multimodular algorithm and return the result.

Input:

self
- matrix over QQ
right
- matrix over QQ
algorithm
- 'default': use whatever is the defalt for A*B when A, B are over ZZ. 'multimodular': use a multimodular algorithm

sage: a = MatrixSpace(QQ,10,5)(range(50))
sage: b = MatrixSpace(QQ,5,12)([1/n for n in range(1,61)])
sage: a._multiply_over_integers(b) == a._multiply_over_integers(b, algorithm='multimodular')
True

sage: a = MatrixSpace(QQ,3)(range(9))
sage: b = MatrixSpace(QQ,3)([1/n for n in range(1,10)])
sage: a._multiply_over_integers(b, algorithm = 'multimodular')
[ 15/28   9/20   7/18]
[  33/7 117/40   20/9]
[249/28   27/5  73/18]

_pickle( )

_set_row_to_negative_of_row_of_A_using_subset_of_columns( )

Set row i of self to -(row r of A), but where we only take the given column positions in that row of A. We do not zero out the other entries of self's row i either.

Input:

i
- integer, index into the rows of self
A
- a matrix
r
- integer, index into rows of A
cols
- a *sorted* list of integers.

sage: a = matrix(QQ,2,3,range(6)); a
[0 1 2]
[3 4 5]
sage: a._set_row_to_negative_of_row_of_A_using_subset_of_columns(0,a,1,[1,2])
sage: a
[-4 -5  2]
[ 3  4  5]

_unpickle( )

Class: MatrixWindow

class MatrixWindow

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