Определитель Вандермонда

Определитель Вандермонда — выражение вида

${\displaystyle \left|V(x_{1},\ldots ,x_{n})\right|={\begin{vmatrix}1&x_{1}&\ldots &x_{1}^{n-1}\\1&x_{2}&\ldots &x_{2}^{n-1}\\\vdots &\vdots &\ddots &\vdots \\1&x_{n}&\ldots &x_{n}^{n-1}\\\end{vmatrix}}=\prod \limits _{1\leqslant j<i\leqslant n}(x_{i}-x_{j}),}$

где ${\displaystyle x_{1},\ldots ,x_{n}}$ — элементы некоторого поля. Матрицей Вандермонда называется либо матрица ${\displaystyle V(x_{1},\ldots ,x_{n})}$^[1][2], либо её транспонированная версия ${\displaystyle V^{\mathrm {T} }(x_{1},\ldots ,x_{n})}$^[3][4][5][6]. Матрица и её определитель названы в честь французского математика А. Т. Вандермонда^[7].

Определитель Вандермонда равен нулю тогда и только тогда, когда существует хотя бы одна пара ${\displaystyle \left(x_{i},x_{j}\right)}$ такая, что ${\displaystyle x_{i}=x_{j},i\neq j}$^[8].

Доказательство

Доказательство по индукции

Индукция по размеру матрицы ${\displaystyle m}$.

База индукции

${\displaystyle m=2}$. В данном случае матрица представляет собой

${\displaystyle V_{2}={\begin{bmatrix}1&x_{1}\\1&x_{2}\\\end{bmatrix}}}$

Очевидно, её определитель равен ${\displaystyle x_{2}-x_{1}}$.

Индукционное предположение

${\displaystyle {\begin{vmatrix}1&x_{1}&x_{1}^{2}&\dots &x_{1}^{m-2}\\1&x_{2}&x_{2}^{2}&\dots &x_{2}^{m-2}\\.&.&.&.&.\\1&x_{m-1}&x_{m-1}^{2}&\dots &x_{m-1}^{m-2}\\\end{vmatrix}}=\prod \limits _{1\leqslant i<j\leqslant m-1}(x_{j}-x_{i})}$

Индукционный переход

${\displaystyle {\begin{vmatrix}1&x_{1}&x_{1}^{2}&\dots &x_{1}^{m-1}\\1&x_{2}&x_{2}^{2}&\dots &x_{2}^{m-1}\\.&.&.&.&.\\1&x_{m}&x_{m}^{2}&\dots &x_{m}^{m-1}\\\end{vmatrix}}}$

Вычтем из последнего столбца предпоследний, умноженный на ${\displaystyle x_{1}}$, из ${\displaystyle m-2}$-го — ${\displaystyle m-3}$-й, умноженный на ${\displaystyle x_{1}}$, из ${\displaystyle i}$-го — ${\displaystyle i-1}$-й, умноженный на ${\displaystyle x_{1}}$ и так далее для всех столбцов. Эти преобразования не меняют определитель матрицы. Получим

${\displaystyle {\begin{vmatrix}1&0&0&\dots &0\\1&x_{2}-x_{1}&x_{2}(x_{2}-x_{1})&\dots &x_{2}^{m-2}(x_{2}-x_{1})\\.&.&.&.&.\\1&x_{m}-x_{1}&x_{m}(x_{m}-x_{1})&\dots &x_{m}^{m-2}(x_{m}-x_{1})\\\end{vmatrix}}}$

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

${\displaystyle {\begin{vmatrix}x_{2}-x_{1}&x_{2}(x_{2}-x_{1})&\dots &x_{2}^{m-2}(x_{2}-x_{1})\\.&.&.&.\\x_{m}-x_{1}&x_{m}(x_{m}-x_{1})&\dots &x_{m}^{m-2}(x_{m}-x_{1})\\\end{vmatrix}}}$

Для всех ${\displaystyle i}$ от 1 до ${\displaystyle m-1}$ вынесем из ${\displaystyle i}$-й строки множитель ${\displaystyle x_{i+1}-x_{1}}$. Получим

${\displaystyle (x_{2}-x_{1})(x_{3}-x_{1})\dots (x_{m}-x_{1}){\begin{vmatrix}1&x_{2}&\dots &x_{2}^{m-2}\\.&.&.&.\\1&x_{m}&\dots &x_{m}^{m-2}\\\end{vmatrix}}}$

Подставим значение имеющегося в предыдущей формуле определителя, известного из индукционного предположения:

${\displaystyle (x_{2}-x_{1})(x_{3}-x_{1})\dots (x_{m}-x_{1})\prod \limits _{2\leqslant i<j\leqslant m}(x_{j}-x_{i})=\prod \limits _{1\leqslant i<j\leqslant m}(x_{j}-x_{i})}$

■

Доказательство через сравнение степеней

Другое доказательство можно получить, если считать, что ${\displaystyle x_{1},\ldots ,x_{n}}$ являются переменными в кольце многочленов ${\displaystyle {\mathbb {C} }[x_{1},\ldots ,x_{n}]}$. В этом случае определитель Вандермонда — это многочлен ${\displaystyle V}$ от ${\displaystyle n}$ переменных. Он состоит из одночленов, степень каждого из которых равна ${\displaystyle 0+1+\ldots +(n-1)={\frac {n(n-1)}{2}}}$. Значит, степень ${\displaystyle V}$ равна тому же числу.

Заметим, что если какие-то ${\displaystyle x_{i}}$ и ${\displaystyle x_{j}}$ совпадают, то определитель равен нулю, поскольку в матрице появляются две одинаковые строки. Поэтому определитель как многочлен должен делиться на ${\displaystyle (x_{i}-x_{j})}$. Всего различных пар ${\displaystyle x_{i}}$ и ${\displaystyle x_{j}}$ (при ${\displaystyle i>j}$) существует ${\displaystyle 0+1+\ldots +(n-1)}$, что равно степени ${\displaystyle V}$. Иными словами, ${\displaystyle V}$ делится на ${\displaystyle \deg V}$ различных многочленов степени ${\displaystyle 1}$. Значит, он равен их произведению с точностью до константы. Но, как можно убедиться, раскрыв скобки, константа равна единице^[9]. ■

Свойства

Матрица Вандермонда представляет собой частный случай альтернативной матрицы, в которой ${\displaystyle f_{i}(\alpha )=\alpha ^{i-1}}$.

Если ${\displaystyle \zeta }$ — первообразный корень ${\displaystyle n}$-й степени из единицы и ${\displaystyle A=(a_{i,j})}$ — матрица Вандермонда с элементами ${\displaystyle a_{i,j}=\zeta ^{ij}}$, то обратная матрица ${\displaystyle B=({\tilde {a}}_{i,j})}$ с точностью до диагональной матрицы имеет вид ${\displaystyle {\tilde {a}}_{i,j}=\zeta ^{-ij}}$: ${\displaystyle AB=n\cdot E}$.

Применение

Определитель Вандермонда имеет многочисленные применения в разных областях математики. Например, при решении задачи интерполяции многочленами, то есть задачи о нахождении многочлена степени ${\displaystyle n-1}$, график которого проходит через ${\displaystyle n}$ заданных точек плоскости с абсциссами ${\displaystyle x_{1},\ldots ,x_{n}}$, определитель Вандермонда возникает как определитель системы линейных уравнений, из которой находятся неизвестные коэффициенты искомого многочлена^[2].

Быстрое умножение вектора на матрицу Вандермонда

Быстрое умножение вектора ${\displaystyle (a_{0},\ldots ,a_{n})^{\mathrm {T} }}$ на матрицу Вандермонда эквивалентно нахождению ${\displaystyle n}$ значений ${\displaystyle x_{i}}$ многочлена ${\displaystyle f(x)=a_{0}+a_{1}x+\ldots +a_{n}x^{n}}$ и может быть вычислено за ${\displaystyle O(\log(n)\cdot M(n))}$ операций, где ${\displaystyle M(n)}$ — затраты на умножения двух полиномов^[10]. Метод быстрого нахождения ${\displaystyle n}$ значений многочлена основывается на том факте, что ${\displaystyle f(x_{i})\equiv a_{0}+a_{1}x+\ldots +a_{n}x^{n}{\pmod {x-x_{i}}}}$. С использованием алгоритма быстрого умножения многочленов, такого как метод умножения Шёнхаге — Штрассена, и с применением парадигмы «разделяй и властвуй» за ${\displaystyle O(\log(n))}$ умножений многочленов (и операций по модулю многочленов) строится дерево, листьями которого будут многочлены (значения) ${\displaystyle f(x)\,{\bmod {\,}}(x-x_{i})}$, а корнем дерева будет многочлен ${\displaystyle f(x)\,{\bmod {\,}}{(x-x_{1})(x-x_{2})\cdots (x-x_{n})}}$^[11].