8
$\begingroup$

Given a permutation $\sigma\in S_n$, let $P_\sigma$ denote the corresponding $n\times n$ permutation matrix. It is easy to see that for $n=3$, there is only one linear relation up to scaling given by $\sum_\sigma sign(\sigma)P_\sigma = 0$. For larger $n$, what are all linear relations $\sum_\sigma c_\sigma P_\sigma=0$?

$\endgroup$
3
  • 1
    $\begingroup$ It may be worth mentioning that the $n\times n$ permutation matrices span a (real) vector space of dimension $(n-1)^2+1$. For $n=3$, that's 6 matrices with a 5-dimensional span, which explains the single linear relation. $\endgroup$ Nov 5, 2015 at 22:59
  • $\begingroup$ @Gerry: yes, this follows from the decomposition given in my answer. $\endgroup$ Nov 5, 2015 at 23:14
  • $\begingroup$ @Qiaochu, yes, but if you are referring to the $(n-1)^2+1$ result, that can be obtained without recourse to representation theory, by methods of introductory Linear Algebra. $\endgroup$ Nov 5, 2015 at 23:25

2 Answers 2

13
$\begingroup$

The standard permutation representation $\mathbb{C}^n$ of $S_n$ breaks up as a direct sum of a trivial representation $1$ and an irreducible representation $V$ of dimension $n - 1$. Hence the natural map $\mathbb{C}[S_n] \to \text{End}(\mathbb{C}^n)$ has image in $\text{End}(1) \oplus \text{End}(V)$. In fact, in terms of the Peter-Weyl decomposition

$$\mathbb{C}[S_n] \cong \bigoplus_V \text{End}(V)$$

where $V$ runs over all complex irreps of $S_n$,the map above is precisely the projection onto the two summands given by $\text{End}(1)$ and $\text{End}(V)$. So the kernel of this projection consists of the summands $\text{End}(W)$ where $W$ is neither trivial nor isomorphic to $V$. Somewhat more explicitly, there is an element of the kernel for each matrix coefficient of $W$. For example, if $\chi_W$ is the character of $W$ then there are linear relations of the form

$$\sum_{\sigma \in S_n} \overline{\chi}_W(\sigma) \sigma = 0$$

and when $n = 3$ this is the only relation, coming from the only irrep of $S_3$ not appearing in $\mathbb{C}^3$, namely the sign rep.

$\endgroup$
5
  • $\begingroup$ For $n=4$ there are 178 independent linear relations. We can also ask for higher order relations (syzygies). More precisely, let $R_n$ be the semigroup algebra (over $\mathbb{R}$, say) of all $n\times n$ matrices of nonnegative integers with equal row and column sums, under addition. Regard $R_n$ as a quotient of the polynomial ring $A_n$ in $n!$ variables, which map to the permutation matrices. Then the Betti numbers of $R_n$ as an $A_n$-module are 1 178 1837 7416 16440 25144 35562 42204 35562 25144 16440 7416 1837 178 1. For $n=5$ the sum of the Betti numbers is $>5.7\times 10^{34}$. $\endgroup$ Nov 5, 2015 at 14:15
  • $\begingroup$ @Richard: I'm a little confused by this statement; it sounds like you're answering a different question. $\endgroup$ Nov 5, 2015 at 18:29
  • 1
    $\begingroup$ Oops, you are right. I am thinking of linear relations $A=B$ which involve only positive coefficients. I consider such a relation to be dependent on others if it is a positive linear combination of these other relations. $\endgroup$ Nov 5, 2015 at 21:21
  • $\begingroup$ I'd be much obliged, Qiaochu, if you could supply some detail on how this applies when (say) $n=4$. $\endgroup$ Nov 5, 2015 at 23:03
  • 1
    $\begingroup$ @Gerry: $S_4$ has five irreps: trivial, sign, the 3d irrep $V$ above, $V$ tensor the sign rep, and another 2d irrep. The space of linear relations has dimension $1^2 + 3^2 + 2^2 = 14$ (alternatively, $24 - 3^2 - 1^2$) and can be given a basis using a basis of matrix coefficients for the sign rep, $V$ tensor the sign rep, and the 2d irrep. $\endgroup$ Nov 5, 2015 at 23:14
1
$\begingroup$

See https://arxiv.org/abs/1804.00916 for an answer in terms of the technology of cellular algebras (due to Graham and Lehrer [Invent. math. 1996]). If I understand the result, it shows that the set of linear relations is a certain cell ideal in the defining cell chain, with respect to Murphy's alternating basis of $\mathbb{C}[S_n]$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.