<s>[INST] 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?
 [/INST] 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$.
</s>