Theorem 3（Giorgi, G., 2020）

Linear Inequality
定理

まず以下の変数や記法を定義する。
・通し番号の集合を分割する２種類の集合$\lbrace M_{i} \rbrace_{i=1}^{p}, \lbrace N_{j} \rbrace_{j=1}^{q}$：

\begin{eqnarray*} \bigcup_{i=1}^p M_{i} &= \lbrace 1, 2, \dots, m \rbrace \\ \bigcup_{j=1}^q N_{j} &= \lbrace 1, 2, \dots, n \rbrace \end{eqnarray*}

・行列$A \in \mathbb{R}^{m \times n}$、その$(i,j)$要素を$a_{i,j}$とする。またブロック行列を$A_{i,j} = (a_{k,r}), \quad k \in M_i, \quad r \in N_j$とする。
・ベクトル$b,y \in \mathbb{R}^{p}, \quad x \in \mathbb{R}^{q}$：

\begin{eqnarray*} b^i = (b_k), \quad k &\in M_i \\ y^i = (y_k), \quad k &\in M_i \\ x^j = (x_r), \quad r &\in N_j \\ \end{eqnarray*}

・$\le$：$b \le y$ はベクトルの各要素について、$\le$ が成立している。
・$\lneq$：$b \lneq y$ はベクトルの各要素について、$\le$ が成立するが、$b=y$は成立しない。

このとき、以下に記す同値条件（１.$\iff$２.）が成立する。
１. 次の線形不等式系が解$x$を持つ。

\begin{eqnarray*} \begin{cases} A_{1,1}x^{1} + A_{1,2}x^2 + A_{1,3}x^3 + \sum_{j=4}^{q} A_{1,j}x^j &=& b^1, \\ A_{2,1}x^{1} + A_{2,2}x^2 + A_{2,3}x^3 + \sum_{j=4}^{q} A_{2,j}x^j &\le& b^2, \\ A_{3,1}x^{1} + A_{3,2}x^2 + A_{3,3}x^3 + \sum_{j=4}^{q} A_{3,j}x^j &<& b^3, \\ A_{i,1}x^{1} + A_{i,2}x^2 + A_{i,3}x^3 + \sum_{j=4}^{q} A_{i,j}x^j &\lneq& b^i, \quad (i = 4, \dots, p), \\ x^1 \text{ : arbitrary}, \quad x^2 \ge \boldsymbol{0}, \quad x^3 > \boldsymbol{0}, \quad x^j \gneq \boldsymbol{0}, \quad j = 4, \dots, q, \end{cases} \end{eqnarray*}

２.ある条件が成立する際、次の線形不等式系は解$y$を持たない。

\begin{eqnarray*} \begin{cases} &y_{1}^{T} A_{1,1} &+ \sum_{i=1}^{p} y_{i}^{T} A_{i,1} &= \boldsymbol{0},\\ E_{j} \equiv &y_{1}^{T} A_{1,j} &+ \sum_{i=2}^{p} y_{i}^{T} A_{i,j} &\ge \boldsymbol{0}, \quad j = 2, \dots, q, \\ y^{T} b \equiv &y_{1}^{T} b^{1} &+ \sum_{i=2}^{p} y_{i}^{T} b^{i} &\le \boldsymbol{0}, \\ &y_{1} \in \mathbb{R}^{|M_{1}|},&\quad y_{i} \ge \boldsymbol{0}, \quad i = 2, \dots, p \end{cases} \end{eqnarray*}

ある条件とは、次のいずれかが満たされることを指す。
・ $y^{T} b < \boldsymbol{0}$
・ $y_{3} \gneq \boldsymbol{0}$
・ $y_{i} > \boldsymbol{0}, \quad \exists i \in \lbrace 4, \dots, p \rbrace$
・ $E_{3} \gneq \boldsymbol{0}$
・ $E_{i} > \boldsymbol{0}, \quad \exists i \in \lbrace 4, \dots, p \rbrace$

証明

(1.の線形不等式を同値な線形等式に書き換え)
スラック変数$w$を用いて、1.を次の線形等式問題に書き換える。

\begin{eqnarray*} \begin{aligned} \begin{bmatrix} A_{1,1} \\ A_{2,1} \\ A_{3,1} \\ \vdots \\ A_{p,1} \end{bmatrix} x^{1} + \begin{bmatrix} A_{1,2} \quad \boldsymbol{0} \\ A_{2,2} \quad I \\ A_{3,2} \quad \boldsymbol{0} \\ \vdots \quad \vdots \\ A_{p,2} \quad \boldsymbol{0} \end{bmatrix} \begin{bmatrix} x^{2} \\ w_2 \end{bmatrix} + \begin{bmatrix} A_{1,3} \quad \boldsymbol{0} \\ A_{2,3} \quad \boldsymbol{0} \\ A_{3,3} \quad I \\ \vdots \quad \vdots \\ A_{p,3} \quad \boldsymbol{0} \end{bmatrix} \begin{bmatrix} x^{3} \\ w \end{bmatrix} +\Sigma_{i = 1}^q \begin{bmatrix} A_{1,i} \\ A_{2,i} \\ A_{3,i} \\ \vdots \\ A_{p,i} \end{bmatrix} x^{i} + \Sigma_{j=1}^{p} \begin{bmatrix} \boldsymbol{0} \\ \vdots \\ \boldsymbol{0} \\ I \\ \boldsymbol{0} \\ \vdots \\ \boldsymbol{0} \end{bmatrix} w_j = \boldsymbol{b} \end{aligned} \end{eqnarray*}

$x^{1} \text{ : arbitrary}, \quad (x^{2}, w_2)^{T} \ge \boldsymbol{0}, \quad (x^{3}, w_3)^{T} > \boldsymbol{0}, \quad x^{i} \gneq \boldsymbol{0} \quad i = 4, \dots, q, \quad w_j \gneq \boldsymbol{0} \quad j = 4, \dots, p$とする。ここで$w_i$の表記を変えるために$x$を用いて表して$x^{i+q} \equiv w_i$とし、それに伴い$A_{1,i+q} = I, \quad A_{1,j} = \boldsymbol{0} \quad j \neq i+q$とし、$A_{i, j} = \boldsymbol{0}, \quad \forall i \in \lbrace 1, 2, \dots, p \rbrace , j = q+1,q+2,q+3$すると、上の式は次のように書き換えられる。

\begin{eqnarray*} \begin{bmatrix} A_{1,1} \\ A_{2,1} \\ A_{3,1} \\ \vdots \\ A_{p,1} \end{bmatrix} x^{1} + \begin{bmatrix} A_{1,2} \quad \boldsymbol{0} \\ A_{2,2} \quad I \\ A_{3,2} \quad \boldsymbol{0} \\ \vdots \quad \vdots \\ A_{p,2} \quad \boldsymbol{0} \end{bmatrix} \begin{bmatrix} x^{2} \\ w_2 \end{bmatrix} + \begin{bmatrix} A_{1,3} \quad \boldsymbol{0} \\ A_{2,3} \quad \boldsymbol{0} \\ A_{3,3} \quad I \\ \vdots \quad \vdots \\ A_{p,3} \quad \boldsymbol{0} \end{bmatrix} \begin{bmatrix} x^{3} \\ w \end{bmatrix} +\Sigma_{i = 1}^{p+q} \begin{bmatrix} A_{1,i} \\ A_{2,i} \\ A_{3,i} \\ \vdots \\ A_{p,i} \end{bmatrix} x^{i}= \boldsymbol{b} \end{eqnarray*}

(補題の適用による証明)
この線形等式が解を持つならば、Lemma 3（Giorgi, G., 2020）より以下の問題は解を持たない。

\begin{eqnarray*} \begin{aligned} &y = \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_p \end{bmatrix} \in \mathbb{R}^{m}, \quad y^{T} \begin{bmatrix} A_{1,1} \\ A_{2,1} \\ A_{3,1} \\ \vdots \\ A_{p,1} \end{bmatrix} = \Sigma_{i=1}^{p} y_{i}^T A_{i,1} = \boldsymbol{0}, \quad y^{T} \begin{bmatrix} A_{1,i} \\ A_{2,i} \\ A_{3,i} \\ \vdots \\ A_{p,i} \end{bmatrix} = E_i \geq \boldsymbol{0}, i = 2, \dots, q, \quad \\ &y_i \geq \boldsymbol{0}, i = 2, \dots, p,\quad y^{T}\boldsymbol{b} \le 0 \\ \end{aligned} \end{eqnarray*}

という問題であり、かつ次のいずれかを満たす。 ・ $y^{T} b < \boldsymbol{0}$
・ $y_{3} \gneq \boldsymbol{0}$
・ $y_{i} > \boldsymbol{0}, \quad \exists i \in \lbrace 4, \dots, p \rbrace$
・ $E_{3} \gneq \boldsymbol{0}$
・ $E_{i} > \boldsymbol{0}, \quad \exists i \in \lbrace 4, \dots, p \rbrace$
これは、2.に等しい。よって、題意は示された。

参考文献

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.