Gordan の定理

定理（講義ｐｄｆ１既出）．

−→a ₁, . . . ,−→a _m ∈ R^{nについて，次の}(1)_と(2)_は同値：

(1) −→p −→0 _かつ−→p = −→0 _なる−→p =

⎛

⎝ p₁ ...

p_m

⎞

⎠ ∈ R^m

（非負要素たちからなるn次元ベクトル）であって p₁−→a ₁ + · · · + p_m−→a _m = −→0 _{を満たすものがある．}

(2) (−→a _i, −→y ) < 0, i = 1, . . . , m, _を満たす−→y ∈ R^{nはない．}

ここで(·, ·)_は内積．

数学的に良い形への書き換え

行列表記のGordan_の定理．A_がn × m_{行列のとき}(1)(2)_が同値：

(1) A−→p = −→0 , −→p −→0 , −→p = −→0 _を満たす−→p ∈ R^{mがある．}

(2) ^tA−→y ∈ R^{mが全成分負になる}−→y ∈ R^{nがない．t}A_{は転置行列．}

書き換えに過ぎないことの証明．行列Aが与えられたとき「列の小箱」にわけてA = (−→a ₁ −→a _m)_と置くとA−→p = p₁−→a ₁+· · ·+p_m−→a _mとなるからこのページの(1)_か ら前ページの(1)を得る．また，列ベクトルの内積を行列の積で書くと(−→a ,−→y ) =

t−→a _i−→y だから^tA−→y =

⎛

⎝ (−→a ₁,−→y ) ...

(−→a _m,−→y )

⎞

⎠ _{なので，このページの}(2)_{から前ページ} の(2)を得る．逆に前ページのように列ベクトル−→a ₁, . . . ,−→a _m ∈ R^{nが与えられた} とき，これらを列とする行列をA = (−→a ₁ · · · −→a _m)と置くと，同様に前ページの (1)(2)からそれぞれこのページの(1)(2)を得る（証明終わり）．

Gordan _{の定理の注．}

・ 小学校で鶴亀算，中学校で連立1次方程式と呼ぶ対象を大学でA−→x = −→b と書い て−→x = A⁻¹−→b を得るように，Gordanの定理も前ページの行列表記が見通し良い．

・ 前ページの形は，前々ページの（中学の連立方程式と大学の行列表記と同程度の）

単なる書き換えであることが，前ページの証明で分かった．

・ よって，前ページと前々ページの定理を区別しない（断らずに前ページの形で定 理を証明し，FJ条件の導出では前々ページの形を使う）．

・ 定理の主張は (1)_⇔(2)_．この同値の気持ちは，方程式と解の同値(A−→x =

−→b ⇔ −→x = A⁻¹−→b ) _{と類似のレベル：}

・ (1)_⇒(2)_{は証明容易}（解を方程式に代入して成立を確かめるレベル）

・ (2)_⇒(1)_からFJ_{条件を得る}（方程式から解を得るレベル．技が必要）

・ 技＝分離定理．(1)_の−→p が，方程式から見いだす解に対応．

− 見え見えのこと：分離定理の−→p がGordan_の定理の−→p

− 注目点１：分離定理の2つの凸集合の選択が，昔の偉い人たちのアイデア

− 注目点２：分離定理は不等号しか結論しないが，Gordan_の定理(1)_{は等号！？}

Gordan _の (1) _⇒ (2) _の証明

注．やさしいけど使わない（解を方程式に代入して成り立つと言うような内容）．

・ 解を方程式に代入して確かめるのと類似の価値はあるので証明を確認しておく．

(1)_⇒(2)_の証明．

(1)_のA−→p = −→0 _{とどんなベクトル}−→y ∈ R^{nと内積を取っても}0_．行 列の積の表記で^t−→y A−→p = 0_．

内積は数だから転置を取っても同じ：^t−→p (^tA−→y ) = 0_． 成分で書くとp₁(^tA−→y )₁ + · · · + p_m(^tA−→y )_m = 0_．

どのi_もp_i 0_で1_{つ以上正という}(1)の仮定なので，背理法で，

(^tA−→y )_iたちが全部負とすると，左辺は負になって上記「= 0_{」と矛盾．}

よって(2)_{のとおり，「}^tA−→y が全成分負」ということは どんな−→y ∈ Rⁿを持ってきても起きない．（証明終わり）

分離定理 から  Gordan _の (2) _⇒ (1)

Gordan_の定理の(2)_⇒(1)_の証明．

分離定理（講義ｐｄｆ１０）のn_をm_，A_をV _，B_をT _{と書き直して} 再掲：『V ⊂ R^mもT ⊂ R^{mも凸集合で}V ∩ T = ∅^{を満たすならば，}

−→x ∈ V ⇒ (−→x ,−→p ) α と−→x ∈ T ⇒ (−→x ,−→p ) α を満たす−→p ∈ R^mとα ∈ R^{がある．』}

Gordan_{の定理の行列表記の}A = (−→a ₁ . . . −→a _m)_{を用いて，}

V = {^tA−→y | −→y ∈ Rⁿ}^とT = {−→x ∈ R^m | ^全座標負} に上記分離定理を使う．

例．m = 2_{（平面）のとき}T は第3象限（軸を含まない）．

・ V は（和とスカラー倍について閉じているので）線形空間．線形空間と第3_象限 は凸集合（講義ｐｄｆ６）．

・ (2)_の仮定『^tA−→y ∈ R^{mが全成分負になる}−→y ∈ R^{nがない』から}V ∩ T = ∅^． よって分離定理の仮定が成り立つからその結論が成り立つ（上記「再掲」参照）．

（続） Gordan _の定理の (2) _⇒ (1) _の証明

前ページの結論（再掲）：Gordan_の(2)_{が成り立つ時}V = {^tA−→y | −→y ∈ Rⁿ}^と T = {−→x ∈ R^m | ^全座標負}^{について，}−→p ∈ R^{mがあって，}

−→x ∈ V ⇒ (−→x ,−→p ) α と−→x ∈ T ⇒ (−→x ,−→p ) α が成り立つ．

・ ここから：

線形空間と「第3象限」なので分離定理の一般論よりも強い結論．

− −→0 = ^tA−→0 ∈ V _{だから上記「}−→x ∈ V ⇒ · · ·^」を−→x = −→0 _に適 用できて0 = (−→0 , −→p ) α_．

− T_（平面m = 2_なら第3象限）は全成分負なすべての点を集めた ので，原点−→0 のいくらでも近い点について(−→x , −→p ) α _よってα 0 でないといけない．

・ 以上から，α = 0_{と決まる．つまり，}

−→x ∈ V ⇒ ^t−→x −→p = (−→x ,−→p ) 0_．

（左辺は行列の式で中央の辺の内積を書き直したもの．）

Gordan _の定理の (2) _⇒ (1) _{の証明（終わり）}

前ページの結論（再掲）：Gordan_の(2)_{が成り立つ時}V = {^tA−→y | −→y ∈ Rⁿ}^に ついて−→p ∈ R^{mがあって，}−→x ∈ V ⇒ ^t−→x −→p = (−→x ,−→p ) 0_．

・ V _の定義（1_{行目の再掲）から}−→x ∈ V _とは−→x = ^tA−→y _の形．

・ 合わせると， (−→y , A−→p ) = ^t−→y A−→p = ^t−→x −→p 0_．

・ −→y ∈ R^{nは何でも良いので}−→y = −A−→p _と選ぶと

−A−→p ² = (−A−→p , A−→p ) = (−→y , A−→p ) 0

ノルムは非負なのでこれが成り立つのは等号の場合だけ．よって A−→p = 0_．

ノルム（長さ）が0のベクトルは零ベクトルだけだから，A−→p = −→0 _． よって(2)_から(1)を得た（証明終わり）．