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

Определитель Вандермонда
Определитель Вандермонда
Названо в честь	Александр Теофил Вандермонд

Определитель Вандермонда
Определитель Вандермонда
Названо в честь	Александр Теофил Вандермонд

Определитель Вандермонда — это определитель квадратной матрицы, строки которой состоят из последовательных степеней заданных чисел, равный произведению всех возможных попарных разностей этих чисел.

Матрица Вандермонда представляет собой частный случай альтернативной матрицы. В случае первообразного корня из единицы обратная матрица с точностью до диагональной матрицы имеет явный вид.

Определитель Вандермонда возникает при решении задачи интерполяции многочленов как определитель системы линейных уравнений, из которой находятся коэффициенты искомого многочлена, график которого проходит через заданные точки. Это одно из многочисленных применений определителя в разных областях математики.

Умножение вектора на матрицу Вандермонда эквивалентно нахождению значений многочлена в заданных точках. Для вычислений применяется быстрое умножение многочленов, например метод Шёнхаге — Штрассена.

Алгоритм строит дерево по принципу «разделяй и властвуй»: листьями являются значения многочлена, а корнем — сам многочлен. Используются операции умножения полиномов и взятия по модулю, а сложность оценивается через затраты на умножение двух многочленов.

Определителем Вандермонда называется определитель

{\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 i<j\leqslant n}(x_{j}-x_{i}),

названный в честь французского математика Александра Теофила Вандермонда^[1].

Данная формула показывает, что определитель Вандермонда равен нулю тогда и только тогда, когда существует хотя бы одна пара $\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$ . Значит, он равен их произведению с точностью до константы. Но, как можно убедиться, раскрыв скобки, константа равна единице. ^[2] ■

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

Быстрое умножение вектора $(a_{0},\dots ,a_{n})^{t}$ на матрицу Вандермонда эквивалентно нахождению $n$ значений $x_{i}$ многочлена $f(x)=a_{0}+a_{1}x+\ldots +a_{n}x^{n}$ и может быть вычислено за $O(\log(n)\cdot M(n))$ операций, где $M(n)$ — затраты на умножения двух полиномов.^[4] Метод быстрого нахождения $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})}$ .^[5]

↑ Alexandre-Théophile Vandermonde Архивная копия от 5 января 2013 на Wayback Machine (рус.).
↑ Ian Stewart Galois Theory, Third Edition, стр. 28, — Chapman & Hall/CRC Mathematics.
↑ Шафаревич И. Р., Ремизов А. О. Линейная алгебра и геометрия, гл. II, пар. 4, — Физматлит, Москва, 2009.
↑ Efficient computation with structured matrices and arithmetic expressions (неопр.). Дата обращения: 24 января 2017. Архивировано 2 февраля 2017 года.
↑ Polynomial Algorithms (неопр.). Дата обращения: 24 января 2017. Архивировано 10 января 2017 года.

Курош А. Г. Курс высшей алгебры. — М.: Наука 1968.
Ильин В. А., Позняк Э. Г. Линейная алгебра. — М.: Наука — Физматлит, 1999.
Шафаревич И. Р., Ремизов А. О. Линейная алгебра и геометрия, — Физматлит, Москва, 2009.

[1] Alexandre-Théophile Vandermonde Архивная копия от 5 января 2013 на Wayback Machine (рус.).

[2] Ian Stewart Galois Theory, Third Edition, стр. 28, — Chapman & Hall/CRC Mathematics.

[3] Шафаревич И. Р., Ремизов А. О. Линейная алгебра и геометрия, гл. II, пар. 4, — Физматлит, Москва, 2009.

[4] Efficient computation with structured matrices and arithmetic expressions (неопр.). Дата обращения: 24 января 2017. Архивировано 2 февраля 2017 года.

[5] Polynomial Algorithms (неопр.). Дата обращения: 24 января 2017. Архивировано 10 января 2017 года.

[1]

[2]

[3]

[4]

[5]

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

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

Свойства

Применение

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

Примечания

Литература

Категории