‣ 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 \(\textit{v}, \textit{v}.\textit{A}, \textit{v}.\textit{A}^2, ..., \textit{v}.\textit{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 \(C\textit{A}C^{-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