Lemma 2（Giorgi, G., 2020） - DROで学位を取るまでの軌跡

定理

以下の線形不等式系のいずれか一方のみが解を持つ。
$A_i$は行列を指しており、$i$は通し番号である。また$\gneq$は、両辺が一致することはないが要素ごとに見ると$\ge$が成立する不等式である。

$\lbrace A_1 x_1 + A_2 x_2 + A_3 x_3 + \sum_{j=4}^{q} A_j x_j = \boldsymbol{0}, x_2 \geq \boldsymbol{0}, x_3 > \boldsymbol{0}, \ x_j \gneq \boldsymbol{0}, j = 4, \dots, q \rbrace$

$\begin{eqnarray*} \left \lbrace \begin{aligned} &y^{T} A_1 = \boldsymbol{0}, y^{T} A_j \geq \boldsymbol{0}, j = 2, \dots, q \\ &\text{　かつ、次の少なくとも一方が成立}\\ &y^{T} A_3 \gneq \boldsymbol{0} \\ &y^{T} A_j > \boldsymbol{0} \ \text{fot at least an index }j, \ 4 \leq j \leq q \end{aligned} \right \rbrace \end{eqnarray*}$

証明

(1.と同値の線形不等式を構築)
$x_j \gneq \boldsymbol{0}$は$w_j > \boldsymbol{0}$を用いて、$\lbrace x_j \geq \boldsymbol{0} \mid 1_j^{T} x_j - w_j = 0, \ w_j > 0 \rbrace$ と書き換えられる。ただし$1_j$は$x_j$と同じ次元のベクトルであり、全ての要素が1である。このとき、1.を次のように書き換える。

$\begin{eqnarray*} \begin{aligned} \begin{bmatrix} A_1 \\ \boldsymbol{0} \\ \boldsymbol{0} \\ \vdots \\ \boldsymbol{0} \end{bmatrix} x_1+ \begin{bmatrix} A_2 & A_4 & A_5 & \dots & A_q \\ \boldsymbol{0} & 1_4^{T} & \boldsymbol{0} & \dots & \boldsymbol{0} \\ \boldsymbol{0} & \boldsymbol{0} & 1_5^{T} & \dots & \boldsymbol{0} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \boldsymbol{0} & \boldsymbol{0} & \boldsymbol{0} & \dots & 1_q^{T} \end{bmatrix} \begin{bmatrix} x_2 \\ x_4 \\ x_5 \\ \vdots \\ x_q \end{bmatrix} + \begin{bmatrix} A_3 & \boldsymbol{0} \\ \boldsymbol{0} & -I \\ \end{bmatrix} \begin{bmatrix} x^3 \\ w \end{bmatrix} = \boldsymbol{0}\\ \end{aligned} \end{eqnarray*}$

$$\text{where} \quad x_j \ge 0 \quad j = 2,4,\cdots,q \quad x_3 >0 \quad w>0$$

(同値な線形不等式が成立しないなら、2が成立する)
得られた線形不等式が解を持たないなら、Lemma 1（Giorgi, G., 2020）により、以下は解を持つ。

$\begin{eqnarray*} \begin{aligned} y^{T} \begin{bmatrix} A_1 \\ \boldsymbol{0} \\ \boldsymbol{0} \\ \vdots \\ \boldsymbol{0} \end{bmatrix} = \boldsymbol{0} , \quad y^{T} \begin{bmatrix} A_2 & A_4 & A_5 & \dots & A_q \\ \boldsymbol{0} & 1_4^{T} & \boldsymbol{0} & \dots & \boldsymbol{0} \\ \boldsymbol{0} & \boldsymbol{0} & 1_5^{T} & \dots & \boldsymbol{0} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \boldsymbol{0} & \boldsymbol{0} & \boldsymbol{0} & \dots & 1_q^{T} \end{bmatrix} \ge \boldsymbol{0} , \quad y^{T} \begin{bmatrix} A_3 & \boldsymbol{0} \\ \boldsymbol{0} & -I \\ \end{bmatrix} \gneq \boldsymbol{0} \end{aligned} \end{eqnarray*}$

つまり、$y^{T} = (y_A, y_4, \cdots, y_q)^{T}$として、

$\begin{eqnarray*} \begin{aligned} &y_A^{T}A_1 = \boldsymbol{0} \\ &y_A^{T}A_2 \ge \boldsymbol{0} \\ &y_A^{T}A_j \ge - y_j \ge 0 \quad j = 4, \cdots, q\\ &(y_A^{T}A_3,y_4, \cdots y_q) \gneq \boldsymbol{0} \end{aligned} \end{eqnarray*}$

となる。つまり、2.が成立する。

(同値な線形不等式が成立するなら、2が成立しない)
同様に考えると、Lemma 1（Giorgi, G., 2020）より、示される。

参考文献

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.