순환행렬과 DFT: 속성과 계산

# 서큘런트 행렬: 고유값, DFT, 대수 구조

서큘런트 행렬은 정사각 행렬로, 첫 번째 행 다음의 각 행이 이전 행의 오른쪽 순환 이동입니다. 차수 n에 대해 서큘런트 C(a₀,…,aₙ₋₁)는 다음과 같습니다:

C(a_0,\ldots,a_{n-1})=\begin{pmatrix} a_0 & a_1 & a_2 & \ldots & a_{n-2} & a_{n-1} \\  a_{n-1} & a_0 & a_1 & \ldots & a_{n-3} & a_{n-2} \\ a_{n-2} & a_{n-1} & a_0 & \ldots & a_{n-4} & a_{n-3} \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ a_2 & a_3 & a_4 & \ldots & a_0 & a_1 \\ a_1 & a_2 & a_3 & \ldots & a_{n-1} & a_0 \end{pmatrix}

모든 계산은 ℂ 위에서 수행됩니다. 주요 표기: χ_A(t) — 특성 다항식, μ_A(t) — 최소 다항식, Sp(A) — 스펙트럼, A* = \overline{A}^⊤ — 에름미트 수반.

차수 4의 순환 치환 행렬 M을 고려해 보세요:

M=\begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{pmatrix}

그의 거듭제곱: M², M³, M⁴ = I. 최소 다항식 μ_M(t) = t⁴ - 1, {I, M, M², M³}이 선형 독립이기 때문입니다. 스펙트럼 Sp(M) = {±1, ±i}.

모든 서큘런트는 M의 다항식입니다: C(a,b,c,d) = f(M), 여기서 f(t) = a + bt + ct² + dt³.

대수적 성질과 대각화

서큘런트는 M_n(ℂ)의 가환 부분대수입니다:

• 서큘런트의 곱은 서큘런트: f(M)g(M) = h(M), h(t) = f(t)g(t).
• 스펙트럼: Sp(C) = {f(λ) | λ ∈ Sp(M)}.
• 행렬식: det C(a,b,c,d) = (a+b+c+d)(a-b+c-d)(a+bi-c-di)(a-bi-c+di).
• 모든 서큘런트는 공통 기저에서 대각화 가능; 서큘런트 대수는 ℂ⁴와 동형입니다.

M의 고유벡터는 λ ∈ Sp(M)에 대해 다음을 만족합니다:

\begin{pmatrix} p\\q\\r\\s \end{pmatrix} \overset{M}{\longmapsto} \begin{pmatrix} q\\r\\s\\p \end{pmatrix}=\lambda\begin{pmatrix} p\\q\\r\\s \end{pmatrix}

λ=1: p=q=r=s. λ=i: q=ip, r=iq=-p, s=ir=-ip.

M은 유니터리(M* = M⁻¹)이므로 직교정규 기저에서 대각화됩니다. 정규화된 행렬 U (1/2 F, F는 DFT 행렬)는 다음과 줍니다:

U^{-1}MU = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & i & 0 & 0 \\ 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & -i \end{pmatrix}, \quad U=\dfrac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1 \\  1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i\end{pmatrix}

이산 푸리에 변환과의 연관성

행렬 F는 서큘런트의 첫 번째 행 (a,b,c,d)를 고유값 벡터로 변환합니다:

F\begin{pmatrix} a \\ b\\c\\d\end{pmatrix}=\begin{pmatrix} a+b+c+d\\a+bi-c-di\\a-b+c-d\\a-bi-c+di\end{pmatrix}

차수 n으로 일반화: Sp(M) = {1, ω, …, ω^{n-1}}, ω = e^{2πi/n}. DFT F는 다항식 f(t) = Σ a_k t^k에 대해 f(ω^k)를 계산합니다.

FFT는 복잡도를 O(n²)에서 O(n log n)으로 줄입니다. n=4에 대해:

• E₀ = a+c, E₁ = a-c, O₀ = b+d, O₁ = b-d.
• f(1) = E₀ + O₀, f(i) = E₁ + iO₁, f(-1) = E₀ - O₀, f(-i) = E₁ - iO₁.

FFT 응용:

• 서큘런트-벡터 곱: F⁻¹(FA · FB).
• 서큘런트-서큘런트 곱: 결과의 첫 행은 F⁻¹(FA · FB)^⊤.

유니터리 DFT 행렬 U = F/√n은 단위 원 위에 스펙트럼을 가집니다. U²는 반사 행렬로 고유값 {1 (⌈(n+1)/2⌉ 번), -1 (⌊(n-1)/2⌋ 번)}.

가우스 합과 U의 스펙트럼

U의 대각합은 이차 가우스 합을 포함합니다:

tr U = (1 + ω + ω⁴ + … + ω^{(n-1)²}) / √n.

가우스 공식:

| n mod 4 | tr U |

|---------|------|

| 0 | 1+i |

| 1 | 1 |

| 2 | 0 |

| 3 | i |

U의 스펙트럼은 tr U를 통해 1, -1, i, -i의 중복도로 결정됩니다.

핵심 요약:

• 서큘런트는 치환 행렬 M의 다항식으로, DFT 기저에서 대각화됩니다.
• 서큘런트 대수는 ℂ[t]/(tⁿ-1)와 동형이므로 가환입니다.
• DFT는 서큘런트 스펙트럼을 효율적으로 계산; FFT가 연산을 가속화합니다.
• 유니터리 DFT 행렬 U의 스펙트럼은 가우스 합과 연결됩니다.
• 응용: 고속 컨볼루션, tⁿ-1 모듈로 다항식 곱셈.

— Editorial Team