Vector with no zero entries in the column space over a finite field

Question

I am interested in the problem that was introduced here

Spanning a vector with no zero coordinates

which is the following:

Given a matrix $A \in (\mathbb{F}_p)^{m \times n}$, is there an efficient method to find a vector in its column space which does not have any 0 entries (or prove that one doesn't exist)?

The answer given in the above post shows that for every characteristic $p > 0$, there is a counterexample matrix to such a vector existing, but I would like to know of a procedure to find one such vector, or show that one cannot exist.

If it helps, I am specifically interested in $p = 3$.

Answer 1

The other answer is correct regarding the NP-completeness of Syndrome decoding, which is about finding a vector with a nonzero lower bound on the Hamming weight in the nullspace of an appropriate matrix. Actually, the original proof for $p=2$ was given in

E. R. Berlekamp, R. J. McEliece, and H. C. van Tilborg, “On the inherent intractability of certain coding problems,” IEEE Transactions on Information Theory, vol. 24, no. 3, May 1978

This was generalized to arbitrary fields by Alexander Barg (there may be an English translation of this paper)

S. Barg. Some new NP-complete coding problems. *Problemy Peredachi Informatsii^, 30(3):23–28, 1994.

The generalized case addresses your question.

Answer 2

The paper S. C. Ntafos, S. L. Hakimi, On the Complexity of Some Coding Problems, IEEE Trans. Inform. Theory IT-27:6 (Nov. 1981), states that the problem of checking whether there is a binary vector $x$ with at least $w>0$ nonzero coordinates such that $xB = 0$ for a given matrix $B$ is, in general, NP-complete.

By standard linear algebra this is easily reduced to your problem for $p = 2$.