Vandermonde determinant

Vandermonde- determinanten är determinanten

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

uppkallad efter den franske matematikern Alexandre Theophile Vandermonde . [1] Denna formel visar att Vandermonde-determinanten är lika med noll om och endast om det finns minst ett par så att . $\left(x_{i},x_{j}\right)$ $x_{i}=x_{j},i\neq j$

Bevis

Bevis genom induktion

Matrisstorleksinduktion . $m$

basinduktion

$m=2$ . I det här fallet är matrisen

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

Uppenbarligen är dess bestämningsfaktor . $x_{2}-x_{1}$

Induktivt antagande

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

induktiv övergång

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

Subtrahera från den sista kolumnen den näst sista, multiplicerad med , från -th - -th, multiplicerad med , från -th - -th, multiplicerad med och så vidare för alla kolumner. Dessa transformationer ändrar inte matrisdeterminanten. Skaffa sig $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}}

Om vi expanderar denna determinant över elementen i den första raden får vi att den är lika med följande 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})&\dots &x_{{m}}^{{m-2}}(x_{{m}}-x_{1})\\\end{vmatrix}}

För alla från 1 att ta ut multiplikatorn från den -: e raden . Skaffa sig $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}}

Vi ersätter värdet på determinanten i föregående formel, känd från induktionshypotesen:

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

■

Bevis genom jämförelse av befogenheter

Ett annat bevis kan erhållas genom att anta att de är variabler i polynomringen . I det här fallet är Vandermonde-determinanten ett polynom i variabler. Den består av monomialer, var och en av dem är lika med . Så graden är samma siffra. $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$

Observera att om några och sammanfaller, så är determinanten lika med noll, eftersom två identiska rader visas i matrisen. Därför måste determinanten som polynom vara delbar med . Totalt finns olika par och (för ) , vilket är lika med graden av . Med andra ord är den delbar med polynom i olika grad . Därför är det lika med deras produkt upp till en konstant. Men som du kan se genom att öppna parenteserna är konstanten lika med en. [2 ] $x_{i}$ $x_{j}$ $(x_{i}-x_{j})$ $x_{i}$ $x_{j}$ $i>j$ $0+1+\ldots +(n-1)$ $V$ $V$ $\deg V$ $ett$

Egenskaper

Vandermonde-matrisen är ett specialfall av en alternativ matris där . $f_{i}(\alpha )=\alpha ^{{i-1}}$

Om är en primitiv th rot av enhet och är en Vandermonde-matris med element , då har den inversa matrisen upp till en diagonal matris formen : . $\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$

Applikation

Vandermonde-determinanten har många tillämpningar inom olika områden av matematik. Till exempel, när man löser problemet med interpolation med polynom , det vill säga problemet med att hitta ett polynom av grad vars graf passerar genom givna punkter i planet med abskiss , uppstår Vandermonde-determinanten som en determinant av ett system av linjära ekvationer , från vilka de okända koefficienterna för det önskade polynomet hittas. [3] $n-1$ $n$ $x_{1},\ldots ,x_{{n}}$

Snabb multiplikation av en vektor med en Vandermonde-matris

Snabb multiplikation av en vektor med en Vandermonde-matris är ekvivalent med att hitta värdena för ett polynom och kan beräknas i operationer, där är kostnaden för att multiplicera två polynom. [4] Metoden för att snabbt hitta värdena för ett polynom är baserad på det faktum att . Använda den snabba multiplikationsalgoritmen för polynom (liksom dess modifiering, operationen att ta modulo ett polynom), såsom Schönhage-Strassen-metoden för multiplikation, applicering av divide and conquer -paradigmet , för multiplikationer av polynom (och operationer modulo polynom) ett träd är byggt, vars löv är polynom (värden ) , och trädets rot är ett polynom . [5] ${\displaystyle (a_{0},\dots,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))))))$

Anteckningar

↑ Alexandre-Théophile Vandermonde Arkiverad 5 januari 2013 på Wayback Machine (ryska) .
↑ Ian Stewart Galois Theory, tredje upplagan, s. 28, Chapman & Hall/CRC Mathematics.
↑ Shafarevich I. R., Remizov A. O. Linjär algebra och geometri, kap. II, par. 4, - Fizmatlit, Moskva, 2009.
↑ Effektiv beräkning med strukturerade matriser och aritmetiska uttryck . Hämtad 24 januari 2017. Arkiverad från originalet 2 februari 2017. (obestämd)
↑ Polynomalgoritmer . Hämtad 24 januari 2017. Arkiverad från originalet 10 januari 2017. (obestämd)

Litteratur

Kurosh A. G. Kurs i högre algebra. - M .: Nauka 1968.
Ilyin V. A., Poznyak E. G. Linjär algebra. - M .: Science - Fizmatlit, 1999.
Shafarevich I. R. , Remizov A. O. Linjär algebra och geometri, Fizmatlit, Moskva, 2009.