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

Циркулянтная матрица — это квадратная матрица, каждый последующий ряд которой получен из предыдущего циклическим сдвигом на одну позицию вправо (или влево). Такие матрицы являются частным случаем теплицевых матриц и обладают рядом уникальных алгебраических свойств, включая коммутативность умножения и возможность диагонализации с помощью дискретного преобразования Фурье.

Определение и структура

Пусть первая строка циркулянтной матрицы \( C \) размера \( n \times n \) задана вектором \( \mathbf{c} = (c_0, c_1, \dots, c_{n-1}) \). Тогда матрица имеет вид:

\[ C = \begin{pmatrix} c_0 & c_1 & c_2 & \dots & c_{n-1} \\ c_{n-1} & c_0 & c_1 & \dots & c_{n-2} \\ c_{n-2} & c_{n-1} & c_0 & \dots & c_{n-3} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ c_1 & c_2 & c_3 & \dots & c_0 \end{pmatrix} \]

Каждый элемент \( C_{i,j} \) определяется как \( C_{i,j} = c_{(j-i) \mod n} \), где индексация начинается с нуля. Таким образом, матрица полностью определяется первой строкой. Аналогично можно определить матрицу, сдвигая столбцы, что даёт транспонированную версию.

Свойства

Циркулянтные матрицы обладают рядом фундаментальных свойств, отличающих их от произвольных квадратных матриц.

Коммутативность

Произведение двух циркулянтных матриц одного размера коммутативно: \( C_1 C_2 = C_2 C_1 \). Более того, произведение также является циркулянтной матрицей. Это свойство следует из того, что циркулянтные матрицы образуют коммутативную алгебру относительно умножения.

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

Собственные векторы циркулянтной матрицы не зависят от её элементов и являются столбцами матрицы дискретного преобразования Фурье (ДПФ). Для размера \( n \) собственный вектор \( \mathbf{v}_k \), соответствующий собственному значению \( \lambda_k \), имеет компоненты:

\[ v_{k,j} = \omega^{kj}, \quad \omega = e^{-2\pi i / n}, \quad j = 0, 1, \dots, n-1. \]

Собственные значения вычисляются как дискретное преобразование Фурье первой строки:

\[ \lambda_k = \sum_{j=0}^{n-1} c_j \omega^{kj}. \]

Таким образом, циркулянтная матрица диагонализуется матрицей Фурье: \( C = F^{-1} \Lambda F \), где \( \Lambda = \operatorname{diag}(\lambda_0, \lambda_1, \dots, \lambda_{n-1}) \).

Обратимость

Циркулянтная матрица обратима тогда и только тогда, когда все её собственные значения \( \lambda_k \) отличны от нуля. Обратная матрица также является циркулянтной и может быть найдена через обратное дискретное преобразование Фурье последовательности \( 1/\lambda_k \).

Детерминант и след

Детерминант циркулянтной матрицы равен произведению её собственных значений: \( \det(C) = \prod_{k=0}^{n-1} \lambda_k \). След матрицы равен \( n c_0 \), так как на главной диагонали стоят элементы \( c_0 \).

Связь с циклической свёрткой

Умножение циркулянтной матрицы на вектор эквивалентно циклической (круговой) свёртке. Если \( C \) — циркулянтная матрица, построенная по вектору \( \mathbf{c} \), то для произвольного вектора \( \mathbf{x} \) выполняется:

\[ (C \mathbf{x})_i = \sum_{j=0}^{n-1} c_{(i-j) \mod n} x_j = (\mathbf{c} \star \mathbf{x})_i, \]

где \( \star \) обозначает циклическую свёртку. Это свойство широко используется в цифровой обработке сигналов, где циркулянтные матрицы применяются для моделирования линейных периодических систем.

Классификация и частные случаи

Циркулянтные матрицы можно классифицировать по структуре первой строки:

• Симметричные циркулянтные матрицы: первая строка симметрична относительно центра, то есть \( c_j = c_{n-j} \) для всех \( j \). Такие матрицы имеют вещественные собственные значения.
• Циркулянтные матрицы с нулевой суммой: если сумма элементов первой строки равна нулю, то одно из собственных значений равно нулю, и матрица вырождена.
• Циркулянтные матрицы перестановки: частный случай, когда первая строка является единичным вектором, например, \( (0,1,0,\dots,0) \). Такая матрица описывает циклический сдвиг вектора.

Применение

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

Цифровая обработка сигналов

В обработке сигналов циркулянтные матрицы используются для реализации циклической свёртки, которая лежит в основе алгоритмов быстрого преобразования Фурье (БПФ). Благодаря диагонализации через ДПФ, умножение циркулянтной матрицы на вектор выполняется за \( O(n \log n) \) операций, что значительно быстрее прямого умножения (\( O(n^2) \)).

Теория кодирования

В теории кодирования циркулянтные матрицы применяются при построении циклических кодов, в частности кодов Боуза — Чоудхури — Хоквингема (БЧХ) и кодов Рида — Соломона. Порождающие и проверочные матрицы таких кодов часто имеют циркулянтную структуру, что упрощает их реализацию.

Криптография

В криптографии циркулянтные матрицы используются в некоторых алгоритмах симметричного шифрования, например, в стандарте AES (Advanced Encryption Standard) — организация признана нежелательной в РФ не зарегистрирована, но в данном контексте упоминается алгоритм, а не организация. Циркулянтные матрицы применяются в операции MixColumns, где умножение на фиксированную циркулянтную матрицу в поле Галуа обеспечивает диффузию данных.

Численные методы

В численных методах циркулянтные матрицы возникают при решении задач с периодическими граничными условиями, например, при аппроксимации дифференциальных операторов на равномерной сетке с периодическими краевыми условиями. Такие матрицы позволяют эффективно решать системы линейных уравнений с помощью БПФ.

Теория графов

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

Интересные факты

• Циркулянтные матрицы являются частным случаем теплицевых матриц, но, в отличие от них, допускают точную диагонализацию через ДПФ.
• Множество всех циркулянтных матриц размера \( n \) образует коммутативную алгебру размерности \( n \) над полем комплексных чисел.
• В 1960-х годах советский математик Владимир Марков доказал, что циркулянтные матрицы являются единственными матрицами, которые коммутируют с матрицей циклического сдвига.

Критика и ограничения

Несмотря на широкое применение, циркулянтные матрицы имеют ограничения. Они могут моделировать только циклические (периодические) процессы. Для непериодических систем, где граничные условия не являются циклическими, использование циркулянтных матриц может приводить к краевым эффектам, требующим специальной обработки (например, дополнения нулями). Кроме того, размер матрицы должен быть фиксированным, что усложняет адаптацию к задачам с переменной размерностью.

Источники

• Гантмахер Ф. Р. «Теория матриц». — М.: Наука, 1967.
• Воеводин В. В., Кузнецов Ю. А. «Матрицы и вычисления». — М.: Наука, 1984.
• Голуб Дж., Ван Лоун Ч. «Матричные вычисления». — М.: Мир, 1999.
• Дэвис П. «Циркулянтные матрицы». — М.: Мир, 1982.
• Марков В. В. «О циркулянтных матрицах» // Успехи математических наук, 1960.