Vandermonde meghatározó

A Vandermonde -determináns a determináns

{\begin{vmatrix}1&x_{1}&\lpontok &x_{1}^{{n-1}}\\1&x_{2}&\lpontok &x_{2}^{{n-1}}\\\vpontok &\vpontok &\dpontok &\vpontok \\1&x_{n}&\lpontok &x_{n}^{{n-1}}\\\end{vmatrix}}\ \ =\prod _{{1\leq j <i\leq n}}\!(x_{i}-x_{j}),

Alexandre Theophile Vandermonde francia matematikusról nevezték el . [1] Ez a képlet azt mutatja, hogy a Vandermonde-determináns akkor és csak akkor egyenlő nullával, ha létezik legalább egy olyan pár , amely . $\left(x_{i},x_{j}\jobb)$ $x_{i}=x_{j},i\neq j$

Bizonyítás

Bizonyítás indukcióval

Mátrix méret indukció . $m$

alapindukció

$m=2$ . Ebben az esetben a mátrix az

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

Nyilvánvaló, hogy a meghatározója . $x_{2}-x_{1}$

Induktív feltételezés

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

induktív átmenet

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

Vonja ki az utolsó oszlopból az utolsó előtti, szorozva -vel , az -edik - -edikből, szorozva -val, az -edik - -edikből, szorozva -val, és így tovább minden oszlop esetében. Ezek a transzformációk nem változtatják meg a mátrix determinánst. Kap $x_{1}$ $m-2$ $m-3$ $x_{1}$ $én$ $i-1$ $x_{1}$

{\begin{vmatrix}1&0&0&\pontok &0\\1&x_{2}-x_{1}&x_{2}(x_{2}-x_{1})&\pontok &x_{2}^{{m-2} }(x_{2}-x_{1})\\.&.&.&.&.\\1&x_{{m}}-x_{1}&x_{{m}}(x_{{m}}- x_{1})&\pontok &x_{{m}}^{{m-2}}(x_{{m}}-x_{1})\\\end{vmátrix}}

Ezt a determinánst kiterjesztve az első sor elemeire, azt kapjuk, hogy egyenlő a következő determinánssal:

{\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})&\pontok &x_{{m}}^{{m-2}}(x_{{m}}-x_{1})\\\end{vmátrix}}

Minden 1- től a -edik sor szorzójának kivételéhez . Kap $én$ $m-1$ $én$ $x_{{i+1}}-x_{1}$

(x_{2}-x_{1})(x_{3}-x_{1})\pontok (x_{{m}}-x_{1}){\begin{vmatrix}1&x_{2}&\pontok &x_{2}^{{m-2}}\\.&.&.&.\\1&x_{{m}}&\pontok &x_{{m}}^{{m-2}}\\\end {vmátrix}}

Az indukciós hipotézisből ismert előző képletben szereplő determináns értékét behelyettesítjük:

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

■

Bizonyítás a hatalom összehasonlításával

Egy másik bizonyítást nyerhetünk, ha feltételezzük, hogy ezek a polinomgyűrű változói . Ebben az esetben a Vandermonde-determináns egy változók polinomja. Monomokból áll, amelyek mindegyikének foka egyenlő -vel . Tehát a fokozat ugyanaz a szám. $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$

Vegye figyelembe, hogy ha néhány és egybeesik, akkor a determináns nulla, mivel a mátrixban két azonos sor jelenik meg. Ezért a determinánsnak mint polinomnak oszthatónak kell lennie -vel . Összességében különböző párok és (for ) léteznek , ami egyenlő a mértékével . Más szóval, osztható különböző fokú polinomokkal . Ezért egyenlő a szorzatukkal egy állandóig. De amint a zárójelek kinyitásával látható, az állandó egyenlő eggyel. [2 ] $x_{i}$ $x_{j}$ $(x_{i}-x_{j})$ $x_{i}$ $x_{j}$ $i>j$ $0+1+\lpont +(n-1)$ $V$ $V$ $\deg V$ $egy$

Tulajdonságok

A Vandermonde mátrix egy speciális esete egy alternatív mátrixnak , amelyben . $f_{i}(\alpha )=\alpha ^{{i-1}}$

Ha az egység primitív gyöke , és egy Vandermonde-mátrix elemekkel , akkor az inverz mátrix egy átlós mátrixig a következő formában van : . $\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$

Alkalmazás

A Vandermonde-determinánsnak számos alkalmazása van a matematika különböző területein. Például, ha megoldjuk a polinomokkal történő interpoláció problémáját , vagyis egy olyan fokszámú polinom megtalálásának problémáját, amelynek gráfja a sík adott pontjain abszciszákkal megy át , akkor a Vandermonde-determináns egy lineáris egyenletrendszer determinánsaként adódik . amelyekben megtaláljuk a kívánt polinom ismeretlen együtthatóit. [3] $n-1$ $n$ $x_{1},\ldots ,x_{{n}}$

Vektor gyors szorzása Vandermonde-mátrixszal

Egy vektor Vandermonde-mátrixszal való gyors szorzása egyenértékű egy polinom értékeinek megtalálásával, és műveletekkel számítható ki , ahol két polinom szorzásának költsége. [4] A polinom értékeinek gyors megtalálásának módszere azon a tényen alapul, hogy . A polinomok gyorsszorzó algoritmusa (valamint annak módosítása, a modulo polinom felvételének művelete), mint például a Schönhage-Strassen szorzási módszer, az oszd meg és uralkodj paradigmát alkalmazva polinomok (és modulo polinomok műveletei) szorzásához épül egy fa, melynek levelei polinomok (értékek ) , a fa gyökere pedig polinom . [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)))))$

Jegyzetek

↑ Alexandre-Théophile Vandermonde Archiválva : 2013. január 5., a Wayback Machine (orosz) .
↑ Ian Stewart Galois elmélet, harmadik kiadás, 28. o., Chapman & Hall/CRC Mathematics.
↑ Shafarevich I. R., Remizov A. O. Lineáris algebra és geometria, ch. II, par. 4, - Fizmatlit, Moszkva, 2009.
↑ Hatékony számítás strukturált mátrixokkal és aritmetikai kifejezésekkel . Letöltve: 2017. január 24. Az eredetiből archiválva : 2017. február 2.. (határozatlan)
↑ Polinom algoritmusok . Letöltve: 2017. január 24. Az eredetiből archiválva : 2017. január 10. (határozatlan)

Irodalom

Kurosh A. G. A magasabb algebra tanfolyama. - M .: Nauka 1968.
Iljin V. A., Poznyak E. G. Lineáris algebra. - M .: Tudomány - Fizmatlit, 1999.
Shafarevich I. R. , Remizov A. O. Lineáris algebra és geometria, Fizmatlit, Moszkva, 2009.