From: Udo =?iso-8859-1?Q?G=F6bel?= Subject: permutation groups and enumeration of irreducible basis Date: Fri, 07 Apr 2000 19:28:42 +0200 Newsgroups: sci.math.research Summary: [missing] Hi, as one step of a solution in an applied physics problem I've come across the following problem: A finite group G is acting on some finite set M. Consider the induced representation on F(M) - the vector space of all complex valued functions on M: Is it possible in an "easy" way to enumerate a basis of this space, each member of which is part of an irreducible representation? By "easy" I mean the following: Of course I can take the standard basis (the delta functions), calculate the character of the representation, determine - by employing the character table - the involved irreducible representations, project all delta functions into the constituent irreducible parts and sort out some basis. Besides generating a lot more functions than I'm looking for this seems not very efficient. So given the character table and perhaps some other information about the group is there an efficient way to do this? Obviously I'm not an expert in permutation groups, so any hint to relevant literature is welcome too. _ Udo ============================================================================== From: Dave Rusin Subject: Re: permutation groups and enumeration of irreducible basis Date: Fri, 7 Apr 2000 09:22:19 -0500 (CDT) To: ugoebel-t@t-online.de What you're asking for is precisely the decomposition of a (permutation) module into its irreducible constituents. Depending on how much you know about your group this may not be too hard. (I hope your group is not too large that the finite set being permuted is also small...) Corresponding to each irreducible representation ("irrep") of a finite group there is a central idempotent in the group algebra, which means quite a specific thing but will look to you like just a formal linear combination of the group elements. You then obtain a decomposition of any module as a sum of submodules by multiplying by these idempotents. For example, if the group is the cyclic group of order 3, with identity e and the other two elements a and b=a^(-1), then the three central idempotents are (1/3)e + (1/3)a + (1/3)b (corresponding to the trivial representation), (1/3)e + (w/3)a + (w^2/3)b (where w =-1/2 + sqrt(-3)/2 is a primitive cube root of 1), and the complex conjugate of this last one.' Well, now given a vector space on which this group acts, with basis vectors v_i, say, simply look at the subspace spanned by the products ( (1/3)e + (1/3)a + (1/3)b )*( v_i ) for all i -- in this case this just means the average of the three images of v_i under the permutation group -- and that gives you the subspace on which the group acts as a multiple of the trivial represetation. Repeat with either of the other idempotents and you get a subspace on which the group acts as a multiple of one of the other representations. You can split these subspaces up further into irreducible subspaces. Simply pick a vector at random, and compute its translates under the group action; these will span a subspace which will be an irreducible module for the group. If that does not exhaust the module, take something in the complement, and repeat this process. This will enable you to find a basis on which the group acts in a block-upper-triangular way, and you can then adjust each basis vector (modulo the next-smaller subspace) so that the group actually acts in a _block-diagonal_ manner; in that case you have found a decomposition into irreducible subspaces. There is group-theoretic software which can perform such calculations fairly easily, I think. Probably this is included in the GAP program (I haven't used that in a while) which is has been made freely available by some of your countrymen. You may find some useful information from index/20-XX.html [deletia --djr] dave (moderator)