Representations of the symmetric group are decomposable in polynomial time
File(s)
Accepted version
Author(s)
Olver, Sheehan
Type
Journal Article
Abstract
We introduce an algorithm to decompose matrix representations of the symmetric group
over the reals into irreducible representations, which as a by-product also computes the mul tiplicities of the irreducible representations. The algorithm applied to a d-dimensional repre sentation of Sn is shown to have a complexity of O(n
2d
3
) operations for determining which
irreducible representations are present and their corresponding multiplicities and a further
O(nd4
) operations to fully decompose representations with non-trivial multiplicities. These
complexity bounds are pessimistic and in a practical implementation using floating point arith metic and exploiting sparsity we observe better complexity. We demonstrate this algorithm on
the problem of computing multiplicities of two tensor products of irreducible representations
(the Kronecker coefficients problem) as well as higher order tensor products. For hook and
hook-like irreducible representations the algorithm has polynomial complexity as n increases.
We also demonstrate an application to constructing a basis of homogeneous polynomials so
that applying a permutation of variables induces an irreducible representation.
over the reals into irreducible representations, which as a by-product also computes the mul tiplicities of the irreducible representations. The algorithm applied to a d-dimensional repre sentation of Sn is shown to have a complexity of O(n
2d
3
) operations for determining which
irreducible representations are present and their corresponding multiplicities and a further
O(nd4
) operations to fully decompose representations with non-trivial multiplicities. These
complexity bounds are pessimistic and in a practical implementation using floating point arith metic and exploiting sparsity we observe better complexity. We demonstrate this algorithm on
the problem of computing multiplicities of two tensor products of irreducible representations
(the Kronecker coefficients problem) as well as higher order tensor products. For hook and
hook-like irreducible representations the algorithm has polynomial complexity as n increases.
We also demonstrate an application to constructing a basis of homogeneous polynomials so
that applying a permutation of variables induces an irreducible representation.
Date Acceptance
2024-11-06
Citation
Foundations of Computational Mathematics
ISSN
1615-3375
Publisher
Springer
Journal / Book Title
Foundations of Computational Mathematics
Copyright Statement
Subject to copyright. This paper is embargoed until publication. Once published the Version of Record (VoR) will be available on immediate open access.
License URL
Publication Status
Accepted
Rights Embargo Date
10000-01-01