Recovering representation from its character

If we know the character of a representation (of a finite group) over C (field of complex numbers), is it possible to recover the representation itself?

This is clearly possible if we know all the irreducible representations of the group. But what if we don't know them?

ADDED: 1) We know the group. By this I mean we have the "multiplication table" of the group. 2) We don't know the irreducible representations. We are only given a character of a representation. 3) We want to obtain a concrete realization of a representation yielding the given character. By this I mean a matrix for each element of the group. 4) Finally, we don't care about efficiency.

-
This question is poorly worded and consequently there has been several answers interpreting it in different ways and reaching opposite conclusions. The answer critically depends on (a) what is known about the group and its representations and characters (b) the desired output (the coefficients w.r.t. irreducible characters? explicit matrices for every element of the group?) and (c) how efficient you want the procedure to be (from pure existence to algorithm). I don't even understand whether the group itself has been given –  Victor Protsak Jul 22 '10 at 6:48
The updated question has a simple answer: guess and check. The character determines the dimension and the group G determines a finite dimensional extension field K=Q[exp(2πi/|G|)] of Q. Finite dimensional vector spaces over Q with a basis can be enumerated, in particular enumerate M_n(K)^G. For each such vector of matrices, test if it is a realization by checking that it defines a group, a group homomorphism, and has the right character. This is a finite process for any character, reducible or not, of the group G. David's answer requires something akin to an irreducible character. –  Jack Schmidt Jul 22 '10 at 17:21
Dear expmat, This question is still unclear, despite the editing. Let me explain why: if we know the group, we know its group ring, and then (as David explains in his answer) we can decompose the group ring into irreds. and thus determine all the irreps. of $G$. (In practice, this may be computationally infeasible, as Bugs Bunny explains in his answer and the accompanying comments, but you say you don't care about this.) Thus (1) and (4) of your ADDED list are not compatible with (2): knowing the group and not caring about efficieny, in principle we do know all the irreps. of the group! –  Emerton Jul 22 '10 at 17:22
@expmat I'm not completely ignoring you, but your question is awfully vague. Do you not see how to get a basis for the ring $A$? How to write down a multiplication table in this basis? How to use a generic element of $A$ to build $n$ orthogonal idempotents? How to use these idempotents to given an isomorphism between $A$ and the $n \times n$ matrices. –  David Speyer Jul 23 '10 at 9:33
expmat, you can work over K=Q[exp(2πi/|G|)], a "splitting field". It is a finite dimensional extension field of Q, so M_n(K)^G is still a finite dimensional Q-vector space. Every character of G is the character of a K-representation of G, and K-equivalence of K-representations is the same as C-equivalence of K-representations. –  Jack Schmidt Jul 23 '10 at 12:29

Here is a bad algorithm, just to show that this is computationally doable. I don't know what a good algorithm would look like.

Step 1: Isolate the $\chi$ component of the group ring Let $\mathbb{C}[G]$ be the group algebra and $\chi$ the character. Define $\pi = 1/|G| \sum \chi(g) g \in \mathbb{C}[G]$. Observe that $\pi$ is a central idempotent. Set $A=\pi \mathbb{C}[G] \pi$. So $A$ is a finite dimensional $\mathbb{C}$ algebra. We could calculate a basis for $A$ by starting with the spanning set $\{ \pi g \pi \}_{g \in G}$ and discarding duplicates, and we could work out how to multiply in that basis.

Now, from representation theoretic nonsense, we know that $A \cong \mathrm{End}(V)$ where $V$ is the representation we are looking for. Specifically, $\pi g \pi$ corresponds to the matrix in $\mathrm{End}(V)$ by which $g$ acts on $V$. If we could compute this isomorphism, we'd be in great shape.

Step 2: Find an isomorphism with a ring of matrices Choose $X$ a generic element of $A$. Computationally, just choose a random linear combination $\sum t(g) \pi g \pi$. Unless you got unlucky with your choice, $X$ with have distinct eigenvalues when acting on $V$. We will use the eigenvectors for those eigenvalues as a canonical basis for $V$ to write down our representation.

Let $d = \dim V$. Form the powers $1$, $X$, $X^2$, ... $X^d$ and, using basic linear algebra, find the polynomial $\sum a_i X^i=0$ they obey. Since $A$ is isomorphic to the $d \times d$ matrices, such a polynomial will exist. Now, at this point I am going to assume that you have a computer algebra system good enough to work with the roots of an arbitrary complex polynomial. I suspect this might be a problem in practice. Let $\lambda_1$, $\lambda_2$, ..., $\lambda_d$ be these roots. Let $P_i(t)$ be the polynomial $\prod_{j \neq i} (t-\lambda_j)/\prod_{j \neq i} (\lambda_i-\lambda_j)$. So $P_i(\lambda_j)=\delta_{ij}$. Set $\pi_i=P_i(X)$. So the $\pi_i$ are commuting orthogonal idempotents in $A$.

Let $e_{ij}$ be the element of $A$ with $\pi_i e_{ij} = e_{ij} \pi_j = e_{ij}$. The element $e_{ij}$ is unique up to scalar factor, and can be found by linear algebra. Once you get these scalar factors right, which I'll gloss over, you have constructed the isomorphism $A \cong \mathrm{End}(V)$.

Step 3: Profit! Write $\pi g \pi$ in the $e_{ij}$ basis. This is, in coordinates, the action of $g$ on $V$.

-
This is one of my favorite answers on MO. Very nicely written, clear, and the "Profit!" made me laugh quite a bit. –  Steve D Jul 21 '10 at 21:10
Well done, Doc, and well deserved brownie point!! You can improve slightly but starting with another "well-known" representation $V$ instead of the regular representation. One should try a smaller permutation representations $V$ or, more general, an induced representation from a large subgroup. All you need to ensure is that the irreducible character is constituent in the character of $V$. –  Bugs Bunny Jul 21 '10 at 21:21
This is definitely an interesting approach, but I still wonder if it can be expected to yield a (faithful) matrix representation of the Monster group in dimension 196883? Even after the character table of the hypothetical simple group was computed in detail, the existence of the group itself was uncertain for a while. I guess what I'm wondering about is how much information about the group has to be used. Even when the existence of the Monster was unproved, a lot was known about the internal structure it must have. –  Jim Humphreys Jul 21 '10 at 22:03
I am using the full ability to multiply in the group. As Jim points out, you can't construct a group from its character table. –  David Speyer Jul 21 '10 at 22:31
This is what the algorithm known as the "meataxe" is all about. It's an algorithm to do the following: given a finite dimensional matrix algebra (one for which you can generate a random element) and a vector space that it acts on (i.e. a module) it either reports that it is irreducible or finds a proper non-zero submodule. Applying this repeatedly can decompose an algebra into a direct sum of 2 sided ideals. See warwick.ac.uk/~mareg/download/papers/bham_95/bham_95.ps –  Victor Miller Jul 22 '10 at 0:21

If I recall correctly, it's quite possible for two nonisomorphic finite groups to have the same character table. (The dihedral and quaternion groups of order 8 should be an example, but I don't have references at hand.) So you can't expect to recover a group or its representations from a knowledge of characters alone.

ADDED: I'm still somewhat doubtful about the value of the question itself. Classical character theory shows that (in principle) each irreducible complex character determines uniquely an irreducible matrix representation, up to equivalence. As David points out in his answer, there is (in principle) an algorithm for working out this matrix representation in the context of the group algebra, assuming you have complete knowledge of the group and its multiplication table. Plus lots of time, patience, computing power.

In practice, characters have been developed partly to shortcut the need for such algorithms, which are usually impractical for interesting groups like SL$(n,q)$ or other finite groups of Lie type: Lusztig's work over several decades has shown how much can be known about the characters even while many of the key representations remain elusive.

Only in rare cases like symmetric groups do you find a "natural" construction of the representations themselves. And rarely do you know the given group completely enough to carry out David's algorithm based on a given character. If you have that kind of omniscience, it seems you might just construct all the irreducible representations within the group algebra without first knowing the character values.

Computational methods have been most used in recent decades to study the more complicated representation theory of finite groups in prime characteristic when the prime divides the group order. Here even the Brauer characters fail to capture enough information about indecomposable representations, etc.

-
There are functions of $k$ variables on a finite group called $k$-characters (ordinary characters are 1-characters) and the 1, 2, and 3-characters do determine the group up to isomorphism but the 1 and 2-characters do not. See ams.org/mathscinet/search/… –  KConrad Jul 21 '10 at 21:07
The group is fixed (and known). I just want to recover the representation of it. –  expmat Jul 21 '10 at 21:08
The full reference is [Hoehnke, H.-J.; Johnson, K. W. The $1$-, $2$-, and $3$-characters determine a group. Bull. Amer. Math. Soc. (N.S.) 27 (1992), no. 2, 243--245. MR1149873 (93d:20017)] –  Mariano Suárez-Alvarez Jul 21 '10 at 22:11
I believe that if one uses the "make link" button at MathSciNet, the resulting page auto-forwards people who don't have MathSciNet access to a still-useful page. In this case, the link is ams.org/mathscinet-getitem?mr=1149873 –  JBL Jul 21 '10 at 23:37

I assume you are talking about complex finite dimensional representations of finite groups. Philosophically speaking, one should be able to recover a representation from a character but, in practice, it is not clear how to do and may require completely new machinery. For example, the characters of $GL(n,q)$ are given by Green functions and were known 20 years before the representations that require Deligne-Lusztig machinery.

Another example is a big monster. Its characters were known several years before the group was invented. I am not even sure that the representations are known in any useful way.

-
There are algorithms which, when given a finit group, produce the character table. From there, one can construct irreps by decomposing the regular representation, for example. Of course, what you have in mind is a nice description of the irreps... –  Mariano Suárez-Alvarez Jul 21 '10 at 20:05
How do you decompose explicitly? You need to know irreducible idempotents and there are no efficient way of producing them. Look at the big monster: characters are easy but you will not find any computer capable of producing all representations!! –  Bugs Bunny Jul 21 '10 at 20:12
I am not think about the efficiency, really. From the characters you can get projections from the regular rep to its isotypical components, and those can be dcomposed by finding explicitly its endomorphism algebra, which can be done by solving (rather huge!) linear systems. –  Mariano Suárez-Alvarez Jul 21 '10 at 20:17
I am really lost at what you are trying to say. The endomorphism algebra of the regular representation is the group algebra, you don't need any linear system to find it. You need a corresponding irreducible idempotent, as I mentioned earlier, which, indeed, can be found by trying to solve "A HUGE SYSTEM"... –  Bugs Bunny Jul 21 '10 at 20:25
I don't know why everyone is even assuming the goal is an algorithm: from my reading of the question, the author simply wondered whether $\chi_\rho$ (assumed to be a positive linear combination of irreducible characters? that's not clear) determines $\rho.$ The answer, of course, depends on how much we know about $G$ (if we know the multiplication table and the character table and don't care about efficiency, then it's easy). –  Victor Protsak Jul 22 '10 at 6:41

This complements David's response which I can't hope to match :-)

I found Rao's book on Linear Algebra and Group theory for Physicists very useful while pondering on this problem sometime ago. It lists steps somewhat similar to those given by David (don't have the book right now). Given a group G = (X | R), it proceeds to find the center, the central idempotents, the basis of the 2-sided ideals, and finally the irrep. Detailed proofs are given as to how the idempotent leads to the irrep. Every irrep leaves a positive definite Hermitian form invariant as was noted by Moore in Math. Ann. 50 p 213(1898). Rao's book then constructs the Dirac algebra representation by way of example.

Gerhard Hiss's paper documents recent work in computational representation theory. It is quite possible that this problem has already been addressed in GAP

-

expat, as you don't care about nothing, here is a similar (to David's) way of doing it. It will be more efficient. Your group is $G$ and your character is $\chi$. You can work over rationals only if your character is defined over rational and your Schur index is 1. You'd better stick to some $Q(\alpha)$ where $\alpha$ is a root of unity.

(1) Pick the largest Abelian subgroup $H$ of $G$ you know. Restrict $\chi$ to $H$. Let $\pi$ be one dimensional constituent of $\chi_H$.

(2) Consider $V$, the induced representation $\pi^G$. You know it explicitly as the basis consists of cosets of $H$ and all the matrices $\pi^G (x)$ are monomial. Notice that by Frobenius reciprocity, your representations is constituent in $\pi^G$.

(3) Pick a generix linear transformation $T$ of $\pi^G$. Let $S=\sum_{x\in G} \pi^G(x)T\pi^G(x^{-1})$. This fellow is a generic element of $END(\pi^G)$. You want to find some idempotents in $A$, the subalgebra of endomorphisms, generated by $S$, as exactly David did. You have a natural map $k[Z]/(f(Z))\rightarrow A$ where $f(Z)$ is the minimal polynomial of $S$ and you just consider the images of idempotents in $k[Z]/(f(Z))$ that you can find explicitly (see them in David's answer). Let $e_1, \ldots e_m$ be the idempotents in $A$ that you have found.

(4) Decompose $\pi^G$ into direct sum of $V_i = IM(e_i)$ by choosing a basis in the image of each $e_i$. Compute each character $\chi_i$ and find $\chi_i$ with $\chi\bullet\chi_i\neq 0$. Now your representation is a constituent of $V_i$ and you repeat steps 3 and 4 for this $V_i$ to get smaller and smaler representations.

-