# Permutation of coordinates: how many linearly independent vectors will this generate?

Let $$V$$ be a vector space and $$\dim V=n$$. Under a basis, the vector $$\mathbf v$$ is represented by the coordinate $$(a_1,a_2,\ldots, a_n)$$. Let $$S_n$$ be the group of all permutations on the set $$\{1,2\ldots, n\}$$ represented by matrices. $$S_n\subseteq M_n(\mathbb R)$$.

Let's form the set $$P_\mathbf v=S_n\mathbf v=\{M\mathbf v:M\in S_n\}.$$

I try to investigate the dimension of $$\text{span }P_\mathbf v$$. It appears to me that a maximal subset of independent vectors in $$P_\mathbf v$$ can either be very large ($$n$$ vectors) or very small (one vector), but not something in between.

What are the possible dimensions of $$\text{span }P_\mathbf v$$?

• This must have something to do with decomposing the representation of the symmetric group into irreducibles. – Giuseppe Negro Oct 15 at 6:46

The symmetric group of order $$n!$$ acting as permutation matrices on an n-dimensional vector space (non-modular characteristic) is well-known to have irreducible decomposition given by the trivial representation $$1 = \mathrm{span}\{(1, \ldots, 1)\}$$ and the $$(n-1)$$-dimensional "standard representation" $$S$$. In any case, your $$P_v$$ is a subrepresentation, so the only possibilities are $$P_v \in \{0, 1, S, 1 \oplus S\}$$. Correspondingly, the possible dimensions are $$0, 1, n-1, n$$.
The first two possibilities are realized by $$v=0, v=(1, \ldots, 1)$$. You can project onto $$1$$ by applying the averaging ("Reynolds") operator $$\frac{1}{n!} \sum_{\sigma \in S_n} \sigma$$, which says you get $$1$$ as a component of $$P_v$$ if and only if the average of your entries is non-zero. Hence $$v=(1, 2, \ldots, n)$$ gives you $$1 \oplus S$$, while $$v=(1, -1, 0, \ldots, 0)$$ gives you $$S$$.
• Very interesting. Can I ask you an embarrassingly naive question? I know that a "representation" is a homomorphism of a group into $GL(V)$. When you say, for example, "the trivial representation $1=\text{span} (1, \ldots, 1)$", where is the homomorphism? – Giuseppe Negro Oct 15 at 8:35
• What is "Standard representation" $S$? – Jethro Oct 15 at 11:47
• @GiuseppeNegro: There are two perspectives on representations: (1) a homomorphism $G \to \mathrm{GL}(V)$, and (2) $V$ can be thought of as a $kG$-module, where $kG$ is the group algebra of $G$ and $k$ is $V$'s field of scalars. Here I was using $V = \mathrm{span}\{(1, \ldots, 1)\}$ where $\sigma \in S_n$ acts trivially, $\sigma \cdot v = v$ for all $v \in V$. Thus, each $\sigma$ acts on $V$ as the identity, so the homomorphism is literally trivial. – J Swanson Oct 15 at 22:25
• @Jethro: the standard representation is by definition this one, i.e. permutation matrices acting on the quotient $k^n/\mathrm{span}\{(1, \ldots, 1)\}$. The "hard part" of my answer would be verifying the standard representation is irreducible. Reversing this answer is one elementary approach. – J Swanson Oct 15 at 22:33
• @JSwanson: Oh, this is very interesting for me, I had never grasped this alternative point of view. I now see that "an irreducible representation" is exactly an irreducible submodule of $V$. Thank you very much. – Giuseppe Negro Oct 16 at 11:23