Lemma 1（Giorgi, G., 2020）

定理

以下の線形不等式系のいずれか一方のみが解を持つ。
1. $\lbrace Ax + Bv + Cz = \boldsymbol{0}, v \ge \boldsymbol{0}, z > \boldsymbol{0} \rbrace$
2. $\lbrace y^{T} A = \boldsymbol{0}, y^{T} B \ge \boldsymbol{0}, y^{T} C \gneq \boldsymbol{0} \rbrace$

この定理はTucker's Theorem of the Alternativeと呼ばれる。

方針

2.と同値の線形不等式系を用意し、それを基に考える。

証明

(2.と同値の線形不等式系3.の用意)
次の不等式系を考える。
3. $\lbrace y^{T} A = \boldsymbol{0}, y^{T} B \ge \boldsymbol{0}, y^{T} C \gneq \boldsymbol{0}, y^{T} C u > 0 \rbrace$
どちらかが解を持たないならば、もう片方も解を持たない。
また、解を持つならば、もう片方も同じ解を持つ。
この不等式系には$u>\boldsymbol{0}$という条件が隠れている。

(2.、つまり3.が成立しないなら1.が成立する)
3.が解を持たないならば、$\lbrace y^{T} A = \boldsymbol{0}, y^{T} B \ge \boldsymbol{0}, y^{T} C \ge \boldsymbol{0}, y^{T} C u > 0 \rbrace$も解を持たない。これを変形して得られる、

$\begin{eqnarray*} \lbrace y^{T} A = \boldsymbol{0}, y^{T} (B+C) \ge \boldsymbol{0}, y^{T} (-C u) < 0 \rbrace \end{eqnarray*}$

について議論する。これが解を持たないので二者択一の線形不等式系（6）（Giorgi, G., 2020）より、

$\begin{eqnarray*} \lbrace (B+C)x + Az = -Cu, x \ge \boldsymbol{0} \rbrace = \lbrace Az + Bx +C(x+u) = 0, x \ge \boldsymbol{0} \rbrace \end{eqnarray*}$

は解を持つ。$x+u > \boldsymbol{0}$より1.と一致することから、1.は解を持つ。

(2.が成立するなら1.が成立しない)
$v \ge \boldsymbol{0}, z > \boldsymbol{0}$において、以下となるため1.は成立しない。

$\begin{eqnarray*} 0 = y^{T}(Ax + Bv + Cz) > 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.
Tucker's Theorem
　Mangasarian, Olvi L. Nonlinear programming. Society for Industrial and Applied Mathematics, 1994. p29