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

2026-03-24 в 16:50, admin, рубрики: канунников, линейная алгебра, преобразование фурье, циркулянты, ШАД, шад helper

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

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

$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), её определитель (который тоже называется циркулянтом), ортонормированный базис из собственных векторов, выведем отсюда простую структуру алгебры циркулянтов, а также покажем их связь с гауссовыми суммами, дискретным преобразованием Фурье и приложениями.

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

— характеристический многочлен,

— минимальный многочлен,

— спектр (множество собственных значений),

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

По теореме Гамильтона-Кэли , поэтому .

Для простоты обозначений и восприятия рассмотрим циркулянт порядка 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}.$

Чтобы устно сделать вывод, что , надо проверить, что эти матрицы линейно независимы. Но это тривиально следует из вида их линейной комбинации

$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)$

Итак, , откуда спектр прост, в частности, матрица диагонализируема.

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

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

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

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

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

, откуда, в частности,

$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).$

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

Чтобы найти собственный базис матрицы , посмотрим, как она действует на векторах, и для каждого найдём собственный вектор:

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

При получаем: ; при : , , , и т.~д.

Кроме того, поскольку матрица унитарна, то есть $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 & iend{array}right).$

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

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

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

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

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

Дискретное преобразование Фурье (DFT) — это линейное преобразование $mathbb{C}^nto 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), позволяющее сократить число операций с до . Поясним на примере . Вместо прямого вычисления

$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*}$

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

Тогда

$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) на вектор или умножения двух циркулянтов.
Именно, произведение циркулянта с первой строкой и вектор-столбца равно

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

где — покоординатное произведение.
Соответственно, произведение двух циркулянтов с первыми строками и есть циркулянт с первой строкой $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_3leftrightarrow e_{n-1},ldots$ , поэтому она сопряжена диагональной матрице

$text{diag}(underbrace{1,ldots,1}_{lceilfrac{n+1}{2}rceil},underbrace{-1,ldots,-1}_{lfloorfrac{n-1}{2}rfloor}).$

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

$text{Sp} U={underbrace{1,ldots,1}_k,underbrace{-1,ldots,-1}_{lceilfrac{n+1}{2}rceil-k},underbrace{i,ldots,i}_l,underbrace{-1,ldots,-1}_{lfloorfrac{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{ при } nequiv 0 pmod 4,\ 1 & text{ при } nequiv 1 pmod 4,\ 0 & text{ при } nequiv 2 pmod 4,\ i & text{ при } nequiv 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+bomega+comega^2)(a+bomega^2+comega), text{ где } omega=e^{2pi i/3}. ;;;; (5)$

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

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

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