by $\supp(v) = \{ i \in [d]\,|\, v_i \neq 0 \}$ (this notation is extended to matrices as well). For a set of $n$ points $V \subset \C^d$ and an integer $\ell$, we denote by $V^\ell \subset \C^{d\ell}$ its $\ell$-fold Cartesian product i.e. $V^\ell=V\times V\times \cdots \times V\ (\ell\ \mathrm{times})$ where we naturally identify $\C^d\times \C^d\times \cdots \times \C^d\ (\ell\ \mathrm{times})$ with $\C^{d\ell}$.

Design matrices {#sec-design-matrices}
---------------

Design matrices, defined in [@BDWY12], are matrices that satisfy a certain condition on their support.

\[def-designmatrix\] Let $A$ be an $m \times n$ matrix over a field $\F$. Let $R_1,\ldots,R_m \in \F^n$ be the rows of $A$ and let $C_1,\ldots,C_n \in \F^m$ be the columns of $A$. We say that $A$ is a [*$(q,k,t)$-design matrix*]{} if

1.  For all $i \in [m]$, $|\supp(R_i)| \leq q$.

2.  For all $j \in [n]$, $|\supp(C_j)| \geq k$.

3.  For all $j_1 \neq j_2 \in [n]$, $|\supp(C_{j_1}) \cap \supp(C_{j_2}) | \leq t$.

Surprisingly, one can derive a general bound on the rank of complex design matrices, despite having no information on the values present at the non zero positions of the matrix. The first bound of this form was given in [@BDWY12] which was improved in [@DSW12].

