if $A.x \le b$, when is $x \le A^{-1}.b$?

Question

I have a relation, derived from optimality conditions of a linear program: $$ L \le A.x \le U$$ with:

• $L, U \in \mathbb{R}^{m}$
• $A \in \mathbb{R}^{m \times n}$, with each element $\in \{0,1\}$
• $x \in \mathbb{R}^{n}$

The matrix $A^TA$ is invertible with all eigenvalues $\gt 0$.

Is this last condition sufficient to ensure that the following equation holds: $$ (A^TA)^{-1}A^TL \le x \le (A^TA)^{-1}A^TU$$

Answer 1

Take $m=n=2$, and $$A = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$$ This matrix satisfies your conditions.

Take $$ L = \begin{pmatrix} 0\\ 1 \end{pmatrix} \qquad x =\begin{pmatrix} -2\\ 2 \end{pmatrix} $$ You have $$ L = \begin{pmatrix} 0\\ 1 \end{pmatrix} \leq A x =\begin{pmatrix} 0\\ 2 \end{pmatrix} $$ but $$ A^{-1}L = \begin{pmatrix} -1\\ 1 \end{pmatrix} \nleq x =\begin{pmatrix} -2\\ 2 \end{pmatrix} \, . $$

The answer is no.