|
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.
The (row) echelon form of matrix a belonging to a submodule of the
module Mn(S). This function returns two values:
- (a)
- The (row) echelon form e of a; and
- (b)
- A matrix b such that b * a = e, i.e. b is a product of
elementary matrices that transforms a into echelon form.
The elementary divisors of the matrix a belonging to a submodule of the
module Mn(S). The divisors are returned as a sequence
[e1, ..., ed], ei | ei + 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.
Al: MonStg Default: "LLL"
Optimize: BoolElt Default: true
Integral: BoolElt Default: true
The row Hermite normal form of a matrix X belonging to the matrix
algebra Mn(R).
The coefficient ring R must be an Euclidean domain.
This function returns two values:
- (a)
- The Hermite normal form H of X; and
- (b)
- 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.
The Smith normal form for the matrix a belonging to a submodule
of the module Mn(S), where S is a Euclidean Domain. This function
returns three values:
- (a)
- The Smith normal form s of a; and
- (b)
- Unimodular matrices b and c such that b * a * c = s, i.e.
b and c are matrices that transform a into Smith normal form.
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]
The functions in this group apply to elements of matrix algebras whose
coefficient rings are fields
which allow factorization of univariate polynomials over them.
The primary rational canonical form of a matrix a belonging
to Mn(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:
- (a)
- The primary rational canonical form p of a;
- (b)
- A non-singular matrix t such that t * a * t - 1 = p;
- (c)
- A sequence of pairs corresponding to the blocks of p where each
pair consists of the irreducible polynomial and multiplicity
making up the block.
The (generalized) Jordan canonical form for the matrix a belonging to the
algebra Mn(K),
where the coefficient ring K must be a field allowing factorization
of univariate polynomials over it.
This function returns three values:
- (a)
- The (generalized) Jordan canonical form j of a;
- (b)
- A non-singular matrix t such that t * a * t - 1= j;
- (c)
- A sequence of pairs corresponding to the blocks of j where each
pair consists of the irreducible polynomial and multiplicity
making up the block.
The rational canonical form of a matrix a belonging
to Mn(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:
- (a)
- The rational canonical form f of a;
- (b)
- A non-singular matrix t such that t * a * t - 1 = f;
- (c)
- A sequence containing the polynomials corresponding to each block
(each non-last one dividing the next).
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.
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.
Returns true iff the matrix a is similar to the matrix 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.
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
]
> Rank(a);
2
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]
> ElementaryDivisors(ax);
[
1,
1,
x + 4,
x^2 + 4,
x^2 + 4
]
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|