半群の表現論に触れてみる（Pythonで）

もともとは[続・サイコロゲームと貧富の差](https://qiita.com/kaityo256/items/f90ef7bea53c0720fdc8)にインスパイアされました。
記述を簡単にするため、次のような試行を考えます。（リンク先記事のゲームよりも、色々な点において簡単になっているのでご注意ください。たとえば、遷移しない状態を削っているので、等重率などに関する議論はこの記事の対象ではありません。）

# 導入：コインゲーム

- 二人の人$X,Y$がりんごを一個ずつ持っている。
- コインの表が出たら$X$が持っているりんごを一つ$Y$に、裏が出たら$Y$が持っているりんごを一つ$X$に渡す。ただし、りんごの数が足りない場合は何もしない。

この試行を繰り返す場合において、$X,Y$が持っているりんごの数は$(2,0), (1,1), (0,2)$のいずれかになります。
この3つのことを状態と呼ぶことにすると、$A:=$表が出る事象・$B:=$裏が出る事象はそれぞれの状態の遷移として表すことができます。
この3つの状態を3次元ベクトル空間$V$の単位ベクトルと思うと、$A$と$B$は行列表示することができて、

```math
A = \left( \begin{matrix}
0 & 0 & 0 \\
1 & 0 & 0 \\
0 & 1 & 1 
\end{matrix} \right), B=\left( \begin{matrix}
1 & 1 & 0 \\
0 & 0 & 1 \\
0 & 0 & 0 
\end{matrix} \right)
```

と表すことができます。
これらは、素朴な意味で非可逆です。つまり、$\operatorname{rank}(A) = \operatorname{rank}(B) = 2 < 3$です。一方で、$A,B$は単位ベクトルをいずれかの単位ベクトルに（重複を許して）移す作用なので、$A,B$が行列の乗法で生成する集合は閉じていて、かつ行列の乗法について結合的です。
このような結合的な演算で閉じた集合のことを半群といいますが、ここでは、その半群の表現論に触れてみることにします。

# 生成する半群のかたち

$A,B$が生成する半群を具体的に書き下してみます。

```python3:notebook
import numpy as np

a = np.array([[0, 0, 0], [1, 0, 0], [0, 1, 1]])
b = np.array([[1, 1, 0], [0, 0, 1], [0, 0, 0]])


def A():
    return a


def B():
    return b

alphabet_default = [A, B]
generated_values_default = {}


def generate_recursive(word, value, alphabet, generated_values):
    key = str(value)
    if key in generated_values.keys():
        generated_values[key]['words'].append(word)
        return
    if word != '':
        generated_values[key] = dict(
            words=[word], value=value, rank=np.linalg.matrix_rank(value), tr=np.trace(value))
    for v in alphabet:
        generate_recursive(word + v.__name__, np.dot(value, v()), alphabet, generated_values)

# 計算
generate_recursive(
    '', np.array([[1, 0, 0], [0, 1, 0], [0, 0, 1]]), alphabet_default, generated_values_default)


# 以下、整形
def get_tex_source(generated_values):
    for k, v in generated_values.items():
        print('''```math
''' + ' = '.join(v['words']) + ''' = \\left( \\begin{matrix}
''' + ' \\\\ \n' . join([' & '.join([str(x) for x in list(r)]) for r in list(v['value'])]) + '''
\\end{matrix} \\right)
, \\operatorname{rank}(''' + v['words'][0] + ''') = ''' + str(v['rank']) + '''
, \\operatorname{tr}(''' + v['words'][0] + ''') = ''' + str(v['tr']) + '''
`''' '''``
''')
        
get_tex_source(generated_values_default)

```

## 書き下した結果

以下のようになります。

```math
A = ABA = \left( \begin{matrix}
0 & 0 & 0 \\ 
1 & 0 & 0 \\ 
0 & 1 & 1
\end{matrix} \right)
, \operatorname{rank}(A) = 2
, \operatorname{tr}(A) = 1
```

```math
AA = AAA = AAB = \left( \begin{matrix}
0 & 0 & 0 \\ 
0 & 0 & 0 \\ 
1 & 1 & 1
\end{matrix} \right)
, \operatorname{rank}(AA) = 1
, \operatorname{tr}(AA) = 1
```

```math
AB = \left( \begin{matrix}
0 & 0 & 0 \\ 
1 & 1 & 0 \\ 
0 & 0 & 1
\end{matrix} \right)
, \operatorname{rank}(AB) = 2
, \operatorname{tr}(AB) = 2
```

```math
ABB = ABBA = ABBB = BAA = \left( \begin{matrix}
0 & 0 & 0 \\ 
1 & 1 & 1 \\ 
0 & 0 & 0
\end{matrix} \right)
, \operatorname{rank}(ABB) = 1
, \operatorname{tr}(ABB) = 1
```

```math
B = BAB = \left( \begin{matrix}
1 & 1 & 0 \\ 
0 & 0 & 1 \\ 
0 & 0 & 0
\end{matrix} \right)
, \operatorname{rank}(B) = 2
, \operatorname{tr}(B) = 1
```

```math
BA = \left( \begin{matrix}
1 & 0 & 0 \\ 
0 & 1 & 1 \\ 
0 & 0 & 0
\end{matrix} \right)
, \operatorname{rank}(BA) = 2
, \operatorname{tr}(BA) = 2
```

```math
BB = BBA = BBB = \left( \begin{matrix}
1 & 1 & 1 \\ 
0 & 0 & 0 \\ 
0 & 0 & 0
\end{matrix} \right)
, \operatorname{rank}(BB) = 1
, \operatorname{tr}(BB) = 1
```

# この表現の性質

一般的な表現論では、その表現が直既約であるか、単純であるかということに興味があります。
群などの表現とほぼ同様に定義ができると思うので（例えば半群環を作ってそれの代数としての表現を考えればよい）、直既約・単純などという事の定義はここではきちんと行わずに、ナイーブに上で得られた行列たちを同時対角化が可能であるかどうかという観点で考えてみます。

これは計算した結果なので天下りですが、

```math
W = \left\{ {\left( \begin{matrix}
x \\ 
y \\ 
z
\end{matrix} \right)
, x + y + z = 0} \right\}
\subset V
```
という2次元の部分空間を考えると、$A, B$の作用で閉じていることが容易にわかり、この表現は単純ではありません。

※元ネタの「富の総和が一定」に対応する部分空間です。


一方で、$A$と$B$の固有値はいずれも1,0になっていて、固有値0に対応する部分空間が$W$であることがわかります。
$A$の固有値1に対応する固有空間は$z$成分だけを持つもの、$B$の固有値1に対応する固有空間は$x$成分だけ持つものなので、これらは明らかに一致せず、直和分解はできない事がわかります。$V$は表現としては直既約であるということになります。

群の場合は、体を適当に選べば完全可約（ある表現が直既約であることと単純であることが同値になる）なので、こんなに簡単な半群に対しても完全可約性が成り立たないというのは、対照的ですね。

# 他の簡単な表現

さきほどの直規約な表現の組成因子にあたる、商表現と部分表現は、単純な表現になります。
つまり、任意の作用が1になる意味での自明な表現と、上述の2次元の部分表現です。
他には表現は存在するのかな？

いま、$A^2=A^3, B^2=B^3$なので、固有値が0または1でないといけないことに注意します。

1次元の表現を考えると、全てを1に移す自明な表現と、全てを0に移す表現があります。

2次元の表現はについて、仮に固有値1を含むと仮定すると、対角化可能でない（Jordan標準形が対角行列でない）場合は$A^2=A^3, B^2=B^3$を満たせなくなってしまうので、固有値1を含むという仮定では自明な表現の直和になります。

そこで固有値0と仮定したときは、まず全てを0に移す表現の直和があります。

全てを0に移す表現ではないと仮定すると、$W$と同形なものになるのでしょうね。（これは厳密には計算していない）

$W$は部分表現を持たないか？ということですが、$W$の基底として$(1,-1,0)^t, (0,1,-1)^t$を取ると、$A,B$の作用は生成消滅演算子と類似の形になるので、持たないです。もう少し丁寧に言うと、任意の$W$の0以外の元に対して$A,B$を適当にかけたり足し算したりすれば、$W$の任意の元を作れます。

# 半群の表現の指標

群の表現の場合は、（共役類で一定になる）traceの値が指標と定義されます。半群の表現の場合にも、同様のものは定義できます。
traceは基底の変換によって不変なので、表現を直和分解/組成分解？（上三角ブロック分解？）する時には単純な足し算になり、有効です。

これまでの2種類の自明な表現の場合は、指標は常に1または常に0ですね。

上述の2次元の単純表現については、$AB,BA$のみ1で、他は0という事になっています。（この指標の値からも、$W$が1次元の部分表現を持たない事が言えます。）

# 半群環自身を表現として見る

群環を群の表現として見るように、半群環を半群の表現として見てみます。
この表現行列を作成するために、半群の具体的な表示を計算していたのでした。
※Jupyterのセルを転載しているので、上のpythonスクリプトと合わせて実行する必要があります。

```notebook2.py
mats = []
labels = generated_values_default.keys()
for x in alphabet_default:
    mat = []
    for label_i in labels:
        result_key = str(np.dot(x(), generated_values_default[label_i]['value']))
        mat.append([1 if result_key == label_j else 0 for label_j in labels])
    mats.append(np.array(mat).transpose())

    
def P():
    return mats[0]


def Q():
    return mats[1]

alphabet_mat = [P, Q]
generated_values = {}

generate_recursive(
    '', np.array([[1 if j == i else 0 for j in range(7)] for i in range(7)]),
    alphabet_mat, generated_values)
get_tex_source(generated_values)

```

## 結果

```math
P = PQP = \left( \begin{matrix}
0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 
1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 
0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 
0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 0 & 0 & 0 & 0
\end{matrix} \right)
, \operatorname{rank}(P) = 4
, \operatorname{tr}(P) = 1
```

```math
PP = PPP = PPQ = \left( \begin{matrix}
0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 
0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 0 & 0 & 0 & 0
\end{matrix} \right)
, \operatorname{rank}(PP) = 1
, \operatorname{tr}(PP) = 1
```

```math
PQ = \left( \begin{matrix}
1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 
0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 
0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 0 & 0 & 0 & 0
\end{matrix} \right)
, \operatorname{rank}(PQ) = 4
, \operatorname{tr}(PQ) = 4
```

```math
PQQ = PQQP = PQQQ = QPP = \left( \begin{matrix}
0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 
0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 0 & 0 & 0 & 0
\end{matrix} \right)
, \operatorname{rank}(PQQ) = 1
, \operatorname{tr}(PQQ) = 1
```

```math
Q = QPQ = \left( \begin{matrix}
0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 
0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 
1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 1 & 1 & 1 & 1
\end{matrix} \right)
, \operatorname{rank}(Q) = 4
, \operatorname{tr}(Q) = 1
```

```math
QP = \left( \begin{matrix}
0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 
0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 
0 & 0 & 0 & 0 & 0 & 0 & 1
\end{matrix} \right)
, \operatorname{rank}(QP) = 4
, \operatorname{tr}(QP) = 4
```

```math
QQ = QQP = QQQ = \left( \begin{matrix}
0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
1 & 1 & 1 & 1 & 1 & 1 & 1
\end{matrix} \right)
, \operatorname{rank}(QQ) = 1
, \operatorname{tr}(QQ) = 1
```

# 結果に対する考察

この結果を見ると、この表現の適当な商や部分表現として、1次元表現ひとつ、2次元表現3つが出現しそうです…が、これはどういう形でくっついているのでしょう。組成列の次元を取った時に、7,6,4,2という形でしょうか。

実際、7つの成分の和が0になるような6次元部分空間を取ると、それは部分表現になっているはずで、その商表現は自明な表現になるはず。以下は、証明などを何もしていない考察です。

## 直和因子（射影加群）についての考察

多分、直和因子（射影加群）は、

- 射影加群でtopが自明表現のもの$P_1$＝上で考察した直既約加群（3次元）
- 射影加群で2次元がtopのもの$P_2$＝2次元の単純加群で、重複数2

これのEndを取ると、

- $P_1$の行き先が$P_1$自身のみで1次元
- 直和因子の$P_2$2つの行き先が、それぞれ$P_1$の中と$P_2$×2のいずれかの合計3つの行き先の中で選べて、3次元×2 = 6次元

で、合計7次元になってちょうど合うんじゃないかな。これは次の機会に検証しましょう。

## 森田同値な道代数(path algebra)について

上の考察が正しければ、$A_2$型のpath algebraと森田同値になるはず。わりと簡単な形になりましたね。

## 一般のnについて

これ、たまたま$A_2$型とかになったから簡単な話なのかなーと思ったら、あんまりそんなことはなく、$n=3$で既に計算がとんでもないことになってしまった…

```python3:notebook3.py
import numpy as np

# 基底となる行列の生成
n = 3
base = {}
work = [0 for i in range(n)]

def get_base_recursive(work, base, n, m):
    if n == 0:
        base[str(work)] = dict(value=[w for w in work])
        return
    for i in range(m):
        work[i] += 1 
        get_base_recursive(work, base, n - 1, m)
        work[i] -= 1

get_base_recursive(work, base, n, n)

# 基本的な操作に対する作用の生成
simple_actions = []
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        sij = []
        for k, v in base.items():
            copy = [k for k in v['value']]
            if v['value'][i] != 0:
                copy[i] -= 1
                copy[j] += 1
            row = [1 if v2['value'] == copy else 0 for k2, v2 in base.items()]
            sij.append(row)
        simple_actions.append(dict(
            name='s_{' + str(i) + ',' + str(j) + '}',
            value=np.array(sij).transpose()
        ))
print(simple_actions)

```

$s_{i,j}$が6個できます。これで半群を生成…
計算の実行：

```python3:notebook4.py
generated_values_default = {}
limit = [0]


def generate_recursive(word, value, alphabet, generated_values, limit):
    limit[0] += 1
    if limit[0] >= 500000:
        # ここは通らない
        print('500000!')
        return
    key = str(value)
    if key in generated_values.keys():
        # generated_values[key]['words'].append(word)
        return
    if word != '':
        generated_values[key] = dict(
            words=[word], value=value, rank=np.linalg.matrix_rank(value), tr=np.trace(value))
    for v in alphabet:
        generate_recursive(word + v['name'], np.dot(value, v['value']), alphabet, generated_values, limit)

# 計算
generate_recursive(
    '', np.array(
        [[1 if i == j else 0 for j in range(len(base.items()))] for i in range(len(base.items()))]),
    simple_actions, generated_values_default, limit)

# 1分以内の計算

```

この6つの行列$s_{i,j}$たちによって実に31738個の要素が生成されるらしいです。
これを直接的な計算で考えるのは、ちょっと大変そうですね。