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

В линейная алгебра, а Матрица Вандермонда, названный в честь Александр-Теофиль Вандермонд, это матрица с условиями геометрическая прогрессия в каждой строке, т.е. м × п матрица

${\displaystyle V={\begin{bmatrix}1&\alpha _{1}&\alpha _{1}^{2}&\dots &\alpha _{1}^{n-1}\\1&\alpha _{2}&\alpha _{2}^{2}&\dots &\alpha _{2}^{n-1}\\1&\alpha _{3}&\alpha _{3}^{2}&\dots &\alpha _{3}^{n-1}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&\alpha _{m}&\alpha _{m}^{2}&\dots &\alpha _{m}^{n-1}\end{bmatrix}},}$

или же

${\displaystyle V_{i,j}=\alpha _{i}^{j-1}\,}$

по всем показателям я и j.^[1] Идентичный термин матрица Вандермонда использовался для транспонировать вышеупомянутой матрицы Макона и Шпицбарта (1958). Матрица Вандермонда, используемая для матрицы дискретного преобразования Фурье^[2] удовлетворяет обоим определениям.

В детерминант квадратной матрицы Вандермонда (где м = п) можно выразить как

${\displaystyle \det(V)=\prod _{1\leq i<j\leq n}(\alpha _{j}-\alpha _{i}).}$

Это называется Определитель Вандермонда или же Полином Вандермонда. Он ненулевой тогда и только тогда, когда все ${\displaystyle \alpha _{i}}$ различны.

Определитель Вандермонда иногда называли дискриминант, хотя в настоящее время дискриминант полинома есть квадрат определителя Вандермонда корни полинома. Определитель Вандермонда - это переменная форма в ${\displaystyle \alpha _{i}}$, что означает обмен двух ${\displaystyle \alpha _{i}}$ меняет знак, переставляя ${\displaystyle \alpha _{i}}$ по даже перестановка не меняет значения определителя. Таким образом, это зависит от выбора заказа для ${\displaystyle \alpha _{i}}$, а его квадрат, дискриминант, не зависит ни от какого порядка, а это означает, что Теория Галуа, что дискриминант полиномиальная функция коэффициентов многочлена, имеющего ${\displaystyle \alpha _{i}}$ как корни.

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

Основное свойство квадратной матрицы Вандермонда

${\displaystyle V={\begin{bmatrix}1&x_{1}&x_{1}^{2}&\dots &x_{1}^{n-1}\\1&x_{2}&x_{2}^{2}&\dots &x_{2}^{n-1}\\1&x_{3}&x_{3}^{2}&\dots &x_{3}^{n-1}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{n}&x_{n}^{2}&\dots &x_{n}^{n-1}\end{bmatrix}}}$

в том, что его определитель имеет простой вид

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

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

Использование полиномиальных свойств

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

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

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

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

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

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

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

Использование линейных карт

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

${\displaystyle \varphi :P_{n}\to F^{n}}$

быть линейная карта определяется

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

Матрица Вандермонда - это матрица ${\displaystyle \varphi }$ с уважением к канонические основы из ${\displaystyle P_{n}}$ и ${\displaystyle F^{n}.}$

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

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

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

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

Это доказывает желаемое равенство. Более того, получается LU разложение из V в качестве

${\displaystyle V=LU^{-1}.}$

По строкам и столбцам

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

Если вычесть первую строку V от всех остальных строк определитель не меняется, и новая матрица имеет вид

${\displaystyle {\begin{bmatrix}1&\mathbf {L} \\\mathbf {0} &A\end{bmatrix}},}$

куда ${\displaystyle \mathbf {L} }$ матрица-строка, ${\displaystyle \mathbf {0} }$ столбец нулей, а А это квадратная матрица, так что

${\displaystyle \det(A)=\det(V).}$

Вступление (я – 1)й ряд и (j – 1)-й столбец А (это яй ряд и j-й столбец всей матрицы)

${\displaystyle x_{i}^{j-1}-x_{1}^{j-1}=(x_{i}-x_{1})\sum _{k=0}^{j-2}x_{i}^{k}x_{1}^{j-2-k}.}$

Разделение ${\displaystyle x_{i}-x_{1}}$ от (я – 1)й ряд А, за я = 2, ..., п, получается матрица B такой, что

${\displaystyle \det(V)=\det(A)=\det(B)\prod _{i=2}^{n}(x_{i}-x_{1}).}$

Коэффициент (я – 1)й ряд и (j – 1)-й столбец B является

${\displaystyle b_{i,j}=\sum _{k=0}^{j-2}x_{i}^{k}x_{1}^{j-2-k}=x_{i}^{j-2}+x_{1}b_{i,j-1},}$

за я = 2, ..., n, и установка ${\displaystyle b_{i,1}=1.}$

Таким образом, вычитая, для j убегая от п до 2, (j – 2)-й столбец B умножается на ${\displaystyle x_{1}}$ от (j – 1)-й столбец получает (п – 1) × (п – 1) Матрица Вандермонда в ${\displaystyle x_{2},\ldots ,x_{n},}$ который имеет тот же определитель, что и B. Итерируя этот процесс на этой меньшей матрице Вандермонда, в конечном итоге получаем желаемое выражение det (V) как продукт ${\displaystyle x_{j}-x_{i}.}$

Результирующие свойства

An м × п прямоугольная матрица Вандермонда такая, что м ≤ п имеет максимум классифицировать м если и только если все Икс_я различны.

An м × п прямоугольная матрица Вандермонда такая, что м ≥ п имеет максимум классифицировать п если и только если есть п из Икс_я которые различны.

Квадратная матрица Вандермонда есть обратимый если и только если Икс_я различны. Известна явная формула обратного.^[3][4][5]

Приложения

Матрица Вандермонда оценивает многочлен в наборе точек; формально это матрица линейная карта который отображает вектор коэффициентов полинома в вектор значений полинома в значениях, появляющихся в матрице Вандермонда. Необращение в нуль определителя Вандермонда для различных точек ${\displaystyle \alpha _{i}}$ показывает, что для различных точек отображение коэффициентов в значения в этих точках является взаимно однозначным соответствием, и, таким образом, проблема полиномиальной интерполяции разрешима с помощью единственного решения; этот результат называется теорема о неразрывности, и является частным случаем Китайская теорема об остатках для многочленов.

Это может быть полезно в полиномиальная интерполяция, поскольку обращение матрицы Вандермонда позволяет выразить коэффициенты полинома через ${\displaystyle \alpha _{i}}$^[6] и значения полинома на ${\displaystyle \alpha _{i}}$Однако интерполяционный полином, как правило, легче вычислить с помощью Формула интерполяции Лагранжа,^[7] который может быть использован для вывода формулы для обратной матрицы Вандермонда.^[8]

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

Когда ценности ${\displaystyle \alpha _{k}}$ принадлежат к конечное поле, то определитель Вандермонда также называют Определитель Мура и имеет специфические свойства, которые используются, например, в теории Код BCH и Исправление ошибок Рида – Соломона коды.

В дискретное преобразование Фурье определяется конкретной матрицей Вандермонда, Матрица ДПФ, где числа α_я выбраны быть корни единства.

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

Это матрица дизайна из полиномиальная регрессия.

Конфлюэнтные матрицы Вандермонда

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

${\displaystyle {\begin{cases}p(0)=a\\p'(0)=b\\p(1)=c\end{cases}}}$

куда ${\displaystyle p}$ является многочленом степени ${\displaystyle \leq 2}$, имеет уникальное решение для всех ${\displaystyle a,b,c}$. В общем, предположим, что ${\displaystyle \alpha _{1},\alpha _{2},...,\alpha _{n}}$ являются (не обязательно различными) числами, и предположим для простоты записи, что одинаковые значения входят в непрерывную последовательность в списке. То есть

${\displaystyle \alpha _{1}=\cdots =\alpha _{m_{1}},\alpha _{m_{1}+1}=\cdots =\alpha _{m_{2}},\ldots ,\alpha _{m_{k-1}+1}=\cdots =\alpha _{m_{k}}}$

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

${\displaystyle {\begin{cases}p(\alpha _{1})=\beta _{1},&p'(\alpha _{1})=\beta _{2},&\ldots ,&p^{(m_{1}-1)}(\alpha _{1})=\beta _{m_{1}}\\p(\alpha _{m_{1}+1})=\beta _{m_{1}+1},&p'(\alpha _{m_{1}+1})=\beta _{m_{1}+2},&\ldots ,&p^{(m_{2}-m_{1}-1)}(\alpha _{m_{2}})=\beta _{m_{2}}\\\qquad \vdots \\p(\alpha _{m_{k-1}+1})=\beta _{m_{k-1}+1},&p'(\alpha _{m_{k-1}+2})=\beta _{m_{k-1}+2},&\ldots ,&p^{(m_{k}-m_{k-1}-1)}(\alpha _{m_{k}})=\beta _{m_{k}}\end{cases}}}$

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

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

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

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

Смотрите также

• Полином Шура - обобщение
• Альтернантная матрица
• Полином Лагранжа
• Вронскиан
• Список матриц
• Определитель Мура над конечным полем
• Формулы Виета

Рекомендации

1. Роджер А. Хорн и Чарльз Р. Джонсон (1991), Темы матричного анализа, Издательство Кембриджского университета. См. Раздел 6.1..
2. Матрица DFT, https://en.wikipedia.org/wiki/DFT_matrix
3. Тернер, Л. Ричард (август 1966 г.). Обратная матрица Вандермонда с приложениями (PDF).
4. Macon, N .; А. Шпицбарт (февраль 1958 г.). "Обратные матрицы Вандермонда". Американский математический ежемесячник. 65 (2): 95–100. Дои:10.2307/2308881. JSTOR  2308881.
5. "Обратная матрица Вандермонда". 2018.
6. Франсуа Виэте (1540-1603), формулы Виета, https://en.wikipedia.org/wiki/Vieta%27s_formulas
7. Нажмите, WH; Теукольский С.А.; Феттерлинг, штат Вашингтон; Фланнери, ВР (2007). «Раздел 2.8.1. Матрицы Вандермонда». Числовые рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN  978-0-521-88068-8.
8. Инверсия матрицы Вандермонда (2018),https://proofwiki.org/wiki/Inverse_of_Vandermonde_Matrix
9. Фултон, Уильям; Харрис, Джо (1991). Теория представлений. Первый курс. Тексты для выпускников по математике, Чтения по математике. 129. Нью-Йорк: Springer-Verlag. Дои:10.1007/978-1-4612-0979-9. ISBN  978-0-387-97495-8. МИСТЕР  1153249. OCLC  246650103. В лекции 4 рассматривается теория представлений симметрических групп, в том числе роль определителя Вандермонда..

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

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

внешняя ссылка

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