トロピカルな計算練習(11)

久々にこのシリーズ。最近またもうこりゃ暑いね。
だいぶ久々なので、何をやっていたか簡単におさらい。

・和をmax演算に置き換えるよ！
・積を和に置き換えるよ！

以上のmax-plusで和積を考える演算をトロピカル演算といいました。

前回まで、いろいろな計算をトロピカル化し、前回は積分をトロピカル化しました。

今回はトロピカルな演算に書き換えた線形代数を見ていこうと思います。
トロピカルな線形代数は、重み付きパスの最短経路の問題なんかに応用されてます。これ、積がplus扱いなんで、普通の積でやるより計算が楽なんでしょうね。

---

線形代数と大仰に言いますが、ベクトルと行列をやるのが今回の目標です。
ベクトルや行列自体書くのは普通の時と変わりません。

$$
\begin{array}{}\begin{pmatrix}2 & 3\end{pmatrix} ,\begin{pmatrix}1\\ 2\\ 0\end{pmatrix} ,\begin{pmatrix}{-} \infty&5 \\0 & 1\end{pmatrix}\end{array}
$$

まあこんな感じの奴らです。

---

余談。
このブログを見ている人はほとんどが理系大学生以上だと思いますが、文系の方や、高校生が見ている可能性もあるので一応補足しますと、高校で習うベクトル(数B→数Cになるんだ、ひっどいね)は横方向で、しかも数をカンマで区切ります。
ところが大学ではカンマ使いませんし、なんなら縦に数字を並べたり、横に並べたりします。
横のベクトルは横ベクトルとか行ベクトル、
縦のベクトルは縦ベクトルとか列ベクトル、
表みたいに書いたのを行列と呼びます。
行列は昔々、数Cにあったので、馴染みのある方も多いかもしれません。(カンマで区切るのは教育的配慮な気がします。でも数Cになるならもうそういう配慮要らなくない？ 行列も復活させようぜ。)
なんで行列なんか作ったのかというと、一つは連立方程式をエイヤッと一撃で倒す技を見つけるためなんです。
あとはそのほかにも便利なことが多々あって、座標上の回転とか、拡大縮小、平行移動もできてなかなか便利だなってことで、数学のみならず物理や情報、統計の世界でも使われます。
なのに、高校では端役扱いなんですね。(こういう考え方もできる。つまりこれをまともに習って使いこなせる僕らは現代社会の特権階級なのだ、と)

これに対して、普通の一つしか成分がない数をスカラーというわけです。
ときに、このスカラーですが、英語だとスケィラーって感じの発音をします。
スカラーと読むのはドイツ語の感じです。ベクトルも英語はヴェクター。
こんな感じで日本の線形代数用語は若干英語とずれてます。
文明開化を感じますね。
スカラー、ベクトル、テンソルと一覧にすると、

$$
\begin{array}{}\begin{matrix}英語&スケィラー&ヴェクター&テンサー\\イタリア語&スカラレ&ヴェットーレ&テンソーレ\\ドイツ語&スカラー&ヴェクトァ&テンゾア\\オランダ語&スカーレェァー&ヴェクトーァ&テンゾァ\\フランス語&スカレェア&ヴェクター&トンセァハ\end{matrix}\end{array}
$$

てな感じです。

---

問題は、このベクトルの演算ですね。
まず普通の和は、

$$
\begin{array}{}\begin{pmatrix}2\\ 3\\ 1\end{pmatrix}+\begin{pmatrix}1\\ 2\\ 0\end{pmatrix}&=&\begin{pmatrix}2+1\\ 3+2\\ 1+0\end{pmatrix}&=&\begin{pmatrix}3\\ 5\\ 1\end{pmatrix}\end{array}
$$

こんなふうに成分ごとに足してやればOKでした。

これをトロピカル化すると、成分ごとにmaxを答えることになります。

$$
\begin{array}{}\begin{pmatrix}2\\ 3\\ 1\end{pmatrix}\oplus\begin{pmatrix}1\\ 2\\0\end{pmatrix}&=&\begin{pmatrix}\max{(2,1)}\\\max{(3,2)}\\\max{(1,0)}\end{pmatrix}&=&\begin{pmatrix}2\\ 3\\ 1\end{pmatrix}\end{array}
$$

---

スカラーとの積は、

$$
\begin{array}{}3\begin{pmatrix}1\\ 2\\ 0\end{pmatrix}&=&\begin{pmatrix}3\cdot 1\\ 3\cdot 2\\ 3\cdot 0\end{pmatrix}&=&\begin{pmatrix}3\\ 6\\ 0\end{pmatrix}\end{array}
$$

全成分に掛けてやるものですね。
これをトロピカルでやると、

$$
\begin{array}{}3\otimes\begin{pmatrix}1\\ 2\\ 0\end{pmatrix}&=&\begin{pmatrix}3\otimes 1\\ 3\otimes 2\\ 3\otimes 0\end{pmatrix}&=&\begin{pmatrix}3+ 1\\ 3+ 2\\ 3+ 0\end{pmatrix}&=&\begin{pmatrix}4\\ 5\\ 3\end{pmatrix}\end{array}
$$

こんな感じになるはずです。

---

さて、ベクトルの内積ですけど、普通のベクトルですと成分ごとの積の和です。
縦横ベクトル表記で内積はこんな感じで書きます。
必ず、横、縦の順で書きます。

$$
\begin{array}{}\begin{pmatrix}2 & 3 &1\end{pmatrix}\begin{pmatrix}1\\ 2\\ 0\end{pmatrix}&=&2\cdot 1+3\cdot 2+1\cdot 0\\&=&2+6+0\\\\&=&8\end{array}
$$

高校だと厄介な書き方をしますが、行列ベクトルで書くとスッキリしますね。
よく大学生のアルバイトで講師をしているとドヤ顔で教えちゃうやつですね。

なので、これをトロピカルにしちゃうとこうなります。

$$
\begin{array}{}\begin{pmatrix}2 & 3 &1\end{pmatrix}\begin{pmatrix}1\\ 2\\ 0\end{pmatrix}&=&(2\otimes 1)\oplus (3\otimes 2) \oplus (1\otimes 0)\\&=&3 \oplus 5 \oplus 1\\\\&=&\max{(3,5,1)}\\\\&=&5\end{array}
$$

各成分和のうち最大を答えるってことですね。

---

同様のことは行列とベクトルでもできます。
普通の行列と縦ベクトルの積は

$$
\begin{array}{}\begin{pmatrix}{a}& {b}\\{c}& {d}\end{pmatrix}\begin{pmatrix}p\\q\end{pmatrix}&=&\begin{pmatrix}{a} p+ {b} q\\{c} p+ {d} q\end{pmatrix}\end{array}
$$

列ベクトルと行列は

$$
\begin{array}{}\begin{pmatrix}s&t\end{pmatrix}\begin{pmatrix}{a}& {b}\\{c}& {d}\end{pmatrix}&=&\begin{pmatrix}s {a} +t {c}&s {b} +t {d}\end{pmatrix}\end{array}
$$

こんな感じで、内積の拡張になってます。
行列どうしの積も同じで、

$$
\begin{array}{}\begin{pmatrix}{a}& {b}\\{c}& {d}\end{pmatrix}\begin{pmatrix}{p}& {q}\\{r}& {s}\end{pmatrix}&=&\begin{pmatrix}{a} {p} + {b} {r}& {a} {q} + {b} {s}\\{c} {p} + {d} {r}& {c} {q} + {d} {s}\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}
$$

さて、こんな演算をしてやるわけですが、見ての通り、結局ベクトルの成分を足して、それの大小関係を行列の成分数だけ見てやることになります。
なので、複雑な行列の(通常)積もみんな通常和と最大にすることができるので、計算のめんどくささはかなり減るのではないかというわけです。

さて、和や積はそのまま書き換えればうまくいくわけですね。ただどうしても差が定義できないのは相変わらずのようです。

ちょっと長くなってきたので今日はここまでにして、次回は単位行列とかその辺がどうなっているのか考えていこうと思います。