Kleene代数の行列計算とトレース

Kozenは、Kleene代数Kを係数とする正方行列の代数Mat_K(n, n)が再びKleene代数になることを示した。半環になることはすぐさまわかるから、問題はKleeneスターの定義となる。これが非常に憶えにくい。

2×2行列のときが本質的で、あとはinductionだから、2×2で話す。第1行が[a b]、第2行が[c d]である行列を[a, b; c, d]と書くことにすると、[a, b; c, d]* は：

• [(a + bd*c)*, (a+bd*c)*bd*; (d+ca*b)*ca*, (d+ca*b)*]

ウゲッ、天下りに暗記はシンド過ぎる。

が、Cazanescu, Stefanescu, Hyland, Hasegawa（カザネスク、ステファネスク、ハイランド、長谷川）などの結果を参照すると、絵算で計算できる。まず、双積と零対象でモノイド圏になっているような対称モノイド圏を考える。そこにトレースがあれば、endo射f:X→XのKleeneスターf*が次のように定義できる。

• f* = Tr^X_X,X(∇;f;Δ)

∇は余対角、Δは対角である（対角はduplicator、ramificator、folkなどとも呼ぶ）。一方、行列[a, b; c, d]は、a, b, c, d:X→Xとして次のように表現できる。

• (Δ_X;(a+c) + Δ_X;(b+d));(X+σ_X+X);(∇_X+∇_X)

上の表現は、行列を4辺の有向二部グラフに描けばすぐに得られる。この二部グラフに対してTr^X_X,X(∇;f;Δ)を作り、ワイヤーを追いかけて書き下すとKozenの表示が得られる。

Cazanescu/Stefanescu/Hyland/Hasegawaの結果を標語的に言えば、

• デカルト・モノイド圏のトレースは不動点を定義し（逆も真）、双デカルト・モノイド圏のトレースはKleeneスターを定義する（逆も真だったと思う）。

ここで、双デカルトとは、デカルト積（直積）かつ余デカルト積（直和）である双積（と零対象）を持つことを意味する。

• traced cartesian monoidal category = category with fixed-point operator
• traced bicartesian monoidal category = category with Kleene-star operator

ところで、双デカルト性から、半加法性（可換モノイドでenrichできる）ことが出るのだろうか？ つまり、余対角∇が足し算になるのだろうか？ 双デカルトでモノイド閉なら、hom積[A, B] が定義できて、随伴を作れるならテンソル積が定義できて、テンソル単位IのEndを取ればスカラー半環ができる -- って、そんなにウマクいくかよ、オイッ。