Recovering representation from its character - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T21:56:42Z http://mathoverflow.net/feeds/question/32836 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/32836/recovering-representation-from-its-character Recovering representation from its character expmat 2010-07-21T19:38:00Z 2010-07-23T07:04:45Z <p>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?</p> <p>This is clearly possible if we know all the irreducible representations of the group. But what if we don't know them?</p> <p>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.</p> http://mathoverflow.net/questions/32836/recovering-representation-from-its-character/32838#32838 Answer by Bugs Bunny for Recovering representation from its character Bugs Bunny 2010-07-21T20:04:06Z 2010-07-21T20:04:06Z <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/32836/recovering-representation-from-its-character/32844#32844 Answer by Jim Humphreys for Recovering representation from its character Jim Humphreys 2010-07-21T21:01:26Z 2010-07-22T11:22:17Z <p>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.</p> <p>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. </p> <p>In practice, characters have been developed partly to shortcut the need for such algorithms, which are usually impractical for interesting groups like SL<code>$(n,q)$</code> 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. </p> <p>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. </p> <p>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.</p> http://mathoverflow.net/questions/32836/recovering-representation-from-its-character/32846#32846 Answer by David Speyer for Recovering representation from its character David Speyer 2010-07-21T21:04:58Z 2010-07-21T21:04:58Z <p>Here is a bad algorithm, just to show that this is computationally doable. I don't know what a good algorithm would look like.</p> <p><strong>Step 1: Isolate the $\chi$ component of the group ring</strong> 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.</p> <p>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.</p> <p><strong>Step 2: Find an isomorphism with a ring of matrices</strong> 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. </p> <p>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$.</p> <p>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)$. </p> <p><strong>Step 3: Profit!</strong> Write $\pi g \pi$ in the $e_{ij}$ basis. This is, in coordinates, the action of $g$ on $V$.</p> http://mathoverflow.net/questions/32836/recovering-representation-from-its-character/32858#32858 Answer by SandeepJ for Recovering representation from its character SandeepJ 2010-07-21T22:50:11Z 2010-07-21T22:50:11Z <p>This complements David's response which I can't hope to match :-)</p> <p>I found Rao's book on <a href="http://www.amazon.com/Algebra-Physicists-Readings-Physical-Sciences/dp/818593164X" rel="nofollow">Linear Algebra and Group theory for Physicists</a> very useful while pondering on this problem sometime ago. It lists steps somewhat similar to those given by David (<em>don't have the book right now</em>). 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 <a href="http://resolver.sub.uni-goettingen.de/purl?GDZPPN002256762" rel="nofollow">Moore in Math. Ann. 50 p 213(1898)</a>. Rao's book then constructs the <a href="http://en.wikipedia.org/wiki/Dirac_algebra" rel="nofollow">Dirac algebra</a> representation by way of example.</p> <p><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.84.3685" rel="nofollow">Gerhard Hiss's paper</a> documents recent work in computational representation theory. It is quite possible that this problem has already been addressed in <a href="http://www.gap-system.org/" rel="nofollow">GAP</a></p> http://mathoverflow.net/questions/32836/recovering-representation-from-its-character/33059#33059 Answer by Bugs Bunny for Recovering representation from its character Bugs Bunny 2010-07-23T07:04:45Z 2010-07-23T07:04:45Z <p>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.</p> <p>(1) Pick the largest Abelian subgroup $H$ of $G$ you know. Restrict $\chi$ to $H$. Let $\pi$ be one dimensional constituent of $\chi_H$.</p> <p>(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$.</p> <p>(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. </p> <p>(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.</p>