5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.