Equivalent representation of a system of linear (in)equalities

33 Views Asked by At

I am reading about the equivalence between zero-sum games and LPs from Adler's 2012 paper. Right after lemma 3, he writes that it is equivalent to represent $$ (\mathsf{A}) := \{x:Ax=b\} = \{x:Ax\geq b,\;\mathbf{1}^\top Ax\leq \mathbf{1}^\top b\} =: (\mathsf{B}) $$ where $\mathbf{1}=[1,\ldots,1]^\top$. Why is $(\mathsf{A})=(\mathsf{B})$ true? It is clear that $(\mathsf{A})\subseteq(\mathsf{B})$, but why do we have $(\mathsf{A})\supseteq(\mathsf{B})$?

1

There are 1 best solutions below

0
On BEST ANSWER

A friend's answer:

\begin{align} Ax\geq b,\;\mathbf{1}^\top Ax\leq \mathbf{1}^\top b \iff Ax-b \geq0,\;\mathbf{1}^\top(Ax-b)\leq0 \end{align} which means $Ax=b$ since $Ax-b\geq0$ and $\mathbf{1}\geq0$.