The computational complexity of rules for the character table of S_n.

DOI10.1016/J.JSC.2003.11.001MaRDI QIDQ2643536zbMATH OpenOpenAlexFDO

Authors Dan Bernstein

Publication date 24 August 2007

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0309225

zbMATH Keywords

algorithmsYoung diagramsYoung tableauxHecke algebrascharacter tablesMurnaghan-Nakayama rulecomputational complexitiesKazhdan-Lusztig characters

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Analysis of algorithms (68W40) Combinatorial aspects of representation theory (05E10) Hecke algebras and their representations (20C08) Representations of finite symmetric groups (20C30)

Abstract: The Murnaghan-Nakayama rule is the classical formula for computing the character table of S_n. Y. Roichman has recently discovered a rule for the Kazhdan-Lusztig characters of q-Hecke algebras of type A, which can also be used for the character table of S_n. For each of the two rules, we give an algorithm for computing entries in the character table of S_n. We then analyze the computational complexity of the two algorithms, and in the case of characters indexed by partitions in the (k,l)-hook, compare their complexities to each other. It turns out that the algorithm based on the Murnaghan-Nakayama rule requires far less operations than the other algorithm. We note the algorithms' complexities' relation to two enumeration problems of Young diagrams and Young tableaux.

Recommendations

• A \(q\)-rational Murnaghan-Nakayama rule
• Murnaghan-Nakayama Rules for Characters of Iwahori-Hecke Algebras of the Complex Reflection Groups G(r, p, n)
• An algoritm for calculating characters of hecke algebrasH_n(q) of typeA_n-1whenqis a root of unity
• A rational-function identity related to the Murnaghan-Nakayama formula for the characters of \(S_ n\)
• A proof of the Murnaghan-Nakayama rule using Specht modules and tableau combinatorics

Cites work

• scientific article; zbMATH DE number 3983158 (Why is no real title available?)
• scientific article; zbMATH DE number 51129 (Why is no real title available?)
• scientific article; zbMATH DE number 601020 (Why is no real title available?)
• scientific article; zbMATH DE number 1405492 (Why is no real title available?)
• scientific article; zbMATH DE number 3099472 (Why is no real title available?)
• A recursive rule for Kazhdan-Lusztig characters
• Maximal degrees for Young diagrams in the \((k,l)\) hook
• On hooks of Young diagrams
• Representations of Coxeter groups and Hecke algebras
• The Characters of the Symmetric Group

Cited in

(6)

• The number of steps in the Robinson-Schensted algorithm
• Generating weighted Hurwitz numbers
• Involutions and the Gelfand character
• RTNI—A symbolic integrator for Haar-random tensor networks
• On the number of \(\lambda\)-unimodal involutions
• On permutation statistics and Hecke algebra characters

This page was built for publication: The computational complexity of rules for the character table of \(S_n\).

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2643536)