How to show that this $2n \times n^2$ matrix has rank $2n-1$? 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?
 A: 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.
A: 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.

*

*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}.
$$


*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}.
$$


*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}.
$$


*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.


*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$.
A: 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$.
A: 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.
