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

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

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

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

В криптографии циркулянтная матрица используется на этапе MixColumns Расширенного стандарта шифрования .

Определение

Циркулянтная матрица принимает форму или транспонированную форму этой формы (по выбору обозначений). Если каждая из них является квадратной матрицей , то матрица называется блочно-циркулянтной матрицей . ${\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}$

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

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

Нормализованные собственные векторы циркулянтной матрицы являются модами Фурье, а именно, где — примитивный корень степени -1 из единицы , а — мнимая единица . $${\displaystyle v_{j}={\frac {1}{\sqrt {n}}}\left(1,\omega ^{j},\omega ^{2j},\ldots ,\omega ^{(n-1)j}\right)^{T},\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^{+}}$
• Матрица , составленная из собственных векторов циркулянтной матрицы, связана с дискретным преобразованием Фурье и его обратным преобразованием: Следовательно, матрица диагонализируется . Фактически, мы имеем , где — первый столбец . Собственные значения задаются произведением . Это произведение можно легко вычислить с помощью быстрого преобразования Фурье . ^[3] И наоборот, для любой диагональной матрицы произведение является циркулянтным. ${\displaystyle F_{n}}$ $${\displaystyle F_{n}{\text{ is unitary}},{\text{ where }}F_{n}=[v_{0},v_{1},\dots ,v_{n-1}]={\frac {1}{\sqrt {n}}}(f_{kj}){\text{ with }}f_{kj}=e^{2\pi i/n\cdot kj},\,{\text{for }}0\leq k,j\leq n-1.}$$ ${\displaystyle U_{n}}$ ${\displaystyle C}$ $${\displaystyle C=F_{n}\operatorname {diag} ({\sqrt {n}}\cdot F_{n}^{\dagger }c)F_{n}^{\dagger },}$$ ${\displaystyle c}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle F_{n}^{\dagger }c}$ ${\displaystyle D}$ ${\displaystyle F_{n}DF_{n}^{\dagger }}$
• Пусть — ( монический ) характеристический многочлен циркулянтной матрицы . Тогда масштабированная производная — это характеристический многочлен следующей подматрицы матрицы : (см. ^[4] для доказательства ). ${\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}}}$$

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

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

Рассмотрим векторы в как функции целых чисел с периодом , (т.е. как периодические бесконечные в обе стороны последовательности: ) или, что эквивалентно, как функции циклической группы порядка (обозначаемой или ) геометрически, на (вершинах) правильного -угольника : это дискретный аналог периодических функций на действительной прямой или окружности . ${\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 {\vec {\lambda }}={\sqrt {n}}\cdot F_{n}^{\dagger }c}$ $${\displaystyle {\begin{array}{lcl}\lambda _{k}&=&c_{0}+c_{n/2}e^{-\pi i\cdot k}+2\sum _{j=1}^{{\frac {n}{2}}-1}c_{j}\cos {(-{\frac {2\pi }{n}}\cdot kj)}\\&=&c_{0}+c_{n/2}\omega _{k}^{n/2}+2c_{1}\Re \omega _{k}+2c_{2}\Re \omega _{k}^{2}+\dots +2c_{n/2-1}\Re \omega _{k}^{n/2-1}\end{array}}}$$ ${\displaystyle n}$ $${\displaystyle {\begin{array}{lcl}\lambda _{k}&=&c_{0}+2\sum _{j=1}^{\frac {n-1}{2}}c_{j}\cos {(-{\frac {2\pi }{n}}\cdot kj)}\\&=&c_{0}+2c_{1}\Re \omega _{k}+2c_{2}\Re \omega _{k}^{2}+\dots +2c_{(n-1)/2}\Re \omega _{k}^{(n-1)/2}\end{array}}}$$ ${\displaystyle n}$ ${\displaystyle \Re z}$ ${\displaystyle z}$ ${\displaystyle \Re \omega _{k}^{j}=\Re e^{-{\frac {2\pi i}{n}}\cdot kj}=\cos(-{\frac {2\pi }{n}}\cdot kj)}$ ${\displaystyle \omega _{k}^{n/2}=e^{-{\frac {2\pi i}{n}}\cdot k{\frac {n}{2}}}=e^{-\pi i\cdot k}}$ ${\displaystyle k}$

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

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

Комплексная версия циркулянтной матрицы, повсеместно встречающаяся в теории связи, обычно является эрмитовой . В этом случае и ее определитель, и все собственные значения являются действительными. ${\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 0-471-05771-1. OCLC  1408988930.
2. AW Ingleton (1956). «Ранг циркулянтных матриц». J. London Math. Soc . s1-31 (4): 445–460. doi :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. Ти, ГДж (2007). «Собственные векторы блочных циркулянтных и чередующихся циркулянтных матриц» (PDF) . Новозеландский журнал математики . 36 : 195–211.

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

• Грей, Р. М. (2006). Матрицы Теплица и циркулянты: обзор (PDF) . Сейчас. doi : 10.1561/0100000006. ISBN 978-1-933019-68-0– через Стэнфордский университет.
• IPython Notebook, демонстрирующий свойства циркулянтных матриц