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 functions.

EchelonForm(X) : ModMatRngElt -> ModMatRngElt, ModMatRngElt

The (row) echelon form of matrix X belonging to a submodule of the module Hom_R(M, N). This function returns two values:

• The (row) echelon form E of X; and
• A matrix T such that T * X = E, i.e., T is a product of elementary matrices that transforms X into echelon form.

The elementary divisors of the matrix X belonging to a submodule of the module Hom_R(M, N). 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, where d is the rank of X. If R is a field, the result is always the empty sequence over R.

    Al: MonStg                          Default: "LLL"

    Optimize: BoolElt                   Default: true

    Integral: BoolElt                   Default: true

The row Hermite normal form of an matrix X belonging to a submodule of the module Hom_R(M, N). The coefficient ring R must be an Euclidean domain. This function returns two values:

• The Hermite normal form H of X; and
• A unimodular matrix T such that T.X = H, i.e., T is the product of elementary matrices which transforms X into Hermite normal form.

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 X) 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 X is very large (say 200 or more).

If R is the ring of integers Z and the parameter Al is set to the string "Sort", then the sorting-gcd algorithm will be used. However, the new algorithm will practically always perform better than the sorting-gcd algorithm.

Given a matrix X belonging to the matrix ring R over the Euclidean domain S, return the rank of X.

The Smith normal form for the matrix X belonging to a submodule of the module Hom_R(M, N). This function returns three values:

• The Smith normal form S of X; and
• Unimodular matrices P and Q such that P * X * Q = S, i.e., P and Q are matrices which transform X into Smith normal form.

> K<w> := GaloisField(8);
> V3 := VectorSpace(K, 3);
> V4 := VectorSpace(K, 4);
> M := Hom(V4, V3);
> A := M ! [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]

> Z  := Integers();
> Z4 := RSpace(Z, 4);
> Z5 := RSpace(Z, 5);
> M  := Hom(Z4, Z5);
> x  := M ! [ 2, -4, 12, 7, 0,   
>             3, -3,  5, -1,  4,
>             2, -1, -4, -5,-12,    
>             0,  3,  6, -2,  0 ];
> x;
[  2  -4  12   7   0]
[  3  -3   5  -1   4]
[  2  -1  -4  -5 -12]
[  0   3   6  -2   0]
> Rank(x);
4
> HermiteForm(x);
[   1    1    1    6 -164]
[   0    3    0   16 -348]
[   0    0    2   13 -200]
[   0    0    0   19 -316]
> SmithForm(x);
[1 0 0 0 0]
[0 1 0 0 0]
[0 0 1 0 0]
[0 0 0 2 0]
> ElementaryDivisors(x);
[ 2 ]