巡回群のフーリエ変換 - ryamadaのコンピュータ・数学メモ

昨日まで、延々と正単体・順列、フーリエ変換、複素数などをいじってきた
このくらいあれこれやっておけば、『巡回群のフーリエ変換』を扱った文書を読んでも大丈夫だろう…ということで：
- まずこちらは、時系列２次元画像の補間をするのに巡回群の行列を用いて、複素回転でやってみようという話。具体的な活用場面が想像しやすくなる
- 次にこちらは、その名も有限アーベル群(巡回群はそのひとつ)のフーリエ変換
この「有限アーベル群のフーリエ変換」の方を覗きながら、Rでも書いてみよう
巡回群にn個の元があるとき、単位元1と生成元 $\sigma$ とを使って、n個の元は $\sigma^0=\sigma^n,\sigma^1,\sigma^2,...,\sigma^{n-1}$ と表せる
巡回群では２つの元の積が別の元になるわけだけれど、その関係は積の数を表せばよいので、行列で表すことができる。それを、群行列と言う。巡回群をと書けば、その群行列は。ここで、この行列の「姿がよい」ようにする意味もあって、次のように作ることにする
- 対角成分は $\sigma^{-i} \times \sigma^{i}=\sigma^0$ を対応づけたい。そうすると、行列 $A_{C_n}$ の $(i,j)$ 成分は $\sigma^{-i} \times \sigma^{j}$ にするとよい。ここで $\sigma^i$ は群の元であって、「数」ではないので、 $\sigma^i$ に「数(複素数)」として $X_i$ を対応づければ
- $\begin{pmatrix}X_0 & X_1 & \ldots & X_{n-1}\\ X_{n-1} & X_0 & \ldots & X_{n-2}\\ \vdots & \vdots & \ddots & \vdots \\ X_1 & X_2 & \ldots & X_0 \end{pmatrix}$ というような行列として群行列を定義できる。ただし、この $X$ は何かしらの体(今回は複素数)であって、ある群に対して、この $X$ の集合は"irreducible factorsにしておく、ということができる(Frobenius 1886年)。
この巡回群の群行列をRで作ってみる。二通りの作り方がある。一つは、n個の数を行列の斜めに地道に配置する方法。もう一つは、 $(X_0,X_1,...,X_{n-1})=(0,1,...,0)$ に対応した群行列 $K$ を使って $\sum_{i=0}^{n-1} X_i K^i$ として計算する方法である

n <- 5
make.Acn <- function(Xs){
	n <- length(Xs)
	nv <- 1:n
	ret <- matrix(0,n,n)
	for(i in 1:n){
		ret[i,] <- Xs[nv]
		nv <- c(nv[n],nv[-n])
	}
	ret
}
make.Acn(Xs)
make.K <- function(n){
	Xs <- c(0,1,rep(0,n-2))
	make.Acn(Xs)
}
make.Acn.2 <- function(Xs){
	n <- length(Xs)
	K <- make.K(n)
	E <- diag(rep(1,n))
	ret <- matrix(0,n,n)
	for(i in 1:n){
		ret <- ret + Xs[i] * E
		E <- K %*% E
	}
	ret
}
Xs <- runif(n) + 1i*runif(n)

make.K(n)
make.Acn(Xs)
make.Acn.2(Xs)
make.Acn(Xs) - make.Acn.2(Xs)