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!


According to H. Flanders, On Spaces of Linear Transformations with Bounded Rank, Journal of the London Mathematical Society, 1962

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.

  • $\begingroup$ Perfect answer, thank you! $\endgroup$
    – zeta zero
    Apr 23 '18 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.