Transition Matrices for Young\u27s Representations of the Symmetric Group

The irreducible modules of the symmetric group Sn are indexed by the integer partitions {λ : λ ⊢ n}. In the 1920\u27s, Alfred Young defined representations on these modules according to the action of permutations σ in Sn on the standard Young tableaux of shape λ, denoted SYT(λ). In this paper, we solve an open problem by determining the change-of-basis matrix Aλ between two of these representations — the seminormal representation and the natural representation — by relating the entries of A λ to walks on the graph Γλ, which is the Hasse diagram for weak Bruhat order on SYT(λ). We then describe a recursive rule for computing these entries that puts the computational complexity for determining Aλ on the order of |SYT(λ)|2, and we abstract our formula to the Iwahori-Hecke algebra Hn(q) and the generalized symmetric group Gr,n