## Computing irreducible representations of finite groups

HTML articles powered by AMS MathViewer

- by László Babai and Lajos Rónyai PDF
- Math. Comp.
**55**(1990), 705-722 Request permission

## Abstract:

We consider the bit-complexity of the problem stated in the title. Exact computations in algebraic number fields are performed symbolically. We present a polynomial-time algorithm to find a complete set of nonequivalent irreducible representations over the field of complex numbers of a finite group given by its multiplication table. In particular, it follows that some representative of each equivalence class of irreducible representations admits a polynomial-size description. We also consider the problem of decomposing a given representation $\mathcal {V}$ of the finite group*G*over an algebraic number field

*F*into absolutely irreducible constituents. We are able to do this in deterministic polynomial time if $\mathcal {V}$ is given by the list of matrices $\{ \mathcal {V}(g);g \in G\}$; and in randomized (Las Vegas) polynomial time under the more concise input $\{ \mathcal {V}(g);g \in S\}$, where

*S*is a set of generators of

*G*.

## References

- M. D. Atkinson,
*The complexity of group algebra computations*, Theoret. Comput. Sci.**5**(1977/78), no. 2, 205–209. MR**483650**, DOI 10.1016/0304-3975(77)90007-X - E. R. Berlekamp,
*Factoring polynomials over large finite fields*, Math. Comp.**24**(1970), 713–735. MR**276200**, DOI 10.1090/S0025-5718-1970-0276200-X
M. Ben-Or, - Thomas Beth,
*On the computational complexity of the general discrete Fourier transform*, Theoret. Comput. Sci.**51**(1987), no. 3, 331–339. MR**909461**, DOI 10.1016/0304-3975(87)90041-7 - Richard Brauer,
*Applications of induced characters*, Amer. J. Math.**69**(1947), 709–716. MR**22851**, DOI 10.2307/2371795 - C. Brott and J. Neubüser,
*A programme for the calculation of characters and representations of finite groups*, Computational problems in abstract algebra (Proc. Conf., Oxford, 1967) Pergamon, Oxford, 1970, pp. 101–110. MR**0291309** - Richard Brauer and John Tate,
*On the characters of finite groups*, Ann. of Math. (2)**62**(1955), 1–7. MR**69825**, DOI 10.2307/2007097 - W. Burnside,
*Theory of groups of finite order*, Dover Publications, Inc., New York, 1955. 2d ed. MR**0069818** - A. L. Chistov,
*Calculation of the Galois group over a function field of characteristic zero with an algebraically closed constant field in polynomial time*, Mathematical methods for constructing and analyzing algorithms (Russian), “Nauka” Leningrad. Otdel., Leningrad, 1990, pp. 200–232, 237 (Russian). MR**1082380** - Michael Clausen,
*Fast Fourier transforms for metabelian groups*, SIAM J. Comput.**18**(1989), no. 3, 584–593. MR**996838**, DOI 10.1137/0218040 - Michael Clausen,
*Fast generalized Fourier transforms*, Theoret. Comput. Sci.**67**(1989), no. 1, 55–63. MR**1015084**, DOI 10.1016/0304-3975(89)90021-2 - Charles W. Curtis and Irving Reiner,
*Representation theory of finite groups and associative algebras*, Wiley Classics Library, John Wiley & Sons, Inc., New York, 1988. Reprint of the 1962 original; A Wiley-Interscience Publication. MR**1013113**
P. Diaconis, - Persi Diaconis,
*Group representations in probability and statistics*, Institute of Mathematical Statistics Lecture Notes—Monograph Series, vol. 11, Institute of Mathematical Statistics, Hayward, CA, 1988. MR**964069**
P. Diaconis and D. Rockmore, - John D. Dixon,
*High speed computation of group characters*, Numer. Math.**10**(1967), 446–450. MR**224726**, DOI 10.1007/BF02162877 - John D. Dixon,
*Computing irreducible representations of groups*, Math. Comp.**24**(1970), 707–712. MR**280611**, DOI 10.1090/S0025-5718-1970-0280611-6
W. Eberly, - Walter Feit,
*Characters of finite groups*, W. A. Benjamin, Inc., New York-Amsterdam, 1967. MR**0219636**
K. Friedl and L. Rónyai, - Susan Landau,
*Factoring polynomials over algebraic number fields*, SIAM J. Comput.**14**(1985), no. 1, 184–195. MR**774938**, DOI 10.1137/0214015 - A. K. Lenstra,
*Factoring multivariate integral polynomials*, Theoret. Comput. Sci.**34**(1984), no. 1-2, 207–213. MR**774045**, DOI 10.1016/0304-3975(84)90117-8 - A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász,
*Factoring polynomials with rational coefficients*, Math. Ann.**261**(1982), no. 4, 515–534. MR**682664**, DOI 10.1007/BF01457454 - Richard S. Pierce,
*Associative algebras*, Studies in the History of Modern Science, vol. 9, Springer-Verlag, New York-Berlin, 1982. MR**674652**
L. Rónyai, - Lajos Rónyai,
*Zero divisors in quaternion algebras*, J. Algorithms**9**(1988), no. 4, 494–506. MR**970191**, DOI 10.1016/0196-6774(88)90014-4 - Lajos Rónyai,
*Computing the structure of finite algebras*, J. Symbolic Comput.**9**(1990), no. 3, 355–373. MR**1056632**, DOI 10.1016/S0747-7171(08)80017-X - J. T. Schwartz,
*Fast probabilistic algorithms for verification of polynomial identities*, J. Assoc. Comput. Mach.**27**(1980), no. 4, 701–717. MR**594695**, DOI 10.1145/322217.322225

*Probabilistic algorithms in finite fields*, Proc. 22nd IEEE FOCS, 1981, pp. 394-398.

*Spectral analysis for ranked data*, Ann. Statist. (to appear).

*Efficient computation of the Fourier transform on finite groups*, manuscript, 1988.

*Computations for algebras and group representations*, Ph.D. Thesis, Department of Computer Science, University of Toronto, 1989.

*Polynomial time solutions of some problems in computational algebra*, Proc. 17th ACM Sympos. on Theory of Computing, 1985, pp. 153-162.

*Simple algebras are difficult*, Proc. 19th ACM Sympos. on Theory of Computing, 1987, pp. 398-408.

## Additional Information

- © Copyright 1990 American Mathematical Society
- Journal: Math. Comp.
**55**(1990), 705-722 - MSC: Primary 68Q40; Secondary 11R33, 20C40
- DOI: https://doi.org/10.1090/S0025-5718-1990-1035925-1
- MathSciNet review: 1035925