  Recently, Dvir, Golovnev, and Weinstein have shown that sufficiently strong
lower bounds for linear data structures would imply new bounds for rigid
matrices. However, their result utilizes an algorithm that requires an $NP$
oracle, and hence, the rigid matrices are not explicit. In this work, we derive
an equivalence between rigidity and the systematic linear model of data
structures. For the $n$-dimensional inner product problem with $m$ queries, we
prove that lower bounds on the query time imply rigidity lower bounds for the
query set itself. In particular, an explicit lower bound of
$\omega\left(\frac{n}{r}\log m\right)$ for $r$ redundant storage bits would
yield better rigidity parameters than the best bounds due to Alon, Panigrahy,
and Yekhanin. We also prove a converse result, showing that rigid matrices
directly correspond to hard query sets for the systematic linear model. As an
application, we prove that the set of vectors obtained from rank one binary
matrices is rigid with parameters matching the known results for explicit sets.
This implies that the vector-matrix-vector problem requires query time
$\Omega(n^{3/2}/r)$ for redundancy $r \geq \sqrt{n}$ in the systematic linear
model, improving a result of Chakraborty, Kamma, and Larsen. Finally, we prove
a cell probe lower bound for the vector-matrix-vector problem in the high error
regime, improving a result of Chattopadhyay, Kouck\'{y}, Loff, and
Mukhopadhyay.
