모든 행이 동일한 요소로 구성되고 각 행이 이전 행에서 오른쪽으로 한 위치씩 회전하는 행렬
선형대수학 에서 순환행렬 은 모든 행 벡터 가 동일한 원소로 구성되고 각 행 벡터가 앞의 행 벡터에 대해 오른쪽으로 한 원소를 회전하는 정사각형 행렬 이다. 이것은 특정한 종류의 토플리츠 매트릭스 다.
수치해석 에서는 순환 행렬이 이산 푸리에 변환 에 의해 대각화 되므로 이를 포함 하는 선형 방정식이 빠른 푸리에 변환을 사용 하여 빠르게 해결될 수 있기 때문에 중요하다.[1] 그것들은 분석적 으로 주기 그룹 C n {\ displaystyle C_{n} 에 있는 콘볼루션 연산자 의 일체형 커널 로 해석 될 수 있으므로 공간 불변 선형 연산에 대한 공식 설명에 자주 나타난다. 이 특성은 직교 주파수 분할 다중화 를 활용하여 주기적 접두사 를 사용하여 기호 (비트)를 확산하는 현대 소프트웨어 정의 라디오에서도 중요하다. 이것은 채널을 순환 매트릭스로 나타낼 수 있게 하여 주파수 영역 의 채널 균등화를 단순화한다.
암호학 에서는 고급 암호화 표준 의 MixColumns 단계에서 순환 매트릭스를 사용한다.
정의 n × n {\displaystyle n\times n} 순환 행렬 C {\displaystyle C} 이(가) 형태를 취함
C = [ c 0 c n − 1 ⋯ c 2 c 1 c 1 c 0 c n − 1 c 2 ⋮ c 1 c 0 ⋱ ⋮ c n − 2 ⋱ ⋱ c n − 1 c n − 1 c n − 2 ⋯ c 1 c 0 ] {\displaystyle 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 i {\ displaystyle c_{i} 라는 용어가 p × p {\displaystyle p\times p} 제곱 행렬인 경우, n p × n p {\displaystyle np\times np} 행렬 C {\displaystystyculant 행렬 이라고 한다.
순환 행렬은 C {\displaystyle C} 의 첫 번째 열(또는 행)으로 나타나는 하나의 벡터, c {\displaystyle c} 에 의해 완전히 지정된다. C {\displaystyle C} 의 나머지 열(및 행, resp.)은 컬럼(또는 행, resp.) 색인 과 동일한 오프셋 을 가진 벡터 c {\displaystyle c} 의 각 순환 순열 이며 , 라인이 0 에서 n - 1 까지 색인된 경우( 행 의 순환 순열은 컬럼의 순환 순열과 동일한 효과를 나타냄)이다. C {\displaystyle C} 의 마지막 행은 벡터 c {\displaystyle c} 이(가) 역방향으로 하나씩 이동된 것이다 .
다른 출처는 다른 방식으로 순환 행렬을 정의하는데, 예를 들어 위와 같다거나, 행렬의 첫 번째 열이 아닌 첫 번째 행에 해당하는 벡터 c {\displaystyle c} 을(가끔은 반순환 행렬이라고 한다 )로 정의한다.
다항식 f( x ) = c 0 + c 1 x + ⋯ + c n - 1 x n - 1 {\ displaystyle f(x)=c_{0}+c_{1 }}x+\dots +c_{n-1}x^{n-1}} 행렬 C {\displaystyle C} 의 연관된 다항식 이라고 한다.
특성. 고유 벡터 및 고유값 순환 행렬의 정규화된 고유 벡터는 푸리에 모드, 즉,
v j = 1 n ( 1 , ω j , ω 2 j , … , ω ( n − 1 ) j ) , j = 0 , 1 , … , n − 1 , {\displaystyle v_{j}={\frac {1}{\sqrt{n}}}왼쪽(1,\omega ^{j},\omega ^{2j},\ldots,\omega ^{n-1)\right),\display j=0,1,\ldots,n-1,} 여기서 Ω = exp (2 π i n ){\ displaystyle \omega =\exp \left({\tfrac {2\pi i}{n}\오른쪽 )은 원시 n {\displaystyle n} -throot of unity 이고 i {\\displaystysty i} 은 가상 단위 다.
(이것은 순환 행렬을 가진 곱셈이 경련을 구현한다는 것을 깨달음으로써 이해할 수 있다. 푸리에 공간에서는 경련이 곱절이 된다. 따라서 푸리에 모드를 가진 순환기 행렬의 산물은 푸리에 모드의 배수를 산출한다. 즉, 고유 벡터).
해당하는 고유값 은 다음과 같다.
λ j = c 0 + c n − 1 ω j + c n − 2 ω 2 j + ⋯ + c 1 ω ( n − 1 ) j , j = 0 , 1 , … , n − 1. {\displaystyle \c_{j}=c_{0}+c_{n-1}\오메가 ^{j}+c_{n-2}\오메가 ^{2j}+\c_{1} }}\omega ^{(n-1)j},\cHB j=0,1,\cHB,n-1. }
결정인자 위의 고유값에 대한 명시적 공식의 결과로서, 순환 행렬의 결정 인자는 다음과 같이 계산할 수 있다.
퇴장시키다 ( C ) = ∏ j = 0 n − 1 ( c 0 + c n − 1 ω j + c n − 2 ω 2 j + ⋯ + c 1 ω ( n − 1 ) j ) . {\displaystyle \det(C)=\prod _{j=0}^{n-1}(c_{0}+c_{n-1}\omega^{j}+c_{n-2}\omega^{2j}+}+\c_{1} }}\omega ^{(n-1)j}). } 전치제를 복용해도 행렬의 고유값은 변하지 않으므로 등가 제형은 다음과 같다. 퇴장시키다 ( C ) = ∏ j = 0 n − 1 ( c 0 + c 1 ω j + c 2 ω 2 j + ⋯ + c n − 1 ω ( n − 1 ) j ) = ∏ j = 0 n − 1 f ( ω j ) . {\displaystyle \det(C)=\prod _{j=0}^{n-1}(c_{0}+c_{1) }}\omega ^{j}+c_{2 }\omega ^{2j}+\c_{n-1}\c_{n-1}\omega ^{(n-1)j}=\prod _{j=0}^{n-1}f(\omega ^{j}). }
순위 순환 행렬 C {\ dapplaystyle C} 의 순위 는 n - d {\d} 과 같으며 , 여기서 d {\dapplaystyle d } 은 (는) 다항식 gcd( f ( x), x n - 1 ) {\dapplaystyle \gcd(x), x ^{n}-1 )의 정도 입니다. [2]
기타 속성 모든 순환제는 순환 순열 매트릭스 P {\displaystyle P} 에 있는 행렬 다항식(이름, 관련 다항식)이다. C = c 0 I + c 1 P + c 2 P 2 + ⋯ + c n − 1 P n − 1 = f ( P ) , {\displaystyle C=c_{0} I+c_{1}P+c_{2} P^{2}+\dots +c_{n-1}P^{n-1}=f(P),} 여기 서 P {\displaystyle P} 은(는) P = [ 0 0 ⋯ 0 1 1 0 ⋯ 0 0 0 ⋱ ⋱ ⋮ ⋮ ⋮ ⋱ ⋱ 0 0 0 ⋯ 0 1 0 ] . {\displaystyle P={\begin{bmatrix}0�&\cdots &0&1\\1���&#{bmatrix}\cdots &0>\ddodots ��&#cdots. } n × n {\displaystyle n\times n} 순환 행렬 집합 은 덧셈 및 스칼라 곱셈과 관련하여 n {\displaystyle n} 차원 벡터 공간 을 형성한다. 이 공간은 순서 n {\displaystyle n }, C n {\ displaystyle C_{n }, 또는 C n {\ displaystyle C_{n} 의 그룹 링 과 동일하게 해석할 수 있다. Circulant matrices form a commutative algebra , since for any two given circulant matrices A {\displaystyle A} and B {\displaystyle B} , the sum A + B {\displaystyle A+B} is circulant, the product A B {\displaystyle AB} is circulant, and A B = B A {\displaystyle AB=BA} . 순환 행렬의 고유 벡터 로 구성된 행렬 U {\displaystyle U} 은 이산 푸리에 변환 및 역변환과 관련이 있다. U n ∗ = 1 n F n , 그리고 U n = 1 n F n − 1 , 어디에 F n = ( f j k ) 와 함께 f j k = e − 2 j k π i / n , 을 위해 0 ≤ j , k < n . {\displaystyle U_{n}^{*}={\frac {1}{\sqrt {n}}}F_{n},\quad {\text{and}}\quad U_{n}={\frac {1}{\sqrt {n}}}F_{n}^{-1},{\text{ where }}F_{n}=(f_{jk}){\text{ with }}f_{jk}=e^{-2jk\pi i/n},\,{\text{for }}0\leq j,k<n. } 따라서 매트릭스 Un {\ displaystyle U_{n} 은(는) C {\displaystyle C} 을(를) 대각선화 한다. 실제로, C = U n 검열하다 ( F n c ) U n ∗ = 1 n F n − 1 검열하다 ( F n c ) F n , {\displaystyle C=U_{n}\operatorname {diag}(F_{n}c) U_{n}^{*}={\frac {1}{n1}{n}^{-1}\operatorname {diag}(F_{n}c) F_{n}} 여기서 c {\displaystyle c} 은 (는) C {\displaystyle C} 의 첫 번째 열이다. C {\displaystyle C} 의 고유값은 제품 Fn c {\displaystyle F_{n}c} 에 의해 제공된다. 이 제품은 빠른 푸리에 변환 으로 쉽게 계산할 수 있다.[3] Let p ( x ) {\displaystyle p(x)} be the (monic ) characteristic polynomial of an n × n {\displaystyle n\times n} circulant matrix C {\displaystyle C} , and let p ′ ( x ) {\displaystyle p'(x)} be the derivative of p ( x ) {\displaystyle p(x)} . Then the polynomial 1 n p ′ ( x ) {\textstyle {\frac {1 }{n}p'(x)} 은 (는) C {\displaystyle C} 의 다음(n - 1 ) × (n - 1 ) {\displaystyle (n-1) 서브트리렉스의 특성 다항식이다. C n − 1 = [ c 0 c n − 1 ⋯ c 3 c 2 c 1 c 0 c n − 1 c 3 ⋮ c 1 c 0 ⋱ ⋮ c n − 3 ⋱ ⋱ c n − 1 c n − 2 c n − 3 ⋯ c 1 c 0 ] {\displaystyle C_{n-1}={\begin{bmatrix}c_{0}&c_{n-1}&\cdots &c_{3}&c_{2}\\c_{1}&c_{0}&c_{n-1}&&c_{3}\\\vdots &c_{1}&c_{0}&\ddots &\vdots \\c_{n-3}&&\ddots &\ddots &c_{n-1}\\c_{n-2}&c_{n-3}&\cdots &c_{1}&c_{0}\\\end{bmatrix}}} (증거에 대해서는 참조).
분석적 해석 순환 행렬은 기하학적으로 해석될 수 있는데, 이것은 이산 푸리에 변환과의 연관성을 설명한다.
Consider vectors in R n {\displaystyle \mathbb {R} ^{n}} as functions on the integers with period n {\displaystyle n} , (i.e., as periodic bi-infinite sequences: … , a 0 , a 1 , … , a n − 1 , a 0 , a 1 , … {\displaystyle \dots ,a_{0},a_{1},\dots ,a_{n-1},a_{0},a_{1},\dots } ) or equivalently, as funct n {\displaystyle n}( Cn {\ displaystyle C_{n} 또는 Z /n Z {\displaystyle \mathb {Z}}}) 의 주기적 그룹에 있는 이온: 기하학적으로 정규 n {\displaysty n} -gon : 실제 선이 나 원의 (정점)과 이산 유사하다.
그렇다면, 연산자 이론의 관점에서, 순환 행렬은 이산 적분 변환 의 커널, 즉 기능에 대한 콘볼루션 연산자 (c 0, c 1, … , c n - 1 ) {\displaystyle (c_{0},c_{1},\dots ,c_{n-1 }; 이것은 이산 원형 콘볼루션 이다. 함수(b i ) := ( c i ) ∗ ( i ) {\displaystyle (b_{i}): =(c_{i})*(a_{i}) 은 (는)
b k = ∑ i = 0 n − 1 a i c k − i {\displaystyle b_{k}=\sum _{i=0}^{n-1a_{i}c_{k-i}}}} (시퀀스가 주기적이라는 것을 나타냄) 이것은 (c i ) {\displaystyle (a_{i}) 의 순환 행렬에 의한 벡터 (i ) {\ displaystyle (a_{i}) 의 산물이다.
그런 다음 이산 푸리에 변환은 매트릭스 설정에서 대각선에 해당하는 경련을 곱셈으로 변환한다.
복합 항목이 있는 모든 순환 행렬의 C ∗{\ displaystyle C^{*}} -algebra는 그룹 C ∗ {\displaystyle C ^{*}} Z 의 Algebra와 이형성 이 있다.
대칭 순환 행렬 대칭 순환기 행렬 C {\displaystyle C} 의 경우 c - n = c i {\displaystyle c_{n-i}=c_{i}} 라는 추가 조건이 있다. 따라서 ⌊ n / 2 ⌋ + 1 {\displaystyle \lfloor n/2\rfloor +1} 요소 에 의해 결정된다.
C = [ c 0 c 1 ⋯ c 2 c 1 c 1 c 0 c 1 c 2 ⋮ c 1 c 0 ⋱ ⋮ c 2 ⋱ ⋱ c 1 c 1 c 2 ⋯ c 1 c 0 ] . {\displaystyle 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}}. }
실제 대칭 행렬의 고유값은 실제 값이다. 해당하는 고유값은 다음과 같다.
λ j = c 0 + 2 c 1 ℜ ω j + 2 c 2 ℜ ω j 2 + ⋯ + 2 c n / 2 − 1 ℜ ω j n / 2 − 1 + c n / 2 ω j n / 2 {\displaystyle \lambda _{j}=c_{0}+2c_{1}\Re \omega _{j}+2c_{2}\Re \omega _{j}^{2}+\dots +2c_{n/2-1}\Re \omega _{j}^{n/2-1}+c_{n/2}\omega _{j}^{n/2}} 단조 로움 (n {\displaystylen}), λ j = c 0 + 2 c 1 ℜ ω j + 2 c 2 ℜ ω j 2 + ⋯ + 2 c ( n − 1 ) / 2 ℜ ω j ( n − 1 ) / 2 {\displaystyle \lambda _{j}=c_{0}+2c_{1}\re \omega _{j}+2c_{2}\re \omega _{j}^{j}^{n-1)/2}}: for n {\displaystyle n} odd , where ℜ z {\displaystyle \Re z} denotes the real part of z {\displaystyle z} . This can be further simplified by using the fact that ℜ ω j k = cos ( 2 π j k / n ) {\displaystyle \Re \omega _{j}^{k}=\cos(2\pi jk/n)} .
대칭 순환 행렬은 이대칭 행렬 의 등급에 속한다.
은둔자 순환 행렬 통신 이론에서 어디서나 볼 수 있는 순환 매트릭스의 복잡한 버전은 대개 에르미트어다 . 이 경우 c - i = c i ∗ , i ≤ n / 2 {\displaystyle c_{n-i}=c_{i}^{ i}^},\;i\leq n/2} 및 그 결정요인과 모든 고유값이 실제 값이다.
n 이 처음 두 행이라도 같을 경우 반드시 형식을 취한다.
[ r 0 z 1 z 2 r 3 z 2 ∗ z 1 ∗ z 1 ∗ r 0 z 1 z 2 r 3 z 2 ∗ … ] . {\displaystyle {\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 {\ displaystyle r_{3} 가 실제인 경우.
n 이 이상하면 우리는 얻는다.
[ r 0 z 1 z 2 z 2 ∗ z 1 ∗ z 1 ∗ r 0 z 1 z 2 z 2 ∗ … ] . {\displaystyle {\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] 은둔자 조건의 고유값 제약에 대해 논의해왔다.
적용들 선형 방정식 주어진 행렬 방정식
C x = b , {\displaystyle C\mathbf {x} =\mathbf {b},} 여기서 C {\ displaystyle C } 은 (는) 크기가 n 인 순환 정사각형 행렬이며, 우리는 방정식을 원형 경련 으로 쓸 수 있다. c ⋆ x = b , {\displaystyle \mathbf {c} \star \mathbf {x} =\mathbf {b},} 여기서 c {\displaystyle \mathbf {c } 는 C {\displaystyle \mathbf {c} 의 첫 번째 열이며, 벡터 c {\ displaystyle \mathbf {x} 및 b {\ displaysty \mathbf {b}} 은 각 방향으로 주기적으로 확장된다 . 원형 콘볼루션 정리 를 이용하여 이산 푸리에 변환 을 이용하여 순환 콘볼루션을 성분별 곱셈으로 변환할 수 있다. F n ( c ⋆ x ) = F n ( c ) F n ( x ) = F n ( b ) {\displaystyle {\mathbf{F}_{n}(\mathbf {x}) \star \mathbf {f}{n}(\mathbf {c} )={\mathcal {F}{n}={\mathbf}}}}}}}}}. 하도록 x = F n − 1 [ ( ( F n ( b ) ) ν ( F n ( c ) ) ν ) ν ∈ Z ] T . {\displaystyle \mathbf {x} ={\mathcal {F}}_{n}^{-1}\left[\left({\frac {({\mathcal {F}}_{n}(\mathbf {b} ))_{\nu }}{({\mathcal {F}}_{n}(\mathbf {c} ))_{\nu }}}\right)_{\! \nu \in \mathb {Z} }\right]^{\rm {T}. }
이 알고리즘은 특히 빠른 푸리에 변환 을 사용하는 경우 표준 가우스 제거 보다 훨씬 빠르다.
그래프 이론에서 그래프 이론 에서 인접 행렬 이 순환인 그래프 또는 디그그래프 를 순환 그래프 (또는 디그그래프)라고 한다. 마찬가지로, 그래프는 자동형 그룹 이 전체 길이 주기를 포함하는 경우 순환한다. 뫼비우스 사다리 는 원시 질서 의 분야 에 대한 Paley 그래프 와 마찬가지로 순환 그래프의 예다.
참조 ^ Davis, Philip J, Circulant Matrice, Wiley, 1970년, 뉴욕 주(州), ISBN 0471057711 ^ A. W. Ingleton (1956). "The Rank of Circulant Matrices". J. London Math. Soc . s1-31 (4): 445–460. doi :10.1112/jlms/s1-31.4.445 . ^ Golub, Gene H. ; Van Loan, Charles F. (1996), "§4.7.7 Circulant Systems", Matrix Computations (3rd ed.), Johns Hopkins, ISBN 978-0-8018-5414-9 ^ Kushel, Olga; Tyaglov, Mikhail (July 15, 2016), "Circulants and critical points of polynomials", Journal of Mathematical Analysis and Applications , 439 (2): 634–650, arXiv :1512.07983 , doi :10.1016/j.jmaa.2016.03.005 , ISSN 0022-247X ^ Tee, G J (2007). "Eigenvectors of Block Circulant and Alternating Circulant Matrices". New Zealand Journal of Mathematics . 36 : 195–211. 외부 링크