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