Given a finite group $G$, let $n$ be the smallest integer s.t. $G \subset S_n$ à la Cayley. I guess that if I want to construct the complex irreps (not just the character table) of $G$ then I could take the irreps of $S_n$ and restrict them to $G$. It seems plausible that after decomposition this might yield all the irreps of $G$, but I'm not entirely sure of this. In any event it seems inefficient, even if it works.

So my question is: what is the (is there a?) general technique for constructing all the inequivalent complex irreps of a finite group?

Maybe this is better suited to the underflow site, but since it's come up in actual work (albeit of the documentary sort) I'm posting here.

  • 1
    $\begingroup$ Just a comment, your suggestion for generating all irreps does work but as you say inefficient. $\endgroup$ – Torsten Ekedahl Nov 10 '10 at 15:57
  • $\begingroup$ The $n$ is $|G|$, unless by à la Cayley you mean simply an injective morphism $G\to S_n$. $\endgroup$ – Mariano Suárez-Álvarez Nov 10 '10 at 16:00
  • $\begingroup$ @Mariano: I do, but good point. $\endgroup$ – Steve Huntsman Nov 10 '10 at 16:07
  • $\begingroup$ There is usually a better choice than $|G|$. You just have to find a subgroup $H<G$ such that the permutation representation $\mathbb{C}[G/H]$ is faithful. Usually, you will be able to find bigger groups than {1}. Still, as Torsten Ekedahl says, this method will be inefficient. $\endgroup$ – Alex B. Nov 10 '10 at 16:08
  • 2
    $\begingroup$ One method of constructing representations is to induce irreducible representations from (maximal) subgroups. $\endgroup$ – Bruce Westbury Nov 10 '10 at 16:11

I think, the article by Vahid Dabbaghian-Abdoly, Journal of Symbolic Computation Volume 39, Issue 6, June 2005, Pages 671-688, entitled "An algorithm for constructing representations of finite groups", doi:10.1016/j.jsc.2005.01.002, and the references in the introduction give you what you are looking for. I think, this is the state of the art to this day. Basically, finding all the irreducible representations can be done in polynomial time.

I am not sure off the top of my head what the complexity of your suggested algorithm will be, but the bottleneck will likely be the fact that $S_n$ always has an irreducible representation of degree $n$. Generically, decomposing a representation of degree $|G|$ is much more work than you should have to do.


Why representations? A better question is to find all irreducible characters or to fill the character table. You can do it efficiently for any given group.

After you have characters, you may want to construct its representations following MO

  • 1
    $\begingroup$ Which question is "better", depends on what you want to do. Also, my understanding of the question is that Steve already knows an algorithm for getting the representations from the character table, but is wondering about more efficient ways of doing it. That was not the focus of the question you have linked to. $\endgroup$ – Alex B. Nov 10 '10 at 17:31
  • $\begingroup$ Violently disagree. If you have a finite group, a character is better than a representation. Most of the things can be done on the level of characters. You need a very subtle question (such that figuring out why two groups have the same charecter tables) to start worrying about representation itself. Nonwithstanding this, the link I give tells you how to extract any representation from the regular representation if this is what you are looking for. $\endgroup$ – Bugs Bunny Nov 10 '10 at 20:54
  • 3
    $\begingroup$ @Bugs: Here is an example of a question which cannot be answered just by studying the character table. <i> What is the element in the top right corner of the matrix representing element $g$ (where $g$ is your favorite element of the group)?</i> On the other hand if one studies properties that are invariant under conjugation (both in the matrix group and in the original group itself), then you are probably right and one just needs the character table. $\endgroup$ – Mark Sapir Nov 11 '10 at 12:46
  • 1
    $\begingroup$ The underlying context of my question is the (quantum) Fourier transform for nonabelian finite groups. "Strong Fourier sampling" requires one to obtain matrix elements. $\endgroup$ – Steve Huntsman Nov 11 '10 at 23:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.