Циркулирующая матрица

Чтобы узнать о симметричных графах, см. Граф циркулянта .

В линейной алгебре циркулянтная матрица — это квадратная матрица , все строки которой состоят из одних и тех же элементов, и каждая строка повернута на один элемент вправо относительно предыдущей строки. Это особый вид матрицы Теплица .

В численном анализе циркулянтные матрицы важны, поскольку они диагонализуются дискретным преобразованием Фурье , и, следовательно, линейные уравнения , которые их содержат, могут быть быстро решены с использованием быстрого преобразования Фурье . Их можно аналитически интерпретировать как интегральное ядро ​​оператора свертки на циклической группе. $C_{n}$ и, следовательно, часто появляются в формальных описаниях пространственно-инвариантных линейных операций. Это свойство также имеет решающее значение в современных программно определяемых радиостанциях, которые используют мультиплексирование с ортогональным частотным разделением для распределения символов (битов) с использованием циклического префикса . Это позволяет представить канал в виде циркулянтной матрицы, упрощая выравнивание канала в частотной области .

В криптографии циркулянтная матрица используется на MixColumns этапе Advanced Encryption Standard .

Определение

Ан $n\times n$ циркулирующая матрица $C$ принимает форму $$C={\begin{bmatrix}c_{0}&c_{n-1}&\cdots &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}&\cdots &c_{1}&c_{0}\\\end{bmatrix}}$$или транспонирование этой формы (по выбору обозначений). Если каждый $c_{i}$ это $p\times p$ квадратная матрица , то $np\times np$ матрица $C$ называется блочно-циркулянтной матрицей .

Матрица циркулянта полностью задается одним вектором: $c$, который отображается как первый столбец (или строка) $C$. Остальные столбцы (и строки соответственно) $C$ каждая циклическая перестановка вектора $c$ со смещением, равным индексу столбца (или строки, соответственно), если строки индексируются из $0$ к $n-1$. (Циклическая перестановка строк имеет тот же эффект, что и циклическая перестановка столбцов.) Последняя строка $C$ вектор $c$ сдвинуто на единицу назад.

Разные источники определяют матрицу циркулянта по-разному, например, как указано выше, или с помощью вектора $c$ соответствующий первой строке, а не первому столбцу матрицы; и, возможно, с другим направлением смещения (что иногда называют антициркулянтной матрицей ).

Полином ​ $f(x)=c_{0}+c_{1}x+\dots +c_{n-1}x^{n-1}$ называется ассоциированным полиномом матрицы $C$.

Характеристики

Собственные векторы и собственные значения

Нормализованными собственными векторами циркулянта являются моды Фурье, а именно: $$v_{j}={\frac {1}{\sqrt {n}}}\left(1,\omega ^{j},\omega ^{2j},\ldots ,\omega ^{(n-1)j}\right),\quad j=0,1,\ldots ,n-1,$$где $\omega =\exp \left({\tfrac {2\pi i}{n}}\right)$ это примитив $n$-й корень из единства и $i$ это мнимая единица .

(Это можно понять, осознав, что умножение на циркулянтную матрицу реализует свертку. В пространстве Фурье свертки становятся умножением. Следовательно, произведение циркулянтной матрицы с модой Фурье дает кратное этой моде Фурье, т.е. это собственный вектор. )

Соответствующие собственные значения имеют вид $$\lambda _{j}=c_{0}+c_{1}\omega ^{j}+c_{2}\omega ^{2j}+\dots +c_{n-1}\omega ^{(n-1)j},\quad j=0,1,\dots ,n-1.$$

Определитель

Как следствие явной формулы для собственных значений, приведенной выше, определитель циркулянтной матрицы можно вычислить как: $$\det C=\prod _{j=0}^{n-1}(c_{0}+c_{n-1}\omega ^{j}+c_{n-2}\omega ^{2j}+\dots +c_{1}\omega ^{(n-1)j}).$$Поскольку транспонирование не меняет собственные значения матрицы, эквивалентная формулировка: $$\det C=\prod _{j=0}^{n-1}(c_{0}+c_{1}\omega ^{j}+c_{2}\omega ^{2j}+\dots +c_{n-1}\omega ^{(n-1)j})=\prod _{j=0}^{n-1}f(\omega ^{j}).$$

Классифицировать

Ранг циркулянтной матрицы $C$ равно $n-d$ где $d$ - степень многочлена $\gcd(f(x),x^{n}-1)$.

Другие объекты недвижимости

• Любой циркулянт представляет собой матричный полином (а именно, ассоциированный полином) в матрице циклических перестановок $P$: $$C=c_{0}I+c_{1}P+c_{2}P^{2}+\dots +c_{n-1}P^{n-1}=f(P),$$ где $P$ задается сопутствующей матрицей $$P={\begin{bmatrix}0&0&\cdots &0&1\\1&0&\cdots &0&0\\0&\ddots &\ddots &\vdots &\vdots \\\vdots &\ddots &\ddots &0&0\\0&\cdots &0&1&0\end{bmatrix}}.$$
• Набор ​ ​ $n\times n$ циркулянтные матрицы образуют $n$- размерное векторное пространство относительно сложения и скалярного умножения. пространство можно интерпретировать как пространство функций на циклической группе порядка Это $n$, $C_{n}$или, что то же самое, как групповое кольцо $C_{n}$.
• Циркулянтные матрицы образуют коммутативную алгебру , поскольку для любых двух данных циркулянтных матриц $A$ и $B$, сумма $A+B$ является циркулянтом, продукт $AB$ является циркулирующим, и $AB=BA$.
• Для неособой циркулянтной матрицы $A$, его инверсия $A^{-1}$ также является циркулянтом. Для сингулярной циркулянтной матрицы ее псевдообратная Мура – ​​Пенроуза $A^{+}$ они распространяют его.
• Матрица $U$ который состоит из собственных векторов циркулянтной матрицы, связан с дискретным преобразованием Фурье и его обратным преобразованием: $$U_{n}^{*}={\frac {1}{\sqrt {n}}}F_{n},\quad {\text{and}}\quad U_{n}={\sqrt {n}}F_{n}^{-1},{\text{ where }}F_{n}=(f_{jk}){\text{ with }}f_{jk}=e^{-2jk\pi i/n},\,{\text{for }}0\leq j,k<n.$$ Следовательно, матрица $U_{n}$ диагонализирует $C$. На самом деле, у нас есть $$C=U_{n}\operatorname {diag} (F_{n}c)U_{n}^{*}=F_{n}^{-1}\operatorname {diag} (F_{n}c)F_{n},$$ где $c$ это первый столбец $C$. Собственные значения $C$ даны продуктом $F_{n}c$. Это произведение можно легко вычислить с помощью быстрого преобразования Фурье . Обратно, для любой диагональной матрицы $D$, продукт $F_{n}^{-1}DF_{n}$ они распространяют его.
• Позволять $p(x)$ быть ( моническим ) характеристическим полиномом $n\times n$ циркулирующая матрица $C$. Тогда масштабированная производная ${\textstyle {\frac {1}{n}}p'(x)}$ является характеристическим полиномом следующих $(n-1)\times (n-1)$ подматрица $C$: $$C_{n-1}={\begin{bmatrix}c_{0}&c_{n-1}&\cdots &c_{3}&c_{2}\\c_{1}&c_{0}&c_{n-1}&&c_{3}\\\vdots &c_{1}&c_{0}&\ddots &\vdots \\c_{n-3}&&\ddots &\ddots &c_{n-1}\\c_{n-2}&c_{n-3}&\cdots &c_{1}&c_{0}\\\end{bmatrix}}$$ (видеть для доказательства ).

Аналитическая интерпретация

Циркулянтные матрицы можно интерпретировать геометрически , что объясняет связь с дискретным преобразованием Фурье.

Рассмотрим векторы в $\mathbb {R} ^{n}$ как функции целых чисел с периодом $n$, (т.е. как периодические бибесконечные последовательности: $\dots ,a_{0},a_{1},\dots ,a_{n-1},a_{0},a_{1},\dots$) или, что то же самое, как функции на циклической группе порядка $n$ (обозначается $C_{n}$ или $\mathbb {Z} /n\mathbb {Z}$) геометрически, на (вершинах) регулярного $n$-gon : это дискретный аналог периодических функций на реальной прямой или окружности .

Тогда, с точки зрения теории операторов , циркулянтная матрица является ядром дискретного интегрального преобразования , а именно оператора свертки для функции $(c_{0},c_{1},\dots ,c_{n-1})$; это дискретная круговая свертка . Формула свертки функций $(b_{i}):=(c_{i})*(a_{i})$ является

$b_{k}=\sum _{i=0}^{n-1}a_{i}c_{k-i}$

(напомним, что последовательности периодические)что является произведением вектора $(a_{i})$ по циркулянтной матрице для $(c_{i})$.

Затем дискретное преобразование Фурье преобразует свертку в умножение, что в матричной настройке соответствует диагонализации.

The $C^{*}$-алгебра всех циркулянтных матриц с комплексными элементами изоморфна группе $C^{*}$-алгебра $\mathbb {Z} /n\mathbb {Z} .$

Симметричные циркулянтные матрицы

Для симметричной циркулянтной матрицы $C$ есть дополнительное условие, что $c_{n-i}=c_{i}$. Таким образом, определяется $\lfloor n/2\rfloor +1$ элементы. $$C={\begin{bmatrix}c_{0}&c_{1}&\cdots &c_{2}&c_{1}\\c_{1}&c_{0}&c_{1}&&c_{2}\\\vdots &c_{1}&c_{0}&\ddots &\vdots \\c_{2}&&\ddots &\ddots &c_{1}\\c_{1}&c_{2}&\cdots &c_{1}&c_{0}\\\end{bmatrix}}.$$

Собственные значения любой вещественной симметричной матрицы вещественны.Соответствующие собственные значения становятся: $$\lambda _{j}=c_{0}+2c_{1}\Re \omega _{j}+2c_{2}\Re \omega _{j}^{2}+\dots +2c_{n/2-1}\Re \omega _{j}^{n/2-1}+c_{n/2}\omega _{j}^{n/2}$$для $n$ даже и $$\lambda _{j}=c_{0}+2c_{1}\Re \omega _{j}+2c_{2}\Re \omega _{j}^{2}+\dots +2c_{(n-1)/2}\Re \omega _{j}^{(n-1)/2}$$для $n$ странно , где $\Re z$ обозначает действительную часть $z$.Это можно еще больше упростить, используя тот факт, что $\Re \omega _{j}^{k}=\cos(2\pi jk/n)$ и $\omega _{j}^{n/2}=\exp \left({\pi ij}\right)=\pm 1$ в зависимости от $j$ четное или нечетное.

Симметричные циркулянтные матрицы относятся к классу бисимметричных матриц .

Эрмитова циркулянтная матрица

Комплексная версия циркулянтной матрицы, повсеместно встречающаяся в теории коммуникаций, обычно является эрмитовой . В этом случае $c_{n-i}=c_{i}^{*},\;i\leq n/2$ и его определитель и все собственные значения действительны.

Если n четно, первые две строки обязательно принимают вид $${\begin{bmatrix}r_{0}&z_{1}&z_{2}&r_{3}&z_{2}^{*}&z_{1}^{*}\\z_{1}^{*}&r_{0}&z_{1}&z_{2}&r_{3}&z_{2}^{*}\\\dots \\\end{bmatrix}}.$$в котором первый элемент $r_{3}$ в верхнем втором полуряде реально.

Если n нечетно, мы получаем $${\begin{bmatrix}r_{0}&z_{1}&z_{2}&z_{2}^{*}&z_{1}^{*}\\z_{1}^{*}&r_{0}&z_{1}&z_{2}&z_{2}^{*}\\\dots \\\end{bmatrix}}.$$

тройник обсудил ограничения на собственные значения для условия Эрмита.

Приложения

В линейных уравнениях

Учитывая матричное уравнение

$C\mathbf {x} =\mathbf {b} ,$

где $C$ представляет собой циркулянтную матрицу размера $n$, мы можем записать уравнение в виде круговой свертки $$\mathbf {c} \star \mathbf {x} =\mathbf {b} ,$$где $\mathbf {c}$ это первый столбец $C$, а векторы $\mathbf {c}$, $\mathbf {x}$ и $\mathbf {b}$ циклически расширяются в каждом направлении. Используя теорему о круговой свертке , мы можем использовать дискретное преобразование Фурье , чтобы преобразовать циклическую свертку в покомпонентное умножение. $${\mathcal {F}}_{n}(\mathbf {c} \star \mathbf {x} )={\mathcal {F}}_{n}(\mathbf {c} ){\mathcal {F}}_{n}(\mathbf {x} )={\mathcal {F}}_{n}(\mathbf {b} )$$так что $$\mathbf {x} ={\mathcal {F}}_{n}^{-1}\left[\left({\frac {({\mathcal {F}}_{n}(\mathbf {b} ))_{\nu }}{({\mathcal {F}}_{n}(\mathbf {c} ))_{\nu }}}\right)_{\!\nu \in \mathbb {Z} }\,\right]^{\rm {T}}.$$

Этот алгоритм намного быстрее стандартного исключения Гаусса , особенно если быстрое преобразование Фурье используется .

В теории графов

В теории графов граф матрица или орграф, которого смежности является циркулянтом, называется циркулянтным графом /орграфом. Эквивалентно, граф является циркулянтным, если его группа автоморфизмов содержит цикл полной длины. Лестницы Мёбиуса являются примерами циркулянтных графов, как и графы Пэли для полей простого порядка .

Внешние ссылки

• Р.М. Грей, Теплиц и циркулянтные матрицы: обзор дои : 10.1561/0100000006
• Блокнот IPython, демонстрирующий свойства циркулянтных матриц