Vandermonde determinant

Vandermonde- determinanten er determinanten

opkaldt efter den franske matematiker Alexandre Theophile Vandermonde . [1] Denne formel viser, at Vandermonde-determinanten er lig med nul, hvis og kun hvis der eksisterer mindst et par , således at .

Bevis

Bevis ved induktion

Matrix størrelse induktion .

basisinduktion

. I dette tilfælde er matrixen

Det er klart, dets determinant er .

Induktiv antagelse induktiv overgang

Træk fra den sidste kolonne den næstsidste, ganget med , fra -th - -th, ganget med , fra -th - -th, ganget med og så videre for alle kolonner. Disse transformationer ændrer ikke matrixdeterminanten. Få

Udvider vi denne determinant over elementerne i den første række, får vi, at den er lig med følgende determinant:

For alle fra 1 at tage multiplikatoren ud fra den -th række . Få

Vi erstatter værdien af ​​determinanten i den foregående formel, kendt fra induktionshypotesen:

Bevis ved sammenligning af magter

Et andet bevis kan opnås ved at antage, at de er variable i polynomialringen . I dette tilfælde er Vandermonde-determinanten et polynomium i variable. Den består af monomialer, hvis grad er lig med . Så graden er det samme tal.

Bemærk, at hvis nogle og falder sammen, så er determinanten lig med nul, da to identiske rækker optræder i matrixen. Derfor skal determinanten som polynomium være delelig med . I alt findes der forskellige par og (for ) , hvilket er lig med graden af ​​. Med andre ord, er deleligt med polynomier i forskellige grader . Derfor er det lig med deres produkt op til en konstant. Men som du kan se ved at åbne parenteserne, er konstanten lig med én. [2 ]

Egenskaber

Vandermonde-matricen er et specialtilfælde af en alternativ matrix , hvor .

Hvis  er en primitiv th rod af enhed og  er en Vandermonde matrix med elementer , så har den inverse matrix op til en diagonal matrix formen :.

Ansøgning

Vandermonde-determinanten har adskillige anvendelser inden for forskellige områder af matematik. For eksempel, når man løser problemet med interpolation med polynomier , det vil sige problemet med at finde et polynomium af grad , hvis graf passerer gennem givne punkter i planet med abscisser , opstår Vandermonde-determinanten som en determinant af et system af lineære ligninger , fra hvor de ukendte koefficienter for det ønskede polynomium findes. [3]

Hurtig multiplikation af en vektor med en Vandermonde-matrix

Hurtig multiplikation af en vektor med en Vandermonde-matrix svarer til at finde værdierne af et polynomium og kan beregnes i operationer, hvor  omkostningerne ved at gange to polynomier er. [4] Metoden til hurtigt at finde værdierne af et polynomium er baseret på det faktum, at . Brug af den hurtige multiplikationsalgoritme for polynomier (såvel som dens modifikation, operationen med at tage modulo et polynomium), såsom Schönhage-Strassen metoden til multiplikation, anvendelse af divide og hersk paradigmet , til multiplikationer af polynomier (og operationer modulo polynomier) der bygges et træ, hvis blade er polynomier (værdier) , og træets rod er et polynomium . [5]

Noter

  1. Alexandre-Théophile Vandermonde Arkiveret 5. januar 2013 på Wayback Machine  (russisk) .
  2. Ian Stewart Galois Theory, tredje udgave, s. 28, Chapman & Hall/CRC Mathematics.
  3. Shafarevich I. R., Remizov A. O. Lineær algebra og geometri, kap. II, stk. 4, - Fizmatlit, Moskva, 2009.
  4. Effektiv beregning med strukturerede matricer og aritmetiske udtryk . Hentet 24. januar 2017. Arkiveret fra originalen 2. februar 2017.
  5. Polynomiske algoritmer . Hentet 24. januar 2017. Arkiveret fra originalen 10. januar 2017.

Litteratur