6

I'm new here and couldn't find a similar question, so pardon me if it's already asked elsewhere. The question is literally simple: Suppose A is a positive definite matrix , could it be generally proved that the set $S=\left \{ x\in R^{n} |x>0,Ax>0 \right \}$ is nonempty? The inequalities are strict and by $x>0$, I mean $x_{i}>0$ for $i=1,2,...,n$.

Honestly speaking, I haven't had any mentionable progress on the analytical side, except trying different types of decompostions (Cholesky, Spectral, etc ...) to no avail. so I tried solving this linear program for different choices of $A\succ 0$ using Matlab so that I could find a counterexample, without success.

$$min w=\mathbf{1}^Ty+\mathbf{1}^Tz$$ $$s.t. \left\{\begin{matrix}x=\mathbf{1}+y\\Ax=\mathbf{1}+z \\ x,y,z\geq 0\end{matrix}\right.$$

where $\mathbf{1}=(1,1,...,1)^{T}$

I'd really appreciate if you would guide me on how could it be proven or negated.

Iman E
  • 75

1 Answers1

3

I would like to use Gordan's theorem: Exactly one of the systems is solvable:

  1. $x^TM>0$
  2. $My=0$, $y\ge0$, $y\ne0$

You want to have the existence of $x$ such that $$ \begin{pmatrix} A \\ I_n \end{pmatrix}x >0. $$ In order to show that, we have to argue that $$ \begin{pmatrix} A^T & I_n \end{pmatrix} y=0, \ y\ge0, \ y\ne0 $$ is unsolvable. Suppose $y$ is such a solution. Then we have $$ y = - A^T y \ge0. $$ Since $A$ is positive definite, and $y\ne0$, $$ 0<y^TAy = - y^Ty<0, $$ which is a contradiction. Thus, such a $y$ cannot exist, which proves the existence of $x$ satisfying 1.

daw
  • 49,113
  • 2
  • 38
  • 76