Given matrix $A$, find vector $x$ such that every entry of $Ax$ is nonzero Given a matrix $A \in \mathbb{R}^{n \times n}$ with no zero rows, what is the complexity of deterministically finding a vector $x \in \mathbb{R}^n$ such that every entry of $Ax$ is nonzero? 


It is easy to see that a vector whose entries are realizations of Gaussian random variables works. Indeed, in this case every entry of $Ax$ is a realization of a continuous Gaussian random variable and, hence, is nonzero with probability $1$. Thus, the probability that all entries of $Ax$ are nonzero is $1$.  Thus if "generate a Gaussian" (or any other continuous random variable) is an allowed operation, then this takes $O(n)$ operations. 

In the deterministic case, you probably need at least $O(n^2)$ operations since every entry of the matrix $A$ probably needs to be read. I'm wondering if you could do it in $O(n^2)$ or, if not, what the best time that you can do this in is.

Edit: I don't seem to have enough reputation to post comments on my own question. In any case, let us suppose that the entries of $A$ are all rational, and we are looking for a vector $x$ with rational entries.
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.