2
$\begingroup$

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}$).

$\endgroup$
3
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ thanks so much for the answer! I also don't yet see how to extend it to my setting, but I'm glad you posted this observation since it differs drastically from what I've tried. I'll try to understand what it gives for my question. $\endgroup$ – Alex Golovnev Nov 11 '17 at 2:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.