Vandermonden determinantti

Vandermonden determinantti on determinantti

{\begin{vmatrix}1&x_{1}&\lpisteet &x_{1}^{{n-1}}\\1&x_{2}&\ldots &x_{2}^{{n-1}}\\\vpisteet &\vpisteet &\dpisteet &\vpisteet \\1&x_{n}&\lpisteet &x_{n}^{{n-1}}\\\end{vmatrix}}\ \ =\prod _{{1\leq j <i\leq n}}\!(x_{i}-x_{j}),

Nimetty ranskalaisen matemaatikon Alexandre Theophile Vandermonden mukaan . [1] Tämä kaava osoittaa, että Vandermonde-determinantti on yhtä suuri kuin nolla, jos ja vain jos on olemassa vähintään yksi pari siten, että . $\vasen(x_{i},x_{j}\oikea)$ $x_{i}=x_{j},i\neq j$

Todiste

Todistus induktiolla

Matriisikoon induktio . $m$

perusinduktio

$m = 2$ . Tässä tapauksessa matriisi on

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

Ilmeisesti sen määräävä tekijä on . $x_{2}-x_{1}$

Induktiivinen oletus

{\begin{vmatrix}1&x_{1}&x_{1}^{2}&\pisteet &x_{1}^{{m-2}}\\1&x_{2}&x_{2}^{2}&\pisteet &x_{2}^{{m-2}}\\.&.&.&.&.\\1&x_{{m-1}}&x_{{m-1}}^{2}&\pisteet &x_{ {m-1}}^{{m-2}}\\\end{vmatrix}}=\prod \limits _{{1\leqslant i<j\leqslant m-1}}(x_{j}-x_ {i})

induktiivinen siirtymä

{\begin{vmatrix}1&x_{1}&x_{1}^{2}&\pisteet &x_{1}^{{m-1}}\\1&x_{2}&x_{2}^{2}&\pisteet &x_{2}^{{m-1}}\\.&.&.&.&.\\1&x_{{m}}&x_{{{m}}^{2}&\pisteet &x_{{m}} ^{{m-1}}\\\end{vmatrix}}

Vähennä viimeisestä sarakkeesta toiseksi viimeinen, kerrottuna -th - -th , kerrottuna -th - -th , kerrottuna -th - -th, kerrottuna ja niin edelleen kaikille sarakkeille. Nämä muunnokset eivät muuta matriisideterminanttia. Saada $x_{1}$ $m-2$ $m-3$ $x_{1}$ $i$ $i-1$ $x_{1}$

{\begin{vmatrix}1&0&0&\pisteet &0\\1&x_{2}-x_{1}&x_{2}(x_{2}-x_{1})&\pisteet &x_{2}^{{m-2} }(x_{2}-x_{1})\\.&.&.&.&.\\1&x_{{m}}-x_{1}&x_{{m}}(x_{{m}}- x_{1})&\pisteet &x_{{m}}^{{m-2}}(x_{{m}}-x_{1})\\\end{vmatrix}}

Laajentamalla tätä determinanttia ensimmäisen rivin elementtien päälle, saadaan, että se on yhtä suuri kuin seuraava determinantti:

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

Kaikille luvusta 1 kertoimen poistamiseksi riviltä - . Saada $i$ $m-1$ $i$ $x_{{i+1}}-x_{1}$

(x_{2}-x_{1})(x_{3}-x_{1})\pisteet (x_{{m}}-x_{1}){\begin{vmatrix}1&x_{2}&\pisteet &x_{2}^{{m-2}}\\.&.&.&.\\1&x_{{m}}&\pisteet &x_{{m}}^{{m-2}}\\\end {vmatrix}}

Korvaamme determinantin arvon edellisessä kaavassa, joka tunnetaan induktiohypoteesista:

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

■

Todistus valtuuksien vertailulla

Toinen todiste voidaan saada olettamalla, että ne ovat muuttujia polynomirenkaassa . Tässä tapauksessa Vandermonden determinantti on muuttujien polynomi. Se koostuu monomeista, joiden kunkin aste on yhtä suuri kuin . Joten tutkinto on sama luku. $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$

Huomaa, että jos jotkut ja ovat samat, niin determinantti on yhtä suuri kuin nolla, koska matriisissa on kaksi identtistä riviä. Siksi determinantin polynomina on oltava jaollinen . Yhteensä eri pareja ja (for ) olemassa , joka on yhtä suuri kuin aste . Toisin sanoen, on jaollinen eri astepolynomeilla . Siksi se on yhtä suuri kuin heidän tuotteensa vakioon asti. Mutta kuten voit nähdä avaamalla sulut, vakio on yhtä suuri kuin yksi. [2 ] $x_{i}$ $x_{j}$ $(x_{i}-x_{j})$ $x_{i}$ $x_{j}$ $i>j$ $0+1+\lpisteet +(n-1)$ $V$ $V$ $\deg V$ $yksi$

Ominaisuudet

Vandermonde-matriisi on erikoistapaus vaihtoehtoisesta matriisista , jossa . $f_{i}(\alpha )=\alpha ^{{i-1}}$

Jos on primitiivinen ykkösjuuri ja se on Vandermonde-matriisi elementteineen , niin käänteismatriisilla diagonaalimatriisiin asti on muoto : . $\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$

Sovellus

Vandermonde-determinantilla on lukuisia sovelluksia matematiikan eri alueilla. Esimerkiksi, kun ratkaistaan polynomien interpoloinnin ongelma , eli ongelma löytää astepolynomi, jonka kuvaaja kulkee tason tiettyjen pisteiden läpi abskissoilla , Vandermonden determinantti syntyy lineaarisen yhtälöjärjestelmän determinanttina , mistä josta löydetään halutun polynomin tuntemattomat kertoimet. [3] $n-1$ $n$ $x_{1},\ldots ,x_{{n}}$

Vektorin nopea kertominen Vandermonde-matriisilla

Vektorin nopea kertominen Vandermonde-matriisilla vastaa polynomin arvojen löytämistä ja voidaan laskea operaatioissa, joissa on kahden polynomin kertomisen hinta. [4] Menetelmä polynomin arvojen nopeaan löytämiseen perustuu siihen, että . Nopean kertolaskualgoritmin käyttäminen polynomille (sekä sen muuntaminen, modulo-polynomin ottaminen), kuten Schönhage-Strassenin kertolaskumenetelmä, jakaa ja hallitse -paradigmaa soveltamalla polynomien kertomiseen (ja operaatioihin modulopolynomien) rakennetaan puu, jonka lehdet ovat polynomeja (arvoja ) ja puun juuri on polynomi . [5] ${\näyttötyyli (a_{0},\pisteet ,a_{n})^{t))$ $n$ $x_{i}$ ${\displaystyle f(x)=a_{0}+a_{1}x+\ldots +a_{n}x^{n))$ $O(\log(n)\cdot M(n))$ $M(n)$ $n$ ${\displaystyle 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)))))$

Muistiinpanot

↑ Alexandre-Théophile Vandermonde Arkistoitu 5. tammikuuta 2013 Wayback Machinessa (venäjäksi) .
↑ Ian Stewart Galois Theory, kolmas painos, s. 28, Chapman & Hall/CRC Mathematics.
↑ Shafarevich I. R., Remizov A. O. Lineaarinen algebra ja geometria, ch. II, par. 4, - Fizmatlit, Moskova, 2009.
↑ Tehokas laskenta strukturoiduilla matriiseilla ja aritmeettisilla lausekkeilla . Haettu 24. tammikuuta 2017. Arkistoitu alkuperäisestä 2. helmikuuta 2017. (määrätön)
↑ Polynomialgoritmit . Haettu 24. tammikuuta 2017. Arkistoitu alkuperäisestä 10. tammikuuta 2017. (määrätön)

Kirjallisuus

Kurosh A. G. Korkeamman algebran kurssi. - M .: Nauka 1968.
Ilyin V. A., Poznyak E. G. Lineaarinen algebra. - M .: Tiede - Fizmatlit, 1999.
Shafarevich I. R. , Remizov A. O. Lineaarinen algebra ja geometria, Fizmatlit, Moskova, 2009.