# Possible ranks of a $n!\times n$ matrix with permuted rows

Let $a_1,\cdots,a_n$ be $n$ arbitrary real numbers. Form the $n! \times n$ matrix $M$ whose rows are obtained by permuting the $n$ numbers given. Find all the possible ranks of such a matrix.

Obviously, the order of listing out these permutation does not affect the rank.

When $n=3$, a possible such $M$ is $$\begin{pmatrix} a_1 & a_2 & a_3 \\ a_1 & a_3 & a_2\\ a_2 & a_3 & a_1 \\ a_2 & a_1 & a_3 \\ a_3 & a_1 & a_2 \\ a_3 & a_2 & a_1\end{pmatrix}$$

For a general $n$, I have proved the existence of ranks with value $0,1,n-1,n$: \eqalign{ & {\text{For }}\operatorname{rank} M = 0,{\text{ put all }}{a_i} = 0 \cr & {\text{For }}\operatorname{rank} M = 1,{\text{ put all }}{a_i} = 1 \cr & {\text{For rank }}M = n - 1,{\text{ put }}{a_1} = {a_2} = ... = {a_{n - 1}} = 1{\text{ and }}{a_n} = - n + 1 \cr & {\text{For rank }}M = n,{\text{ put }}{a_1} = 1{\text{ and all other }}{a_i} = 0 \cr}

All except the third one are trivial observations, to prove the third one, note that when ${a_1} = {a_2} = ... = {a_{n - 1}} = 1{\text{ and }}{a_n} = - n + 1$, the sum of the $n$ columns of $M$ is zero, hence its columns are linear dependent, we have ${\text{rank }}M \leqslant n - 1$.

However, note that the $(n - 1) \times (n - 1)$ matrix $${\left( {\begin{array}{*{20}{c}} { - n + 1}&1& \cdots &1 \\ 1&{ - n + 1}& \cdots &1 \\ \vdots &1& \ddots &1 \\ 1&1&1&{ - n + 1} \end{array}} \right)}$$ is a submatrix of $M$, and by formula for $n \times n$ matrix with $x$ on diagonal and $y$ elsewhere,
$$\left| {\begin{array}{*{20}{c}} x&y& \cdots &y\\ y&x& \cdots &y\\ \vdots &y& \ddots &y\\ y&y&y&x \end{array}} \right| = {(x - y)^{n - 1}}\left[ {x + (n - 1)y} \right]$$ this submatrix is invertible and thus has rank $n-1$. Hence the original $M$ satisfies ${\text{rank }}M \geqslant n - 1$

However, I can't prove or disprove the existence of other values of rank. Even the simplest case when $M$ is a $4! \times 4$, I cannot assert or rule out the existence of $M$ such that ${\text{rank }}M = 2$

There is a similar question in Stackexchange, but it only tells the facts that I had already knew, and does not give any insight.

This is a question from Artin's Algebra so I think this is not very hard. Any help will be greatly appreciated.

You've already listed all the ranks that can be achieved. The row space affords a representation of the symmetric group $S_n$ acting on the row vectors. This representation decomposes into the standard representation and the trivial representation (see e.g. Wikipedia). If you write the top row as $\vec s+\vec t$, with $\vec s$ in the subspace that transforms according to the standard representation and $\vec t$ in the subspace that transforms according to the trivial representation, you have the following options:
• If $\vec s=\vec0$ and $\vec t=0$, the rank is $0$.
• If $\vec s=\vec0$ and $\vec t\ne0$, all permutations reproduce $\vec t$, so the rank is $1$.
• If $\vec s\ne\vec0$ and $\vec t=0$, since the standard representation is irreducible, acting with all permutations on $\vec s$ produces row vectors that span the entire $(n-1)$-dimensional subspace, so the rank is $n-1$.
• If $\vec s\ne\vec0$ and $\vec t\ne0$, the row vectors are of the form $\vec s'+\vec t$, where the $\vec s'$ together span the entire $(n-1)$-dimensional subspace. By acting with the projector onto the $1$-dimensional subspace corresponding to the trivial representation (that is, by forming the average of the rows), we can form $\vec t$ as a linear combination of the rows. This we can then subtract from all rows, yielding the vectors $\vec s'$ that span the $(n-1)$-dimensional subspace. Thus in this case the rank is $n$.