1# Various representation isomorphism functions e.g. testing for
2# isomorphism and computing an explicit isomorphism.
3
4# Wraps an n^2 long list into a n long list of n long lists
5WrapMatrix@ := function(vec, n)
6    local result, current_row, elems_seen;
7    result := [];
8    current_row := [];
9    elems_seen := 0;
10    while elems_seen < Length(vec) do
11        elems_seen := elems_seen + 1;
12        Add(current_row, vec[elems_seen]);
13        if Length(current_row) = n then
14            Add(result, current_row);
15            current_row := [];
16        fi;
17    od;
18    return result;
19end;
20
21# Gives the full list of the E_ij standard basis matrices for M_n(C)
22MatrixBasis@ := function(n)
23    local coords, make_mat;
24    coords := Cartesian([1..n], [1..n]);
25
26    make_mat := function(coord)
27        local ret;
28        ret := NullMat(n, n);
29        ret[coord[1]][coord[2]] := 1;
30        return ret;
31    end;
32
33    return List(coords, make_mat);
34end;
35
36# Calculates the isomorphism using the cool fact about the product
37# (see below)
38InstallGlobalFunction( LinearRepresentationIsomorphism, function(rho, tau, args...)
39    local G, n, matrix_basis, vector_basis, alpha, triv, fixed_space, A, A_vec, rho_cent_basis, tau_cent_basis, triv_proj, used_tensors, rho_dual, class1, class2, candidate_map, classes, tries, sum, v, v_0, im, orbit, gen, i, rand;
40
41    # if set, these bases for the centralisers will be used to avoid
42    # summing over G
43    rho_cent_basis := fail;
44    tau_cent_basis := fail;
45
46    if Length(args) >= 2 then
47        rho_cent_basis := args[1];
48        tau_cent_basis := args[2];
49    fi;
50
51    if not AreRepsIsomorphic(rho, tau) then
52        return fail;
53    fi;
54
55    G := Source(rho);
56    n := DegreeOfRepresentation(rho);
57
58    # We want to find a matrix A s.t. tau(g)*A = A*rho(g) for all g in
59    # G. We do this by finding fixed points of the linear maps A ->
60    # tau(g)*A*rho(g^-1). This is done by considering the
61    # representation alpha: g -> (A -> tau(g)*A*rho(g^-1)) and finding a
62    # vector in the canonical summand corresponding to the trivial
63    # irrep. i.e. a vector which is fixed by all g, which is exactly
64    # what we want.
65
66    # The trick we use to avoid summing over G is to notice that alpha
67    # is actually \tau \otimes \rho^*, i.e. g -> tau(g) \otimes
68    # \rho(g^-1)^T.
69
70    rho_dual := FuncToHom@(G, g -> TransposedMat(Image(rho, g^-1)));
71
72    # The representation alpha : G -> GL(V) (V is the space of
73    # matrices).  We only actually need this if we are *not* using
74    # Kronecker products.
75    alpha := TensorProductOfRepresentations(tau, rho_dual);
76
77    # the projection of V onto V_triv, the trivial canonical summand,
78    # is just given by the sum over whole group of alpha(g)
79
80    if ValueOption("use_kronecker") = true then
81        # We do this with the BSGS method, this is probably fast. We try
82        # to sum in a way that doesn't require us to store any huge
83        # Kronecker products.
84        triv_proj := GroupSumBSGS(G, g -> KroneckerProduct(Image(tau, g), Image(rho_dual, g)));
85    fi;
86
87    classes := ConjugacyClasses(G);
88
89    # The idea here is that we want an element that is fixed by alpha,
90    # the natural choice is the sum of an orbit of some random vector
91    # v. We know that some choice of v gives an orbit sum that is
92    # invertible, so "almost all" choices of v work.
93
94    A := NullMat(n, n);
95
96    tries := 0;
97
98    repeat
99        if ValueOption("use_orbit_sum") = true then
100            v_0 := RandomInvertibleMat(n);
101            sum := v_0;
102            orbit := [v_0];
103
104            # This sums the orbit of v_0 under alpha. We know this will
105            # terminate since G is finite.
106            i := 1;
107            while i <= Length(orbit) do
108                for gen in GeneratorsOfGroup(G) do
109                    im := Image(alpha, gen) * orbit[i];
110                    if not (im in orbit) then
111                        Add(orbit, im);
112                    fi;
113                od;
114                i := i + 1;
115            od;
116
117            A := Sum(orbit);
118        elif ValueOption("use_kronecker") = true then
119            A := WrapMatrix@(triv_proj * Flat(RandomInvertibleMat(n)), n);
120        else
121            # Anything involving kronecker products has O(degree^4)
122            # space usage, Could be excessive. in some cases we have
123            # to resort to summing over the group which usually works
124            # but is slow. We can use linearity of alpha and the pair
125            # representation of tensor products to avoid excessive
126            # memory usage.
127            rand := RandomInvertibleMat(n);
128            A := Sum(G, g -> Image(alpha, g) * rand);
129        fi;
130        tries := tries + 1;
131    until RankMat(A) = n; # i.e. until A is invertible
132
133    return A;
134end );
135
136# Calculate the iso without using the cool fact about the conjugation
137# action being given by \tau \otimes \rho^*
138LinearRepresentationIsomorphismNoProduct@ := function(rho, tau)
139    local G, n, matrix_basis, vector_basis, alpha, triv, fixed_space, A, A_vec, alpha_f;
140
141    if not AreRepsIsomorphic(rho, tau) then
142        return fail;
143    fi;
144
145    G := Source(rho);
146    n := DegreeOfRepresentation(rho);
147
148    # We want to find a matrix A s.t. tau(g)*A = A*rho(g) for all g in
149    # G. We do this by finding fixed points of the linear maps A ->
150    # tau(g)*A*rho(g^-1). This is done by considering the
151    # representation alpha: g -> (A -> tau(g)*A*rho(g^-1)) and finding a
152    # vector in the canonical summand corresponding to the trivial
153    # irrep. i.e. a vector which is fixed by all g, which is exactly
154    # what we want.
155
156    # Standard basis for M_n(C)
157    matrix_basis := MatrixBasis@(n);
158
159    # The unwrapped vector versions, these are the what the matrices
160    # of our representation will act on
161    #
162    # We construct them in this way to keep track of the
163    # correspondence between the matrices and vectors
164    vector_basis := List(matrix_basis, Flat);
165
166    # This is the function that gives the representation alpha
167    alpha_f := function(g)
168        local matrix_imgs, vector_imgs;
169        matrix_imgs := List(matrix_basis, A -> Image(tau, g) * A * Image(rho, g^-1));
170
171        # unwrap them and put them in a matrix
172        vector_imgs := List(matrix_imgs, Flat);
173
174        # we want the images to be columns not rows (we act from the
175        # left), so transpose
176        return TransposedMat(vector_imgs);
177    end;
178
179    # the representation alpha
180    alpha := FuncToHom@(G, alpha_f);
181
182    # trivial representation on G
183    triv := FuncToHom@(G, g -> [[1]]);
184
185    # space of vectors fixed under alpha
186    fixed_space := IrrepCanonicalSummand@(alpha, triv);
187
188    A := NullMat(n, n);
189
190    # Keep picking matrices until we get an invertible one. This would
191    # happen with probability 1 if we really picked uniformly random
192    # vectors over C.
193    repeat
194        # we pick a "random vector"
195        A_vec := Sum(Basis(fixed_space), v -> Random(Integers)*v);
196        A := WrapMatrix@(A_vec, n);
197    until RankMat(A) = n;
198
199    return A;
200end;
201
202# calculates an isomorphism between rho and tau by summing over G
203# (slow, but works)
204# TODO: can I use a trick to sum over the generators instead of G?
205InstallGlobalFunction( LinearRepresentationIsomorphismSlow, function(rho, tau, args...)
206    local G, n, candidate, tries;
207    G := Source(rho);
208    n := DegreeOfRepresentation(rho);
209
210    if not AreRepsIsomorphic(rho, tau) then
211        return fail;
212    fi;
213
214    # we just pick random invertible matrices and sum over the group
215    # until we actually get a representation isomorphism. This almost
216    # always happens, so we "should" get one almost always on the
217    # first time.
218    candidate := NullMat(n, n);
219    tries := 0;
220    repeat
221        candidate := RandomInvertibleMat(n);
222        candidate := Sum(G, g -> Image(tau, g) * candidate * Image(rho, g^-1));
223        tries := tries + 1;
224    until IsLinearRepresentationIsomorphism(candidate, rho, tau);
225
226    return candidate;
227end );
228
229# Tells you if two representations of the same group are isomorphic by
230# examining characters
231InstallGlobalFunction( AreRepsIsomorphic, function(rep1, rep2)
232    local G, irr_chars;
233
234    if Source(rep1) <> Source(rep2) then
235        return false;
236    fi;
237
238    G := Source(rep1);
239    irr_chars := IrrWithCorrectOrdering@(G);
240
241    # Writes the characters in the irr_chars basis, they are the same
242    # iff they are isomorphic
243    return IrrVectorOfRepresentation@(rep1, irr_chars) = IrrVectorOfRepresentation@(rep2, irr_chars);
244end );
245
246# checks if A rho(g) = tau(g) A
247InstallGlobalFunction( IsLinearRepresentationIsomorphism, function(A, rho, tau)
248    local gens;
249    gens := GeneratorsOfGroup(Source(rho));
250    return RankMat(A) = DegreeOfRepresentation(rho) and ForAll(gens, g -> A * Image(rho, g) = Image(tau, g) * A);
251end );
252