Given matrix $A$, find vector $x$ such that every entry of $Ax$ is nonzero
Define
$$
M = 1 + \frac{\max_{ij} |A_{ij}|}{\min'_{ij} |A_{ij}|},
$$
where the minimum is taken over all non-zero entries. Then the vector $x$ given by $x_j = M^{j-1}$ satisfies your condition.

Indeed, consider some row $A_{i\cdot}$, and suppose that $A_{ik} \neq 0$ but $A_{i\ell} = 0$ for all $\ell &gt; k$. Suppose, without loss of generality, that $A_{ik} &gt; 0$ and that $\min'_{ij} |A_{ij}| = 1$. Then
$$
(Ax)_i = \sum_{j=1}^k A_{ij} M^{j-1} \geq M^{k-1} - (M-1) \sum_{j=1}^{k-1} M^{j-1} = 1.
$$

Whether the encoding of $x$ is small enough depends on your exact computation model.