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

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

$|V(x_1,\dots ,x_n)|=\left|\begin{array}{cccc}1& x_1& \dots & x_1^{n-1}\\ 1& x_2& \dots & x_2^{n-1}\\ ⋮& ⋮& \ddots & ⋮\\ 1& x_n& \dots & x_n^{n-1}\end{array}\right|=\prod _{1⩽j<i⩽n}(x_i-x_j),$

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

Определитель Вандермонда равен нулю тогда и только тогда, когда существует хотя бы одна пара $(x_i,x_j)$ такая, что $x_i=x_j,i\ne j$.

Свойства

Матрица Вандермонда представляет собой частный случай альтернативной матрицы, в которой $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,\dots ,x_n$, определитель Вандермонда возникает как определитель системы линейных уравнений, из которой находятся неизвестные коэффициенты искомого многочлена.

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

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