21

数理解析研究所講究録
第2008巻 2016年 21-28

Cellular automaton and matrix over words

東洋大学

総合情報学部佐藤忠‐Tadakazu Sato

Department of Information Science and Arts
Toyo University

1.

まえがき

‐次元セルオートマトンを議論するとき、局所関数を有向グラフで表現してその状態遷移行列を考え、その代数構造を調べることは重要である。この状態遷移行列の各要素はシンボルである。 Q をシンボルからなる有限集合とするとQ 上の行列である。この行列の固有値、固有ベクトルを求めるためにはモノQ^{*} から複素数体 \mathrm{c} 上の代数 R(Q)を定義する必要がある。本論文

イド

ではワード上の行列の転置を定義することにより、複素数体 \mathrm{c} 上の行列の自然な拡張である R(Q) 上の行列のスペクトル分解を考える。
2.

諸定義と基本的性質

1次元セルオートマトンは<Z,Q,n,f> の4組で与えられる。ここで z はセルが配置されているセル空間、
n は近傍の個数(スコープ幅)、

Q は各オートマトンの状態を表す有限集合、
f:Q^{n}\rightarrow Q は局所関数。写像 c:Z\rightarrow Q を様相といい、各オートマトンの状態の分布を表わす。この様相に局所関数 f で‐斉に変換すると新しい様相 C^{ $\dag er$} は次式で与えられる。

22\forall_{j}\in Z, c'(i)=f(c(i),c(i+1),\cdots,c(i+|N|-1))
c\rightarrow c^{\uparrow} なる対応を為 (c)=c'と書く。f。とシフト写像との合成を並列写像という。このとき次の関係が成立する。
並列写像は単射である

0

並列写像は逆変換を持つ

Q をシンボルからなる有限集合とし、 Q^{*} を Q 上の長さ 0 以上のワードのw\in Q^{*} に対して |w| はワードの長さを表す。

集合とする。

w_{1}, w_{2}\in Q^{*} に対して加法、乗法を次のように定義する。 w_{1}+w_{2}\mathrm{O}\mathcal{W}_{1} または w_{2}とする。

加法の単位元を 0 で表し -w を加法における逆元とする。加法はアーベル群である。乗法はワードの連接、乗法の単位元はヌルワード1である。乗法は結合の法則を満たし、更に加法との分配の法則を満たす。従って Q から非可換環\forall_{a\in Q} に対して aa^{-1}=a^{-1}a=1 となる a^{-1}

R(Q)が自然に定義される。

を定義する。 C を複素数体とする。 C の元の長さは 0 である。
して w を反転させたワードを t_{w} で表す。
rw を反転させたワードを素数である。

\forall_{w\in Q^{*}} に対\forall_{r\in C^{\forall}w\in Q^{*}} に対して{}^{t}(rw) =\overline{r}^{t}w と定義する。ここで \overline{r} は r と共役な複\forall_{r_{1},r_{2}\in C^{\forall}w_{1},w_{2}\in Q^{*}} に対して {}^{t}(r_{1}w_{1}+r_{2}w_{2} ) =^{t}(r_{1}w_{1})+^{t}(r_{2}w_{2})と定義し、2つの列ベクトル li,v に対して内積を <u, $\nu$>=^{t}u $\nu$ と定義する。
z, w\in R(Q)に対して w=z^{n}

上 m\times n の行列の集合を表し、のとき z=w^{1/n}と表す。

M_{m,n}(Q) で R(Q)

M_{n}(Q) で R(Q) 上 n\times n の行列の集合を表す。

23

A=\{w_{i,j}\}\in M_{m,n} に対して {}^{t}A=\{^{t}w_{j,t} } と定義する。
性質1. 次の命題が成立する。

{}^{t}(w^{1/n})=(^{ $\iota$}w)^{]/n}(1)w\in R(Q)

に対して

(2)

w\in R(Q)が逆元をもつとき(3)\forall_{A}, B\in M_{n}(Q)に対してt(W^{-1})=(^{l}W)^{-1}t(AB)=^{t}B^{t}A

局所関数 f(x_{1},\cdots,x_{n}):Q^{n}\rightarrow Q の有向グラフを次のように作る。

Q^{n-1} をノードの集合とし、ノード x_{1}\cdots x_{n-1}には f(x_{1}, \cdots, x_{n})3.

からノード x_{2}\ldots x_{n} へのエッジを付ける。この有向グラフの遷移行列を A(f) と書く。

遷移行列の固有値と固有ベクトル

非ゼロの列ベク トル V に対して A $\nu$= $\nu$冗のときを A の固有値、V を列固有ベク トルと言う。また非ゼロの行ベク トル V に対して vA=$\lambda$_{\mathcal{V}} のとき$\lambda$ を A の固有値、
例1.

V を行固有ベクトルと言う

f(x,y,z)=x+ymod2 をスコープ幅3の線形局所関数とする。

0\leftrightarrow a, 1\leftrightarrow b で符号化すると状態遷移行列は

A_{f}=\let{bginary}{l a& 0&\ 0& b&\ b& 0&\ 0& a& \end{ary}\ight},

f_{\infty} は2対1写像である。

24

A_{f} の固有値は a+b, a-b, 0 である。

a+b に対する列固有ベクトルを \mathcal{V}_{1}とし、行固有ベク トルを t_{\mathcal{U}_{1} とする。 a-b に対する列固有ベクトルを \mathcal{V}_{2} とし
行固有ベクトルを t_{u_{2} とする。 0 に対する2つの列固有ベクトルを \mathcal{V}_{3}, \mathcal{V}_{4} 、行固有ベク トルを t_{u_{3} ,t_{u_{4} として以下のようにとる。

\displayte\mahcl{V}_1=\frac{}sqt2\lef{bginary}{l \ b \ a end{ray}\ight,macl{V}_2=\frac{1}sqt2\lef{bginary}{l \ -b \ -a end{ray}\ight,macl{V}_3=\eft{bginary}{l1\ - \mathr{O}\ mathr{O}\end{ary}\ight,macl{V}_4=\eft{bginary}{l0\ 1\ - end{ary}\ight

t_{u_{1} =\displaystyle \frac{1}{\sqrt{2} (1, 1, 1, 1), t_{u_{2} =\frac{1}{\sqrt{2} (1, 1, -1, -1){}^{t}u_{3}=(a^{-1},0,-b^{-1},0), t_{u_{4^{=}}}(0, b^{-1}, 0, -a^{-\mathrm{l}})これらの固有ベクトルの間には次式が成立する。

t_{u_{1}v_{1}}=<u_{1}, V_{1}>=a+b, t_{u_{2}v_{2}=<}u_{2}, \mathcal{V}_{2}>=a-bt_{u_{1}v_{2}=<}u_{1}, \mathcal{V}_{2}>=0, t_{u_{2}v_{1}=<}u_{2}, \mathcal{V}_{1}>=0

A_{f}=v_{1}^{t}u_{1}+v_{2}^{t}u_{2}(1)

したがって任意の正の整数 n に対して

A_{f}^{n}=v_{1}^{t}u_{1}(a+b)^{n-1}+v_{2}^{t}u_{2}(a-b)^{n-1}trA_{f}^{n}=(a+b)^{n}+(a-b)^{n}=2(a^{n}+\cdots)
このことからもんは2対1写像である。

25(1) 式は一種のスペクトル分解であるが行および列固有ベクトルが正規直交系をなしていない。これを正規直交系にしたい。このとき次の定理が成立する。

定理1.

A\in M_{n}( $\Sigma$) が n 個の列固有ベクトル v_{1},,v_{n} を持つとき

P=(v_{1},\cdots,v_{n})\in M_{n}( $\Sigma$) が正則なら A は次式のようにスペクトル分解される。

\displayst le\mathrm{A}=\sum_{i=1}^{n}v_{i}$\lambda$_{i}^{t}u_{i}
ここで

Av_{i}=v_{i}A_{i}(1\leq i\leq n),(_{$\iota$}^{t}:u_{n}u_{1}]\equiv( _{1},\cdots,v_{n})^{-1}とおく。

\left{\begin{ar y}{l ^{t}u_1\ {}^tu_{n} \end{ar y}\ight}(v_{1,\cdots,v_{n})=\left(bgin{ar y}{l <u_{1},v\mathr {l}>&\cdots&<u_{1},vn>\ & \ <u_{n},v\mathr {l}>&\cdots&<u_{n},v > \end{ar y}\ight)=I(v_{1},\cdots,v_{n})\left\{ begin{ar y}{l }^{tu_{\mathrm{l}\ \ {}^tu_{n} \end{ar y}\right\}=v_{1} ^{t}u_{1}+\cdots+v_{n} ^{t}u_{n}=I
例2.

A_{f}=\let{bginary}{l a& 0&\ 0& b&\ b& 0&\ 0& a& \end{ary}\ight}

A_{f} の列固有ベクトルを v_{1},の正規直交系によるスペクトル分解,

v_{n} 次のように選んで行列 (v_{1},\cdots,v_{n}) を作る(v_{1}\cdotsv_{4})=\left{begin{ar y}{l a& 1&0\ b&- \mathr{l}&0\ b& 0&1\ a&- 0&-1 \end{ar y}\ight},$\lambda$=a+b,$\gamma$=a-b

とおいて26[^{t}:u_41)\eqiv({}cdots_4)^-1=\lef{bginary}l\fc{$gam^-1}\frc{2mathl}$\bd^{-1&frac}$\gm^{-1frac}2$\lmbda^{-1}&frc2$\gam^{-1}frc2$\lambd^{-1}&frac2$\gm^{-1}frac\thm{l2}$abd^-1\ frac{} b,2($\gam^{-thrl}+$\ambd^{-1)(gma$}+\lbd^{-1)&frac}\{b2(r^-1}+$\lambd{)(gma$^-1}+\lbd{)&1+\fracb}2($gm^{-1}\labd$)frc{a}2(\gm$^-1}labd{)&\frac}($gm^{-1\labd$})frc{a2($\gm^{-1}labd$)\en{ary}ight
A_{f}=v_{1}$\lambda$^{\mathrm{t} u_{1}+v_{2}$\gamma$^{t}u_{2}=\displayte\lft{\begin{ar y}{l a\ b\ b\ a \end{ar y}\right\}(a+b)\frac{1}2$\lambd$^{-1},\frac{1}2$\lambd$^{-1},\frac{1}2$\lambd$^{-1},\frac{1}2$\lambd$^{-\mathrm{I})+\left{\begin{ar y}{l a\ -b\ b\ -a \end{ar y}\right\}(a-b)\frac{1}2$\gam $^{-1},\frac{1}2$\gam $^{-1},\frac{1}2$\gam $^{-1},\frac{1}2$\gam $^{-1})=\displayte\lft{begin{ary}l a\ b \ a\end{ary}\ight}(\frac{1}2\frac{1}2,\frac{1}2,\frac{1}2)+\left{bgin{ary}l a\ -b\ -a\end{ary}\ight}(\frac{1}2'\frac{1}2,-\frac{1}2,-\frac{1}2)=\left{bgin{ary}l a& 0&\mathr{O}\ 0&\mathr{O}&b \ b& 0&\ 0& a& \end{ary}\ight}
例3.

g(x,y)=2x+ymod3

をスコープ幅2の線形局所関数とする。

0\leftrightarrow a, 1\leftrightarrow b, 2\leftrightarrow c で符号化すると状態遷移行列 A_{g} はA_{g}=\left{\begin{ar y}{l a,bc\ ac,b\ b,ca \end{ar y}\right\},g_{\infty} は3対1写像である。

A_{g} の固有値をろ,4,うとすると
ろ =a+b+c,$\lambda$_{2}=a+be^{i2 $\pi$/3}+ce^{i4\prime r/3},

4=a+be^{i4 $\pi$-3}+ce^{i2 $\pi$/3}$\lambda$_{ \gam a$} ,4,ろ の固有ベクトルをそれぞれ v_{1}, v_{2}, v_{3} で表すと

27

v_{1}=\displayte\frac{1}\sqrt{3}\left{bgin{ary}l 1\ 1\end{ary}\ight},v_{2=\frac{1}\sqrt{3}\left{bgin{ary}l e^{i2$\p/3}\ e^{i4$\p/3}\ 1\end{ary}\ight},v_{3=\frac{1}\sqrt{3}\left{bgin{ary}l e^{i4$\p/3}\ e^{i2$\p/3}\ 1\end{ary}\ight}<v_{i},v_{j}\succ=^{t}v_{j}v_{j}=$\delta$_{i,j}, P\equiv(v_{1},v_{2},v_{3}), {}^{t}PP=I

P^{-1}AP=(0 $\lambda$_{2}0 $\lambda$_{3}0 ],A=P\left(\begin{ar y}{l } a+b c&0&0\ 0&$\lambda$_{2}&0\ 0&0&$\lambda$_{3} \end{ar y}\right)P^{-1}
例4.

h(x,y)=x+ymod3をスコープ幅2の線形局所関数とする。

0\leftrightarrow a, 1\leftrightarrow b, 2\leftrightarrow c で符号化すると状態遷移行列 A_{h} は

A_{h}=[_{c,ab}^{a,bc}b_{-}c_{-}a)$\lambda$_{\mathrm{J}}=a+b+c,h_{\infty} は3対1写像である.

ろ =a+be^{i2rr/3}+ce^{i4 $\pi$/3},とおくと A_{h} の3つの固有値はろ,ろ亀,‐

h=a+be^{i4 $\pi$/3}+ce^{i2 $\pi$/3}$\lambda$_{2} ろである。このときl(ろ) =$\lambda$_{\mathrm{p} ,t(ろ )=$\lambda$_{\mathrm{T} したがってt &う =\sqrt{$\lambda$_{7}$\lambda$_{2} が成立する。そして、それぞれの列固有ベ,クトルを以下のように v_{1},v_{2},v_{3} とすると

28

v_{1},=\displayte\frac{1}sqrt3[_{1}^ ),v_{2}=\frac1{sqrt6}\lef{bginary}{l$\ambd_{$\gam }^{-1\sqrt$lambd_{1}$\lambd_{2}+1\ e^{i2$\p/3}lambd$_{1}^-\mathr{l}\sqt$lambd_{\athrml}$\abd_{2}+e^i4$\p/3} e^{i4$\p/3}lambd$_{\athrml}^{-]\sqrt$lambd_{\athrml}$\abd_{2}+e^i$\p/3} end{ary}\ight,v_{3}=\displayte\frac{1}\sqrt{6}[_-e^{i4$\p/3}tex{ろ^-}1\sqrt{A_1} {2+e^i$\p/3}^{-\texろ^{-}1\sqrt{A_1}$\lambd$_{2}+1-e^{i2$\p/3}A_{\mathr{T}^-1\sqrt{$lambd$_{\eta$} lmbda$_{2}+e^i4$\p/3}),

このとき <v_{j},v_{j}>=^{t}v_{i}v_{j}=$\delta$_{i,j}なのでP\equiv(v_{1},v_{2},v_{3}) とおくと{}^{t}PP=I が成立する。したがって、次式が成立する。

P^{-1}AP=[0 \sqrt{\text{うろ} 0 -0\sqrt{$\lambda$_{1}A_{2} 0),A=P[0 \sqrt{\text{ろ$\lambda$_{}2 }0 -\sqrt{$\lambda$_{7}$\lambda$_{2} 0 )\mathrm{t}P{}^{t}A=A であり、 \mathrm{A} は対称行列である。
注意1. 複素数対上のエルミット行列の固有値は実数であるが、非可換環上の対称行列の固有値は必ずしも実数値になるとは限らない。
参考文献

佐藤、「単射であるセルラーオートマトンの性質について」
RIMS 1915,158‐160,2014