==Циклическая матрица== --- это квадратная матрица вида $$ \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 \ . $$ Каждая строка, начиная со второй, получается сдвигом предыдущей вправо на один элемент; тот элемент, что при этом сдвиге "вываливается" за пределы матрицы, переставляется в начало строки. Называется также **циркулянтом**[[(//англ.//) circulant matrix]], хотя в отечественной литературе циркулянтом чаще называют определитель этой матрицы. Первую строку циклической матрицы $$ (a_1, a_2, a_3, \dots, a_n) $$ будем называть ее **порождающей строкой**. Является частным случаем ((:algebra2#тёплицева тёплицевой матрицы)). Матрица, которая получается аналогичным способом, но сдвигом каждой следующей строки __влево__ на один элемент с переброской выпадающего элемента в конец строки, может быть получена перестановкой строк циклической матрицы: $$ \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} $$ Такая матрица будет ((:algebra2:hankel ганкелевой)). Циклическая матрица возникает естественным образом при описании операции циклической свёртки. Рассмотрим два полинома от переменной $ 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) $ будет ((:mapping:operator#оператор линейным оператором)) на линейном пространстве полиномов степеней $ \le n_{} $ с коэффициентами из соответствующих множеств[[Хотя формально множества $ \mathbb Z[x] $ и $ \mathbb Q[x] $ не являются линейными пространствами, но мы не будем слишком ориентироваться на формализм...]]. Аналогичное утверждение будет справедливо и для строк коэффициентов. Но тогда оба линейных оператора могут быть описаны посредством ((:mapping:operator#матрица_оператора матрицы оператора)). Посмотрим, какой она имеет вид. !!П!! **Пример.** Для $$ 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) \ . $$ Матрица оператора оказывается циклической. ♦ Свёртка (и ее модификации) используется в ☞ ((:signal#линейные_стационарные_системы ТЕОРИИ СИГНАЛОВ)) и в ☞ ((:codes:cyclic#свёртка ТЕОРИИ КОДИРОВАНИЯ)). Матрица ((:algebra2#элементарных_преобразований перестановки)) $$ 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) $$ является циклической, она называется **основной циркулянтной матрицей перестановки**. ((:algebra2#полином_от_матрицы_и_матричный_полином Степени)) этой матрицы также будут циклическими матрицами: $$ 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_{} $ означает ((:algebra2#единичная единичную)) матрицу. Любая циклическая матрица может быть представлена в виде $$ a_1 E + a_2 C+a_3C^2+\dots+a_n C^{n-1} $$ т.е. в виде ((:algebra2#полином_от_матрицы_и_матричный_полином полинома от матрицы)) $ 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} $$ --- //((:complex_num#корни_из_единицы корне 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) \ . $$ Вычислим определитель произведения матриц. Согласно ((:algebra2:dets#теорема_бине_-_коши теореме Бине-Коши)), получаем равенство: $$ \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| $$ отличен от нуля следует из того, что он является ((:algebra2:vander#opredelitel определителем Вандермонда)). ♦ Результат теоремы становится вообще очевидным, если перевести его на язык ((:dets:resultant результантов)). Дело в том, что циклическую матрицу можно рассматривать как матрицу из представления результанта полиномов $ x^n-1 $ и $ a_{1}+a_2x+a_3x^2+\dots+a_nx^{n-1} $ ((:dets:resultant#результант_в_форме_безу в форме Безу)). В самом деле, вторая строчка этой матрицы состоит из коэффициентов остатка $ 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}) \, ,$$ величина которого ((:dets:resultant#результант_в_форме_сильвестра равна произведению значений второго полинома на корнях первого)). Для полного соответствия результата теоремы представлению результанта в форме Безу, требуется еще переставить столбцы матрицы $ \mathfrak C_{} $ --- коэффициенты остатков записываются в ((:dets:resultant#результант_в_форме_безу матрице Безу)) $ 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 $ --- //((:dets/resultant#rezultant_v_forme_silvestra результант)) указанных полиномов, рассматриваемых относительно переменной// $ x $. //((:algebra2:charpoly#собственное_число Спектр)) циклической матрицы совпадает с набором чисел// $$ \{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 $$ является ((:algebra2:charpoly#собственный_вектор собственным вектором)) циклической матрицы, соответствующим собственному числу $ f(\varepsilon_j) $. Иными словами, собственными векторами произвольной циклической матрицы являются столбцы ((:algebra2:fourier матрицы дискретного преобразования Фурье)). ==Задачи== ☞ ((:algebra2:cyclic:problems ЗДЕСЬ))