The functions defined here apply to matrices defined over fields or Euclidean domains. See also the section on Reduction in the Lattices chapter for a description of the function LLL and related basis-reduction functions for matrices.
Given an m x n matrix A over the ring R, return the (reduced) row echelon form E of A, and also an invertible m x m transformation matrix T over R such that T.A = E. Recall that T is a product of elementary matrices that transforms A into the echelon form E. If R is a Euclidean domain, the function HermiteForm (described below) is invoked. Note however, that the the user cannot set the parameters for HermiteForm when invoking it via EchelonForm.
Given a square m x m matrix A over the ring R, return the adjoint of A as an m x m matrix. The base ring R must be a ring with exact division whose characteristic is zero or greater than m (this includes most commutative rings).
The functions described in this section apply to square matrices defined over fields which support factorization of univariate polynomials. See [Ste97] for a description of the single algorithm which is the basis of most of these functions.
Given a square matrix A over a field K such that factorization of polynomials is possible over K, return the primary rational form of A. Each block in the form is the companion matrix of a power of an irreducible polynomial. This function returns three values:
- (a)
- The primary rational canonical form F of A;
- (b)
- An invertible matrix T such that T.A.T - 1 = F;
- (c)
- A sequence of pairs corresponding to the blocks of F where each pair consists of the irreducible polynomial and the multiplicity making up the block. This is the value returned by PrimaryInvariantFactors(A).
Given a square matrix A over a field K such that factorization of polynomials is possible over K, return the generalized Jordan form of A. Each block in the form is a Jordan block (which itself is derived from a power of an irreducible polynomial), and the generalized Jordan form corresponds to the usual Jordan form if the minimal polynomial splits over K. This function returns three values:
- (a)
- The Jordan canonical form F of A;
- (b)
- An invertible matrix T such that T.A.T - 1 = F;
- (c)
- A sequence of pairs corresponding to the blocks of F where each pair consists of the irreducible polynomial and the multiplicity making up the block. This is the value returned by PrimaryInvariantFactors(A).
Given a square matrix A over a field K such that factorization of polynomials is possible over K, return the rational form of A. For each block other than the final block, the polynomial corresponding to that block divides the polynomial corresponding to the next block. This function returns three values:
- (a)
- The rational form F of A;
- (b)
- An invertible matrix T such that T.A.T - 1 = F;
- (c)
- A sequence containing the polynomials corresponding to the successive blocks (where each polynomial, other than the last, divides the next polynomial). This is the value returned by InvariantFactors(A).
Given a square matrix A over a field K such that factorization of polynomials is possible over K, return the primary invariant factors of A. This is the same as the third return value of PrimaryRationalForm(A) or JordanForm(A).
Given a square matrix A over a field K such that factorization of polynomials is possible over K, return the invariant factors of A. This is the same as the third return value of RationalForm(A).
Given square m x m matrices A and B, both over a field K such that factorization of polynomials is possible over K, return true iff and only if A is similar to B, and if so, return also an invertible m x m transformation matrix T such that T.A.T - 1 = B.
Given a square m x m matrix A over the ring R, return the Hessenberg form of A as an m x m matrix. The form has zero entries above the super-diagonal. (This form is used in one of the characteristic polynomial algorithms.) The base ring R must be a field.
Given a non-singular 2n x 2n alternating matrix A over the integers, this function returns the (alternating) Frobenius form F of A. That is, a block matrix F = (matrix(0 & D
- D & 0)), where D is a diagonal matrix with positive diagonal entries, di, satisfying d1 | d2 | ... | dn. The second return value is the change of basis matrix B, such that BA ()tB = F.
> K := GF(5);
> A := Matrix(K, 5,
> [ 0, 2, 4, 2, 0,
> 2, 2, 2, 3, 3,
> 3, 4, 4, 1, 3,
> 0, 0, 0, 0, 1,
> 0, 0, 0, 1, 0 ]);
> A;
[0 2 4 2 0]
[2 2 2 3 3]
[3 4 4 1 3]
[0 0 0 0 1]
[0 0 0 1 0]
> PrimaryInvariantFactors(A);
[
<x + 1, 1>,
<x + 1, 1>,
<x + 4, 1>,
<x + 4, 1>,
<x + 4, 1>
]
> JordanForm(A);
[4 0 0 0 0]
[0 4 0 0 0]
[0 0 1 0 0]
[0 0 0 1 0]
[0 0 0 0 1]
> R, T, F := RationalForm(A);
> R;
[1 0 0 0 0]
[0 0 1 0 0]
[0 1 0 0 0]
[0 0 0 0 1]
[0 0 0 1 0]
> T;
[1 3 0 2 1]
[2 1 2 2 0]
[3 4 3 4 1]
[1 0 0 0 0]
[0 2 4 2 0]
> T*A*T^-1 eq R;
true;
> F;
[
x + 4,
x^2 + 4,
x^2 + 4
]
> P<x> := PolynomialRing(K);
> PM := MatrixAlgebra(P, 5);
> Ax := PM ! x - PM ! A;
> Ax;
[ x 3 1 3 0]
[ 3 x + 3 3 2 2]
[ 2 1 x + 1 4 2]
[ 0 0 0 x 4]
[ 0 0 0 4 x]
> SmithForm(Ax);
[ 1 0 0 0 0]
[ 0 1 0 0 0]
[ 0 0 x + 4 0 0]
[ 0 0 0 x^2 + 4 0]
[ 0 0 0 0 x^2 + 4]
> ElementaryDivisors(Ax);
[
1,
1,
x + 4,
x^2 + 4,
x^2 + 4
]
The functions defined here apply to matrices defined over Euclidean domains. See also the section on Reduction in the Lattices chapter for a description of the function LLL and related functions, which are very useful for integer matrices.
Al: MonStg Default: "Default"
Optimize: BoolElt Default: true
Integral: BoolElt Default: true
Given an m x n matrix A over the Euclidean ring R, return the Hermite form H of A, and also an invertible m x m transformation matrix T over R such that T.A = H.The basic algorithm used is the classical Kannan-Bachem algorithm [KB79], [CC82], which has classical complexity (but does not suffer from bad coefficient growth).
Since V2.13, for matrices over the integers there is also a fast modular algorithm by Allan Steel. By default, Magma chooses between these two algorithms, usually favouring the new modular algorithm. But one may set the parameter Al to "Modular" to force the modular algorithm to be used, and to "Classical" to force the classical algorithm to be used.
If R is the ring of integers Z and the matrix T is requested (i.e., if an assignment statement is used with two variables on the left side), then the LLL algorithm will also be used by default to improve T (using the kernel of A) so that the size of its entries are very small. If the parameter Optimize is set to false, then this will not happen (which will be faster but the entries of T will not be as small). If the parameter Integral is set to true, then the integral (de Weger) LLL method will be used in the LLL step, instead of the default floating point method.
Given an m x n matrix A over the Euclidean ring R, return the Smith normal form of A. This function returns three values:The algorithm implemented first uses the sparse techniques described in [HHR93] to reduce the matrix to a dense submatrix, then, if this is non-trivial, it either repeatedly calls the Hermite normal form algorithm (see above) and transposes until a diagonal form is obtained, or uses the modular algorithm of F. Lübeck [Lüb02].
- (a)
- The Smith normal form S of A; and
- (b)
- Unimodular matrices P and Q such that P.A.Q = S, i.e., P and Q are matrices which transform A into Smith normal form.
Unless one wishes one or both of the transformation matrices, it is preferable to use the following function ElementaryDivisors since it gives the same information, but saves memory since the matrix S does not need to be constructed.
Given an m x n matrix A over the Euclidean ring or field R, return the elementary divisors of A. These are simply the non-zero diagonal entries of the Smith form of A, in order. The divisors are returned as a sequence [e1, ..., er] of r elements of R (which may include ones), where r is the rank of A and ei | ei + 1 for i=1, ..., r - 1. The divisors are normalized, so the result is unique. If R is a field, the result is always the sequence of r ones, where r is the rank of A.Note that if m=n=r, then the determinant of A is the product of the ei and if R is also a domain, then er is the lowest common denominator of the inverse of A over the field of fractions of R.
Given an m x n matrix A over the integer ring Z, having rank r, return an m x n matrix S over Z whose first r rows form a basis of the saturation w.r.t. Q of the Q-vector space spanned by the rows of A. The rows of S thus span the same space over Q as those of A, while the Z-module spanned by the rows of S is the set of all v such that for some non-zero scalar s, s.v is in the Z-module spanned by the rows of A.
> K<w> := GF(8); > A := Matrix(K, 4, 3, [1,w,w^5, 0,w^3,w^4, w,1,w^6, w^3,1,w^4]); > A; [ 1 w w^5] [ 0 w^3 w^4] [ w 1 w^6] [w^3 1 w^4] > EchelonForm(A); [ 1 0 0] [ 0 1 0] [ 0 0 1] [ 0 0 0]We now illustrate some of these operations for a 4 x 5 matrix over Z.
> A := Matrix(4, 5, > [ 2,-4,12,7,0, > 3,-3,5,-1,4, > 2,-1,-4,-5,-12, > 0,3,6,-2,0]); > A; [ 2 -4 12 7 0] [ 3 -3 5 -1 4] [ 2 -1 -4 -5 -12] [ 0 3 6 -2 0] > Rank(A); 4 > HermiteForm(A); [ 1 1 1 6 -164] [ 0 3 0 16 -348] [ 0 0 2 13 -200] [ 0 0 0 19 -316] > SmithForm(A); [1 0 0 0 0] [0 1 0 0 0] [0 0 1 0 0] [0 0 0 2 0] > ElementaryDivisors(A); [ 1, 1, 1, 2 ]