What is the rank of the matrix consisting of all permutations of one vector? [duplicate]
Let $a=(a_1,...,a_n)^\top\in\mathbb{R}^n$ be a column vector and let $M_1,...,M_{n!}$ denote all $n\times n$ permutation matrices. When is the rank of the matrix that consists of all possible permutations of $a$: $$ A=[M_1 a \,|\; ... \; |\, M_{n!} a]\in\mathbb{R}^{n\times n!} $$ equal to $n$? Obviously, $rank(A)\le n$ and if all entries of $a$ are identical, then $rank(A)=1$. Moreover, if $A$ has rank $n$, then there exist two entries $i,j$ s.t. $a_i\not=a_j$. Is the converse statement also true?
Solution 1:
The rank takes the following $4$ possible values in the following situations:
- Rank $0$: $a = 0$.
- Rank $1$: the $a_i$ are all equal to some nonzero scalar.
- Rank $n-1$: the $a_i$ sum to $0$, and at least one is not zero.
- Rank $n$: otherwise.
This is not hard to prove directly but can be fit into the general context of representation theory. $\mathbb{R}^n$ is a representation of the symmetric group, and it decomposes as a direct sum of two irreducible representations, namely the trivial representation (spanned by the all-ones vector) and an irreducible representation of dimension $n-1$ (vectors summing to zero). If $v \in \mathbb{R}^n$ is a vector, then
$$\text{span}(gv : g \in S_n)$$
is an invariant subspace of $\mathbb{R}^n$, and so must be a sum of irreducible subrepresentations. Moreover, in this case (although not in general) every such sum occurs. This gives the above.