==Матрица дискретного преобразования Фурье (ДПФ) == $$ F=\left[ \varepsilon_j^{k} \right]_{j,k=0}^{n-1}= \left( \begin{array}{lllll} 1 & 1 & 1 & \dots & 1 \\ 1 & \varepsilon_1 & \varepsilon_1^2 & \dots & \varepsilon_1^{n-1} \\ 1 & \varepsilon_2 & \varepsilon_2^2 & \dots & \varepsilon_2^{n-1} \\ 1 & \varepsilon_3 & \varepsilon_3^2 & \dots & \varepsilon_3^{n-1} \\ \vdots & & & & \vdots \\ 1 & \varepsilon_{n-1} & \varepsilon_{n-1}^{2} & \dots & \varepsilon_{n-1}^{n-1} \end{array} \right)_{n\times n} \quad npu \quad \varepsilon_j = \cos \frac{2 \pi j}{n} + {\mathbf i} \, \sin \frac{2 \pi j}{n} $$ --- ((:complex_num#корни_из_единицы корне n-й степени из 1)). Основываясь на свойстве $ \varepsilon_j=\varepsilon_1^j $, матрицу часто записывают в эквивалентном виде $$ F= \left[ \varepsilon^{jk} \right]_{j,k=0}^{n-1}= \left( \begin{array}{lllll} 1 & 1 & 1 & \dots & 1 \\ 1 & \varepsilon & \varepsilon^2 & \dots & \varepsilon^{n-1} \\ 1 & \varepsilon^2 & \varepsilon^4 & \dots & \varepsilon^{2(n-1)} \\ 1 & \varepsilon^3 & \varepsilon^6 & \dots & \varepsilon^{3(n-1)} \\ \vdots & & & & \vdots \\ 1 & \varepsilon^{n-1} & \varepsilon^{2(n-1)} & \dots & \varepsilon^{(n-1)^2} \end{array} \right)_{n\times n} \quad npu \quad \varepsilon = \cos \frac{2 \pi}{n} + {\mathbf i} \, \sin \frac{2 \pi}{n} \ . $$ !!П!! **Пример.** При $ n=4 $ матрица **ДПФ**: $$ F= \left( \begin{array}{rrrr} 1 & 1 & 1 & 1\\ 1 & \mathbf i & -1 & - \mathbf i \\ 1 & -1 & 1 & -1 \\ 1 & -\mathbf i & -1 & \mathbf i \end{array} \right) \ . $$ При $ n=8 $ ☞ ((:algebra2:fourier:F8 ЗДЕСЬ)). ♦ Матрица **ДПФ** является ((:algebra2#симметричная симметричной)): $ F=F^{\top} $; она является частным случаем ((algebra2:vander матрицы Вандермонда)). !!Т!! **Теорема 1.** $$ \det F = \left\{ \begin{array}{ll} n^{n/2} {\mathbf i}^{n(n-1)/2+1} & \mbox{ при }\ n_{} - \mbox{ четном }, \\ n^{n/2} {\mathbf i}^{n(n-1)/2} & \mbox{ при }\ n_{} - \mbox{ нечетном }. \end{array} \right. $$ **Доказательство.** С одной стороны, возведем матрицу $ F_{} $ в квадрат, результатом будет ((:algebra2:hankel ганкелева матрица)) $$ F^2= \left(\begin{array}{lllll} h_0 & h_1 & h_2 & \dots & h_{n-1} \\ h_1 & h_2 & h_3 & \dots & h_n \\ h_2 & h_3 & h_4 & \dots & h_{n+1} \\ \vdots & & & & \vdots \\ h_{n-1} & h_{n} & h_{n+1} & \dots & h_{2n-2} \end{array} \right) $$ при $$ h_j=1+\varepsilon_1^j+\varepsilon_2^j+\dots+\varepsilon_{n-1}^j=1+\varepsilon_j^1+\varepsilon_j^2+\dots+\varepsilon_j^{n-1}\ .$$ Теперь воспользуемся результатом, полученным ☞ ((:complex_num:vspom3 ЗДЕСЬ)): $$ h_j= \left\{ \begin{array}{ccc} n & npu & \varepsilon_j=1 , \\ 0 & npu & \varepsilon_j\ne 1 . \end{array} \right. $$ Таким образом, $$ F^2= \left(\begin{array}{cccccc} n & 0 & 0 & \dots & 0 & 0 \\ 0 & 0 & 0 & \dots & 0 & n \\ 0 & 0 & 0 & \dots & n & 0 \\ \vdots & & & & & \vdots \\ 0 & n & 0 & \dots & 0 & 0 \end{array} \right) $$ и, на основании ((:algebra2:dets#определение определения определителя)), имеем $$ \det F^2 =(-1)^{(n-1)(n-2)/2}n^n \quad \Rightarrow \quad \det F \in \{\pm \mathbf i ^{(n-1)(n-2)/2} n^{n/2} \} . $$ Осталось только выбрать из двух полученных чисел одно истинное. Для этого рассмотрим $ \det F $ как определитель Вандермонда: $$ \det F = \prod_{0\le j 0 $. Поэтому $$ | \det F | = \prod_{0\le j ♦ !!Т!! **Теорема 2.** //Матрица обратная к матрице// **ДПФ** //вычисляется по формуле//: $$ F^{-1}=\frac{1}{n}\left[ \varepsilon_{-j}^{k} \right]_{j,k=0}^{n-1}= \left( \begin{array}{lllll} 1 & 1 & 1 & \dots & 1 \\ 1 & \varepsilon_{-1} & \varepsilon_{-1}^2 & \dots & \varepsilon_{-1}^{n-1} \\ 1 & \varepsilon_{-2} & \varepsilon_{-2}^2 & \dots & \varepsilon_{-2}^{n-1} \\ 1 & \varepsilon_{-3} & \varepsilon_{-3}^2 & \dots & \varepsilon_{-3}^{n-1} \\ \vdots & & & & \vdots \\ 1 & \varepsilon_{-(n-1)} & \varepsilon_{-(n-1)}^{2} & \dots & \varepsilon_{-(n-1)}^{n-1} \end{array} \right) \quad npu \quad \varepsilon_{-j} = \cos \frac{2 \pi j}{n} - {\mathbf i} \, \sin \frac{2 \pi j}{n} $$ Основываясь на свойстве $ \varepsilon_{-j}=\varepsilon_{-1}^j=\overline{\varepsilon_1}^j $ (см. ☞ ((:complex_num#корни_из_единицы ЗДЕСЬ)) ), матрицу часто записывают в эквивалентном виде $$ F^{-1}= \frac{1}{n}\left[ \overline{\varepsilon}^{jk} \right]_{j,k=0}^{n-1}=\frac{1}{n} \left( \begin{array}{lllll} 1 & 1 & 1 & \dots & 1 \\ 1 & \overline{\varepsilon} & \overline{\varepsilon}^2 & \dots & \overline{\varepsilon}^{n-1} \\ 1 & \overline{\varepsilon}^2 & \overline{\varepsilon}^4 & \dots & \overline{\varepsilon}^{2(n-1)} \\ 1 & \overline{\varepsilon}^3 & \overline{\varepsilon}^6 & \dots & \overline{\varepsilon}^{3(n-1)} \\ \vdots & & & & \vdots \\ 1 & \overline{\varepsilon}^{n-1} & \overline{\varepsilon}^{2(n-1)} & \dots & \overline{\varepsilon}^{(n-1)^2} \end{array} \right) \quad npu \quad \overline{\varepsilon} = \cos \frac{2 \pi}{n} - {\mathbf i} \, \sin \frac{2 \pi}{n} \ . $$ Образно говоря: обращение матрицы $ F_{} $ сводится к сопряжению каждого ее элемента и делению его на порядок матрицы. **Доказательство** сводится к проверке умножением: $$ \left( \begin{array}{lllll} 1 & 1 & 1 & \dots & 1 \\ 1 & \varepsilon_{-1} & \varepsilon_{-1}^2 & \dots & \varepsilon_{-1}^{n-1} \\ 1 & \varepsilon_{-2} & \varepsilon_{-2}^2 & \dots & \varepsilon_{-2}^{n-1} \\ 1 & \varepsilon_{-3} & \varepsilon_{-3}^2 & \dots & \varepsilon_{-3}^{n-1} \\ \vdots & & & & \vdots \\ 1 & \varepsilon_{-(n-1)} & \varepsilon_{-(n-1)}^{2} & \dots & \varepsilon_{-(n-1)}^{n-1} \end{array} \right)\cdot \left( \begin{array}{lllll} 1 & 1 & 1 & \dots & 1 \\ 1 & \varepsilon_1 & \varepsilon_1^2 & \dots & \varepsilon_1^{n-1} \\ 1 & \varepsilon_2 & \varepsilon_2^2 & \dots & \varepsilon_2^{n-1} \\ 1 & \varepsilon_3 & \varepsilon_3^2 & \dots & \varepsilon_3^{n-1} \\ \vdots & & & & \vdots \\ 1 & \varepsilon_{n-1} & \varepsilon_{n-1}^{2} & \dots & \varepsilon_{n-1}^{n-1} \end{array} \right)= $$ (в следующей матрице везде суммирование идет по $ j \in \{0,1,\dots,n-1\} $, и все эти суммы равны нулю (см. ☞ ((:complex_num:vspom3 ЗДЕСЬ)) ): $$ =\left( \begin{array}{lllll} n & \sum \varepsilon_j & \sum \varepsilon_j^2 & \dots & \sum \varepsilon_j^{n-1} \\ \sum \varepsilon_{-j} & n & \sum \varepsilon_j & \dots & \sum \varepsilon_j^{n-2} \\ \sum \varepsilon_{-j}^2 & \sum \varepsilon_{-j} & n & \dots & \sum \varepsilon_j^{n-3} \\ \sum \varepsilon_{-j}^3 & \sum \varepsilon_{-j}^2 & \sum \varepsilon_{-j} & \dots & \sum \varepsilon_j^{n-4} \\ \vdots & & & & \vdots \\ \sum \varepsilon_{-j}^{n-1} & \sum \varepsilon_{-j}^{n-2} & \sum \varepsilon_{-j}^{n-3} & \dots & n \end{array} \right) = \left( \begin{array}{lllll} n & 0 & 0 & \dots & 0 \\ 0 & n & 0 & \dots & 0 \\ 0 & 0 & n & \dots & 0 \\ \vdots & & & \ddots & \vdots \\ 0 & 0 & 0 & \dots & n \end{array} \right) \ . $$ ♦ !!П!! **Пример.** При $ n=4 $: $$ F^{-1}=\frac{1}{4} \left( \begin{array}{rrrr} 1 & 1 & 1 & 1\\ 1 & -\mathbf i & -1 & \mathbf i \\ 1 & -1 & 1 & -1 \\ 1 & \mathbf i & -1 & -\mathbf i \end{array} \right) \ ; $$ при $ n=8 $ ☞ ((:algebra2:fourier:F8 ЗДЕСЬ)). ♦ Видим, что обращение матрицы $ F_{} $ фактически сводится к перестановке ее строк; это хорошо заметно на матрице 8-го порядка. Подозрение, что матрица $ F^{-1} $ должна быть очень похожа на матрицу $ F_{} $ следовало из первого этапа доказательства теоремы 1: фактически $ F^2 $ уже была близка к диагональной матрице. Алгоритм перестановки строк матрицы $ F_{} $, приводящий к ее обращению, следует из правила $ \overline{\varepsilon_j}=\varepsilon_{-j}=\varepsilon_{n-j} $: вторая строка переставляется местами с последней, третья --- с предпоследней, и т.д. !!Т!! **Теорема 3.** //((:algebra2:charpoly#собственное_число Собственные числа)) матрицы// $ F_{} $ //находятся во множестве// $ \{\pm\sqrt{n}, \pm\mathbf i\sqrt{n} \} $. //Кратности определяются из следующей таблицы//: $$ \begin{array}{c|c|c|c|c} n & \lambda= \sqrt{n} & \lambda= - \sqrt{n} & \lambda= -\mathbf i \sqrt{n} & \lambda= \mathbf i \sqrt{n} \\ \hline 4m & m+1 & m & m & m-1 \\ 4m+1 & m+1 & m & m & m \\ 4m+2 & m+1 & m+1 & m & m \\ 4m+3 & m+1 & m+1 & m+1 & m \\ \end{array} $$ !!П!! **Пример.** Характеристический полином матрицы $ F_{} $ при $ n_{}=4 $: $$ \det (F-\lambda E) \equiv (\lambda - 2\, \mathbf i)(\lambda+2)(\lambda-2)^2 \ ; $$ при $ n_{}=8 $ ☞ ((:algebra2:fourier:F8 ЗДЕСЬ)). ♦ {{users:au:scriber.jpg |}} \\ \\ \\ Статья не закончена! ==Источник== С небольшими модификациями взято из: **Проскуряков И.В.** //Сборник задач по линейной алгебре.// М.Наука. 1974