"Dividing" both sides of an inequality by a vector

Question

As ridiculous as the question sounds, I'm just referring to a very specific case. Suppose that I'm given two $n \times 1$ vectors $x$ and $c$, an $m \times n$ matrix $A$ and a $m \times 1$ vector $y$, and the following inequality:

$$c^Tx \geq y^TAx$$

If $x \geq 0$ (all its components are $\geq 0$), intuitively it seems to follow that $c^T \geq y^TA$ and hence that $c \geq A^Ty$. It's incorrect to say that we "multiply both sides by $x^{-1}$" because there's no notion of the inverse of a column vector as such. Is there any rigorous justification for:

$$c^Tx \geq y^TAx \implies c^T \geq y^TA$$

provided that $x$ is non-negative (or for reversing the above inequality if $x$ is negative)?

(Clarification: By $a \geq b$, where $a, b \in \mathbb{R}^n$, I mean that $a_i \geq b_i$ for all $i = 1, 2, \ldots, n$.)

Answer 1

If all the terms of (column) vectors $\mathbf x,\mathbf y$ are non-negative, $\mathbf y^T\mathbf x$ is non-negative.

It is not true, however, that if all the terms of $\mathbf x$ are non-negative, and $\mathbf y^T\mathbf x\geq 0$ that all the terms of $y$ are non-negative.

For example, $$\begin{align}\mathbf x&=\begin{pmatrix}1\\1\end{pmatrix},\\\mathbf y&=\begin{pmatrix}2\\-1\end{pmatrix}.\end{align}$$ o] So you can't cancel $x$ from $y^Tx\geq \mathbf 0^T x,$ for example.

Basically, you are saying that if $x\geq 0$ (for some definition of $\geq$) and $(c^T-y^TA)x\geq 0$ then $c^T-y^TA\geq 0,$ which is not true.

---

A Visualization

The sign of $\mathbf y^T\mathbf x$ is the same as the sign of the cosine of the angle between the two. So $\mathbf y^T \mathbf x\geq 0$ means the angle is less than $\frac{\pi}{2}.$

Also, $\mathbf x\geq 0$ just means that $x$ is in the non-negative quadrant, octant, etc., depending on the dimension.

But any $\mathbf x$ in that quadrant has a $\mathbf y$ such that $\mathbf y^T\mathbf x>0$ and $\mathbf y$ is not in the same quadrant (octant, etc.)

Answer 2

$c^T x \geq y^T A x \Leftrightarrow vx =(c^T-y^TA)x \geq 0$.

So, we need to investigate when $vx = 0$ and when $vx > 0$.

The first case is simple enough, as either $x = 0$ (which is not always the case) or we must require $v = 0$ so that $c^T = y^T A$.

For the second case, we can use the geometric definition that $vx = |v|\cdot|x|\cdot cos(\theta) > 0$ whenever $-\pi/2 <\theta < \pi/2$. To visualize, if $x$ is a vector, we can imagine some $n-1$-dimensional "plane" which $x$ is perpendicular to. Then $vx$ is positive when $v$ points to the same side of the "plane" as $x$. If each component of $x$ is non-negative but not all $0$, then $x$ lies in the first orthant (generalized quadrant). So, if $v$ is also in the first orthant and $v\neq0$, then $vx$ will be positive. However, it's clear that there are other $v$ which don't lie in the first orthant but are still on the same side of the "plane" as $x$ is.

To see this, draw an $xy$-plane, and draw an arrow from the origin into the first quadrant, called $x$. Then, the "plane" is the line through the origin which is perpendicular to $x$. Finally, any vector $v$ which starts in the origin and stays on the same side of that line as $x$ will have $vx > 0$.

Excuse the crudeness of the drawing:

Answer 3

A somewhat more quantitative answer:

When $x$ is normalized, we can apply the triangle inequality to find that $$|(a-b)^{T}e_{i}-(a-b)^{T}x|=|(a-b)^{T}(e_{i}-x)|\leq \|a-b\|\sqrt{2(1-x^{T}e_{i})},$$ so $$(a-b)^{T}e_{i}\in (a-b)^{T}x\pm\|a-b\|\sqrt{2(1-x^{T}e_{i})},$$ which means that we have tighter control over the components $(a-b)^{T}e_{i}$ where $x$ and $e_{i}$ are close, as we would expect from intuition. In this sense, the worst case would be the constant vector $x=[1/\sqrt{n}]_{i=1}^{n},$ since this is equally far from all of the $e_{i}$'s.

This also lets us see explicitly the tradeoff in information: since $\sum_{i=1}^{n}|x^{T}e_{i}|^{2}=1,$ when $1-x^{T}e_{i}$ decreases, all of the $x^{T}e_{j},\,j\neq i$ must decrease, so $1-x^{T}e_{j}$ increases for all $j\neq i$.