Пусть задан набор чисел (элементов поля) $ \{x_1,x_2,\dots,x_n \} $, не обязательно различных. Матрицу вида $$ \mathbf V_{m,n}(x_1, x_2,\ldots,x_n) = \left( \begin{array}{llll} 1& 1& \ldots& 1\\ x_1& x_2& \ldots& x_n\\ x_1^2& x_2^2& \ldots& x_n^2\\ \vdots& \vdots& & \vdots \\ x_1^{m-1}& x_2^{m-1}& \ldots& x_n^{m-1} \end{array} \right)_{m\times n} $$ или ей транспонированную будем называть $ m \times n $-матрицей Вандермонда.

Частным случаем квадратной матрицы Вандермонда является матрица дискретного преобразования Фурье: $$ 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} $$ — корне 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\times n $-матрицы Вандермонда называется определителем Вандермонда. При $ n=1 $ он, очевидно, равен $ 1 $. При $ n>1 $ будем обозначать его $ V(x_1,\dots,x_n) $: $$ V(x_1,\dots,x_n)= \left| \begin{array}{llll} 1& 1& \ldots& 1\\ x_1& x_2& \ldots& x_n\\ x_1^2& x_2^2& \ldots& x_n^2\\ \vdots& \vdots& & \vdots \\ x_1^{n-1}& x_2^{n-1}& \ldots& x_n^{n-1} \end{array} \right|= \left| \begin{array}{llll} 1& x_1& \ldots& x_1^{n-1}\\ 1& x_2& \ldots& x_2^{n-1}\\ \vdots& \vdots& & \vdots \\ 1 & x_n& \ldots & x_n^{n-1} \end{array} \right| \, . $$ Очевидно, этот определитель является полиномом от переменных $ x_1,\dots,x_n $: $$ V(x_1,x_2)=x_2-x_1,\ V(x_1,x_2,x_3)= x_1^2x_3-x_1x_3^2+x_1x_2^2-x_1^2x_2+x_2x_3^2-x_2^2x_3, \dots , $$ причем полиномом однородным степени $ n(n-1)/2 $ и с целыми коэффициентами. Этот полином оказывается приводимым над $ \mathbb Z $.

Теорема. Имеет место тождество

$$ V(x_1,\dots,x_n) \equiv \prod_{1\le j < k \le n} (x_k-x_j)\ . $$

Доказательство ☞ ЗДЕСЬ.

Определитель Вандермонда порядка $ n\ge 2 $ отличен от нуля тогда и только тогда, когда все числа $ x_1,x_2,\dots,x_n $ различны.

Пример.

$$ V(x_1,x_2,x_3)\equiv (x_2-x_1)(x_3-x_1)(x_3-x_2) \ ; $$ $$ V(x_1,x_2,x_3,x_4) \equiv $$ $$ \equiv (x_2-x_1)(x_3-x_1)(x_3-x_2)(x_4-x_1)(x_4-x_2)(x_4-x_3) \ . $$ ♦

Определитель матрицы дискретного преобразования Фурье вычисляется по формулам:

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

Доказательство ☞ ЗДЕСЬ.

Матрица Вандермонда естественным образом возникает в задаче полиномиальной интерполяции.

Задача. Построить полином $ y_{}=f(x) $, принимающий значения согласно следующей таблице: $$ \begin{array}{c|ccccc} x & x_1 & x_2 & \dots & x_n \\ \hline y & y_1 & y_2 &\dots & y_n \end{array} $$ Здесь числа $ \{ x_{j}, y_{j} \}_{j=1}^n $ — из $ \mathbb Q_{} $, $ \mathbb R_{} $ или $ \mathbb C_{} $, или вообще элементы произвольного поля, которое в дальнейшем будем обозначать через $ \mathbb A_{} $. $ \{ x_{j} \}_{j=1}^n $ называются узлами интерполяции; искомый полином называется интерполяционным.

Теорема. При $ x_{1},\dots,x_{n} $ различных существует единственный полином $ f(x) \in \mathbb A_{}[x] $ степени $ \le n_{}-1 $ такой, что $ f(x_{1})=y_{1},\dots,f(x_{n})=y_{n} $.

Доказательство. Коэффициенты полинома $ f(x)=A_{0}+A_1x+\dots+A_{n-1}x^{n-1} $ можно определить из системы уравнений $$ \left\{\begin{array}{ccl} A_0+A_1x_1+\dots+A_{n-1}x_1^{n-1}&=&y_1 \\ A_0+A_1x_2+\dots+A_{n-1}x_2^{n-1}&=&y_2 \\ \dots & & \dots \\ A_0+A_1x_n+\dots+A_{n-1}x_n^{n-1}&=&y_n, \end{array} \right. $$ матрица которой как раз и является матрицей Вандермонда. По теореме из предыдущего пункта ее определитель отличен от нуля. На основании теоремы Крамера система имеет единственное решение. ♦

Фактическое нахождение коэффициентов интерполяционного полинома посредством решения системы линейных уравнений по формулам Крамера достаточно громоздко. «Сходу» удается получить только выражения для $ A_0 $ и $ A_{n-1} $.

Пример. Для $ n=4 $ имеем

$$ A_0=\frac{\left| \begin{array}{clll} y_1 & x_1 & x_1^2 & x_1^3 \\ y_2 & x_2 & x_2^2 & x_2^3 \\ y_3 & x_3 & x_3^2 & x_3^3 \\ y_4 & x_4 & x_4^2 & x_4^3 \end{array} \right|}{V(x_1,x_2,x_3,x_4)}= $$ раскладываем определитель по первому столбцу:

$$ =\frac{y_1x_2x_3x_4V(x_2,x_3,x_4)-y_2x_1x_3x_4 V(x_1,x_3,x_4)+y_3x_1x_2x_4V(x_1,x_2,x_4)-y_4x_1x_2x_3V(x_1,x_2,x_3)}{V(x_1,x_2,x_3,x_4)}= $$ $$ =\frac{y_1x_2x_3x_4}{(x_1-x_2)(x_1-x_3)(x_1-x_4)}+\frac{y_2x_1x_3x_4}{(x_2-x_1)(x_2-x_3)(x_2-x_4)}+\frac{y_3x_1x_2x_4}{(x_3-x_1)(x_3-x_2)(x_3-x_4)}+ $$ $$ +\frac{y_4x_1x_2x_3}{(x_4-x_1)(x_4-x_2)(x_4-x_3)} \, . $$ $$ A_4=\frac{\left| \begin{array}{clll} 1 & x_1 & x_1^2 & y_1 \\ 1 & x_2 & x_2^2 & y_2 \\ 1 & x_3 & x_3^2 & y_3 \\ 1 & x_4 & x_4^2 & y_4 \end{array} \right|}{V(x_1,x_2,x_3,x_4)}= $$ раскладываем определитель по последнему столбцу: $$ =\frac{y_1}{(x_1-x_2)(x_1-x_3)(x_1-x_4)}+\frac{y_2}{(x_2-x_1)(x_2-x_3)(x_2-x_4)}+\frac{y_3}{(x_3-x_1)(x_3-x_2)(x_3-x_4)}+ $$ $$ +\frac{y_4}{(x_4-x_1)(x_4-x_2)(x_4-x_3)} \, . $$

♦

Однако, с помощью некоторых вспомогательных манипуляций удается свести вычисление интерполяционного полинома к определителю Вандермонда. С этой целью воспользуемся результатом упражнения 7 ☞ ЗДЕСЬ. Если $ f(x)=A_{0}+A_1x+\dots+A_{n-1}x^{n-1} $ при столбце коэффициентов, удовлетворяющем уравнению $$ \mathbf V \left[\begin{array}{l} A_0 \\ A_1 \\ \vdots \\ A_{n-1} \end{array} \right] = \left[\begin{array}{l} y_1 \\ y_2 \\ \vdots \\ y_{n} \end{array} \right] \, , $$ то $$ f(x) \equiv \left| \begin{array}{llrrrc} 1 & x_1 & x_1^2 & \dots & x_1^{n-1} & -y_1 \\ 1 & x_2 & x_2^2 & \dots & x_2^{n-1} & -y_2 \\ \vdots & \vdots & & & & \vdots \\ 1 & x_n & x_n^2 & \dots & x_n^{n-1} & -y_n \\ 1 & x & x^2 & \dots & x^{n-1} & 0 \end{array} \right| \Big/ \left| \begin{array}{lrrrr} 1 & x_1 & x_1^2 & \dots & x_1^{n-1} \\ 1 & x_2 & x_2^2 & \dots & x_2^{n-1} \\ \vdots & \vdots & & & \vdots \\ 1 & x_n & x_n^2 & \dots & x_n^{n-1} \end{array} \right| \equiv $$ Теперь разложим определитель из числителя по последнему столбцу $$ \equiv (-1)^{n-1} y_1\frac{V(x_2,\dots,x_n,{\color{RubineRed} x})}{V(x_1,x_2,\dots,x_n)}+(-1)^{n-2}y_2\frac{V(x_1,x_3,\dots,x_n,{\color{RubineRed} x})}{V(x_1,x_2,\dots,x_n)}+\dots+ y_n\frac{V(x_1,x_2,\dots,x_{n-1},{\color{RubineRed} x})}{V(x_1,x_2,\dots,x_n)} \equiv $$ и переставим строки в определителях числителей $$ \equiv y_1\frac{V({\color{RubineRed} x},x_2,\dots,x_n)}{V(x_1,x_2,\dots,x_n)}+y_2\frac{V(x_1,{\color{RubineRed} x},\dots,x_n)}{V(x_1,x_2,\dots,x_n)}+\dots+ y_n\frac{V(x_1,x_2,\dots,x_{n-1},{\color{RubineRed} x})}{V(x_1,x_2,\dots,x_n)} \, . $$ Теперь воспользуемся теоремой предыдущего пункта и сократим общие множители числителей и знаменателей. Обозначим $$ W(x) = (x-x_1)\times \dots \times (x-x_n) \, , $$ $$ W_j(x) = \frac{W(x)}{x-x_j} =(x-x_1)\times \dots \times (x-x_{j-1}) (x-x_{j+1})\times \dots \times (x-x_n) \quad npu \quad j\in \{1,\dots,n\} . $$ Тогда получаем представление интерполяционного полинома в виде: $$ f(x) \equiv \sum_{j=1}^n \frac{y_jW_j(x)}{W_j(x_j)}= $$ $$ \begin{array}{ll} = & \displaystyle y_1\frac{(x-x_2)\times \dots \times (x-x_n)}{(x_1-x_2)\times \dots \times (x_1-x_n)}+ \\ + & \displaystyle y_2\frac{(x-x_1)(x-x_3)\times \dots \times (x-x_n)}{(x_2-x_1)(x_2-x_3)\times \dots \times (x_2-x_n)}+ \\ + & \dots+ \\ + & \displaystyle y_n\frac{(x-x_1)\times \dots \times (x-x_{n-1})}{(x_n-x_1)\times \dots \times (x_n-x_{n-1})} . \end{array} $$ Это представление известно как интерполяционный полином в форме Лагранжа. Легко выводимое равенство $$ W_j(x_j)=W^{\prime}(x_j) $$ позволяет записать ту же форму в эквивалентном виде $$ f(x) \equiv \sum_{j=1}^n \frac{y_jW_j(x)}{W^{\prime}(x_j)} \, . $$ Полиномы $$ \widetilde W_j(x) = W_j(x)/W_j(x_j) \equiv W_j(x)/W^{\prime}(x_j) \quad npu \quad j \in \{1,\dots,n\} \, , $$ участвующие в этом представлении, часто называют базисными интерполяционными полиномами. Они обладает следующим свойством: $$ \widetilde W_j(x_k) = \delta_{jk} \ , $$ где $ \delta_{jk} $ — символ Кронекера. Иными словами, $ \widetilde W_j(x) $ является интерполяционным полиномом для таблицы $$ \begin{array}{c|ccccc} x & x_1 & x_2 & \dots & x_{j-1} & x_j & x_{j+1} & \dots & x_n \\ \hline y & 0 & 0 & \dots & 0 & 1 & 0 & \dots & 0 \end{array} $$

Представление интерполяционного полинома в форме Лагранжа еще не дает явных формул для коэффициентов. Для этого еще нужно разложить базисные полиномы по степеням $ x_{} $. Если это сделать: $$ {\widetilde W}_j(x)\equiv w_{j0}+w_{j1}x+\dots+ w_{j,n-1}x^{n-1} \, , $$ то мы получим возможность обращения матрицы Вандермонда.

Теорема. При условии различности всех $ x_1,x_2,\dots,x_n $ имеет место равенство

$$ \left( \begin{array}{llll} 1& 1& \ldots& 1\\ x_1& x_2& \ldots& x_n\\ x_1^2& x_2^2& \ldots& x_n^2\\ \vdots& \vdots& & \vdots \\ x_1^{n-1}& x_2^{n-1}& \ldots& x_n^{n-1} \end{array} \right)^{-1}= \left( \begin{array}{llll} w_{10}& w_{11}& \ldots& w_{1,n-1}\\ w_{20}& w_{21}& \ldots& w_{2,n-1}\\ \dots & & & \dots \\ w_{n0}& w_{n1}& \ldots& w_{n,n-1}\\ \end{array} \right) \, . $$

Доказательство может быть произведено разными способами. Самый простой заключается в формальной проверке утверждения умножением матрицы $ \left[ w_{jk} \right]_{j=1,\dots,n,k=0,\dots,n-1} $ на матрицу Вандермонда слева. В результате получаем $$ \left(\begin{array}{llll} \widetilde W_1(x_1) & \widetilde W_1(x_2) & \dots & \widetilde W_1(x_n) \\ \widetilde W_2(x_1) & \widetilde W_2(x_2) & \dots & \widetilde W_2(x_n) \\ \dots & & & \dots \\ \widetilde W_n(x_1) & \widetilde W_n(x_2) & \dots & \widetilde W_n(x_n) \end{array} \right) $$ и эта матрица является единичной на основании свойства базисных интерполяционных полиномов. ♦

Пример. Вычислить

$$ \left(\begin{array}{ccc} 1 & 1 & 1 \\ 1 & 2 & 3 \\ 1 & 4 & 9 \end{array} \right)^{-1} \, . $$

Решение. Имеем: $$ W(x)=(x-1)(x-2)(x-3) \ , $$ $$ \widetilde W_1(x)=\frac{(x-2)(x-3)}{(1-2)(1-3)} = 3 -\frac{2}{5}x+\frac{1}{2}x^2,\ $$ $$ \widetilde W_2(x)=\frac{(x-1)(x-3)}{(2-1)(2-3)} = -3 +4\,x-x^2,\ $$ $$ \widetilde W_3(x)=\frac{(x-1)(x-2)}{(3-1)(3-2)} = 1 -\frac{3}{2}x+\frac{1}{2}x^2 \, . $$

Ответ. $$ \left(\begin{array}{ccc} 3 & -5/2 & 1/2 \\ -3 & 4 & -1 \\ 1 & -3/2 & 1/2 \end{array} \right) \, . $$

Доказать, что сумма всех строк матрицы $ \mathbf V^{-1} $ равна $ [1,0,0,\dots,0] $.

Следующая задача — организовать параллелизацию вычисления коэффициентов базисных интерполяционных полиномов. С этой целью вычислим величины $$ \xi_1=\frac{1}{W^{\prime}(x_1)},\dots, \xi_n=\frac{1}{W^{\prime}(x_n)} \, . $$ и составим из них столбец $$ \Xi_0=\left[\xi_1,\dots, \xi_n\right]^{\top} \, . $$ Умножим его на столбец $$ \Lambda=\left[x_1,\dots, x_n\right]^{\top} \ , $$ причем умножение векторов рассматривается адамарово, т.е. поэлементное $$ \Xi_1= \Xi_0 \otimes \Lambda= \left[\xi_1 x_1 ,\dots, \xi_n x_n \right]^{\top} \ . $$ Продолжив процесс умножения, сгененируем последовательность $$ \Xi_0, \Xi_1=\Xi_0 \otimes \Lambda, \Xi_2=\Xi_1 \otimes \Lambda, \dots, \Xi_{n-1}=\Xi_{n-2} \otimes \Lambda, \dots, \Xi_{2n-2} = \Xi_{2n-3} \otimes \Lambda \ . $$ На основании равенств Эйлера-Лагранжа сумма элементов любого из столбцов $ \Xi_0,\dots,\Xi_{n-2} $ равна $ 0_{} $, а сумма элементов столбца $ \Xi_{n-1} $ равна $ 1 $.

Теорема[2]. Вычислим суммы элементов столбцов $ \Xi_n, \Xi_{n+1},\dots, \Xi_{2n-2} $, т.е. величины

$$ \sigma_k = \sum_{j=1}^n \frac{x_j^{n+k-1}}{W^{\prime}(x_j)} , \quad k\in \{1,\dots,n-1\} \ . $$ Столбцы матрицы $$ \mathbf V^{-1}=\left[\mathbf V_{[1]}^{-1},\mathbf V_{[2]}^{-1},\dots, \mathbf V_{[n]}^{-1} \right] $$ связаны со столбцами $ \Xi_0, \Xi_{1},\dots, \Xi_{n-1} $ следующими рекурсивными соотношениями: $$ \left\{ \begin{array}{lcl} \mathbf V_{[n]}^{-1}&=&\Xi_0, \\ \mathbf V_{[n-1]}^{-1}&=&\Xi_1-\sigma_1 \mathbf V_{[n]}^{-1}, \\ \mathbf V_{[n-2]}^{-1}&=&\Xi_2-\sigma_1 \mathbf V_{[n-1]}^{-1} - \sigma_2 \mathbf V_{[n]}^{-1}, \\ \dots & & \dots \\ \mathbf V_{[1]}^{-1}&=&\Xi_{n-1}-\sigma_1 \mathbf V_{[2]}^{-1} - \sigma_2 V_{[3]}^{-1}- \dots - \sigma_{n-1} \mathbf V_{[n]}^{-1}. \end{array} \right. $$

Доказательство. На основании равенств Эйлера-Лагранжа имеем $$ \mathbf V\cdot \mathbf V_{[n]}^{-1}=\mathbf V\cdot \Xi_0=\left[\sum_{j=1}^n\frac{ 1}{W^{\prime}(x_j)},\ \sum_{j=1}^n\frac{ x_j}{W^{\prime}(x_j)},\dots, \sum_{j=1}^n\frac{ x_j^{n-1}}{W^{\prime}(x_j)} \right]^{\top}= $$ $$ = [0,0,\dots,0,1]^{\top} \, . $$ Далее, на основании только что выведенного равенства, получаем: $$ \mathbf V\cdot \mathbf V_{[n-1]}^{-1}=V\cdot \Xi_1-\sigma_1 \mathbf V \cdot \mathbf V_{[n]}^{-1} = [0,0,\dots,1,\sigma_1]^{\top} - \sigma_1 [0,0,\dots,0,1]^{\top} = $$ $$ =[0,0,\dots,1,0]^{\top} \, . $$ Применением теперь уже двух полученных равенств, доказываем третье равенство из теоремы: $$ \mathbf V\cdot \mathbf V_{[n-2]}^{-1}=V\cdot \Xi_2-\sigma_1 \mathbf V \cdot \mathbf V_{[n-1]}^{-1} - \sigma_2 \mathbf V \cdot \mathbf V_{[n]}^{-1} = $$ $$ =[0,0,\dots,1,\sigma_1,\sigma_2]^{\top} - \sigma_1 [0,0,\dots,1,0]^{\top} - \sigma_2 [0,0,\dots,0,1]^{\top} = [0,0,\dots,1,0,0]^{\top} \, . $$ И так далее. ♦

Пример. Для приведенного выше примера

$$ \mathbf V=\left(\begin{array}{ccc} 1 & 1 & 1 \\ 1 & 2 & 3 \\ 1 & 4 & 9 \end{array} \right) $$ имеем $$ x_1=1,\ x_2=2,\ x_3=3,\ W^{\prime}(1)=2,\ W^{\prime}(2)=-1,\ W^{\prime}(3)=2 \, . $$ Запишем последовательность столбцов $ \Xi_0, \Xi_{1},\Xi_{2},\Xi_{3}, \Xi_{4} $ в виде матрицы $$ \left[ \begin{array}{rrrrr} 1/2 & 1/2 & 1/2 & 1/2 & 1/2 \\ -1 & -2 & -4 & -8 & -16 \\ 1/2 & 3/2 & 9/2 & 27/2 & 81/2 \end{array} \right] \ . $$ Суммируем элементы двух последних столбцов: $$ \sigma_1=6, \ \sigma_2=25 $$ и применяем теорему: $$ \begin{array}{lll} V_{[3]}^{-1}&=& \left[ \begin{array}{r} 1/2 \\ -1 \\ 1/2 \end{array} \right], \ \\ V_{[2]}^{-1}&=& \left[ \begin{array}{r} 1/2 \\ -2 \\ 3/2 \end{array} \right]- 6 \left[ \begin{array}{r} 1/2 \\ -1 \\ 1/2 \end{array} \right]= \left[ \begin{array}{r} -5/2 \\ 4 \\ -3/2 \end{array} \right], \\ V_{[1]}^{-1}&=& \left[ \begin{array}{rrrrr} 1/2 \\ -4 \\ 9/2 \end{array} \right] - 6\, \left[ \begin{array}{r} -5/2 \\ 4 \\ -3/2 \end{array} \right]-25\, \left[ \begin{array}{r} 1/2 \\ -1 \\ 1/2 \end{array} \right]= \left[ \begin{array}{r} 3\\ -3 \\ 1 \end{array} \right] \ . \end{array} $$ ♦

Теорема. Матрица обратная к матрице дискретного преобразования Фурье вычисляется по формуле:

$$ 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 $ (см. ☞ ЗДЕСЬ ), матрицу часто записывают в эквивалентном виде $$ 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} \ . $$

Доказательство ☞ ЗДЕСЬ.

Ядро матрицы $$ \mathbf V_{m,n}(x_1, x_2,\ldots,x_n) = \left( \begin{array}{llll} 1& 1& \ldots& 1\\ x_1& x_2& \ldots& x_n\\ x_1^2& x_2^2& \ldots& x_n^2\\ \vdots& \vdots& & \vdots \\ x_1^{m-1}& x_2^{m-1}& \ldots& x_n^{m-1} \end{array} \right)_{m\times n} $$ при $ m<n $ и различных $ \{x_1,x_2,\dots,x_n \} $ имеет базисными векторами $$ \big[x_1^j/W^{\prime}(x_1), \dots, x_n^j/W^{\prime}(x_n)\big]^{\top} \ \mbox{ при } j\in \{0,1,\dots,n-m-1\} \, . $$ Следствие равенств Эйлера-Лагранжа.

Ядро матрицы $$ \left( \begin{array}{llll} 1 & x_1 & x_1^2 & \dots & x_1^{m-1} \\ 1 & x_2 & x_2^2 & \dots & x_2^{m-1} \\ \vdots & & & \vdots \\ 1 & x_n & x_n^2 & \dots & x_n^{m-1} \end{array} \right)_{n\times m} $$ при $ n=m-1 $ имеет базисным вектором $ \left[ w_0,\dots, w_n \right]^{\top} $, а при $ n < m-1 $ — базисные векторы $$ \left[ w_0,\dots, w_n,0, 0, \dots, 0 \right]^{\top}, \ \left[0,w_0,\dots, w_n,0, \dots, 0 \right]^{\top}, \dots , \left[0,\dots,0, w_0,\dots, w_n \right]^{\top} \, . $$ Здесь $ \{w_j\} $ — коэффициенты канонического разложения полинома $$ \prod_{k=1}^n (x-x_k) \equiv w_0+w_1x+\dots+w_nx^n \, , $$ т.е. $$ w_0=(-1)^n \prod_{k=1}^n x_k, \dots, w_{n-1}=-\sum_{k=1}^n x_k, w_n=1 \, . $$

Материалы настоящего пункта взяты из [3].

Естественным обобщением матрицы Вандермонда является матрица¹⁾ $$ \widehat{\mathbf V}=\left( \begin{array}{cccc} x_1^{n_1} & x_1^{n_2} & \dots & x_1^{n_m} \\ x_2^{n_1} & x_2^{n_2} & \dots & x_2^{n_m} \\ \vdots & & & \vdots \\ x_m^{n_1} & x_m^{n_2} & \dots & x_m^{n_m} \end{array} \right) \quad npu \ \{n_1, n_2, \dots, n_m \} \subset \mathbb N \cup \{ 0 \} . $$ Ее определитель будем обозначать $ \widehat V $.

По аналогии с ☞ ПУНКТОМ, обозначим $$ W(x)=\prod_{j=1}^m (x-x_j) \, . $$ Вычислим выражения $$ \sigma_k(x_1,\dots,x_m) = \sum_{j=1}^{m} \frac{x_j^{m+k-1}}{W^{\prime}(x_j)} \quad \mbox{ для } \ k \in \{-(m-1),-(m-2),\dots,-1,0, 1,2, \dots \} \, . $$

Теорема 1. Имеют место равенства:

$$ \sigma_0 \equiv 1; \ \sigma_k \equiv 0 \quad npu \ k \in \{-1,-2,\dots,-(m-1)\} \, . $$ При $ k>0 $ выражение $ \sigma_k $ представляет собой симметрический полином от $ x_1,\dots,x_m $, равный сумме всевозможных мономов степени $ k $: $$ \sigma_k=\sum_{j_1+\dots+j_m=k}x_1^{j_1}\times \dots \times x_m^{j_m} \, . $$

Равенства $$ \sum_{j=1}^m \frac{x_j^k}{W'(x_j)}=\left\{ \begin{array}{cc} 0 & npu \ k< m-1; \\ 1 & npu \ k= m-1. \end{array} \right. $$ известны как равенства Эйлера-Лагранжа; доказательство ☞ ЗДЕСЬ.

Пример. Для $ m=4 $:

$$ \sigma_3=x_1^3+x_2^3+x_3^3+x_4^3+x_3^2x_2+x_3^2x_1+x_4x_3^2+x_3x_4^2+x_2^2x_3+x_1^2x_3 $$ $$ +x_2^2x_1+x_1^2x_2+x_1x_4^2+x_2^2x_4+x_2x_4^2+x_1^2x_4+x_3x_1x_2+x_1x_4x_3+x_2x_4x_3+x_1x_2x_4 $$

Теорема 2. Имеют место равенства

$$ \sigma_k=\frac{1}{\displaystyle \prod_{1\le \ell<j \le m} (x_j-x_{\ell})}\left| \begin{array}{cccc} 1 & 1 & \dots & 1 \\ x_1 & x_2 & \dots & x_m\\ \vdots & & & \vdots \\ x_1^{m-1} & x_2^{m-1} & \dots & x_m^{m-1}\\ x_1^{k+m-1} & x_2^{k+m-1} & \dots & x_m^{k+m-1} \end{array} \right| \quad \mbox{ при } \ k\in \mathbb N $$

Теорема 3. Имеет место формула Crocchi, связывающая величины $ \sigma_k $ с суммами Ньютона $ s_k=x_1^k+x_2^k+\dots+x_m^k $ полинома $ W(x) $:

$$ \sigma_{k-1} s_1+\sigma_{k-2} s_2+\dots+\sigma_{1} s_{k-1} + s_k = k \sigma_k \, . $$

Теорема 4. Имеет место равенство

$$ \widehat V=\left| \begin{array}{cccc} \sigma_{n_1} & \sigma_{n_1-1} & \dots & \sigma_{n_1-m} \\ \sigma_{n_2} & \sigma_{n_2-1} & \dots & \sigma_{n_2-m} \\ \vdots & & & \vdots \\ \sigma_{n_m} & \sigma_{n_m-1} & \dots & \sigma_{n_m-m} \end{array} \right| \prod_{1\le \ell <j \le m} (x_j-x_{\ell}) $$

Ввиду равенств Эйлера-Лагранжа можно ожидать, что матрица в правой части этой формулы имеет достаточное количество нулевых элементов.

Пример.

$$ \left| \begin{array}{cccc} x_1^{1} & x_1^{2} & x_1^4 & x_1^{6} \\ x_2^{1} & x_2^{2} & x_2^4 & x_2^{6} \\ x_3^{1} & x_3^{2} & x_3^4 & x_3^{6} \\ x_4^{1} & x_4^{2} & x_4^4 & x_4^{6} \end{array} \right|= \left| \begin{array}{cccc} 0 & 0 & \sigma_1 & \sigma_3 \\ 0 & 1 & \sigma_2 & \sigma_4 \\ 1 & \sigma_1 & \sigma_3 & \sigma_5 \\ \sigma_1 & \sigma_2 & \sigma_4 & \sigma_6 \end{array} \right| \prod_{1\le \ell < j \le 4} (x_j-x_{\ell}) \, . $$

Для доказательства справедливости формулы перемножим матрицы $$ \left( \begin{array}{cccc} 1/W^{\prime} (x_1) & 1/W^{\prime} (x_2) & 1/W^{\prime} (x_3) & 1/W^{\prime} (x_4) \\ x_1/W^{\prime} (x_1) & x_2/W^{\prime} (x_2) & x_3/W^{\prime} (x_3) & x_4/W^{\prime} (x_4) \\ x_1^2/W^{\prime} (x_1) & x_2^2/W^{\prime} (x_2) & x_3^2/W^{\prime} (x_3) & x_4^2/W^{\prime} (x_4) \\ x_1^3/W^{\prime} (x_1) & x_2^3/W^{\prime} (x_2) & x_3^3/W^{\prime} (x_3) & x_4^3/W^{\prime} (x_4) \end{array} \right) \left( \begin{array}{cccc} x_1^{1} & x_1^{2} & x_1^4 & x_1^{6} \\ x_2^{1} & x_2^{2} & x_2^4 & x_2^{6} \\ x_3^{1} & x_3^{2} & x_3^4 & x_3^{6} \\ x_4^{1} & x_4^{2} & x_4^4 & x_4^{6} \end{array} \right) $$ и, на основании равенств Эйлера-Лагранжа, имеем: $$ = \left( \begin{array}{cccc} \sigma_{-2} & \sigma_{-1} & \sigma_1 & \sigma_3 \\ \sigma_{-1} & \sigma_0 & \sigma_2 & \sigma_4 \\ \sigma_0 & \sigma_1 & \sigma_3 & \sigma_5 \\ \sigma_1 & \sigma_2 & \sigma_4 & \sigma_6 \end{array} \right)= \left( \begin{array}{cccc} 0 & 0 & \sigma_1 & \sigma_3 \\ 0 & 1 & \sigma_2 & \sigma_4 \\ 1 & \sigma_1 & \sigma_3 & \sigma_5 \\ \sigma_1 & \sigma_2 & \sigma_4 & \sigma_6 \end{array} \right) \, . $$ Переходим в равенстве к определителям:

$$ \left| \begin{array}{cccc} 1/W^{\prime} (x_1) & 1/W^{\prime} (x_2) & 1/W^{\prime} (x_3) & 1/W^{\prime} (x_4) \\ x_1/W^{\prime} (x_1) & x_2/W^{\prime} (x_2) & x_3/W^{\prime} (x_3) & x_4/W^{\prime} (x_4) \\ x_1^2/W^{\prime} (x_1) & x_2^2/W^{\prime} (x_2) & x_3^2/W^{\prime} (x_3) & x_4^2/W^{\prime} (x_4) \\ x_1^3/W^{\prime} (x_1) & x_2^3/W^{\prime} (x_2) & x_3^3/W^{\prime} (x_3) & x_4^3/W^{\prime} (x_4) \end{array} \right|=\frac{1}{\prod_{j=1}^4 W^{\prime} (x_j)} \left| \begin{array}{cccc} 1 & 1 & 1 & 1 \\ x_1 & x_2 & x_3 & x_4 \\ x_1^2 & x_2^2 & x_3^2 & x_4^2 \\ x_1^3 & x_2^3 & x_3^3 & x_4^3 \end{array} \right|= $$ $$ =\frac{\displaystyle \prod_{1\le \ell <j \le m} (x_j-x_{\ell})}{\displaystyle \prod_{1\le \ell <j \le m} (x_j-x_{\ell})^2}=\frac{1}{\displaystyle \prod_{1\le \ell <j \le m} (x_j-x_{\ell})} \, . $$ ♦

В достаточно широком классе случаев можно гарантировать невырожденность обобщенной матрицы Вандермонда.

Теорема 5 [5]. Если $ 0 \le n_1< n_2 < \dots < n_m $ и $ 0 < x_1< \dots < x_m $, то $$ \widehat V > 0 \, .$$

☞ ЗДЕСЬ

[1]. Кнут Д. Искусство программирования. Т.1., изд. Вильямс, 2002.

[2]. Маров А.В., Утешев А.Ю. Матричный формализм кодов Рида-Соломона Вестник СПбГУ. Серия 10. 2016. Вып. 4. 4-17.

[3]. Encyklopädie der Mathematischen Wissenschaften mit Einschluss ihrer Anwendungen. Bd. I. Arithmetik und Algebra. Редактор — Meyer W.F. 1898-1904. Leipzig, Teubner

[4]. Проскуряков И.В. Сборник задач по линейной алгебре. М.Наука. 1974

[5]. Полиа Г., Сеге Г.Задачи и теоремы из анализа.Т. 2. М.Наука. 1972, с. 54