How to show that this $2n \times n^2$ matrix has rank $2n-1$?

Question

The matrix is fairly messy to present, but quite easy to understand. When $n=3$, the matrix is

\begin{bmatrix} 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0\\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0\\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1\\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \end{bmatrix}

So, basically, it splits into two parts:

• the upper part (from row $1$ to row $n$) has $n$ identity matrices $I_n$.

• the lower part is $O_n^1, \ldots, O_n^n$, where each $O_n^i$ is an $n \times n$ matrix whose $i$-th row is all one whereas the other entries are zero.

By some examples and intuition, I am aware that the rank of such a matrix is $2n-1$, but how should I rigorously prove it?

Answer 1

The $2n$th row is the sum of the first $n$ rows minus the sum of rows $n+1$ through $2n-1.$ Thus the rank is at most $2n-1.$

The last $n$ columns in the first $n$ rows and the $0$s in rows $n+1$ through $2n-1$ in the last $n$ columns, show that the only way to make a row of $n^2$ zeros a linear combination of the first $2n-1$ rows is to make the first $n$ coefficients in the linear combination equal to $0.$ But then you can't get $0$s in the first $n^2-n$ columns except by using $0$ as the $(n+1)$th through $(2n-1)$the coefficients. Hence the rows other than the last one are linearly independent.

Answer 2

Let $$ A=\begin{bmatrix} I_n \mid I_n \mid \cdots \mid I_n\\ O^1_n \mid O^2_n \mid \cdots \mid O^n_n\\ \end{bmatrix}. $$ We're looking for the rank of $A$ so we can do row and column reduction.

1. Remove the first block-column from the other block-columns

We get $$ A \sim \begin{bmatrix} I_n \mid 0 \mid \cdots \mid 0\\ O^1_n \mid O^2_n - O^1_n \mid \cdots \mid O^n_n - O^1_n\\ \end{bmatrix}. $$

2. Add the last line to the $n+1$-th line, the before last to the $n+1$-th line, ..., until you get

$$ A \sim \begin{bmatrix} I_n \mid 0 \mid \cdots \mid 0\\ O^1_n \mid O^2_n \mid \cdots \mid O^n_n\\ \end{bmatrix}. $$

3. Remove the first $n$ lines of the $n+1-$th line

We get $$ A \sim \begin{bmatrix} I_n \mid 0 \mid \cdots \mid 0\\ 0 \mid O^2_n \mid \cdots \mid O^n_n\\ \end{bmatrix}. $$

4. For each $O^k_n$ block (with $k \ge 2$) remove the columns following the first one

So we get $$ A \sim \begin{bmatrix} I_n \mid 0 \mid \cdots \mid 0\\ 0 \mid U^2_n \mid \cdots \mid U^n_n\\ \end{bmatrix}. $$ where $U^k_n$ is $n \times n$ matrix with $1$ in the position $(k,1)$ and $0$ elsewhere.

5. Move the first column of $U_n^n$ to the last column of $A$, the first column of $U_n^{n-1}$ to the before last column of $A$, ... (here we're just pushing all the columns to the right).

We can move $I_n$ to the bottom-right (above the previous $1$'s) to finally get $$ A \sim \begin{bmatrix} 0 \mid 0\\ 0 \mid I_{2n-1} \end{bmatrix}. $$

It follows that the rank of $A$ equals $2n-1$.

Answer 3

Things will perhaps be clearer if we write these $2n$ rows from $\Bbb{R}^{n^2}$ as $n \times n$ matrices.

For $n=3$ we are looking at $$\begin{bmatrix} 1 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0\end{bmatrix},\begin{bmatrix} 0 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 0\end{bmatrix},\begin{bmatrix} 0 & 0 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 1\end{bmatrix}, \begin{bmatrix} 1 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0\end{bmatrix},\begin{bmatrix} 0 & 0 & 0 \\ 1 & 1 & 1\\ 0 & 0 & 0\end{bmatrix},\begin{bmatrix} 0 & 0 & 0\\ 0 & 0 & 0 \\ 1 & 1 & 1\end{bmatrix}.$$

Call them $A_1, \ldots, A_{2n}$. We will prove that $\{A_1, \ldots, A_{2n-1}\}$ is linearly inependent and $A_{2n}$ is in its span.

Assume $$0 = \sum_{i=1}^{2n-1}\alpha_iA_i = \begin{bmatrix} \alpha_{1}+\alpha_{n+1} & \alpha_{2}+\alpha_{n+1} & \cdots & \alpha_{n}+\alpha_{n+1} \\ \alpha_{1}+\alpha_{n+2} & \alpha_{2}+\alpha_{n+2} & \cdots & \alpha_{n}+\alpha_{n+2}\\ \vdots & \vdots & \ddots & \vdots \\ \alpha_{1}+\alpha_{2n-1} & \alpha_{2}+\alpha_{2n-1} & \cdots & \alpha_{n}+\alpha_{2n-1}\\ \alpha_{1} & \alpha_{2}& \cdots & \alpha_{n}\end{bmatrix}$$ so first we get $\alpha_1=\cdots=\alpha_n = 0$ and then $\alpha_{n+1}=\cdots=\alpha_{2n-1}=0$.

On the other hand, we have $$A_{2n}= \sum_{i=1}^n A_i - \sum_{i=n+1}^{2n-1}A_i.$$

Therefore $\dim\operatorname{span}\{A_1, \ldots, A_{2n}\} = 2n-1$.

Answer 4

Let $A$ be the $2n \times n^2$ matrix in your question. It is easy to check that $$AA^T = \begin{bmatrix}nI_n & 1_{n \times n} \\ 1_{n \times n} & nI_n \end{bmatrix}$$ where $I_n$ is the $n \times n$ identity matrix and $1_{n \times n}$ is the $n \times n$ matrix of all ones. (To see why this is true, try computing the dot product of each pair of rows of $A$.) Hence, $$AA^T - nI_{2n} = \begin{bmatrix}0_{n \times n} & 1_{n \times n} \\ 1_{n \times n} & 0_{n \times n} \end{bmatrix},$$ which clearly has rank-$2$. By inspection $\begin{bmatrix} 1_{n \times 1} \\ 1_{n\times 1}\end{bmatrix}$ and $\begin{bmatrix} 1_{n \times 1} \\ -1_{n\times 1}\end{bmatrix}$ are eigenvectors of $AA^T-nI_{2n}$ with respective eigenvalues of $n$ and $-n$. Hence, the eigenvalues of $AA^T-nI_{2n}$ are $n$, $-n$, and $0$ (with multiplicity $2n-2$). Therefore, the eigenvalues of $AA^T$ can be found by adding $n$ to each of the eigenvalues of $AA^T-nI_{2n}$, i.e. $2n$, $0$, and $n$ (with multiplicity $2n-2$). Since $AA^T$ is symmetric and has exactly $2n-1$ non-zero eigenvalues, $\text{rank}(AA^T) = 2n-1$. Therefore, $\text{rank}(A) = \text{rank}(AA^T) = 2n-1$ as well.