はじめに

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

可換代数

$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$ を

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$ について以下は同値。

$A\in \langle X_n\rangle$
$A$ は $X_n$ と可換
$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$ について以下は同値。

$A\in \langle X_n\rangle$
$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$ を

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$ について以下は同値。

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

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

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

$A\in \langle W_n\rangle$
$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$ を

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$ に対するクロスサム条件を

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

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

\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$ について以下は同値。

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

証明
自明！

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

$A\in \langle B_n\rangle$
$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)$ を

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$ について

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

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

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

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

証明
1$\to$ 2
自明

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

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}

一方で

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$ を計算する方法を考えよう。

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}

とおく。すると、

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)$ は

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

で与えられることが分かる。Bostan–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)$ と等しい。また、

\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$ を計算するために

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

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

\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–Masseyアルゴリズムを用いる計算量 $O(n^2)$ の確率的アルゴリズムがある。
ステップ3 は繰り返し二乗法等のアルゴリズムで計算量 $O(\mathsf{M}(n)\log k)$ である。
ステップ4 は $O(n^2)$ である。
よって合計で計算量 $O(n^3 + \mathsf{M}(n)\log k)$ となる。

参考文献

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