Циркулянт

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

Означення

$n\times n$ циркулянт $\ C$ має вигляд

$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,$ що з'являється в першому стовпці $C,$ повністю визначає циркулянт. Інші стовпці $C$ є циклічними переставками вектора $c$ зі зсувом, що дорівнює індексу стовпця. Останній рядок $C$ є вектором $c$ у зворотньому порядку, а інші рядки є його циклічними переставками.

Многочлен $f(x)=c_{0}+c_{1}x+\dots +c_{n-1}x^{n-1}$ називається пов'язаним многочленом матриці $C.$

Властивості

Власні вектори і значення

Нормалізовані власні вектори циркулянта задаються як

$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,$

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

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

$\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.$

Визначник

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

$\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}).$

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

$\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}).$

Доведення  

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

${\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(\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$ дорівнює $n-d$, де $d$ це степінь $\gcd(f(x),x^{n}-1)$.

Див. також

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