Determinant Vandermonde

Determinantul Vandermonde este determinantul

{\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 _{{1\leq j <i\leq n}}\!(x_{i}-x_{j}),

numit după matematicianul francez Alexandre Theophile Vandermonde . [1] Această formulă arată că determinantul Vandermonde este egal cu zero dacă și numai dacă există cel puțin o pereche astfel încât . $\left(x_{i},x_{j}\right)$ $x_{i}=x_{j},i\neq j$

Dovada

Dovada prin inducție

Inducerea dimensiunii matricei . $m$

inductia de baza

$m=2$ . În acest caz, matricea este

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

Evident, determinantul său este . $x_{2}-x_{1}$

Ipoteza inductivă

{\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}&\puncte &x_{ {m-1}}^{{m-2}}\\\end{vmatrix}}=\prod \limits _{{1\leqslant i<j\leqslant m-1}}(x_{j}-x_ {i})

tranziție inductivă

{\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}}

Scădeți din ultima coloană penultima, înmulțită cu , din -a - -lea, înmulțită cu , din -a - -lea, înmulțită cu și așa mai departe pentru toate coloanele. Aceste transformări nu modifică determinantul matricei. obține $x_{1}$ $m-2$ $m-3$ $x_{1}$ $i$ $i-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}}

Expandând acest determinant peste elementele primului rând, obținem că este egal cu următorul determinant:

{\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})&\puncte &x_{{m}}^{{m-2}}(x_{{m}}-x_{1})\\\end{vmatrix}}

Pentru toate de la 1 pentru a scoate multiplicatorul de pe linia --a . obține $i$ $m-1$ $i$ $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}}

Înlocuim valoarea determinantului în formula anterioară, cunoscută din ipoteza de inducție:

(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})

■

Dovada prin comparație de puteri

O altă demonstrație poate fi obținută presupunând că acestea sunt variabile în inelul polinomial . În acest caz, determinantul Vandermonde este un polinom în variabile. Este alcătuit din monomii, gradul fiecăruia fiind egal cu . Deci, gradul este același număr. $x_{1},\ldots ,x_{n}$ ${{\mathbb C}}[x_{1},\ldots ,x_{n}]$ $V$ $n$ $0+1+\ldots +(n-1)={\frac {n(n-1)}2}$ $V$

Rețineți că, dacă unele și coincid, atunci determinantul este egal cu zero, deoarece în matrice apar două rânduri identice. Prin urmare, determinantul ca polinom trebuie să fie divizibil cu . În total, există perechi diferite și (pentru ) , ceea ce este egal cu gradul de . Cu alte cuvinte, este divizibil cu polinoame de diferite grade . Prin urmare, este egal cu produsul lor până la o constantă. Dar, după cum puteți vedea prin deschiderea parantezelor, constanta este egală cu unu. [2 ] $x_{i}$ $x_{j}$ $(x_{i}-x_{j})$ $x_{i}$ $x_{j}$ $i>j$ $0+1+\ldots +(n-1)$ $V$ $V$ $\deg V$ $unu$

Proprietăți

Matricea Vandermonde este un caz special al unei matrice alternative în care . $f_{i}(\alpha )=\alpha ^{{i-1}}$

Dacă este o rădăcină primitivă a unității și este o matrice Vandermonde cu elemente , atunci matricea inversă până la o matrice diagonală are forma : . $\zeta$ $n$ $A=(a_{{i,j}})$ $a_{{i,j}}=\zeta ^{{ij}}$ $B=({\tilde {a}}_{{i,j}})$ ${\tilde {a}}_{{i,j}}=\zeta ^{{-ij}}$ $AB=n\cdot E$

Aplicație

Determinantul Vandermonde are numeroase aplicații în diferite domenii ale matematicii. De exemplu, la rezolvarea problemei interpolării prin polinoame , adică problema găsirii unui polinom de grad al cărui grafic trece prin puncte date ale planului cu abscise , determinantul Vandermonde apare ca determinant al unui sistem de ecuații liniare , din pe care se găsesc coeficienţii necunoscuţi ai polinomului dorit. [3] $n-1$ $n$ $x_{1},\ldots ,x_{{n}}$

Înmulțirea rapidă a unui vector cu o matrice Vandermonde

Înmulțirea rapidă a unui vector cu o matrice Vandermonde este echivalentă cu găsirea valorilor unui polinom și poate fi calculată în operații, unde este costul înmulțirii a două polinoame. [4] Metoda de găsire rapidă a valorilor unui polinom se bazează pe faptul că . Folosind algoritmul de înmulțire rapidă pentru polinoame (precum și modificarea acestuia, operația de a lua modulo un polinom), cum ar fi metoda de înmulțire Schönhage-Strassen, aplicând paradigma împărțire și cuceri , pentru înmulțiri de polinoame (și operații modulo polinoame) se construiește un arbore, ale cărui frunze sunt polinoame (valori) , iar rădăcina arborelui este un polinom . [5] $(a_{0},\dots, a_{n})^{t)$ $n$ $x_{i}$ $f(x)=a_{0}+a_{1}x+\ldots +a_{n}x^{n)$ $O(\log(n)\cdot M(n))$ $M(n)$ $n$ $f(x_{i})\equiv a_{0}+a_{1}x+\ldots +a_{n}x^{n}{\pmod {x-x_{i)))$ $O(\log(n))$ $f(x)\,{\bmod {\,}}(x-x_{i})$ ${\displaystyle f(x)\,{\bmod {\,)){(x-x_{1})(x-x_{2})\cdots (x-x_{n)))))$

Note

↑ Alexandre-Théophile Vandermonde Arhivat 5 ianuarie 2013 la Wayback Machine (rusă) .
↑ Ian Stewart Galois Theory, Ediția a treia, p. 28, Chapman & Hall/CRC Mathematics.
↑ Şafarevici I. R., Remizov A. O. Algebră liniară şi geometrie, cap. II, alin. 4, - Fizmatlit, Moscova, 2009.
↑ Calcul eficient cu matrici structurate și expresii aritmetice . Preluat la 24 ianuarie 2017. Arhivat din original la 2 februarie 2017. (nedefinit)
↑ Algoritmi polinomi . Preluat la 24 ianuarie 2017. Arhivat din original la 10 ianuarie 2017. (nedefinit)

Literatură

Kurosh A. G. Curs de algebră superioară. - M .: Nauka 1968.
Ilyin V. A., Poznyak E. G. Algebră liniară. - M .: Știință - Fizmatlit, 1999.
Shafarevich I. R. , Remizov A. O. Linear Algebra and Geometry, Fizmatlit, Moscova, 2009.