13

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?

MathKi
  • 183
  • I think you wanted to write there not exist two entries – user84976 Jul 06 '16 at 08:41
  • 1
    The converse statement surely is not true: if you consider $a=(1,-1)$ then $rk(A)=1$ – user84976 Jul 06 '16 at 08:43
  • 6
    I think this is a duplicate of this earlier question. As I answered that one I refrain from casting a duplicate vote. Also it is not clear which direction the closing should go given that Qiaochu's answer is very nice. – Jyrki Lahtonen Jul 06 '16 at 09:47
  • 1
    @JyrkiLahtonen the old question is more general as it considers arbitrary fields. Thus this one should be closed as dupe. I voted like this. (One might consider a merge. The modification to the answer needed seem minimal.) – quid Jul 06 '16 at 12:29
  • @JyrkiLahtonen: Given the better wording of the other Question and the nice answer here by Qiaochu, this is perhaps a good candidate for merging? – hardmath Jul 06 '16 at 14:02

1 Answers1

22

The rank takes the following $4$ possible values in the following situations:

  1. Rank $0$: $a = 0$.
  2. Rank $1$: the $a_i$ are all equal to some nonzero scalar.
  3. Rank $n-1$: the $a_i$ sum to $0$, and at least one is not zero.
  4. 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.

Qiaochu Yuan
  • 419,620