I am studying representation theory, and I would like to find an algorithm that finds, given a finite group $G$, a one to one morphism $p : G \to GL_n(\mathbb{C})$ (the integer $n$ is also found by the algorithm). I don't necessarily want this algorithm to be efficient. First is it possible to make such an algorithm ?

Now I am wondering how to begin with. I thought about finding the character table of the group first (I know this not an easy task) and find its irreductible representations, but then from here I don't see how I can find a solution to my problem. If I have all the irreductible representations of my group I don't see how I can get $p$. I mean the characters only give information about the sum on the digonal of $p(g)$, but how to get from this information the other entries in the matrices ?

Thank you !

  • $\begingroup$ "given a group $G$" is important. i removed the parentheses $\endgroup$ – mathworker21 Jun 3 at 11:02
  • $\begingroup$ Take a look at Theorem 2.12 of "Introduction to Representation Theory" by Etingof (for finite groups only). Since the field is $\mathbb{C}$, $A=\mathbb{C}[G]$ is semisimple, and therefore there is an isomorphism of algebras $A\cong \oplus_i End(V_i)$, where $V_i$ are the irreducible representations of $G$. $\endgroup$ – Javi Jun 3 at 11:04
  • $\begingroup$ @mathworker21 when I say given a group $G$ it means any type of group theoric description of $G$ (for example Cayley table) $\endgroup$ – bonjour1 Jun 3 at 11:04
  • 4
    $\begingroup$ If $G$ is finite you can just use $n=\#G$ with the regular representation. For infinite $G$ we may not have finite dimensional faithful representation. $\endgroup$ – user10354138 Jun 3 at 11:08
  • 1
    $\begingroup$ Matrices of the regular representations are easily extracted from the Caley table. Try at hand with the symmetric group of order 6. $\endgroup$ – InfiniteLooper Jun 3 at 11:22

Every finite group embeds into a permutation group; this is Cayley's theorem. The proof of the theorem is essentially constructive, with $G$ embedding into $S_{|G|}$. That is, there is an algorithm with input a Cayley table* of a finite group $G$ and output a permutation group $\operatorname{Perm}(G)$ isomorphic to $G$. You can then easily embed $\operatorname{Perm}(G)$ into $\operatorname{GL}_{|G|}(\mathbb{C})$ using permutation matrices, and again this can be made algorithmic.

*The input form can vary, but the OP explicitly mentions Cayley tables in the comments.

  • $\begingroup$ Thankfully, the OP also explicitly mentioned that the algorithm didn't need to be efficient ! (well this one is very quick to find the morphism, but the $n$ it produces is most often far from optimal) $\endgroup$ – Max Jun 3 at 14:55
  • $\begingroup$ The constructive proof of Cayley's Theorem is essentially the content of my answer, except that instead of embedding in $S_{|G|}$, I've further mapped $S_{|G|}$ into $SO(|G|)$ so that you get an actual faithful representation of $G$ in the orthogonal group. $\endgroup$ – John Hughes Jun 6 at 10:45

Take a group, with elements $g_1, \ldots, g_n$.

Associate to $g_1$ the vector $e_1 \in \Bbb R^n$.

Now for element $g_1$, compute the $n$ items $$ g_1 \cdot g_1, g_1 \cdot g_2, \ldots, g_1 \cdot g_n. $$ These will be the elements of $G$, in some new order, such as $$ g_7, g_2, \ldots, g_3. $$ Write down the corresponding vectors as the columns of a matrix $$ M_1 = \pmatrix{ e_7, e_2, \ldots, e_3} $$ Do the same for $g_2$ to produce $M_2$, and so on.

The map $g_1 \mapsto M_1, g_2 \mapsto M_2, \ldots$ will be a injective homomorphism of groups.

(Unless I've messed up and forgotten a transpose somewhere...)

You can test this out pretty quickly by trying it for $\Bbb Z/3\Bbb Z$, or even $S_3$.


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.