Vandermondův determinant

Vandermondův determinant je determinant

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

pojmenovaný po francouzském matematikovi Alexandru Theophile Vandermondovi . [1] Tento vzorec ukazuje, že Vandermondův determinant je roven nule právě tehdy, když existuje alespoň jeden pár takový, že . $\left(x_{i},x_{j}\right)$ $x_{i}=x_{j},i\neq j$

Důkaz

Důkaz indukcí

Indukce velikosti matice . $m$

základní indukce

$m=2$ . V tomto případě je matice

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

Je zřejmé, že jeho determinantem je . $x_{2}-x_{1}$

Indukční předpoklad

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

indukční přechod

{\begin{vmatrix}1&x_{1}&x_{1}^{2}&\tečky &x_{1}^{{m-1}}\\1&x_{2}&x_{2}^{2}&\tečky &x_{2}^{{m-1}}\\.&.&.&.&.\\1&x_{{m}}&x_{{m}}^{2}&\tečky &x_{{m}} ^{{m-1}}\\\end{vmatrix}}

Odečtěte od posledního sloupce předposlední, vynásobený , od -th - -th, násobený , od -th - -th, násobený a tak dále pro všechny sloupce. Tyto transformace nemění determinant matice. Dostat $x_{1}$ $m-2$ $m-3$ $x_{1}$ $i$ $i-1$ $x_{1}$

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

Rozšířením tohoto determinantu o prvky prvního řádku dostaneme, že se rovná následujícímu determinantu:

{\begin{vmatrix}x_{2}-x_{1}&x_{2}(x_{2}-x_{1})&\tečky &x_{2}^{{m-2}}(x_{2} -x_{1})\\.&.&.&.\\x_{{m}}-x_{1}&x_{{m}}(x_{{m}}-x_{1})&\tečky &x_{{m}}^{{m-2}}(x_{{m}}-x_{1})\\\end{vmatrix}}

Pro všechny od 1 vyjměte násobitel z -tého řádku . Dostat $i$ $m-1$ $i$ $x_{{i+1}}-x_{1}$

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

Dosadíme hodnotu determinantu do předchozího vzorce, známého z indukční hypotézy:

(x_{2}-x_{1})(x_{3}-x_{1})\tečky (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})

■

Důkaz porovnáním sil

Další důkaz lze získat za předpokladu, že se jedná o proměnné v polynomickém kruhu . V tomto případě je Vandermondův determinant polynom v proměnných. Skládá se z monočlenů, jejichž stupeň je roven . Takže stupeň je stejné číslo. $x_{1},\ldots ,x_{n}$ ${{\mathbb C}}[x_{1},\ldots ,x_{n}]$ $PROTI$ $n$ $0+1+\ldots +(n-1)={\frac {n(n-1)}2}$ $PROTI$

Všimněte si, že pokud se některé a shodují, pak je determinant roven nule, protože v matici se objevují dva stejné řádky. Proto musí být determinant jako polynom dělitelný . Celkem existují různé páry a (pro ) , což se rovná stupni . Jinými slovy, je dělitelné polynomy různého stupně . Proto se rovná jejich součinu až do konstanty. Jak ale můžete vidět otevřením závorek, konstanta je rovna jedné. [2 ] $x_{i}$ $x_{j}$ $(x_{i}-x_{j})$ $x_{i}$ $x_{j}$ $i>j$ $0+1+\ldots +(n-1)$ $PROTI$ $PROTI$ $\deg V$ $jeden$

Vlastnosti

Vandermondova matice je speciálním případem alternativní matice, ve které . $f_{i}(\alpha )=\alpha ^{{i-1}}$

Jestliže je primitivní th odmocnina jednoty a je to Vandermondova matice s prvky , pak má inverzní matice až k diagonální matici tvar : . $\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$

Aplikace

Vandermondův determinant má četné aplikace v různých oblastech matematiky. Například při řešení úlohy interpolace polynomy , tedy problému nalezení polynomu stupně, jehož graf prochází danými body roviny s úsečkami , vzniká Vandermondův determinant jako determinant soustavy lineárních rovnic , z kterým se najdou neznámé koeficienty požadovaného polynomu. [3] $n-1$ $n$ $x_{1},\ldots ,x_{{n}}$

Rychlé násobení vektoru Vandermondovou maticí

Rychlé násobení vektoru Vandermondovou maticí je ekvivalentní nalezení hodnot polynomu a lze jej vypočítat v operacích, kde jsou náklady na násobení dvou polynomů. [4] Metoda rychlého nalezení hodnot polynomu je založena na tom, že . Použití algoritmu rychlého násobení pro polynomy (stejně jako jeho modifikace, operace převzetí modulo a polynom), jako je Schönhage-Strassenova metoda násobení, aplikace paradigmatu rozděl a panuj , pro násobení polynomů (a operace modulo polynomy) je postaven strom, jehož listy jsou polynomy (hodnoty) a kořenem stromu je polynom . [5] ${\displaystyle (a_{0},\tečky ,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)))))$

Poznámky

↑ Alexandre-Théophile Vandermonde Archivováno 5. ledna 2013 na Wayback Machine (ruština) .
↑ Ian Stewart Galois Theory, třetí vydání, s. 28, Chapman & Hall/CRC Mathematics.
↑ Shafarevich I. R., Remizov A. O. Lineární algebra a geometrie, kap. II, odst. 4, - Fizmatlit, Moskva, 2009.
↑ Efektivní výpočty se strukturovanými maticemi a aritmetickými výrazy . Získáno 24. ledna 2017. Archivováno z originálu 2. února 2017. (neurčitý)
↑ Polynomiální algoritmy . Staženo 24. ledna 2017. Archivováno z originálu 10. ledna 2017. (neurčitý)

Literatura

Kurosh A. G. Kurz vyšší algebry. - M.: Nauka 1968.
Ilyin V. A., Poznyak E. G. Lineární algebra. - M.: Věda - Fizmatlit, 1999.
Shafarevich I. R. , Remizov A. O. Lineární algebra a geometrie, Fizmatlit, Moskva, 2009.