Определитель Вандермонда
Определителем Вандермонда называется определитель
названный в честь французского математика Александра Теофила Вандермонда. [1] Данная формула показывает, что определитель Вандермонда равен нулю тогда и только тогда, когда существует хотя бы одна пара такая, что .
Доказательство
Индукция по размеру матрицы .
- База индукции
. В данном случае матрица представляет собой
Очевидно, её определитель равен .
- Индукционное предположение
- Индукционный переход
Вычтем из последнего столбца предпоследний, умноженный на , из -го — -й, умноженный на , из -го — -й, умноженный на и так далее для всех столбцов. Эти преобразования не меняют определитель матрицы. Получим
Раскладывая этот определитель по элементам первой строки, получаем, что он равен следующему определителю:
Для всех от 1 до вынесем из -й строки множитель . Получим
Подставим значение имеющегося в предыдущей формуле определителя, известного из индукционного предположения:
Другое доказательство можно получить, если считать, что являются переменными в кольце многочленов . В этом случае определитель Вандермонда — это многочлен от переменных. Он состоит из одночленов, степень каждого из которых равна . Значит, степень равна тому же числу.
Заметим, что если какие-то и совпадают, то определитель равен нулю, поскольку в матрице появляются две одинаковые строки. Поэтому определитель как многочлен должен делиться на . Всего различных пар и (при ) существует , что равно степени . Иными словами, делится на различных многочленов степени . Значит, он равен их произведению с точностью до константы. Но, как можно убедиться, раскрыв скобки, константа равна единице. [2] ■
Свойства
Матрица Вандермонда представляет собой частный случай альтернативной матрицы, в которой .
Если — первообразный корень -й степени из единицы и — матрица Вандермонда с элементами , то обратная матрица с точностью до диагональной матрицы имеет вид : .
Применение
Определитель Вандермонда имеет многочисленные применения в разных областях математики. Например, при решении задачи интерполяции многочленами, то есть задачи о нахождении многочлена степени , график которого проходит через заданных точек плоскости с абсциссами , определитель Вандермонда возникает как определитель системы линейных уравнений, из которой находятся неизвестные коэффициенты искомого многочлена.[3]
Быстрое умножение вектора на матрицу Вандермонда
Быстрое умножение вектора на матрицу Вандермонда эквивалентно нахождению значений многочлена и может быть вычислено за операций, где — затраты на умножения двух полиномов.[4] Метод быстрого нахождения значений многочлена строится на том факте, что . Используя алгоритм быстрого умножения многочленов (а также его модификацию операцию взятия по модулю многочлена), такой как Метод умножения Шёнхаге — Штрассена, применив парадигму разделяй и властвуй, за умножений многочленов (и операций по модулю многочленов) строится дерево, листьями которого будут многочлены (значения) , а корнем дерева будет многочлен .[5]
Примечания
- ↑ Alexandre-Théophile Vandermonde (рус.).
- ↑ Ian Stewart Galois Theory, Third Edition, стр. 28, — Chapman & Hall/CRC Mathematics.
- ↑ Шафаревич И. Р., Ремизов А. О. Линейная алгебра и геометрия, гл. II, пар. 4, — Физматлит, Москва, 2009.
- ↑ Efficient computation with structured matrices and arithmetic expressions .
- ↑ Polynomial Algorithms .
Литература
- Курош А. Г. Курс высшей алгебры. — М.: Наука 1968.
- Ильин В. А., Позняк Э. Г. Линейная алгебра. — М.: Наука — Физматлит, 1999.
- Шафаревич И. Р., Ремизов А. О. Линейная алгебра и геометрия, — Физматлит, Москва, 2009.