Extremal Collections of $k$-Uniform Vectors

Abstract

We show any matrix of rank $r$ over ${\mathbb{F}}_q$ can have $\le \left(\genfrac{}{}{0ex}{}{r}{k}\right)(q-1{)}^k$ distinct columns of weight $k$ if $k\le O_q(\sqrt{\log r})$ (up to divisibility issues), and $\le \left(\genfrac{}{}{0ex}{}{r}{k}\right)(q-1{)}^{r-k}$ distinct columns of co-weight $k$ if $k\le O_q(r^{2/3})$. This shows the natural examples consisting of only $r$ rows are optimal for both, and the proofs will recover some form of uniqueness of these examples in all cases.

14 pages, major corrections to Theorem 1.6 and Corollary 3.7