Not Solved - Proof of Inequality $x^Ty+y^Tz-x^Tz\le 1$

Question

Let $x, y, z$ are three $n\times 1$ vectors. For each vector, every element is between 0 and 1, and the sum of all elements in each vector is 1. Now I am wonder why the following inquality holds:

$x^Ty+y^Tz-x^Tz\le 1$

My Attempt: I try to rewrite the LHS of this inequality as

$|x^Ty+(y-x)^Tz|\le |x^T\cdot 1|+\| y-x\|_1\|z\|_{\max} \le 1+\| y-x\|_1 \times 1 $

However, this bound looks a bit larger than 1. Any suggestions are appreciated.

Answer 1

Hint: Show that for real numbers $ a, b, c \in [0, 1 ]$, we have

$$ b ( a + c ) - ac \leq b. $$

The expression is linear in each variable, so we just have to check the 8 end points.

Corollary: $ (x^T + z^T) y - x^T z \leq 1^T y = 1$.

Answer 2

Note that your conditions imply $x \cdot x \le1$ for every $x$. From $(x-y) \cdot (x-y) \ge0$ expand to get

$$2x\cdot y \le x\cdot x + y\cdot y\le2 \Rightarrow x\cdot y \le 1$$

Your inequality follows immediately