考察対象の半群について

まず、コインゲームについて再掲します。

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

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

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)

と表すことができます。この$A,B$の生成する半群が考察対象なのでした。

前回、末尾で$n$を増やすと$n=3$で既に大変なことになるということを述べたのですが、もっと易しい一般化が、およそ2パターンあることに気付きました。
元ネタをリスペクトして、「人間」と「りんご」という言葉を使うことにすると、「人間」を増やすという一般化と、「りんご」を増やすという二種類の一般化があります。
ここでは、人間の数を$m$、りんごの数を$n$と表すことにします。

さらに、ブレイド群またはWeyl群（またはCoxeter群）を理論的な背景とする、作用の削減という観点もあります。
これは、やや天下りなのですが…

群を生成する時に、ある種の関係式を用いるのと同様に、半群においても関係式を用いて定義をする事ができます。
上の$n=2,m=2$の場合では$ABA=A, BAB=B$という関係式が成り立っています。（他にも成り立っていますが。）
この関係式は、最も基本的な群の一つである対称群、例えば3つの区別できる物の置換全体の為す群を$S_3$とし、1つ目の要素と2つ目の要素の置換を$s_1$、2つ目の要素と3つ目の要素の置換を$s_2$と書くと、$s_1,s_2$は$S_3$を生成する要素になっていて、$s_1s_2s_1=s_2s_1s_2$を満たします。
一般に、このような関係式で定義される群は、ある種の無限次元の代数の性質を理解する上で重要になり、量子論など様々な場面で扱う事になります。
この時、特に対称群においては、1つ目と2つ目、2つ目と3つ目、…というように隣り合う要素の置換だけを組み合わせることで任意の置換を再現できることが知られているので、これと同じ考え方を今回の考察対象の半群にも適用することができます。
具体的には、$m=3$の場合には、1番目の人と3番目の人の間のやりとりは考えない、という具合です。

さて、今回は、このように生成元を少なくした上で、ある程度一般の$m,n$についても考察をしていきたいと思います。
以後、対象の半群を$T_m^n$と書くことにします。

改良版プログラム

notebook_cell_1

import numpy as np

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

def get_array_key(arr):
    return '\n'.join([str(l) for l in list(arr)])

def get_base_recursive(work, base, n, m):
    if n == 0:
        base[get_array_key(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, m)

# 基本的な操作に対する作用の生成
simple_actions = []
for i in range(m):
    for j in range(m):
        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)
        # これは隣接する場合のみ
        if i - j == 1 or j - i == 1:
            simple_actions.append(dict(
                name='s_{' + str(i) + ',' + str(j) + '}',
                value=np.array(sij).transpose()
            ))
print(simple_actions)

notebook_cell_2

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 = get_array_key(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)


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

notebook_cell_3

mats = []
labels = generated_values_default.keys()
for v in simple_actions:
    mat = []
    for label_i in labels:
        result_key = get_array_key(np.dot(v['value'], generated_values_default[label_i]['value']))
        mat.append([1 if result_key == label_j else 0 for label_j in labels])
    mats.append(dict(name=v['name'], value=np.array(mat).transpose()))

generated_values = {}
limit = [0]
dim = len(generated_values_default.items())


generate_recursive(
    '', np.array([[1 if j == i else 0 for j in range(dim)] for i in range(dim)]),
    mats, generated_values, limit)
# get_tex_source(generated_values)

def get_rank_tr(generated_values):
    for k, v in generated_values.items():
        print(str(v['rank']) + '\t' + str(v['tr']))

print(len(generated_values))
print('----')
get_rank_tr(generated_values_default)
print('----')
get_rank_tr(generated_values)

これによって、前回のプログラムのように関係式、行列のランク、トレースなどを出力できます。

改良ポイント：str(array)を使わない

ディクショナリのハッシュ値としてstr(array)（arrayはnumpyのarray）を使っていたのですが、これは適当な次数の場合に...で省略される事がわかったので、単純なstrを使うのをやめました。
※前回の記事のものは、n=2,3では正しく動くので、そのままにしてあります

n=2, m=2の場合についての考察

直既約加群（表現）の分類

前回書いたとおり、単純加群として1次元の自明な加群と、2次元の加群があります。
（2次元の加群…$A=s_{0,1}$の作用が左下のみ1で他が0の正方行列、$B=s_{1,0}$の作用が右上のみ1で他が0の正方行列として与えられる加群）
さらに、Topが1次元、radicalが2次元、合計3次元の直既約加群があって、これは射影加群（半群環自身を半群の表現と見た時の、直和因子）になっています。
これは、（係数体を適当に選べば）以下のような事実の組み合わせによって示されます：

単純加群の間の準同型は、それらが同型の時1次元、同型でないとき0次元のベクトル空間をなす
（単位的）代数$\mathbb{A}$において、$\mathbb{A}$自身の$\mathbb{A}$自己同型は$\mathbb{A}$と同型
ある$\mathbb{A}$-射影加群のTop（その加群をradicalで割った商）がベクトル空間として見て$r$次元かつ単純ならば、その$\mathbb{A}$-射影加群は$\mathbb{A}$の中に$r$個直和として含まれる
$\mathbb{A}$-射影加群$P$のTopが$S$であるとすると、$S$がTopの加群に対しては必ず$P$からの全射が存在する
各単純加群がTopとなる射影加群が存在する
$n=2, m=2$のとき、半群環は単位的である

上の事実を全て認めれば、この半群環が7次元であることと、半群環に3次元の直既約加群が含まれることと、2次元の単純加群をTopに持つ射影加群が半群環に2つ含まれることから、その次元を比較することで2次元の単純加群が射影的である事が従います。

n=1, m=2の場合

じつは、こちらの方が「もっと簡単」なのでした。ただ、この場合はなんと半群環が単位的でなくなってしまいます！
たしかに、群と違って1が存在しないので、半群環は単位的でなくなる可能性もあるのですが、なんとびっくりでした。ちなみに、今回扱うものに関しては、これ以外は単位的です。
直既約な表現は、すべて1におくる自明な表現と、すべて0におくる自明な表現と、2次元でTopがすべて1の表現、radが全て0の表現です。
全て0の表現は、単位的な場合には出てこないというか考えるべき対象では無いのですが、半群代数の生成時に$T_2^1$の要素のみを生成元とする場合、それらの線形結合によって単位的な元を構成できないので、そのような表現を考えることができてしまいます。
容易にわかるように、$s_{0,1}-s_{1,0}$により生成される代数（ベクトル空間）は$T_2^1$代数自身のアニヒレーターで、つまり0として作用します。
一般に代数が単位元を持つ場合は、（当然ですが）自分自身のアニヒレーターは存在せず、全ての作用が0であるような表現は考えない方が都合が良いです。

m=2でnを一般にした場合

半群の要素数

上のプログラムで生成した半群の要素数を眺めると、7,17,34,60,...となっていて、これを数列辞典で調べると$1+...+n^2 + n$でした。これは組合せ論的に示せそう…と思っていたのですが、半群を具体的に構成すれば簡単に示せました。
$n+1 \times n+1$行列

\begin{pmatrix}
0 & 0 & 0 & \cdots & 0 \\ 
1 & 0 & 0 & \ddots & \vdots \\ 
0 & 1 & 0 & \ddots & 0 \\ 
\vdots & \ddots & \ddots & \ddots & \vdots \\ 
0 & \cdots & 0 & 1 & 1
\end{pmatrix}
,
\begin{pmatrix}
1 & 1 & 0 & \cdots & 0 \\ 
0 & 0 & 1 & \ddots & \vdots \\ 
0 & 0 & 0 & \ddots & 0 \\ 
\vdots & \ddots & \ddots & \ddots & 1 \\ 
0 & \cdots & 0 & 0 & 0
\end{pmatrix}

の２つの元は、各列成分につきたかだか1つしか1が無い元を生成しますが、その元において隣合う列$j$および$j+1$のベクトルの1が入っている成分は、たかだか1しか離れておらず、かつ、$j$列の1が入る成分はかならず$j+1$列より下に入ることはありません（生成元の形より）。

これによって、$\operatorname{rank}=2$の場合の要素の形を考えると、その要素の1が占める2行の選び方が$n$通り、1の入る行が変わる位置の選び方が$n$通り、これを掛け合わせて$n^2$となります。（これは$s_{0,1}^ls_{1,0}^{k}s_{0,1}^{n-k} (1 \leq k, l \leq n)$の形で実際にかけます。）

$\operatorname{rank}>2$のものについては、$T_2^{n-1}$の場合の$\operatorname{rank}\geq 2$の要素への全単射を構成することができて、帰納的に$\operatorname{rank}\geq 2$の要素の数が$2^2+\cdots+n^2$であることが言えます。
$\operatorname{rank} = 1$の要素については、これを表現と思うと定義で用いた直既約表現と同型になっていることを示すことができて、$n+1$次元であることがわかり、$\operatorname{rank} = 1$の要素数は$n+1$となります。

単純加群

$\operatorname{rank}$は非可逆なので、任意の自然数$k$に対して$\operatorname{rank}$が$k$以下の要素で生成される半群環の部分環$M_k$はイデアル（部分加群）になっています。そこで、$M_k/M_{k-1}$を考えると、これが$n-k+2$次元の単純加群の$n-k+2$個の直和になっています。

その証明方法ですが、まず$T_{2}^n$半群代数の$\operatorname{rank}=1$で割った商代数$A_n$について、この代数において$M_k/M_{k-1}$が$n-k+2$次元の単純加群の$n-k+2$個の直和になることを示します。
これは、$A_{n-1}$が$A_n$の商代数になっていることを利用して、数学的帰納法と次元による議論で示せます。
そうすると、$A_n$における1次元以外の単純加群を列挙することができて、これらは全て$T_{2}^n$半群代数の加群としても単純加群になります。あとは、次元に関する議論により、射影可群でもあることがわかり、所期の結果を得ます。

指標の値

自明な表現以外の指標値は、n次元単純加群における指標＋その加群の次元数ーnで与えれます。これも数学的帰納法によって同様に示せます。

圏論的な形

森田同値で言えば$A_2$型の道代数に独立な点を$n-2$個増やして得られる代数と森田同値になります。

mを一般にした場合（n=1）

$n=2$だと少し大変そうなので、$n=1$で$m\geq 2$とします。
~~多分、単位的です。（斜めに1が並ぶ奴を作れるので）~~
半群のままだと、単位的じゃないです。

半群のままだと、半群の要素数＝半群代数の次元は二項係数を使って$C(2m-1,m-1) - 1$という計算になります。

これは、実は半群に単位元を追加してやってモノイドにしたほうが色々な意味で見通した良くて、要素数は$C(2m-1,m-1)$になり、単位的な代数に対しての表現論の一般論が使えます。
このモノイドについて色々と計算をした結果、単純な加群は$m$個あって、各単純加群の次元は$0\leq i \leq m - 1$として$C(m-1,i)$で、$C(m-1,i)$がTopの射影加群は$C(m-1,i+1)$をradに持つような構造になっています。
それでパスカルの三角形的な次元の計算をすると、$C(2m-1,m-1)$と一致します。

射影加群の候補となる、Topが$C(m-1,i)$に対応する加群は、今までと同じようにrankによる分解によって具体的に構成できます。必ずしも直和ではないですが、組成列としてそのようなことが言えるので、モノイド環に関する次元についての議論をすれば、上の主張が言えるはず。

そうすると、$A_m$型でまっすぐ繋いだ道代数を長さ2以上の経路のなす（両側）イデアルで割った代数と森田同値になります。これはそれっぽい結果ですね。
このモノイドの表現についての考察は、もう少しきちんと別の記事にまとめます。

指標表を作って眺めたり、rankの一覧を作って眺めたり、かつては手作業でやっていたであろう事がPython等によって簡単に計算できて、随分楽な時代になったものですね。

なんだか面白くなってきてしまったので、もう少し色々考えそう…