Computing irreducible representations of finite groups

The bit complexity of computing irreducible representations of finite groups is considered. Exact computations in algebraic number fields are performed symbolically. A polynomial-time algorithm for finding a complete set of inequivalent irreducible representations over the field of complex numbers of a finite group given by its multiplication table is presented. It follows that some representative of each equivalence class of irreducible representations admits a polynomial-size description. The problem of decomposing a given representation V of the finite group G over an algebraic number field F into absolutely irreducible constituents is considered. It is shown that this can be done in deterministic polynomial time if V is given by the list of matrices {V(g); g∈G} and in randomized (Las Vegas) polynomial time under the more concise input {V(g); g∈S}, where S is a set of generators of G