论文标题
对称组的表示在多项式时间内可分解
Representations of the symmetric group are decomposable in polynomial time
论文作者
论文摘要
我们将一种算法引入了对称组的正交矩阵表示，而将真实分解为不可减至的表示，作为副产品的副产品还计算了不可减至表示的多重性。 $ s_n $的算法适用于$ s_n $的$ d $维表示，其复杂性为$ o（n^2 d^3）$操作，用于确定存在哪些不可减至的表示形式及其相应的多重性，以及其他$ o（n d^4）$操作，以完全分解非trivivial ultivial ulivial ul-trivial pultivical ul-trivial fultial ul-trivial fultial cultivical univial univial undial corultical useplociation。这些复杂性界限是悲观的，在使用浮点算术和利用稀疏性的实际实现中，我们观察到了更好的复杂性。我们在计算两种不可减至表示的张量产物（Kronecker系数问题）以及高阶张量张量产品的多重性问题上证明了这种算法。对于挂钩和类似钩状的不可减至表示，算法随着$ n $的增加而具有多项式复杂性。我们还展示了构建多元正交多项式相对于张量产品重量的应用程序的应用，以便应用变量的置换会引起不可约的表示。
We introduce an algorithm to decompose orthogonal matrix representations of the symmetric group over the reals into irreducible representations, which as a by-product also computes the multiplicities of the irreducible representations. The algorithm applied to a $d$-dimensional representation of $S_n$ is shown to have a complexity of $O(n^2 d^3)$ operations for determining which irreducible representations are present and their corresponding multiplicities and a further $O(n d^4)$ operations to fully decompose representations with non-trivial multiplicities. These complexity bounds are pessimistic and in a practical implementation using floating point arithmetic 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 multivariate orthogonal polynomials with respect to a tensor product weight so that applying a permutation of variables induces an irreducible representation.
