「Viability(実現可能性)の判定法〜グラフ理論の応用(産業連関⑤)〜」グラフ理論編その16

本記事の内容
viable(実行可能)の軽い復習と言いたいこと
前回とは別のviabilityの判定法
1. 前回のお話
2. 判定条件
投入係数がviableであるための必要十分条件の一般化
皆様のコメントを下さい！
結

本記事の内容

本記事はviabilityの判定条件を与える記事です。

本記事を読むにあたり、viableについて知っている必要があるため、以下の記事も合わせて御覧ください。

「グラフ理論の応用〜産業連関①(産業連関とは？)〜」【幾何学の基礎シリーズ】グラフ理論編その12

...

viable(実行可能)の軽い復習と言いたいこと

viableとは以下でした。

viable(実行可能)

均衡産出高もである、あるいは投入係数に当たる$\left\{a_{ij}\right\}$がviable(実行可能)とは、レオンチェフ方程式が任意の$b_1,\dots,b_n\ (b_i\geq0)$に対して一意的な解$x_1,\dots,x_n\ (x_i\geq0)$を持つことをいう。

詳しくは、【幾何学の基礎シリーズ】グラフ理論編その13を御覧ください。

そして、言いたいこと

定理0.

ある$b_1>0,\dots,b_n>0$に対してレオンチェフ方程式$(\ast)$が解$x_1\geq0,\dots,x_n\geq0$を持つならば、$\left\{a_{ij}\right\}$はviableである。
条件$(\ast\ast)$の下で、$\left\{a_{ij}\right\}$はviableである。

です。
特に定理0.の2.を述べたいです。
定理0.の1.の証明については【幾何学の基礎シリーズ】グラフ理論編その15を御覧ください。

前回とは別のviabilityの判定法

では、前回とは別のviabilityの判定法について述べます。

前回のお話

前回、

定理0.の1.

レオンチェフ方程式が、ある$\boldsymbol{b}>0$に対して解$\boldsymbol{x}\geq0$を持てば、$A$はviableである。

を証明しました。
この定理の証明は【幾何学の基礎シリーズ】グラフ理論編その15を御覧ください。

この定理0.の(1)はviabilityの判定条件を与えていますが、これとは異なる判定法も存在します。

それを説明するために、以下の定理を明示します。

定理1.

成分が全て非負な$n$次正方行列$A=\left( a_{ij}\right)$は次の性質を満たす固有値$\lambda(A)$を持つ。

$\lambda(A)\geq0$.
$A$の任意の固有値$\lambda$について、$\left|\lambda\right|\leq \lambda(A)$が成り立つ。
$\displaystyle\min_{j=1,\dots,n}\sum_{i=1}^na_{ij}\leq\lambda\leq\max_{j=1,\dots,n}\sum_{i=1}^na_{ij}$

これを見て、「お。なんか見たことあるな。」と思った方、鋭いです。
これはペロン-フロベニウスの定理の一部です。

ペロン-フロベニウスの定理とは以下でした。

Perron-Frobeniusの定理

成分がすべて非負な既約$n$次正方行列$A=\left(a_{ij} \right)$は$A\neq O$であるとき、次の性質を満たす固有値$\lambda(A)$を持つ。

$\lambda(A)>0$であり、$\lambda(A)$は特性根として単根である。さらに成分が正の固有ベクトルを持つ。
$A$の任意の固有値$\lambda$について、$\left|\lambda\right|\leq \lambda(A)$が成り立つ。すなわち$\lambda(A)$は$A$の最大な正の固有値である。
$A\boldsymbol{x}=\lambda\boldsymbol{x}$、$\boldsymbol{x}\geq0$、$\boldsymbol{x}\neq\boldsymbol{0}$であるとき、$\lambda=\lambda(A)$かつ$\boldsymbol{x}>0$が成り立つ。
$\displaystyle\min_{j=1,\dots,n}\sum_{i=1}^na_{ij}\leq\lambda(A)\leq\max_{j=1,\dots,n}\sum_{i=1}^na_{ij}$、$\displaystyle\min_{i=1,\dots,n}\sum_{j=1}^na_{ij}\leq\lambda(A)\leq\max_{i=1,\dots,n}\sum_{j=1}^na_{ij}$

ペロン-フロベニウスの定理の証明は【幾何学の基礎シリーズ】グラフ理論編その9を御覧ください。

$n=2$の場合、
$$
\det\left(xI-A \right)=x^2-\left( a_{11}+a_{22}\right)x+\left( a_{11}a_{22}-a_{12}a_{21}\right)
$$
であり、これは以前登場した二次関数$f(x)$そのものです。
つまり、$A$の固有値は二次方程式$f(x)=0$の解です。
故に、$n=2$のとき定理の主張(1)と(2)が成り立つ、と考えることも出来ます。

判定条件

いよいよviabilityの判定条件を述べます。

定理2.

非負行列$A$がviableであるための必要十分条件は、$\lambda(A)<1$となることである。

この定理2.は、以前証明した以下の命題の一般化です。

命題3.

方程式 \begin{eqnarray} &&a_{11}x_1+a_{12}x_2+b_1=x_1\\ &&a_{21}x_1+a_{22}x_2+b_2=x_2 \end{eqnarray} において、任意の$b_1.b_2\geq0$に対して一意的な非負解$x_1,x_2$を持つための必要十分条件は、$\lambda_1<1$である。

命題3.の証明は【幾何学の基礎シリーズ】グラフ理論編その14を御覧ください。

命題2.の証明

証明の一部は定理0.の(1)と似ています。

$\lambda(A)<1$としましょう。
このとき、$I-A$は逆行列を持つから、$\boldsymbol{x}=\left( I-A\right)^{-1}\boldsymbol{b}$とします。
勿論、$\boldsymbol{x}$は$\boldsymbol{x}=A\boldsymbol{x}+\boldsymbol{b}$を満たしています。

ここで、次の事実を使います。

補題4.

$\boldsymbol{x}=A\boldsymbol{x}+\boldsymbol{b}$の下で、任意の自然数$k$について、 $$ \boldsymbol{x}=A^k\boldsymbol{x}+A^{k-1}\boldsymbol{b}+A^{k-2}\boldsymbol{b}+\cdots+A\boldsymbol{b}+\boldsymbol{b}\tag{2} $$ が成り立つ。

補題4.の証明は【幾何学の基礎シリーズ】グラフ理論編その15を御覧ください。

補題4.と$\displaystyle\lim_{k\to\infty}A^k=O$(これについては【幾何学の基礎シリーズ】グラフ理論編その15を参照して下さい)から
\begin{eqnarray} \boldsymbol{x}&=&\lim_{k\to\infty}A^k\boldsymbol{x}+\lim_{k\to\infty}\left(A^{k-1}+A^{k-2}+\cdots+A+I \right)\boldsymbol{b}\\
&=&\lim_{k\to\infty}\left(A^{k-1}+A^{k-2}+\cdots+A+I \right)\boldsymbol{b}
\end{eqnarray}
となります。

任意の$k$に対して、
$$
\left(A^{k-1}+A^{k-2}+\cdots+A+I \right)\boldsymbol{b}\geq0
$$
だから、
$$
\lim_{k\to\infty}\left(A^{k-1}+A^{k-2}+\cdots+A+I \right)\boldsymbol{b}\geq0
$$
です。
故に、$\boldsymbol{x}\geq0$が得られ、$A$はviableです。

逆に、$A$がviableだとしましょう。
$\lambda(A)\geq0$としたとき、矛盾が生じることを見ます(背理法！)。
まず、$\lambda(A)\neq1$であることは、$I-A$が逆行列を持つことから分かるので、$\lambda(A)>1$です。

$A^k$の$(i,j)$成分を$a_{ij}^{(k)}$で表すことにします。
仮定の下で、$a_{ij}^{(k)}$が有界でないような$i,j$が存在します。
実際、もし全ての$i,j$に対して$a_{ij}^{(k)}$が有界であれば、任意の可逆な行列(逆行列を持つような行列)$P$に対して、$P^{-1}AP$の全ての成分もまた有界です。
特に、$PA^kP^{-1}$が上三角行列となるように$P$を取ります。

どうしてこのような$P$を取れるのか、というと、以下が成り立つからです。

定理5.(固有値と三角化)

$n$次正方行列$A$が、重複も含めて$n$個の固有値$\lambda_1,\dots,\lambda_n$をもつとき(すなわち、$\varphi_A(t)=(\lambda_1-t)\cdots(\lambda_n-t)$となるとき)、$A$は適当な正則行列$P$によって次の形に三角化される。 $$ P^{-1}AP= \begin{pmatrix} \lambda_1&&&\huge{*}\\ &\lambda_2&&\\ &&\ddots&\\ \huge{O}&&&\lambda_n \end{pmatrix} $$

定理5.の証明は【線型代数学の基礎シリーズ】固有値編その3を御覧ください。

さて、$PA^kP^{-1}$が上三角行列となるように$P$を取るので、
$$
P^{-1}AP=
\begin{pmatrix}
\lambda(A)&\ast&\ast&\cdots&\ast\\
&\lambda_1&\ast&\cdots&\ast\\
&&\lambda_2&\cdots&\ast\\
&&&\ddots&\vdots\\
\huge{O}&&&&\lambda_{n-1}
\end{pmatrix}
$$
です。
ここで、$\left( P^{-1}AP\right)^k=P^{-1}A^kP$を使うと、
$$
P^{-1}A^kP=
\begin{pmatrix}
\lambda(A)^k&\ast&\ast&\cdots&\ast\\
&\lambda_1^k&\ast&\cdots&\ast\\
&&\lambda_2^k&\cdots&\ast\\
&&&\ddots&\vdots\\
\huge{O}&&&&\lambda_{n-1}^k
\end{pmatrix}
$$
だから、これは有界ではありません。
これは矛盾です。

さて、$\boldsymbol{b}>0$として、$\boldsymbol{x}=A\boldsymbol{x}+\boldsymbol{b}$の解$\boldsymbol{x}\geq0$が存在するから、
$$
\boldsymbol{x}=A^k\boldsymbol{x}+\left(A^{k-1}+A^{k-2}+\cdots+A+I \right)\boldsymbol{b}
$$
において、$k\to\infty$とすると、右辺のある成分は有界ではありません。
一方で、右辺は$k$に依存せずに一定だから矛盾です。

命題2.の証明終わり

命題2.の系として2つ紹介します。

系6.

非負行列$A~\left(a_{ij}\right)$が条件 $$ \max_{j=1,\dots,n}\sum_{i=1}^na_{ij}<1 $$ を満たしていれば、$A$はviableである。

系7.

viableな$A$に対するレオンチェフ逆行列$\left( I-A\right)^{-1}$は非負行列である。

投入係数がviableであるための必要十分条件の一般化

以下の以前証明した命題も一般化されます。

命題8.

投入係数$\left\{a_{ij}\right\}$がviableであるための必要十分条件は \begin{eqnarray} 1-a_{11}>0,\\ 1-a_{11}-a_{22}+a_{11}a_{22}-a_{12}a_{21}>0 \end{eqnarray} である。

命題8.の証明は【幾何学の基礎シリーズ】グラフ理論編その14を御覧ください。

さて、命題8.を一般化するに当たり、次の一般的な定理を使います。

定理9.

$B=\left( b_{ij}\right)$を$n$次の正方行列で、$i\neq j$に対して$b_{ij}\leq0$を満たすとする。このとき、次の3条件は同値である。

$B\boldsymbol{x}=\boldsymbol{c}$は、ある$\boldsymbol{c}>0$に対して解$\boldsymbol{x}\geq0$を持つ。
$B\boldsymbol{x}=\boldsymbol{c}$は、任意の$\boldsymbol{c}\geq0$に対して解$\boldsymbol{x}\geq0$を持つ。
$B$の主小行列式は全て正である(Hawkins-Simon(ホーキンス-サイモン)条件)。

非負行列$A$に対して、$B=I-A$の$(i,j)$成分は$i\neq j$のとき非正です。
従って、次の系を得ます。

系10.

非負行列$A$がviableであるための必要十分条件は$I-A$がホーキンス-サイモン条件を満たすことである。

この系10.が命題8.の一般化です。
そして、定理0.の2.です。

系$n=2$のときは、ホーキンス-サイモン条件が命題8.の条件と一致します。

定理9.における1.と2.の同値性の証明は、実は定理0.の1.に帰着させることが出来ます。
$A=I-\varepsilon B$として、$\varepsilon>0$を十分小さく取ると、$A\geq0$とすることが出来ます。
$\varepsilon B=I-A$だから、$\boldsymbol{x}=A\boldsymbol{x}+\boldsymbol{b}$を仮定すると、
$$
\left(I-A \right)\varepsilon^{-1}\boldsymbol{x}=\varepsilon B\varepsilon^{-1}\boldsymbol{x}=B\boldsymbol{x}=\boldsymbol{c}
$$
となります。
故に、$A$は定理0.の(1)の条件を満たし、任意の$\boldsymbol{c}\geq0$に対して$\left(I-A \right)\boldsymbol{y}=\boldsymbol{c}$を満たすような$\boldsymbol{y}\geq0$が存在することになります。
$\boldsymbol{x}=\varepsilon\boldsymbol{y}(\geq0)$とおけば、
$$
B\boldsymbol{x}=\varepsilon^{-1}\left(I-A \right)\varepsilon\boldsymbol{y}=\left( I-A\right)\boldsymbol{y}=\boldsymbol{c}
$$
となって、定理9.の2.が示されたことになります。
今回は定理9の2.と3.の同値性は省略します。

定理11.

$A$をviableとする。$\boldsymbol{x}_0$を任意に与え、ベクトルの列$\boldsymbol{x}_1,\boldsymbol{x}_2,\dots,\boldsymbol{x}_n$を帰納的に $$ \boldsymbol{x}_{n+1}=A\boldsymbol{x}_n+\boldsymbol{b} $$ により定める。このとき極限 $$ \lim_{n\to\infty}\boldsymbol{x}_n=\boldsymbol{x} $$ が存在し、しかも$\boldsymbol{x}$はレオンチェフ方程式の解である。

定理11.の証明

数学的帰納法で
$$
\boldsymbol{x}_n=A^n+\left( A^{n-1}+A^{n-2}+\cdots+A+I\right)\boldsymbol{b}\tag{$\alpha$}
$$
を証明しましょう。
$n=1$のときは、$\boldsymbol{x}_1=A\boldsymbol{x}_0+\boldsymbol{b}$だから正しいです。
$n$のときに正しいと仮定すると、
\begin{eqnarray}
\boldsymbol{x}_{n+1}&=&A\boldsymbol{x}_n+\boldsymbol{b}\\
&=&A\left(A^n\boldsymbol{x}_0+\left( A^{n-1}+A^{n-2}+\cdots+A+I\right)\boldsymbol{b}\right)+\boldsymbol{b}\\
&=&A^{n+1}\boldsymbol{x}_0+\left(A^n+\cdots+A+I \right)\boldsymbol{b}
\end{eqnarray}
が得られるため、$n+1$のときも正しいです。
従って、全ての$n$で正しいです。

$A$はviableだから、
\begin{eqnarray}
&&\lim_{n\to\infty}A^n=O,\\
&&\lim_{n\to\infty}\left( A^{n-1}+A^{n-2}+\cdots+A+I\right)=\left(I-A \right)^{-1}
\end{eqnarray}
であり、これを$(\alpha)$に適用すれば、
$$
\lim_{n\to\infty}\boldsymbol{x}_n=\left( I-A\right)^{-1}\boldsymbol{b}
$$
です。

定理11.の証明終わり

皆様のコメントを下さい！

今回から数学者の逸話を軽く紹介します。

第一回目はアリストテレス(紀元前384-紀元前322)です。

アリストテレスはソクラテス、プラトンに並ぶ古代ギリシャの最大の哲学者、博物学者でもあります。
学園アカデミアにおいて、プラトンに20年間師事、師の死後マケドニアの王子(後のアレキサンダー大王又はアレクサンドロス3世)の家庭教師になった時期もあります。

その後、アテネにリュケイオンという学校を建てて、そこで形而上学、以前学、論理学、詩学、倫理学、政治学、博物学など、多岐にわたる主題について多くの著述を行いました。
この学校の学生は逍遥学派(しょうようがくは)と呼ばれます。
ヨーロッパ中世までアリストテレスの思弁的物理及び有限的宇宙観は大きな影響を与え、16世紀になって漸くコペルニクスやガリレオ・ガリレイによって乗り越えられることになります。

数学上の直接の寄与は無いようですが、論理学の創始者として数学に間接的な影響を与えました。
また、演繹科学の成り立ちを明確に意識し、科学理論は少数の前提から理論のすべての結論を演繹的に導く営みであるとしました。
アリストテレスのこのような観点はユークリッドの原論で現実化されました。
なお、アリストテレスによる論理学的著作は、6世紀にオルガノン(Organon)と命名されました。

プラトン哲学が宗教的超越的であるのと比較して、アリストテレスの哲学は世俗的自然主義的だそうです。
この双方の哲学は、キリスト教信仰とギリシャ以降の学問との綜合を目指したスコラ哲学に取り入れられました。
特にプラトン主義はアウグスチヌス(354-480)によりキリスト教と結び付けられ、アリストテレス主義はトマス・アクィナス(1225-1274)によりキリスト教神学のもとに体系づけられました。

ルネサンス期の科学思想においても、特に「世界」を理解しようとする動機の上では(たとえそれが「負の偏向」に力を貸したとしても)、プラトンやアリストテレスの影響を無視することはできないようです。

如何でしたか？
数学に直接の貢献は無いにせよ、数学を考えるというその論理だったりと間接的に大きな影響を与えた偉人ですね。

皆様はアリストテレスについてどう思いますか？
ここに書かれている事以外でアリストテレスについてご存知のことがあれば是非コメントで教えて下さい！

結

今回は、投入係数行列がviableであるための判定法を一般化して解説しました。
viableであるための判定法は複数ありますが、viableという概念があって、それを調べることで現実的にモデル化が可能か、ということを吟味し、世の中に還元しています。

次回はレオンチェフ方程式を用いて、経済分析を行う方法について簡単に解説します。

乞うご期待！
質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、「定理〇〇の△△が分からない！」などいただければ全てお答えします！
お問い合わせの内容にもよりますが、ご質問はおおよそ３日以内にお答えします。
もし直ちに回答が欲しければその旨もコメントでお知らせください。直ちに対応いたします。

グラフ理論についてより詳しく知りたい方は以下を参考にすると良いと思います！