[Next] [Prev] [Right] [Left] [Up] [Index] [Root]
Canonical Forms

Canonical Forms

Subsections

Canonical Forms for Matrices over Euclidean Domains

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

EchelonForm(a) : AlgMatElt -> AlgMatElt, AlgMatElt
The (row) echelon form of matrix a belonging to a submodule of the module M_n(S). This function returns two values:
ElementaryDivisors(a) : AlgMatElt -> [RngElt]
The elementary divisors of the matrix a belonging to a submodule of the module M_n(S). 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 a. If R is a field, the result is always the empty sequence over R.

HermiteForm(X) : AlgMatElt -> AlgMatElt, AlgMatElt
    Al: MonStg                          Default: "LLL"
    Optimize: BoolElt                   Default: true
    Integral: BoolElt                   Default: true
The row Hermite normal form of an matrix X belonging to the matrix algebra M_n(R). The coefficient ring R must be an Euclidean domain. This function returns two values: 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.

SmithForm(a) : AlgMatElt -> AlgMatElt, AlgMatElt, AlgMatElt
The Smith normal form for the matrix a belonging to a submodule of the module M_n(S), where S is a Euclidean Domain. This function returns three values:

Example AlgMat_EchelonForm (H51E6)

We illustrate some of these operations in the context of the algebra M_4(K), where K is the field GF(8).

> K<w> := FiniteField(8);
> M := MatrixAlgebra(K, 4);
> A := M ! [1, w, w^5, 0,  w^3, w^4, w, 1,  w^6, w^3, 1, w^4, 1, w, 1, w ];
> A;
[  1   w w^5   0]
[w^3 w^4   w   1]
[w^6 w^3   1 w^4]
[  1   w   1   w]
> EchelonForm(A);
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]

Canonical Forms for Matrices over a Field

The functions in this group apply to elements of matrix algebras whose coefficient rings are fields which allow factorization of univariate polynomials over them.

PrimaryRationalForm(a) : AlgMatElt -> AlgMatElt, AlgMatElt, [ <RngUPolElt, RngIntElt ]
The primary rational canonical form of a matrix a belonging to M_n(K), where the coefficient ring K must be a field allowing factorization of univariate polynomials over it. Each block corresponds to a power of an irreducible polynomial. This function returns three values:
JordanForm(a) : AlgMatElt -> AlgMatElt, AlgMatElt, [ <RngUPolElt, RngIntElt ]
The (generalized) Jordan canonical form for the matrix a belonging to the algebra M_n(K), where the coefficient ring K must be a field allowing factorization of univariate polynomials over it. This function returns three values:
RationalForm(a) : AlgMatElt -> AlgMatElt, AlgMatElt, [ RngUPolElt ]
The rational canonical form of a matrix a belonging to M_n(K), where the coefficient ring K must be a field allowing factorization of univariate polynomials over it. For each block before the last block, the polynomial corresponding to that block divides the polynomial corresponding to the next block. This function returns three values:
PrimaryInvariantFactors(a) : AlgMatElt -> [ <RngUPolElt, RngIntElt ]
The primary invariant factors of the matrix a. This is the same as the third return value of PrimaryRationalForm(a) or JordanForm(a). The coefficient ring must be a field allowing factorization of univariate polynomials over it.
InvariantFactors(a) : AlgMatElt -> [ AlgPolElt ]
The invariant factors of the matrix a. This is the same as the third return value of RationalForm(a). The coefficient ring must be a field allowing factorization of univariate polynomials over it.
IsSimilar(a, b) : AlgMatElt, AlgMatElt -> BoolElt, AlgMatElt
True iff a is similar to b. If a is similar to b, a transformation matrix t is also returned with t * a * t^(-1)=b. The coefficient ring must be a field allowing factorization of univariate polynomials over it.

Example AlgMat_ElementaryDivisors (H51E7)

We consider the algebra M_5(P), where P is the polynomial ring in indeterminate x over the field GF(5). We take the matrix having x^i + x^j in its (i, j)-th position.

> K := GaloisField(5);
> P<x> := PolynomialAlgebra(K);
> M := MatrixAlgebra(P, 5);
> a := M ! [x^i + x^j: i, j in [1..5]];
> a;
[      2*x   x^2 + x   x^3 + x   x^4 + x   x^5 + x]
[  x^2 + x     2*x^2 x^3 + x^2 x^4 + x^2 x^5 + x^2]
[  x^3 + x x^3 + x^2     2*x^3 x^4 + x^3 x^5 + x^3]
[  x^4 + x x^4 + x^2 x^4 + x^3     2*x^4 x^5 + x^4]
[  x^5 + x x^5 + x^2 x^5 + x^3 x^5 + x^4     2*x^5]
> ElementaryDivisors(a);
[
    x,
    x^3 + 3*x^2 + x
]

Example AlgMat_CanonicalForms (H51E8)

We construct a 5 by 5 matrix over the finite field with 5 elements and then calculate various canonical forms. We verify the correctness of the polynomial invariant factors corresponding to the rational form by calculating the Smith form of the characteristic matrix of the original matrix.

> K := GF(5);
> P<x> := PolynomialRing(K);    
> A := MatrixAlgebra(K, 5);
> a := 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
> ];
> 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>
]
> 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]
> f;
[
    x + 4,
    x^2 + 4,
    x^2 + 4
]
> PA := MatrixAlgebra(P, 5);
> ax := PA ! x - PA ! 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]

[Next] [Prev] [Right] [Left] [Up] [Index] [Root]