5
大学数学基礎解説
文献あり

半環上の線形代数

1101
1

はじめに

少し前に、トロピカル半環上の行列を用いてグラフの最短経路の距離を計算することができるという 記事 が話題になりました。この記事では、トロピカル半環上の行列の計算の背景にある代数理論である半環上の加群について解説しようと思います。

端的なまとめ

線形代数のもっとも基本的な要素は環上の加群の理論だと思われがちだけど、実際には半環上の加群の理論なのではないでしょうか、という話。

半環

さっそくですが、半環の定義を見てみましょう。

半環

Aが半環とは、Aが以下を満たす乗法と加法を持つときをいう。

  • Aは乗法に関して1を単位元とするモノイドである
    • x,y,zA, x(yz)=(xy)z
    • xA, x1=1x=x
  • Aは加法に関して0を単位元とする可換モノイドである
    • x,y,zA, x+(y+z)=(x+y)+z
    • xA, x+0=0+x=x
    • x,yA, x+y=y+x
  • 分配法則が成り立つ
    • x,y,zA, x(y+z)=xy+xz
    • x,y,zA, (x+y)z=xz+yz
  • 0を掛けると0になる
    • xA, x0=0x=0

実はこの定義、環の定義とほとんど同じものです。実際に見比べてみましょう。

Aが環とは、Aが以下を満たす乗法と加法を持つときときをいう。

  • Aは乗法に関して1を単位元とするモノイドである
  • Aは加法に関して0を単位元とする可換である
  • 分配法則が成り立つ
  • (0を掛けると0になる)

異なる部分を強調してみました。異なる部分は、半環は加法に関して可換モノイドであることを要求しているのに対して、環は加法に関して可換群であることを要求しているという点です。このことから、環は引き算を持つような半環であるということができます。(実際には環のほうがメジャーなので、半環は引き算を持たない環であるといわれることのほうが多いのですが......)。また、環においては0を掛けると0になるというのは他の条件から従うので、上の定義ではこの条件に括弧をつけています。

半環の圏を考えることができます。

半環の圏

f:ABが半環の準同型とは、ABが半環であってfが乗法および加法に関してモノイド準同型であるときをいう。半環を対象として半環の準同型を射とする圏をSRingと書く。

半環の例をいくつか見ていきましょう。

環は半環です。上の定義から明らかですね。

自然数

自然数全体N={0,1,2,}は通常の演算で半環です。これはSRingの始対象です。最も基本的な半環です。

半環の圏におけるNは、環の圏におけるZの類似とみなせます。半環という名前もこの例をみると納得できます。というのも、NZの半分だからです(インフォーマルな言い方ですが、伝わると思います)。このような例を見ると、半環と環は大体同じようなものという気がしてきます。ですが、実際には、環の世界には対応物が存在しない半環もあります。その最も代表的な例がトロピカル半環です。

トロピカル半環

R{}は、乗法を通常の加法、加法を小さい方をとる操作によって定めると、半環になります。

一見すると不思議な演算の定め方ですが、半環の定義中の条件がすべて成り立つことがわかります。トロピカル半環を考えるときは、記法上の紛らわしさを軽減させるために、乗法を+と書いて、加法をと書くことが多いです。トロピカル半環における計算の例をふたつほど挙げておきます。
(34)+9=min(3,4)+9=3+9=12(3)+=min(3,)+=3+=

半環上の加群

以下では半環Aをひとつ固定します。

半環上の加群

以下の条件を満たすVA-加群という。

  • Vは加法を持ち、その加法に関して可換モノイドである
  • Vは以下の条件を満たす作用A×VV, (a,x)axを持つ
    • aA, x,yV, a(x+y)=ax+ay
    • a,bA, xV, (a+b)x=ax+bx
    • a,bA, xV, a(bx)=(ba)x
    • xV, 1x=x

A-加群の定義中の作用に関する三番目の条件を
a,bA, xV, a(bx)=(ab)x
に変えたものはA-加群と呼ばれます。Aの乗法が可換のときは、右A-加群と左A-加群は同じものです。半環Aに対して乗法の向きを変えることで反対半環Aopが定義されるということを知っていれば、右A-加群とは左Aop-加群であるということができます。

以下では単にA-加群といったら右A-加群のこととします。

線形写像

VWA-加群とする。以下の条件を満たす写像f:VWA-線形写像という。

  • x,yV, f(x+y)=f(x)+f(y)
  • aA, xV, f(ax)=af(x)
半環上の加群の圏

A-加群とA-線形写像は圏をなす。この圏をAModと書く。

半環A自身は、作用をax=xaと定めることで右A-加群の構造を持ちます。

Mを加法に関する可換モノイドとします。作用N×MMax=x++x (a個の和)で定めることで、Mは自然にN-加群の構造を持ちます。

半環上の行列

半環上の行列

IJを集合とする。写像M:I×JAのことをA上のI×J行列という。M(i,j)=aijのとき、M=(aij)(i,j)I×Jと書く。

A上のI×J行列Mが与えられたとき、各iIについてM{i}×Jに制限して得られる行列をMi行といい、各jJについてMI×{j}に制限して得られる行列をMj列といいます。

mnが自然数でI={0,,m1}およびJ={0,,n1}であるとき、A上のI×J行列のことをA上のm×n行列といいます。A上のm×n行列は、Aの元を長方形の配列として縦にm行、横にn列並べたものとして表されます。

(314035)N上の2×3行列です。

行列の積

M=(aij)(i,j)I×JA上のI×J行列として、N=(bjk)(j,k)I×JA上のJ×K行列とする。任意のkKについてNk列は有限の台を持つとする。このとき、MNの積MN
MN=(jJaijbjk)(i,k)I×K
で定まるA上のI×K行列とする。

線形代数において最も重要な事実のひとつは、線形写像に関する計算が行列の積で記述されるということです。このことについて見てみましょう。

基本となるのは基底という概念です。

基底

VA-加群とする。以下の条件を満たすVの元の族(vi)iI基底という。

  • 任意のxVについて、有限の台を持つAの元の族(xi)iIであって、x=iIxiviを満たすものが一意に存在する。

Vを基底(vi)iIを持つA-加群とします。このとき、基底の定義より、任意のxVx=iIxiviと一意的に表せます。(xi)iII×1行列と思うことができます。この行列をM(x)と書くことにします(Mはmatrixの頭文字です)。行列M(x)x(vi)iI列ベクトルと呼ぶこともあります。列ベクトルであることを強調したい場合は、(xi)iI(xi0)(i,0)I×1と書くことにします。

線形写像の表現行列

VおよびWA-加群として、これらはそれぞれ基底(vi)iIおよび(wj)jJを持つとする。f:VWA-線形写像とする。このとき、基底(vi)iI, (wj)jJに関する線形写像f表現行列M(f)=(aji)(j,i)J×I
f(vi)=jJajiwj
で定める。

言い換えると、M(f)i列はM(f(vi))(wj)jJに関する列ベクトルと等しいということです。

線形写像による像は行列と列ベクトルの積

VおよびWA-加群として、これらはそれぞれ基底(vi)iIおよび(wj)jJを持つとする。f:VWA-線形写像とする。このとき
M(f(x))=M(f)M(x)
が成り立つ。

M(f)=(aji)(j,i)J×Iとします。基底を用いてx=iIxi0viおよびf(x)=jJyj0wjと表します。
このとき、
f(x)=f(iIxi0vi)=iIxi0f(vi)(線形写像の定義)=iIxi0(jJajiwj)(表現行列の定義)=jJ(iIajixi0)wj(加群の定義)
となります。よってyj0=iIajixi0です。右辺は行列の積の定義よりM(f)M(x)j成分と等しいので、定理が従います。

線形写像の合成は行列の積

U, VおよびWA-加群として、これらはそれぞれ基底(ui)iI, (vj)jJおよび(wk)kKを持つとする。f:UVおよびg:VWA-線形写像とする。M(f)を基底(ui)iI, (vj)jJに関するfの表現行列として、M(g)を基底(vj)jJ, (wk)kKに関するgの表現行列とする。このとき
M(gf)=M(g)M(f)
が成り立つ。

xUを任意にとります。すると、一つ目の定理より
M(gf)M(x)=M((gf)(x))=M(g)M(f(x))=M(g)M(f)M(x)
となります。iIを任意にとります。上の式でx=uiとすると、M(gf)M(g)M(f)i列が等しいことがわかります。iは任意なので、定理が従います。

上の定理は右A-加群に関するものですが、左A-加群versionを考えることもできます。その場合は、上のふたつの定理はそれぞれ
tM(f(x))=tM(x)tM(f)tM(gf)=tM(f)tM(g)
なります。ここで、行列Mに対してtMMの転置行列です。

おわりに

半環上の行列の背景にある代数理論として、半環の加群について見てきました。

環ではなく半環を考えるのには次のようなメリットがあります。

  • トロピカル半環という環の世界に対応物がない対象を扱える。
  • Z上で成り立つことが実際にはN上で成り立つということが「深い定理」として現れることがある。

ひとつめについては、「はじめに」で紹介した記事のように計算機科学にも応用があるように、わかりやすいメリットといえます。ふたつめについて例を挙げて説明しようと思います。

Pを整数の分割の集合としたときに、各分割λPに対してSchur関数と呼ばれる無限変数の対称多項式sλN[x1,x2,]が定まります。Schur関数で生成される半環N[sλ]λPN-加群とみなしたとき、Schur関数(sλ)λPN[sλ]λPの基底を与えることが知られています。これは(sλ)λPZ-加群Z[sλ]λPの基底であるという事実よりずっと非自明な事実で、その背景には対称群の表現論やリー代数の表現論といった理論があることが知られています。Schur関数ついては参考文献で挙げる『Symmetric Functions and Hall Polynomials』という本に詳しく書いてあります。

参考文献

[1]
Macdonald, Ian Grant, Symmetric functions and Hall polynomials. 2nd ed., Oxford: Clarendon Press, 1995, p. x + 475
投稿日:2021127
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

shiro
5
1101

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. はじめに
  2. 端的なまとめ
  3. 半環
  4. 半環上の加群
  5. 半環上の行列
  6. おわりに
  7. 参考文献