patternMinor
Given matrix $A$, find vector $x$ such that every entry of $Ax$ is nonzero
Viewed 0 times
suchentrynonzeroeverythatfindmatrixgivenvector
Problem
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.
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.
Solution
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 > k$. Suppose, without loss of generality, that $A_{ik} > 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.
$$
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 > k$. Suppose, without loss of generality, that $A_{ik} > 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.
Context
StackExchange Computer Science Q#85405, answer score: 3
Revisions (0)
No revisions yet.