ファルカスの線型不等式の基本定理

連立1次方程式に解が存在しないための必要十分条件

変数\(x_{1},\cdots ,x_{n}\in \mathbb{R} \)に関する連立1次方程式\begin{equation}\left\{
\begin{array}{c}
a_{11}x_{1}+\cdots +a_{1n}x_{n}=b_{1} \\
\vdots \\
a_{m1}x_{1}+\cdots +a_{mn}x_{n}=b_{m}\end{array}\right. \quad \cdots (1)
\end{equation}が与えられているものとします。ただし、\(a_{ij}\in \mathbb{R} \)は係数、\(b_{i}\in \mathbb{R} \)は定数項、\(x_{i}\in \mathbb{R} \)は変数です。

連立1次方程式\(\left( 1\right) \)の係数行列\(A\)と変数ベクトル\(x\)および定数ベクトル\(b\)を、\begin{eqnarray*}A &=&\begin{pmatrix}
a_{11} & \cdots & a_{1n} \\
\vdots & \ddots & \vdots \\
a_{m1} & \cdots & a_{mn}\end{pmatrix}\in M_{m,n}\left( \mathbb{R} \right) \\
x &=&\begin{pmatrix}
x_{1} \\
\vdots \\
x_{n}\end{pmatrix}\in M_{n,1}\left( \mathbb{R} \right) \\
b &=&\begin{pmatrix}
b_{1} \\
\vdots \\
b_{m}\end{pmatrix}\in M_{m,1}\left( \mathbb{R} \right)
\end{eqnarray*}と定めます。このとき、\begin{eqnarray*}
Ax &=&\begin{pmatrix}
a_{11} & \cdots & a_{1n} \\
\vdots & \ddots & \vdots \\
a_{m1} & \cdots & a_{mn}\end{pmatrix}\begin{pmatrix}
x_{1} \\
\vdots \\
x_{n}\end{pmatrix}\quad \because A,x\text{の定義} \\
&=&\begin{pmatrix}
a_{11}x_{1}+\cdots +a_{1n}x_{n} \\
\vdots \\
a_{m1}x_{1}+\cdots +a_{mn}x_{n}\end{pmatrix}\quad \because \text{行列積の定義} \\
&=&x_{1}\left(
\begin{array}{c}
a_{11} \\
\vdots \\
a_{m1}\end{array}\right) +\cdots +x_{n}\left(
\begin{array}{c}
a_{1n} \\
\vdots \\
a_{mn}\end{array}\right) \\
&=&x_{1}\mathrm{col}\left( A,1\right) +\cdots +x_{n}\mathrm{col}\left(
A,n\right)
\end{eqnarray*}という変形が可能であるため、連立1次方程式\(\left( 1\right) \)を行列方程式\begin{equation}Ax=b \quad \cdots (2)
\end{equation}として表現したり、ベクトル方程式\begin{equation}
x_{1}\mathrm{col}\left( A,1\right) +\cdots +x_{n}\mathrm{col}\left( A,n\right) =b
\quad \cdots (3)
\end{equation}として表現することもできます。\(\left( 1\right) ,\left(2\right) ,\left( 3\right) \)の解集合は一致するため、これらを同一視できます。

ベクトル方程式\(\left( 3\right) \)に解が存在することとは、\begin{equation*}\exists \left(
\begin{array}{c}
x_{1} \\
\vdots \\
x_{n}\end{array}\right) \in \mathbb{R} ^{n}:x_{1}\mathrm{col}\left( A,1\right) +\cdots +x_{n}\mathrm{col}\left(
A,n\right) =b
\end{equation*}が成り立つことを意味します。つまり、定数ベクトル\(b\)が係数行列\(A\)の列ベクトルからなる集合\begin{equation*}\left\{ \mathrm{col}\left( A,1\right) ,\cdots ,\mathrm{col}\left( A,n\right)
\right\} \subset \mathbb{R} ^{m}
\end{equation*}の何らかの線型結合として表現可能であるということです。線型スパンを用いてこれを表現すると、\begin{equation}
b\in \mathrm{span}\left( \left\{ \mathrm{col}\left( A,1\right) ,\cdots ,\mathrm{col}\left( A,n\right) \right\} \right) \quad \cdots (4)
\end{equation}となります。

線型代数における議論において明らかになったように、\(\left( 4\right) \)が成り立つことは、\begin{equation}\mathrm{span}\left( \left\{ \mathrm{col}\left( A,1\right) ,\cdots ,\mathrm{col}\left( A,n\right) \right\} \right) =\mathrm{span}\left( \left\{ \mathrm{col}\left( A,1\right) ,\cdots ,\mathrm{col}\left( A,n\right) ,b\right\} \right)
\quad \cdots (5)
\end{equation}と必要十分です。さらに、拡大係数行列を、\begin{equation*}
\widetilde{A}=\left( A,b\right) \in M_{m,n+1}\left( \mathbb{R} \right)
\end{equation*}と定義したとき、\(\left(5\right) \)が成り立つことは、\begin{equation*}\mathrm{rank}\left( A\right) =\mathrm{rank}\left( \widetilde{A}\right)
\end{equation*}と必要十分です。

連立1次方程式に解が存在するための必要十分条件が明らかになっているのであれば、その否定をとることにより、連立1次方程式に解が存在しないための必要十分条件が得られます。具体的には以下の通りです。

以下の条件もまた連立1次方程式に解が存在しないための必要十分条件になります。

連立1次方程式に解が存在するための必要十分条件と、解が存在しないための必要十分条件がそれぞれ明らかになりました。連立1次方程式には解が存在するかしないかのどちらか一方であるため以下を得ます。

線型不等式の基本定理

連立1次方程式\begin{equation}
Ax=b \quad \cdots (1)
\end{equation}に解\(x\in \mathbb{R} ^{n}\)が存在するための必要十分条件と、解が存在しないための必要十分条件がそれぞれ明らかになりました。では、連立1次方程式\(\left( 1\right) \)について、以下の条件\begin{equation*}\forall i\in \left\{ 1,\cdots ,n\right\} :x_{i}\geq 0
\end{equation*}すなわち、\begin{equation*}
x\geq 0
\end{equation*}を満たす解\(x\in \mathbb{R} ^{n}\)が存在するための必要十分条件と、そのような解が存在しないための必要十分条件をそれぞれ特定できるでしょうか。

繰り返しになりますが、連立1次方程式\(Ax=b\)に解\(x\in \mathbb{R} ^{n}\)が存在するための必要十分条件の1つは、\begin{equation*}\exists \left(
\begin{array}{c}
x_{1} \\
\vdots \\
x_{n}\end{array}\right) \in \mathbb{R} ^{n}:x_{1}\mathrm{col}\left( A,1\right) +\cdots +x_{n}\mathrm{col}\left(
A,n\right) =b
\end{equation*}です。定数ベクトル\(b\)が係数行列\(A\)の列ベクトルからなる集合\begin{equation*}\left\{ \mathrm{col}\left( A,1\right) ,\cdots ,\mathrm{col}\left( A,n\right)
\right\} \subset \mathbb{R} ^{m}
\end{equation*}の何らかの線型結合として表現可能であるということです。線型スパンを用いてこれを表現すると、\begin{equation*}
b\in \mathrm{span}\left( \left\{ \mathrm{col}\left( A,1\right) ,\cdots ,\mathrm{col}\left( A,n\right) \right\} \right)
\end{equation*}となります。したがって、連立1次方程式\(Ax=b\)に\(x\geq 0\)を満たす解\(x\in \mathbb{R} ^{n}\)が存在するための必要十分条件は、\begin{equation*}\exists \left(
\begin{array}{c}
x_{1} \\
\vdots \\
x_{n}\end{array}\right) \in \mathbb{R} _{+}^{n}:x_{1}\mathrm{col}\left( A,1\right) +\cdots +x_{n}\mathrm{col}\left(
A,n\right) =b
\end{equation*}となります。つまり、定数ベクトル\(b\)が係数行列\(A\)の列ベクトルからなる集合\begin{equation*}\left\{ \mathrm{col}\left( A,1\right) ,\cdots ,\mathrm{col}\left( A,n\right)
\right\} \subset \mathbb{R} ^{m}
\end{equation*}の何らかの錐結合として表現可能であるということです。凸錐を用いてこれを表現すると、\begin{equation*}
b\in \mathrm{Cone}\left( \left\{ \mathrm{col}\left( A,1\right) ,\cdots ,\mathrm{col}\left( A,n\right) \right\} \right)
\end{equation*}となります。であるならば、連立1次方程式\(Ax=b\)に\(x\geq 0\)を満たす解\(x\in \mathbb{R} ^{n}\)が存在しないめの必要十分条件は、\begin{equation*}b\not\in \mathrm{Cone}\left( \left\{ \mathrm{col}\left( A,1\right) ,\cdots ,\mathrm{col}\left( A,n\right) \right\} \right)
\end{equation*}です。以降では、これらの条件を別の形で表現します。

係数行列\(A\in M_{m,n}\left( \mathbb{R} \right) \)と定数ベクトル\(b\in M_{m,1}\left( \mathbb{R} \right) \)が与えられているものとします。ただし、係数行列の階数を、\begin{equation*}r=\mathrm{rank}\left( A\right)
\end{equation*}と表記します。このとき、以下の2つの場合のどちらか一方が成り立つことが保証されます。

1つ目のケースは、連立1次方程式\(Ax=b\)に\(x\geq 0\)を満たす解\(x\in \mathbb{R} ^{n}\)が存在する場合です。これは、定数ベクトル\(b\)が、係数行列\(A\)を構成する線型独立な列ベクトル集合の錐結合として表現されることとして表現されます。つまり、係数行列\(A\)の第\(j\)列ベクトルを、\begin{equation*}a_{j}=\mathrm{col}\left( A,j\right) =\left(
\begin{array}{c}
a_{j1} \\
\vdots \\
a_{jm}\end{array}\right) \in M_{m,1}\left( \mathbb{R} \right)
\end{equation*}と表記するのであれば、以上の事実は、\(k\leq n\)を満たす何らかの番号\(k\in \mathbb{N} \)に対して、以下の条件\begin{equation*}\left\{ a_{\left( 1\right) },\cdots ,a_{\left( k\right) }\right\} \subset
\left\{ a_{1},\cdots ,a_{n}\right\}
\end{equation*}を満たす線型独立なベクトル集合\(\left\{ a_{\left( 1\right)},\cdots ,a_{\left( k\right) }\right\} \)が存在して、\begin{equation}\exists \lambda _{1},\cdots ,\lambda _{k}\geq 0:b=\lambda _{1}a_{\left(
1\right) }+\cdots +\lambda _{k}a_{\left( k\right) } \quad \cdots (1)
\end{equation}と表されることを意味します。凸錐の定義より、\(\left( 1\right) \)が成り立つことを、\begin{equation*}b\in \mathrm{Cone}\left( \left\{ a_{\left( 1\right) },\cdots ,a_{\left(
k\right) }\right\} \right)
\end{equation*}と表現することもできます。

2つ目のケースは、連立1次方程式\(Ax=b\)に\(x\geq 0\)を満たす解\(x\in \mathbb{R} ^{n}\)が存在しない場合です。これは、係数行列\(A\)を構成する何らかの線型独立な\(r-1\)個の列ベクトル集合\begin{equation*}\left\{ a_{\left( 1\right) },\cdots ,a_{\left( r-1\right) }\right\} \subset
\left\{ a_{1},\cdots ,a_{n}\right\}
\end{equation*}と、何らかの行ベクトル\(y\in M_{1,m}\left( \mathbb{R} \right) \)の中に、以下の条件\begin{eqnarray*}&&\left( a\right) \ \forall j\in \left\{ 1,\cdots ,r-1\right\} :ya_{\left(
j\right) }=0 \\
&&\left( b\right) \ \forall j\in \left\{ 1,\cdots ,n\right\} :ya_{j}\geq 0 \\
&&\left( c\right) \ yb<0
\end{eqnarray*}を満たすものが存在することとして表現されます。方向ベクトル\(y\)と直交するとともに原点を通過する超平面は、\begin{equation*}H\left( y,0\right) =\left\{ x\in M_{m,1}\left( \mathbb{R} \right) \ |\ yx=0\right\}
\end{equation*}と表現されるため、条件\(\left( a\right) \)は、係数行列\(A\)を構成する線型独立な\(r-1\)個の列ベクトル\(a_{\left( 1\right) },\cdots ,a_{\left( r-1\right) }\)が何らかの超平面\(H\left( y,0\right) \)上に位置することを意味し、条件\(\left( b\right) ,\left( c\right) \)は、その超平面\(H\left( y,0\right) \)によってベクトル\(a_{1},\cdots ,a_{n}\)とベクトル\(b\)が分離されることを意味します。

以上の命題を線型不等式の基本定理（fundamental theorem of linear inequalities）と呼びます。

アルゴリズムの適用例：ケース1

先の命題の証明において提示したアルゴリズムの適用例を提示します。まずはケース1の場合です。

例（非負の解を持つ連立1次方程式）

変数\(x_{1},x_{2},x_{3}\in \mathbb{R} \)に関する連立1次方程式\begin{equation*}\left\{
\begin{array}{c}
x_{2}+x_{3}=1 \\
x_{1}+x_{2}=\frac{1}{2}\end{array}\right.
\end{equation*}が与えられているものとします。係数行列と定数ベクトルは、\begin{eqnarray*}
A &=&\left( a_{1},a_{2},a_{3}\right) =\begin{pmatrix}
0 & 1 & 1 \\
1 & 1 & 0\end{pmatrix}\in M_{2,3}\left( \mathbb{R} \right) \\
b &=&\left(
\begin{array}{c}
1 \\
\frac{1}{2}\end{array}\right) \in M_{2,1}\left( \mathbb{R} \right)
\end{eqnarray*}です。係数行列の列ベクトルと定数ベクトルを以下に図示しました。

図より、\(b\)を\(\left\{ a_{2},a_{3}\right\} \)の錐結合として表せることが直感的に明らかであるため、この連立1次方程式は非負の解を持つことが予想されます。つまり、パターン1のケースであることです。同じことを先のアルゴリズムを用いて確認します。係数行列の階数は、\begin{equation*}\mathrm{rank}\left( A\right) =2
\end{equation*}です。そこで、2つの線型独立な列ベクトル\begin{equation*}
D_{1}=\left\{ a_{1},a_{2}\right\}
\end{equation*}を選びます（下図）。

その上で、\begin{equation*}
b=\lambda _{1}a_{1}+\lambda _{2}a_{2}
\end{equation*}とおくと、\begin{equation*}
\lambda _{1}<0
\end{equation*}となるため、\(D_{1}\)から\(a_{1}\)を消去することにより\(\left\{ a_{2}\right\} \)を得ます。以下の行ベクトル\begin{equation*}y=\left( -1,1\right)
\end{equation*}を選べば、\begin{eqnarray*}
ya_{2} &=&\left( -1,1\right) \left(
\begin{array}{c}
1 \\
1\end{array}\right) =0 \\
ya_{1} &=&\left( -1,1\right) \left(
\begin{array}{c}
0 \\
1\end{array}\right) =1 \\
yb &=&\left( -1,1\right) \left(
\begin{array}{c}
1 \\
\frac{1}{2}\end{array}\right) =-\frac{1}{2}<0
\end{eqnarray*}が成り立ちます。その一方で、\begin{equation*}
ya_{3}=\left( -1,1\right) \left(
\begin{array}{c}
1 \\
0\end{array}\right) =-1<0
\end{equation*}であるため、次のサイクルへ進みます。具体的には、\(D_{1}\)中の\(a_{1}\)を\(a_{3}\)に入れ替えると、\begin{equation*}D_{2}=\left\{ a_{2},a_{3}\right\}
\end{equation*}を得ます（下図）。

その上で、\begin{equation*}
b=\lambda _{2}a_{2}+\lambda _{3}a_{3}
\end{equation*}とおくと、\begin{eqnarray*}
\lambda _{2} &=&\frac{1}{2}\geq 0 \\
\lambda _{3} &=&\frac{1}{2}\geq 0
\end{eqnarray*}となるためプロセスを終了します。以上より、これはケース1であることが明らかになりました。実際、\begin{equation*}
\left(
\begin{array}{c}
x_{1} \\
x_{2} \\
x_{3}\end{array}\right) =\left(
\begin{array}{c}
0 \\
\frac{1}{2} \\
\frac{1}{2}\end{array}\right)
\end{equation*}は与えられた連立1次方程式の非負解です。

アルゴリズムの適用例：ケース2

続いてケース2の場合です。

例（非負の解を持たない連立1次方程式）

変数\(x_{1},x_{2},x_{3}\in \mathbb{R} \)に関する連立1次方程式\begin{equation*}\left\{
\begin{array}{c}
x_{2}+x_{3}=1 \\
x_{1}+x_{2}=-1\end{array}\right.
\end{equation*}が与えられているものとします。係数行列と定数ベクトルは、\begin{eqnarray*}
A &=&\left( a_{1},a_{2},a_{3}\right) =\begin{pmatrix}
0 & 1 & 1 \\
1 & 1 & 0\end{pmatrix}\in M_{2,3}\left( \mathbb{R} \right) \\
b &=&\left(
\begin{array}{c}
1 \\
-1\end{array}\right) \in M_{2,1}\left( \mathbb{R} \right)
\end{eqnarray*}です。係数行列の列ベクトルと定数ベクトルを以下に図示しました。

図より、\(b\)を列ベクトル\(a_{1},a_{2},a_{3}\)の錐結合として表せないことが直感的に明らかであるため、この連立1次方程式は非負の解を持たないことが予想されます。つまり、パターン2のケースであることです。同じことを先のアルゴリズムを用いて確認します。係数行列の階数は、\begin{equation*}\mathrm{rank}\left( A\right) =2
\end{equation*}です。そこで、2つの線型独立な列ベクトル\begin{equation*}
D_{1}=\left\{ a_{1},a_{2}\right\}
\end{equation*}を選びます（下図）。

その上で、\begin{equation*}
b=\lambda _{1}a_{1}+\lambda _{2}a_{2}
\end{equation*}とおくと、\begin{equation*}
\lambda _{1}<0
\end{equation*}となるため、\(D_{1}\)から\(a_{1}\)を消去することにより\(\left\{ a_{2}\right\} \)を得ます。以下の行ベクトル\begin{equation*}y=\left( -1,1\right)
\end{equation*}を選べば、\begin{eqnarray*}
ya_{2} &=&\left( -1,1\right) \left(
\begin{array}{c}
1 \\
1\end{array}\right) =0 \\
ya_{1} &=&\left( -1,1\right) \left(
\begin{array}{c}
0 \\
1\end{array}\right) =1 \\
yb &=&\left( -1,1\right) \left(
\begin{array}{c}
1 \\
-1\end{array}\right) =-2<0
\end{eqnarray*}が成り立ちます。その一方で、\begin{equation*}
ya_{3}=\left( -1,1\right) \left(
\begin{array}{c}
1 \\
0\end{array}\right) =-1<0
\end{equation*}であるため、次のサイクルへ進みます。具体的には、\(D_{1}\)中の\(a_{1}\)を\(a_{3}\)に入れ替えると、\begin{equation*}D_{2}=\left\{ a_{2},a_{3}\right\}
\end{equation*}を得ます（下図）。

その上で、\begin{equation*}
b=\lambda _{2}a_{2}+\lambda _{3}a_{3}
\end{equation*}とおくと、\begin{equation*}
\lambda _{2}<0
\end{equation*}となるため、\(D_{1}\)から\(a_{2}\)を消去することにより\(\left\{ a_{3}\right\} \)を得ます。以下の行ベクトル\begin{equation*}y=\left( 0,1\right)
\end{equation*}を選べば、\begin{eqnarray*}
ya_{3} &=&\left( 0,1\right) \left(
\begin{array}{c}
1 \\
0\end{array}\right) =0 \\
ya_{2} &=&\left( 0,1\right) \left(
\begin{array}{c}
1 \\
1\end{array}\right) =1 \\
yb &=&\left( 0,1\right) \left(
\begin{array}{c}
1 \\
-1\end{array}\right) =-1<0
\end{eqnarray*}が成り立ちます。さらに、\begin{equation*}
ya_{1}=\left( 0,1\right) \left(
\begin{array}{c}
0 \\
1\end{array}\right) =1
\end{equation*}であるため、プロセスを終了します。以上より、これはケース2であることが明らかになりました。実際、ベクトル\(y\)を法線ベクトルとする超平面（\(x\)軸）によって列ベクトル\(a_{1},a_{2},a_{3}\)と定数ベクトル\(b\)が分離されています。