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

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

$\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}),$

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

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

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

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

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

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

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

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

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

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

${\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})$

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

${\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}}$

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

${\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}}$

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

${\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}}$

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

$(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}}$

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

$(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})$

■

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

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

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

Свойства

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

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

Применение

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

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

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