可換代数と行列の性質

# はじめに

基本的に自分用のメモ。こういうまとめを見たことがないので記しておく。記述はてきとー。用語もひょっとしたら間違ってる。

# 可換代数

**$K$-代数 (結合多元環, associative algebra)**
体 $K$ 上の線形空間 $V$ が積 $V\times V\to V$ を持ち、その単位元を持ち分配法則とか満たすとき $V$ (と演算を合わせたもの)を $K$-代数と呼ぶ。

要は正方行列のクラスだと思えばよい。積が可換なとき、$K$-可換代数と呼ぶ。
$A_1,\cdots,A_n$ から生成される代数を $\langle A_1,\dotsc,A_n\rangle$ と書く。
以降、単項生成の $K$-代数(自動的に $K$-可換代数)について考える。体 $K$ については特定しない。

# 可換代数の例
## 巡回行列
$n\times n$ 行列 $X_n$ を

```math 
X_n := \begin{bmatrix}
0&0&0&0&1\\
1&0&0&0&0\\
0&1&0&0&0\\
0&0&1&0&0\\
0&0&0&1&0
\end{bmatrix}
```

と定義する。


**定理**
$n\times n$ 行列 $A$ について以下は同値。

1. $A\in \langle X_n\rangle$ 
2. $A$ は $X_n$ と可換
3. $A$ は 巡回行列


**証明**
1$\to$ 2
自明

2$\to $ 3
自明 ($AX_n=X_nA$ は $A_{i-1\bmod n,j}=A_{i,j-1 \bmod n}$ を意味する)

3$\to$ 1
$X_n^k$ はベクトルを $k$ 個だけ巡回シフトする行列になる。$X_n^0,\dotsc,X_n^{n-1}$ の線形結合で任意の巡回行列が表せる。
(別証明) 両方 $n$ 次元。




**定理**
体 $K$ が 1 の原始 $n$ 乗根 $\omega_n$ を持つとき、$n\times n$ 行列 $A$ について以下は同値。

1. $A\in \langle X_n\rangle$ 
2. $A$ は離散フーリエ基底 $\\{[1\,\omega_n^i\,\omega_n^{2i}\,\dotsm\,\omega_n^{(n-1)i}]^T\mid i = 0,\dotsc,n-1\\}$ で対角化できる

**証明**
1$\to$ 2
$X_n$ は離散フーリエ基底で対角化でる。

2$\to$ 1
両方 $n$ 次元。

## 歪巡回行列
$n\times n$ 行列 $W_n$ を

```math 
W_n := \begin{bmatrix}
0&0&0&0&-1\\
1&0&0&0&0\\
0&1&0&0&0\\
0&0&1&0&0\\
0&0&0&1&0
\end{bmatrix}
```

と定義する。


**定理**
$n\times n$ 行列 $A$ について以下は同値。

1. $A\in \langle W_n\rangle$ 
2. $A$ は $W_n$ と可換
3. $A$ は 歪巡回行列


**証明**
巡回行列のときと一緒。自明！



**定理**
体 $K$ が 1 の原始 $2n$ 乗根 $\omega_{2n}$ を持つとき、$n\times n$ 行列 $A$ について以下は同値。

1. $A\in \langle W_n\rangle$ 
2. $A$ は基底 $\\{[1\,\omega_{2n}^i\,\omega_{2n}^{2i}\,\dotsm\,\omega_{2n}^{(n-1)i}]^T\mid i = 1,3,\dotsc,2n-1\\}$ で対角化できる

**証明**
自明！


## クロスサム条件満たす行列
$n\times n$ 行列 $B_n$ を

```math 
B_n := \begin{bmatrix}
0&1&0&0&0\\
1&0&1&0&0\\
0&1&0&1&0\\
0&0&1&0&1\\
0&0&0&1&0
\end{bmatrix}
```

と定義する。

また、行列 $A$ に対するクロスサム条件を

```math 
A_{i-1,j}+A_{i+1,j}=A_{i,j-1}+A_{i,j+1},\forall i, j
```

と定義する。ただし、行列からはみ出た部分の成分は 0 とする。
クロスサム条件を満たす行列は一行目から一意に定まるし、一行目は自由に定めることができる。

```math 
\begin{bmatrix}
a&   b&     c&   d&   e\\
b& a+c&   b+d& c+e&   d\\
c& b+d& a+c+e&b+d& c\\
d& c+e& b+d& a+c& b\\
e& d& c& b& a
\end{bmatrix}
```

自明に線形結合に閉じており、その次元は $n$ となる。対称行列にもなる。


**定理**
$n\times n$ 行列 $A$ について以下は同値。

1. $A\in \langle B_n\rangle$ 
2. $A$ は $B_n$ と可換
3. $A$ は クロスサム条件を満たす

**証明**
自明！

**定理**
体 $K$ が 1 の原始 $n+1$ 乗根 $\omega_{n+1}$ を持つとき、$n\times n$ 行列 $A$ について以下は同値。

1. $A\in \langle B_n\rangle$ 
2. $A$ は離散サイン基底 $\\{[s_{n+1}(i)\,s_{n+1}(2i)\,s_{n+1}(3i)\,\dotsm\,s_{n+1}(ni)]^T\mid s_{n+1}(i):=(\omega_{n+1}^i-\omega_{n+1}^{-i})/\sqrt{2(n+1)},\, i = 1,\dotsc,n\\}$ で対角化できる

**証明**
1$\to$ 2
$B_n$ は離散サイン基底で対角化でる。

2$\to$ 1
両方 $n$ 次元。

この代数 $\langle B_n\rangle$ は $\mathcal{T}$ 代数と呼ばれることもある。


## コンパニオン行列
$n\times n$ 行列 $C_n(c)$ を

```math 
C_n(c) := \begin{bmatrix}
0&0&0&0&c_0\\
1&0&0&0&c_1\\
0&1&0&0&c_2\\
0&0&1&0&c_3\\
0&0&0&1&c_4
\end{bmatrix}
```

と定義する。

$n\times n$ 行列 $C$ について

```math 
\begin{bmatrix}
v & Cv & C^2 v &\dotsm & C^{n-1}v
\end{bmatrix}
```

という形の行列を $C$ の Krylov 行列と呼ぶ。ここで $v$ は任意の $n$ 次元ベクトルである。
Krylov 行列は線形結合について閉じている。また、$C$ を左から乗ずる操作にも閉じている。


**定理**
$n\times n$ 行列 $A$ について以下は同値。

1. $A\in \langle C_n(c)\rangle$ 
2. $A$ は $C_n(c)$ と可換
3. $A$ は $C_n(c)$ の Krylov 行列

**証明**
1$\to$ 2
自明

2$\to $ 3
$A$ の $i\in\\{0,\dotsc,n-1\\}$ 列目を $a_i$ とする。

```math 
A C_n(c) =  
\begin{bmatrix}
a_1&a_2&\dotsm a_{n-1} & \sum_{i=0}^{n-1} c_i a_i
\end{bmatrix}
```

一方で 

```math 
C_n(c) A =  
\begin{bmatrix}
C_n(c)a_0&C_n(c)a_1&\dotsm&C_n(c) a_{n-1} 
\end{bmatrix}
```

よって $i=1,\dotsc,n-1$ について $a_i = C_n(c) a_{i-1}$ が成り立つ。つまり $a_i = C_n(c)^i a_0$ が成り立つ。証明終。

(3$\to$ 2: ケーリー・ハミルトンの定理より $\sum_{i=0}^{n-1} c_i C_n(c)^i  = C_n(c)^n$ が成り立つ。)

3$\to$ 1
両方 $n$ 次元。



# 応用や関連する話題

## 鏡像法なんていらない? その1
一般的な $n$ 次元ベクトル $v$ と $A\in\langle B_n\rangle$ について $A v$ を計算する方法を考えよう。

```math 
M\left(\begin{bmatrix}v_0\\ \vdots \\ v_{n-1}\end{bmatrix}\right)
:=
\begin{bmatrix}v_0\\ \vdots \\ v_{n-1}\\0\\-v_{n-1}\\ \vdots \\ -v_0\\ 0\end{bmatrix}
```
とおく。すると、

```math 
M(B_n v) = (X_{2(n+1)} + X_{2(n+1)}^{-1}) M(v)
```
が成り立つ。
よって $M(B_n^k x) = (X_{2(n+1)} + X_{2(n+1)}^{-1})^k M(x)$ が成り立つ。
$B_n^k v$ を直接計算するには $v$ を離散サイン変換して、各成分に $(\omega_{n+1}^i + \omega_{n+1}^{-i})^k$ を掛けてから逆離散サイン変換することになる。
一方で $(X_{2(n+1)} + X_{2(n+1)}^{-1})^k M(v)$ に基づいて計算する場合は $M(v)$ を離散フーリエ変換して $(\omega_{2(n+1)}^i + \omega_{2(n+1)}^{-i})^k$ を各成分に掛けてから逆離散フーリエ変換することになる。

後者の手法のことを鏡像法と呼ぶ。$B_n$ のことを理解していれば、鏡像法を経由しないで直接離散サイン変換を使うことができる。$v$ を離散サイン変換する代わりに $M(v)$ を離散フーリエ変換するのは、離散サイン変換をその関数の奇関数拡張の離散フーリエ変換から計算することに対応する。 

これらのことから、一般に $A\in\langle B_n\rangle$ について $A v$ の計算が高速にできる。これは 巡回畳み込み ($A\in\langle X_n\rangle$) の場合と同様である。 $A\in\langle B_n\rangle$ かどうかはクロスサム条件から簡単に判定できる。

## 鏡像法なんていらない? その2
一般的な $n$ 次元ベクトル $v$ と自然数 $k$ について $B_n^k v$ を計算する方法を考えよう。

簡単な計算より $B_n$ の特性多項式 $F_n(x)$ は

```math 
\begin{align}
F_0(x) &= 1\\
F_1(x) &= x\\
F_n(x) &= xF_{n-1}(x) - F_{n-2}(x)
\end{align}
```

で与えられることが分かる。Bostan&ndash;Mori のアルゴリズムや Fiduccia のアルゴリズムを用いることで $O(n\log n)$ 回の演算で $F_n$ が計算できる。

$\Gamma(x) := x^k \bmod F_n(x)$ について $\Gamma(B_n)v$ がもとめるものになる。




## もっと速い行列累乗(上の考察はあまり関係ない)
一般的な $n\times n$ 行列 $A$ と $n$ 次元ベクトル $v$ について、$A^n v$ を計算する方法を考えよう。
Krylov 空間 $\mathrm{span}(v, Av, A^2v,\dotsc, A^{n-1} v)$ を考える。この次元を $d$ とすると、Krylov 空間は $\mathrm{span}(v, Av,\dotsc, A^{d-1} v)$ と等しい。また、

```math 
\sum_{i=0}^d c_{d-i} A^i v = 0
```

を満たす $(c_i\in K)_{i=0}^d$ で $c_0\ne 0$ であるものが存在する。 

この空間において、基底 $\\{v, Av,\dotsc, A^{d-1} v\\}$ について、$A$ の行列表示はコンパニオン行列 $C_n(c)$ となる。 
よって、$A^k v$ を計算するために

1. $Av,\dotsc, A^{d-1} v$ を計算する
2. $Γ(x) := \sum_{i=0}^{d} c_{d-i} x^i$ を計算する
3. $T(x) = \sum_{i=0}^{d-1} T_i x^i := x^k \bmod \Gamma(x)$ を計算する
4. $\sum_{i=0}^{d-1} T_i A^i v$ を計算し出力する

というアルゴリズムが得られる。
ステップ1 は愚直にやると計算量が $O(n^3)$ かかる。もう少し賢い方法として

```math 
\begin{bmatrix}
A^{2^t} v & A^{2^t+1} v & \dotsm & A^{2^{t+1}-1} v
\end{bmatrix}
=
A^{2^t}
\begin{bmatrix}
v & A v & \dotsm & A^{2^t-1} v 
\end{bmatrix}
```

を用いると計算量 $\mathsf{MM}(n)t$ で $\begin{bmatrix} v& Av&\dotsm&A^{2^t}v\end{bmatrix}$ を得ることができる。
ステップ2 は愚直にやると計算量が $O(n^3)$ かかるが、ランダムなベクトルと内積を取ってから Berlekamp&ndash;Masseyアルゴリズムを用いる計算量 $O(n^2)$ の確率的アルゴリズムがある。
ステップ3 は繰り返し二乗法等のアルゴリズムで計算量 $O(\mathsf{M}(n)\log k)$ である。 
ステップ4 は $O(n^2)$ である。
よって合計で計算量 $O(n^3 + \mathsf{M}(n)\log k)$ となる。

## 参考文献

1. Dario Bini and Milvio Capovani, Spectral and computational properties of band symmetric Toeplitz matrices, *Linear Algebra and its Applications,* vol. 52&ndash;53, pp. 99&ndash;126, 1983.
1. Joachim von zur Gathen and Jürgen Gerhard, Modern Computer Algebra, Cambridge University Press, 3rd edition, 2013.
1. Walter Keller-Gehrig, Fast algorithms for the characteristics polynomial, *Theoretical Computer Science,* vol. 36, pp. 309&ndash;317, 1985.