\[thm-rankbound\] Let $A$ be an $m \times n$ matrix with entries in $\C$. If $A$ is a $(q,k,t)$ design matrix then the following two bounds hold $$\begin{aligned}
\rank(A) \geq n - \frac{ntq^2}{k}.\label{eq-rank1}\\
\rank(A) \geq n - \frac{mtq^2}{k^2}.\label{eq-rank2}\end{aligned}$$

The Veronese embedding {#sec-veronese-embedding}
----------------------

We denote by $$\m(d,r) = \binom{d+r}{d}$$ the number of monomials of degree at most $r$ in $d$ variables. We will often use the lower bound $\m(d,r) \geq (r/d)^d$. The Veronese embedding $\phi_{d,r} : \C^d \mapsto \C^{\m(d,r)}$ sends a point $a = (a_1,\ldots,a_d) \in \C^d$ to the vector of evaluations of all monomials of degree at most $r$ at the point $a$. For example, the map $\phi_{2,2}$ sends $(a_1,a_2)$ to $(1,a_1,a_2,a_1^2,a_1a_2,a_2^2)$. We can identify each point $w \in \C^{\m(d,r)}$ with a polynomial $f_w \in \C[x_1,\ldots,x_d]$ of degree at most $r$ in an obvious manner so that the value $f_w(a)$ at a point $a \in \C^d$ is given by the standard inner product ${\langle w,\phi_{d,r}(a) \rangle}$. We will use the following two easy claims.

\[cla-veronese-vanish\] Let $V \subset \C^d$ and let $U = \phi_{d,r}(V) \subset \C^{\m(d,r)}$. Then $U$ is contained in a hyperplane iff there is a non-zero polynomial $f \in \C[x_1,\ldots,x_d]$ of degree at most $r$ that vanishes on 