Let $m$ be an odd positive integer. Let $r$ be the smallest extension order of finite field $GF(q)$ that the $m$-th roots of unity are in $GF(q^r)$. For instance, it can be assumed that $q = 2$.

Let $\mathbf{d}_i$, $1 \le i \le m$ be unknown $k$-dim vectors over $GF(q)$. Let $G$ be given $k \times l$ matrix over $GF(q)$. Let $\mathbf{y}$ be unknown $l$-dim vector over $GF(q^r)$. Let $H$ be $s \times m$ matrix over $GF(q^r)$ of full rank over $GF(q^r)$.

I have to find unknown non-zero vectors $\mathbf{d}_i$, $1 \le i \le m$ and $\mathbf{y}$ so the following equation vanishes: $(\mathbf{d}_1^T G \mathbf{y}, \mathbf{d}_2^T G \mathbf{y}, \ldots, \mathbf{d}_m^T G \mathbf{y}) H^T = 0$. How it can be done?

Thank you very much!

  • $\begingroup$ If you write your vectors $d_i$ as the rows of a matrix $D$, then unless I misread something your problem is to find, given matrices $G$ and $H$, a vector $y$ and a matrix $D$ such that $$HDGy=0.$$ I guess you want $D,y$ nonzero? Or do you want all such $D,y$. $\endgroup$ Dec 12 '12 at 9:15
  • $\begingroup$ THanks for your reply! You are quite right, I want to find $D$ and $\mathbf{y}$ being non-zero. I have updated the question with this constraint. $\endgroup$
    – ddd
    Dec 12 '12 at 9:27

As others have noticed, this reduces to the problem of finding a non-zero $m\times k$ matrix $D$ such that $HDG$ has a non-trivial kernel.

If $l\ge 2$, you can take all the $\mathbf{d}_i$ equal but nonzero, so that $D$ has rank $1$ and $HDG$ has rank at most $1$, and $HDG$ has a non-trivial kernel.

If $l=1$, the problem is equivalent to $HDG=0$, which can be solved by linear algebra.


So, it sounds like the problem can be reduced to:

Given matrices $H,G$, find a non-zero $m \times k$ matrix $D$ such that the $s \times l$ matrix $HDG$ has a non-trivial kernel.

Of course, once you find such a matrix $D$, it is easy to find a non-zero vector $y$ that is in its kernel (by linear algebra), so the task is to find such a $D$.

If $s \le l$, this problem is probably easy. If you pick $D$ randomly, then with non-trivial (some constant $> 0$) probability, $HDG$ will have non-trivial kernel, and you can quickly test whether this is the case, so you will only need to try a constant number of random matrices $D$.

If $s > l$, I don't know if there is a better solution.


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.