5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What is your model of computation? You have to be careful when real numbers are involved. $\endgroup$ – Yuval Filmus Dec 12 '17 at 20:52
  • 1
    $\begingroup$ You can always post comments on your own question. The problem is that you have two separate accounts. You can use the "contact" link at the bottom of the page to get them merged and then you'll be able to comment on your post. $\endgroup$ – David Richerby Dec 13 '17 at 1:30
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

Given $\mathrm A \in \mathbb{R}^{n \times n}$ with no zero rows, we would like to find $\mathrm x \in \mathbb{R}^n$ such that every entry of $\rm Ax$ is nonzero. Let $\mathrm b \in \mathbb{R}^n$ be a vector of nonzero parameters. Solving the linear system

$$\rm A x = b$$

we find at least one solution $\rm x_{b}$ for every choice of $\rm b$ that has no zero entries and is in the column space of $\rm A$ (so that the linear system is feasible).

If matrix $\rm A$ happens to have full rank, then the unique solution is $\rm x_b = A^{-1} b$, i.e., a linear combination of the $n$ columns of $\rm A^{-1}$ in which all $n$ coefficients are nonzero.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.