Циркулянтная матрица

Матрица линейной алгебры

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

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

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

Определение

Циркулянтная матрица имеет вид ${\displaystyle n\times n}$ ${\displaystyle C}$

$${\displaystyle 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}}}$$

транспонированиематрицейматрицей блочного циркулянта ${\displaystyle c_{i}}$ ${\displaystyle p\times p}$ ${\displaystyle np\times np}$ ${\displaystyle C}$

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

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

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

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

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

Нормализованными собственными векторами циркулянта являются моды Фурье, а именно:

$${\displaystyle 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,}$$

из единицымнимая единица ${\displaystyle \omega =\exp \left({\tfrac {2\pi i}{n}}\right)}$ ${\displaystyle n}$ ${\displaystyle i}$

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

Соответствующие собственные значения имеют вид

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

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

Как следствие явной формулы для приведенных выше собственных значений, определитель циркулянтной матрицы можно вычислить как:

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

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

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

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

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

• Любой циркулянт представляет собой матричный полином (а именно, ассоциированный полином) в матрице циклических перестановок : ${\displaystyle P}$
  $${\displaystyle C=c_{0}I+c_{1}P+c_{2}P^{2}+\dots +c_{n-1}P^{n-1}=f(P),}$$
  где задается сопутствующей матрицей ${\displaystyle P}$
  $${\displaystyle 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}}.}$$
• Набор циркулянтных матриц образует -мерное векторное пространство относительно сложения и скалярного умножения. Это пространство можно интерпретировать как пространство функций на циклической группе порядка , или , что то же самое, как групповое кольцо . ${\displaystyle n\times n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle C_{n}}$ ${\displaystyle C_{n}}$
• Циркулянтные матрицы образуют коммутативную алгебру , поскольку для любых двух данных циркулянтных матриц и , сумма является циркулянтом, произведение является циркулянтом, и . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A+B}$ ${\displaystyle AB}$ ${\displaystyle AB=BA}$
• Для неособой циркулянтной матрицы ее обратная также является циркулянтом. Для сингулярной циркулянтной матрицы ее псевдообратная Мура – ​​Пенроуза является циркулянтом. ${\displaystyle A}$ ${\displaystyle A^{-1}}$ ${\displaystyle A^{+}}$
• Матрица , состоящая из собственных векторов циркулянтной матрицы, связана с дискретным преобразованием Фурье и его обратным преобразованием: ${\displaystyle U}$
  $${\displaystyle 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.}$$
  Следовательно, матрица диагонализуется . На самом деле, у нас есть ${\displaystyle U_{n}}$ ${\displaystyle C}$
  $${\displaystyle C=U_{n}\operatorname {diag} (F_{n}c)U_{n}^{*}=F_{n}^{-1}\operatorname {diag} (F_{n}c)F_{n},}$$
  где находится первый столбец . Собственные значения задаются произведением . Это произведение можно легко вычислить с помощью быстрого преобразования Фурье . ^[3] И наоборот, для любой диагональной матрицы произведение является циркулянтом. ${\displaystyle c}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle F_{n}c}$ ${\displaystyle D}$ ${\displaystyle F_{n}^{-1}DF_{n}}$
• Пусть – ( монический ) характеристический многочлен циркулянтной матрицы . Тогда масштабированная производная является характеристическим полиномом следующей подматрицы : ${\displaystyle p(x)}$ ${\displaystyle n\times n}$ ${\displaystyle C}$ ${\textstyle {\frac {1}{n}}p'(x)}$ ${\displaystyle (n-1)\times (n-1)}$ ${\displaystyle C}$
  $${\displaystyle 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}}}$$
  (доказательство см. в [ ^4] ).

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

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

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

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

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

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

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

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

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

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

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

Собственные значения любой вещественной симметричной матрицы вещественны. Соответствующие собственные значения становятся:

$${\displaystyle \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}}$$

четных ${\displaystyle n}$

$${\displaystyle \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}}$$

нечетногочасть ${\displaystyle n}$ ${\displaystyle \Re z}$ ${\displaystyle z}$ ${\displaystyle \Re \omega _{j}^{k}=\cos(2\pi jk/n)}$ ${\displaystyle \omega _{j}^{n/2}=\exp \left({\pi ij}\right)=\pm 1}$ ${\displaystyle j}$

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

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

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

Если n четно, первые две строки обязательно принимают вид

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

${\displaystyle r_{3}}$

Если n нечетно, мы получаем

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

Ти ^[5] обсуждал ограничения на собственные значения для условия Эрмита.

Приложения

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

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

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

где – циркулянтная матрица размера , мы можем записать уравнение как круговую свертку ${\displaystyle C}$ ${\displaystyle n}$

$${\displaystyle \mathbf {c} \star \mathbf {x} =\mathbf {b} ,}$$

теорему о круговой сверткедискретное преобразование Фурье ${\displaystyle \mathbf {c} }$ ${\displaystyle C}$ ${\displaystyle \mathbf {c} }$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {b} }$

$${\displaystyle {\mathcal {F}}_{n}(\mathbf {c} \star \mathbf {x} )={\mathcal {F}}_{n}(\mathbf {c} ){\mathcal {F}}_{n}(\mathbf {x} )={\mathcal {F}}_{n}(\mathbf {b} )}$$

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

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

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

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

Рекомендации

1. Дэвис, Филип Дж. , Циркулянтные матрицы, Уайли, Нью-Йорк, 1970 ISBN  0471057711
2. AW Инглтон (1956). «Ранг циркулянтных матриц». Дж. Лондон Математика. Соц . с1-31(4): 445–460. дои : 10.1112/jlms/s1-31.4.445.
3. Голуб, Джин Х .; Ван Лоан, Чарльз Ф. (1996), «§4.7.7 Циркулянтные системы», Матричные вычисления (3-е изд.), Джонс Хопкинс, ISBN 978-0-8018-5414-9
4. Кушель, Ольга; Тяглов, Михаил (15 июля 2016 г.), «Циркулянты и критические точки полиномов», Журнал математического анализа и приложений , 439 (2): 634–650, arXiv : 1512.07983 , doi : 10.1016/j.jmaa.2016.03.005 , ISSN  0022-247X
5. Ти, GJ (2007). «Собственные векторы блочного циркулянта и знакопеременные циркулянтные матрицы». Новозеландский математический журнал . 36 : 195–211.

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

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