Матрица циркуляции

редактировать

Матрица, в которой каждая строка повернута на одну позицию вправо от предыдущей строки

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

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

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

Содержание

1 Определение
2 Свойства
- 2.1 Собственные векторы и собственные значения
- 2.2 Определитель
- 2.3 Ранг
- 2.4 Другие свойства
3 Аналитическая интерпретация
4 Симметричные циркулянтные матрицы
5 Сложные симметричные циркулянтные матрицы
6 Приложения
- 6.1 В линейных уравнениях
- 6.2 В теории графов
7 Ссылки
8 Внешние ссылки

Определение

An $n × n {\ displaystyle n \ times n }$ $n \ times n$ циркулянтная матрица $C {\ displaystyle C}$ $C$ принимает форму

C = [c 0 cn - 1… c 2 c 1 c 1 c 0 cn - 1 c 2 ⋮ c 1 c 0 ⋱ ⋮ cn - 2 ⋱ ⋱ cn - 1 cn - 1 cn - 2… c 1 c 0] {\ 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} \\\ end {bmatrix }}}

{\ 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} \\\ end {bmatrix}}}

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

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

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

Многочлен $f (x) = c 0 + c 1 x + ⋯ + cn - 1 xn - 1 {\ displaystyle f (x) = c_ {0} + c_ {1} x + \ точки + c_ {n-1} x ^ {n-1}}$ $f (x) = c_ {0} + c_ {1} x + \ dots + c _ {{n- 1}} х ^ {{п-1}}$ называется ассоциированным многочленом матрицы $C {\ displaystyle C}$ $C$ .

Свойства

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

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

vj = 1 n (1, ω j, ω 2 j,…, ω (n - 1) j), j = 0, 1,…, n - 1, {\ 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 v_ {j} = {\ frac {1} {\ sqrt {n}}} (1, \ omega ^ {j}, \ omega ^ {2j}, \ ldots, \ omega ^ {(n-1) j}), \ quad j = 0,1, \ ldots, n-1,}

где $ω = exp ⁡ ( 2 π in) {\ displaystyle \ omega = \ exp \ left ({\ tfrac {2 \ pi i} {n}} \ right)}$ ${\ displaystyle \ omega = \ exp \ left ({\ tfrac {2 \ pi i} {n}} \ right)}$ является примитивом $n {\ displaystyle n}$ $n$ -й корень из единицы и $i {\ displaystyle i}$ $i$ - мнимая единица.

(это можно понять, осознав что циркулянтная матрица реализует свертку.)

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

λ j = c 0 + cn - 1 ω j + сп - 2 ω 2 j +… + c 1 ω (n - 1) j, j = 0, 1,…, n - 1. {\ 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 \ 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.}

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

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

det (C) = ∏ j = 0 n - 1 (c 0 + cn - 1 ω j + cn - 2 ω 2 j + ⋯ + c 1 ω (n - 1) j). {\ 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_ {n-1} \ omega ^ {j} + c_ {n-2} \ omega ^ {2j} + \ dots + c_ {1} \ omega ^ {( п-1) j}).}

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

det (C) = ∏ j = 0 n - 1 (c 0 + c 1 ω j + c 2 ω 2 j + ⋯ + cn - 1 ω (n - 1) j) = ∏ j = 0 n - 1 f (ω 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 \ 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} ^ {п-1} е (\ омега ^ {j}).}

Ранг

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

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

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

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

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

где

P {\ displaystyle P}

P

задается как

P = [0 0… 0 1 1 0… 0 0 0 ⋱ ⋱ ⋮ ⋮ ⋮ ⋱ ⋱ 0 0 0… 0 1 0]. {\ 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}}.}

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

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

U n ∗ = 1 n F n, и U n = 1 n F n - 1, где F n = (fjk) с fjk = e - 2 jk π i / n, для 0 ≤ j, k < n. {\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{with}}\quad f_{jk}=e^{-2jk\pi i/n},\quad {\text{for}}\quad 0\leq j,k

{\ displaystyle U_ {n} ^ {*} = {\ frac {1} { \ sqrt {n}}} F_ {n}, \ quad {\ text {and}} \ quad U_ {n} = {\ frac {1} {\ sqrt {n}}} F_ {n} ^ {- 1 }, \ quad {\ text {где}} \ quad F_ {n} = (f_ {jk}) \ quad {\ text {with}} \ quad f_ {jk} = e ^ {- 2jk \ pi i / n }, \ quad {\ text {for}} \ quad 0 \ leq j, k <n.}

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

U n {\ displaystyle U_ {n}}

U_ {n}

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

C {\ displaystyle C}

C

. Фактически, мы имеем

C = U n diag ⁡ (F nc) U n ∗ = 1 n F n - 1 diag ⁡ (F nc) F n, {\ displaystyle C = U_ {n} \ operatorname {diag } (F_ {n} c) U_ {n} ^ {*} = {\ frac {1} {n}} F_ {n} ^ {- 1} \ operatorname {diag} (F_ {n} c) F_ { n},}

{\ displaystyle C = U_ {n} \ operatorname {diag} (F_ {n} c) U_ {n} ^ {*} = {\ frac {1} {n}} F_ {n} ^ {- 1} \ operatorname {diag} (F_ {n} c) F_ {n},}

, где

c {\ displaystyle c}

c

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

C {\ displaystyle C}

C

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

C {\ displaystyle C}

C

даются произведением

F n c {\ displaystyle F_ {n} c}

{\ displaystyle F_ {n} c}

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

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

C n - 1 = [ c 0 cn - 1… c 3 c 2 c 1 c 0 cn - 1 c 3 ⋮ c 1 c 0 ⋱ ⋮ cn - 3 ⋱ ⋱ cn - 1 cn - 2 cn - 3… c 1 c 0] {\ 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}}}

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

(см. доказательство).

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

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

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

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

bk = ∑ i = 0 n - 1 aick - i {\ displaystyle b_ {k} = \ sum _ {i = 0} ^ {n-1} a_ {i} c_ {ki} }

b_ {k} = \ sum _ {{i = 0}} ^ {{n -1}} a_ {i} c _ {{ki}}

(напомним, что последовательности периодические)

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

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

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

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

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

C = [c 0 c 1… c 2 c 1 c 1 c 0 c 1 c 2 ⋮ c 1 c 0 ⋱ ⋮ c 2 ⋱ ⋱ c 1 c 1 c 2… c 1 c 0]. {\ 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 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} \\\ конец {bmatrix}}.}

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

λ j = c 0 + 2 c 1 ℜ ω j + 2 c 2 ℜ ω j 2 +… + 2 cn / 2 - 1 ℜ ω jn / 2 - 1 + cn / 2 ω jn / 2 {\ 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 \ 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}}

для $n {\ displaystyle n}$ $n$ даже и

λ j = c 0 + 2 c 1 ℜ ω j + 2 c 2 ℜ ω j 2 +… + 2 c (n - 1) / 2 ℜ ω J (N - 1) / 2 {\ 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 \ 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}}

для нечетного $n {\ displaystyle n}$ $n$ , где $ℜ z {\ displaystyle \ Re z}$ $\ Re z$ обозначает действительную часть $z {\ displaystyle z}$ $г$ . Это можно еще более упростить, если использовать тот факт, что $ℜ ω jk = cos ⁡ (2 π jk / n) {\ displaystyle \ Re \ omega _ {j} ^ {k} = \ cos (2 \ pi jk / n)}$ ${\ displaystyle \ Re \ omega _ {j} ^ {k} = \ cos (2 \ pi jk / n)}$ .

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

Сложная версия циркулянтной матрицы, широко распространенная в теории связи, обычно эрмитова. В этом случае $cn - i = ci ∗, i ≤ n / 2 {\ displaystyle c_ {ni} = c_ {i} ^ {*}, \; i \ leq n / 2}$ ${\ displaystyle c_ {ni} = c_ {i} ^ {*}, \; я \ Leq n / 2}$ и его определитель и все собственные значения действительны.

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

[r 0 z 1 z 2 r 3 z 2 ∗ z 1 ∗ z 1 ∗ r 0 z 1 z 2 r 3 z 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 {\ 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 {\ displaystyle r_ {3}}$ ${\ displaystyle r_ {3}}$ в верхней второй половине строки является действительным.

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

[r 0 z 1 z 2 z 2 ∗ z 1 ∗ z 1 ∗ r 0 z 1 z 2 z 2 ∗…]. {\ 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}}.}

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

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

Приложения

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

Дано матричное уравнение

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

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

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

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

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

где $c {\ displaystyle c}$ $c$ - это первый столбец $C {\ displaystyle C}$ $C$ , а векторы $c {\ displaystyle c}$ $c$ , $x {\ displaystyle x }$ $x$ и $b {\ displaystyle b}$ $b$ циклически расширяются в каждом направлении. Используя теорему о круговой свертке, мы можем использовать дискретное преобразование Фурье для преобразования циклической свертки в покомпонентное умножение

F n (c ⋆ x) = F n (c) F N (Икс) знак равно F N (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 {\ mathcal {F}} _ {n} (\ mathbf {c} \ star \ mathbf {x}) = {\ mathcal {F}} _ {n} (\ mathbf {c}) {\ mathcal {F}} _ {n} (\ mathbf {x}) = {\ mathcal {F}} _ {n} (\ mathbf {b})}

так что

x = F n - 1 [((F n (b)) ν (F n (c)) ν) ν ∈ Z] T. {\ 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}}.}

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

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

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

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

Ссылки

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