はじめに
少し前に、トロピカル半環上の行列を用いてグラフの最短経路の距離を計算することができるという
記事
が話題になりました。この記事では、トロピカル半環上の行列の計算の背景にある代数理論である半環上の加群について解説しようと思います。
端的なまとめ
線形代数のもっとも基本的な要素は環上の加群の理論だと思われがちだけど、実際には半環上の加群の理論なのではないでしょうか、という話。
半環
さっそくですが、半環の定義を見てみましょう。
半環
が半環とは、が以下を満たす乗法と加法を持つときをいう。
- は乗法に関してを単位元とするモノイドである
- は加法に関してを単位元とする可換モノイドである
- 分配法則が成り立つ
- を掛けるとになる
実はこの定義、環の定義とほとんど同じものです。実際に見比べてみましょう。
環
が環とは、が以下を満たす乗法と加法を持つときときをいう。
- は乗法に関してを単位元とするモノイドである
- は加法に関してを単位元とする可換群である
- 分配法則が成り立つ
- (を掛けるとになる)
異なる部分を強調してみました。異なる部分は、半環は加法に関して可換モノイドであることを要求しているのに対して、環は加法に関して可換群であることを要求しているという点です。このことから、環は引き算を持つような半環であるということができます。(実際には環のほうがメジャーなので、半環は引き算を持たない環であるといわれることのほうが多いのですが......)。また、環においてはを掛けるとになるというのは他の条件から従うので、上の定義ではこの条件に括弧をつけています。
半環の圏を考えることができます。
半環の圏
が半環の準同型とは、とが半環であってが乗法および加法に関してモノイド準同型であるときをいう。半環を対象として半環の準同型を射とする圏をと書く。
半環の例をいくつか見ていきましょう。
自然数
自然数全体は通常の演算で半環です。これはの始対象です。最も基本的な半環です。
半環の圏におけるは、環の圏におけるの類似とみなせます。半環という名前もこの例をみると納得できます。というのも、はの半分だからです(インフォーマルな言い方ですが、伝わると思います)。このような例を見ると、半環と環は大体同じようなものという気がしてきます。ですが、実際には、環の世界には対応物が存在しない半環もあります。その最も代表的な例がトロピカル半環です。
トロピカル半環
は、乗法を通常の加法、加法を小さい方をとる操作によって定めると、半環になります。
一見すると不思議な演算の定め方ですが、半環の定義中の条件がすべて成り立つことがわかります。トロピカル半環を考えるときは、記法上の紛らわしさを軽減させるために、乗法をと書いて、加法をと書くことが多いです。トロピカル半環における計算の例をふたつほど挙げておきます。
半環上の加群
以下では半環をひとつ固定します。
半環上の加群
以下の条件を満たすを右-加群という。
- は加法を持ち、その加法に関して可換モノイドである
- は以下の条件を満たす作用を持つ
右-加群の定義中の作用に関する三番目の条件を
に変えたものは左-加群と呼ばれます。の乗法が可換のときは、右-加群と左-加群は同じものです。半環に対して乗法の向きを変えることで反対半環が定義されるということを知っていれば、右-加群とは左-加群であるということができます。
以下では単に-加群といったら右-加群のこととします。
線形写像
とを-加群とする。以下の条件を満たす写像を-線形写像という。
半環自身は、作用をと定めることで右-加群の構造を持ちます。
を加法に関する可換モノイドとします。作用を (個の和)で定めることで、は自然に-加群の構造を持ちます。
半環上の行列
半環上の行列
とを集合とする。写像のことを上の行列という。のとき、と書く。
上の行列が与えられたとき、各についてをに制限して得られる行列をの行といい、各についてをに制限して得られる行列をの列といいます。
とが自然数でおよびであるとき、上の行列のことを上の行列といいます。上の行列は、の元を長方形の配列として縦に行、横に列並べたものとして表されます。
行列の積
を上の行列として、を上の行列とする。任意のについての列は有限の台を持つとする。このとき、との積を
で定まる上の行列とする。
線形代数において最も重要な事実のひとつは、線形写像に関する計算が行列の積で記述されるということです。このことについて見てみましょう。
基本となるのは基底という概念です。
基底
を-加群とする。以下の条件を満たすの元の族を基底という。
- 任意のについて、有限の台を持つの元の族であって、を満たすものが一意に存在する。
を基底を持つ-加群とします。このとき、基底の定義より、任意のはと一意的に表せます。は行列と思うことができます。この行列をと書くことにします(はmatrixの頭文字です)。行列をの列ベクトルと呼ぶこともあります。列ベクトルであることを強調したい場合は、をと書くことにします。
線形写像の表現行列
およびを-加群として、これらはそれぞれ基底およびを持つとする。を-線形写像とする。このとき、基底に関する線形写像の表現行列を
で定める。
言い換えると、の列はのに関する列ベクトルと等しいということです。
線形写像による像は行列と列ベクトルの積
およびを-加群として、これらはそれぞれ基底およびを持つとする。を-線形写像とする。このとき
が成り立つ。
とします。基底を用いておよびと表します。
このとき、
となります。よってです。右辺は行列の積の定義よりの成分と等しいので、定理が従います。
線形写像の合成は行列の積
, およびを-加群として、これらはそれぞれ基底, およびを持つとする。およびを-線形写像とする。を基底に関するの表現行列として、を基底に関するの表現行列とする。このとき
が成り立つ。
を任意にとります。すると、一つ目の定理より
となります。を任意にとります。上の式でとすると、との列が等しいことがわかります。は任意なので、定理が従います。
上の定理は右-加群に関するものですが、左-加群versionを考えることもできます。その場合は、上のふたつの定理はそれぞれ
なります。ここで、行列に対してはの転置行列です。
おわりに
半環上の行列の背景にある代数理論として、半環の加群について見てきました。
環ではなく半環を考えるのには次のようなメリットがあります。
- トロピカル半環という環の世界に対応物がない対象を扱える。
- 上で成り立つことが実際には上で成り立つということが「深い定理」として現れることがある。
ひとつめについては、「はじめに」で紹介した記事のように計算機科学にも応用があるように、わかりやすいメリットといえます。ふたつめについて例を挙げて説明しようと思います。
を整数の分割の集合としたときに、各分割に対してSchur関数と呼ばれる無限変数の対称多項式が定まります。Schur関数で生成される半環を-加群とみなしたとき、Schur関数はの基底を与えることが知られています。これはが-加群の基底であるという事実よりずっと非自明な事実で、その背景には対称群の表現論やリー代数の表現論といった理論があることが知られています。Schur関数ついては参考文献で挙げる『Symmetric Functions and Hall Polynomials』という本に詳しく書いてあります。