# How to solve a system of quadratic equations over finite fields?

Hello!

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!

• 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$. Dec 12 '12 at 9:15
• 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.
– 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.