Key Theorem（Giorgi, G., 2020）

Linear Inequality
定理

$x \in \mathbb{R}^{n}, y \in \mathbb{R}^{n}, A \in \mathbb{R}^{m \times n}$を用いた不等式系

\begin{eqnarray*} Ax \ge \boldsymbol{0} \quad y^T A = \boldsymbol{0}, \quad y \ge \boldsymbol{0} \end{eqnarray*}

は、$Ax^{*} + y^{*} > \boldsymbol{0}$を満たす解$(x^{*}, y^{*})$を持つ。

証明

題意の線型不等式系が解を持つための必要十分条件は、Theorem 3（Giorgi, G., 2020）より、その対となる線形不等式系が解を持たないことである。そのため、その線形不等式系が解を持たないことを示す。

まず題意の線型不等式系は次の様に記述できる。

\begin{eqnarray*} \begin{cases} A^T y &=& \boldsymbol{0} \\ -Ax &\le& \boldsymbol{0} \\ -Ax - Iy &<& \boldsymbol{0} \\ y &\ge& \boldsymbol{0} \end{cases} \end{eqnarray*}

その対となる問題は、Theorem 3（Giorgi, G., 2020）により、以下の様に記述される。

\begin{eqnarray*} \begin{cases} z_{2}^{T} A + z_{3}^{T} A &=& \boldsymbol{0}, \\ z_{1}^{T} A^{T} - z_{3}^{T} &\ge& \boldsymbol{0}, \\ z_{1} \in \mathbb{R}^{n}, z_{2} \ge \boldsymbol{0}, z_{3} \ge \boldsymbol{0}, z_{3} \neq \boldsymbol{0} \end{cases} \end{eqnarray*}

この線型不等式系より、

\begin{eqnarray*} 0 = (z_{2} + z_{3})^{T} A z_{1} \ge (z_{2} + z_{3})^{T} z_{3} \geq z_3^{T} z_3 > 0. \end{eqnarray*}

となるため、この系を満たす解は存在しない。よって示された。

参考文献

Giorgi, G. "All linear theorems of the alternative have a common father. An addendum to a paper of CT Perng." Fundamental Journal of Mathematics and Mathematical Sciences 13 (2020): 43-78.