トロピカルな計算練習(12)
前回の記事ではベクトルの和、スカラーとの積、内積をトロピカル化しました。
今回は単位行列その他がどんなふうになるのか見ていきます。
まず単位行列ですが、普通の演算→トロピカル演算の対応を考えると、
$$
\begin{array}{}\begin{pmatrix}0&-\infty\\-\infty&0\end{pmatrix}\end{array}
$$
というのが考えられます。
こいつを試しにかけてみますと、
$$
\begin{array}{}\begin{pmatrix}a&b\\c&d\end{pmatrix}\begin{pmatrix}0&-\infty\\-\infty&0\end{pmatrix}&=&\begin{pmatrix}a\oplus -\infty&-\infty\oplus b\\c\oplus-\infty&-\infty\oplus d\end{pmatrix}\\&=&\begin{pmatrix}a&b\\c&d\end{pmatrix}\end{array}
$$
なので、ちゃんと積の単位元になっています。
和のほうは、零行列が欲しいのですが、これも対応からして、
$$
\begin{array}{}\begin{pmatrix}-\infty&-\infty\\-\infty&-\infty\end{pmatrix}\end{array}
$$
になるはずです。
こいつを使ったトロピカル和はたしかに単位的になります。
このトロピカル零行列は積の吸収元的役割もしてくれますね。
さて、そうすると次点で気になるのは逆行列、零因子でしょう。
$$
\begin{array}{}\begin{pmatrix}{a}& {b}\\{c}& {d}\end{pmatrix}\begin{pmatrix}{p}& {q}\\{r}& {s}\end{pmatrix}&=&\begin{pmatrix}\max{({a}+{p},{b}+{r})}&\max{( {a}+{q} , {b} +{s} )}\\\max{({c} +{p} , {d} +{r} )}&\max{({c}+{q} , \textcolor{blue}{d} +{s} )}\end{pmatrix}\end{array}
$$
しかし、このようにトロピカル行列の積演算にはmaxが入ってしまいます。
トロピカル演算ではmaxに対する逆元がないという状況でした。つまり、トロピカルな行列の積も逆行列を特定することは簡単にはできないと言えそうです。
ひとまず１行1列について、$${\max(a+p,b+r)=0}$$であることから推察するに、$${p=-a,r=-\infty}$$あるいは$${p=-\infty,r=-b}$$が考えられますが、いずれも2行1列が$${-\infty}$$になりません。
ということは、元の行列の成分$${a,b,c,d}$$にも$${-\infty}$$が必要です。
たとえば、すごく制限のつく形ですが、$${b=c=-\infty}$$であれば、
$$
\begin{array}{}\begin{pmatrix}{a}& {-\infty}\\{-\infty}& {d}\end{pmatrix}\begin{pmatrix}{-a}& {-\infty}\\{-\infty}& {-d}\end{pmatrix}&=&\begin{pmatrix}\max{(0,-\infty)}&\max{( -\infty , -\infty )}\\\max{(-\infty , -\infty)}&\max{(-\infty , 0 )}\end{pmatrix}\\&=&\begin{pmatrix}0&-\infty\\-\infty&0\end{pmatrix}\end{array}
$$
これはちゃんとトロピカル単位行列になっています。
他にも
$$
\begin{pmatrix}2&-\infty&-\infty\\-\infty&-\infty&3\\-\infty&4&-\infty\end{pmatrix}
$$
こんなのなんかも逆行列を持ちます。
$$
\begin{pmatrix}2&-\infty&-\infty\\-\infty&-\infty&3\\-\infty&4&-\infty\end{pmatrix}\begin{pmatrix}-2&-\infty&-\infty\\-\infty&-\infty&-4\\-\infty&-3&-\infty\end{pmatrix}=\begin{pmatrix}0&-\infty&-\infty\\-\infty&0&-\infty\\-\infty&-\infty&0\end{pmatrix}
$$
つまり、各行各列に一つずつ$${-\infty}$$ではない要素があればよさそうです。
では零因子はというと、こっちの方も難しい。
結局$${-\infty}$$を作るにはどこかの成分に$${-\infty}$$が必要です。ということは、ほとんど$${-\infty}$$な行列でないと零因子が作れない/なれないように思えます。
というわけで、トロピカルな行列も、トロピカル演算の特性を受け継いでいる以上、逆演算、逆元という概念に対しては普通の行列より弱いようです。
逆行列の存在条件に関しては、"数理解析研究所講究録 1020 巻 1997 年 165-179"に記載があるんですが、この段のみ具体的にどんな行列なのかなぜか例がありません。加えて文中で「単位行列」とか「対角行列」とか言っているのですが、例がないが故、成分にでてくる元がトロピカルの単位元なのか通常の単位元なのか分からずちょっと詰まっています。
おそらく上の例のように、置換行列の配置であれば良いということなのでしょうが、確証がないので(私には)断言できません。
よくわからん。なんだよ他の所は例があるのに。
講究録の引用元とされている"Synchronization and Linearity - An Algebra for Discrete Event Systems"に至っては全502ページのうちどこかに条件の記載があるようなのですが、該当の箇所が箇条書きもなにもなくひたすら文書だけで説明しているので、なんにもわからずに放置していたりします。
気になる方は検索してみてください。
まあ、こんなんでちょっと後一枚の壁で手が届かない感じですが、いずれにしてもトロピカル行列の逆行列存在性は普通の行列より厳しいようです。
ただ、だからといってトロピカル行列が「使い物にならない」わけではありません。
「たす、かけるだけ」しかやらないのであれば、上のようなことをあまり気にする必要はないと思います。
(無論トロピカルな連立方程式を行列で解くならそんなことは言っていられません。上で出てきた二つの記事ではトロピカル行列の固有値の話とか、そういうことをちゃんとやってます)
そういう有名な応用例が、重み付きの経路問題です。
この点間の数値は大きいほどそこを通りたい、小さいほど通りたくないというパラメーターだとします。つまり通れない経路は$${-\infty}$$です。
たとえばイメージとして、その道を通るとその数字の枚数だけ一万円札が貰えると思ってはいかがでしょう。つまりAからCに行けば3万円。無理矢理BからDに行くと「罰金無限大円な」と小学生みたいなことになるわけです。
僕らはmax-plusのトロピカルをやっているのでこの表記ですが、min-plusなら「通りたくなさ」になります。
つまり通れない経路は$${\infty}$$ですので、なんとなく電気抵抗とイメージが重なりそうですね。
この時経路ごとのパラメーターを行列にまとめます。
上の図では定義していませんが、自身に帰るルート(つまり動かない)という選択もあるので、これはすべて0にしておきましょう。
$$
\begin{array}{}\begin{pmatrix}0&1&3&2\\1&0&1&-\infty\\3&1&0&1\\2&-\infty&1&0\end{pmatrix}\end{array}
$$
このときこの行列は「点Xにいた人間が点Yに1回で行くコスト」をX行Y列に配置しています。もちろんします。
では二回の移動はどうか。
トロピカルの積でやると、各経路候補のうち一番多くもらえる金額が算出できます。
この方がルートのコスト計算にも応用が効くわけです。
$$
\begin{array}{}\begin{pmatrix}6&4&3&4\\4&2&4&3\\3&4&6&5\\4&3&5&4\end{pmatrix}\end{array}
$$
これをみるとBスタートで二回移動後Bにいる、はやはり獲得賞金が少なくなります。
Dと比べても少ないのは、Dの場合DADの移動はAD=2のおかげでちょっと他の頂点よりお得なのに対しBの周りには1の経路しかないからです。
さて、こんな感じでこのnoteでは過去の記事との整合性も取ることにしてmax-plusに注目したのですが、min-plusもなかなか実用的です。
要するにmax-plusの逆なんですから、最も安い経路が出せることになります。
これは、経路の持つ数を「賞金」に見立てるより、例えば「距離」「運賃」なんかに見立てるとわかりやすいかと思います。
max-plusとmin-plusの移行は、元を全て$${\pm}$$反転させることでできます。
なので繋がっていない経路は$${-\infty}$$から$${\infty}$$に書き変わるので、距離は無限大、なるほど辿り着けるわけがない、なのでちゃんと想像通りの結果になってくれますね。
以上のトロピカル演算による行列積ですけど、一つ注意してほしいのは、このトロピカル行列演算で出てくるのはあくまで経路の最大(最小)値で、どんな順に頂点を踏んできたかの履歴は不明です。
しかし、たとえばどこかのルートの値が変化したとすると、それによって経路の最大最小がどう変化するのか比較的軽い計算で考えることができそうです。
これは希望ですけど、それができるなら、トロピカル行列でトロピカルな連立方程式を解くことで、逆にどんな値をルートが取ればコストを最小化できるかなんてことも計算できるんじゃないでしょうか。
まあその辺は、うえに上げました502ページの記事と闘ってからまた書くことにします。
この記事が気に入ったらサポートをしてみませんか？