УказательРазделыОбозначенияАвторО проекте


§

Вспомогательная страница к разделу МАТРИЦА


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

— это квадратная матрица вида

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

Каждая строка, начиная со второй, получается сдвигом предыдущей вправо на один элемент; тот элемент, что при этом сдвиге «вываливается» за пределы матрицы, переставляется в начало строки. Называется также циркулянтом, хотя в отечественной литературе циркулянтом чаще называют определитель этой матрицы.

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

§

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

\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_{} с коэффициентами из соответствующих множеств1). Аналогичное утверждение будет справедливо и для строк коэффициентов. Но тогда оба линейных оператора могут быть описаны посредством матрицы оператора. Посмотрим, какой она имеет вид.

П

Пример. Для 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 (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 \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 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) \ .

Т

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

\{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) Хотя формально множества \mathbb Z[x] и \mathbb Q[x] не являются линейными пространствами, но мы не будем слишком ориентироваться на формализм…

2016/10/13 23:18 редактировал au