Циркулянт

У лінійній алгебрі, циркулянт — особливий підвид матриць Тепліца, в якій кожен вектор-стовпчик являє собою попередній вектор стовпчик циклічно зсунутий на один елемент праворуч. У обчислювальній математиці, циклічні матриці важливі, бо воно діагоналізовні за допомогою дискретного перетворення Фур'є, тобто, лінійні рівняння, які містять їх можна розв'язати застосувавши швидке перетворення Фур'є.[1] Їх можна інтерпретувати аналітично як інтегральне ядро згортки циклічної групи $\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)$ .[2]

Див. також

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

Примітки

Philip J. Davis, Circulant Matrices, Wiley, New York, 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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[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.