Q.
Let $u=\left(u_{1}, u_{2}, \ldots, u_{n}\right)$ be a fixed non-zero vector in $\mathbb{R}^{n}$ such that $u_{1}+u_{2}+\cdots+u_{n}=0$, and let $A$ be the $n ! \times n$ matrix whose rows are the $n$ ! permutations of $u$. Show that $\operatorname{rank}(A)=n-1$.
My approach:
Here $U=(u_1,…, u_n) $ and $A$ be the permutation matrix whose rows are the n! Permutations of $U$.
Here, $U=\left(u_{1}, u_{1}, \ldots . u_{n}\right)$.
$\pi:\left{u_{1}, \ldots, u_{n}\right} \rightarrow\left{u_{1}, \ldots u_{n}\right} .
$π$: $\left(\begin{array}{lll}u_{1} & u_{2} & u_{n} \\ u_{2} & u_{3} & u_{1}\end{array}\right)$
$A=\left(\begin{array}{c}e_{π_{1}} \\ e_{π_{2}} \\ \vdots \\ e_{π_{n}}\end{array}\right)$
$=\left(\begin{array}{c}e_{2} \\ e_{3} \\ \vdots \\ e_{1}\end{array}\right)$
$=\left(\begin{array}{lllllll}0 & 1 & 0 & 0 & \cdots & \cdots & \cdots \\ 0 & 0 & 1 & 0 & \cdots & \cdots & \cdots \\ 0 & 0 & 0 & 1 & \cdots & \cdots \\ \vdots & & & & & \cdots & \\ 1 & 0 & \cdots & & & \cdots & \end{array}\right)_{n ! \times n .}$
Here how can i use that $u_1+…+u_n=0$ and how can i show that rank of $A$ is $(n-1) $ ?
Best Answer
The rows belong to hyperplane with equation $x_1+\cdots+x_n=0$, so the rank of $A$ is at most $n-1$.
Since $u$ is not null but $u_1+\cdots+u_n=0$, so $u$ has two different coordinates, $u_i \ne u_j$. By considering the differences of the two vectors $u \circ \pi^{-1}$ and $u \circ \pi^{-1} \circ \tau^{-1}$, where $\pi$ is any permutation sending $(i,j)$ on $(k,k+1)$ and $\tau$ the transposition exchanging $k$ and $k+1$, you check that each vector $e_{k+1}-e_k, 1 \le k \le n-1$ (where $(e_1,\ldots,e_n)$ denotes the canonical basis) is spanned by the rows of the matrix $A$, so the rank of $A$ is at least $n-1$.
We are done.
Below is an attempt to extract an $n \times n$ matrix with rank $n-1$. partial answer. The matrix $A$ is $n! \times n$. The sum of the $n$ columns is null, so the rank is at most $n-1$.
Consider the circulant array $$B = \left( \begin{array}{cccc} u_1 & u_n & \cdots & u_2 \\ u_2 & u_1 & \ddots & u_3 \\ \vdots & \ddots & \ddots & \vdots \\ u_n & u_{n-1} & \cdots & u_1 \end{array} \right).$$ This array is $u_1I + u_2C + \cdots + u_nC^{n-1}$, where $C$ is a permutation matrix $$C = \left( \begin{array}{ccccc} 0 & \cdots & \cdots & 0 & 1 \\ 1 & \ddots & \ddots & \ddots & 0 \\ 0 & \ddots & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & \vdots \\ 0 & \cdots & 0 & 1 & 0 \end{array} \right).$$
Since the eigenvalues of $C$ are the $n$-th roots of unity, the eigenvalues of $B$ are $u_1 + u_2\zeta + \cdots + u_n\zeta^{n-1}$ where $\zeta$ ranges over the $n$-th roots of unity. When $\zeta=1$, you get the eigenvalue $0$. It suffices to check that the other eigenvalues are not $0$.
This may be false for particular choice of $(u_1,\ldots,u_n)$ but my impression is that some permutation $(u_\pi(1),\ldots,u_\pi(n))$ will work since $u_1,\ldots,u_n$ are not all the same.