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

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

${\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}),$

названный в честь французского математика Александра Теофила Вандермонда. Данная формула показывает, что определитель Вандермонда равен нулю тогда и только тогда, когда существует хотя бы одна пара $\left(x_i,x_j\right)$$\left(x_{i},x_{j}\right)$ такая, что $x_i=x_j,i\ne <!--\; \ne \; -->j$$x_{i}=x_{j},i\neq j$.

ДоказательствоПравить

Доказательство по индукции

Индукция по размеру матрицы $m$$m$ .

База индукции

$m=2$$m=2$ . В данном случае матрица представляет собой

$V_{2}={\begin{bmatrix}1&x_{1}\\1&x_{2}\\\end{bmatrix}}$ 

Очевидно, её определитель равен $x_2-<!--\; -\; -->x_1$$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$$x_{1}$ , из $m-<!--\; -\; -->2$$m-2$ -го — $m-<!--\; -\; -->3$$m-3$ -й, умноженный на $x_1$$x_{1}$ , из $i$$i$ -го — $i-<!--\; -\; -->1$$i-1$ -й, умноженный на $x_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$$i$  от 1 до $m-<!--\; -\; -->1$$m-1$  вынесем из $i$$i$ -й строки множитель $x_{i+1}-<!--\; -\; -->x_1$$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,\dots <!--\; \dots \; -->,x_n$$x_{1},\ldots ,x_{n}$  являются переменными в кольце многочленов $\mathbb{C}[x_1,\dots <!--\; \dots \; -->,x_n]$${{\mathbb C}}[x_{1},\ldots ,x_{n}]$ . В этом случае определитель Вандермонда — это многочлен $V$$V$  от $n$$n$  переменных. Он состоит из одночленов, степень каждого из которых равна $0+1+\dots <!--\; \dots \; -->+(n-<!--\; -\; -->1)=\frac{n(n-<!--\; -\; -->1)}{2}$$0+1+\ldots +(n-1)={\frac {n(n-1)}2}$ . Значит, степень $V$$V$  равна тому же числу.

Заметим, что если какие-то $x_i$$x_{i}$  и $x_j$$x_{j}$  совпадают, то определитель равен нулю, поскольку в матрице появляются две одинаковые строки. Поэтому определитель как многочлен должен делиться на $(x_i-<!--\; -\; -->x_j)$$(x_{i}-x_{j})$ . Всего различных пар $x_i$$x_{i}$  и $x_j$$x_{j}$  (при $i>j$$i>j$ ) существует $0+1+\dots <!--\; \dots \; -->+(n-<!--\; -\; -->1)$$0+1+\ldots +(n-1)$ , что равно степени $V$$V$ . Иными словами, $V$$V$  делится на $\mathrm{deg}<!--\; \; -->V$$\deg V$  различных многочленов степени $1$$1$ . Значит, он равен их произведению с точностью до константы. Но, как можно убедиться, раскрыв скобки, константа равна единице. ■

СвойстваПравить

Матрица Вандермонда представляет собой частный случай альтернативной матрицы, в которой $f_i(\mathrm{\alpha <!--\; \alpha \; -->})={\mathrm{\alpha <!--\; \alpha \; -->}}^{i-<!--\; -\; -->1}$$f_{i}(\alpha )=\alpha ^{{i-1}}$ .

Если $\mathrm{\zeta <!--\; \zeta \; -->}$$\zeta$  — первообразный корень $n$$n$ -й степени из единицы и $A=(a_{i,j})$$A=(a_{{i,j}})$  — матрица Вандермонда с элементами $a_{i,j}={\mathrm{\zeta <!--\; \zeta \; -->}}^{ij}$$a_{{i,j}}=\zeta ^{{ij}}$ , то обратная матрица $B=({\stackrel{~<!--\; ~\; -->}{a}}_{i,j})$$B=({\tilde {a}}_{{i,j}})$  с точностью до диагональной матрицы имеет вид ${\stackrel{~<!--\; ~\; -->}{a}}_{i,j}={\mathrm{\zeta <!--\; \zeta \; -->}}^{-<!--\; -\; -->ij}$${\tilde {a}}_{{i,j}}=\zeta ^{{-ij}}$ : $AB=n\cdot <!--\; \cdot \; -->E$$AB=n\cdot E$ .

ПрименениеПравить

Определитель Вандермонда имеет многочисленные применения в разных областях математики. Например, при решении задачи интерполяции многочленами, то есть задачи о нахождении многочлена степени $n-<!--\; -\; -->1$$n-1$ , график которого проходит через $n$$n$  заданных точек плоскости с абсциссами $x_1,\dots <!--\; \dots \; -->,x_n$$x_{1},\ldots ,x_{{n}}$ , определитель Вандермонда возникает как определитель системы линейных уравнений, из которой находятся неизвестные коэффициенты искомого многочлена.

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

Быстрое умножение вектора $(a_0,\dots <!--\; \dots \; -->,a_n{)}^t$$(a_{0},\dots ,a_{n})^{t}$  на матрицу Вандермонда эквивалентно нахождению $n$$n$  значений $x_i$$x_{i}$  многочлена $f(x)=a_0+a_{1}x+\dots <!--\; \dots \; -->+a_n{x}^n$$f(x)=a_{0}+a_{1}x+\ldots +a_{n}x^{n}$  и может быть вычислено за $O(\log <!--\; \; -->(n)\cdot <!--\; \cdot \; -->M(n))$$O(\log(n)\cdot M(n))$  операций, где $M(n)$$M(n)$  — затраты на умножения двух полиномов. Метод быстрого нахождения $n$$n$  значений многочлена строится на том факте, что $f(x_i)\equiv <!--\; \equiv \; -->a_0+a_{1}x+\dots <!--\; \dots \; -->+a_n{x}^n(\mathrm{mod}x-<!--\; -\; -->x_i)$$f(x_{i})\equiv a_{0}+a_{1}x+\ldots +a_{n}x^{n}{\pmod {x-x_{i}}}$ . Используя алгоритм быстрого умножения многочленов (а также его модификацию операцию взятия по модулю многочлена), такой как Метод умножения Шёнхаге — Штрассена, применив парадигму разделяй и властвуй, за $O(\log <!--\; \; -->(n))$$O(\log(n))$  умножений многочленов (и операций по модулю многочленов) строится дерево, листьями которого будут многочлены (значения) $f(x)mod(x-<!--\; -\; -->x_i)$$f(x)\,{\bmod {\,}}(x-x_{i})$ , а корнем дерева будет многочлен $f(x)mod(x-<!--\; -\; -->x_1)(x-<!--\; -\; -->x_2)\cdots <!--\; \cdots \; -->(x-<!--\; -\; -->x_n)$$f(x)\,{\bmod {\,}}{(x-x_{1})(x-x_{2})\cdots (x-x_{n})}$ .

ЛитератураПравить

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