YaChudo

Циркулянт

Переглядів: 0. Оновлено 10.11.2026.

У лінійній алгебрі, циркулянт — особливий підвид матриць Тепліца, в якій кожен вектор-стовпчик являє собою попередній вектор стовпчик циклічно зсунутий на один елемент праворуч. У обчислювальній математиці, циклічні матриці важливі, бо воно діагоналізовні за допомогою дискретного перетворення Фур'є, тобто, лінійні рівняння, які містять їх можна розв'язати застосувавши швидке перетворення Фур'є.[1] Їх можна інтерпретувати аналітично як інтегральне ядро згортки циклічної групи Z / n Z , {\displaystyle \mathbb {Z} /n\mathbb {Z} ,} тому вони часто з'являються у формальних описах просторово інваріантних лінійних операцій. У криптографії, циклічні матриці використовуються в MixColumns етапі в Advanced Encryption Standard.

Означення

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}&\dots &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}&\dots &c_{1}&c_{0}\\\end{bmatrix}}.}

Один вектор c , {\displaystyle c,} що з'являється в першому стовпці C , {\displaystyle C,} повністю визначає циркулянт. Інші стовпці C {\displaystyle C} є циклічними переставками вектора 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 ,   ω j 2 ,   … ,   ω j n − 1 ) T , j = 0 , 1 , … , n − 1 , {\displaystyle v_{j}={\frac {1}{\sqrt {n}}}(1,~\omega _{j},~\omega _{j}^{2},~\ldots ,~\omega _{j}^{n-1})^{T},\quad j=0,1,\ldots ,n-1,}

де ω j = exp ⁡ ( 2 π i j n ) {\displaystyle \omega _{j}=\exp \left({\tfrac {2\pi ij}{n}}\right)} є n-м коренем з одиниці, а i {\displaystyle i} це уявна одиниця.

Відповідні власні значення такі

λ j = c 0 + c n − 1 ω j + c n − 2 ω j 2 + … + c 1 ω j n − 1 , j = 0 … n − 1. {\displaystyle \lambda _{j}=c_{0}+c_{n-1}\omega _{j}+c_{n-2}\omega _{j}^{2}+\ldots +c_{1}\omega _{j}^{n-1},\qquad j=0\ldots n-1.}

Визначник

Визначник циркулянта можна обчислити як:

d e t ( C ) = ∏ j = 0 n − 1 ( c 0 + c n − 1 ω j + c n − 2 ω j 2 + ⋯ + c 1 ω j n − 1 ) . {\displaystyle \mathrm {det} (C)=\prod _{j=0}^{n-1}(c_{0}+c_{n-1}\omega _{j}+c_{n-2}\omega _{j}^{2}+\dots +c_{1}\omega _{j}^{n-1}).}

Оскільки транспонування не змінює власні значення матриці, то тотожним формулюванням є

d e t ( C ) = ∏ j = 0 n − 1 ( c 0 + c 1 ω j + c 2 ω j 2 + ⋯ + c n − 1 ω j n − 1 ) = ∏ j = 0 n − 1 f ( ω j ) . {\displaystyle \mathrm {det} (C)=\prod _{j=0}^{n-1}(c_{0}+c_{1}\omega _{j}+c_{2}\omega _{j}^{2}+\dots +c_{n-1}\omega _{j}^{n-1})=\prod _{j=0}^{n-1}f(\omega _{j}).}
Доведення

Помножимо циркулянт праворуч на визначник Вандермонда типу | ω j i − 1 | n × n {\displaystyle |\omega _{j}^{i-1}|_{n\times n}} :

| a 1 a 2 ⋯ a n a n a 1 ⋯ a n − 1 ⋮ ⋮ ⋱ ⋮ a 2 a 3 ⋯ a 1 | ⋅ | 1 1 ⋯ 1 ω 1 ω 2 ⋯ ω n ⋮ ⋮ ⋱ ⋮ ω 1 n − 1 ω 2 ( n − 1 ) ⋯ ω n n | = | f ( ω 1 ) f ( ω 2 ) ⋯ f ( ω n ) ω 1 f ( ω 1 ) ω 2 f ( ω 2 ) ⋯ ω n f ( ζ n ) ⋮ ⋮ ⋱ ⋮ ω 1 n − 1 f ( ω 1 ) ω 2 n − 1 f ( ω 2 ) ⋯ ω n n − 1 f ( ω n ) | = {\displaystyle {\begin{vmatrix}a_{1}&a_{2}&\cdots &a_{n}\\a_{n}&a_{1}&\cdots &a_{n-1}\\\vdots &\vdots &\ddots &\vdots \\a_{2}&a_{3}&\cdots &a_{1}\end{vmatrix}}\cdot {\begin{vmatrix}1&1&\cdots &1\\\omega _{1}&\omega _{2}&\cdots &\omega _{n}\\\vdots &\vdots &\ddots &\vdots \\\omega _{1}^{n-1}&\omega _{2}^{(n-1)}&\cdots &\omega _{n}^{n}\end{vmatrix}}={\begin{vmatrix}f(\omega _{1})&f(\omega _{2})&\cdots &f(\omega _{n})\\\omega _{1}f(\omega _{1})&\omega _{2}f(\omega _{2})&\cdots &\omega _{n}f(\zeta _{n})\\\vdots &\vdots &\ddots &\vdots \\\omega _{1}^{n-1}f(\omega _{1})&\omega _{2}^{n-1}f(\omega _{2})&\cdots &\omega _{n}^{n-1}f(\omega _{n})\end{vmatrix}}=}

= f ( ω 1 ) f ( ω 2 ) … f ( ω n ) ⋅ | 1 1 ⋯ 1 ω 1 ω 2 ⋯ ω n ⋮ ⋮ ⋱ ⋮ ω 1 n − 1 ω 2 n − 1 ⋯ ω n n − 1 | {\displaystyle =f(\omega _{1})f(\omega _{2})\ldots f(\omega _{n})\cdot {\begin{vmatrix}1&1&\cdots &1\\\omega _{1}&\omega _{2}&\cdots &\omega _{n}\\\vdots &\vdots &\ddots &\vdots \\\omega _{1}^{n-1}&\omega _{2}^{n-1}&\cdots &\omega _{n}^{n-1}\end{vmatrix}}}

Тепер скорочуємо на визначник Вандермонда як ненульовий.■

Ранг

Ранг циркулянта C {\displaystyle C} дорівнює n − d {\displaystyle n-d} , де d {\displaystyle d} це степінь gcd ( f ( x ) , x n − 1 ) {\displaystyle \gcd(f(x),x^{n}-1)} .[2]

Див. також

Циркулянтний граф

Примітки

  1. ↑ Philip J. Davis, Circulant Matrices, Wiley, New York, 1970 ISBN 0471057711
  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.

Джерело: стаття у Вікіпедії та історія редагувань (автори).