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

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

названный в честь французского математика Александра Теофила Вандермонда. [1] Данная формула показывает, что определитель Вандермонда равен нулю тогда и только тогда, когда существует хотя бы одна пара такая, что .

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

Свойства

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

Если   - первообразный корень  -й степени из единицы и   - матрица Вандермонда с элементами  , то обратная матрица   с точностью до диагональной матрицы имеет вид  :  .

Применение

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

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

Быстрое умножение вектора   на матрицу Вандермонда эквивалентно нахождению   значений   многочлена   и может быть вычислено за   операций, где   — затраты на умножения двух полиномов.[4] Метод быстрого нахождения   значений многочлена строится на том факте, что  . Используя алгоритм быстрого умножения многочленов (а так же его модификацию операцию взятия по модулю многочлена), такой как Метод умножения Шёнхаге — Штрассена, применив парадигму разделяй и властвуй, за   умножений многочленов (и операций по модулю многочленов) строится дерево, листьями которого будут многочлены (значения)  , а корнем дерева будет многочлен  .[5]

Примечания

  1. Alexandre-Théophile Vandermonde  (рус.).
  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.
  5. Polynomial Algorithms.

Литература

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