##############################################################################
##
#W  glasby.gi           Cubefree                               Heiko Dietrich
##
##

##############################################################################
## 
#F  RewriteAbsolutelyIrreducibleMatrixGroup( G ) 
## 
## G has to be an absolutely irreducible subgroup of GL(d,q). The output
## is a group H such that H is conjugate to G in GL(d,q) and H is a subgroup
## of GL(d, r) where GF(r) is the subfield of GF(q) generated by the traces 
## of the elements in G. This implementation is based on an algorithm of 
## Howlett and Glasby.
##
InstallGlobalFunction( RewriteAbsolutelyIrreducibleMatrixGroup, function( G )
    local aMat, d, K, q, p, m, gen, k, a, Ga, el, v, H, HH, A, x, C, 
          i, t, n, min, size, solv;

    # check
    if not IsMatrixGroup( G )
       or not IsFinite( FieldOfMatrixGroup( G ) )
       or not MTX.IsAbsolutelyIrreducible(GModuleByMats( GeneratorsOfGroup( G ),
             FieldOfMatrixGroup( G ) ) ) then
        Error("<G> must be an absolutely irreducible matrix group over a finite field");
    fi;

    # auxiliary function computes M^(a^i) for M\in GL(d,K)
    # and an automorphism a: K \to K 
    aMat := function( M, d, i, a )
        local x,y,z,H,j;

        H := MutableCopyMat( M );
        for x in [1..d] do
            for y in [1..d] do
                z := H[x,y];
                for j in [1..i] do
                    z := a(z);
                od;
                H[x,y] := z;
            od;
        od;
        return H;
    end;

    # set up  
    K   := FieldOfMatrixGroup(G);
    d   := DimensionOfMatrixGroup(G);
    q   := Size(K);
    p   := Characteristic(K);
    m   := DegreeOverPrimeField(K);
    gen := GeneratorsOfGroup(G);

    size := 0;
    solv := 0;
    if HasSize(G) then size := Size(G); fi;
    if HasIsSolvableGroup(G) then solv := IsSolvableGroup(G); fi;

    # check if there are subfields of K
    if IsPrime(Size(K)) then
        return G;
    fi;

    # the subfield generated by the traces of the elements of G has to contain
    # the subfield generated by the traces of the generators of G
    min := DegreeOverPrimeField(Field(List(gen,TraceMat)));

    # check all possible subfields
    for n in Filtered( DivisorsInt( m ),x -> x<m and x>=min ) do
     
        k := GF( p^n );
        t := m/n;
        a := x -> x^(p^n);

        Info(InfoCF,4,"        Test subfield ",k," of ", K);

        # find isomorphism between G and G^a
        Ga := GModuleByMats( List( gen, x -> aMat(x,d,1,a) ), K);
        C  := GModuleByMats( gen, K );
        MTX.IsIrreducible( Ga );
        C  := SMTX.Isomorphism( C, Ga );
 
        # only if rewritting is possible over GF(p^n)
        if IsMatrix( C ) then
              
            # normalize C
            for v in K do
                if not IsZero( v ) then
                    H  := v^-1*C;
                    HH := H;
                    for i in [1..t-1] do
                        HH := HH * aMat( H, d, i, a );
                    od;
                    if HH = HH^0 then
                        C := H;
                        break;
                    fi;
                fi;
             od;
            
            # compute A
            A := 0;
            while not A in GL(d,q) do
                x := RandomMat( d, d, K );
                A := x;
                for i in [1..t-1] do
                    A := x + C * aMat(A,d,1,a);
                od;
            od;
            G := G^A;
            if not size=0 then SetSize(G,size); fi;
            if not solv=0 then SetIsSolvableGroup(G,solv); fi;
            return G;
        fi;
    od;

    # the case if no rewriting occurs
    return G;
end);