# Vector space of matrices of rank $\le r$

Let $F$ be a field, and $M_{n\times n}(F)$ be the set of $n\times n$ matrices with entries in $F$.
Let $V$ be a subspace of $M_{n\times n}(F)$ where every matrix in $V$ has rank at most $r$.
Prove that $\dim V\le nr$.

This is a puzzle I found on the internet which I am having trouble solving. I suppose I am not even sure if the result is correct, but it seems so. It is easy to come up with subspaces of dimension $nr$, like the set of matrices where all but $r$ columns are zero, but these examples are all tight.

I have been able to find literature on subspaces of matrices of rank $\ge r$, but not of rank $\le r$. I would appreciate any hints, references, or even solutions which require $F=\mathbb R$ or $\mathbb C$.

Here is a failed attempt that might serve for inspiration:

Let $t=\dim V$, and assume $t=nr+1$. By using Gaussian elimination, we can find a basis $A^1,\dots,A^t$ for $V$ such that for each $1\le k\le t$, there exists a position $(i(k),j(k))$ where $A^k_{i(t),j(t)}=1$, while $A^\ell_{i(t),j(t)}=0$ for all $\ell\neq k$. These positions are the "leading ones" found by Gaussian elimination, and when choosing a matrix in $V$, the entries in these positions can be chosen independently of each other.

Since there are $nr+1$ leading ones, there exists $r+1$ leading ones which are in pairwise different rows and columns (this follows from a pigeonhole argument). I was hoping to leverage this to show how to that the $(r+1)\times(r+1)$ sub-matrix where these rows and columns intersect could be chosen to have rank $r+1$ by an appropriate choice of the leading ones. This fails, because there is no control over the other entries in the sub-matrix, and they can get in the way.

Many thanks!

Theorem: Let $r\leq n\leq m$ be positive integers, let $\Bbb F$ be a field with at least $r+1$ elements, and let $V$ be a subspace of $\mathcal{M}_{m\times n}(\Bbb F)$ where each element has rank at most $r$. Then $$\dim V\leq nr.$$
The extra condition "with at least $r+1$ elements" can actually be omitted, according to R. Meshulam, On the maximal rank in a subspace of matrices, The Quarterly Journal of Mathematics, 1985.