少し前に、トロピカル半環上の行列を用いてグラフの最短経路の距離を計算することができるという 記事 が話題になりました。この記事では、トロピカル半環上の行列の計算の背景にある代数理論である半環上の加群について解説しようと思います。
線形代数のもっとも基本的な要素は環上の加群の理論だと思われがちだけど、実際には半環上の加群の理論なのではないでしょうか、という話。
さっそくですが、半環の定義を見てみましょう。
$A$が半環とは、$A$が以下を満たす乗法と加法を持つときをいう。
実はこの定義、環の定義とほとんど同じものです。実際に見比べてみましょう。
$A$が環とは、$A$が以下を満たす乗法と加法を持つときときをいう。
異なる部分を強調してみました。異なる部分は、半環は加法に関して可換モノイドであることを要求しているのに対して、環は加法に関して可換群であることを要求しているという点です。このことから、環は引き算を持つような半環であるということができます。（実際には環のほうがメジャーなので、半環は引き算を持たない環であるといわれることのほうが多いのですが......）。また、環においては$0$を掛けると$0$になるというのは他の条件から従うので、上の定義ではこの条件に括弧をつけています。
半環の圏を考えることができます。
$f:A \to B$が半環の準同型とは、$A$と$B$が半環であって$f$が乗法および加法に関してモノイド準同型であるときをいう。半環を対象として半環の準同型を射とする圏を$\mathsf{SRing}$と書く。
半環の例をいくつか見ていきましょう。
環は半環です。上の定義から明らかですね。
自然数全体$\mathbb{N} = \{ 0,1,2,\cdots\}$は通常の演算で半環です。これは$\mathsf{SRing}$の始対象です。最も基本的な半環です。
半環の圏における$\mathbb{N}$は、環の圏における$\mathbb{Z}$の類似とみなせます。半環という名前もこの例をみると納得できます。というのも、$\mathbb{N}$は$\mathbb{Z}$の半分だからです（インフォーマルな言い方ですが、伝わると思います）。このような例を見ると、半環と環は大体同じようなものという気がしてきます。ですが、実際には、環の世界には対応物が存在しない半環もあります。その最も代表的な例がトロピカル半環です。
$\mathbb{R} \sqcup \{ \infty \}$は、乗法を通常の加法、加法を小さい方をとる操作によって定めると、半環になります。
一見すると不思議な演算の定め方ですが、半環の定義中の条件がすべて成り立つことがわかります。トロピカル半環を考えるときは、記法上の紛らわしさを軽減させるために、乗法を$+$と書いて、加法を$\oplus$と書くことが多いです。トロピカル半環における計算の例をふたつほど挙げておきます。
\begin{align}
&(3 \oplus 4) + 9 = \min(3,4) + 9 = 3+9 = 12\\
&(3 \oplus \infty) + \infty = \min(3,\infty) + \infty = 3+\infty = \infty
\end{align}
以下では半環$A$をひとつ固定します。
以下の条件を満たす$V$を右$A$-加群という。
右$A$-加群の定義中の作用に関する三番目の条件を
\begin{align*}
\forall a,b \in A,\ \forall x \in V,\ a \ast (b \ast x) = (a \cdot b) \ast x
\end{align*}
に変えたものは左$A$-加群と呼ばれます。$A$の乗法が可換のときは、右$A$-加群と左$A$-加群は同じものです。半環$A$に対して乗法の向きを変えることで反対半環$A^{\mathrm{op}}$が定義されるということを知っていれば、右$A$-加群とは左$A^{\mathrm{op}}$-加群であるということができます。
以下では単に$A$-加群といったら右$A$-加群のこととします。
$V$と$W$を$A$-加群とする。以下の条件を満たす写像$f:V \to W$を$A$-線形写像という。
$A$-加群と$A$-線形写像は圏をなす。この圏を${}_{A}\mathsf{Mod}$と書く。
半環$A$自身は、作用を$a \ast x = x \cdot a$と定めることで右$A$-加群の構造を持ちます。
$M$を加法に関する可換モノイドとします。作用$\mathbb{N} \times M \to M$を$a \ast x = x + \dots + x$ ($a$個の和)で定めることで、$M$は自然に$\mathbb{N}$-加群の構造を持ちます。
$I$と$J$を集合とする。写像$M: I \times J \to A$のことを$A$上の$I \times J$行列という。$M(i,j)=a_{ij}$のとき、$M=(a_{ij})_{(i,j) \in I \times J}$と書く。
$A$上の$I \times J$行列$M$が与えられたとき、各$i \in I$について$M$を$\{ i\} \times J$に制限して得られる行列を$M$の$i$行といい、各$j \in J$について$M$を$I \times \{j \}$に制限して得られる行列を$M$の$j$列といいます。
$m$と$n$が自然数で$I=\{0,\dots,m-1 \}$および$J= \{0,\dots,n-1 \}$であるとき、$A$上の$I \times J$行列のことを$A$上の$m \times n$行列といいます。$A$上の$m \times n$行列は、$A$の元を長方形の配列として縦に$m$行、横に$n$列並べたものとして表されます。
$\left( \begin{array}{cc} 3 & 1 & 4\\ 0 & 3 & 5 \end{array} \right)$は$\mathbb{N}$上の$2 \times 3$行列です。
$M=(a_{ij})_{(i,j) \in I \times J}$を$A$上の$I \times J$行列として、$N=(b_{jk})_{(j,k) \in I \times J}$を$A$上の$J \times K$行列とする。任意の$k\in K$について$N$の$k$列は有限の台を持つとする。このとき、$M$と$N$の積$MN$を
\begin{align*}
MN = \left( \sum_{j \in J} a_{ij}\cdot b_{jk} \right)_{(i,k) \in I \times K}
\end{align*}
で定まる$A$上の$I \times K$行列とする。
線形代数において最も重要な事実のひとつは、線形写像に関する計算が行列の積で記述されるということです。このことについて見てみましょう。
基本となるのは基底という概念です。
$V$を$A$-加群とする。以下の条件を満たす$V$の元の族$(v_i)_{i \in I}$を基底という。
$V$を基底$(v_i)_{i \in I}$を持つ$A$-加群とします。このとき、基底の定義より、任意の$x \in V$は$x = \sum_{i \in I} x_i \ast v_i$と一意的に表せます。$(x_i)_{i \in I}$は$I \times 1$行列と思うことができます。この行列を$M(x)$と書くことにします($M$はmatrixの頭文字です)。行列$M(x)$を$x$の$(v_i)_{i \in I}に関する$列ベクトルと呼ぶこともあります。列ベクトルであることを強調したい場合は、$(x_i)_{i \in I}$を$(x_{i0})_{(i,0) \in I \times 1}$と書くことにします。
$V$および$W$を$A$-加群として、これらはそれぞれ基底$(v_i)_{i \in I}$および$(w_j)_{j \in J}$を持つとする。$f:V \to W$を$A$-線形写像とする。このとき、基底$(v_i)_{i \in I},\ (w_j)_{j \in J}$に関する線形写像$f$の表現行列$M(f) = (a_{ji})_{(j,i) \in J \times I}$を
\begin{align}
f(v_i) = \sum_{j \in J} a_{ji} \ast w_j
\end{align}
で定める。
言い換えると、$M(f)$の$i$列は$M(f(v_i))$の$(w_j)_{j \in J}$に関する列ベクトルと等しいということです。
$V$および$W$を$A$-加群として、これらはそれぞれ基底$(v_i)_{i \in I}$および$(w_j)_{j \in J}$を持つとする。$f:V \to W$を$A$-線形写像とする。このとき
\begin{align}
M(f(x)) = M(f)M(x)
\end{align}
が成り立つ。
$M(f)=(a_{ji})_{(j,i) \in J \times I}$とします。基底を用いて$x = \sum_{i \in I} x_{i0} \ast v_i$および$f(x) = \sum_{j \in J} y_{j0} \ast w_j$と表します。
このとき、
\begin{align*}
f(x) &= f\left(\sum_{i \in I} x_{i0} \ast v_i \right) &&\text{}\\
&= \sum_{i \in I} x_{i0} \ast f(v_i) &&\text{(線形写像の定義)}\\
&= \sum_{i \in I} x_{i0} \ast \left(\sum_{j \in J} a_{ji} \ast w_j \right) &&\text{(表現行列の定義)}\\
&= \sum_{j \in J} \left( \sum_{i \in I} a_{ji} \cdot x_{i0} \right) \ast w_j &&\text{(加群の定義)}
\end{align*}
となります。よって$y_{j0}= \sum_{i \in I}a_{ji} \cdot x_{i0}$です。右辺は行列の積の定義より$M(f)M(x)$の$j$成分と等しいので、定理が従います。
$U$, $V$および$W$を$A$-加群として、これらはそれぞれ基底$(u_i)_{i \in I}$, $(v_j)_{j \in J}$および$(w_k)_{k \in K}$を持つとする。$f:U \to V$および$g:V \to W$を$A$-線形写像とする。$M(f)$を基底$(u_i)_{i \in I},\ (v_j)_{j \in J}$に関する$f$の表現行列として、$M(g)$を基底$(v_j)_{j \in J},\ (w_k)_{k \in K}$に関する$g$の表現行列とする。このとき
\begin{align*}
M(g \circ f) = M(g)M(f)
\end{align*}
が成り立つ。
$x \in U$を任意にとります。すると、一つ目の定理より
\begin{align*}
M(g \circ f)M(x) = M((g \circ f)(x)) = M(g)M(f(x)) = M(g)M(f)M(x)
\end{align*}
となります。$i \in I$を任意にとります。上の式で$x = u_i$とすると、$M(g \circ f)$と$M(g)M(f)$の$i$列が等しいことがわかります。$i$は任意なので、定理が従います。
上の定理は右$A$-加群に関するものですが、左$A$-加群versionを考えることもできます。その場合は、上のふたつの定理はそれぞれ
\begin{align*}
{}^t M(f(x)) &= {}^t M(x){}^t M(f) \\
{}^t M(g \circ f) &= {}^t M(f){}^t M(g)
\end{align*}
なります。ここで、行列$M$に対して${}^t M$は$M$の転置行列です。
半環上の行列の背景にある代数理論として、半環の加群について見てきました。
環ではなく半環を考えるのには次のようなメリットがあります。
ひとつめについては、「はじめに」で紹介した記事のように計算機科学にも応用があるように、わかりやすいメリットといえます。ふたつめについて例を挙げて説明しようと思います。
$\mathcal{P}$を整数の分割の集合としたときに、各分割$\lambda \in \mathcal{P}$に対してSchur関数と呼ばれる無限変数の対称多項式$s_{\lambda} \in \mathbb{N}[x_1,x_2,\dots]$が定まります。Schur関数で生成される半環$\mathbb{N}[s_{\lambda}]_{\lambda \in \mathcal{P}}$を$\mathbb{N}$-加群とみなしたとき、Schur関数$(s_{\lambda})_{\lambda \in \mathcal{P}}$は$\mathbb{N}[s_{\lambda}]_{\lambda \in \mathcal{P}}$の基底を与えることが知られています。これは$(s_{\lambda})_{\lambda \in \mathcal{P}}$が$\mathbb{Z}$-加群$\mathbb{Z}[s_{\lambda}]_{\lambda \in \mathcal{P}}$の基底であるという事実よりずっと非自明な事実で、その背景には対称群の表現論やリー代数の表現論といった理論があることが知られています。Schur関数ついては参考文献で挙げる『Symmetric Functions and Hall Polynomials』という本に詳しく書いてあります。