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.
 A: 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.
A: 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^{-1} \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$.
A: 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
A: 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.
A: 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.
A: I found this question because I was looking to do the same thing. The method I had in mind was as follows. (Corrections requested!)


*

*Let $\rho$ be the permutation representation of finite group G.

*Let $\rho^k$ be the $k$-fold tensor product of $\rho$, which corresponds to the diagonal action of $G$ on $k$ copies of itself.

*Recognize the fact that every irreducible character eventually shows up in one of these representations for large enough $k$. (I remember learning this, but I haven't found a reference.)

*For any character $\chi$, the idempotent projection on $\rho^k$ is given by 
$$ \phi_{\chi,k} = \frac{1}{|G|}\sum_{g\in G} \chi(g) \rho^k(g).$$
Use this to build projections for $k = 1, 2, \dots$. Keep going until you get a projection that is non-zero.

*Build the representation as $$ g \mapsto \phi_{\chi, k} \rho^k(g) \phi_{\chi, k}. $$ This will be potentially very large because (a) it is just a low-dimensional projection within a large space and (b) the character could occur with large multiplicity. So then use linear algebra tricks (i.e., I haven't thought this part through) to grab just the active part of the space.


Surely, this will usually be very inefficient, but would this work? Or does it require some assumption, like that $\chi$ be irreducible?
