Инструменты сайта


Циклическая матрица

— это квадратная матрица вида $$ \mathfrak C= \left(\begin{array}{lllll} a_1 & a_2 & a_3 & \dots & a_n \\ a_n & a_1 & a_2 & \dots & a_{n-1} \\ a_{n-1} & a_n & a_1 & \dots & a_{n-2} \\ \vdots & & \ddots & \ddots & \vdots \\ a_2 & a_3 & a_4 & \dots & a_1 \end{array} \right)=\left[ a_{j-k+1 \pmod{n}}\right]_{j,k=1}^n \ . $$ Каждая строка, начиная со второй, получается сдвигом предыдущей вправо на один элемент; тот элемент, что при этом сдвиге «вываливается» за пределы матрицы, переставляется в начало строки. Называется также циркулянтом1), хотя в отечественной литературе циркулянтом чаще называют определитель этой матрицы. Первую строку циклической матрицы $$ (a_1, a_2, a_3, \dots, a_n) $$ будем называть ее порождающей строкой.

Является частным случаем тёплицевой матрицы.

Матрица, которая получается аналогичным способом, но сдвигом каждой следующей строки влево на один элемент с переброской выпадающего элемента в конец строки, может быть получена перестановкой строк циклической матрицы: $$ \begin{array}{c} \rightarrow \\ \left( \begin{array}{cccc} a_1 & a_2 & a_3 & a_4 \\ a_4 & a_1 & a_2 & a_3 \\ a_3 & a_4 & a_1 & a_2 \\ a_2 & a_3 & a_4 & a_1 \end{array} \right) \end{array} \qquad \qquad \begin{array}{c} \leftarrow \\ \left( \begin{array}{cccc} a_1 & a_2 & a_3 & a_4 \\ a_2 & a_3 & a_4 & a_1 \\ a_3 & a_4 & a_1 & a_2 \\ a_4 & a_1 & a_2 & a_3 \end{array} \right) \end{array} $$ Такая матрица будет ганкелевой.

Циклическая матрица возникает естественным образом при описании операции циклической свёртки. Рассмотрим два полинома от переменной $ x_{} $: $$ f(x)=a_0x^{n-1}+a_1x^{n-2}+\dots+a_{n-1} \quad u \quad g(x)=b_0x^{n-1}+b_1x^{n-2}+\dots+b_{n-1} \ .$$ Их коэффициенты можно считать числами любого из множеств $ \mathbb Z_{}, \mathbb Q, \mathbb R $ или $ \mathbb C_{} $. Циклической свёрткой полиномов $ f_{}(x) $ и $ g_{}(x) $ называется полином $ h_{}(x)=c_0x^{n-1}+c_1x^{n-2}+\dots+c_{n-1} $, равный остатку от деления произведения $ f(x) g(x) $ на $ x^n-1 $: $$ h(x)\equiv f(x) g(x) \pmod{x^n-1} \ . $$ Это определение индуцирует определение циклической свёртки векторов: для строк коэффициентов вовлеченных полиномов свёртка определяется как $$(c_0,c_1,\dots,c_{n-1})=(a_0,a_1,\dots,a_{n-1})*(b_0,b_1,\dots,b_{n-1}) \ . $$ Зафиксируем теперь коэффициенты одного из полиномов, например, полинома $ f_{}(x) $. Тогда отображение, ставящее в соответствие полиному $ g_{} (x) $ полином $ h_{}(x) $ будет линейным оператором на линейном пространстве полиномов степеней $ \le n_{} $ с коэффициентами из соответствующих множеств2). Аналогичное утверждение будет справедливо и для строк коэффициентов. Но тогда оба линейных оператора могут быть описаны посредством матрицы оператора. Посмотрим, какой она имеет вид.

П

Пример. Для

$$ f(x)=4\,x^3-3\,x^2+x+7,\ g(x)=b_0x^{3}+b_1x^{2}+b_2x+b_3 $$ и $ n_{}=4 $ имеем: $$ f(x) g(x) \pmod{x^4-1} \equiv $$ $$ \equiv (7\,b_0+b_1-3\,b_2+4\,b_3)\,x^3+(4\,b_0+7\,b_1+b_2-3\,b_3)\,x^2+ $$ $$+(-3\,b_0+4\,b_1+7\,b_2+b_3)\,x+(b_0-3\,b_1+4\,b_2+7\,b_3) $$ и $ (c_0,c_1,c_2,c_{3})=(4,-3,1,7)*(b_0,b_1,b_2,b_3) \quad \iff $ $$ \iff \quad \left( \begin{array}{r} c_0 \\ c_1 \\ c_2 \\ c_3 \end{array} \right)= \left( \begin{array}{rrrr} 7 & 1 & -3 & 4 \\ 4 & 7 & 1 & -3 \\ -3 & 4 & 7 & 1 \\ 1 & -3 & 4 & 7 \end{array} \right) \left( \begin{array}{r} b_0 \\ b_1 \\ b_2 \\ b_3 \end{array} \right) \ . $$ Матрица оператора оказывается циклической.

Свёртка (и ее модификации) используется в ТЕОРИИ СИГНАЛОВ и в ТЕОРИИ КОДИРОВАНИЯ.

Матрица перестановки $$ C= \left(\begin{array}{lllll} 0 & 1 & 0 & \dots & 0 \\ 0& 0 & 1 & \dots & 0 \\ \vdots & & & \ddots & \vdots \\ 0 & 0 & 0 & \dots & 1 \\ 1 & 0 & 0 & \dots & 0 \end{array} \right) $$ является циклической, она называется основной циркулянтной матрицей перестановки. Степени этой матрицы также будут циклическими матрицами: $$ C^2= \left(\begin{array}{llllll} 0 & 0 & 1 & \dots & 0 & 0 \\ 0& 0 & 0 & \dots & 0 & 0 \\ \vdots & & & \ddots & & \vdots \\ 1 & 0 & 0 & \dots & 0 & 0 \\ 0 & 1 & 0 & \dots & 0 & 0 \end{array} \right) ,\dots,C^{n-1}= \left(\begin{array}{llllll} 0 & 0 & 0 & \dots & & 1 \\ 1& 0 & 0 & \dots & & 0 \\ \vdots & & & \ddots & & \vdots \\ 0 & 0 & 0 & \dots & 0 & 0 \\ 0 & 0 & 0 & \dots & 1 & 0 \end{array} \right), C^n = E , $$ где $ E_{} $ означает единичную матрицу.

Любая циклическая матрица может быть представлена в виде $$ a_1 E + a_2 C+a_3C^2+\dots+a_n C^{n-1} $$ т.е. в виде полинома от матрицы $ C_{} $.

Т

Теорема. Произведение циклических матриц коммутативно и является циклической матрицей.

Т

Теорема. Определитель циклической матрицы равен

$$ \prod_{k=0}^{n-1} g(\varepsilon_k) \quad npu \quad g(x)=a_{1}+a_2x+a_3x^2+\dots+a_nx^{n-1} \ , $$ и $$ \varepsilon_k=\cos \frac{2\,\pi k}{n} + {\mathbf i} \sin \frac{2\,\pi k}{n} $$ — корне n-й степени из единицы.

Доказательство проведем для случая $ n=4_{} $. Умножим циклическую матрицу справа на матрицу $$ \left(\begin{array}{llll} 1 & 1 & 1 & 1 \\ 1 & \varepsilon_1 & \varepsilon_2 & \varepsilon_3 \\ 1 & \varepsilon_1^2 & \varepsilon_2^2 & \varepsilon_3^2 \\ 1 & \varepsilon_1^3 & \varepsilon_2^3 & \varepsilon_3^3 \end{array} \right) \ , $$ в результате получим матрицу $$ \left(\begin{array}{llll} g(1) & g(\varepsilon_1) & g(\varepsilon_2) & g(\varepsilon_3) \\ g(1) & a_4+a_1\varepsilon_1+a_2\varepsilon_1^2+a_3\varepsilon_1^3 & * & * \\ g(1) & a_3+a_4\varepsilon_1+a_1\varepsilon_1^2+a_2\varepsilon_1^3 & * & * \\ g(1) & a_2+a_3\varepsilon_1+a_4\varepsilon_1^2+a_1\varepsilon_1^3 & * & * \end{array} \right) \ , $$ в которой элементы третьего и четвертого столбцов аналогичны элементам второго. Теперь преобразуем элементы второго столбца: $$ a_4+a_1\varepsilon_1+a_2\varepsilon_1^2+a_3\varepsilon_1^3 =\varepsilon_1(a_1+a_2\varepsilon_1+a_3\varepsilon_1^2+a_4\varepsilon_1^3)=\varepsilon_1g(\varepsilon_1) $$ поскольку $ \varepsilon_1^4=1 $. Аналогично $$ a_3+a_4\varepsilon_1+a_1\varepsilon_1^2+a_2\varepsilon_1^3 =\varepsilon_1^2g(\varepsilon_1),\ a_2+a_3\varepsilon_1+a_4\varepsilon_1^2+a_1\varepsilon_1^3=\varepsilon_1^3g(\varepsilon_1) \ . $$ Таким образом, произведение матриц равно $$ \left(\begin{array}{llll} g(1) & g(\varepsilon_1) & g(\varepsilon_2) & g(\varepsilon_3) \\ g(1) & \varepsilon_1g(\varepsilon_1) & \varepsilon_2g(\varepsilon_2) & \varepsilon_3g(\varepsilon_3) \\ g(1) & \varepsilon_1^2g(\varepsilon_1) & \varepsilon_2^2g(\varepsilon_2) & \varepsilon_3^2g(\varepsilon_3) \\ g(1) & \varepsilon_1^3g(\varepsilon_1) & \varepsilon_2^3g(\varepsilon_2) & \varepsilon_3^3g(\varepsilon_3) \end{array} \right) \ . $$ Вычислим определитель произведения матриц. Согласно теореме Бине-Коши, получаем равенство: $$ \left|\begin{array}{llll} a_1 & a_2 & a_3 & a_4 \\ a_4 & a_1 & a_2 & a_3 \\ a_3 & a_4 & a_1 & a_{2} \\ a_2 & a_3 & a_4 & a_1 \end{array} \right|\cdot \left|\begin{array}{llll} 1 & 1 & 1 & 1 \\ 1 & \varepsilon_1 & \varepsilon_2 & \varepsilon_3 \\ 1 & \varepsilon_1^2 & \varepsilon_2^2 & \varepsilon_3^2 \\ 1 & \varepsilon_1^3 & \varepsilon_2^3 & \varepsilon_3^3 \end{array} \right| = \left|\begin{array}{lrrr} g(1) & g(\varepsilon_1) & g(\varepsilon_2) & g(\varepsilon_3) \\ g(1) & \varepsilon_1g(\varepsilon_1) & \varepsilon_2g(\varepsilon_2) & \varepsilon_3g(\varepsilon_3) \\ g(1) & \varepsilon_1^2g(\varepsilon_1) & \varepsilon_2^2g(\varepsilon_2) & \varepsilon_3^2g(\varepsilon_3) \\ g(1) & \varepsilon_1^3g(\varepsilon_1) & \varepsilon_2^3g(\varepsilon_2) & \varepsilon_3^3g(\varepsilon_3) \end{array} \right| \ . $$ В определителе справа выносим общие множители столбцов: $$ \left|\begin{array}{llll} a_1 & a_2 & a_3 & a_4 \\ a_4 & a_1 & a_2 & a_3 \\ a_3 & a_4 & a_1 & a_{2} \\ a_2 & a_3 & a_4 & a_1 \end{array} \right|\cdot \left|\begin{array}{llll} 1 & 1 & 1 & 1 \\ 1 & \varepsilon_1 & \varepsilon_2 & \varepsilon_3 \\ 1 & \varepsilon_1^2 & \varepsilon_2^2 & \varepsilon_3^2 \\ 1 & \varepsilon_1^3 & \varepsilon_2^3 & \varepsilon_3^3 \end{array} \right| =g(1) g(\varepsilon_1) g(\varepsilon_2) g(\varepsilon_3) \left|\begin{array}{llll} 1 & 1 & 1 & 1 \\ 1 & \varepsilon_1 & \varepsilon_2 & \varepsilon_3 \\ 1 & \varepsilon_1^2 & \varepsilon_2^2 & \varepsilon_3^2 \\ 1 & \varepsilon_1^3 & \varepsilon_2^3 & \varepsilon_3^3 \end{array} \right| \ . $$ В результате и получаем доказываемое. То, что определитель $$ \left|\begin{array}{llll} 1 & 1 & 1 & 1 \\ 1 & \varepsilon_1 & \varepsilon_2 & \varepsilon_3 \\ 1 & \varepsilon_1^2 & \varepsilon_2^2 & \varepsilon_3^2 \\ 1 & \varepsilon_1^3 & \varepsilon_2^3 & \varepsilon_3^3 \end{array} \right| $$ отличен от нуля следует из того, что он является определителем Вандермонда.

Результат теоремы становится вообще очевидным, если перевести его на язык результантов. Дело в том, что циклическую матрицу можно рассматривать как матрицу из представления результанта полиномов $ x^n-1 $ и $ a_{1}+a_2x+a_3x^2+\dots+a_nx^{n-1} $ в форме Безу. В самом деле, вторая строчка этой матрицы состоит из коэффициентов остатка $ g_1(x) $ от деления полинома $ x\cdot g(x) $ на $ x^n-1 $: $$a_{1}x+a_2x^2+a_3x^3+\dots+a_{n-1}x^{n-1}+a_nx^{n}\equiv $$ $$ \equiv a_{1}x+a_2x^2+a_3x^3+\dots+a_{n-1}x^{n-1}+a_n(x^{n}-1+1)\equiv $$ $$ \equiv \underbrace{a_n+a_{1}x+a_2x^2+a_3x^3+\dots+a_{n-1}x^{n-1}}_{g_{_1}(x)}+a_n(x^{n}-1) \ . $$ Формально, после умножения $ g_{}(x) $ на $ x_{} $ остаток от деления на $ x^n-1 $ может быть получен заменой $ x^{n} \to 1_{} $. Далее, остаток $ g_{2}(x) $ от деления полинома $ x^2 \cdot g(x) $ на $ x^n-1 $ совпадает с остатком от деления полинома $ x\cdot g_1(x) $ на $ x^n-1 $ и т.д. Матрица, составленная из коэффициентов остатков $ \{g_{k}(x) \}_{k=0}^{n-1} $ и будет иметь определителем результант $$ \mathcal R(x^n-1, a_{1}+a_2x+a_3x^2+\dots+a_nx^{n-1}) \, ,$$ величина которого равна произведению значений второго полинома на корнях первого. Для полного соответствия результата теоремы представлению результанта в форме Безу, требуется еще переставить столбцы матрицы $ \mathfrak C_{} $ — коэффициенты остатков записываются в матрице Безу $ B_{} $ по убыванию степеней. Так что, формально, $$ \det \mathfrak C=(-1)^{n(n-1)/2} \det B \ . $$
Попарным перемножением сомножителей в выражении для циклического определителя, можно представить его в «вещественном виде» — т.е. избавиться от мнимой единицы: $$ \left|\begin{array}{llll} a_1 & a_2 & a_3 & a_4 \\ a_4 & a_1 & a_2 & a_3 \\ a_3 & a_4 & a_1 & a_{2} \\ a_2 & a_3 & a_4 & a_1 \end{array} \right|= $$ $$ =(a_1+a_2+a_3+a_4)(a_1-a_2+a_3-a_4)(a_1^2+a_2^2+a_3^2+a_4^2-2\,a_1a_3-2\,a_2a_4) \ . $$
Т

Теорема. Характеристический полином циклической матрицы, с точностью до знака, равен

$$ \mathcal R_x(x^n-1,z-g(x)) \, . $$ Здесь $ \mathcal R_x $ — результант указанных полиномов, рассматриваемых относительно переменной $ x $. Спектр циклической матрицы совпадает с набором чисел $$ \{g(1),g(\varepsilon_1), \dots, g(\varepsilon_{n-1}) \} \ .$$

Доказательство следует из того факта, что характеристическая матрица циклической матрицы $$ \left(\begin{array}{ccccc} a_1-\lambda & a_2 & a_3 & \dots & a_n \\ a_n & a_1-\lambda & a_2 & \dots & a_{n-1} \\ a_{n-1} & a_n & a_1-\lambda & \dots & a_{n-2} \\ \vdots & & & & \vdots \\ a_2 & a_3 & a_4 & \dots & a_1-\lambda \end{array} \right) $$ сама является циклической матрицей — и можно применить предыдущую теорему.

=>

Вектор

$$ \left[1,\varepsilon_j,\varepsilon_j^2,\dots,\varepsilon_j^{n-1} \right]^{\top} \in \mathbb C^n $$ является собственным вектором циклической матрицы, соответствующим собственному числу $ f(\varepsilon_j) $. Иными словами, собственными векторами произвольной циклической матрицы являются столбцы матрицы дискретного преобразования Фурье.

Задачи

1)
(англ.) circulant matrix
2)
Хотя формально множества $ \mathbb Z[x] $ и $ \mathbb Q[x] $ не являются линейными пространствами, но мы не будем слишком ориентироваться на формализм…
algebra2/cyclic.txt · Последние изменения: 2021/12/08 11:49 — au