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

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

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

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

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

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

Индукция по размеру матрицы $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 _{1\leqslant i<j\leqslant m-1}(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$ . Значит, он равен их произведению с точностью до константы. Но, как можно убедиться, раскрыв скобки, константа равна единице^[9]. ■

Свойства

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

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

Быстрое умножение вектора $(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)$ — затраты на умножения двух полиномов^[10]. Метод быстрого нахождения $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})}$ ^[11].

Примечания

↑ Horn R. A., Johnson C. R.. Matrix analysis. — 2nd ed. — Cambridge University Press, 2013. — P. 37. — ISBN 978-0-521-83940-2.
↑ ¹ ² Шафаревич И. Р., Ремизов А. О.. Линейная алгебра и геометрия. — М.: Физматлит, 2009. — С. 55—56. — 512 с. — ISBN 978-5-9221-1139-3.
↑ Тыртышников Е. Е. Матричный анализ и линейная алгебра. — М.: Физматлит, 2007. — С. 119. — 480 с. — ISBN 978-5-9221-0778-5.
↑ Stoll R. R.. Linear algebra and matrix theory. — New York: Dover Publications, 1969. — P. 102.
↑ Курош А. Г. Курс высшей алгебры. — 19-е изд., стер.. — СПб.: Лань, 2013. — С. 50. — 432 с. — ISBN 978-5-8114-0521-3.
↑ Ильин В. А., Позняк Э. Г. Линейная алгебра. — 6-е изд., стер.. — М.: Физматлит, 2005. — С. 34—35. — 280 с. — ISBN 5-9221-0481-0.
↑ Alexandre-Théophile Vandermonde (неопр.). Архивировано из оригинала 5 января 2013 года.
↑ Bernstein D. S.. Matrix Mathematics: Theory, Facts, and Formulas (англ.). — 2nd ed.. — Princeton University Press, 2009. — P. 354. — ISBN 978-0-691-13287-7.
↑ Ian Stewart Galois Theory, Third Edition, стр. 28, — Chapman & Hall/CRC Mathematics.
↑ Efficient computation with structured matrices and arithmetic expressions (неопр.). Дата обращения: 24 января 2017. Архивировано 2 февраля 2017 года.
↑ Polynomial Algorithms (неопр.). Дата обращения: 24 января 2017. Архивировано 10 января 2017 года.