このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

二重圏の簡単な例:非負行列の順序構造

圏論の練習問題:モノイド二重圏の定義の同値性」と「二重圏の具体的な定義」において、二重圏を話題にしました。しかし、二重圏の事例は出していません。例がないことには実感の持ちようがありませんよね。

二重圏の典型的な例は、コボルディズムの二重圏でしょう。コボルディズムの圏は直和によりモノイド構造も入るのでモノイド二重圏にもなっています。計算のモデルでは、境界付きオートマトン(状態遷移系)と模倣を考えると二重圏ができます。これも直和によりモノイド二重圏となります。

これらの例を構成するのは面倒だし、幾何/物理/計算科学などの背景が多少は要求されます。そこで、予備知識無しでも作れていじれる例をでっち上げてみました。素材は行列です。

内容:

準備

行列の計算をするには、係数域が体や環である必要はなくて、半環で十分です。半環とは、可換モノイド演算である足し算と、モノイド演算である掛け算(可換でなくてもよい)を持ち、分配法則が成立する代数系です。Hが半環のとき、Hを係数とする行列の全体をMatHと書くことにします。

Rを実数全体の集合として、P := {x∈R | x≧0 } として非負実数の集合Pを定義します。Pは単なる集合ではなくて、実数から受け継いだ足し算と掛け算があるとします。この足し算と掛け算に関してPは半環となるので、P係数の行列の集合MatPが定義できます。MatP には、普通のとおりに足し算と掛け算が定義できます。

これから述べることは、「これならいじれるぞ、2-圏の簡単な例」に書いたことを少し拡張したものです。「これならいじれるぞ」記事では、係数域(スカラー)をハッキリさせずに NNMat(NonNegative Matrix)という集合を導入したのですが、今回は、NNMat := MatP とします。つまり、NNMatは非負実数係数の行列の全体です。この呼び名は長たらしいので非負行列と略称します。

NNMatはMatPなので、行列の圏に関する一般論をすべて使えます。行列の圏に関しては次の記事を参照してください。

また、「これならいじれるぞ、2-圏の簡単な例」の最後には、その他の参考エントリーもまとめてあります。

NNMatの圏としての構造、ホムセットNNMat(n, m)、単位行列In、行列Aに対する width(A), height(A)、B・A、A;B などの記法に関しては、いま挙げた記事群を参照してください。以下で「行列」と言えば、それは非負行列を意味します。

概要

これならいじれるぞ、2-圏の簡単な例」では、非負行列A, Bに対して、順序 A≦B を定義しました。しかし、この順序は同じサイズの行列にしか定義されません。つまり、次が成立しています。

  • A≦B ならば width(A) = width(B)
  • A≦B ならば height(A) = height(B)

別な言い方をすると、ホムセットNNMat(n, m)ごとに、順序関係≦n,mがあって、それらを寄せ集めた関係が≦だとみなせます。AとBが異なるホムセットに属するときは、それらのあいだの順序を考えることは無意味だったのです。先の命題をより正確に記述すると:

  • A≦B が意味を持つならば width(A) = width(B)
  • A≦B が意味を持つならば height(A) = height(B)

今回は、ホムセットに属する2つの行列、つまりサイズの違う行列に関しても順序関係を拡張します。新しい順序を⊆と書きます。集合の包含関係の記号を流用してますが、集合の包含とは無関係です。⊆は、まったく勝手に取った2つの行列に対して意味を持つわけではなくて、次の条件があります。

  • A⊆B が意味を持つならば width(A) ≦ width(B)
  • A⊆B が意味を持つならば height(A) ≦ height(B)

つまり、widthとheightは(意味を持つ範囲内で)、行列の順序⊆と自然数の順序≦に対して単調写像になっています。

さらに、順序関係⊆は、次の性質をもつように定義します。

  • A⊆A'、B⊆B' であり、A;BとA';B'が定義可能ならば、A;B ⊆ A';B' である。

行列のサイズ拡張

Aが行列であって、width(A)≦n、height(A)≦m である自然数n, mが与えられているします。このとき、n列m行の新しい行列Xを次のように定義します; width(A)<i≦n または height(A)<j≦m であるi, jに関しては、X[j, i] := 0 とします。その他のi, jに関してはAと同じ値で X[j, i] := A[j, i] とします。行列を「成分を並べた四角形」とみなすと、Aをゼロ成分で縁取りしたものがXです。行列のサイズを自明な方法で拡張する操作ですね。

このようにして作ったXをA~n,mと書くことにしましょう。A |→ A~n,m という対応は、写像 (-)~n,m:NNMat→NNMat(n, m) を定義しますが、全域ではなくて部分写像になります。(-)~n,mの定義域は次のとおり:

  • {A∈NNMat | width(A)≦n かつ height(A)≦m}

(-)~n,mはいくつかの等式を満たします。A, Bが行列、n, m, k, p, qは自然数だとして、等式の両辺が定義される状況では次が成立します。

  1. A∈NNMat(n, m) ならば A~n,m = A
  2. (A~n,m)~p,q = A~p,q
  3. (A;B)~n,m = A~n,k;B~k,m

非負行列の順序構造を定義する

行列AとBが同じサイズなら、順序関係 A≦B を「これならいじれるぞ、2-圏の簡単な例」の方法で定義できます。

  • A≦B ⇔ (すべてのi, jについて A[j, i] ≦ B[j, i])

AのサイズがBのサイズより小さいとき、A⊆B を次のように定義します。B∈NNMat(n, m) だとして:

  • A⊆B ⇔ A~n,m≦B

A~n,mとBは同じサイズになるので、A~n,m≦B は意味を持ちます。

関係「⊆」と演算「;」が定義される範囲内で、次が成立します。

  1. A⊆A
  2. A⊆B、B⊆C ならば A⊆C
  3. A⊆B ならば width(A) ≦ width(B)
  4. A⊆B ならば height(A) ≦ height(B)
  5. A⊆A' かつ B⊆B' ならば A;B ⊆ A';B'

これらは、定義に基いて確かめることができます。

非負行列の二重圏

行列の集合NNMatに(部分的な)順序関係⊆を導入できました。これにより、二重圏の構造を定義できます。「二重圏の具体的な定義」で導入した記号達(書体の違いに注意) Dh1, Dv1, D2h, D2v, D0, D2 を使います。

まず、二重圏Dの素材たちです。

  1. D0 := N = {0, 1, 2, ...}
  2. Dh1 := NNMat
  3. Dv1 := {(n, n')∈N×N | n≦n'}
  4. D2 := {(A, A')∈NNMat×NNMat | A⊆A'}

4つの圏 Dh1, Dv1, D2h, D2v は次のようなものです。

  1. Dh1は、Nを対象の集合とする非負行列の圏である。
  2. Dv1は、Nを対象の集合とし、Nの大小順序≦を射とする圏である。
  3. D2hは、「A⊆A' かつ B⊆B' ならば A;B ⊆ A';B'」に基いて定義される、順序の横結合の圏である。
  4. D2vは、NNMatを対象の集合とし、NNMatの順序関係⊆を射とする圏である。

この二重圏では、自然数の普通の足し算と行列の対角ブロック和でモノイド積を入れることができるので、実はモノイド二重圏になっています。行列計算と順序しか使ってないので、簡単に実験ができます。二重圏の感じを掴むために役立つのではないかと思います。