AAECC 7, 391 399 (1996)
AAECC ApplicableAlgebra in Engineering, Communication and Computing
9 Springer-Verlag1996
Extensions of Irreducible Representations Torsten Minkwitz Institut ffir Algorithmen und Kognitive Systeme, Universitiit Karlsruhe, D-76128 Karlsruhe, Germany,
[email protected] Received August 19, 1995
Abstract. This article is concerned with the problem of computing extensions of irreducible representations. Assume that an irreducible representation p of a subgroup H of some finite group G is known, whose character is the restriction of an irreducible character Z of G. Then there is an extension/5 of p from H to G affording Z. In the article, a formula is presented that allows the explicit construction of extensions. A consequence of the result is an improved method to compute ordinary unitary representations for all irreducible characters of solvable groups.
Keywords: Group Theory, Irreducible Ordinary Representations, Generalized Fourier Transforms.
1 Introduction There are several applications of representation theory that require the availability of explicit representations of finite groups (e.g. to apply generalized Fourier transforms as defined in [2], [3], [4], [8] or to find fast algorithms for other signal transforms as treated in [9]). While the problem of computing irreducible modular representations is solved quite well by Parker's MEATAXE, no such general method exists yet for the case of ordinary representations. This article adds another technique to existing ones for solving the problem for the ordinary case. In particular, it provides an improved method to compute ordinary unitary representations 1 for all irreducible characters of solvable groups. However, the method presented is more general than that. It was used to compute irreducible representations of some non-solvable groups of orders up to more than l0 s . The method has been implemented in the M A G M A computer algebra system written by John Cannon's group in Sydney. In Sect. 2, the main theorem of this article is stated, a few definitions are made and some helpful lemmata are proved. Sect. 3 contains the proof of the main theorem. In Sect. 4, an improved method is presented to compute representations for 1A representation is unitary, if all its matrices are unitary
392
T. Minkwitz
all irreducible characters. The appendix contains an example calculation of a unitary irreducible representation of degree 10 of the Mathieu group M l l . This underlines the statement that this is not a method restricted to solvable groups. The article assumes some familiarity with representation theory of finite groups. For the reader unfamiliar with some of the terminology used, the books [5], [11] are recommended.
2 The Extension Theorem
Let Z be an ordinary irreducible character of a finite group G. The problem in consideration is to compute a representation r that affords Z. If Z is not a linear character, this can be a difficult task. Several articles have been published on this topic (see [-1], [6], [7]). However, up to now, there are no general formulae, which solve the problem. The cited articles present solutions that essentially involve solving linear systems of equations over cyclotomic fields, which yields the methods unfeasible for larger degrees of representations. A natural approach is to try to find the desired representation of G from a known representation of a subgroup of G. An easy case is the one, when Z is the induction of some irreducible character ~ of a known subgroup K of G, and one already knows a representation of K affording ~. In that case, one simply uses Formula 2 and gets the desired result. This shall be called the induction case. Another case that appears quite frequently is the one, when the restriction of Z to some subgroup H of G yields an irreducible character ~ of H. In that case the knowledge of a representation p of H affording ~ is already a partial answer to the problem. What is needed is an extension of the map p: H ~ GL~(V) to G, where Iz is a field of characteristic zero and V is the representation space over F of p. This is the extension case. The following theorem gives a solution for it. Theorem 1 (Extension Theorem) Let G be a finite group, H a subgroup of G and Z an
irreducible character of G such that ~ = Resn(z ) is irreducible. I f p is a representation of H affording 4, then p defined by .... Z(1) w "hPtKJ:=~-;a~uZt lk)P(h)
is an irreducible representation of G affording Z such that Resn(~) = p. The theorem will be proved in Sect. 3. If p is any representation of G and Z is an irreducible character of G, then Z(1) e:= ~ ~ z(g)q~(g) I
(1)
I g~G
is a central primitive idempotent of the FG-algebra A, which is defined as the matrix algebra generated by the p(g) for all geG (see [-5], [11]). The (left and right) ideal generated by e affords the character Z (i.e. Trace(e.p(g))= Z(g) for all g~G). If the conditions of Theorem 1 hold, then ~ is trivially contained with multiplicity one in Resn(z). With Frobenius reciprocity, this means that Z is contained with multiplicity one in Ind~i(~). Therefore, the rows of e generate the Z(1)-dimensional representation space of the K-component of ,co:= lnd•(p). Let d := Z(1) be the degree of the character Z and n:= [G:H] be the index of H in G. The induced representation o f p is defined
Extensions of Irreducible Representations
393
up to isomorphism by
f~(glgg? 1) ~(glgg21)) i "'" i , gcG, ~(g,gg;t) ... P(g,gg21) .
qo(g) = Ind~(p)(g):=
.
.
(2)
where (gi)l <_i<_,is some fixed set of representatives of left cosets of H in G and/)(g) is zero for any g(~H and p(g) if g~H. Equation 1 is used to compute the central primitive idempotent e from Z and ~p. The next 1emma will show a useful property ofe. L e m m a 2 Let G be a finite group, H a subgroup of G and Z an irreducible character of
G such that~ = Resu(Z) is irreducible. Ifp is a representation of H affording ~, then the submatrix in the first d rows and columns of e:= ~g~GZ(g)lndG(p)(g) (thus the upper left "corner" of e) is equal to (1/n)I d (d), where d:= Z(1), n:= [-G:H] and Id(m) is the identity matrix of degree m for an integer m. Proof. Since e is computed from an induced representation, the sum can be drawn into the matrix. Therefore, one can rewrite e using Eq. 2:
j [ E Z(g)P(glgg; 1) ...
Ig~Gx(g)lo(guggl )
"'"
2 z(g)~(glgg~ 1)1
LZ-~pignggn 1)/
The submatrix in question is: d
1
d
1
d
4(1)
- - ~ z(g)P(glgg[ ) = - - ~ z(g[ ggl)P(g) = - - Y', z(g)f3(g) = ~ ~ ~(h)p(h) IGlg~a [G[g~ [GlgeG ,v, hEH 1
4(1)
--
The expression within parenthesis' at the end is again a central primitive idempotent, because it has exactly the form and properties of the right hand side of Eq. 1. Its rank is 4(1) = d. The only idempotent matrix of full rank is the identity matrix. QED. It is clear from L e m m a 2 that the first d row vectors of e are a basis of the representation space of the X-component of (p. This component is irreducible, because X has been shown to have multiplicity one in (p. Let B be the d x (d- n)-matrix formed by the first d rows of e and B the (d.n) x d-matrix formed by the first d columns of e. Since e is an idempotent and because of L e m m a 2, it holds that
BB = lid(d).
(3)
n
The next lemma proves that these two matrices can be used to obtain an irreducible representation of G.
394
T. Minkwitz
Lemma 3 Let q) be a representation of a finite group G and Z an irreducible character of G that is contained with multiplicity one in the character of (o. I f B is a matrix, whose rows are a basis of the representation space V of the Z-component of cp and for some other matrix B it holds that BB = Id(d), then
g ~ Bqo(g)B defines an irreducible representation ~ of G affording Z. Proof. One adds rows to B from a basis of the orthogonal complement space V • of V. This is done until the resulting matrix D is square. It is by construction an invertible matrix. Therefore, and since V and V • are invariant under cp, DcpD- 1 is decomposed and the degree d upper most blocks of the representation matrices of yield an irreducible representation of G affording Z. It was assumed that BB = Id(d). Therefore, the column vectors of/~ must be the sum of the first d columns of D - 1 and of a matrix formed of complex conjugates of column vectors from V • This is trivially true, because matrix multiplication involves computing inner products of rows of the first factor with columns of the second, except for complex conjug&tion. If D 1 is the matrix formed by the first d columns of D -1 and O 2 = B - D1, then
D~D-1
p(g) = B(p(g)B = B(p(g)(D 1 + D2) = (Bq)(g)D 0 + (B~o(g)D2). The first term of the sum is the degree d upper most block ofD~o(g)D- 1 which is the image of an irreducible representation. The second term is zero, because q0(g) leaves V invariant and the complex conjugate of D 2 has columns from V • whose inner products with row vectors of B(eV) are zero by definition. QED. Consider again the matrices B and/~ as in Eq. 3. L e m m a 3 shows that the m a p ~ : G --+GLr( V ) defined through:
kF--~n(B~o(k)B)
(4)
with keG is an irreducible representation affording Z. In the next section it will be shown that this expression can be simplified further.
3 Proof of the Extension Theorem We keep the notation of the last section. F r o m Eq. 1 and 2 one can see that:
B = ~1 I
z(g)P(glgg~ 1)..... ~, z(g)P(glgg21) I\g~G
(5)
gEO
Since (p is an induced representation, each row and column of its matrices is non-zero only at a m a x i m u m of d positions. For any row or column, all of these positions belong to one single coset of H in G. Consider the matrix ~0(k) for some keG. For a row belonging to the coset of g; the only non-zero entries belong to columns of the coset of gjk. Therefore, it holds that: 1
B~o(k) = ~1 I
i
z(g)P(glgg71)P(g;lkg[l),..., ~ z(g)~(glgg2 )P(g~,,@2 ) , I\gEG
geG
(6)
Extensions of Irreducible Representations
395
is such that gj,kg~ ~EH. The sums run exactly over those elements ge G such that g lggj71 e H for the different i~ [1... n]. They can therefore be rewritten to run over h~H, ~ can then be simplified to p and the two matrix factors inside the sum can be multiplied: w h e r e gji
Bq~(k) =
id~_j(~ x(gl lhgj)p(hgj,kgl 1). . . . . ~ z(gl-lhgj,)p(hgj, kg~ 1) i,,a i -\h~H
h~H
/
h~(hg~ 'g/) d f r~ , -1, --1 _,,., Z ~ 2. zig1 ngln )PW)..... ~, z(g~lhg,k-~)P(h) / I~l \ h ~ H hell c~
=
d /
k
==| ~, z(g~" -lg71hglgi1)P(h), IGl\heH
....
E z(g yk- l g 7 l hgng; 1)p(h)1/
h~H
h-+(g~kgs~h) d [ ~ 1 1 1)p(glkgy ~h) ~ = ~ L z(hglgy )p(g~kgy h),..., ~, z(hgng~ / \hell
=
hell
P(glkgf
z(gy
gl)p(h),...,~,z(gflhg,)P(h) h~H
)
h ~ ( g f g g i 1)
=
P(glkgf )~1 [
I\geG
z(g)P(glgg~ ).... , ~ z(g)P(gfgg, 1) ,
(7)
geG
where gf is the representative of the left coset of k. It should be remembered that one can always choose gl = 1. That means that B~p(k) is just the product ofp(kg~ *) with the submatrix of the rows of the central primitive idempotent e belonging to the eoset of gf. Since e is idempotent, the product of it with B is again a submatrix of e and it holds that 1
d
nBcp(k)B= np(kg y ) ( ~ [ ~ z(g)fi(gfgg~ l) ) =
np(kgf 1
z(g; lhgl)p(h \
hell
/
h~(gjk Ih) d _ 1 i~[h~.~HZ(k- hg~)p(h). --
= ~H~h~ Z(h- ~k)p(h).
(S)
This is already the result to be proved for the theorem. If k~H, then this projects trivially to p(k), because then gf = gl = 1 and p(k) can be factored out of the expression in the first line in Eq. 8 and the rest is the identity because of L e m m a 2. So the representation fi as defined in (4) really is an extension of p. QED. It should be noted that if p is unitary, the extension fi must be unitary as well.
396
T. Minkwitz
4 Computing Unitary Irreducible Representations for Solvable Groups It is known that for a prime index normal subgroup H of a finite group G, every irreducible character Z of G is either the induction of an irreducible character of H or the restriction ofz to H is irreducible (see e.g. [4]). So either the induction case holds or the extension case. Also, each non-trivial solvable group G has a prime index solvable normal subgroup H. These two observations, Formula 2 and the extension theorem together yield an algorithm to compute unitary irreducible representations for a solvable group G. One first computes a composition series for G. To compute a representation affording Z, one checks whether the restriction of Z to the prime index normal subgroup /-/ of G in the series produces an irreducible character (through orthogonality relations). If yes, then recurse with H and ~ and then apply the formula from the extension theorem. If not, then there is an irreducible character ~' of H such that Z = Ind~(~'). Therefore, recurse with ~' and then use Formula 2 to get a representation of G affording Z. The base case is the trivial 1-element group that has the 1-representation as its only irreducible. Since the 1-representation is trivially unitary, the result will always be unitary as well. This is, to the knowledge of the author, the first efficient method to achieve such results. Using the M A G M A computer algebra system, it has always been more time consuming to compute the conjugacy classes and characters of the groups in the composition series than to apply the induction or extension formulae. The actual algorithm implemented does not work as simple as stated above though. To avoid applying the formula of the extension theorem too often, the smallest group H in the composition series of G is found, such that the restriction of Z to H is the irreducible character ~. Then it is known that the next step down in the series leads to an induction case. If that next step down is the subgroup K, one can compute the representation r affording Z using Formula 2:
P(9) = ~H~L z(h- l g)Ind~( 4')(h) 9"
k~KZ(hw:KIk,l h ;
19)4'(k) / (9)
IHI \ E z(h~ k (hrn~Klg)4'(k) "" ~ z(hw:K~k; lh(u~K~g)4'(k)] ",ksK
keK
where 4' is an irreducible representation of K such that Ind,(4') affords ~ and (hi)~__
Extensions of Irreducible Representations
397
5 Conclusions A new way to compute extensions of group representations has been presented. It is useful for constructing explicit irreducible representations of finite groups. In the case of solvable groups, the results of this article provides an improved method to compute unitary irreducible representations in characteristic zero. Other methods, such as the one described in [6] do not guarantee any representation for some irreducible character of a solvable group. Dixon's method was implemented by the author and found to be considerably slower (it should be noted that the method was, at least in theory, applicable to all tried cases, even though it was pointed out in [7] that there are solvable groups that it can't handle). The new result fits in well with the new method for computing irreducible representations presented in [ 10]. Combining those results with the extension formula, the currently most general and efficient method to compute ordinary irreducible representations can be compiled. It will soon be made available to all users of MAGMA. I want to thank my advisor Thomas Beth and also John Cannon for encouraging me to keep working on the topic.
Appendix The Mathieu group M 11 can be generated by the three permutations (see [6]): x = ( 1 2 3 4 5 6 7 8 9 10 11) y = ( 1 5 9 6)(2 8 3 4) z = ( 1 7 9 6 8 3 5 4)(2 10). The aim is to compute an irreducible representation that affords the character: )~ = (10, - 2 , 1, 0, 0, 1, co, -co, - 1 , - 1 ) , where co2 = _ 2. The Mi ~ = (x, y, z> has a subgroup H generated by the permutations: u = ( 1 8 9 3 10)(2 5 7 4 6) v = ( 2 6 7 9)(3 5 8 10) It has order 360 and an irreducible character: 3=(10, - 2 , 1, 1, 0, 0, 0), which is the restriction o f z to H. The group H = (u, v} has a subgroup K generated by the permutations: t = ( 1 5 4 10)(2 9 6 7) s = ( 1 7 8 6)(2 10 5 9) Now ~ is the induced character of a linear character of K to H. Therefore, an irreducible representation p of H affording ~ can easily be found through Formula 2. Since Resu(z)= 4, now the formula of the extension theorem can be used to construct a representation r of G affording )6
6
~(z) = 1
P(y)=~
~(x)=~
X+X
X 2
X 2
2
X_X
3
X-X
1 -X 2
3
Xq-2X2+X
1 -X 2
X+X
Xq-2X2+X
3
3
3
--lq-X 2
X+X
1 -X 2
X+X
-X--2X
--X+X
z
3
3
X
-X+X
3
X 3
3
3
3
3
3
3
X 3
3
3
3
3
2
2X2+X
X--2X2q-X
X
I+X
--X--X
2q-X--X
--X-X
_X_X
3
3
--lq-X 2
3
--X-}-X 3
2
--X--X
X+2X2-X
Xq-2X2q-X
3
3
2
2
2
--X--2X2--X
X-X
3X+3X
I +X 2
-I+X
--I-]X
--I+X
lq-g 2
Xq-X a
3
3
2
X 2
X2
-- 1 + X 2
-I+X
1
1
X~-X 3
- 1 -X 2
1 -X 2
3
3
Xa
3
3
3
2X 2-X
--X-X
--2+X-X
3X + 3X 3
2
2xZ+x
2--X+X
X
X
--X+2X
2
_I_X
I+X 2
-- 1 -- X 2
1
1 +X 2
1
--I+X
1 --X 2
X+X
--1--X 2
3
- 1+ X 2
3X - 3X 3
3
Xq-2X2q-X
3
3
2
--I+X
X_X
-X+X
1 _if(2
2
3
l +X z
-X-X
--Xq-2xZ-x
X+X
2
3
3
3
X 3
3
X 3
-X--2Xz-X
X
2+X
--X+X
X+X
-X-X
-2+X-X
2
1 -X
-I+X
1 -X
--X--X
X-~-X 3
3
3
Xq-2X2q-X
a
3
3
a
3
X-2X2+X
X-X
X+X
X+2X2+X
2-X+X
X--X
3
2+X
2+X-X
-2+X
Xq-X
-X-X
I+X
X_X
--X-2X
X_X
X+2X
a
3
3 3
X 3
X 3
3
X 3
3
2
3
2
3
3
X 3
3
3
2
--Xq-X
_X_2X2_X
X--X
2+X
X--X
-X+X
3
3
X 3
2
3
X 3 3
lq-X 2
X-X
-2-X+X
2-X4-X
X
--]--X
X+X
2+X--X
3 X 3
a
X-}- X 3
X--X
2+X
X +X 3
Xq-2X2+X
X 3
3
2
3
3
3
3
X
X+X
2--X+X 3
3
X 3
--2--X+X
3
3
X 3
3
3
-- 1 - - X 2
X--X
X+X
-X--2X
-X-X
2-X+X
X-2Xz+X
-X+X
X+X
X@X
X 3
--1--X 2 X
3 3
X 3
3
3
3 3
3
3
X 2
2
--2--X+X
X
3 3
X 3
2q-X--X
2-X+X
1
X+2X
--X-X
-X+X
X
X+2X+X
-2+X--X
2 ~ X--X
X+X
-X+X
2X 2
3
3
X+X X--X
--X-X
X a
a
3
2
X+X
X+X
2+X--X
X-X
3
a
1 +X 2
--X+2X
--X+2Xi--x
a
a
3
3
3
3
X 3
3
3
3
2X2-X -X--X
-X
X-2X2-X
X+X
X--X
3
3
X 3
3
a
2
--2--X+X
X-2X2+X
I+X
--2+X
--X
3
3
X 3
3 3
--lq-X 2
2-X+X
X_X
X+2X2-X
- X-
X+X
X+X
--X-~X
-X-X
2+X-X
X+X
X 3
X 3
3
3
3
--X--X
X-X
X+X
3
3
X+X
3
a
3
-- 1 - - X 2 --2
3
3
2
3
Xq-2X2+X
X
X
X--2X2+X
2
X--X
X+X
--2--X+X
X+X
X@X
-1-X
2--X+X
-2+X-X
X
3 3
X 3
1 --X 2
2+X-X
--X-X
3
X 3
X--X
X
--X--X
-X+X
2X2+X
_2_X+X
X
a
a
3
3
3
3
3
3
X-}-X 3
2--X+X -2
X
X 3
3
3
X+X
X 3
a 3
X+X
--X
X--2X2+X
X a
X 3
X--2X2+X X
3
3
3
3 3
3
3
3
3
X 3
X 3
3
3
X a
1 -TX 2
X+X
--X--X
2-X+X
2+X
3
a 2
X-~-X 3
X+X
X
--X q-2X 2
--2--Xq-X
I+X
X+X
-X+X
X4-2X2-X
Xq_2X2q_X
1 +X 2
X-}- 2 X 2 + X 3
2
--X
2-X+X
X-}-2X2--X
X+X
X+X
X-}-X 3
X
X 3
X 3
3 X 2
2-X+X
3 3
2+X--X
-X--X
X
X+X
3
3
3
3
a 3
X 3
3
3
3
X 3
3
1 +X 2
X+2X2--X
XWX
X--2X2q-X
X--X
2+X--X
--X+2X
2
X-}-X 3
X+2X2+X 2+X-X
3 X 3 1 +X 2
-X.-X
X
-X-X
3
X 3
3
a
_X_}_X 3
1
X+X
-2+X
X-}-X 3
2+X-X
X
2+X--X
2+X-X
Xor-X 3
a 3
3
a
3
3
3
3
3
3
3
X+2X
_X_2X
-X+2Xz-X
X+X
3 3 3
3
3
3
3 2
X 3
2_X 3
3
1--X z
-2-X+X
_X_X
_X_X
X+X a X X 3
X_X
3
X 3 X--2X2+X
X
3 2 X+2X2+X
--X--X
I--X
X_X
X-I-2X2+X
X-X
Xq_2X 2 _X3 t
-- 1 - - X 2
X-X
--X--X
X-X
-X-kX
X--2X2-}-X
2+X--X
X--X
X--2X2q-X
X-}-2X2@X
Extensions of Irreducible Representations
399
where X = x / ~ is an 8-th r o o t of unity. T h e r e p r e s e n t a t i o n t5 is unitary. It t o o k a b o u t half a m i n u t e to c o m p u t e in M A G M A .
References 1. Babai, L., R6nyai, L.: Computing Irreducible Representations of Finite Groups. Math. Comput. 55, 705-722 (1990) 2. Beth, T.: Verfahren der schnellen Fouriertransformation. Stuttgart: Teubner 1984 3. Beth, T.: Generalized Fourier Transforms. Lecture Notes of Computer Science vol. 296, pp. 92-118. Berlin, Heidelberg, New York: Springer 1988 4. Clausen, M., Baum, U.: Fast Fourier Transforms. BI-Wissenschaftsverlag, Mannheim, t993 5. Curtis, C. W., Reiner, I.: Methods of Representation theory I. New York: Wiley-Interscience 1981 6. Dixon, J. D.: Constructing Representations of Finite Groups. DIMACS Series in Discrete Mathematics and Theoretical Computer Science vol. 11 (1993) 7. Janusz, G. J.: Primitive Idempotents in Group Algebras. Proc AMS 17, 520 523 (1966) 8. Karpovsky, M. G.: Fast Fourier Transforms on Finite Non-Abelian Groups. IEEE Trans. Comput. C-26, 1028-1030 (1977) 9. Minkwitz, T.: Algorithmensynthese fiir lineare Systeme mit Symmetrie. Doctoral Thesis, University of Karlsruhe, 1993 10. Minkwitz, T.: On the Computation of Ordinary Irreducible Representations of Finite Groups. Proceedings of ISSAC 95, (1995) 11. Serre, J.-P.: Linear Representations of Finite Groups. Graduate Texts in Mathematics vol. 42. Berlin, Heidelberg, New York: Springer 1977
