Просто о циркулянтах и их связи с дискретным преобразованием Фурье / Хабр

Автор статьи: Канунников Андрей, к. ф.-м. н., преподаватель ШАДХелпер.

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

$C(a_0,\ldots,a_{n-1})=\begin{pmatrix} a_0 & a_1 & a_2 & \ldots & a_{n-2} & a_{n-1} \\ a_{n-1} & a_0 & a_1 & \ldots & a_{n-3} & a_{n-2} \\ a_{n-2} & a_{n-1} & a_0 & \ldots & a_{n-4} & a_{n-3} \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ a_2 & a_3 & a_4 & \ldots & a_0 & a_1 \\ a_1 & a_2 & a_3 & \ldots & a_{n-1} & a_0 \end{pmatrix}. \;\;\;\;\; (1)$

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

Договоримся об обозначениях. Все матрицы будем рассматривать над полем $\mathbb{C}$ комплексных чисел. Для матрицы $A\in \text{M}_n(\mathbb{C})$ будем использовать обозначения:

$\bullet$ $\chi_A(t)=|tE-A|$ — характеристический многочлен,

$\bullet$ $\mu_A(t)$ — минимальный многочлен,

$\bullet$ $\text{Sp}(A)$ — спектр (множество собственных значений),

$\bullet$ $A^*=\overline{A}^\top$ — эрмитова сопряжённая матрица.

По теореме Гамильтона-Кэли $\chi_A(A)=0$ , поэтому $\mu_A(t)\mid \chi_A(t)$ .

Для простоты обозначений и восприятия рассмотрим циркулянт порядка 4. Частным случаем циркулянта является матрица циклической перестановки и её степени:

$M=\begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{pmatrix}, M^2=\begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix}, M^3=\begin{pmatrix} 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ \end{pmatrix}, M^4=E=\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}.$

Чтобы устно сделать вывод, что $\mu_M(t)=t^4-1$ , надо проверить, что эти матрицы линейно независимы. Но это тривиально следует из вида их линейной комбинации

$aE+bM+cM^2+dM^3=\begin{pmatrix} a & b & c & d \\ d & a & b & c \\ c & d & a & b \\ b & c & d & a \end{pmatrix}=C(a,b,c,d). \;\;\;\; (2)$

Итак, $\mu_M(t)=t^4-1=\chi_M(t)$ , откуда спектр $\text{Sp}(M)=\sqrt[4]{1}=\{\pm 1,\pm i\}$ прост, в частности, матрица диагонализируема.

Попутно мы обнаружили, что любой циркулянт является многочленом от матрицы , точнее,

$C(a,b,c,d)=f(M), \text{ где } f(t)=a+bt+ct^2+dt^3.$

Говорят, что многочлен ассоциирован с циркулянтом .

Отсюда немедленно получаем ряд следствий.

$\bullet$ Произведение циркулянтов снова цирулянт и не зависит от порядка множителей: , где . Таким образом, циркулянты образуют коммутативную подалгебру в алгебре матриц.

$\bullet$ $\text{Sp} C(a,b,c,d)=\{f(\pm 1),f(\pm i)\}$ , откуда, в частности,

$\begin{vmatrix} a & b & c & d \\ d & a & b & c \\ c & d & a & b \\ b & c & d & a \end{vmatrix}=(a+b+c+d)(a-b+c-d)(a+bi-c-di)(a-bi-c+di).$

$\bullet$ Все циркулянты диагонализируемы в одном и том же базисе, определённом однозначно с точностью до умножения базисных векторов на скаляры. Тем самым, алгебра циркулянтов сопряжена алгебре диагональных матриц, изоморфной, в свою очередь прямому произведению $\mathbb{C}^4$ (с покомпонентными операциями).

Чтобы найти собственный базис матрицы , посмотрим, как она действует на векторах, и для каждого $\lambda\in \text{Sp} M$ найдём собственный вектор:

$\begin{pmatrix} p\\q\\r\\s \end{pmatrix} \overset{M}{\longmapsto} \begin{pmatrix} q\\r\\s\\p \end{pmatrix}=\lambda\begin{pmatrix} p\\q\\r\\s \end{pmatrix}.$

При $\lambda=1$ получаем: ; при $\lambda=i$ : , , , и т.~д.

Кроме того, поскольку матрица унитарна, то есть $M^*=M^{-1}$ , то она диагонализируема в ортонормированном базисе (это характеристическое свойство так называемых нормальных матриц — матриц, коммутирующих со своими эрмитовыми сопряжёнными). То есть найденные собственные векторы ортогональны относительно эрмитова скалярного произведения в $\mathbb{C}^n$ :

$(X,Y)=X^\top Y=\overline{x_1}y_1+\ldots+\overline{x_n}y_n.$

Нормируя их, мы получим ортонормированный базис. Записав его по столбцам матрицы , получим

$\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & i & 0 & 0 \\ 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & -i \end{pmatrix}=U^{-1}\begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{pmatrix}U, \text{ где } U=\dfrac{1}{2} \left(\begin{array}{rrrr} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i\end{array}\right).$

Если отбросить нормирующий множитель $\dfrac 12$ , получится матрица дискретного преобразования Фурье. Она переводит вектор первой строки циркулянта (2) в вектор его собственных значений:

$\left(\begin{array}{rrrr} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i\end{array}\right)\begin{pmatrix} a \\ b\\c\\d\end{pmatrix}=\begin{pmatrix} a+b+c+d\\a+bi-c-di\\a-b+c-d\\a-bi-c+di\end{pmatrix}.$

Всё сказанное обобщается на циркулянты (1) любого порядка . Спектр соответствующей матрицы состоит из всех корней степени из единицы,

$\text{Sp} M=\sqrt[n]{1}=\{1,\omega,\ldots,\omega^{n-1}\}, \text{ где } \omega=e^{2\pi i/n}. \;\;\;\; (3)$

Алгебра циркулянтов сопряжена алгебре диагональных матриц, изоморфной, в свою очередь, алгебре $\mathbb{C}^n$ с покоординатными операциями, а также алгебре $\mathbb{C}[t]/(t^n-1)$ : операции с циркулянтами (сложение, умножение, умножение на скаляры) соответствуют операциями над их ассоциированными многочленами по модулю .

Дискретное преобразование Фурье (DFT) — это линейное преобразование $\mathbb{C}^n\to \mathbb{C}^n$ с матрицей

$F=\begin{pmatrix} 1 & 1 & 1 & \ldots & 1 & 1 \\ 1 & \omega & \omega^2 & \ldots & \omega^{n-2} & \omega^{n-1}\\ 1 & \omega^2 & \omega^4 & \ldots & \omega^{2(n-2)} & \omega^{2(n-1)}\\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ 1 & \omega^{n-2} & \omega^{2(n-2)} & \ldots & \omega^{(n-2)^2} & \omega^{(n-2)(n-1)} \\ 1 & \omega^{n-1} & \omega^{2(n-1)} & \ldots & \omega^{(n-2)(n-1)} & \omega^{(n-1)^2} \end{pmatrix}.$

Оно переводит вектор $(a_0,\ldots,a_{n-1})$ коэффициентов многочлена $f(t)=a_0+a_1t+\ldots+a_{n-1}t^{n-1}$ в вектор $(f(1),f(\omega),\ldots,f(\omega^{n-1}))$ его значений на корнях из единицы (3). Пр этом для экономного вычисления применяется быстрое преобразование Фурье (FFT), позволяющее сократить число операций с до $O(n\log n)$ . Поясним на примере . Вместо прямого вычисления

$\begin{align*} f(1)&=a+b+c+d,\\ f(i)&=a+bi-c-di,\\f(-1)&=a-b+c-d,\\f(-i)&=a-bi-c+di \end{align*}$

разобьём переменные на индексы с чётными и нечётными номерами:

$E_0=a+c,\;E_1=a-c,\;O_0=b+d,\;O_1=b-d.$

Тогда

$\begin{align*} f(1)&=E_0+O_0,\\ f(i)&=E_1+iO_1,\\f(-1)&=E_0-O_0,\\f(-i)&=E_1-iO_1. \end{align*}$

Быстрое преобразование Фурье применяется для быстрого умножения циркулянта (1) на вектор или умножения двух циркулянтов.
Именно, произведение циркулянта с первой строкой $A^\top$ и вектор-столбца равно

$F^{-1}(FA \cdot FB),$

где $\cdot$ — покоординатное произведение.
Соответственно, произведение двух циркулянтов с первыми строками $A^\top$ и $B^\top$ есть циркулянт с первой строкой $F^{-1}(FA \cdot FB)^\top.$

Рассмотрим унитарную матрицу

$U=\dfrac{1}{\sqrt{n}}F.$

У неё очень интересный спектр. Как у любой унитарной матрицы, её спектр лежит на единичной окружности. Чтобы его найти, прежде всего возведём матрицу в квадрат:

$U^2=\begin{pmatrix} 1 & 0 & 0 & \ldots & 0 & 0 & 0 \\ 0 & 0 & 0 & \ldots & 0 & 0 & 1 \\ 0 & 0 & 0 & \ldots & 0 & 1 & 0 \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ 0 & 0 & 0 & \ldots & 0 & 0 & 0 \\ 0 & 0 & 1 & \ldots & 0 & 0 & 0 \\ 0 & 1 & 0 & \ldots & 0 & 0 & 0 \end{pmatrix}.$

Это симметричная матрица отражения: $e_1\mapsto e_1$ , $e_2\leftrightarrow e_n$ , $e_3\leftrightarrow e_{n-1},\ldots$ , поэтому она сопряжена диагональной матрице

$\text{diag}(\underbrace{1,\ldots,1}_{\lceil\frac{n+1}{2}\rceil},\underbrace{-1,\ldots,-1}_{\lfloor\frac{n-1}{2}\rfloor}).$

Отсюда следует, что спектр матрицы для некоторых $k,l\in \mathbb{N}_0$ имеет вид

$\text{Sp} U=\{\underbrace{1,\ldots,1}_k,\underbrace{-1,\ldots,-1}_{\lceil\frac{n+1}{2}\rceil-k},\underbrace{i,\ldots,i}_l,\underbrace{-1,\ldots,-1}_{\lfloor\frac{n-1}{2}\rfloor-l}\}.$

В общем случае определиться с кратностями собственных значений поможет знание следа

$\text{tr} U=\dfrac{1+\omega+\omega^4+\ldots+\omega^{(n-1)^2}}{\sqrt{n}}.$

В числителе стоит знаменитая квадратичная сумма Гаусса. Гаусс долго с ней мучился и в конце концов нашёл явную формулу. В терминах следа матрицы эта формула имеет вид

$\text{tr} U=\begin{cases} 1+i & \text{ при } n\equiv 0 \pmod 4,\\ 1 & \text{ при } n\equiv 1 \pmod 4,\\ 0 & \text{ при } n\equiv 2 \pmod 4,\\ i & \text{ при } n\equiv 3 \pmod 4.\end{cases}$

Следовательно,

$\text{Sp} U=\begin{cases} \{\underbrace{1,\ldots,1}_{m+1},\underbrace{-1,\ldots,-1}_{m}, \underbrace{i,\ldots,i}_{m}, \underbrace{-i,\ldots,-i}_{m-1}\} & \text{ при } n=4m,\\ \{\underbrace{1,\ldots,1}_{m+1},\underbrace{-1,\ldots,-1}_{m}, \underbrace{i,\ldots,i}_{m}, \underbrace{-i,\ldots,-i}_{m}\} & \text{ при } n=4m+1,\\ \{\underbrace{1,\ldots,1}_{m+1},\underbrace{-1,\ldots,-1}_{m+1}, \underbrace{i,\ldots,i}_{m}, \underbrace{-i,\ldots,-i}_{m}\} & \text{ при } n=4m+2,\\ \{\underbrace{1,\ldots,1}_{m+1},\underbrace{-1,\ldots,-1}_{m+1}, \underbrace{i,\ldots,i}_{m+1}, \underbrace{-i,\ldots,-i}_{m}\} & \text{ при } n=4m+3. \end{cases}$

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

$\begin{vmatrix} a & b & c \\ c & a & b \\ b & c & a \end{vmatrix}=a^3+b^3+c^3-3abc =(a+b+c)(a+b\omega+c\omega^2)(a+b\omega^2+c\omega), \text{ где } \omega=e^{2\pi i/3}. \;\;\;\; (5)$

Считая неизвестной, а и параметрами, мы сразу получаем решения уравнения

$x^3-3bcx+b^3+c^3=0. \;\;\;\ (6)$

Отметим, что корень можно угадать, исходя из формулы куба суммы

Два других корня $-b\omega-c\omega^2$ и $-b\omega^2-c\omega$ можно теперь найти по формулам Виета, а можно воспользоваться той же формулой куба сумма, умножив в ней на $\omega$ , а — на $\omega^2$ , или наоборот (при этом величины и не изменятся). Это, кстати, элементарный способ получить разложение (5).

Любое кубическое уравнение линейной заменой $x\to x-\frac A3$ сводится к уравнению вида

Чтобы свести его к уравнению (6), найдём и из системы

$\left\{\begin{aligned} &p=-3bc \\ &q=b^3+c^3\end{aligned}\right.$

и придём к формуле Кардано

$x=\sqrt[3]{-b^3}+\sqrt[3]{-c^3}=\sqrt[3]{-\frac q2+\sqrt{\frac{q^2}{4}+\frac{p^3}{27}}}+\sqrt[3]{-\frac q2-\sqrt{\frac{q^2}{4}+\frac{p^3}{27}}}, \;\;\; (7)$

Где квадратные корни принимают одно и то~же значение (любое), а кубические выбираются так, чтобы их произведение было равно $bc=-\tfrac p3$ .