순환 행렬

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
3. 성질
4. 특별한 형태의 순환 행렬
- 4.1. 대칭 순환 행렬
- 4.2. 에르미트 순환 행렬
5. 응용
- 5.1. 선형 방정식
- 5.2. 그래프 이론
참조

1. 개요

순환 행렬은 첫 번째 열(또는 행) 벡터로 완전히 정의되는 특수한 형태의 정사각 행렬이다. 순환 행렬은 순환 순열 행렬의 행렬 다항식으로 표현 가능하며, 가환 대수를 형성하고 이산 푸리에 변환(DFT) 행렬과 밀접한 관련이 있다. 순환 행렬은 고유 벡터와 고유값을 가지며, 행렬식, 계수 등의 성질을 갖는다. 대칭 순환 행렬과 에르미트 순환 행렬과 같은 특별한 형태도 존재한다. 순환 행렬은 선형 방정식 풀이, 그래프 이론 등 다양한 분야에 응용된다. 특히, 순환 행렬을 이용한 선형 방정식은 원형 컨볼루션으로 변환하여 효율적으로 해결할 수 있으며, 그래프의 인접 행렬이 순환 행렬인 경우 순환 그래프라고 부른다.

더 읽어볼만한 페이지

수치선형대수학 - 가우스 소거법
가우스 소거법은 연립 일차 방정식의 해를 구하기 위해 행렬을 사다리꼴로 변환하는 알고리즘이며, 기본 행 연산을 통해 전진 소거와 후퇴 대입 단계를 거쳐 해를 계산하고, 행렬식 계산 등 다양한 분야에 응용된다.
수치선형대수학 - LINPACK
LINPACK은 부동소수점 연산 성능을 평가하는 벤치마크 프로그램이자 FORTRAN 라이브러리로, 슈퍼컴퓨터 성능 측정 기준으로 사용되는 HPLinpack 벤치마크의 기반이 되었으며, TOP500 목록에서 고성능 컴퓨터 순위를 결정하는 데 기여한다.
행렬 - 스핀 (물리학)
스핀은 양자역학적 각운동량으로, 양자화된 값을 가지며 자기 쌍극자 모멘트를 유발하여 다양한 분야에 응용되고 스핀트로닉스 기술 발전에 기여하지만, 전자의 스핀 기원은 아직 완전히 밝혀지지 않았다.
행렬 - 파울리 행렬
파울리 행렬은 양자역학에서 스핀을 나타내는 데 사용되는 에르미트 행렬이자 유니타리 행렬로, 행렬식은 -1이고 대각합은 0이며, 리 대수의 생성원이자 파울리 벡터로 정의되어 다양한 물리학 분야에서 활용된다.

순환 행렬
기본 정보
순환 행렬의 예시
유형	정사각 행렬
정의	각 행이 바로 위 행의 원소를 오른쪽으로 한 번 이동시킨 형태를 갖는 행렬
다른 이름	순회 행렬
특징
교환 법칙	두 순환 행렬 A와 B에 대해 AB = BA가 성립한다.
고유 벡터	푸리에 기저
고유값	이산 푸리에 변환으로 계산 가능
관련 개념	테플리츠 행렬
예시
3x3 순환 행렬	C = Â Â Â Â Â Â Â Â Â Â {\begin{bmatrix}c_{0}&c_{1}&c_{2}\\c_{2}&c_{0}&c_{1}\\c_{1}&c_{2}&c_{0}\\\end{bmatrix}}
활용
응용 분야	선형 시불변 시스템 분석 부호 이론 암호학

2. 정의

$n \times n$ '''순환 행렬''' $C$ 는 다음과 같은 형식을 갖는다.

$C = \begin{bmatrix}c_0 & c_{n-1} & \cdots & c_2 & c_1 \\c_1 & c_0 & c_{n-1} & & c_2 \\\vdots & c_1 & c_0 & \ddots & \vdots \\c_{n-2} & & \ddots & \ddots & c_{n-1} \\c_{n-1} & c_{n-2} & \cdots & c_1 & c_0 \\\end{bmatrix}$

순환 행렬은 첫 번째 열(또는 행) 벡터 $c$ 하나로 완전히 결정된다. 나머지 열(또는 행)은 벡터 $c$ 를 순환적으로 이동시켜 얻을 수 있다. $C$ 의 나머지 열(및 행)은 열(또는 행) 인덱스와 동일한 오프셋을 가진 벡터 $c$ 의 각 순환 순열이다(행의 순환 순열은 열의 순환 순열과 동일한 효과를 갖는다). 0에서 $n-1$ 까지 행의 색인을 지정하는 경우, $C$ 의 마지막 행은 역방향으로 한 칸 이동한 벡터 $c$ 이다. 행렬 $C$ 의 "연관 다항식"은 $f(x) = c_0 + c_1 x + \dots + c_{n-1} x^{n-1}$ 로 정의된다.

임의의 행렬 $A$ 는 다음과 같다.

: $A=\begin{pmatrix}a_0 & a_{1} & \dots & a_{n-1} & a_{n} \\a_{n} & a_0 & a_{1} & & a_{n-1} \\\vdots & a_{n}& a_0 & \ddots & \vdots \\a_{2} & & \ddots & \ddots & a_{1} \\a_{1} & a_{2} & \dots & a_{n} & a_0\end{pmatrix}$

행렬 $A$ 가 갖는 주대각선을 기준으로 순환적인 대칭을 보인다면, 다음과 같은 확장된 순환행렬들을 예상할 수 있다.

: $\begin{pmatrix} a_0 & a_1 \\ a_1 & a_0 \end{pmatrix}$

: $\begin{pmatrix} a_0 & a_1 & a_2 \\ a_2 & a_0 & a_1 \\ a_1 & a_2 & a_0 \end{pmatrix}$

: $\begin{pmatrix} a_0 & a_1 & a_2 & a_3 \\ a_3 & a_0 & a_1 & a_2 \\ a_2 & a_3 & a_0 & a_1 \\ a_1 & a_2 & a_3 & a_0 \end{pmatrix}$

: $\begin{pmatrix} a_0 & a_1 & a_2 & a_3 & a_4 \\ a_4 & a_0 & a_1 & a_2 & a_3 \\ a_3 & a_4 & a_0 & a_1 & a_2 \\ a_2 & a_3 & a_4 & a_0 & a_1 \\ a_1 & a_2 & a_3 & a_4 & a_0 \end{pmatrix}$

3. 성질

모든 순환 행렬은 순환 순열 행렬 $P$ 에 대한 행렬 다항식으로 표현 가능하다.^[3] 즉, $C = c_0 I + c_1 P + c_2 P^2 + \dots + c_{n-1} P^{n-1} = f(P)$ 와 같이 나타낼 수 있으며, 여기서 $P$ 는 동반 행렬이다.

$n \times n$ 순환 행렬의 집합은 덧셈 및 스칼라 곱에 대해 $n$ -차원 벡터 공간을 형성한다. 이 공간은 차수 $n$ 인 순환군 $C_n$ 에 대한 함수 공간, 또는 $C_n$ 의 군환으로 해석할 수 있다.

순환 행렬은 가환 대수를 형성하는데, 이는 임의의 두 순환 행렬 $A$ 와 $B$ 에 대해 $A + B$ 와 $AB$ 모두 순환 행렬이며, $AB = BA$ 가 성립하기 때문이다.

비특이 순환 행렬 $A$ 의 역행렬 $A^{-1}$ 도 순환 행렬이다. 특이 순환 행렬의 경우, 그 무어-펜로즈 역행렬 $A^+$ 는 순환 행렬이다.

이산 푸리에 변환(DFT) 행렬은 순환 행렬과 밀접하게 연관되어 있다. 순환 행렬 $C$ 는 DFT 행렬 $F_n$ 을 사용하여 대각화할 수 있다.^[3]

3. 1. 고유 벡터와 고유값

순환 행렬의 정규화된 고유 벡터는 푸리에 모드이며, 다음과 같다.

:

v_j=\frac{1}{\sqrt{n}} \left(1, \omega^j, \omega^{2j}, \ldots, \omega^{(n-1)j}\right)^{T},\quad j = 0, 1, \ldots, n-1,

여기서

\omega=\exp \left(\tfrac{2\pi i}{n}\right)

는 원시

n

차 단위근이고,

i

는 허수 단위이다.

해당 고유값은 다음과 같다.

:

\lambda_j = c_0+c_{1} \omega^j + c_{2} \omega^{2j} + \dots + c_{n-1} \omega^{(n-1)j},\quad j = 0, 1, \dots, n-1.

3. 2. 행렬식

순환 행렬의 행렬식은 고윳값을 이용하여 다음과 같이 계산할 수 있다.^[1]

:

\det C = \prod_{j=0}^{n-1} (c_0 + c_{n-1} \omega^j + c_{n-2} \omega^{2j} + \dots + c_1\omega^{(n-1)j}).

전치를 해도 행렬의 고윳값이 바뀌지 않으므로, 동등한 공식은 다음과 같다.^[1]

:

\det C= \prod_{j=0}^{n-1} (c_0 + c_1 \omega^j + c_2 \omega^{2j} + \dots + c_{n-1}\omega^{(n-1)j})= \prod_{j=0}^{n-1} f(\omega^j).

순환 행렬의 첫 번째 행의 고속 푸리에 변환(FFT)을 수행한 경우, 해당 순환 행렬의 행렬식은 스펙트럼 값의 곱이 된다.^[1]

:

C = W \Lambda W^{-1}

(고유 분해)

:

\det (C) = \det \left( W \Lambda W^{-1} \right)

:

\det (C) = \det \left( W \right) \det \left( \Lambda \right) \det \left( W^{-1} \right)

:

\det (C) = \det \left( \Lambda \right) = \textstyle\prod\limits_{k=1}^n \lambda_k

여기서^[1]

''C''는 ''n''차의 순환 행렬이다.
''W''는 유니터리한 이산 푸리에 변환 행렬이다.
$\Lambda$ 는 고윳값이 $\lambda_k$ 인 대각 행렬이다.

마지막 항

\textstyle\prod\limits_{k=1}^n \lambda_k

는 스펙트럼 값의 곱과 같다.^[1]

3. 3. 계수(Rank)

순환 행렬

C

의 계수는

n - d

와 같으며, 여기서

d

는 다항식

\gcd( f(x), x^n - 1)

의 차수이다.^[2]

3. 4. 기타 성질

모든 순환 행렬은 순환 순열 행렬

P

에 대한 행렬 다항식으로 표현할 수 있다.^[3] 즉, 다음 형태로 나타낼 수 있다.

C = c_0 I + c_1 P + c_2 P^2 + \dots + c_{n-1} P^{n-1} = f(P),

여기서

P

는 다음과 같은 동반 행렬이다.

P = \begin{bmatrix}0&0&\cdots&0&1\\1&0&\cdots&0&0\\0&\ddots&\ddots&\vdots&\vdots\\\vdots&\ddots&\ddots&0&0\\0&\cdots&0&1&0\end{bmatrix}.

n \times n

순환 행렬의 집합은 덧셈 및 스칼라 곱에 대해

n

-차원 벡터 공간을 형성한다. 이 공간은 차수

n

인 순환군

C_n

에 대한 함수 공간, 또는

C_n

의 군환으로 해석할 수 있다.

순환 행렬은 가환 대수를 형성한다. 임의의 두 순환 행렬

A

와

B

에 대해 합

A + B

와 곱

AB

는 모두 순환 행렬이며,

AB = BA

가 성립하기 때문이다.

비특이 순환 행렬

A

의 역행렬

A^{-1}

도 순환 행렬이다. 특이 순환 행렬의 경우, 무어-펜로즈 역행렬

A^+

는 순환 행렬이다.

이산 푸리에 변환(DFT) 행렬은 순환 행렬과 밀접한 관련이 있다. 순환 행렬

C

는 다음과 같이 DFT 행렬

F_n

을 통해 대각화할 수 있다.^[3]

C = F_n^{-1}\operatorname{diag}(F_n c) F_n ,

여기서

c

는

C

의 첫 번째 열이다.

C

의 고유값은

F_n c

로 주어지며, 이는 고속 푸리에 변환(FFT)을 통해 빠르게 계산할 수 있다.

순환 행렬의 행렬식은 스펙트럼 값의 곱으로 계산 가능하다.

:

C = W \Lambda W^{-1}

(고유 분해)

:

\det (C) = \det \left( W \Lambda W^{-1} \right)

:

\det (C) = \det \left( W \right) \det \left( \Lambda \right) \det \left( W^{-1} \right)

:

\det (C) = \det \left( \Lambda \right) = \textstyle\prod\limits_{k=1}^n \lambda_k

여기서

$C$ 는 $n$ 차 순환 행렬이다.
$W$ 는 유니터리한 이산 푸리에 변환 행렬이다.
$\Lambda$ 는 고유값이 $\lambda_k$ 인 대각 행렬이다.

4. 특별한 형태의 순환 행렬

순환 행렬에는 다음과 같은 특별한 형태가 있다.

'''대칭 순환 행렬''': 대칭 순환 행렬은 $c_{n-i}=c_i$ 라는 추가 조건이 있으며, $\lfloor n/2\rfloor + 1$ 개의 요소로 결정된다. 대칭 순환 행렬은 양대칭 행렬에 속한다.

'''에르미트 순환 행렬''': 에르미트 순환 행렬은 $c_{n-i} = c_i^*$ 조건을 만족하며, 행렬식과 모든 고윳값은 실수이다.^[5]

4. 1. 대칭 순환 행렬

대칭 순환 행렬

C

는

c_{n-i}=c_i

라는 추가 조건이 있으며,

\lfloor n/2\rfloor + 1

개의 요소로 결정된다.

:

C = \begin{bmatrix}c_0     & c_1 & \cdots & c_2    & c_1    \\c_1     & c_0 & c_1    &        & c_2    \\\vdots  & c_1 & c_0    & \ddots & \vdots \\c_2     &     & \ddots & \ddots & c_1    \\c_1     & c_2 & \cdots & c_1    & c_0    \\\end{bmatrix}.

모든 실수 대칭 행렬의 고유값은 실수이다. 해당하는 고유값

\vec{\lambda}= \sqrt n \cdot F_n^{\dagger} c

는 다음과 같다.

:

\begin{array}{lcl} \lambda_k & = & c_0 + c_{n/2} e^{-\pi i \cdot k} + 2\sum_{j=1}^{\frac{n}{2}-1} c_j \cos{(-\frac{2\pi}{n}\cdot k j )} \\& = & c_0+ c_{n/2} \omega_k^{n/2} + 2 c_1 \Re \omega_k + 2 c_2 \Re \omega_k^2 + \dots + 2c_{n/2-1} \Re \omega_k^{n/2-1} \end{array}

(

n

이 짝수인 경우)

:

\begin{array}{lcl} \lambda_k & = & c_0 + 2\sum_{j=1}^{\frac{n-1}{2}} c_j \cos{(-\frac{2\pi}{n}\cdot k j )}  \\& = & c_0 + 2 c_1 \Re \omega_k + 2 c_2 \Re \omega_k^2 + \dots + 2c_{(n-1)/2} \Re \omega_k^{(n-1)/2} \end{array}

(

n

이 홀수인 경우)

여기서

\Re z

는

z

의 실수 부분을 나타낸다. 이는

\Re \omega_k^j = \Re e^{-\frac{2\pi i}{n} \cdot kj} = \cos(-\frac{2\pi}{n} \cdot kj)

이고

\omega_k^{n/2}=e^{-\frac{2\pi i}{n} \cdot k \frac{n}{2}} =e^{-\pi i \cdot k}

라는 사실을 사용하여

k

가 짝수 또는 홀수에 따라 더 단순화할 수 있다.

대칭 순환 행렬은 양대칭 행렬에 속한다.

4. 2. 에르미트 순환 행렬

에르미트 순환 행렬은

c_{n-i} = c_i^*

조건을 만족하며, 행렬식과 모든 고윳값은 실수이다.^[5]

만약 ''n''이 짝수라면 처음 두 행은 다음 형식을 가진다.

\begin{bmatrix}r_0     & z_1 & z_2 & r_3 & z_2^* & z_1^* \\z_1^* & r_0     & z_1 & z_2 & r_3 & z_2^*  \\\dots \\\end{bmatrix}.

여기서 상위 절반 행의 첫 번째 원소

r_3

는 실수이다.

만약 ''n''이 홀수라면, 다음과 같다.

\begin{bmatrix}r_0     & z_1 & z_2 & z_2^* & z_1^* \\z_1^*  & r_0   & z_1 & z_2 & z_2^* \\\dots\\\end{bmatrix}.

5. 응용

순환 행렬은 선형 방정식과 그래프 이론에서 응용된다.

5. 1. 선형 방정식

주어진 행렬 방정식

C \mathbf{x} = \mathbf{b}

에서

C

가 크기

n

인 순환 행렬일 때, 이 방정식을 원형 컨벌루션으로 다음과 같이 나타낼 수 있다.

:

\mathbf{c} \star \mathbf{x} = \mathbf{b}

여기서

\mathbf c

는

C

의 첫 번째 열이고, 벡터

\mathbf c

,

\mathbf x

,

\mathbf b

는 양방향으로 순환적으로 확장된다. 원형 컨벌루션 정리를 사용하면, 이산 푸리에 변환을 사용하여 원형 컨벌루션을 성분별 곱셈으로 변환할 수 있다.

:

\mathcal{F}_{n}(\mathbf{c} \star \mathbf{x}) = \mathcal{F}_{n}(\mathbf{c}) \mathcal{F}_{n}(\mathbf{x}) = \mathcal{F}_{n}(\mathbf{b})

따라서

:

\mathbf{x} = \mathcal{F}_n^{-1} \left[ \left(\frac{(\mathcal{F}_n(\mathbf{b}))_{\nu}}{(\mathcal{F}_n(\mathbf{c}))_{\nu}}\right)_{\!\nu\in\Z}\, \right]^{\rm T}

이 알고리즘은 표준 가우스 소거법보다 훨씬 빠르며, 특히 고속 푸리에 변환을 사용하는 경우 더욱 그렇다.

5. 2. 그래프 이론

그래프 이론에서, 그래프 또는 유향 그래프의 인접 행렬이 순환 행렬이면 순환 그래프/유향 그래프라고 부른다. 그래프의 자기 동형 사상군에 전체 길이의 사이클이 포함되어 있으면 순환 그래프가 된다. 뫼비우스 사다리는 순환 그래프의 예시이며, 소수 차수의 체에 대한 페일리 그래프 역시 순환 그래프이다.

참조

_[1] 서적 Circulant Matrices Wiley 1970
_[2] 논문 The Rank of Circulant Matrices
_[3] 간행물 Matrix Computations Johns Hopkins
_[4] 논문 Circulants and critical points of polynomials 2016-07-15
_[5] 논문 Eigenvectors of Block Circulant and Alternating Circulant Matrices https://core.ac.uk/d[...] 2007
_[6] 서적 Circulant Matrices Wiley 1970

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com