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

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

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

Примечания

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 .
(неопр.) . Архивировано из 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.
(неопр.) . Дата обращения: 24 января 2017. 2 февраля 2017 года.
(неопр.) . Дата обращения: 24 января 2017. 10 января 2017 года.