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$?
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$– Gerry MyersonCommented Nov 5, 2015 at 22:59
-
$\begingroup$ @Gerry: yes, this follows from the decomposition given in my answer. $\endgroup$– Qiaochu YuanCommented 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$– Gerry MyersonCommented Nov 5, 2015 at 23:25
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
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.
answered Nov 5, 2015 at 8:00
-
$\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$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented Nov 5, 2015 at 23:14
$\begingroup$
$\endgroup$
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]$.
