AUTHORS:
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: loads(dumps(a)) == a
True
sage: Matrix(ZZ,0,0).inverse()
[]
Matrix over the integers.
On a 32-bit machine, they can have at most rows or
columns. On a 64-bit machine, matrices can have at most
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
Block Korkin-Zolotarev reduction.
INPUT:
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]
Returns LLL reduced or approximated LLL reduced lattice R for this matrix interpreted as a lattice.
A lattice is
-LLL-reduced if the two following
conditions hold:
where and
is the
-th vector of the Gram-Schmidt
orthogonalisation of
.
The default reduction parameters are and
. The parameters
and
must satisfy:
and
. Polynomial time
complexity is only guaranteed for
.
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:
LLL reduction of the lattice whose gram matrix is self.
INPUT:
OUTPUT:
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)
Returns a new copy of this matrix.
EXAMPLES:
sage: a = matrix(ZZ,1,3, [1,2,-3]); a
[ 1 2 -3]
sage: b = a.__copy__(); b
[ 1 2 -3]
sage: b is a
False
sage: b == a
True
Add two dense matrices over ZZ.
EXAMPLES:
sage: a = MatrixSpace(ZZ,3)(range(9))
sage: a+a
[ 0 2 4]
[ 6 8 10]
[12 14 16]
sage: b = MatrixSpace(ZZ,3)(range(9))
sage: b.swap_rows(1,2)
sage: a+b
[ 0 2 4]
[ 9 11 13]
[ 9 11 13]
Assuming self is a full rank n x m matrix in reduced row Echelon form over ZZ and row is a vector of degree m, this function creates a new matrix that is the echelon form of self with row appended to the bottom.
Warning
It is assumed that self is in echelon form.
INPUT:
OUTPUT:
ALGORITHM: For each pivot column of self, we use the extended Euclidean algorithm to clear the column. The result is a new matrix B whose row span is the same as self.stack(row), and whose last row is 0 if and only if row is in the QQ-span of the rows of self. If row is not in the QQ-span of the rows of self, then row is nonzero and suitable to be inserted into the top n rows of A to form a new matrix that is in reduced row echelon form. We then clear that corresponding new pivot column.
EXAMPLES:
sage: a = matrix(ZZ, 3, [1, 0, 110, 0, 3, 112, 0, 0, 221]); a
[ 1 0 110]
[ 0 3 112]
[ 0 0 221]
sage: a._add_row_and_maintain_echelon_form(vector(ZZ,[1,2,3]),[0,1,2])
([1 0 0]
[0 1 0]
[0 0 1], [0, 1, 2])
sage: a._add_row_and_maintain_echelon_form(vector(ZZ,[0,0,0]),[0,1,2])
([ 1 0 110]
[ 0 3 112]
[ 0 0 221], [0, 1, 2])
sage: a = matrix(ZZ, 2, [1, 0, 110, 0, 3, 112])
sage: a._add_row_and_maintain_echelon_form(vector(ZZ,[1,2,3]),[0,1])
([ 1 0 110]
[ 0 1 219]
[ 0 0 545], [0, 1, 2])
Return the adjoint of this matrix.
Assumes self is a square matrix (checked in adjoint).
EXAMPLES:
sage: m = matrix(ZZ,3,[1..9])
sage: m.adjoint()
[ -3 6 -3]
[ 6 -12 6]
[ -3 6 -3]
Return the matrix obtained by coercing the entries of this matrix into the given ring.
EXAMPLES:
sage: a = matrix(ZZ,2,[1,-7,3,5])
sage: a._change_ring(RDF)
[ 1.0 -7.0]
[ 3.0 5.0]
Return matrix obtained from self by deleting all zero columns along with the positions of those columns.
OUTPUT: matrix list of integers
EXAMPLES:
sage: a = matrix(ZZ, 2,3, [1,0,3,-1,0,5]); a
[ 1 0 3]
[-1 0 5]
sage: a._delete_zero_columns()
([ 1 3]
[-1 5], [1])
Determinant of this matrix using Gauss-Bareiss. If (optional) flag is set to 1, use classical Gaussian elimination.
For efficiency purposes, this det is computed entirely on the PARI stack then the PARI stack is cleared. This function is most useful for very small matrices.
EXAMPLES:
sage: matrix(ZZ,3,[1..9])._det_pari()
0
sage: matrix(ZZ,3,[1..9])._det_pari(1)
0
Return space separated string of the entries in this matrix, in the given base. This is optimized for speed.
INPUT: base -an integer = 36; (default: 10)
EXAMPLES:
sage: m = matrix(ZZ,2,3,[1,2,-3,1,-2,-45])
sage: m._export_as_string(10)
'1 2 -3 1 -2 -45'
sage: m._export_as_string(16)
'1 2 -3 1 -2 -2d'
Very very quickly modifies self so that the gcd of the entries in each row is 1 by dividing each row by the common gcd.
EXAMPLES:
sage: a = matrix(ZZ, 3, [-9, 3, -3, -36, 18, -5, -40, -5, -5, -20, -45, 15, 30, -15, 180])
sage: a
[ -9 3 -3 -36 18]
[ -5 -40 -5 -5 -20]
[-45 15 30 -15 180]
sage: a._factor_out_common_factors_from_each_row()
sage: a
[ -3 1 -1 -12 6]
[ -1 -8 -1 -1 -4]
[ -3 1 2 -1 12]
INPUT:
OUTPUT:
Hermite form of this matrix, computed using PARI. The computation is done entirely on the PARI stack, then the PARI stack is cleared. This function is only useful for small matrices, and can crash on large matrices (e.g., if the PARI stack overflows).
flag – 0 (default), 1, 3 or 4 (see docstring for gp.mathnf). include_zero_rows – if False, do not include any of the zero
rows at the bottom of the matrix in the output.
NOTE: In no cases is the transformation matrix returned by this function.
EXAMPLES:
sage: matrix(ZZ,3,[1..9])._hnf_pari()
[1 2 3]
[0 3 6]
[0 0 0]
sage: matrix(ZZ,3,[1..9])._hnf_pari(include_zero_rows=False)
[1 2 3]
[0 3 6]
sage: matrix(ZZ,3,[1..9])._hnf_pari(1)
[1 2 3]
[0 3 6]
[0 0 0]
sage: matrix(ZZ,3,[1..9])._hnf_pari(3)
[1 2 3]
[0 3 6]
[0 0 0]
sage: matrix(ZZ,3,[1..9])._hnf_pari(4)
[1 2 3]
[0 3 6]
[0 0 0]
Hermite form of this matrix, computed using PARI.
flag – 0 (default), 1, 3 or 4 (see docstring for gp.mathnf). include_zero_rows – if False, do not include any of the zero
rows at the bottom of the matrix in the output.
NOTE: In no cases is the transformation matrix returned by this function.
EXAMPLES:
sage: a = matrix(ZZ,3,3,[1..9])
sage: a._hnf_pari_big(flag=1, include_zero_rows=False)
[1 2 3]
[0 3 6]
Return matrix obtained by self by inserting zero columns so that the columns with positions specified in cols are all 0.
INPUT:
OUTPUT: matrix
EXAMPLES:
sage: a = matrix(ZZ, 2,3, [1,0,3,-1,0,5]); a
[ 1 0 3]
[-1 0 5]
sage: b, cols = a._delete_zero_columns()
sage: b
[ 1 3]
[-1 5]
sage: cols
[1]
sage: b._insert_zero_columns(cols)
[ 1 0 3]
[-1 0 5]
Invert this matrix using IML. The output matrix is an integer matrix and a denominator.
INPUT:
OUTPUT: A, d such that A*self = d
ALGORITHM: Uses IML’s p-adic nullspace function.
EXAMPLES:
sage: a = matrix(ZZ,3,[1,2,5, 3,7,8, 2,2,1])
sage: b, d = a._invert_iml(); b,d
([ 9 -8 19]
[-13 9 -7]
[ 8 -2 -1], 23)
sage: a*b
[23 0 0]
[ 0 23 0]
[ 0 0 23]
AUTHORS:
Compute a list of independent generators that span the right kernel of self.
ALGORITHM: Use IML to compute the right kernel over QQ, clear denominators, then saturate.
Compute an LLL reduced list of independent generators that span the right kernel of self.
EXAMPLES:
A matrix of generators for a simple matrix of rank 2:
sage: M = MatrixSpace(ZZ,2,4)(range(8))
sage: M
[0 1 2 3]
[4 5 6 7]
sage: M._kernel_matrix_using_pari()
[ 1 -1 -1 1]
[ 0 -1 2 -1]
Testing matrices with no rows or no columns:
sage: N = MatrixSpace(ZZ,0,4)()
sage: N
[]
sage: N._kernel_matrix_using_pari()
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]
sage: P=MatrixSpace(ZZ,4,0)()
sage: P
[]
sage: P._kernel_matrix_using_pari()
[]
ALGORITHM: Call pari’s matkerint function.
Return modn linbox object associated to this integer matrix.
EXAMPLES:
sage: a = matrix(ZZ, 3, [1,2,5,-7,8,10,192,5,18])
sage: b = a._linbox_modn(19); b
<sage.libs.linbox.linbox.Linbox_modn_dense object at ...>
sage: b.charpoly()
[2L, 10L, 11L, 1L]
INPUT:
EXAMPLES:
sage: a = matrix(ZZ, 3, [1,2,5,-7,8,10,192,5,18])
sage: a.det()
-3669
sage: a._linbox_modn_det(5077)
1408
sage: a._linbox_modn_det(3)
0
sage: a._linbox_modn_det(2)
1
sage: a.det()%5077
1408
sage: a.det()%2
1
sage: a.det()%3
0
EXAMPLES:
sage: a = matrix(QQ,2,range(6))
sage: (3/4) * a
[ 0 3/4 3/2]
[ 9/4 3 15/4]
EXAMPLES:
sage: m = matrix(ZZ,2,3,[1,2,-3,1,-2,-45])
sage: m._magma_init_(magma)
'Matrix(IntegerRing(),2,3,StringToIntegerSequence("1 2 -3 1 -2 -45"))'
sage: magma(m) # optional - magma
[ 1 2 -3]
[ 1 -2 -45]
EXAMPLE:
sage: n = 3
sage: a = MatrixSpace(ZZ,n,n)(range(n^2))
sage: b = MatrixSpace(ZZ,n,n)(range(1, n^2 + 1))
sage: a._multiply_classical(b)
[ 18 21 24]
[ 54 66 78]
[ 90 111 132]
Multiply matrices over ZZ using linbox.
Warning
This is very slow right now, i.e., linbox is very slow.
EXAMPLES:
sage: A = matrix(ZZ,2,3,range(6))
sage: A*A.transpose()
[ 5 14]
[14 50]
sage: A._multiply_linbox(A.transpose())
[ 5 14]
[14 50]
Multiply this matrix by left using a multi modular algorithm.
EXAMPLES:
sage: M = Matrix(ZZ, 2, 3, range(5,11))
sage: N = Matrix(ZZ, 3, 2, range(15,21))
sage: M._multiply_multi_modular(N)
[310 328]
[463 490]
sage: M._multiply_multi_modular(-N)
[-310 -328]
[-463 -490]
ntl.mat_ZZ representation of self.
EXAMPLE:
sage: a = MatrixSpace(ZZ,200).random_element(x=-2, y=2) # -2 to 2
sage: A = a._ntl_()
Note
NTL only knows dense matrices, so if you provide a sparse matrix NTL will allocate memory for every zero entry.
Return PARI C-library version of this matrix.
EXAMPLES:
sage: a = matrix(ZZ,2,2,[1,2,3,4])
sage: a._pari_()
[1, 2; 3, 4]
sage: pari(a)
[1, 2; 3, 4]
sage: type(pari(a))
<type 'sage.libs.pari.gen.gen'>
EXAMPLES:
sage: a = matrix(ZZ,2,3,[1,193,15,-2,3,0])
sage: a._pickle()
('1 61 f -2 3 0', 0)
sage: S = ModularSymbols(250,4,sign=1).cuspidal_submodule().new_subspace().decomposition() # long time
sage: S == loads(dumps(S)) # long time
True
INPUT:
Rank of this matrix, computed using PARI. The computation is done entirely on the PARI stack, then the PARI stack is cleared. This function is most useful for very small matrices.
Computes information that gives the reduced row echelon form (over QQ!) of a matrix with integer entries.
INPUT:
OUTPUT:
If you put standard basis vectors in order at the pivot columns, and put the matrix (1/d)*X everywhere else, then you get the reduced row echelon form of self, without zero rows at the bottom.
Note
IML is the actual underlying -adic solver that we
use.
AUTHORS:
ALGORITHM: I came up with this algorithm from scratch. As far as I know it is new. It’s pretty simple, but it is ... (fast?!).
Let A be the input matrix.
IML: Return the rational kernel of this matrix (acting from the left), considered as a matrix over QQ. I.e., returns a matrix K such that self*K = 0, and the number of columns of K equals the nullity of self.
AUTHORS:
The options are exactly like self.right_kernel(...), but returns a matrix A whose rows form a basis for the right kernel, i.e., so that self*transpose(A) = 0.
This is mainly useful internally to avoid all overhead associated with creating a free module.
EXAMPLES:
sage: A = matrix(ZZ, 3, 3, [1..9])
sage: A._right_kernel_matrix()
[-1 2 -1]
Note that the basis matrix returned above is not in Hermite/echelon form.
sage: A.right_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, 2, 4, [2, 1, -18, -1, -1, 1, -1, -5])
sage: K = A._right_kernel_matrix(); K
[-17 -20 -3 0]
[ 7 3 1 -1]
K is a basis for the right kernel:
sage: A*K.transpose()
[0 0]
[0 0]
We illustrate the LLL flag:
sage: L = A._right_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]
Return Singular representation of this integer matrix.
INPUT:
EXAMPLE:
sage: A = random_matrix(ZZ,3,3)
sage: As = singular(A); As
-8 2 0
0 1 -1
2 1 -95
sage: As.type()
'intmat'
Let A equal self be a square matrix. Given B return an integer matrix C and an integer d such that self C*A == d*B if right is False or A*C == d*B if right is True.
OUTPUT:
EXAMPLES:
sage: A = matrix(ZZ,4,4,[0, 1, -2, -1, -1, 1, 0, 2, 2, 2, 2, -1, 0, 2, 2, 1])
sage: B = matrix(ZZ,3,4, [-1, 1, 1, 0, 2, 0, -2, -1, 0, -2, -2, -2])
sage: C,d = A._solve_iml(B,right=False); C
[ 6 -18 -15 27]
[ 0 24 24 -36]
[ 4 -12 -6 -2]
sage: d
12
sage: C*A == d*B
True
sage: A = matrix(ZZ,4,4,[0, 1, -2, -1, -1, 1, 0, 2, 2, 2, 2, -1, 0, 2, 2, 1])
sage: B = matrix(ZZ,4,3, [-1, 1, 1, 0, 2, 0, -2, -1, 0, -2, -2, -2])
sage: C,d = A._solve_iml(B)
sage: C
[ 12 40 28]
[-12 -4 -4]
[ -6 -25 -16]
[ 12 34 16]
sage: d
12
sage: A*C == d*B
True
ALGORITHM: Uses IML.
AUTHORS:
If self is a matrix of full rank, then this function
returns a vector or matrix
such that
.
If
is a vector then
is a vector and if
is a matrix, then
is a matrix. The base
ring of
is the integers unless a denominator is needed
in which case the base ring is the rational numbers.
Note
In Sage one can also write A B for A.solve_right(B), i.e., Sage implements the “the MATLAB/Octave backslash operator”.
Note
This is currently only implemented when A is square.
INPUT:
OUTPUT: a matrix or vector over
EXAMPLES:
sage: a = matrix(ZZ, 2, [0, -1, 1, 0])
sage: v = vector(ZZ, [2, 3])
sage: a \ v
(3, -2)
Note that the output vector or matrix is always over
.
sage: parent(a\v)
Vector space of dimension 2 over Rational Field
We solve a bigger system where the answer is over the rationals.
sage: a = matrix(ZZ, 3, 3, [1,2,3,4, 5, 6, 8, -2, 3])
sage: v = vector(ZZ, [1,2,3])
sage: w = a \ v; w
(2/15, -4/15, 7/15)
sage: parent(w)
Vector space of dimension 3 over Rational Field
sage: a * w
(1, 2, 3)
We solve a system where the right hand matrix has multiple columns.
sage: a = matrix(ZZ, 3, 3, [1,2,3,4, 5, 6, 8, -2, 3])
sage: b = matrix(ZZ, 3, 2, [1,5, 2, -3, 3, 0])
sage: w = a \ b; w
[ 2/15 -19/5]
[-4/15 -27/5]
[ 7/15 98/15]
sage: a * w
[ 1 5]
[ 2 -3]
[ 3 0]
TESTS: We create a random 100x100 matrix and solve the corresponding system, then verify that the result is correct. (Note that this test is very risky without having a seeded random number generator!)
sage: n = 100
sage: a = random_matrix(ZZ,n)
sage: v = vector(ZZ,n,range(n))
sage: x = a \ v
sage: a * x == v
True
Subtract two dense matrices over ZZ.
EXAMPLES:
sage: M = Mat(ZZ,3)
sage: a = M(range(9)); b = M(reversed(range(9)))
sage: a - b
[-8 -6 -4]
[-2 0 2]
[ 4 6 8]
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]
INPUT:
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
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:
EXAMPLES:
sage: t = ModularSymbols(11,sign=1).hecke_matrix(2)
sage: w = t.change_ring(ZZ)
sage: w.list()
[3, -1, 0, -2]
Return the determinant of this matrix.
INPUT:
algorithm
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
. This gives a divisor of the determinant. Then we
compute
using a multimodular algorithm and the
Hadamard bound, skipping primes that divide
.
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
Return the echelon form of this matrix over the integers, also known as the hermit normal form (HNF).
INPUT:
algorithm
max 75 rows or columns: pari with flag 1 larger – use padic 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)
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:
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]
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:
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
Return the Frobenius form (rational canonical form) of this matrix.
INPUT: flag -an integer:
INPUT:
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 0 18]
[ 0 1 12],
[ -1 2 -1]
[ 0 23/15 -14/15]
[ 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:
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.
Return the gcd of all entries of self; very fast.
EXAMPLES:
sage: a = matrix(ZZ,2, [6,15,-6,150])
sage: a.gcd()
3
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
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]
Return the index of self in its saturation.
INPUT:
OUTPUT:
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]
Create a new matrix from self with.
INPUT:
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]
Return True if this lattice is
-LLL reduced. See self.LLL
for a definition of LLL reduction.
INPUT:
EXAMPLE:
sage: A = random_matrix(ZZ, 10, 10)
sage: L = A.LLL()
sage: A.is_LLL_reduced()
False
sage: L.is_LLL_reduced()
True
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.
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
[-17 -20 -3 0]
[ 7 3 1 -1]
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
INPUT:
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
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:
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]
Return the product of the sums of the entries in the submatrix of self with given columns.
INPUT:
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 proportion of the entries of this matrix, leaving the rest unchanged.
The parameters are the same as the integer ring’s random_element function.
If x and y are given, randomized entries of this matrix to be between x and y and have density 1.
INPUT:
OUTPUT:
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]
Return the rank of this matrix.
OUTPUT:
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
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:
OUTPUT:
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
Return the right kernel of this matrix, as a module over the integers. This is the saturated ZZ-module spanned by all the column vectors v such that self*v = 0.
INPUT:
By convention if self has 0 columns, the right kernel is of dimension 0, whereas the right kernel is the whole domain if self has 0 rows.
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]
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 module
embedded in
is the a module
that
contains
with finite index such that
is torsion free. This function takes the
row span
of self, and finds another matrix of full rank
with row span the saturation of
.
INPUT:
OUTPUT:
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
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)
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
See also
Return the matrix self on top of other: [ self ] [ other ]
EXAMPLES:
sage: M = Matrix(ZZ, 2, 3, range(6))
sage: N = Matrix(ZZ, 1, 3, [10,11,12])
sage: M.stack(N)
[ 0 1 2]
[ 3 4 5]
[10 11 12]
Find a symplectic basis for self if self is an anti-symmetric, alternating matrix.
Returns a pair (F, C) such that the rows of C form a symplectic basis for self and F = C * self * C.transpose().
Raises a ValueError if self is not anti-symmetric, or self is not alternating.
Anti-symmetric means that . Alternating means
that the diagonal of
is identically zero.
A symplectic basis is a basis of the form
such that
= 0 for all vectors
for all
for all
for all
.
The ordering for the factors and for
the placement of zeroes was chosen to agree with the output of
smith_form.
See the example for a pictorial description of such a basis.
EXAMPLES:
sage: E = matrix(ZZ, 5, 5, [0, 14, 0, -8, -2, -14, 0, -3, -11, 4, 0, 3, 0, 0, 0, 8, 11, 0, 0, 8, 2, -4, 0, -8, 0]); E
[ 0 14 0 -8 -2]
[-14 0 -3 -11 4]
[ 0 3 0 0 0]
[ 8 11 0 0 8]
[ 2 -4 0 -8 0]
sage: F, C = E.symplectic_form()
sage: F
[ 0 0 1 0 0]
[ 0 0 0 2 0]
[-1 0 0 0 0]
[ 0 -2 0 0 0]
[ 0 0 0 0 0]
sage: F == C * E * C.transpose()
True
sage: E.smith_form()[0]
[1 0 0 0 0]
[0 1 0 0 0]
[0 0 2 0 0]
[0 0 0 2 0]
[0 0 0 0 0]
Returns the transpose of self, without changing self.
EXAMPLES:
We create a matrix, compute its transpose, and note that the original matrix is not changed.
sage: A = matrix(ZZ,2,3,xrange(6))
sage: type(A)
<type 'sage.matrix.matrix_integer_dense.Matrix_integer_dense'>
sage: B = A.transpose()
sage: print B
[0 3]
[1 4]
[2 5]
sage: print A
[0 1 2]
[3 4 5]
sage: A.subdivide(None, 1); A
[0|1 2]
[3|4 5]
sage: A.transpose()
[0 3]
[---]
[1 4]
[2 5]
TESTS:
sage: from sage.matrix.matrix_integer_dense import _lift_crt
sage: T1 = Matrix(Zmod(5), 4, 4, [1, 4, 4, 0, 2, 0, 1, 4, 2, 0, 4, 1, 1, 4, 0, 3])
sage: T2 = Matrix(Zmod(7), 4, 4, [1, 4, 6, 0, 2, 0, 1, 2, 4, 0, 6, 6, 1, 6, 0, 5])
sage: T3 = Matrix(Zmod(11), 4, 4, [1, 4, 10, 0, 2, 0, 1, 9, 8, 0, 10, 6, 1, 10, 0, 9])
sage: _lift_crt(Matrix(ZZ, 4, 4), [T1, T2, T3])
[ 1 4 -1 0]
[ 2 0 1 9]
[-3 0 -1 6]
[ 1 -1 0 -2]
sage: from sage.ext.multi_modular import MultiModularBasis
sage: mm = MultiModularBasis([5,7,11])
sage: _lift_crt(Matrix(ZZ, 4, 4), [T1, T2, T3], mm)
[ 1 4 -1 0]
[ 2 0 1 9]
[-3 0 -1 6]
[ 1 -1 0 -2]
Compare various multiplication algorithms.
INPUT:
OUTPUT:
EXAMPLES:
sage: from sage.matrix.matrix_integer_dense import tune_multiplication
sage: tune_multiplication(2, nmin=10, nmax=60, bitmin=2,bitmax=8)
10 2 0.2
...