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$?



Linear relations among permutation matrices
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. 


