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

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

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

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

Определение

An ${ Displaystyle п раз п}$ циркулянтная матрица ${ displaystyle C}$ принимает форму

{ displaystyle 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} конец {bmatrix}}}

или транспонировать эту форму (по выбору обозначений).

Циркулянтная матрица полностью задается одним вектором, ${ displaystyle c}$ , который отображается как первый столбец (или строка) ${ displaystyle C}$ . Остальные столбцы (и строки соответственно) ${ displaystyle C}$ каждый циклические перестановки вектора ${ displaystyle c}$ со смещением, равным индексу столбца (или строки, соответственно), если строки проиндексированы от 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}}} (1, omega ^ {j}, omega ^ {2j}, ldots, omega ^ {(n-1 ) j}), 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_ {n-1} omega ^ {j} + c_ {n-2} omega ^ {2j} + ldots + c_ {1} omega ^ {(n-1) j}, qquad j = 0,1, ldots, 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}).}

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

В классифицировать циркулянтной матрицы ${ displaystyle C}$ равно ${ displaystyle n-d}$ , куда ${ displaystyle d}$ это степень полинома ${ Displaystyle НОД (е (х), х ^ {п} -1)}$ .^[2]

Другие свойства

Любой циркулянт является матричным многочленом (а именно ассоциированным многочленом) от циклического матрица перестановок ${ displaystyle P}$ :

{ displaystyle C = c_ {0} I + c_ {1} P + c_ {2} P ^ {2} + ldots + c_ {n-1} P ^ {n-1} = f (P),}

куда

{ displaystyle P}

дан кем-то

{ displaystyle P = { begin {bmatrix} 0 & 0 & ldots & 0 & 1 1 & 0 & ldots & 0 & 0 0 & ddots & ddots & vdots & vdots vdots & ddots & ddots & 0 & 0 0 & ldots & 0 & 1 & 0 end {bmatrix}}.}

Набор ${ Displaystyle п раз п}$ циркулянтные матрицы образуют ${ displaystyle n}$ -размерный векторное пространство относительно их стандартного сложения и скалярного умножения. Это пространство можно интерпретировать как пространство функций на циклическая группа порядка п, ${ displaystyle C_ {n}}$ , или эквивалентно групповое кольцо из ${ displaystyle C_ {n}}$ .
Циркулянтные матрицы образуют коммутативная алгебра, поскольку для любых двух заданных циркулянтных матриц ${ displaystyle A}$ и ${ displaystyle B}$ , сумма ${ displaystyle A + B}$ циркулирует, продукт ${ displaystyle AB}$ циркулирует, и ${ displaystyle AB = BA}$ .
Матрица ${ displaystyle U}$ который состоит из собственные векторы циркулянтной матрицы связана с дискретное преобразование Фурье и его обратное преобразование:

{ displaystyle U_ {n} ^ {*} = { frac {1} { sqrt {n}}} F_ {n}, quad { text {and}} quad U_ {n} = { frac {1} { sqrt {n}}} F_ {n} ^ {- 1}, quad { text {where}} quad F_ {n} = (f_ {jk}) quad { text {с }} quad f_ {jk} = e ^ {- 2jk pi i / n}, quad { text {for}} quad 0 leq j, k

Следовательно, матрица

{ displaystyle U_ {n}}

диагонализует

{ displaystyle C}

. Фактически у нас есть

{ displaystyle C = U_ {n} operatorname {diag} (F_ {n} c) U_ {n} ^ {*} = { frac {1} {n}} F_ {n} ^ {- 1} имя оператора {диаг} (F_ {n} c) F_ {n},}

куда

{ displaystyle c}

это первый столбец

{ displaystyle C}

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

{ displaystyle C}

даются продуктом

{ displaystyle F_ {n} c}

. Этот продукт можно легко рассчитать с помощью быстрое преобразование Фурье.^[3]

Позволять ${ displaystyle p (x)}$ - (монический) характеристический многочлен ${ Displaystyle п раз п}$ циркулянтная матрица ${ displaystyle C}$ , и разреши ${ Displaystyle р '(х)}$ быть производной от ${ displaystyle p (x)}$ . Тогда многочлен ${ displaystyle { frac {1} {n}} p '(x)}$ является характеристическим полиномом следующих ${ Displaystyle (п-1) раз (п-1)}$ подматрица ${ displaystyle C}$ :

{ displaystyle C_ {n-1} = { begin {bmatrix} c_ {0} & c_ {n-1} & dots & 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} & dots & c_ {1} & c_ {0} end {bmatrix}}}

(видеть^[4] для доказательства).

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

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

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

Тогда с точки зрения теория операторов, циркулянтная матрица является ядром дискретного интегральное преобразование, а именно оператор свертки для функции ${ 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 (а_ {я})}$ циркулянтной матрицей для ${ displaystyle (c_ {i})}$ .

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

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

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

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

{ displaystyle C = { begin {bmatrix} c_ {0} & c_ {1} & dots & 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} & dots & c_ {1} & c_ {0} end {bmatrix}}.}

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

{ displaystyle lambda _ {j} = c_ {0} + 2c_ {1} Re omega _ {j} + 2c_ {2} Re omega _ {j} ^ {2} + ldots + 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} + ldots + 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 с_ {п-я} = с_ {я} ^ {*}, ; я Leq п / 2}$ и его определитель и все собственные значения действительны.

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

{ 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}}$ в верхнем втором полустрочке реально.

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

{ displaystyle { begin {bmatrix} r_ {0} & z_ {1} & z_ {2} & z_ {2} ^ {*} & z_ {1} ^ {*} z_ {1} ^ {*} & r_ {0 } & z_ {1} & z_ {2} & z_ {2} ^ {*} точки end {bmatrix}}.}

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

Приложения

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

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

{ Displaystyle mathbf {C} mathbf {x} = mathbf {b},}

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

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

куда ${ displaystyle c}$ это первый столбец ${ displaystyle C}$ , а векторы ${ displaystyle c}$ , ${ displaystyle x}$ и ${ displaystyle 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 mathbf {Z}} right] ^ { rm {T}}.}

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

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

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

внешняя ссылка

[1] Дэвис, Филип Дж., Циркулянтные матрицы, Wiley, New York, 1970. ISBN 0471057711

[2] А. В. Инглтон (1956). «Ранг циркулянтных матриц». J. London Math. Soc. s1-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, Дои:10.1016 / j.jmaa.2016.03.005, ISSN 0022-247X

[5] Ти, Дж. Дж. (2007). «Собственные векторы блочных циркулянтных и переменных циркулянтных матриц». Новозеландский математический журнал. 36: 195–211.

[1]

[2]

[3]

[4]

[5]

Числовая линейная алгебра
Ключевые идеи	Плавающая точка Численная стабильность
Проблемы	Система линейных уравнений Матричные разложения Умножение матриц (алгоритмы ) Расщепление матрицы Редкие проблемы
Аппаратное обеспечение	Кеш процессора TLB Алгоритм без кеширования SIMD Многопроцессорность
Программного обеспечения	MATLAB Подпрограммы базовой линейной алгебры (BLAS) ЛАПАК Специализированные библиотеки Программное обеспечение общего назначения