Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Computing irreducible representations of finite groups


Authors: László Babai and Lajos Rónyai
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
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] M. D. Atkinson, The complexity of group algebra computations, Theoret. Comput. Sci. 5 (1977), 205-209. MR 483650 (80a:16020)
  • [2] E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713-735. MR 0276200 (43:1948)
  • [3] M. Ben-Or, Probabilistic algorithms in finite fields, Proc. 22nd IEEE FOCS, 1981, pp. 394-398.
  • [4] T. Beth, On the computational complexity of the general discrete Fourier transform, Theoret. Comput. Sci. 51 (1987), 331-339. MR 909461 (88i:20009)
  • [5] R. Brauer, Applications of induced characters, Amer. J. Math. 69 (1947), 709-716. MR 0022851 (9:268e)
  • [6] C. Brott and J. Neubüser, A programme for the calculation of characters and representations of finite groups, Computational Problems in Abstract Algebra (J. Leech, ed.), Pergamon Press, 1970. MR 0291309 (45:403)
  • [7] R. Brauer and J. Tate, On the characters of finite groups, Ann. of Math. (2) 62 (1955), 1-7. MR 0069825 (16:1087c)
  • [8] W. Burnside, Theory of groups of finite order, 2nd ed., Dover, 1955. MR 0069818 (16:1086c)
  • [9] A. L. Chistov and D. Yu. Grigoryev, Polynomial time factoring of the multivariable polynomials over a global field, LOMI preprint E-5-82, Leningrad, 1982. MR 1082380 (92f:12018)
  • [10] M. Clausen, Fast Fourier transform for metabelian groups, SIAM J. Comput. 18 (1989), 584-593. MR 996838 (90e:94002)
  • [11] -, Fast generalized Fourier transforms, Theoret. Comput. Sci. (to appear). MR 1015084 (91f:68081)
  • [12] C. W. Curtis and I. Reiner, Representation theory of finite groups and associative algebras, Wiley, 1966. MR 1013113 (90g:16001)
  • [13] P. Diaconis, Spectral analysis for ranked data, Ann. Statist. (to appear).
  • [14] -, Group representations in probability and statistics, Inst. of Math. Stat., Hayward, CA, 1988. MR 964069 (90a:60001)
  • [15] P. Diaconis and D. Rockmore, Efficient computation of the Fourier transform on finite groups, manuscript, 1988.
  • [16] J. D. Dixon, High speed computation of group characters, Numer. Math. 10 (1967), 446-450. MR 0224726 (37:325)
  • [17] -, Computing irreducible representations of groups, Math. Comp. 24 (1970), 707-712. MR 0280611 (43:6330)
  • [18] W. Eberly, Computations for algebras and group representations, Ph.D. Thesis, Department of Computer Science, University of Toronto, 1989.
  • [19] W. Feit, Characters of finite groups, Benjamin, 1967. MR 0219636 (36:2715)
  • [20] K. Friedl and L. Rónyai, Polynomial time solutions of some problems in computational algebra, Proc. 17th ACM Sympos. on Theory of Computing, 1985, pp. 153-162.
  • [21] S. Landau, Factoring polynomials over algebraic number fields, SIAM J. Comput. 14 (1985), 184-195. MR 774938 (86d:11102)
  • [22] A. K. Lenstra, Factoring polynomials over algebraic number fields, Proc. EUROCAL, Lecture Notes in Comput. Sci., vol. 162, Springer, 1983, pp. 245-254. MR 774816 (86g:12001b)
  • [23] A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), 515-534. MR 682664 (84a:12002)
  • [24] R. S. Pierce, Associative algebras, Graduate Texts in Math., vol. 88, Springer, 1982. MR 674652 (84c:16001)
  • [25] L. Rónyai, Simple algebras are difficult, Proc. 19th ACM Sympos. on Theory of Computing, 1987, pp. 398-408.
  • [26] -, Zero divisors in quaternion algebras, J. Algorithms 9 (1988), 494-506. MR 970191 (90f:11102)
  • [27] -, Computing the structure of finite algebras, J. Symb. Comput. 9 (1990), 355-373. MR 1056632 (91h:68093)
  • [28] J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, J. Assoc. Comput. Mach. 27 (1980), 701-717. MR 594695 (82m:68078)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 68Q40, 11R33, 20C40

Retrieve articles in all journals with MSC: 68Q40, 11R33, 20C40


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1990-1035925-1
Article copyright: © Copyright 1990 American Mathematical Society

American Mathematical Society