巡回行列
概要
巡回行列（circulant matrix）とは、第 $0$ 行が $(c(0),\dots,c(n-1))$ で、各行が 1 つ上の行を右へ 1 つ巡回的にずらしたものである $n$ 次正方行列、すなわち $(j,k)$ 成分が $c(k-j)$（添字は $n$ で割った余り）の行列のことである。巡回シフト行列 $S$ と可換な行列と同じで、全体は $K[x]/(x^n-1)$ と同型な可換環をなす。体が $1$ の原始 $n$ 乗根 $\zeta$ をもつとき、すべての巡回行列は Fourier 行列で同時に対角化され、固有値は $\sum_mc(m)\zeta^{tm}$、行列式はその積である。
前提知識: 行列式, 固有値, 多項式環, 離散Fourier変換と反転公式
長さ $n$ の数列 $c(0),c(1),\dots,c(n-1)$ から、第 $0$ 行を $\bigl(c(0),c(1),\dots,c(n-1)\bigr)$ とし、各行を 1 つ上の行を右へ 1 つ巡回的にずらしたものにして作る $n$ 次正方行列を 巡回行列（circulant matrix）という。$n=3$ なら
$$
\begin{pmatrix}c(0)&c(1)&c(2)\\ c(2)&c(0)&c(1)\\ c(1)&c(2)&c(0)\end{pmatrix}
$$
である。巡回行列は、成分を 1 つずつ巡回的にずらす置換行列 $S$ と可換な行列のことであり、$S$ の多項式として書ける行列のことでもある。そのため巡回行列どうしの積は可換で、巡回行列の全体は多項式環の剰余環 $K[x]/(x^n-1)$ と同じ構造をもつ。
複素数を成分とする巡回行列は、成分によらない共通の固有ベクトル $v_t=(1,\zeta^t,\zeta^{2t},\dots,\zeta^{(n-1)t})^{\top}$（$\zeta=e^{2\pi i/n}$）をもち、すべて同じ行列（Fourier 行列）で同時に対角化される。固有値は多項式 $p_c(x)=\sum_mc(m)x^m$ の $1$ の $n$ 乗根での値 $p_c(\zeta^t)$ であり、行列式・階数・逆行列がそこから読み取れる。巡回行列を掛けることは巡回畳み込みをとることなので、巡回行列を係数とする連立 1 次方程式は離散 Fourier 変換で成分ごとの式に分かれる。
| 結果 | 内容 |
|---|---|
| thm-circ-algebra | 巡回行列 $\iff$ $S$ と可換 $\iff$ $S$ の多項式。全体は $K[x]/(x^n-1)$ と同型 |
| thm-circ-diag | Fourier 行列による同時対角化。固有値は $p_c(\zeta^t)$ |
| cor-circ-det | 行列式 $\prod_tp_c(\zeta^t)$、正則性と逆行列、正規性 |
| ex-circ-counterexamples | 巡回させない、逆向きにずらす、$1$ の原始 $n$ 乗根がない体、のそれぞれで結論が崩れる |
定義
以下、$n\ge1$ とし、行列の行と列の番号を $0,1,\dots,n-1$ とする。添字はすべて $n$ で割った余りで考える。たとえば $c(-1)=c(n-1)$、$c(n)=c(0)$ である。$K$ は可換環（thm-circ-diag 以降は体）とし、$e_0,\dots,e_{n-1}$ を $K^n$ の標準基底（列ベクトル）とする。
$K$ の元の列 $c=\bigl(c(0),\dots,c(n-1)\bigr)$ に対し、$(j,k)$ 成分が
$$
\operatorname{circ}(c)_{jk}:=c(k-j)\qquad(0\le j,k\le n-1、添字は n で割った余り)
$$
である $n$ 次正方行列 $\operatorname{circ}(c)$ を、$c$ を第 $0$ 行とする 巡回行列 という。$c$ に多項式
$$
p_c(x):=\sum_{m=0}^{n-1}c(m)\,x^m
$$
を対応させ、これを $\operatorname{circ}(c)$ の 表示多項式 と呼ぶ。また $c=(0,1,0,\dots,0)$ の巡回行列を $S$ と書き、巡回シフト行列 という。
$S$ の $(j,k)$ 成分は $k\equiv j+1\pmod n$ のときだけ $1$ で、ほかは $0$ である。したがって
$$
(Sx)_j=x_{j+1}\qquad\bigl(x={}^{t}(x_0,\dots,x_{n-1})\bigr),\qquad Se_k=e_{k-1}
$$
であり、$S$ はベクトルの成分を 1 つずつ前に送る置換行列である（置換行列）。$(j,k)$ 成分が $c(k-j)$ であることは、$(j,k)$ 成分が $k-j$ の余りだけで決まること、すなわち「行列の各対角線（端で折り返して続けたもの）の上で成分が一定」ということである。
流儀の注意：$(j,k)$ 成分を $c(j-k)$ とし、$c$ を第 $0$ 列にとる流儀もある（VKG14 (2.245)、p. 150）。その行列はこの記事の $\operatorname{circ}(c)$ の転置で、$c$ を $m\mapsto c(-m)$ に替えた列の巡回行列でもあるので、以下の結果は添字の符号を読み替えればそのまま成り立つ。この記事の流儀は 離散Fourier変換と反転公式 の節「巡回行列の固有ベクトル」と同じである。
直感
巡回行列は「番号が輪になって並んだ $n$ 個の場所」の上の、平行移動で形を変えない線形な操作である。各場所の新しい値を、自分から $m$ 個先の場所の値に重み $c(m)$ を掛けて足し合わせて作る：$(\operatorname{circ}(c)x)_j=\sum_mc(m)x_{j+m}$。重みが場所によらないので、操作は輪を回す $S$ と可換になる。輪を回す操作の固有ベクトルは「1 周で $t$ 回まわる波」$v_t$ であり、平行移動と可換な操作は波の形を変えず振幅だけを変える。これが、巡回行列がすべて同じ固有ベクトルで対角化される理由である。
例
- $n=2$：$\operatorname{circ}(a,b)=\begin{pmatrix}a&b\\ b&a\end{pmatrix}$ で、$\zeta=-1$ なので固有値は $p(1)=a+b$、$p(-1)=a-b$ である。実際 $\det=a^2-b^2=(a+b)(a-b)$ である。
- $n=3$：$\omega:=e^{2\pi i/3}$ とすると、$\operatorname{circ}(a,b,c)$ の固有値は $a+b+c$、$a+b\omega+c\omega^2$、$a+b\omega^2+c\omega$ であり、cor-circ-det により
$$ a^3+b^3+c^3-3abc=(a+b+c)(a+b\omega+c\omega^2)(a+b\omega^2+c\omega) $$
である。左辺は Sarrus の方法で行列式を展開した値である。$a=1$、$b=c=0$ なら左辺 $1$、右辺 $1\cdot1\cdot1$ で合う。$a=b=c=1$ なら左辺 $0$ で、右辺の第 1 因子は $3$、第 2 因子は $1+\omega+\omega^2=0$ である。
- $L:=2I-S-S^{-1}$、すなわち $c=(2,-1,0,\dots,0,-1)$（$n\ge3$）の巡回行列は、$n$ 個の頂点が輪になったグラフの Laplace 行列である（各頂点で、値の 2 倍から両隣の値を引く）。表示多項式は $p(x)=2-x-x^{n-1}$ で、$\zeta^{t(n-1)}=\zeta^{-t}$ なので固有値は
$$ p(\zeta^t)=2-\zeta^t-\zeta^{-t}=2-2\cos\frac{2\pi t}{n}=4\sin^2\frac{\pi t}{n}\qquad(t=0,\dots,n-1) $$
である。$t=0$ の固有値 $0$ の固有ベクトルは定数ベクトル $v_0$ であり、ほかの固有値は正である。 - すべての成分が $1$ の行列 $J=\operatorname{circ}(1,\dots,1)$ は $p(x)=1+x+\cdots+x^{n-1}$ をもち、固有値は $p(1)=n$ と、$t\ne0$ での $p(\zeta^t)=\frac{\zeta^{tn}-1}{\zeta^t-1}=0$ である。よって $J$ の階数は $1$ である。
性質
巡回行列の全体がなす環
$K$ を可換環とし、$A=(a_{jk})\in M_n(K)$ とする。
- 次は同値である。(i) $A$ は巡回行列である。(ii) $AS=SA$。(iii) $A=f(S)$ となる多項式 $f\in K[x]$ がある。
- $\operatorname{circ}(c)=p_c(S)=\sum_{m=0}^{n-1}c(m)S^m$ である。
- $K$ 上の多項式に $x\mapsto S$ を代入する写像は、環の同型
$$ \Phi\colon K[x]/(x^n-1)\xrightarrow{\ \sim\ }\{n\text{ 次の巡回行列の全体}\},\qquad p_c(x)\bmod(x^n-1)\mapsto\operatorname{circ}(c) $$
を引き起こす。特に巡回行列どうしの和・積・スカラー倍はまた巡回行列であり、巡回行列どうしは可換である。 - 積の表示多項式は $p_ap_b$ を $x^n=1$ で簡約したもので、成分では
$$ \operatorname{circ}(a)\operatorname{circ}(b)=\operatorname{circ}(a*b),\qquad (a*b)(k):=\sum_{m=0}^{n-1}a(m)\,b(k-m) $$
（巡回畳み込み）である。
段 1（$S^m$ の成分）．$S^m$ は $c(m)=1$、ほかは $0$ の列の巡回行列である。実際 $(S^m)_{jk}=1$ となるのは $k\equiv j+m$ のときだけであることが、$m$ についての帰納法で分かる（$(S^{m+1})_{jk}=\sum_l(S^m)_{jl}S_{lk}$ で $0$ でない項は $l\equiv j+m$、$k\equiv l+1$ のとき）。したがって $\sum_mc(m)S^m$ の $(j,k)$ 成分は、$m\equiv k-j$ となるただ 1 つの $m$ の係数 $c(k-j)$ であり、2 が成り立つ。$S^n=I$ も同じ計算から分かる。
段 2（1 の同値）．(i) ならば (iii) は 2 による。(iii) ならば (ii) は、$S$ の多項式が $S$ と可換であることによる。(ii) ならば (i)：成分で $(AS)_{jk}=\sum_la_{jl}S_{lk}=a_{j,k-1}$、$(SA)_{jk}=\sum_lS_{jl}a_{lk}=a_{j+1,k}$ である。$AS=SA$ なら、すべての $j,k$ で $a_{j+1,k}=a_{j,k-1}$、すなわち $a_{j+1,k+1}=a_{jk}$ である。これをくり返すと $a_{jk}=a_{0,k-j}$ となり、$A=\operatorname{circ}(c)$、$c(m):=a_{0m}$ である。
段 3（3 の同型）．代入 $f\mapsto f(S)$ は環準同型 $K[x]\to M_n(K)$ で、$S^n=I$ なので $x^n-1$ を $0$ に送り、$K[x]/(x^n-1)$ からの環準同型 $\Phi$ を引き起こす。$K[x]/(x^n-1)$ の元は $1,x,\dots,x^{n-1}$ の係数でただ 1 通りに書ける（$x^n-1$ はモニックなので割り算ができる）。段 1 より $\Phi\bigl(\sum_mc(m)x^m\bigr)=\operatorname{circ}(c)$ の第 $0$ 行は $c$ なので、$\Phi$ の値から $c$ が読み取れる。よって $\Phi$ は単射であり、1 と 2 から像はちょうど巡回行列の全体である。$K[x]/(x^n-1)$ は可換環なので、像の元どうしも可換である。
段 4（4 の式）．$p_a(x)p_b(x)=\sum_{m,l}a(m)b(l)x^{m+l}$ を $x^n=1$ で簡約すると、$x^k$ の係数は $m+l\equiv k$ となる組の和 $\sum_ma(m)b(k-m)$ である。3 によりこれが積 $\operatorname{circ}(a)\operatorname{circ}(b)$ の第 $0$ 行である。$\square$
段 2 の計算は、$A\mapsto S^{-1}AS$ が成分を対角線に沿って 1 つずらす操作であることを示している。thm-circ-algebra の 3 によって、巡回行列についての問いは剰余環 $K[x]/(x^n-1)$ の問いに言い換えられる。たとえば $\operatorname{circ}(c)$ が $K$ 上で正則であることは、$p_c$ が $K[x]/(x^n-1)$ で可逆であることと同値である。実際、$A=\operatorname{circ}(c)$ が $M_n(K)$ で逆行列をもてば、$AS=SA$ の両側に $A^{-1}$ を掛けて $SA^{-1}=A^{-1}S$ となるので、1 により $A^{-1}$ も巡回行列であり、$\Phi$ は単位元 $1$ を $I$ に送る同型なので $A^{-1}$ に対応する元が $p_c$ の逆元になる。逆向きは $\Phi$ が積を保つことから従う。
Fourier 行列による同時対角化
体 $K$ の元 $\zeta$ が $\zeta^n=1$ を満たし、$0< m< n$ では $\zeta^m\ne1$ であるとき、$\zeta$ を $1$ の 原始 $n$ 乗根 という。複素数では $\zeta=e^{2\pi i/n}=\cos\frac{2\pi}n+i\sin\frac{2\pi}n$ がその例である。
$K$ を体、$\zeta\in K$ を $1$ の原始 $n$ 乗根とする。$t=0,\dots,n-1$ について
$$
v_t:={}^{t}\bigl(1,\zeta^t,\zeta^{2t},\dots,\zeta^{(n-1)t}\bigr),\qquad F:=\bigl(v_0\ v_1\ \cdots\ v_{n-1}\bigr)=\bigl(\zeta^{jt}\bigr)_{0\le j,t\le n-1}
$$
とおく。
- $n$ は $K$ で $0$ でなく、$F$ は正則で、$F^{-1}=\frac1n\bigl(\zeta^{-tk}\bigr)_{0\le t,k\le n-1}$ である。
- すべての $c$ と $t$ について $\operatorname{circ}(c)\,v_t=p_c(\zeta^t)\,v_t$ である。したがって
$$ \operatorname{circ}(c)=F\operatorname{diag}\bigl(p_c(1),p_c(\zeta),\dots,p_c(\zeta^{n-1})\bigr)F^{-1} $$
であり、$n$ 次の巡回行列はすべて同じ行列 $F$ で同時に対角化される。 - $K=\mathbb{C}$、$\zeta=e^{2\pi i/n}$ のとき、$U:=\frac1{\sqrt n}F$ はユニタリ行列であり、$\operatorname{circ}(c)=U\operatorname{diag}\bigl(p_c(\zeta^t)\bigr)_tU^*$ である。
段 1（$1$ の冪根の和）．$G:=\bigl(\zeta^{-tk}\bigr)_{t,k}$ とおく。$FG$ の $(j,k)$ 成分は $\sum_{t=0}^{n-1}\zeta^{t(j-k)}$ である。$j=k$ ならこれは $n\cdot1$ である。$j\ne k$ なら $q:=\zeta^{j-k}$ は、$j-k$ が $n$ の倍数でないので $q\ne1$ であり、$q^n=1$ から等比数列の和は $\frac{q^n-1}{q-1}=0$ である。よって $FG=n\,I$ である。
段 2（$n\ne0$ と $F$ の正則性）．$F$ は相異なる $n$ 個の元 $1,\zeta,\dots,\zeta^{n-1}$ の Vandermonde 行列 $\bigl((\zeta^j)^t\bigr)_{j,t}$ なので、行列式は $\prod_{j< j'}(\zeta^{j'}-\zeta^j)\ne0$ であり（Vandermondeの行列式 の定理「Vandermonde の行列式の公式」）、$F$ は正則である。$K=\mathbb{C}$ の場合の段 1 の式は、同じ記事の命題「1 の冪根の Vandermonde 行列」でもある。$n=0$ なら $FG=O$ から $G=F^{-1}O=O$ となるが、$G$ の成分 $\zeta^0=1$ は $0$ でないので矛盾する。よって $n\ne0$ で、$F^{-1}=\frac1nG$ である。
段 3（シフトの固有ベクトル）．$Sx$ の第 $j$ 成分は $x_{j+1}$ なので、$Sv_t$ の第 $j$ 成分は $\zeta^{(j+1)t}=\zeta^t\cdot\zeta^{jt}$ である（$j=n-1$ では $x_{j+1}=x_0=1$ で、$\zeta^{nt}=1$ から $\zeta^{(j+1)t}=1$ と一致する）。よって $Sv_t=\zeta^tv_t$、$S^mv_t=\zeta^{tm}v_t$ であり、thm-circ-algebra の 2 から
$$
\operatorname{circ}(c)\,v_t=\sum_mc(m)S^mv_t=\sum_mc(m)\zeta^{tm}v_t=p_c(\zeta^t)\,v_t
$$
である。列ごとに書けば $\operatorname{circ}(c)F=F\operatorname{diag}(p_c(\zeta^t))_t$ であり、右から $F^{-1}$ を掛けて 2 を得る。
段 4（ユニタリ性）．$\zeta=e^{2\pi i/n}$ では $\overline{\zeta^{jt}}=\zeta^{-jt}$ なので $G$ は $F$ の共役転置 $F^*$ に等しく、段 1 は $F^*F=FF^*=nI$、すなわち $U^*U=I$ を意味する。$F^{-1}=\frac1nF^*$ を 2 に代入すれば 3 になる。$\square$
$S$ の固有多項式が $t^n-1$ であることは 置換行列 の記事でも別の方法（最小多項式）で示されているが、thm-circ-diag の証明は固有ベクトルを直接書き下すので、固有値 $1,\zeta,\dots,\zeta^{n-1}$ と対角化が同時に得られる。
$K,\zeta$ を thm-circ-diag のとおりとし、$C=\operatorname{circ}(c)$、$\lambda_t:=p_c(\zeta^t)$ とおく。
- $\det C=\prod_{t=0}^{n-1}\lambda_t$ であり、固有多項式は $\prod_t(x-\lambda_t)$ である。$C$ の階数は $\lambda_t\ne0$ となる $t$ の個数に等しい。
- $C$ が正則であることは、すべての $t$ で $\lambda_t\ne0$ であることと同値である。このとき $C^{-1}$ は巡回行列で、その固有値は $\lambda_t^{-1}$ である。
- $K=\mathbb{C}$ のとき、$C$ は正規行列である。さらに $C$ が Hermite 行列であることは、すべての $m$ で $c(-m)=\overline{c(m)}$ であることと同値であり、そのときすべての $\lambda_t$ は実数である。
$D:=\operatorname{diag}(\lambda_t)_t$ とおくと thm-circ-diag により $C=FDF^{-1}$ である。
1：相似な行列は行列式・固有多項式・階数が等しく、対角行列 $D$ ではそれぞれ $\prod_t\lambda_t$、$\prod_t(x-\lambda_t)$、$0$ でない対角成分の個数である。
2：1 から $\det C\ne0$ と「すべての $\lambda_t\ne0$」は同値である。このとき $C^{-1}=FD^{-1}F^{-1}$ であり、$C^{-1}$ は $S$ と可換なので（$CS=SC$ の両側に $C^{-1}$ を掛ける）thm-circ-algebra の 1 により巡回行列である。
3：thm-circ-diag の 3 により $C=UDU^*$ で、$C^*=UD^*U^*$ である。$DD^*=D^*D$ なので $CC^*=UDD^*U^*=UD^*DU^*=C^*C$ である。また $C^*$ の $(j,k)$ 成分は $\overline{C_{kj}}=\overline{c(j-k)}$ なので、$C^*=\operatorname{circ}(c^*)$、$c^*(m):=\overline{c(-m)}$ である。巡回行列は第 $0$ 行で決まるので、$C=C^*$ は $c=c^*$、すなわち $c(-m)=\overline{c(m)}$ と同値である。そのとき $D=U^*CU$ は Hermite 行列で対角なので、対角成分 $\lambda_t$ は実数である。$\square$
1 の行列式の式は、$\lambda_t$ を $c(0),\dots,c(n-1)$ の多項式と見れば、$\mathbb{Z}[\zeta][c(0),\dots,c(n-1)]$ の中の恒等式であり、ex-circ-small の 3 次の場合がその例である。
巡回畳み込みと離散 Fourier 変換
$Cx$ の第 $j$ 成分は
$$
(Cx)_j=\sum_{k}c(k-j)\,x_k=\sum_mc(m)\,x_{j+m}
$$
である。$\check c(m):=c(-m)$ とおくと、これは $x$ と $\check c$ の巡回畳み込み $\sum_kx_k\,\check c(j-k)$ に等しい（離散Fourier変換と反転公式 の定義「巡回畳み込み」）。同じ記事の離散 Fourier 変換 $\widehat f(t)=\sum_kf(k)\zeta^{-tk}$ を使うと
$$
\widehat{\check c}(t)=\sum_mc(-m)\zeta^{-tm}=\sum_mc(m)\zeta^{tm}=p_c(\zeta^t)=\lambda_t
$$
であり、畳み込みが変換で積になること（同じ記事の命題「畳み込みは変換で積になる」）から $\widehat{Cx}(t)=\lambda_t\,\widehat x(t)$ である。これは $F^{-1}=\frac1nG$ の各行が変換 $x\mapsto\widehat x$ を与えていることを使って、thm-circ-diag の 2 を書き直したものである。したがって $Cx=b$ を解くには、$b$ を変換し、成分ごとに $\lambda_t$ で割り、逆変換すればよい。高速 Fourier 変換を使えば、その計算量は $n\log n$ 程度である（VKG14 §2.6、p. 134 と式 (3.271)、p. 307。同じ対角化は同書 §3.6.3 の式 (3.181)、p. 259 に、第 $0$ 列を与える流儀で述べられている）。
$n=4$、$\zeta=i$、$C=\operatorname{circ}(2,1,0,1)$ として $Cx=b$、$b={}^{t}(4,0,0,0)$ を解く。$p(x)=2+x+x^3$ なので固有値は $\lambda_0=4$、$\lambda_1=2+i+i^3=2$、$\lambda_2=2-1-1=0$、$\lambda_3=2-i+i=2$ であり、$\lambda_2=0$ なので $C$ は正則でない（cor-circ-det の 2）。実際、$v_2={}^{t}(1,-1,1,-1)$ について $Cv_2=0$ である。$b$ を変換すると $\widehat b(t)=4$（すべての $t$）なので、$t=2$ の式 $0\cdot\widehat x(2)=4$ が解けず、$Cx=b$ に解はない。右辺を $b'={}^{t}(4,0,4,0)$ にすると $\widehat{b'}=(8,0,8,0)$ で、$t=2$ の式は $0\cdot\widehat x(2)=8$ となり、やはり解はない。$b''={}^{t}(1,1,1,1)$ なら $\widehat{b''}=(4,0,0,0)$ で、$\widehat x(0)=1$、$\widehat x(1)=\widehat x(3)=0$、$\widehat x(2)$ は任意となり、$x=\frac14{}^{t}(1,1,1,1)+s\,v_2$（$s$ は任意）が解のすべてである。
条件を外したときの反例
| 外した条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 端で折り返す（成分 $c(k-j)$ の添字を $n$ で割った余りで考える） | $T=\begin{pmatrix}0&1\\0&0\end{pmatrix}$ | $S$ との可換性と対角化（thm-circ-algebra・thm-circ-diag） |
| 各行を右へずらす | $H=\begin{pmatrix}1&0&0\\0&0&1\\0&1&0\end{pmatrix}$（各行を左へずらした行列） | $v_t$ が固有ベクトルであること（thm-circ-diag の 2） |
| $K$ が $1$ の原始 $n$ 乗根をもつ | $K=\mathbb{F}_3$、$n=3$ の $S$ | 対角化できること（thm-circ-diag の 2） |
1 行目：$T$ は各対角線（$k-j=0$ の位置は $0$、$k-j=1$ は $1$、$k-j=-1$ は $0$）の上で成分が一定だが、端で折り返すと $(1,0)$ 成分は $c(-1)=c(1)=1$ でなければならず、巡回行列ではない。このように折り返さない行列を Toeplitz 行列という（VKG14 (2.246)、p. 150）。$n=2$ の $S=\begin{pmatrix}0&1\\1&0\end{pmatrix}$ について $TS=\begin{pmatrix}1&0\\0&0\end{pmatrix}\ne\begin{pmatrix}0&0\\0&1\end{pmatrix}=ST$ である。また $T^2=O$、$T\ne O$ なので $T$ はどの体の上でも対角化できない（対角化できれば固有値はすべて $0$ で、$T=O$ になる）。
2 行目：$H$ の第 1 行・第 2 行は、それぞれ 1 つ上の行を左へ 1 つ巡回的にずらしたもので、$H$ は「右へ」の条件だけを満たさない。$\omega=e^{2\pi i/3}$ として $Hv_1=H\,{}^{t}(1,\omega,\omega^2)={}^{t}(1,\omega^2,\omega)=v_2$ であり、第 $0$ 成分が $1$ どうしなので $Hv_1$ が $v_1$ の定数倍なら定数は $1$ だが、$\omega^2\ne\omega$ なので $v_1$ は $H$ の固有ベクトルでない。$H$ は対称行列なので別の直交基底では対角化できるが、すべての巡回行列に共通の $v_t$ では対角化できない。
3 行目：$\mathbb{F}_3$ では $x^3-1=(x-1)^3$ なので、$1$ の 3 乗根は $1$ だけで、原始 3 乗根はない。$S^3=I$ から $(S-I)^3=S^3-3S^2+3S-I=S^3-I=O$（$3=0$）であり、$S$ の固有値は $1$ だけである。$S$ が対角化できれば $S$ は $I$ と相似、すなわち $S=I$ となるが、$S\ne I$ なので対角化できない。$\mathbb{F}_2$、$n=2$ の同じ現象は 置換行列 の記事の例「反例：標数 2 では置換行列は対角化できないことがある」にある。同じく $K=\mathbb{R}$、$n=3$ でも、$S$ の固有値 $\omega,\omega^2$ が実数でないので $S$ は $\mathbb{R}$ の上では対角化できない（$\mathbb{C}$ の上ではできる）。
補足
thm-circ-algebra の剰余環 $K[x]/(x^n-1)$ は、巡回群 $\mathbb{Z}/n\mathbb{Z}$ の群環 $K[\mathbb{Z}/n\mathbb{Z}]$ と同じものである（$x$ が生成元 $1$ にあたる）。一般の有限アーベル群 $G$ について、平行移動と可換な線形写像 $\mathbb{C}^G\to\mathbb{C}^G$ は $G$ の指標で同時に対角化され（離散Fourier変換 の定理「平行移動と可換な線形写像の対角化」）、巡回行列はその $G=\mathbb{Z}/n\mathbb{Z}$ の場合である。$x^n-1$ を $x^n+1$ に替えると、折り返すときに符号を変える行列（歪巡回行列）が得られ、$\mathbb{C}$ の上では $1$ の原始 $2n$ 乗根の奇数乗を使って同じように対角化される（この記事では証明しない）。また、複素平面上の $n$ 角形の頂点の列に巡回行列を掛ける操作は、多角形を「各頂点の近くの頂点の重みつき平均」で作り直す操作であり、Napoleonの定理 や Petr–Douglas–Neumannの定理 はこの操作の固有ベクトル $v_t$（正 $n$ 角形）による分解として読める。
関連項目
- 前提: 行列式, 固有値, 離散Fourier変換と反転公式
- 比較: 置換行列, 正規行列
- 直後に読む: 離散Fourier変換, 高速Fourier変換
- 発展: 群環, Petr–Douglas–Neumannの定理
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
