Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The following is a special case of my earlier question which is still not solved.

Suppose both $\mathbf{a_i}$ and $\mathbf{v}$ are $1\times N$ vectors over a finite field $\mathbb{F_q}$, where $i\in \{1,2,\ldots\,K\}$. $\mathbf{a_i}$ are very sparse, i.e. there are only two or three non-zero entries in each $\mathbf{a_i}$. Now, I have $K$ inequations $\mathbf{a_i}\cdot\mathbf{v}\neq 0$.

What is the necessary and sufficient condition that there exists at one such $\mathbf{v}$ that make the $K$ inequations hold simultaneously? Thanks.

share|improve this question
1  
It's very bad style to post this question without linking to your earlier question of which it's a special case. Are you not aware that this will cause lots of people to duplicate effort that's already been spent on answering the other question? –  joriki Nov 3 '11 at 8:40
    
I am very sorry for that. This new question is not directly obtained from my previous question. So, I even didn't notice this is actually a special case of my previous question. Thanks for warning me. –  Leon Nov 3 '11 at 8:52
    
In that case, I apologize for the italics, I've removed my downvote, and I suggest that you review the basics of matrix products and dot products again before you start applying them to finite fields. –  joriki Nov 3 '11 at 8:58
    
It's okay. Thanks for your advice. I'll review them carefully. –  Leon Nov 3 '11 at 9:50
1  
I think it's usual in English to reserve "inequality" for expressions like $a>b$ or $a \geq b$. Expressions like $a \neq b$ are inequations. –  Chris Eagle Nov 3 '11 at 11:38
show 3 more comments

3 Answers 3

up vote 1 down vote accepted

There is a solution to this system of inequalities if and only if the product $\prod_i\mathbf a_i\cdot\mathbf v$ is not equivalent to the zero polynomial. This polynomial can have up to $|\mathbb F_q|^N$ different coefficients, so computing it will in general not be more efficient than testing every possible value of $\mathbf v$, but if the $\mathbf a_i$ have few components, or you can transform to a basis in which they have few components, it may be.

share|improve this answer
    
In the special case $K<q$ this is efficiently solvable with a randomized algorithm due to the Schwartz-Zippel lemma –  Tim Seguine Dec 5 '12 at 18:28
add comment

A counting argument gives the following sufficient condition. I write it up as an answer, because I first stated it incorrectly in a comment (I had confused the roles of $N$ and $K$).

Obviously we must assume that $a_i\neq(0,0,\ldots,0)$ for all $i$. The inequation $a_i\cdot v\neq0$ rules out as potential solutions the points $v$ of the hyperplane determined by the equation $a_i\cdot v=0$. This hyperplane is actually a subspace of dimension $N-1$, so it has $q^{N-1}$ points. The point $v=(0,0,\ldots,0)$ is in all those subspaces, so the union of $K$ such subspaces has at most $1+K\cdot (q^{N-1}-1)$ points. Thus something will be left over, if $1+K\cdot (q^{N-1}-1)<q^N$. This holds whenever $K\le q$, so we get a sufficient condition for the existence of a solution: 1) $a_i\neq(0,0,\ldots,0)$ for all $i$, and 2) $K\le q$. This condition is by no means necessary.

share|improve this answer
    
In general the bound $K\le q$ is the best possible in the following sense. If $$F_q=\{x_1,x_2,\ldots,x_q\},$$ then the choices $a_i=(1,0,0,\ldots,x_i)$, $1\le i\le q$, and $a_{q+1}=(0,0,\ldots,0,1)$ do not admit any solutions to the system of inequations. Therefore we cannot guarantee that a solution exists, if $K=q+1$. –  Jyrki Lahtonen Nov 3 '11 at 15:06
    
If $K>q$ and $\mathbf{a_i}$ are given, is it possible to determine whether a solution exists? –  Leon Nov 3 '11 at 16:13
    
@Leon: I don't see anything more efficient than joriki's suggestion. BTW, with my example of $q+1$ unsolvable inequations the polynomial he describes is $x_1x_N(x_1^{q-1}-x_N^{q-1})$, which clearly vanishes everywhere. –  Jyrki Lahtonen Nov 3 '11 at 20:34
add comment

Since very little is known about the $\mathbf{a}_i$ except that they are sparse, it is not clear that a necessary and sufficient condition can be specified at all.

If the $\mathbf{a}_i$ are very sparse, say with exactly two nonzero entries each, and if the nonzero entries are equally likely to be chosen independently with probability $(q-1)^{-1}$ from the nonzero elements of $\mathbb{F}_q$, then the probability that $\mathbf{v} = (1, 1, \ldots, 1)$ satisfies the $K$ inequations is $(1 - (q-1)^{-1})^K$ which might be good enough if $q$ is large and $K$ is small.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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