Let $A \in k^{m \times n}$ be a matrix over the finite field $k$. Assume that we know that there is some $x = (x_1 \ldots x_n)^T \in k^n$ in the column space of $A$ such that $x_i \neq 0$ for all $i = 1,\ldots,n$. But we do not know the values $x_i$.
What is the complexity of finding an instance of such $x$ (which one is irrelevant)? If we knew the values $x_1,\ldots,x_n \in k$, then the complexity is that of solving the linear equation system $Ay = x$.
Edit: Maybe there is some connection to linear codes and finding an instance of a code with maximal weight. But I am not familiar with those things.