Vandermonde matris

I linjär algebra är en Vandermonde-matris , uppkallad efter Alexandre-Théophile Vandermonde , en matris med termerna för en geometrisk progression i varje rad: en m × n -matris

$V={\begin{bmatrix}1&x_{1}&x_{1}^{2}&\dots &x_{1}^{n-1}\\1&x_{2} &x_{2}^{2}&\dots &x_{2}^{n-1}\\1&x_{3}&x_{3}^{2}&\dots &x_{3}^{n-1}\\ \vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{m}&x_{m}^{2}&\dots &x_{m}^{n-1}\end{bmatrix}},$

eller

$V_{i,j}=x_{i}^{j-1}\,$

för alla index i och j . Vissa författare definierar Vandermonde-matrisen som transponeringen av ovanstående matris.

Determinanten för en kvadratisk Vandermonde-matris kallas ett Vandermonde-polynom eller Vandermonde - determinant . Dess värde är polynomet

$\det(V)=\prod _{1\leq i<j\leq n}(x_{j}-x_ {i})$

som inte är noll om och bara om alla $x_{i}$ är distinkta.

Vandermonde-determinanten kallades ibland diskriminanten , även om för närvarande diskriminanten för ett polynom är kvadraten på Vandermonde-determinanten av polynomets rötter . Vandermonde-determinanten är en alternerande form i $x_{i}$ , vilket betyder att byte av två $x_{i}$ ändrar tecknet, samtidigt som $x_{i} permuteras.$ med en jämn permutation ändrar inte värdet på determinanten. Det beror alltså på valet av en ordning för $x_{i}$ , medan dess kvadrat, diskriminanten, inte beror på någon ordning, och detta antyder, enligt Galois teori , att diskriminanten är ett polynom . funktion av koefficienterna för polynomet som har $x_{i}$ som rötter.

Bevis

Huvudegenskapen för en kvadratisk Vandermonde-matris

$V={\begin{bmatrix}1&x_{1}&x_{1}^{2}&\dots &x_{1}^{n-1}\\1&x_{2}&x_ {2}^{2}&\dots &x_{2}^{n-1}\\1&x_{3}&x_{3}^{2}&\dots &x_{3}^{n-1}\\\ vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{n}&x_{n}^{2}&\dots &x_{n}^{n-1}\end{bmatrix}}$

är att dess determinant har den enkla formen

$\det(V)=\prod _{1\leq i<j\leq n}(x_{j}-x_{i}).$

Tre bevis på denna jämlikhet ges nedan. Den första använder polynomegenskaper, särskilt den unika faktoriseringsegenskapen för multivariata polynom . Även om det är begreppsmässigt enkelt, involverar det icke-elementära begrepp av abstrakt algebra . Det andra beviset kräver ingen explicit beräkning, utan involverar begreppen determinant för en linjär karta och förändring av bas . Det tillhandahåller också strukturen för LU-nedbrytningen av Vandermonde-matrisen. Den tredje är mer elementär och mer komplicerad och använder endast elementära rad- och kolumnoperationer .

Använda polynomegenskaper

Enligt Leibniz-formeln är det( V ) ett polynom i x $x_{i},$ heltalskoefficienter. Alla poster i den i :te kolumnen har totalgraden i – 1 . Således, återigen enligt Leibniz formel, har alla termer av determinanten total grad

$0+1+2+\cdots +(n-1)={\frac {n(n-1)}{2}};$

(det vill säga att determinanten är ett homogent polynom av denna grad).

Om man för i ≠ j , ersätter $x_{i}$ för $x_{j}$ , får man en matris med två lika rader, som alltså har en nolldeterminant. Således, med faktorsatsen , är $x_{j}-x_{i}$ en divisor av det( V ) . Genom den unika faktoriseringsegenskapen för multivariata polynom delar produkten av alla $x_{j}-x_{i}$ det( V ) , dvs.

$\det(V)=Q\prod _{1\leq i<j\leq n}(x_{j }-x_{i}),$

där Q är ett polynom. Eftersom produkten av alla $x_{j}-x_{i}$ och det( V ) har samma grad $n(n-1) /2,$ polynomet Q är i själva verket en konstant. Denna konstant är ett, eftersom produkten av diagonalposterna för V är $x_{2}x_{3}^{2}\cdots x_{n}^{ n-1},$ som också är den monomial som erhålls genom att ta den första termen av alla faktorer i ${\displaystyle \textstyle \prod _{1\leq i<j\leq n}(x_{j}-x_{i}).} Detta$ bevisar att

$\det(V)=\prod _{1\leq i<j\leq n}(x_{j}-x_{i}).$

Använda linjära kartor

Låt F vara ett fält som innehåller alla $x_{i},$ och P n {\displaystyle P_{n}} F-vektorrymden för $grad$ mindre än n med koefficienter i F . Låta

$\varphi :P_{n}\to F^{n}$

vara den linjära kartan som definieras av

$p(x)\mapsto (p(x_{1}),\ldots ,p(x_{n})).$

Vandermonde-matrisen är matrisen för $\varphi$ med avseende på de kanoniska baserna för $P_{n}$ och $F^{n}.$

Att ändra basen för $P_{n}$ innebär att multiplicera Vandermonde-matrisen med en förändring av basmatrisen M (från höger). Detta ändrar inte determinanten om determinanten för M är 1 .

Polynomen $1$ , $x-x_{1}$ , $(x-x_{1})(x- x_{2})$ , …, $(x-x_{1})(x-x_{2})\ cdots (x-x_{n-1})$ är moniska av respektive grader 0, 1, …, n – 1 . Deras matris på monomial basis är en övre triangulär matris U (om monomierna är ordnade i ökande grader), med alla diagonala poster lika med en. Denna matris är således en förändring av basmatris av determinant ett. Matrisen för $\varphi$ på denna nya grund är

$L={\begin{bmatrix}1&0&0&\ldots &0\\1&x_{2}-x_{1}&0&\ldots &0\\1&x_{3}-x_{1}&(x_{3}-x_{ 1})(x_{3}-x_{2})&\ldots &0\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{n}-x_{1}&(x_{n }-x_{1})(x_{n}-x_{2})&\ldots &(x_{n}-x_{1})(x_{n}-x_{2})\cdots (x_{n }-x_{n-1})\end{bmatrix}}.$

Vandermonde-determinanten är alltså lika med determinanten för denna matris, som är produkten av dess diagonala poster.

Detta bevisar den önskade jämlikheten. Dessutom får man LU-sönderdelningen av V as

$V=LU^{-1}.$

Genom rad- och kolumnoperationer

Detta tredje bevis är baserat på det faktum att om man lägger till produkten till en kolumn i en matris med en skalär från en annan kolumn så förblir determinanten oförändrad.

Så genom att subtrahera från varje kolumn – förutom den första – den föregående kolumnen multiplicerad med $x_{1},$ ändras inte determinanten. (Dessa subtraktioner måste göras genom att börja från de sista kolumnerna, för att subtrahera en kolumn som ännu inte har ändrats). Detta ger matrisen

${\begin{bmatrix}1&0&0&0&\cdots &0\\1&x_{2}-x_{1}&x_{2}(x_{2}-x_{1})&x_{2}^{2}(x_{ 2}-x_{1})&\cdots &x_{2}^{n-2}(x_{2}-x_{1})\\1&x_{3}-x_{1}&x_{3}(x_{ 3}-x_{1})&x_{3}^{2}(x_{3}-x_{1})&\cdots &x_{3}^{n-2}(x_{3}-x_{1} )\\\vdots &\vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{n}-x_{1}&x_{n}(x_{n}-x_{1})&x_{n} ^{2}(x_{n}-x_{1})&\cdots &x_{n}^{n-2}(x_{n}-x_{1})\\\end{bmatrix}}.$

Genom att tillämpa Laplace-expansionsformeln längs den första raden får vi ${\displaystyle \det(V)=\det(B)} ,$ med

$B={\begin{bmatrix}x_{2}-x_{1}&x_{2}(x_{2}-x_{1})&x_{2}^{2}(x_{2}-x_ {1})&\cdots &x_{2}^{n-2}(x_{2}-x_{1})\\x_{3}-x_{1}&x_{3}(x_{3}-x_ {1})&x_{3}^{2}(x_{3}-x_{1})&\cdots &x_{3}^{n-2}(x_{3}-x_{1})\\\ vdots &\vdots &\vdots &\ddots &\vdots \\x_{n}-x_{1}&x_{n}(x_{n}-x_{1})&x_{n}^{2}(x_{ n}-x_{1})&\cdots &x_{n}^{n-2}(x_{n}-x_{1})\\\end{bmatrix}}.$

Eftersom alla poster i i $\displaystyle i}$ -th raden av $B$ har en faktor på $x_{i+1}-x_{1},$ man kan ta ut dessa faktorer och få

$\det(V)=(x_{2}-x_{1})(x_{3}-x_{1} )\cdots (x_{n}-x_{1}){\begin{vmatrix}1&x_{2}&x_{2}^{2}&\cdots &x_{2}^{n-2}\\1&x_{3 }&x_{3}^{2}&\cdots &x_{3}^{n-2}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{n}&x_{n}^{ 2}&\cdots &x_{n}^{n-2}\\\end{vmatrix}}=\prod _{1<j\leq n}(x_{j}-x_{1})\det(V '),$

där $V'$ är en Vandermonde-matris i $x_{2},\ldots ,x_{n}.$ Genom att iterera denna process på denna mindre Vandermonde-matris får man så småningom det önskade uttrycket av det( V ) som produkten av alla $x_{j}-x_{i}$ så att i < j .

Resulterande egenskaper

En m × n rektangulär Vandermonde-matris så att m ≤ n har maximal rang m om och endast om alla x _i är distinkta.

En m × n rektangulär Vandermonde-matris så att m ≥ n har maximal rang n om och endast om det finns n av x _i som är distinkta.

En kvadratisk Vandermonde-matris är inverterbar om och endast om x _i är distinkt. En explicit formel för inversen är känd.

Ansökningar

Vandermonde-matrisen utvärderar ett polynom vid en uppsättning punkter; formellt är det matrisen för den linjära kartan som mappar vektorn av koefficienter för ett polynom till vektorn för polynomets värden vid de värden som förekommer i Vandermonde-matrisen. Att Vandermonde-determinanten inte försvinner för distinkta punkter $\alpha _{i}$ visar att för distinkta punkter är kartan från koefficienter till värden vid dessa punkter en en-till-en-överensstämmelse, och därmed att polynominterpolationsproblemet är lösbart med en unik lösning; detta resultat kallas unsolvenssatsen och är ett specialfall av den kinesiska restsatsen för polynom .

Detta kan vara användbart vid polynominterpolation , eftersom invertering av Vandermonde-matrisen gör det möjligt att uttrycka koefficienterna för polynomet i termer av $\alpha _{i}$ och polynomets värden vid $\ alfa _{i}$ . Emellertid är interpolationspolynomet i allmänhet lättare att beräkna med Lagrange-interpolationsformeln , som också kan användas för att härleda en formel för inversen av en Vandermonde-matris.

Vandermonde-determinanten används i representationsteorin för den symmetriska gruppen .

När värdena $\alpha _{k}$ tillhör ett ändligt fält , så kallas Vandermonde-determinanten också en Moore-determinant och har specifika egenskaper som används till exempel i teorin om BCH-kod och Reed –Solomon felkorrigeringskoder .

Den diskreta Fourier-transformen definieras av en specifik Vandermonde-matris, DFT-matrisen , där talen α _i är valda för att vara enhetsrötter . Med hjälp av Fast Fourier Transform är det möjligt att beräkna produkten av en Vandermonde-matris med en vektor i $O(n(\log n)^{2})$ tid.

Laughlin- vågfunktionen med fyllningsfaktor ett (uppträder i Quantum Hall-effekten ), med formeln för Vandermonde-determinanten, kan ses vara en Slater-determinant . Detta gäller inte längre för fyllningsfaktorer som skiljer sig från en, dvs. i den fraktionerade Quantum Hall-effekten .

Det är designmatrisen för polynomregression .

Det är den normaliserade volymen av godtyckliga $k$ -ytor av cykliska polytoper . Specifikt, om $F=C_{d}(t_{i_{1}},\dots ,t_{i_{k+1}} )$ är en $k$ -yta av den cykliska polytopen ${\displaystyle C_{d}(T)\subset \mathbb {R} ^{d}} ($ där ${\displaystyle T=\{t_{1},\dots ,t_{N}\}_{<}\subset \mathbb {Z} } ),$ sedan

$$\mathrm {nvol} (F)={\frac {1}{k!}}\prod _{1\leq m<n\leq k+1}{(t_{i_{n}}-t_ {jag är}})}.$$

Sammanflytande Vandermonde-matriser

Som beskrivits tidigare beskriver en Vandermonde-matris det linjära algebrainterpolationsproblemet att hitta koefficienterna för ett polynom $p(x)$ av grad $n-1$ baserat på värdena ${\displaystyle p(\alpha _{1}),\,...,\,p(\alpha _{n})} ,$ där $\alpha _{1},\,...,\,\alpha _{n}$ är distinkta punkter. Om $\alpha _{i}$ inte är distinkta, har detta problem ingen unik lösning (vilket återspeglas av det faktum att motsvarande Vandermonde-matris är singular). Men om vi ger derivatornas värden vid de upprepade punkterna, kan problemet ha en unik lösning. Till exempel problemet

${\begin{cases}p(0)=a\\p'(0)=b\\p(1)=c \end{cases}}$

där $p$ är ett polynom med grad ≤ 2, har en unik lösning för alla $a,b,c$ . Antag i allmänhet att $\alpha _{1},\alpha _{2},...,\alpha _{n}$ är (inte nödvändigtvis distinkta) siffror, och anta för att underlätta noteringen att lika värden kommer in kontinuerliga sekvenser i listan. Det är

$\alpha _{1}=\cdots =\ alpha _{m_{1}},\ \alpha _{m_{1}+1}=\cdots =\alpha _{m_{2}},\ \ldots ,\ \alpha _{m_{k-1} +1}=\cdots =\alpha _{m_{k}}$

där $m_{k}=n,$$m_{1}<m_{2}<\cdots <m_{k},$ och $\alpha _{m_{1}},\ldots ,\alpha _{m_{k}}$ är distinkta. Då är motsvarande interpolationsproblem

${\begin{cases}p(\alpha _{1})=\beta _{1},&p'(\alpha _{1})=\beta _{2},&\ldots , &p^{(m_{1}-1)}(\alpha _{1})=\beta _{m_{1}}\\p(\alpha _{m_{1}+1})=\beta _ {m_{1}+1},&p'(\alpha _{m_{1}+1})=\beta _{m_{1}+2},&\ldots ,&p^{(m_{2}- m_{1}-1)}(\alpha _{m_{2}})=\beta _{m_{2}}\\\qquad \vdots \\p(\alpha _{m_{k-1}+ 1})=\beta _{m_{k-1}+1},&p'(\alpha _{m_{k-1}+2})=\beta _{m_{k-1}+2}, &\ldots ,&p^{(m_{k}-m_{k-1}-1)}(\alpha _{m_{k}})=\beta _{m_{k}}\end{cases}}$

Och motsvarande matris för detta problem kallas en konfluent Vandermonde-matris . I vårt fall (vilket är det allmänna fallet, fram till permutering av raderna i matrisen) ges formeln för den enligt följande: om $1\leq i,j\leq n$ , sedan $m_{\ell }<i\leq m_{\ell +1}$ för vissa (unika) $0\leq \ell \ leq k-1$ (vi betraktar $m_{0}=0$ ). Då har vi

$V_{i,j}={\begin{cases}0,&{\text{if }}j<i-m_{\ell };\\[6pt]{\dfrac {(j-1) !}{(j-(i-m_{\ell }))!}}\alpha _{i}^{j-(i-m_{\ell })},&{\text{if }}j\ geq i-m_{\ell }.\end{cases}}$

Denna generalisering av Vandermonde-matrisen gör den icke-singular (så att det finns en unik lösning på ekvationssystemet) samtidigt som de behåller de flesta egenskaperna hos Vandermonde-matrisen. Dess rader är derivator (av någon ordning) av de ursprungliga Vandermonde-raderna.

Ett annat sätt att ta emot denna formel är att låta några av $\alpha _{i}$ gå godtyckligt nära varandra. Till exempel, om $\alpha _{1}=\alpha _{2}$ , låt sedan $\alpha _{2}\to \alpha _{1 }$ i den ursprungliga Vandermonde-matrisen, ger skillnaden mellan den första och andra raden motsvarande rad i den sammanflytande Vandermonde-matrisen. Detta gör att vi kan koppla det generaliserade interpolationsproblemet (givet värde och derivator på en punkt) till det ursprungliga fallet där alla punkter är distinkta: ges $p(\alpha ),p '(\alpha )$ liknar att ges $p(\alpha ),p(\alpha +\varepsilon )$ där $\varepsilon$ är mycket små.

Se även

• Medföljande matris § Diagonaliserbarhet
• Schurpolynom – en generalisering
• Alternativ matris
• Lagrangepolynom
• Wronskian
• Lista över matriser
• Moore determinant över ett ändligt fält
• Vietas formler

Vidare läsning

• Ycart, Bernard (2013), "A case of matematical eponymy: the Vandermonde determinant", Revue d'Histoire des Mathématiques , 13 , arXiv : 1204.4716 , Bibcode : 2012arXiv1204.4716Y .

externa länkar

• Vandermonde matris på ProofWiki