Decomposing Monomial Representations of Solvable Groups

We present an efficient algorithm that decomposes a monomial representation of a solvable groupG into its irreducible components. In contradistinction to other approaches, we also compute the decomposition matrixA in the form of a product of highly structured, sparse matrices. This factorization provides a fast algorithm for the multiplication with A. In the special case of a regular representation, we hence obtain a fast Fourier transform forG . Our algorithm is based on a constructive representation theory that we develop. The term “constructive" signifies that concrete matrix representations are considered and manipulated, rather than equivalence classes of representations as it is done in approaches that are based on characters. Thus, we present well-known theorems in a constructively refined form and derive new results on decomposition matrices of representations. Our decomposition algorithm has been implemented in the GAP share package AREP. One application of the algorithm is the automatic generation of fast algorithms for discrete linear signal transforms.