‣ GcdCoprimeSplit( a, b ) | ( function ) |
Computes a divisor a_1 of the polynomial a and a divisor b_1 of the polynomial b such that a_1 and b_1 are coprime and the lcm of a, b is a_1*b_1. This is based on Lemma 5 in [Bon14]. (See also Lemma 4.3 in [Gec20]).
(Note that it does not use the prime factorisation of polynomials but only gcd computations.)
gap> x:=X(Rationals);; gap> a:=x^2*(x-1)^3*(x-2)*(x-3); x_1^7-8*x_1^6+24*x_1^5-34*x_1^4+23*x_1^3-6*x_1^2 gap> b:=x^2*(x-1)^2*(x-2)^4*(x-4); x_1^9-14*x_1^8+81*x_1^7-252*x_1^6+456*x_1^5-480*x_1^4+272*x_1^3-64*x_1^2 gap> GcdCoprimeSplit(a,b); [ x_1^5-4*x_1^4+5*x_1^3-2*x_1^2, x_1^4-6*x_1^3+12*x_1^2-10*x_1+3, x_1^7-12*x_1^6+56*x_1^5-128*x_1^4+144*x_1^3-64*x_1^2 ]
‣ PolynomialToMatVec( A, pol, v ) | ( function ) |
Returns the row vector obtained by multiplying the row vector v with the matrix pol(A), where p is a polynomial. The actual computation is more efficient than this naive approach.
gap> A:=[ [ 0, 1, 0, 1 ], > [ 0, 0, 0, 0 ], > [ 0, 1, 0, 1 ], > [ 1, 1, 1, 1 ] ];; gap> x:=X(Rationals);; gap> pol:=x^6-6*x^5+12*x^4-10*x^3+3*x^2;; gap> v:=[ 1, 1, 1, 1 ];; gap> PolynomialToMatVec(A,pol,v); [ 8, -16, 8, -16 ]
‣ LcmMaximalVectorMat( A, v1, v2, pol1, pol2 ) | ( function ) |
Returns, given a matrix A, vectors v1, v2 with minimal polynomials pol1, pol2, a new pair [v,pol], where v has minimal polynomial pol, and pol is the least common multiple of pol1 and pol2. This crucially relies on GcdCoprimeSplit (4.1-1) to avoid factorisation of polynomials.
‣ SpinMatVector( A, v ) | ( function ) |
Computes the smallest subspace containing the vector v that is invariant under the matrix A. The output is a quadruple, with
1st component = basis of that subspace in row echelon form;
2nd component = matrix with rows v, v.A, v.A^2, ..., v.A^{d-1} (where d is the degree of the local minimal polynomial of v);
3rd component = the coefficients a_0, a_1, ..., a_d of the local minimal polynomial; and
4th component = the positions of the pivots of the first component.
gap> A:=[ [ 5, 2, -4, 2 ], > [ -1, 0, 2, -1 ], > [ -1, -1, 3, -1 ], > [ -13, -7, 14, -6 ] ];; gap> SpinMatVector(A,[1,0,0,0]); [ [ [ 1, 0, 0, 0 ], [ 0, 1, -2, 1 ] ], [ [ 1, 0, 0, 0 ], [ 5, 2, -4, 2 ] ], [ -1, 0, 1 ], [ 1, 2 ] ] gap> SpinMatVector(A,[0,1,0,0]); [ [ [ 0, 1, 0, 0 ], [ 1, 0, -2, 1 ], [ 0, 0, 1, -1/2 ] ], [ [ 0, 1, 0, 0 ], [ -1, 0, 2, -1 ], [ 6, 3, -4, 2 ] ], [ 1, -1, -1, 1 ], [ 2, 1, 3 ] ] gap> SpinMatVector(A,[1,1,0,0]); [ [ [ 1, 1, 0, 0 ], [ 0, 1, 1, -1/2 ] ], [ [ 1, 1, 0, 0 ], [ 4, 2, -2, 1 ] ], [ 1, -2, 1 ], [ 1, 2 ] ]
‣ CyclicChainMat( A ) | ( function ) |
Repeatedly computes the smallest invariant subspaces containing different vectors to compute a chain of cyclic subspaces. The output is a triple [B,C,svec] where C is such that CAC^-1 has a block triangular shape with companion matrices along the diagonal), B is the row echelon form of C and svec is the list of indices where the blocks begin.
gap> A:=[ [ 0, 1, 0, 1 ], > [ 0, 0, 1, 0 ], > [ 0, 1, 0, 1 ], > [ 1, 1, 1, 1 ] ];; gap> sp:=CyclicChainMat(A); [ [ [ 1, 0, 0, 0 ], [ 0, 1, 0, 1 ], [ 0, 0, 1, 0 ], [ 0, 0, 0, 1 ] ], [ [ 1, 0, 0, 0 ], [ 0, 1, 0, 1 ], [ 1, 1, 2, 1 ], [ 0, 0, 0, 1 ] ], [ 1, 4, 5 ] ] gap> PrintArray(sp[2]*A*sp[2]^-1); [ [ 0, 1, 0, 0 ], [ 0, 0, 1, 0 ], [ 0, 3, 1, 0 ], [ 1/2, 1/2, 1/2, 0 ] ]
‣ MaximalVectorMat( A ) | ( function ) |
Returns the minimal polynomial and a maximal vector of the matrix A, that is, a vector whose local minimal polynomial is that of A. This is done by repeatedly spinning up vectors until a maximal one is found. The exact algorithm is a combination of
the minimal polynomial algorithm by Neunhoeffer-Praeger; see [NP08]; and
the method described by Bongartz (see [Bon14]) for computing maximal vectors.
See also the article by Geck at [Gec20].
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> MaximalVectorMat(A); [ [ 1, -2, 1, 1, 0, 0, 1 ], x_1^4-7*x_1^3+17*x_1^2-17*x_1+6 ] gap> v:=last[1];; gap> SpinMatVector(A,v)[3]; [ 6, -17, 17, -7, 1 ]
In the following example, M_2 is the (challenging) test matrix from the paper by Neunhoeffer-Praeger:
gap> LoadPackage("AtlasRep");; g:=AtlasGroup("B",1); M2:=g.1+g.2+g.1*g.2; <matrix group of size 4154781481226426191177580544000000 with 2 generators> <an immutable 4370x4370 matrix over GF2> gap> SetInfoLevel(Infonofoma,1); gap> MaximalVectorMat(M2);;time; #I Degree of minimal polynomial is 2097 6725 gap> MinimalPolynomial(M2);;time; 13415 gap> LoadPackage("cvec"); gap> MinimalPolynomial(CMat(M2));;time; 9721
‣ JacobMatComplement( T, d ) | ( function ) |
Modifies an already given complementary subspace to the complementary subspace defined by Jacob; concretely, this is realized by assuming that T is a matrix in block triangular shape, where the upper left diagonal block is a companion matrix (as returned by RatFormStep1 (4.1-8); the variable d gives the size of that block. (If T gives a maximal cyclic subspace, then Jacob's complement is also T-invariant; but even if not, it appears to be very useful because it produces many zeroes.)
‣ RatFormStep1( A, v ) | ( function ) |
Spins up a vector v under a matrix A, computes a complementary subspace (using Jacob's construction), and performs the base change. The output is a quadruple [A1,P,pol,str] where A1 is the new matrix, P is the base change, pol is the minimal polynomial and str is either 'split' or 'not', according to whether the extension is split or not.
gap> v:=[ 1, 1, 1, 1 ];; gap> A:=[ [ 0, 1, 0, 1 ], > [ 0, 0, 1, 0 ], > [ 0, 1, 0, 1 ], > [ 1, 1, 1, 1 ] ];; gap> PrintArray(RatFormStep1(A,v)[1]); [ [ 0, 1, 0, 0 ], [ 0, 0, 1, 0 ], [ 0, 3, 1, 0 ], [ 1, 0, 0, 0 ] ]
generated by GAPDoc2HTML