Given a field K and an n× n-matrix A over K, the Frobenius normal form of A is a block diagonal matrix, where the diagonal blocks are companion matrices corresponding to the invariant factors of A. It reflects the minimal decomposition of the vector space K^n into cyclic subspaces under the action of A. The Frobenius normal form is also called the rational canonical form.
‣ FrobeniusNormalForm( A ) | ( function ) |
Returns the invariant factors of a matrix A and an invertible matrix P such that PAP^-1 is the Frobenius normal form of A. The algorithm first computes a maximal vector and an A-invariant complement following Jacob's construction (as described in matrix language in [Gec20]); then the algorithm continues recursively. It works for matrices over any field that is available in GAP. The output is a triple with
1st component = list of invariant factors;
2nd component = base change matrix P; and
3rd component = indices where the various blocks in the normal form begin.
gap> A:=[ [ 2, 2, 0, 1, 0, 2, 1 ], > [ 0, 4, 0, 0, 0, 1, 0 ], > [ 0, 1, 1, 0, 0, 1, 1 ], > [ 0, -1, 0, 1, 0, -1, 0 ], > [ 0, -7, 0, 0, 1, -5, 0 ], > [ 0, -2, 0, 0, 0, 1, 0 ], > [ 0, -1, 0, 0, 0, -1, 1 ] ];; gap> f:=FrobeniusNormalForm(A); [ [ x_1^4-7*x_1^3+17*x_1^2-17*x_1+6, x_1^2-3*x_1+2, x_1-1 ], [ [ 1, -2, 1, 1, 0, 0, 1 ], [ 2, -7, 1, 2, 0, -1, 3 ], [ 4, -26, 1, 4, 0, -8, 6 ], [ 8, -89, 1, 8, 0, -35, 11 ], [ -1/2, -2, 0, 1/2, 0, -2, -3/2 ], [ -1, -4, 0, 0, 0, -4, -2 ], [ 0, 9/4, 0, -3, 1, 5/4, 1/4 ] ], [ 1, 5, 7 ] ] gap> PrintArray(f[2]*A*f[2]^-1); [ [ 0, 1, 0, 0, 0, 0, 0 ], [ 0, 0, 1, 0, 0, 0, 0 ], [ 0, 0, 0, 1, 0, 0, 0 ], [ -6, 17, -17, 7, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 1, 0 ], [ 0, 0, 0, 0, -2, 3, 0 ], [ 0, 0, 0, 0, 0, 0, 1 ] ]
Note that the Frobenius normal form is unique up to the choice of the companion matrices and the permutation of the blocks corresponding to the invariant factors. So while this function is significantly more efficient than the existing 'RationalCanonicalFormTransform', the two functions yield slightly different results. In 'RationalCanonicalFormTransform', the companion matrices are consistent with the output of 'CompanionMat'. However, given an n× n cyclic matrix A, along with a corresponding cyclic vector v, one can compute a change of basis matrix from A to a companion matrix of its minimal polynomial by computing v multiplied with powers of A (i.e., v, vA, ...., vA^n-1). This approach follows GAP’s convention of right multiplication and yields a companion matrix in the form used by FrobeniusNormalForm. Furthermore 'RationalCanonicalFormTransform' sorts the invariant factors in ascending order, while FrobeniusNormalForm sorts them in descending order.
gap> A := [ [ 0*Z(5), Z(5)^3, 0*Z(5), Z(5)^0, Z(5)^3 ], > [ Z(5)^0, 0*Z(5), Z(5)^2, Z(5)^2, Z(5)^2 ], > [ Z(5), Z(5), 0*Z(5), Z(5)^0, Z(5)^3 ], > [ 0*Z(5), Z(5), Z(5)^2, Z(5)^2, Z(5) ], > [ Z(5)^3, Z(5)^3, Z(5)^0, Z(5)^3, Z(5)^0 ] ];; gap> T:=RationalCanonicalFormTransform(A);; gap> S:=TransposedMat(FrobeniusNormalForm(TransposedMat(A))[2]);; gap> Display(A^T); . . . . 3 1 . . . 2 . 1 . . 3 . . 1 . 4 . . . 1 . gap> Display(A^S); . . . . 3 1 . . . 2 . 1 . . 3 . . 1 . 4 . . . 1 .
Additionally, RationalCanonicalFormTransform sorts the invariant factors in ascending order, whereas the FrobeniusNormalForm sorts them in descending order. Consequently, the outputs of the two functions agree up to a permutation of blocks and transposition. To get a drop in replacement for 'RationalCanonicalFormTransform', see FrobeniusNormalFormLikeRCFT (2.1-2).
gap> aa:=[[ 0, -8, 12, 40,-36, 4, 0, 59, 15, -9], > [ -2, -2, -2, 6,-11, 1, -1, 10, 1, 0], > [ 1, 5, 0, -6, 12, -2, 0,-12, -4, 2], > [ 0, 0, 0, 2, 0, 0, 0, 7, 0, 0], > [ 0, 2, -3, -7, 8, -1, 0, -7, -3, 2], > [ -5, -4, -6, 18,-30, 2, -2, 35, 5, -1], > [ -1, -6, 6, 20,-28, 3, 0, 24, 10, -6], > [ 0, 0, 0, -1, 0, 0, 0, -3, 0, 0], > [ 0, 0, -1, -2, -2, 0, -1, -7, 0, 0], > [ 0, -8, 9, 21,-36, 4, -2, 12, 12, -8]];; gap> t:=RationalCanonicalFormTransform(aa);; gap> Display(aa^t); [ [ 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 ], [ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ], [ 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 ], [ 0, 0, 0, 0, 0, 1, 0, 0, 0, 1 ], [ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 1, 0, -1 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 1, -1 ] ] gap> res:=FrobeniusNormalForm(aa);; gap> Display(aa^(res[2]^-1)); [ [ 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 ], [ 1, 1, 1, 0, -1, -1, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 1, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ], [ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 ] ]
‣ FrobeniusNormalFormLikeRCFT( A ) | ( function ) |
This function returns the same result as FrobeniusNormalForm (2.1-1), except that the invariant factors are sorted in descending order and the companion matrices on the diagonal are transposed. Furthermore, if P is the computed base change matrix, the Frobenius normal form is obtained by P^-1AP (instead of PAP^-1). This means that P can be used as a direct drop-in replacement for RationalCanonicalFormTransform.
Note that this function works by calling FrobeniusNormalForm (2.1-1) and then modifying the computed transformation matrix and is thus potentially less efficient than using the original function.
gap> A := [ [ 0*Z(5), Z(5)^2, Z(5)^2, 0*Z(5), Z(5)^3, Z(5)^3, 0*Z(5), Z(5)^3, > 0*Z(5), Z(5) ], > [ Z(5)^0, Z(5)^0, Z(5)^0, Z(5), Z(5)^3, Z(5), Z(5)^3, 0*Z(5), Z(5), > 0*Z(5) ], > [ Z(5), 0*Z(5), 0*Z(5), Z(5)^3, Z(5)^2, Z(5)^0, 0*Z(5), Z(5)^0, > Z(5), Z(5)^2 ], > [ 0*Z(5), 0*Z(5), 0*Z(5), Z(5)^2, 0*Z(5), 0*Z(5), 0*Z(5), Z(5)^2, > 0*Z(5), 0*Z(5) ], > [ 0*Z(5), Z(5)^2, Z(5)^2, Z(5)^0, Z(5)^0, Z(5)^3, 0*Z(5), Z(5)^0, > Z(5)^2, Z(5)^2 ], > [ 0*Z(5), Z(5), Z(5)^3, Z(5)^0, 0*Z(5), Z(5)^2, Z(5)^0, 0*Z(5), > 0*Z(5), Z(5)^3 ], > [ Z(5)^3, Z(5)^3, Z(5), 0*Z(5), Z(5)^2, Z(5)^0, 0*Z(5), Z(5)^3, > 0*Z(5), Z(5)^3 ], > [ 0*Z(5), 0*Z(5), 0*Z(5), Z(5)^3, 0*Z(5), 0*Z(5), 0*Z(5), Z(5)^2, > 0*Z(5), 0*Z(5) ], > [ 0*Z(5), 0*Z(5), Z(5)^3, Z(5)^0, Z(5)^0, 0*Z(5), Z(5)^3, Z(5)^0, > 0*Z(5), 0*Z(5) ], > [ 0*Z(5), Z(5)^2, Z(5)^3, Z(5), Z(5)^3, Z(5)^3, Z(5)^0, Z(5)^2, > Z(5)^2, Z(5)^2 ] ];; gap> frob := FrobeniusNormalFormLikeRCFT(A)[2];; gap> rat := RationalCanonicalFormTransform(A);; gap> Display(A^rat); . . . 1 . . . . . . 1 . . . . . . . . . . 1 . . . . . . . . . . 1 . . . . . . . . . . . . . . . . 4 . . . . 1 . . . . 2 . . . . . 1 . . . 1 . . . . . . 1 . . . . . . . . . . 1 . 1 . . . . . . . . 1 3 gap> Display(A^frob); . . . 1 . . . . . . 1 . . . . . . . . . . 1 . . . . . . . . . . 1 . . . . . . . . . . . . . . . . 4 . . . . 1 . . . . 2 . . . . . 1 . . . 1 . . . . . . 1 . . . . . . . . . . 1 . 1 . . . . . . . . 1 3
‣ InvariantFactorsMat( A ) | ( function ) |
Returns the invariant factors of the matrix A, i.e., the minimal polynomials of the diagonal blocks in the Frobenius normal form of A. Thus, 'InvariantFactorsMat' also specifies the rational canonical form of A, but without computing the base change.
gap> A := [ [ 2, 2, 0, 1, 0, 2, 1 ], > [ 0, 4, 0, 0, 0, 1, 0 ], > [ 0, 1, 1, 0, 0, 1, 1 ], > [ 0, -1, 0, 1, 0, -1, 0 ], > [ 0, -7, 0, 0, 1, -5, 0 ], > [ 0, -2, 0, 0, 0, 1, 0 ], > [ 0, -1, 0, 0, 0, -1, 1 ] ];; gap> InvariantFactorsMat(A); [ x_1^4-7*x_1^3+17*x_1^2-17*x_1+6, x_1^2-3*x_1+2, x_1-1 ]
The Jordan normal form of a matrix A is a block diagonal matrix, where the diagonal blocks are Jordan blocks corresponding to the elementary divisors of A. It reflects the maximal decomposition of the vector space K^n into cyclic subspaces under the action of A. For a more thorough definition of the Jordan normal form and details about the algorithms used, see [Bon26].
‣ JordanNormalForm( A ) | ( function ) |
Returns a list containing two entries. The first is a base change matrix B such that BAB^-1 is the Jordan normal form of A, i.e. a block diagonal matrix where the diagonal blocks are Jordan blocks corresponding to the elementary divisors of A in descending order. The second entry is a list of the elementary divisors of A, also in descending order. The algorithm first computes a primary decomposition of A and then computes a cyclic decomposition of the primary components. Finally it computes Jordan block form for each of the cyclic components. The blocks are ordered in the same order as in the list containing the elementary divisors. It works for matrices over finite fields.
Since all of the blocks on the resulting transformed matrix are cyclic, one can retrieve their size by the degrees of the respective elementary divisor.
gap> A := [ [ 0*Z(5), 0*Z(5), Z(5)^3, Z(5)^3, Z(5)^3, Z(5)^0 ], > [ 0*Z(5), Z(5)^2, Z(5)^2, Z(5)^0, Z(5)^3, Z(5)^3 ], > [ Z(5)^0, Z(5)^0, Z(5)^3, Z(5)^2, Z(5)^0, Z(5) ], > [ 0*Z(5), Z(5)^3, Z(5), Z(5), 0*Z(5), Z(5)^2 ], > [ Z(5)^2, Z(5)^0, Z(5)^0, 0*Z(5), Z(5), Z(5) ], > [ 0*Z(5), Z(5)^0, Z(5)^2, Z(5), Z(5), Z(5) ] ];; gap> B := JordanNormalForm(A);; gap> Display(A^Inverse(B[1])); 3 . . . . . . 1 . . . . . . . 1 . . . . 2 . . . . . . . . 1 . . . . 3 4
This function computes the Jordan normal form of A significantly faster if A is either cyclic or has irreducible minimal polynomial.
gap> B:= [ [ Z(5), Z(5)^3, 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5) ], > [ Z(5)^0, Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5) ], > [ 0*Z(5), 0*Z(5), Z(5), Z(5)^3, 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5) ], > [ 0*Z(5), 0*Z(5), Z(5)^0, Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5) ], > [ 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), Z(5), Z(5)^3, 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5) ], > [ 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), Z(5)^0, Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5) ], > [ 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), Z(5), Z(5)^3, 0*Z(5), 0*Z(5) ], > [ 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), Z(5)^0, Z(5), 0*Z(5), 0*Z(5) ], > [ 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), Z(5), Z(5)^3 ], > [ 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), Z(5)^0, Z(5) ] ];; gap> Factors(MinimalPolynomial(B)); [ x_1^2+x_1+Z(5)^0 ] gap> Display(B^Inverse(JordanNormalForm(B)[1])); . 1 . . . . . . . . 4 4 . . . . . . . . . . . 1 . . . . . . . . 4 4 . . . . . . . . . . . 1 . . . . . . . . 4 4 . . . . . . . . . . . 1 . . . . . . . . 4 4 . . . . . . . . . . . 1 . . . . . . . . 4 4
generated by GAPDoc2HTML