Dense matrices over the integer ring.¶

AUTHORS:

William Stein
Robert Bradshaw

EXAMPLES:

sage: a = matrix(ZZ, 3,3, range(9)); a
[0 1 2]
[3 4 5]
[6 7 8]
sage: a.det()
0
sage: a[0,0] = 10; a.det()
-30
sage: a.charpoly()
x^3 - 22*x^2 + 102*x + 30
sage: b = -3*a
sage: a == b
False
sage: b < a
True

TESTS:

sage: a = matrix(ZZ,2,range(4), sparse=False)
sage: TestSuite(a).run()
sage: Matrix(ZZ,0,0).inverse()
[]

class sage.matrix.matrix_integer_dense.Matrix_integer_dense¶

Bases: sage.matrix.matrix_dense.Matrix_dense

Matrix over the integers.

On a 32-bit machine, they can have at most $2^{32}-1$ rows or columns. On a 64-bit machine, matrices can have at most $2^{64}-1$ rows or columns.

EXAMPLES:

sage: a = MatrixSpace(ZZ,3)(2); a
[2 0 0]
[0 2 0]
[0 0 2]
sage: a = matrix(ZZ,1,3, [1,2,-3]); a
[ 1  2 -3]
sage: a = MatrixSpace(ZZ,2,4)(2); a
...
TypeError: nonzero scalar matrix must be square

BKZ(delta=None, fp='rr', block_size=10, prune=0, use_givens=False)¶

Block Korkin-Zolotarev reduction.

INPUT:

fp - ‘fp’ - double precision: NTL’s FP or fpLLL’s double
'qd' - quad doubles: NTL’s QP
'qd1' - quad doubles: uses quad_float precision to compute Gram-Schmidt, but uses double precision in the search phase of the block reduction algorithm. This seems adequate for most purposes, and is faster than ‘qd’, which uses quad_float precision uniformly throughout.
'xd' - extended exponent: NTL’s XD
'rr' - arbitrary precision (default)
block_size - specifies the size of the blocks in the reduction. High values yield shorter vectors, but the running time increases exponentially with block_size. block_size should be between 2 and the number of rows of self (default: 10)
prune - The optional parameter prune can be set to any positive number to invoke the Volume Heuristic from [Schnorr and Horner, Eurocrypt ‘95]. This can significantly reduce the running time, and hence allow much bigger block size, but the quality of the reduction is of course not as good in general. Higher values of prune mean better quality, and slower running time. When prune == 0, pruning is disabled. Recommended usage: for block_size = 30, set 10 = prune = 15.
use_givens - use Given’s orthogonalization. This is a bit slower, but generally much more stable, and is really the preferred orthogonalization strategy. For a nice description of this, see Chapter 5 of [G. Golub and C. van Loan, Matrix Computations, 3rd edition, Johns Hopkins Univ. Press, 1996].

EXAMPLE:

sage: A = Matrix(ZZ,3,3,range(1,10))
sage: A.BKZ()
[ 0  0  0]
[ 2  1  0]
[-1  1  3]
sage: A = Matrix(ZZ,3,3,range(1,10))
sage: A.BKZ(use_givens=True)
[ 0  0  0]
[ 2  1  0]
[-1  1  3]

sage: A = Matrix(ZZ,3,3,range(1,10))
sage: A.BKZ(fp="fp")
[ 0  0  0]
[ 2  1  0]
[-1  1  3]

LLL(delta=None, eta=None, algorithm='fpLLL:wrapper', fp=None, prec=0, early_red=False, use_givens=False)¶

Returns LLL reduced or approximated LLL reduced lattice R for this matrix interpreted as a lattice.

A lattice $(b_1, b_2, ..., b_d)$ is $(\delta, \eta)$ -LLL-reduced if the two following conditions hold:

For any $i>j$ , we have $|mu_{i, j}| <= \eta$ ,
For any $i<d$ , we have $\delta |b_i^*|^2 <= |b_{i + 1}^* + mu_{i + 1, i} b_i^* |^2$ ,

where $mu_{i,j} = <b_i, b_j^*>/<b_j^*,b_j^*>$ and $b_i^*$ is the $i$ -th vector of the Gram-Schmidt orthogonalisation of $(b_1, b_2, ..., b_d)$ .

The default reduction parameters are $\delta=3/4$ and $eta=0.501$ . The parameters $\delta$ and $\eta$ must satisfy: $0.25 < \delta <= 1.0$ and $0.5 <= \eta < sqrt(\delta)$ . Polynomial time complexity is only guaranteed for $\delta < 1$ .

The lattice is returned as a matrix. Also the rank (and the determinant) of self are cached if those are computed during the reduction. Note that in general this only happens when self.rank() == self.ncols() and the exact algorithm is used.

INPUT:

delta - parameter as described above (default: 3/4)
eta - parameter as described above (default: 0.501), ignored by NTL
algorithm - string (default: “fpLLL:wrapper”) one of the algorithms mentioned below
fp
- None - NTL’s exact reduction or fpLLL’s wrapper
- 'fp' - double precision: NTL’s FP or fpLLL’s double
- 'qd' - quad doubles: NTL’s QP
- 'xd' - extended exponent: NTL’s XD or fpLLL’s dpe
- 'rr' - arbitrary precision: NTL’RR or fpLLL’s MPFR
prec - precision, ignored by NTL (default: auto choose)
early_red - perform early reduction, ignored by NTL (default: False)
use_givens - use Givens orthogonalization (default: False) only applicable to approximate reductions and NTL. This is more stable but slower.

Also, if the verbose level is = 2, some more verbose output is printed during the calculation if NTL is used.

AVAILABLE ALGORITHMS:
NTL:LLL - NTL’s LLL + fp
fpLLL:heuristic - fpLLL’s heuristic + fp
fpLLL:fast - fpLLL’s fast
fpLLL:wrapper - fpLLL’s automatic choice (default)

OUTPUT: a matrix over the integers

EXAMPLE:

sage: A = Matrix(ZZ,3,3,range(1,10))
sage: A.LLL()
[ 0  0  0]
[ 2  1  0]
[-1  1  3]

We compute the extended GCD of a list of integers using LLL, this example is from the Magma handbook:

sage: Q = [ 67015143, 248934363018, 109210, 25590011055, 74631449, \
            10230248, 709487, 68965012139, 972065, 864972271 ]
sage: n = len(Q)
sage: S = 100
sage: X = Matrix(ZZ, n, n + 1)
sage: for i in xrange(n):
...       X[i,i + 1] = 1
sage: for i in xrange(n): 
...       X[i,0] = S*Q[i]
sage: L = X.LLL()
sage: M = L.row(n-1).list()[1:]
sage: M
[-3, -1, 13, -1, -4, 2, 3, 4, 5, -1]
sage: add([Q[i]*M[i] for i in range(n)])
-1

ALGORITHM: Uses the NTL library by Victor Shoup or fpLLL library by Damien Stehle depending on the chosen algorithm.

REFERENCES:

ntl.mat_ZZ or sage.libs.fplll.fplll for details on the used algorithms.

LLL_gram()¶

LLL reduction of the lattice whose gram matrix is self.

INPUT:

M - gram matrix of a definite quadratic form

OUTPUT:

U - unimodular transformation matrix such that U.transpose() * M * U is LLL-reduced.

ALGORITHM: Use PARI

EXAMPLES:

sage: M = Matrix(ZZ, 2, 2, [5,3,3,2]) ; M
[5 3]
[3 2]
sage: U = M.LLL_gram(); U
[-1  1]
[ 1 -2]
sage: U.transpose() * M * U
[1 0]
[0 1]

Semidefinite and indefinite forms raise a ValueError:

sage: Matrix(ZZ,2,2,[2,6,6,3]).LLL_gram()
...
ValueError: not a definite matrix
sage: Matrix(ZZ,2,2,[1,0,0,-1]).LLL_gram()
...
ValueError: not a definite matrix

BUGS: should work for semidefinite forms (PARI is ok)

antitranspose()¶

Returns the antitranspose of self, without changing self.

EXAMPLES:

sage: A = matrix(2,3,range(6))
sage: type(A)
<type 'sage.matrix.matrix_integer_dense.Matrix_integer_dense'>
sage: A.antitranspose()
[5 2]
[4 1]
[3 0]
sage: A
[0 1 2]
[3 4 5]

sage: A.subdivide(1,2); A
[0 1|2]
[---+-]
[3 4|5]
sage: A.antitranspose()
[5|2]
[-+-]
[4|1]
[3|0]

charpoly(var='x', algorithm='linbox')¶

INPUT:

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

Note

Linbox charpoly disabled on 64-bit machines, since it hangs in many cases.

EXAMPLES:

sage: A = matrix(ZZ,6, range(36))
sage: f = A.charpoly(); f
x^6 - 105*x^5 - 630*x^4
sage: f(A) == 0
True
sage: n=20; A = Mat(ZZ,n)(range(n^2))
sage: A.charpoly()
x^20 - 3990*x^19 - 266000*x^18
sage: A.minpoly()          
x^3 - 3990*x^2 - 266000*x

decomposition(**kwds)¶

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, and are saturated as ZZ modules.

INPUT:

self - a matrix over the integers
**kwds - these are passed onto to the decomposition over QQ command.

EXAMPLES:

sage: t = ModularSymbols(11,sign=1).hecke_matrix(2)
sage: w = t.change_ring(ZZ)
sage: w.list()
[3, -1, 0, -2]

determinant(algorithm='default', proof=None, stabilize=2)¶

Return the determinant of this matrix.

INPUT:

algorithm
- 'default' – use ‘pari’ when number of rows less than 50;
  
  otherwise, use ‘padic’
- 'padic' - uses a p-adic / multimodular algorithm that relies on code in IML and linbox
- 'linbox' - calls linbox det (you must set proof=False to use this!)
- 'ntl' - calls NTL’s det function
- 'pari' - uses PARI
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.
stabilize - if proof is False, require det to be the same for this many CRT primes in a row. Ignored if proof is True.

ALGORITHM: The p-adic algorithm works by first finding a random vector v, then solving A*x = v and taking the denominator $d$ . This gives a divisor of the determinant. Then we compute $\det(A)/d$ using a multimodular algorithm and the Hadamard bound, skipping primes that divide $d$ .

TIMINGS: This is perhaps the fastest implementation of determinants in the world. E.g., for a 500x500 random matrix with 32-bit entries on a core2 duo 2.6Ghz running OS X, Sage takes 4.12 seconds, whereas Magma takes 62.87 seconds (both with proof False). With proof=True on the same problem Sage takes 5.73 seconds. For another example, a 200x200 random matrix with 1-digit entries takes 4.18 seconds in pari, 0.18 in Sage with proof True, 0.11 in Sage with proof False, and 0.21 seconds in Magma with proof True and 0.18 in Magma with proof False.

EXAMPLES:

sage: A = matrix(ZZ,8,8,[3..66])
sage: A.determinant()
0

sage: A = random_matrix(ZZ,20,20)
sage: D1 = A.determinant()
sage: A._clear_cache()
sage: D2 = A.determinant(algorithm='ntl')
sage: D1 == D2
True

Next we try the Linbox det. Note that we must have proof=False.

sage: A = matrix(ZZ,5,[1,2,3,4,5,4,6,3,2,1,7,9,7,5,2,1,4,6,7,8,3,2,4,6,7])
sage: A.determinant(algorithm='linbox')
...
RuntimeError: you must pass the proof=False option to the determinant command to use LinBox's det algorithm
sage: A.determinant(algorithm='linbox',proof=False)
-21
sage: A._clear_cache()
sage: A.determinant()
-21

A bigger example:

sage: A = random_matrix(ZZ,30)
sage: d = A.determinant()
sage: A._clear_cache()
sage: A.determinant(algorithm='linbox',proof=False) == d
True

echelon_form(algorithm='default', proof=None, include_zero_rows=True, transformation=False, D=None)¶

Return the echelon form of this matrix over the integers, also known as the hermit normal form (HNF).

INPUT:

algorithm

–'default' - max 10 rows or columns: pari with flag 0

max 75 rows or columns: pari with flag 1 larger – use padic algorithm
- 'padic' - an asymptotically fast p-adic modular algorithm,
  
  If your matrix has large coefficients and is small, you may also want to try this.
- 'pari' - use PARI with flag 1
- 'pari0' - use PARI with flag 0
- 'pari4' - use PARI with flag 4 (use heuristic LLL)
- 'ntl' - use NTL (only works for square matrices of
  
  full rank!)
proof - (default: True); if proof=False certain determinants are computed using a randomized hybrid p-adic multimodular strategy until it stabilizes twice (instead of up to the Hadamard bound). It is incredibly unlikely that one would ever get an incorrect result with proof=False.
include_zero_rows - (default: True) if False, don’t include zero rows
transformation - if given, also compute transformation matrix; only valid for padic algorithm
D - (default: None) if given and the algorithm is ‘ntl’, then D must be a multiple of the determinant and this function will use that fact.

OUTPUT:

matrix - the Hermite normal form (=echelon form over ZZ) of self.

Note

The result is not cached.

EXAMPLES:

sage: A = MatrixSpace(ZZ,2)([1,2,3,4])
sage: A.echelon_form()
[1 0]
[0 2]
sage: A = MatrixSpace(ZZ,5)(range(25))
sage: A.echelon_form()
[  5   0  -5 -10 -15]
[  0   1   2   3   4]
[  0   0   0   0   0]
[  0   0   0   0   0]
[  0   0   0   0   0]

Getting a transformation matrix in the nonsquare case:

sage: A = matrix(ZZ,5,3,[1..15])
sage: H, U = A.hermite_form(transformation=True, include_zero_rows=False)
sage: H
[1 2 3]
[0 3 6]
sage: U
[  0   0   0   4  -3]
[  0   0   0  13 -10]
sage: U*A == H
True

TESTS: Make sure the zero matrices are handled correctly:

sage: m = matrix(ZZ,3,3,[0]*9)
sage: m.echelon_form() 
[0 0 0]
[0 0 0]
[0 0 0]
sage: m = matrix(ZZ,3,1,[0]*3)
sage: m.echelon_form()
[0]
[0]
[0]
sage: m = matrix(ZZ,1,3,[0]*3)
sage: m.echelon_form()
[0 0 0]

The ultimate border case!

sage: m = matrix(ZZ,0,0,[])        
sage: m.echelon_form()
[]

Note

If ‘ntl’ is chosen for a non square matrix this function raises a ValueError.

Special cases: 0 or 1 rows:

sage: a = matrix(ZZ, 1,2,[0,-1])
sage: a.hermite_form()
[0 1]
sage: a.pivots()
[1]
sage: a = matrix(ZZ, 1,2,[0,0])
sage: a.hermite_form()
[0 0]
sage: a.pivots()
[]
sage: a = matrix(ZZ,1,3); a
[0 0 0]
sage: a.echelon_form(include_zero_rows=False)
[]
sage: a.echelon_form(include_zero_rows=True)
[0 0 0]

Illustrate using various algorithms.:

sage: matrix(ZZ,3,[1..9]).hermite_form(algorithm='pari')
[1 2 3]
[0 3 6]
[0 0 0]
sage: matrix(ZZ,3,[1..9]).hermite_form(algorithm='pari0')
[1 2 3]
[0 3 6]
[0 0 0]
sage: matrix(ZZ,3,[1..9]).hermite_form(algorithm='pari4')
[1 2 3]
[0 3 6]
[0 0 0]
sage: matrix(ZZ,3,[1..9]).hermite_form(algorithm='padic')
[1 2 3]
[0 3 6]
[0 0 0]
sage: matrix(ZZ,3,[1..9]).hermite_form(algorithm='default')
[1 2 3]
[0 3 6]
[0 0 0]

The ‘ntl’ algorithm doesn’t work on matrices that do not have full rank.:

sage: matrix(ZZ,3,[1..9]).hermite_form(algorithm='ntl')
...
ValueError: ntl only computes HNF for square matrices of full rank.
sage: matrix(ZZ,3,[0] +[2..9]).hermite_form(algorithm='ntl')
[1 0 0]
[0 1 0]
[0 0 3]

elementary_divisors(algorithm='pari')¶

Return the elementary divisors of self, in order.

Warning

This is MUCH faster than the smith_form function.

The elementary divisors are the invariants of the finite abelian group that is the cokernel of left multiplication of this matrix. They are ordered in reverse by divisibility.

INPUT:

self - matrix
algorithm - (default: ‘pari’)
- 'pari': works robustly, but is slower.
- 'linbox' - use linbox (currently off, broken)

OUTPUT: list of integers

Note

These are the invariants of the cokernel of left multiplication:

sage: M = Matrix([[3,0,1],[0,1,0]])
sage: M
[3 0 1]
[0 1 0]
sage: M.elementary_divisors()
[1, 1]
sage: M.transpose().elementary_divisors()
[1, 1, 0]        

EXAMPLES:

sage: matrix(3, range(9)).elementary_divisors()
[1, 3, 0]
sage: matrix(3, range(9)).elementary_divisors(algorithm='pari')
[1, 3, 0]
sage: C = MatrixSpace(ZZ,4)([3,4,5,6,7,3,8,10,14,5,6,7,2,2,10,9])
sage: C.elementary_divisors()
[1, 1, 1, 687]

sage: M = matrix(ZZ, 3, [1,5,7, 3,6,9, 0,1,2])
sage: M.elementary_divisors()
[1, 1, 6]

This returns a copy, which is safe to change:

sage: edivs = M.elementary_divisors()
sage: edivs.pop()
6
sage: M.elementary_divisors()
[1, 1, 6]

See also

smith_form()

frobenius(flag=0, var='x')¶

Return the Frobenius form (rational canonical form) of this matrix.

INPUT: flag -an integer:

0 - (default) return the Frobenius form of this matrix.
1 - return only the elementary divisor polynomials, as polynomials in var.
2 - return a two-components vector [F,B] where F is the Frobenius form and B is the basis change so that $M=B^{-1}FB$ .
var - a string (default: ‘x’)

INPUT:

flag - 0 (default), 1 or 2 as described above

ALGORITHM: uses pari’s matfrobenius()

EXAMPLE:

sage: A = MatrixSpace(ZZ, 3)(range(9))
sage: A.frobenius(0)
[ 0  0  0]
[ 1  0 18]
[ 0  1 12]
sage: A.frobenius(1)
[x^3 - 12*x^2 - 18*x]
sage: A.frobenius(1, var='y')
[y^3 - 12*y^2 - 18*y]
sage: A.frobenius(2)
(
[ 0  0  0]  [    -1      2     -1]
[ 1  0 18]  [     0  23/15 -14/15]
[ 0  1 12], [     0  -2/15   1/15]
)
sage: a=matrix([])
sage: a.frobenius(2)
([], [])
sage: a.frobenius(0)
[]
sage: a.frobenius(1)
[]
sage: B = random_matrix(ZZ,2,3)
sage: B.frobenius()
...
ArithmeticError: frobenius matrix of non-square matrix not defined.

AUTHORS:

Martin Albrect (2006-04-02)

TODO: - move this to work for more general matrices than just over Z. This will require fixing how PARI polynomials are coerced to Sage polynomials.

gcd()¶

Return the gcd of all entries of self; very fast.

EXAMPLES:

sage: a = matrix(ZZ,2, [6,15,-6,150])
sage: a.gcd()
3

height()¶

Return the height of this matrix, i.e., the max absolute value of the entries of the matrix.

OUTPUT: A nonnegative integer.

EXAMPLE:

sage: a = Mat(ZZ,3)(range(9))
sage: a.height()
8
sage: a = Mat(ZZ,2,3)([-17,3,-389,15,-1,0]); a
[ -17    3 -389]
[  15   -1    0]
sage: a.height()
389

hermite_form(*args, **kwds)¶

Return the Hermite normal form of self.

This is a synonym for self.echelon_form(...). See the documentation for self.echelon_form for more details.

EXAMPLES:

sage: A = matrix(ZZ, 3, 5, [-1, -1, -2, 2, -2, -4, -19, -17, 1, 2, -3, 1, 1, -4, 1])
sage: E, U = A.hermite_form(transformation=True)
sage: E
[   1    0   52 -133  109]
[   0    1   19  -47   38]
[   0    0   69 -178  145]
sage: U
[-46   3  11]
[-16   1   4]
[-61   4  15]
sage: U*A
[   1    0   52 -133  109]
[   0    1   19  -47   38]
[   0    0   69 -178  145]
sage: A.hermite_form()
[   1    0   52 -133  109]
[   0    1   19  -47   38]
[   0    0   69 -178  145]

TESTS: This example illustrated trac 2398.

sage: a = matrix([(0, 0, 3), (0, -2, 2), (0, 1, 2), (0, -2, 5)])
sage: a.hermite_form()
[0 1 2]
[0 0 3]
[0 0 0]
[0 0 0]

index_in_saturation(proof=None)¶

Return the index of self in its saturation.

INPUT:

proof - (default: use proof.linear_algebra()); if False, the determinant calculations are done with proof=False.

OUTPUT:

positive integer - the index of the row span of this matrix in its saturation

ALGORITHM: Use Hermite normal form twice to find an invertible matrix whose inverse transforms a matrix with the same row span as self to its saturation, then compute the determinant of that matrix.

EXAMPLES:

sage: A = matrix(ZZ, 2,3, [1..6]); A
[1 2 3]
[4 5 6]
sage: A.index_in_saturation()
3
sage: A.saturation()
[1 2 3]
[1 1 1]

insert_row(index, row)¶

Create a new matrix from self with.

INPUT:

index - integer
row - a vector

EXAMPLES:

sage: X = matrix(ZZ,3,range(9)); X
[0 1 2]
[3 4 5]
[6 7 8]
sage: X.insert_row(1, [1,5,-10])
[  0   1   2]
[  1   5 -10]
[  3   4   5]
[  6   7   8]
sage: X.insert_row(0, [1,5,-10])
[  1   5 -10]
[  0   1   2]
[  3   4   5]
[  6   7   8]
sage: X.insert_row(3, [1,5,-10])
[  0   1   2]
[  3   4   5]
[  6   7   8]
[  1   5 -10]

is_LLL_reduced(delta=None, eta=None)¶

Return True if this lattice is $(\delta, \eta)$ -LLL reduced. See self.LLL for a definition of LLL reduction.

INPUT:

delta - parameter as described above (default: 3/4)
eta - parameter as described above (default: 0.501)

EXAMPLE:

sage: A = random_matrix(ZZ, 10, 10)
sage: L = A.LLL()
sage: A.is_LLL_reduced()
False
sage: L.is_LLL_reduced()
True

kernel_matrix(algorithm='default', LLL=False, proof=None)¶

The options are exactly like self.kernel(...), but returns a matrix A whose rows form a basis for the left kernel, i.e., so that A*self = 0.

This is mainly useful to avoid all overhead associated with creating a free module.

INPUT:

algorithm – ‘default’, ‘pari’, or ‘padic’;

default – choose from one of the below based

on heuristic

'pari' – uses pari’s matkerint function; good

for small matrices

'padic' – uses an asymptotically fast p-adic

algorithm; horrible for small matrices, but great for large mxn matrices with m+3 <= n.

LLL – whether to LLL reduce result (default: False)

proof – whether result is provably correct (only

relevant for padic algorithm)

EXAMPLES:

sage: A = matrix(ZZ, 3, 3, [1..9])
sage: A.kernel_matrix()
[ 1 -2  1]

Note that the basis matrix returned above is not in Hermite/echelon form.

sage: A.kernel()
Free module of degree 3 and rank 1 over Integer Ring
Echelon basis matrix:
[ 1 -2  1]

We compute another kernel:

sage: A = matrix(ZZ, 4, 2, [2, -1, 1, 1, -18, -1, -1, -5])
sage: K = A.kernel_matrix(); K
[ -7  -3  -1   1]
[  4 -11   0  -3]

K is a basis for the left kernel:

sage: K*A
[0 0]
[0 0]

We illustrate the LLL flag:

sage: L = A.kernel_matrix(LLL=True); L
[ -7  -3  -1   1]
[  4 -11   0  -3]
sage: K.hermite_form()
[ 1 64  3 12]
[ 0 89  4 17]
sage: L.hermite_form()
[ 1 64  3 12]
[ 0 89  4 17]

Two kernel matrices via PARI, one of full rank:

sage: B = matrix(ZZ, [[2,-1,1],[1,-1,0],[-5,4,-1],[-8,6,-2]])
sage: B.kernel_matrix(algorithm='pari')
[ 1  1 -1  1]
[ 0  2  2 -1]
sage: C = matrix(ZZ, [[1,1,2],[1,1,4]])
sage: D = C.kernel_matrix(algorithm='pari'); D
[]
sage: D.ncols()
2

minpoly(var='x', algorithm='linbox')¶

INPUT:

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

Note

Linbox charpoly disabled on 64-bit machines, since it hangs in many cases.

EXAMPLES:

sage: A = matrix(ZZ,6, range(36))
sage: A.minpoly()
x^3 - 105*x^2 - 630*x
sage: n=6; A = Mat(ZZ,n)([k^2 for k in range(n^2)])
sage: A.minpoly()
x^4 - 2695*x^3 - 257964*x^2 + 1693440*x

pivots()¶

Return the pivot column positions of this matrix as a list of Python integers.

This returns a list, of the position of the first nonzero entry in each row of the echelon form.

OUTPUT:

list - a list of Python ints

EXAMPLES:

sage: n = 3; A = matrix(ZZ,n,range(n^2)); A
[0 1 2]
[3 4 5]
[6 7 8]
sage: A.pivots()
[0, 1]
sage: A.echelon_form()
[ 3  0 -3]
[ 0  1  2]
[ 0  0  0]

prod_of_row_sums(cols)¶

Return the product of the sums of the entries in the submatrix of self with given columns.

INPUT:

cols - a list (or set) of integers representing columns of self.

OUTPUT: an integer

EXAMPLES:

sage: a = matrix(ZZ,2,3,[1..6]); a
[1 2 3]
[4 5 6]
sage: a.prod_of_row_sums([0,2])
40
sage: (1+3)*(4+6)
40
sage: a.prod_of_row_sums(set([0,2]))
40

randomize(density=1, x=None, y=None, distribution=None, nonzero=False)¶

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

The parameters are the same as the ones for the integer ring’s random_element function.

If x and y are given, randomized entries of this matrix have to be between x and y and have density 1.

INPUT:

self - a mutable matrix over ZZ
density - a float between 0 and 1
x, y - if not None, these are passed to the ZZ.random_element function as the upper and lower endpoints in the uniform distribution
distribution - would also be passed into ZZ.random_element if given
nonzero - bool (default: False); whether the new entries are guaranteed to be zero

OUTPUT:

None, the matrix is modified in-place

EXAMPLES:

sage: A = matrix(ZZ, 2,3, [1..6]); A
[1 2 3]
[4 5 6]
sage: A.randomize()
sage: A
[-8  2  0]
[ 0  1 -1]
sage: A.randomize(x=-30,y=30)
sage: A
[  5 -19  24]
[ 24  23  -9]

rank()¶

Return the rank of this matrix.

OUTPUT:

nonnegative integer - the rank

Note

The rank is cached.

ALGORITHM: First check if the matrix has maxim possible rank by working modulo one random prime. If not call LinBox’s rank function.

EXAMPLES:

sage: a = matrix(ZZ,2,3,[1..6]); a
[1 2 3]
[4 5 6]
sage: a.rank()
2
sage: a = matrix(ZZ,3,3,[1..9]); a
[1 2 3]
[4 5 6]
[7 8 9]
sage: a.rank()
2

Here’s a bigger example - the rank is of course still 2:

sage: a = matrix(ZZ,100,[1..100^2]); a.rank()
2

rational_reconstruction(N)¶

Use rational reconstruction to lift self to a matrix over the rational numbers (if possible), where we view self as a matrix modulo N.

INPUT:

N - an integer

OUTPUT:

matrix - over QQ or raise a ValueError

EXAMPLES: We create a random 4x4 matrix over ZZ.

sage: A = matrix(ZZ, 4, [4, -4, 7, 1, -1, 1, -1, -12, -1, -1, 1, -1, -3, 1, 5, -1])

There isn’t a unique rational reconstruction of it:

sage: A.rational_reconstruction(11)
...
ValueError: Rational reconstruction of 4 (mod 11) does not exist.

We throw in a denominator and reduce the matrix modulo 389 - it does rationally reconstruct.

sage: B = (A/3 % 389).change_ring(ZZ)
sage: B.rational_reconstruction(389) == A/3
True

right_kernel(algorithm='default', LLL=False, proof=None, echelonize=True)¶

Return the right kernel of a matrix over the integers.

INPUT:

algorithm - see the docs for self.kernel_matrix
LLL - bool (default: False); if True the basis is an LLL reduced basis; otherwise, it is an echelon basis.
proof - None (default: proof.linear_algebra()); if False, impacts how determinants are computed.

OUTPUT: A module over the integers is returned. This is the saturated ZZ-module spanned by all the column vectors v such that self*v = 0.

EXAMPLES:

sage: M = MatrixSpace(ZZ,2,4)(range(8))
sage: M.right_kernel()
Free module of degree 4 and rank 2 over Integer Ring
Echelon basis matrix:
[ 1  0 -3  2]
[ 0  1 -2  1]

With zero columns the right kernel has dimension 0.

sage: M = matrix(ZZ, [[],[],[]])
sage: M.right_kernel()
Free module of degree 0 and rank 0 over Integer Ring
Echelon basis matrix:
[]

With zero rows, the whole domain is the kernel, so the dimension is the number of columns.

sage: M = matrix(ZZ, [[],[],[]]).transpose()
sage: M.right_kernel()
Ambient free module of rank 3 over the principal ideal domain Integer Ring

saturation(p=0, proof=None, max_dets=5)¶

Return a saturation matrix of self, which is a matrix whose rows span the saturation of the row span of self. This is not unique.

The saturation of a $\ZZ$ module $M$ embedded in $\ZZ^n$ is the a module $S$ that contains $M$ with finite index such that $\ZZ^n/S$ is torsion free. This function takes the row span $M$ of self, and finds another matrix of full rank with row span the saturation of $M$ .

INPUT:

p - (default: 0); if nonzero given, saturate only at the prime $p$ , i.e., return a matrix whose row span is a $\ZZ$ -module $S$ that contains self and such that the index of $S$ in its saturation is coprime to $p$ . If $p$ is None, return full saturation of self.
proof - (default: use proof.linear_algebra()); if False, the determinant calculations are done with proof=False.
max_dets - (default: 5); technical parameter - max number of determinant to compute when bounding prime divisor of self in its saturation.

OUTPUT:

matrix - a matrix over ZZ

Note

The result is not cached.

ALGORITHM: 1. Replace input by a matrix of full rank got from a subset of the rows. 2. Divide out any common factors from rows. 3. Check max_dets random dets of submatrices to see if their GCD (with p) is 1 - if so matrix is saturated and we’re done. 4. Finally, use that if A is a matrix of full rank, then $hnf(transpose(A))^{-1}*A$ is a saturation of A.

EXAMPLES:

sage: A = matrix(ZZ, 3, 5, [-51, -1509, -71, -109, -593, -19, -341, 4, 86, 98, 0, -246, -11, 65, 217])
sage: A.echelon_form()
[      1       5    2262   20364   56576]
[      0       6   35653  320873  891313]
[      0       0   42993  386937 1074825]
sage: S = A.saturation(); S
[  -51 -1509   -71  -109  -593]
[  -19  -341     4    86    98]
[   35   994    43    51   347]

Notice that the saturation spans a different module than A.

sage: S.echelon_form()
[ 1  2  0  8 32]
[ 0  3  0 -2 -6]
[ 0  0  1  9 25]
sage: V = A.row_space(); W = S.row_space()
sage: V.is_submodule(W)
True
sage: V.index_in(W)
85986
sage: V.index_in_saturation()
85986

We illustrate each option:

sage: S = A.saturation(p=2)
sage: S = A.saturation(proof=False)
sage: S = A.saturation(max_dets=2)

smith_form()¶

Returns matrices S, U, and V such that S = U*self*V, and S is in Smith normal form. Thus S is diagonal with diagonal entries the ordered elementary divisors of S.

Warning

The elementary_divisors function, which returns the diagonal entries of S, is VASTLY faster than this function.

The elementary divisors are the invariants of the finite abelian group that is the cokernel of this matrix. They are ordered in reverse by divisibility.

EXAMPLES:

sage: A = MatrixSpace(IntegerRing(), 3)(range(9))
sage: D, U, V = A.smith_form()
sage: D
[1 0 0]
[0 3 0]
[0 0 0]
sage: U
[ 0  1  0]
[ 0 -1  1]
[-1  2 -1]
sage: V
[-1  4  1]
[ 1 -3 -2]
[ 0  0  1]
sage: U*A*V
[1 0 0]
[0 3 0]
[0 0 0]

It also makes sense for nonsquare matrices:

sage: A = Matrix(ZZ,3,2,range(6))
sage: D, U, V = A.smith_form()
sage: D
[1 0]
[0 2]
[0 0]
sage: U
[ 0  1  0]
[ 0 -1  1]
[-1  2 -1]
sage: V
[-1  3]
[ 1 -2]
sage: U * A * V
[1 0]
[0 2]
[0 0]

Empty matrices are handled sensibly (see trac #3068):

sage: m = MatrixSpace(ZZ, 2,0)(0); d,u,v = m.smith_form(); u*m*v == d
True
sage: m = MatrixSpace(ZZ, 0,2)(0); d,u,v = m.smith_form(); u*m*v == d
True
sage: m = MatrixSpace(ZZ, 0,0)(0); d,u,v = m.smith_form(); u*m*v == d
True