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