はじめに
基本的に自分用のメモ。こういうまとめを見たことがないので記しておく。記述はてきとー。用語もひょっとしたら間違ってる。
可換代数
$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.