Assume

. We have to prove the existence of a subset

of

of cardinality at most

such that

.

For every

, choose a linear map

such that

(some projection on a complement subspace, for instance). Finally, let us introduce the linear map

given by

. Its kernel is

due to the assumption, hence

is injective, and its image has dimension

. Consider a matrix of

, consisting in piling up the matrices of

(

); then we can find

independent rows. Let

be the subspaces corresponding to these rows (

if two rows come from the same "submatrix"). The map

has rank

by the previous choice, hence its kernel (i.e.

) is

. This concludes.