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.
> 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: "LLL"
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. Recall that T is a product of elementary matrices that transforms A into its echelon form H.The algorithm implemented is an optimized version of the Kannan-Bachem algorithm [KB79], [CC82], which has classical complexity but does not suffer from bad coefficient growth. More advanced modular algorithms will be available in the near future.
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 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. The integral method will often be faster if the rank of the kernel of A is very large (say 200 or more).
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 repeatedly calls the Hermite normal form algorithm (see above) and transposes until a diagonal form is obtained. More advanced modular algorithms will be available in the near future.
- (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.
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 [e_1, ..., e_d], e_i | e_(i + 1) (i=1, ..., d - 1) of d elements of R (which may include ones), where d is the rank of A. If R is a field, the result is always the sequence of r ones, where r is the rank 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); [ 2 ]