순환 행렬

Circulant matrix

선형대수학에서 순환행렬은 모든 행 벡터가 동일한 원소로 구성되고 각 행 벡터가 앞의 행 벡터에 대해 오른쪽으로 한 원소를 회전하는 정사각형 행렬이다. 이것은 특정한 종류의 토플리츠 매트릭스다.

수치해석에서는 순환 행렬이 이산 푸리에 변환에 의해 대각화되므로 이를 포함하는 선형 방정식이 빠른 푸리에 변환을 사용하여 빠르게 해결될 수 있기 때문에 중요하다.[1] 그것들은 분석적으로 주기 그룹 에 있는 콘볼루션 연산자일체형 커널해석될 수 있으므로 공간 불변 선형 연산에 대한 공식 설명에 자주 나타난다. 이 특성은 직교 주파수 분할 다중화를 활용하여 주기적 접두사를 사용하여 기호(비트)를 확산하는 현대 소프트웨어 정의 라디오에서도 중요하다. 이것은 채널을 순환 매트릭스로 나타낼 수 있게 하여 주파수 영역의 채널 균등화를 단순화한다.

암호학에서는 고급 암호화 표준MixColumns 단계에서 순환 매트릭스를 사용한다.

정의

순환 행렬 이(가) 형태를 취함

또는 이 형식의 전치(표기법 선택) 라는 용어가 제곱 행렬인 경우, × p C 행렬이라고 한다

순환 행렬은 의 첫 번째 열(또는 행)으로 나타나는 하나의 벡터, 에 의해 완전히 지정된다 의 나머지 열(및 행, resp.)은 컬럼(또는 행, resp.) 과 동일한 벡터 c {\ c의 각 순환 순열이며, 라인이 에서 n- 까지 색인된 경우의 순환 순열은 컬럼의 순환 순열과 동일한 효과를 나타냄)이다. 의 마지막 행은 벡터 이(가) 역방향으로 하나씩 이동된 것이다.

다른 출처는 다른 방식으로 순환 행렬을 정의하는데, 예를 들어 위와 같다거나, 행렬의 첫 번째 열이 아닌 첫 번째 행에 해당하는 c c을(가끔은 반순환 행렬이라고 한다)로 정의한다.

다항식 )= + c ++ c - n- } 행렬 연관된 다항식이라고 한다

특성.

고유 벡터 및 고유값

순환 행렬의 정규화된 고유 벡터는 푸리에 모드, 즉,

여기서 = ( i )은 원시n n} of unity이고 i 가상 단위다.

(이것은 순환 행렬을 가진 곱셈이 경련을 구현한다는 것을 깨달음으로써 이해할 수 있다. 푸리에 공간에서는 경련이 곱절이 된다. 따라서 푸리에 모드를 가진 순환기 행렬의 산물은 푸리에 모드의 배수를 산출한다. 즉, 고유 벡터).

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

결정인자

위의 고유값에 대한 명시적 공식의 결과로서, 순환 행렬의 결정 인자는 다음과 같이 계산할 수 있다.

전치제를 복용해도 행렬의 고유값은 변하지 않으므로 등가 제형은 다음과 같다.

순위

순환 행렬 순위는 n- 과 같으며, 여기서 d (는) gcdx x - 1 ) ^{)의 정도 입니다[2]

기타 속성

  • 모든 순환제는 순환 순열 매트릭스 P에 있는 행렬 다항식(이름, 관련 다항식)이다
    P 은(는)
  • n 순환 행렬 집합은 덧셈 및 스칼라 곱셈과 관련하여 차원 벡터 공간을 형성한다. 이 공간은 순서 또는 C 그룹 링과 동일하게 해석할 수 있다
  • Circulant matrices form a commutative algebra, since for any two given circulant matrices and , the sum is circulant, the product is circulant, and .
  • 순환 행렬의 고유 벡터로 구성된 행렬 이산 푸리에 변환 및 역변환과 관련이 있다.
    따라서 매트릭스 은(는 C {\ C을(를) 대각선화한다 실제로,
    여기서 (는) 의 첫 번째 열이다 의 고유값은 제품 c 에 의해 제공된다 이 제품은 빠른 푸리에 변환으로 쉽게 계산할 수 있다.[3]
  • Let be the (monic) characteristic polynomial of an circulant matrix , and let be the derivative of . Then the polynomial (는) 의 다음- 1) (- 1){\서브트리렉스의 특성 다항식이다
    (증거에 대해서는 참조).

분석적 해석

순환 행렬은 기하학적으로 해석될 수 있는데, 이것은 이산 푸리에 변환과의 연관성을 설명한다.

Consider vectors in as functions on the integers with period , (i.e., as periodic bi-infinite sequences: ) or equivalently, as funct 또는 Z {Z주기적 있는 기하학적으로 정규 -gon: 실제 선이나 원의 (정점)과 이산 유사하다.

그렇다면, 연산자 이론의 관점에서, 순환 행렬은 이산 적분 변환의 커널, 즉 기능에 대한 콘볼루션 0 1,, n- 1) 이것은 이산 원형 콘볼루션이다. 함수 ) (c ) ( ) (는)

(시퀀스가 주기적이라는 것을 나타냄) 이것은 (i) 의 순환 행렬에 의한 벡터(i )displaystyle 의 산물이다

그런 다음 이산 푸리에 변환은 매트릭스 설정에서 대각선에 해당하는 경련을 곱셈으로 변환한다.

복합 항목이 있는 모든 순환 행렬의 C -algebra는 그룹 이 있다

대칭 순환 행렬

대칭 순환기 C{\C -n = {\라는 추가 조건이 있다 따라서 / + +1에 의해 결정된다.

실제 대칭 행렬의 고유값은 실제 값이다. 해당하는 고유값은 다음과 같다.

단조로움(
for odd, where denotes the real part of . This can be further simplified by using the fact that .

대칭 순환 행렬은 이대칭 행렬의 등급에 속한다.

은둔자 순환 행렬

통신 이론에서 어디서나 볼 수 있는 순환 매트릭스의 복잡한 버전은 대개 에르미트어다. 이 경우 -= , i / i}^},\; 그 결정요인과 모든 고유값이 실제 값이다.

n이 처음 두 행이라도 같을 경우 반드시 형식을 취한다.

상단 후반 줄의 첫 번째 원소 가 실제인 경우.

n이 이상하면 우리는 얻는다.

티는[5] 은둔자 조건의 고유값 제약에 대해 논의해왔다.

적용들

선형 방정식

주어진 행렬 방정식

여기서 (는 크기가 인 순환 정사각형 행렬이며, 우리는 방정식을 원형 경련으로 쓸 수 있다.
여기서 { C {\ 의 첫 번째 열이며 은 각 방향으로 주기적으로 확장된다. 원형 콘볼루션 정리를 이용하여 이산 푸리에 변환을 이용하여 순환 콘볼루션을 성분별 곱셈으로 변환할 수 있다.
하도록

이 알고리즘은 특히 빠른 푸리에 변환을 사용하는 경우 표준 가우스 제거보다 훨씬 빠르다.

그래프 이론에서

그래프 이론에서 인접 행렬이 순환인 그래프 또는 디그그래프순환 그래프(또는 디그그래프)라고 한다. 마찬가지로, 그래프는 자동형 그룹이 전체 길이 주기를 포함하는 경우 순환한다. 뫼비우스 사다리는 원시 질서분야에 대한 Paley 그래프와 마찬가지로 순환 그래프의 예다.

참조

  1. ^ Davis, Philip J, Circulant Matrice, Wiley, 1970년, 뉴욕 주(州), ISBN0471057711
  2. ^ 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.
  3. ^ 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
  4. ^ 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
  5. ^ Tee, G J (2007). "Eigenvectors of Block Circulant and Alternating Circulant Matrices". New Zealand Journal of Mathematics. 36: 195–211.

외부 링크