# Decomposition of rectangular matrices into a product of a sparse and a small matrices

I would like to construct a rectangular matrix which doesn't have a decomposition into a product of a sparse and a small matrices. It is easy to see that a random matrix doesn't have such a representation, but I'd like to find an explicit example.

More precisely, I want to find an explicit matrix $M\in\mathbb{F}^{n^{100}\times n}$ over a finite field $\mathbb{F}$, such that $M$ can't be represented as a product $A \times B$, where the matrix $A\in\mathbb{F}^{n^{100} \times n^2}$ has only constant number of non-zero elements per row (no constraints on $B\in\mathbb{F}^{n^2\times n}$).

I do not know yet how to solve your question, but there is a similar question with the same difficulty that allows a nice solution. Note that you are basically asking whether we can efficiently find a set of cardinality $n^{100}$ in a huge abelian group that cannot be covered by the sum of constant number of copies of a set of cardinality $n^2$. Assume now that our huge abelian group is $\mathbb Z_p$ instead of $\mathbb F^n$. Then, given $n$, we can do the following explicit construction of a set $A$ of cardinality $2n$ that cannot be covered by any set of the form $B+B+\dots+B$ ($K$ times) with $B\subset \mathbb Z_p$, $|B|=n$ assuming that $p>P(n,K)$.
The key observation is that for every set $B$ of cardinality $n$, and any $Q$, we can find $q\le Q^n$ such that $qB\in[-p/Q,p/Q]$ (Dirichlet simultaneous approximation lemma). Then we will have $q(B+\dots+B)\subset [-Kp/Q, Kp/Q]$. Now just take $A=\{[p/(R+1)],[p/(R+2)],\dots,[p/(R+2n)]\}$ with $Q^{2/3}<R<Q/2K$. Then every $q<Q^N$ is not divisible by at least one of $R+i$ ($i=1,\dots,2n$), so the corresponding $qa$ will be at the distance at least $p/(R+n)-Q^n\gg Kp/Q$ from the origin.
Adjusting this argument to your setting will require some notion of a "small" vector in $\mathbb F^n$, a not too large set of linear operators that can make any $n^2$ vectors small simultaneously and a simple reason why it cannot happen to some $n^{100}$ vectors. As I said, I do not see immediately how to manage this, but I still decided to post this curious (IMHO) observation (which should be classical, of course).