Матрица Вандермонда

В линейной алгебре матрица Вандермонда , названная в честь Александра-Теофиля Вандермонда , представляет собой матрицу с членами геометрической прогрессии в каждой строке: $(m+1)\times (n+1)$ матрица

$V=V(x_{0},x_{1},\cdots ,x_{m})={\begin{bmatrix}1&x_{0}&x_{0}^{2}&\dots &x_{0}^{n}\\1&x_{1}&x_{1}^{2}&\dots &x_{1}^{n}\\1&x_{2}&x_{2}^{2}&\dots &x_{2}^{n}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{m}&x_{m}^{2}&\dots &x_{m}^{n}\end{bmatrix}}$

с записями $V_{i,j}=x_{i}^{j}$, Дж ^й степень числа $x_{i}$, для всех отсчитываемых от нуля индексов, $i$ и $j$. Некоторые авторы определяют матрицу Вандермонда как транспонированную вышеприведенную матрицу.

Определитель матрицы квадратной Вандермонда ( когда $n=m$) называется определителем Вандермонда или полиномом Вандермонда . Его значение:

$\det(V)=\prod _{0\leq i<j\leq n}(x_{j}-x_{i}).$

Это ненулевое значение тогда и только тогда, когда все $x_{i}$ различны (нет двух одинаковых), что делает матрицу Вандермонда обратимой .

Приложения

Задача полиномиальной интерполяции состоит в нахождении многочлена $p(x)=a_{0}+a_{1}x+a_{2}x^{2}+\dots +a_{n}x^{n}$ который удовлетворяет $p(x_{0})=y_{0},\ldots ,p(x_{m})=y_{m}$ для заданных точек данных $(x_{0},y_{0}),\ldots ,(x_{m},y_{m})$. Эту проблему можно переформулировать в терминах линейной алгебры с помощью матрицы Вандермонда следующим образом. $V$ вычисляет значения $p(x)$ в точках $x=x_{0},\ x_{1},\dots ,\ x_{m}$ через матричное умножение $Va=y$, где $a=(a_{0},\ldots ,a_{n})$ вектор коэффициентов и $y=(y_{0},\ldots ,y_{m})=(p(x_{0}),\ldots ,p(x_{m}))$ — вектор значений (оба записаны как векторы-столбцы):

$${\begin{bmatrix}1&x_{0}&x_{0}^{2}&\dots &x_{0}^{n}\\1&x_{1}&x_{1}^{2}&\dots &x_{1}^{n}\\1&x_{2}&x_{2}^{2}&\dots &x_{2}^{n}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{m}&x_{m}^{2}&\dots &x_{m}^{n}\end{bmatrix}}\cdot {\begin{bmatrix}a_{0}\\a_{1}\\\vdots \\a_{n}\end{bmatrix}}={\begin{bmatrix}p(x_{0})\\p(x_{1})\\\vdots \\p(x_{m})\end{bmatrix}}.$$Если $n=m$ и $x_{0},\dots ,\ x_{n}$ различны, то V — квадратная матрица с ненулевым определителем, т. е. обратимая матрица . Таким образом, по заданным V и y можно найти искомое $p(x)$ решив его коэффициенты $a$ в уравнении $Va=y$:

$a=V^{-1}y$.

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

В статистике уравнение $Va=y$ означает, что матрица Вандермонда является матрицей плана полиномиальной регрессии .

В численном анализе решение уравнения $Va=y$ наивно методом исключения Гаусса приводит к алгоритму с временной сложностью O( n ³ ). Используя структуру матрицы Вандермонда, можно использовать метод разделенных разностей Ньютона. (или интерполяционная формула Лагранжа ) решить уравнение за O( n ² ) время, что также дает UL- факторизацию $V^{-1}$. Полученный алгоритм дает чрезвычайно точные решения, даже если $V$ является плохо кондиционированным . (См. полиномиальную интерполяцию .)

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

Когда значения $x_{i}$ принадлежат конечному полю , определитель Вандермонда также называется определителем Мура и обладает свойствами, которые важны в теории кодов БЧХ и кодов исправления ошибок Рида – Соломона .

Дискретное преобразование Фурье определяется конкретной матрицей Вандермонда, матрицей ДПФ , где $x_{i}$ выбраны как n ^й корни единства . Быстрое преобразование Фурье вычисляет произведение этой матрицы на вектор в O( n log ² п ) время.

В физической теории квантового эффекта Холла определитель Вандермонда показывает, что волновая функция Лафлина с коэффициентом заполнения 1 равна определителю Слейтера . Это уже не так для коэффициентов заполнения, отличных от 1 в дробном квантовом эффекте Холла .

В геометрии многогранников матрица Вандермонда дает нормированный объем произвольного $k$-грани циклических многогранников . В частности, если $F=C_{d}(t_{i_{1}},\dots ,t_{i_{k+1}})$ это $k$-грань циклического многогранника $C_{d}(T)\subset \mathbb {R} ^{d}$ соответствующий $T=\{t_{1}<\cdots <t_{N}\}\subset \mathbb {R}$, затем $$\mathrm {nvol} (F)={\frac {1}{k!}}\prod _{1\leq m<n\leq k+1}{(t_{i_{n}}-t_{i_{m}})}.$$

Определитель

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

$\det(V)=\prod _{0\leq i<j\leq n}(x_{j}-x_{i})$

которое отлично от нуля тогда и только тогда, когда все $x_{i}$ различны.

Определитель Вандермонда раньше иногда называли дискриминантом , но в современной терминологии это дискриминант многочлена. $p(x)=(x-x_{0})\cdots (x-x_{n})$ - квадрат определителя Вандермонда корней $x_{i}$. Определитель Вандермонда представляет собой альтернативную форму в $x_{i}$, что означает, что обмен двумя $x_{i}$ меняет знак и $\det(V)$ таким образом, зависит от порядка $x_{i}$. Напротив, дискриминант $\det(V)^{2}$ не зависит ни от какого порядка, так что из теории Галуа следует, что дискриминант является полиномиальной функцией коэффициентов $p(x)$.

Формула определителя доказывается ниже тремя способами. Первый использует свойства полиномов, особенно свойство уникальной факторизации многомерных полиномов . Хотя концептуально он прост, он включает в себя неэлементарные понятия абстрактной алгебры . Второе доказательство основано на понятиях линейной алгебры о смене базиса в векторном пространстве и определителе линейного отображения . При этом он вычисляет LU-разложение матрицы Вандермонда. Третье доказательство более элементарно, но и сложнее, в нем используются только элементарные операции со строками и столбцами .

Первое доказательство: полиномиальные свойства

Первое доказательство опирается на свойства многочленов.

По Лейбница формуле $\det(V)$ является многочленом от $x_{i}$, с целыми коэффициентами. Все записи из $(i-1)$-й столбец имеет общую степень $i$. Таким образом, опять же по формуле Лейбница, все члены определителя имеют полную степень

$0+1+2+\cdots +n={\frac {n(n+1)}{2}};$

(т. е. определитель представляет собой однородный многочлен данной степени).

Если для $i\neq j$, один заменяет $x_{i}$ для $x_{j}$, получается матрица с двумя равными строками, которая, таким образом, имеет нулевой определитель. Таким образом, считая определитель одномерным по $x_{i},$ из факторной теоремы следует, что $x_{j}-x_{i}$ является делителем $\det(V).$ Отсюда следует, что для всех $i$ и $j$, $x_{j}-x_{i}$ является делителем $\det(V).$

Теперь это будет усилено, чтобы показать, что произведение всех этих делителей $\det(V)$ является делителем $\det(V).$ Действительно, пусть $p$ быть многочленом с $x_{i}-x_{j}$ как фактор, то $p=(x_{i}-x_{j})\,q,$ для некоторого полинома $q.$ Если $x_{k}-x_{l}$ является еще одним фактором $p,$ затем $p$ становится нулевым после замены $x_{k}$ для $x_{l}.$ Если $\{x_{i},x_{j}\}\neq \{x_{k},x_{l}\},$ фактор $q$ после этой замены становится нулевым, так как множитель $x_{i}-x_{j}$ остается ненулевым. Итак, по факторной теореме $x_{k}-x_{l}$ делит $q,$ и $(x_{i}-x_{j})\,(x_{k}-x_{l})$ делит $p.$

Повторяя этот процесс, начиная с $\det(V),$ это понятно $\det(V)$ делится на произведение всех $x_{i}-x_{j}$ с $i<j;$ то есть

$\det(V)=Q\prod _{0\leq i<j\leq n}(x_{j}-x_{i}),$

где $Q$ является полиномом. Как продукт всех $x_{j}-x_{i}$ и $\det(V)$ иметь одинаковую степень $n(n+1)/2$, полином $Q$ фактически является константой. Эта константа равна единице, поскольку произведение диагональных элементов $V$ является $x_{1}x_{2}^{2}\cdots x_{n}^{n}$, который также является мономом , который получается путем взятия первого члена всех факторов в $\textstyle \prod _{0\leq i<j\leq n}(x_{j}-x_{i}).$ Это доказывает, что $Q=1,$ и заканчивает доказательство.

$\det(V)=\prod _{0\leq i<j\leq n}(x_{j}-x_{i}).$

Второе доказательство: линейные карты

Пусть F — поле , содержащее все $x_{i},$ и $P_{n}$ векторное F пространство полиномов степени меньше или равной n с коэффициентами из F . Позволять

$\varphi :P_{n}\to F^{n+1}$

быть линейным отображением , определяемым

$p(x)\mapsto (p(x_{0}),p(x_{1}),\ldots ,p(x_{n}))$.

Матрица Вандермонда – это матрица $\varphi$ относительно канонических оснований $P_{n}$ и $F^{n+1}.$

основы Изменение $P_{n}$ представляет собой умножение матрицы Вандермонда на матрицу замены базиса M (справа). Это не меняет определитель, если определитель M равен 1 .

Полиномы $1$, $x-x_{0}$, $(x-x_{0})(x-x_{1})$, …, $(x-x_{0})(x-x_{1})\cdots (x-x_{n-1})$ являются моническими соответствующими степенями 0, 1, …, n . Их матрица на мономиальном базисе представляет собой верхнетреугольную матрицу U (если мономы упорядочены по возрастанию) со всеми диагональными элементами, равными единице. Таким образом, эта матрица представляет собой матрицу замены детерминанта. Матрица $\varphi$ на этой новой основе

${\begin{bmatrix}1&0&0&\ldots &0\\1&x_{1}-x_{0}&0&\ldots &0\\1&x_{2}-x_{0}&(x_{2}-x_{0})(x_{2}-x_{1})&\ldots &0\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{n}-x_{0}&(x_{n}-x_{0})(x_{n}-x_{1})&\ldots &(x_{n}-x_{0})(x_{n}-x_{1})\cdots (x_{n}-x_{n-1})\end{bmatrix}}$.

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

Это доказывает желаемое равенство. Более того, можно получить разложение V LU - как $V=LU^{-1}$.

Третье доказательство: операции со строками и столбцами

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

Итак, вычитая из каждого столбца, кроме первого, предыдущий столбец, умноженный на $x_{0}$, определитель не изменяется. (Эти вычитания необходимо выполнять, начиная с последних столбцов, для вычитания столбца, который еще не был изменен). Это дает матрицу

$V={\begin{bmatrix}1&0&0&0&\cdots &0\\1&x_{1}-x_{0}&x_{1}(x_{1}-x_{0})&x_{1}^{2}(x_{1}-x_{0})&\cdots &x_{1}^{n-1}(x_{1}-x_{0})\\1&x_{2}-x_{0}&x_{2}(x_{2}-x_{0})&x_{2}^{2}(x_{2}-x_{0})&\cdots &x_{2}^{n-1}(x_{2}-x_{0})\\\vdots &\vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{n}-x_{0}&x_{n}(x_{n}-x_{0})&x_{n}^{2}(x_{n}-x_{0})&\cdots &x_{n}^{n-1}(x_{n}-x_{0})\\\end{bmatrix}}$

Применяя формулу разложения Лапласа по первой строке, получаем $\det(V)=\det(B)$, с

$B={\begin{bmatrix}x_{1}-x_{0}&x_{1}(x_{1}-x_{0})&x_{1}^{2}(x_{1}-x_{0})&\cdots &x_{1}^{n-1}(x_{1}-x_{0})\\x_{2}-x_{0}&x_{2}(x_{2}-x_{0})&x_{2}^{2}(x_{2}-x_{0})&\cdots &x_{2}^{n-1}(x_{2}-x_{0})\\\vdots &\vdots &\vdots &\ddots &\vdots \\x_{n}-x_{0}&x_{n}(x_{n}-x_{0})&x_{n}^{2}(x_{n}-x_{0})&\cdots &x_{n}^{n-1}(x_{n}-x_{0})\\\end{bmatrix}}$

Поскольку все записи в $i$-й ряд $B$ иметь коэффициент $x_{i+1}-x_{0}$, можно исключить эти факторы и получить

$\det(V)=(x_{1}-x_{0})(x_{2}-x_{0})\cdots (x_{n}-x_{0}){\begin{vmatrix}1&x_{1}&x_{1}^{2}&\cdots &x_{1}^{n-1}\\1&x_{2}&x_{2}^{2}&\cdots &x_{2}^{n-1}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{n}&x_{n}^{2}&\cdots &x_{n}^{n-1}\\\end{vmatrix}}=\prod _{1<i\leq n}(x_{i}-x_{0})\det(V')$,

где $V'$ является матрицей Вандермонда в $x_{1},\ldots ,x_{n}$. Повторяя этот процесс на этой меньшей матрице Вандермонда, в конечном итоге получаем желаемое выражение $\det(V)$ как продукт всех $x_{j}-x_{i}$ такой, что $i<j$.

Ранг матрицы Вандермонда

• Прямоугольная матрица Вандермонда размером m × n такая, что m ≤ n, имеет ранг m тогда и только тогда, когда все x _i различны.
• Прямоугольная матрица Вандермонда размером m × n такая, что m ≥ n, имеет ранг n тогда и только тогда, когда существует n из xi _, которые различны.
• Квадратная матрица Вандермонда обратима тогда и только тогда, когда x _i различны. Известна явная формула обратного процесса (см. ниже).

Обратная матрица Вандермонда

Как объяснялось выше в разделе «Приложения», задача полиномиальной интерполяции для $p(x)=a_{0}+a_{1}x+a_{2}x^{2}+\dots +a_{n}x^{n}$удовлетворяющий $p(x_{0})=y_{0},\ldots ,p(x_{n})=y_{n}$ эквивалентно матричному уравнению $Va=y$, которое имеет единственное решение $a=V^{-1}y$. Существуют и другие известные формулы, решающие задачу интерполяции, которая должна быть эквивалентна уникальной $a=V^{-1}y$, поэтому они должны дать явные формулы для обратной матрицы $V^{-1}$. В частности, интерполяция Лагранжа показывает, что столбцы обратной матрицы

$$V^{-1}={\begin{bmatrix}1&x_{0}&\dots &x_{0}^{n}\\\vdots &\vdots &&\vdots \\[.5em]1&x_{n}&\dots &x_{n}^{n}\end{bmatrix}}^{-1}=L={\begin{bmatrix}L_{00}&\!\!\!\!\cdots \!\!\!\!&L_{0n}\\\vdots &&\vdots \\L_{n0}&\!\!\!\!\cdots \!\!\!\!&L_{nn}\end{bmatrix}}$$

являются коэффициентами полиномов Лагранжа

$L_{j}(x)=L_{0j}+L_{1j}x+\cdots +L_{nj}x^{n}=\prod _{0\leq i\leq n \atop i\neq j}{\frac {x-x_{i}}{x_{j}-x_{i}}}={\frac {f(x)}{(x-x_{j})\,f'(x_{j})}}\,,$

где $f(x)=(x-x_{0})\cdots (x-x_{n})$. Это легко продемонстрировать: полиномы явно удовлетворяют $L_{j}(x_{i})=0$ для $i\neq j$ пока $L_{j}(x_{j})=1$, поэтому мы можем вычислить произведение $VL=[L_{j}(x_{i})]_{i,j=0}^{n}=I$, единичная матрица.

Сливные матрицы Вандермонда

Как описано ранее, матрица Вандермонда описывает интерполяционную задачу линейной алгебры по нахождению коэффициентов полинома. $p(x)$ степени $n-1$ на основе ценностей $p(x_{1}),\,...,\,p(x_{n})$, где $x_{1},\,...,\,x_{n}$ это отдельные точки. Если $x_{i}$ не различны, то эта задача не имеет единственного решения (и соответствующая матрица Вандермонда сингулярна). Однако если указать значения производных в повторяющихся точках, то задача может иметь единственное решение. Например, проблема

${\begin{cases}p(0)=y_{1}\\p'(0)=y_{2}\\p(1)=y_{3}\end{cases}}$

где $p(x)=ax^{2}+bx+c$, имеет уникальное решение для всех $y_{1},y_{2},y_{3}$ с $y_{1}\neq y_{3}$. В общем, предположим, что $x_{1},x_{2},...,x_{n}$ являются (не обязательно разными) числами, и предположим для простоты, что равные значения соседствуют:

$x_{1}=\cdots =x_{m_{1}},\ x_{m_{1}+1}=\cdots =x_{m_{2}},\ \ldots ,\ x_{m_{k-1}+1}=\cdots =x_{m_{k}}$

где $m_{1}<m_{2}<\cdots <m_{k}=n,$ и $x_{m_{1}},\ldots ,x_{m_{k}}$ различны. Тогда соответствующая интерполяционная задача имеет вид

${\begin{cases}p(x_{m_{1}})=y_{1},&p'(x_{m_{1}})=y_{2},&\ldots ,&p^{(m_{1}-1)}(x_{m_{1}})=y_{m_{1}},\\p(x_{m_{2}})=y_{m_{1}+1},&p'(x_{m_{2}})=y_{m_{1}+2},&\ldots ,&p^{(m_{2}-m_{1}-1)}(x_{m_{2}})=y_{m_{2}},\\\qquad \vdots &&&\qquad \vdots \\p(x_{m_{k}})=y_{m_{k-1}+1},&p'(x_{m_{k}})=y_{m_{k-1}+2},&\ldots ,&p^{(m_{k}-m_{k-1}-1)}(x_{m_{k}})=y_{m_{k}}.\end{cases}}$

Соответствующая матрица для этой задачи называется конфлюэнтной матрицей Вандермонда и задается следующим образом. Если $1\leq i,j\leq n$, затем $m_{\ell }<i\leq m_{\ell +1}$ для уникального $0\leq \ell \leq k-1$ (обозначая $m_{0}=0$). Мы позволяем

$V_{i,j}={\begin{cases}0&{\text{if }}j<i-m_{\ell },\\[6pt]{\dfrac {(j-1)!}{(j-(i-m_{\ell }))!}}x_{i}^{j-(i-m_{\ell })}&{\text{if }}j\geq i-m_{\ell }.\end{cases}}$

Это обобщение матрицы Вандермонда делает ее неособой , так что существует единственное решение системы уравнений, и она обладает большинством других свойств матрицы Вандермонда. Его строки являются производными (некоторого порядка) исходных строк Вандермонда.

Другой способ получить эту формулу — взять предел матрицы Вандермонда в качестве $x_{i}$подходим друг к другу. Например, чтобы получить случай $x_{1}=x_{2}$, вычтем первую строку из второй в исходной матрице Вандермонда и позволим $x_{2}\to x_{1}$: это дает соответствующую строку в конфлюэнтной матрице Вандермонда. Это выводит обобщенную задачу интерполяции с заданными значениями и производными как предел исходного случая с отдельными точками: давая $p(x_{i}),p'(x_{i})$ похоже на предоставление $p(x_{i}),p(x_{i}+\varepsilon )$ для маленьких $\varepsilon$. Геометры изучили проблему отслеживания сливающихся точек вдоль их касательных линий, известную как компацитификация конфигурационного пространства .

См. также

• Сопутствующая матрица § Диагонализация
• Полином Шура – ​​обобщение
• Переменная матрица
• Полином Лагранжа
• Вронскиан
• Список матриц
• Определитель Мура над конечным полем
• Формула Плейса

Дальнейшее чтение

• Икарт, Бернар (2013), «Случай математической эпонимии: определитель Вандермонда», Revue d'Histoire des Mathématiques , 13 , arXiv : 1204.4716 , Bibcode : 2012arXiv1204.4716Y .

Внешние ссылки

• Матрица Вандермонда в ProofWiki