連立1次方程式や連立1次「不等式」に関して，「択一定理」と呼ばれる一群の定理がある。その中の一つ，Stiemke の定理は，ここ数年間，きちんと証明を理解したいと思いつつ，ほったらかしのままだった。
何年かぶりにその定理のことを思い出したのだが，相変わらず証明を素直に学ばずに，ある程度自力で証明できないかとだらだら考えを巡らせていた。
とはいえ，全くなんのヒントも無しに証明を見出せるほどの実力が僕にはないことは重々承知している。そこで，von Neumann と Morgenstern の有名な本，『ゲームの理論と経済行動 I』（ちくま学芸文庫）の 16 節「線型性と凸性」からヒントを得ようと思い立った。実際のところは，なんとなく凸集合の性質について Brezis の『関数解析 その理論と応用に向けて』（産業図書）の第 V 章で述べられている理論を復習したくなり，そういえば von Neumann と Morgenstern の本にも凸集合に関する丁寧な解説が載っていることを思い出したか，それとも凸集合の性質について学ぶために Tucker の解説を学ぼうとしたところ，そこで von Neumann と Morgenstern の本が挙げられていたからだったろうか。
我ながら何がきっかけだったかはっきり思い出せないのだが，ともかく『ゲームの理論と経済行動 I』をパラパラとページっていると，「16.4. 行列についての定理」で，なしくずしに一つの択一定理が導出されているではないか。くどいくらい丁寧に解説が述べられているので，議論の道筋を理解することは難しくはない。しかし，「何でいきなりそんな設定を持ち出すの？」といった疑問が湧くのは禁じ得ない。読んですぐには彼らの技巧がすんなり頭に入らなかったが，少し考えてみたところ，いわゆる slack 変数と呼ばれるものを導入したことに他ならないということに気づいた。
スラック変数自体については（僕には非常にしばしばありがちなことだが）耳学問として用語だけは知っていた。一松信『偏微分と極値問題』（現代数学社）をだいぶ昔からときどき手にとっては眺めていたのだが，そこで見かけて以来ずっと頭の中にひっかかっていたのである。今改めてその書を見ると，線形計画法や双対問題などを取り扱った箇所に，今まさに僕が関心のある択一定理に関連の深い Farkas の定理も載っている。どうやら，その章に本気でアタックすべき時機がきたのかもしれない。
それはともかくとして，Stiemke の定理や Farkas の定理の証明を知りたければ，Tucker の解説や，Gale の "The Theory of Linear Economic Models"，あるいは Dantzig & Thapa の "Linear Programming" などの定評のあるテキストを勉強すれば済む話だが，von Neumann と Morgenstern 流のやり方がとても気に入ったので，どうにかその路線で自力で証明できないかと夢を観てしまった。
ところで，いったい何を証明したいのかというと，Gale の本の Theorem 2.6 (p.44) をとりあえずの目標として設定したい。
それは，実 m×n 行列 A および n 次元行ベクトル b に対し，
xA=b を満たす非負の（すなわち，全ての成分が 0 以上であるような）m 次元行ベクトル x が存在するか，
または
Ay≧0 かつ by＜0 を満たすような n 次元列ベクトル y が存在するか
のいずれか「一方のみ」が成り立つ，
という「択一定理」である。
この定理に引き続いて Gale が解説しているように，この定理には幾何学的な解釈が可能である。しかし，Gale がそこで与えた証明は数学的帰納法に基づくもののようで，幾何学的，直観的に理解できる類のものではなさそうである（ちゃんと読んでいないので根拠のない誤解かもしれないが）。
僕としては，von Neumann と Morgenstern の本で学び，心地よい感動すら覚えた論法に沿った方法でこの定理を証明したいと思い，試行錯誤を続けた。最終的に成功するまでに一カ月近く費やしてしまった。僕の数学の実力のなさがまたまた露呈してしまったわけだが，事実なのだから仕方がない。
さて，証明の指針はこうである。今のところ僕にとって理解しやすいのは，上に挙げた等式の両辺の転置を取ったり，不等号の向きを逆にした，いろいろと裏返ったバージョン，つまり，先ほどと記号は同じだが行や列が入れ替わった別物になってしまうが，
m×n 行列 A および m 次元列ベクトル b に対し，
Ax=b を満たす非負の m 次元列ベクトル x が存在するか，
または
yA≦0 かつ yb＞0 を満たす m 次元行ベクトル y が存在する
という定理の方なので，その流儀で指針を述べよう。
まず，行列 A の第 i 列を成分に持つ m 次元列ベクトルを A_i とおくと，A=[A_1 A_2 ... A_n] と表せる。
さて，これら n 本の列ベクトルに 0 以上の実数を掛けたものの線型結合で表せるベクトルの全体を K とおく。これは凸錐 (convex cone) などと呼ばれる，ちょうど円錐や三角錐のような錐体であり，特に閉凸集合である。
このような設定の下で考えると，ベクトル b で表される点について，それが 凸錐 K の周および内部にあるか，あるいはその外部にあるかのどちらか一方のみの状況が起こり得るが，この択一定理はまさにそうした当たり前の状況を述べているに過ぎないのである。
そのような，「図を描いて考えれば当たり前」だという感覚に基づいた証明はできないものかというのが（ここ一ヵ月の）僕の悲願だったわけだが，実際の証明に必要な道具立ては少々大がかりである。とはいっても，幾何学的な意味合いは非常に簡単な内容である。
ではようやく証明の概略を述べよう。
b は凸錐 K に属するか属さないかのいずれか一方のみが成り立つわけだが，
まず，b が K に属するならば，K の定義により，b は n 個の非負実数 x_i を用いて
x_1 A_1 + x_2 A_2 + ... + x_n A_n = b
と表されるが，x を，第 i 成分に x_i を持つ列ベクトルとすれば，これを行列の積を用いて表したものが等式 Ax=b に他ならない。
他方，b が K に属さないとき，b から凸錐 K に垂線を引くことができる（この事実を数学的に証明するには，極限に関する少々大げさな道具立てが必要となるが，直観的には明らかなことであろう）。その垂線の足に対応するベクトルを c とおく。ベクトル b-c は凸錐 K の表面に対して垂直なわけである。このベクトルを法線に持ち，原点（と，実は垂線の足 c）を通る（超）平面 (b-c)・z=0 は，点 b と凸錐 K をきれいに分離する（そのことの証明にも極限を用いた議論のお世話になる）。つまり，(b-c)・b＞0 であり，凸錐 K に属する任意の点 p に対し，(b-c)・p≦0 が成り立つことが示せる。ここで，行ベクトル y を，列ベクトル b-c の転置行列とおくと，yb＞0 である。また，特に各 A_i は凸錐 K に属するから yA_i≦0 が成り立つ。これらを行列の積を用いてまとめれば yA≦0（n 次元行ベクトル yA の各成分が 0 以下という意味）となる。
このように，僕の眼には
Ax=b が「b は A の列ベクトルたちの非負係数の線型結合で表せる」，
yA≦0 かつ yb＞0 が「超平面 yz=0 が b と凸錐 K を分離する」
という風に映るので，上に述べた転置バージョンの方がしっくりくるというわけである。もちろん，これは単に好みの問題にすぎず，まったく本質的なことではない。Gale の本に載っているオリジナルバージョンに合わせるには，単に行列 A を行ベクトルの結合として分割し，上の議論をそれに合わせてほんの少しだけ修正すれば済む。
ところで，僕がいったいどこでつまづいていたのかと言えば，はじめ von Neumann と Morgenstern の議論を猿真似して A_i たちの張る凸包が b を含む，含まないだのと考えていたのだが，なかなか yA≦0 の右辺がちゃんと 0 になるような，つまり，原点を通るような分離超平面の存在を導き出せなかったのである。それらにさらに b を付け加えてみたが，やはり似て非なる新たな択一定理が得られるばかりであった。定理の叙述をよく読み返したら，凸包でなく凸錐を考えるべきだと気づき，その線で考えを進めてみたものの，一般の凸集合とその外部の点を分離する超平面の存在に関する定理の利用ばかりを考えており，原点を通る分離超平面をどう見出せばよいのかがなかなかわからなかった。b が外部にある時の凸錐 K への射影 c を使いたいという欲求のみは当初から持ってはいた。そして K は一般の凸集合ではなく，もう少し特殊な凸錐であるという事情をどう利用すればよいのかがわかっていなかった。それが，5日の午前2時過ぎ，そろそろ寝ようと思ったにもかかわらず，ふとアイデアが湧き，図を描いて確信を得てしまい，それから一時間ほど議論を詰めた結果，幸いにも成功したというわけである。そのときは，それから約2時間後に久々の震度3の地震に起こされるとは夢にも思っていなかったのだが。
なお，僕の論法にはどうしても位相，つまり極限が必要となるので，そういった知識のない人たちにとっては初等的とは言えない証明であり，その点が残念であるが，幾何学的な直観にマッチしているので，その点は大いに満足している。Gale や Tucker が紹介している証明は，おそらく極限を使わず，数学的帰納法と四則演算のみで証明する方法であり，そちらの方がより線形代数らしい証明であるといえよう。
いずれにせよ，僕の頭でもしっかり理解できた気がする基本的な定理が一つ手に入ったのだから，さくっと Stiemke の定理（と Minty が呼んでいる，Gale の本の上の定理のすぐ次に出てくる Theorem 2.7）を理解し，いよいよ本丸である Minty の極大単調作用素 (maximal monotone operators) へと進んで行きたいものであるが，はてさて，どうせまたのらりくらりと取り組むことになるので，本丸を攻め落とすのはいったいいつの日になることやら・・・。
何年かぶりにその定理のことを思い出したのだが，相変わらず証明を素直に学ばずに，ある程度自力で証明できないかとだらだら考えを巡らせていた。
とはいえ，全くなんのヒントも無しに証明を見出せるほどの実力が僕にはないことは重々承知している。そこで，von Neumann と Morgenstern の有名な本，『ゲームの理論と経済行動 I』（ちくま学芸文庫）の 16 節「線型性と凸性」からヒントを得ようと思い立った。実際のところは，なんとなく凸集合の性質について Brezis の『関数解析 その理論と応用に向けて』（産業図書）の第 V 章で述べられている理論を復習したくなり，そういえば von Neumann と Morgenstern の本にも凸集合に関する丁寧な解説が載っていることを思い出したか，それとも凸集合の性質について学ぶために Tucker の解説を学ぼうとしたところ，そこで von Neumann と Morgenstern の本が挙げられていたからだったろうか。
我ながら何がきっかけだったかはっきり思い出せないのだが，ともかく『ゲームの理論と経済行動 I』をパラパラとページっていると，「16.4. 行列についての定理」で，なしくずしに一つの択一定理が導出されているではないか。くどいくらい丁寧に解説が述べられているので，議論の道筋を理解することは難しくはない。しかし，「何でいきなりそんな設定を持ち出すの？」といった疑問が湧くのは禁じ得ない。読んですぐには彼らの技巧がすんなり頭に入らなかったが，少し考えてみたところ，いわゆる slack 変数と呼ばれるものを導入したことに他ならないということに気づいた。
スラック変数自体については（僕には非常にしばしばありがちなことだが）耳学問として用語だけは知っていた。一松信『偏微分と極値問題』（現代数学社）をだいぶ昔からときどき手にとっては眺めていたのだが，そこで見かけて以来ずっと頭の中にひっかかっていたのである。今改めてその書を見ると，線形計画法や双対問題などを取り扱った箇所に，今まさに僕が関心のある択一定理に関連の深い Farkas の定理も載っている。どうやら，その章に本気でアタックすべき時機がきたのかもしれない。
それはともかくとして，Stiemke の定理や Farkas の定理の証明を知りたければ，Tucker の解説や，Gale の "The Theory of Linear Economic Models"，あるいは Dantzig & Thapa の "Linear Programming" などの定評のあるテキストを勉強すれば済む話だが，von Neumann と Morgenstern 流のやり方がとても気に入ったので，どうにかその路線で自力で証明できないかと夢を観てしまった。
ところで，いったい何を証明したいのかというと，Gale の本の Theorem 2.6 (p.44) をとりあえずの目標として設定したい。
それは，実 m×n 行列 A および n 次元行ベクトル b に対し，
xA=b を満たす非負の（すなわち，全ての成分が 0 以上であるような）m 次元行ベクトル x が存在するか，
または
Ay≧0 かつ by＜0 を満たすような n 次元列ベクトル y が存在するか
のいずれか「一方のみ」が成り立つ，
という「択一定理」である。
この定理に引き続いて Gale が解説しているように，この定理には幾何学的な解釈が可能である。しかし，Gale がそこで与えた証明は数学的帰納法に基づくもののようで，幾何学的，直観的に理解できる類のものではなさそうである（ちゃんと読んでいないので根拠のない誤解かもしれないが）。
僕としては，von Neumann と Morgenstern の本で学び，心地よい感動すら覚えた論法に沿った方法でこの定理を証明したいと思い，試行錯誤を続けた。最終的に成功するまでに一カ月近く費やしてしまった。僕の数学の実力のなさがまたまた露呈してしまったわけだが，事実なのだから仕方がない。
さて，証明の指針はこうである。今のところ僕にとって理解しやすいのは，上に挙げた等式の両辺の転置を取ったり，不等号の向きを逆にした，いろいろと裏返ったバージョン，つまり，先ほどと記号は同じだが行や列が入れ替わった別物になってしまうが，
m×n 行列 A および m 次元列ベクトル b に対し，
Ax=b を満たす非負の m 次元列ベクトル x が存在するか，
または
yA≦0 かつ yb＞0 を満たす m 次元行ベクトル y が存在する
という定理の方なので，その流儀で指針を述べよう。
まず，行列 A の第 i 列を成分に持つ m 次元列ベクトルを A_i とおくと，A=[A_1 A_2 ... A_n] と表せる。
さて，これら n 本の列ベクトルに 0 以上の実数を掛けたものの線型結合で表せるベクトルの全体を K とおく。これは凸錐 (convex cone) などと呼ばれる，ちょうど円錐や三角錐のような錐体であり，特に閉凸集合である。
このような設定の下で考えると，ベクトル b で表される点について，それが 凸錐 K の周および内部にあるか，あるいはその外部にあるかのどちらか一方のみの状況が起こり得るが，この択一定理はまさにそうした当たり前の状況を述べているに過ぎないのである。
そのような，「図を描いて考えれば当たり前」だという感覚に基づいた証明はできないものかというのが（ここ一ヵ月の）僕の悲願だったわけだが，実際の証明に必要な道具立ては少々大がかりである。とはいっても，幾何学的な意味合いは非常に簡単な内容である。
ではようやく証明の概略を述べよう。
b は凸錐 K に属するか属さないかのいずれか一方のみが成り立つわけだが，
まず，b が K に属するならば，K の定義により，b は n 個の非負実数 x_i を用いて
x_1 A_1 + x_2 A_2 + ... + x_n A_n = b
と表されるが，x を，第 i 成分に x_i を持つ列ベクトルとすれば，これを行列の積を用いて表したものが等式 Ax=b に他ならない。
他方，b が K に属さないとき，b から凸錐 K に垂線を引くことができる（この事実を数学的に証明するには，極限に関する少々大げさな道具立てが必要となるが，直観的には明らかなことであろう）。その垂線の足に対応するベクトルを c とおく。ベクトル b-c は凸錐 K の表面に対して垂直なわけである。このベクトルを法線に持ち，原点（と，実は垂線の足 c）を通る（超）平面 (b-c)・z=0 は，点 b と凸錐 K をきれいに分離する（そのことの証明にも極限を用いた議論のお世話になる）。つまり，(b-c)・b＞0 であり，凸錐 K に属する任意の点 p に対し，(b-c)・p≦0 が成り立つことが示せる。ここで，行ベクトル y を，列ベクトル b-c の転置行列とおくと，yb＞0 である。また，特に各 A_i は凸錐 K に属するから yA_i≦0 が成り立つ。これらを行列の積を用いてまとめれば yA≦0（n 次元行ベクトル yA の各成分が 0 以下という意味）となる。
このように，僕の眼には
Ax=b が「b は A の列ベクトルたちの非負係数の線型結合で表せる」，
yA≦0 かつ yb＞0 が「超平面 yz=0 が b と凸錐 K を分離する」
という風に映るので，上に述べた転置バージョンの方がしっくりくるというわけである。もちろん，これは単に好みの問題にすぎず，まったく本質的なことではない。Gale の本に載っているオリジナルバージョンに合わせるには，単に行列 A を行ベクトルの結合として分割し，上の議論をそれに合わせてほんの少しだけ修正すれば済む。
ところで，僕がいったいどこでつまづいていたのかと言えば，はじめ von Neumann と Morgenstern の議論を猿真似して A_i たちの張る凸包が b を含む，含まないだのと考えていたのだが，なかなか yA≦0 の右辺がちゃんと 0 になるような，つまり，原点を通るような分離超平面の存在を導き出せなかったのである。それらにさらに b を付け加えてみたが，やはり似て非なる新たな択一定理が得られるばかりであった。定理の叙述をよく読み返したら，凸包でなく凸錐を考えるべきだと気づき，その線で考えを進めてみたものの，一般の凸集合とその外部の点を分離する超平面の存在に関する定理の利用ばかりを考えており，原点を通る分離超平面をどう見出せばよいのかがなかなかわからなかった。b が外部にある時の凸錐 K への射影 c を使いたいという欲求のみは当初から持ってはいた。そして K は一般の凸集合ではなく，もう少し特殊な凸錐であるという事情をどう利用すればよいのかがわかっていなかった。それが，5日の午前2時過ぎ，そろそろ寝ようと思ったにもかかわらず，ふとアイデアが湧き，図を描いて確信を得てしまい，それから一時間ほど議論を詰めた結果，幸いにも成功したというわけである。そのときは，それから約2時間後に久々の震度3の地震に起こされるとは夢にも思っていなかったのだが。
なお，僕の論法にはどうしても位相，つまり極限が必要となるので，そういった知識のない人たちにとっては初等的とは言えない証明であり，その点が残念であるが，幾何学的な直観にマッチしているので，その点は大いに満足している。Gale や Tucker が紹介している証明は，おそらく極限を使わず，数学的帰納法と四則演算のみで証明する方法であり，そちらの方がより線形代数らしい証明であるといえよう。
いずれにせよ，僕の頭でもしっかり理解できた気がする基本的な定理が一つ手に入ったのだから，さくっと Stiemke の定理（と Minty が呼んでいる，Gale の本の上の定理のすぐ次に出てくる Theorem 2.7）を理解し，いよいよ本丸である Minty の極大単調作用素 (maximal monotone operators) へと進んで行きたいものであるが，はてさて，どうせまたのらりくらりと取り組むことになるので，本丸を攻め落とすのはいったいいつの日になることやら・・・。
※コメント投稿者のブログIDはブログ作成者のみに通知されます