# Vandermonde-matrix

In de lineaire algebra, een deelgebied van de wiskunde, is een Vandermonde-matrix, vernoemd naar de 18e-eeuwse Franse wiskundige Alexandre-Théophile Vandermonde, een matrix met als opgelegde voorwaarde dat elke rij in deze matrix uit een meetkundige rij moet bestaan, dat wil zeggen, een $m\times n$-matrix van de vorm:
    $V={\begin{bmatrix}1&\alpha _{1}&\alpha _{1}^{2}&\dots &\alpha _{1}^{n-1}\\1&\alpha _{2}&\alpha _{2}^{2}&\dots &\alpha _{2}^{n-1}\\1&\alpha _{3}&\alpha _{3}^{2}&\dots &\alpha _{3}^{n-1}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&\alpha _{m}&\alpha _{m}^{2}&\dots &\alpha _{m}^{n-1}\\\end{bmatrix}}$
of
    $V_{i,j}=\alpha _{i}^{j-1}$
voor alle indices $i$ en $j$. Sommige auteurs gebruiken de getransponeerde van de bovenstaande matrix.
Een Vandermonde-matrix wordt dus volledig bepaald door de getallen $\alpha _{i}(i=1,2,\ldots ,n).$

## Veeltermevaluatie

De Vandermonde-matrix komt aan bod bij het evalueren van een polynoom
    $v(x)=\sum _{i=0}^{n}v_{i}x^{i}$
in een aantal punten $x_{0},x_{1},\dots ,x_{m}$.
Door de Vandermonde-matrix
    $V={\begin{bmatrix}1&x_{0}&x_{0}^{2}&\dots &x_{0}^{n}\\1&x_{1}&x_{1}^{2}&\dots &x_{1}^{n}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{m}&x_{m}^{2}&\dots &x_{m}^{n}\\\end{bmatrix}}$
te vermenigvuldigen met de vector
    $v=(v_{0},v_{1},\dots ,v_{n})$
krijgt men de vector met de te berekenen waarden:
    $V\,v=(v(x_{0}),v(x_{1}),\ldots ,v(x_{m}))$
Als de punten $x_{0},x_{1},\dots ,x_{n-1}$ de $n$-de eenheidswortels zijn, komt dit neer op de berekening van de discrete fouriertransformatie van $v$.

## Interpolatie van een polynoom

Nauw verwant met het vorige probleem is dat van de interpolatie van een polynoom: gegeven $n+1$ verschillende punten $(x_{i},y_{i}),i=0,1,\ldots ,n,$ bepaal de polynoom $p(x)$ van de graad $n$ die door de gegeven punten loopt; met andere woorden waarvoor geldt dat voor $i=0,\ldots ,n$
    $p(x_{i})=\sum _{j=0}^{n}p_{j}x_{i}^{j}=y_{i}$
Om de onbekende coëfficiënten $p_{0},p_{1},\dots ,p_{n}$ te vinden moet men het volgende stelsel van lineaire vergelijkingen oplossen, geschreven in matrixnotatie:
    ${\begin{bmatrix}1&x_{0}&x_{0}^{2}&\ldots &x_{0}^{n}\\1&x_{1}&x_{1}^{2}&\ldots &x_{1}^{n}\\\vdots &\vdots &\vdots &&\vdots \\1&x_{n}&x_{n}^{2}&\ldots &x_{n}^{n}\\\end{bmatrix}}{\begin{bmatrix}p_{0}\\p_{1}\\\vdots \\p_{n}\end{bmatrix}}={\begin{bmatrix}y_{0}\\y_{1}\\\vdots \\y_{n}\end{bmatrix}}$.
De coëfficiëntenmatrix van dit stelsel is een Vandermonde-matrix. Een Vandermonde-matrix is echter slecht geconditioneerd, wat betekent dat er grote afwijkingen kunnen optreden in de berekende waarden $p_{0},p_{1},\ldots ,p_{n}$ bij kleine veranderingen in $y_{0},y_{1},\ldots ,y_{n}$.

## Determinant

De determinant van een vierkante Vandermonde-matrix $V_{n}$ van de orde $n>1$ is:
    $V_{n}={\begin{vmatrix}1&x_{1}&x_{1}^{2}&\ldots &x_{1}^{n-2}&x_{1}^{n-1}\\1&x_{2}&x_{2}^{2}&\ldots &x_{2}^{n-2}&x_{2}^{n-1}\\\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\1&x_{n}&x_{n}^{2}&\ldots &x_{n}^{n-2}&x_{n}^{n-1}\end{vmatrix}}$
Het aantal variabelen $x_{i}$ in deze determinant is $n$.
Voor deze determinant geldt:
    $V_{n}=\prod _{1\leq i<j\leq n}(x_{j}-x_{i})$
Het bewijs van deze stelling gaat met volledige inductie naar het aantal variabelen $n$ in de determinant.
Voor $n=2$ is de bewering juist.
    $V_{2}={\begin{vmatrix}1&x_{1}\\1&x_{2}\end{vmatrix}}=x_{2}-x_{1}$
Er wordt in het volgende gebruikgemaakt van de regels voor het vegen van een determinant.
Stel dat de bewering juist is voor zekere $n$, dan geldt:
    $V_{n+1}={\begin{vmatrix}1&x_{1}&x_{1}^{2}&\ldots &x_{1}^{n-1}&x_{1}^{n}\\1&x_{2}&x_{2}^{2}&\ldots &x_{2}^{n-1}&x_{2}^{n}\\\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\1&x_{n+1}&x_{n+1}^{2}&\ldots &x_{n+1}^{n-1}&x_{n+1}^{n}\end{vmatrix}}={\begin{vmatrix}1&x_{1}&x_{1}^{2}&\ldots &x_{1}^{n-1}&0\\1&x_{2}&x_{2}^{2}&\ldots &x_{2}^{n-1}&x_{2}^{n}-x_{2}^{n-1}x_{1}\\\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\1&x_{n+1}&x_{n+1}^{2}&\ldots &x_{n+1}^{n-1}&x_{n+1}^{n}-x_{n+1}^{n-1}x_{1}\end{vmatrix}}$
De tweede determinant ontstaat door in de eerste determinant $x_{1}$ maal de voorlaatste kolom van de laatste kolom af te trekken. Zo van achter naar voren voortgaand, ontstaat door steeds $x_{1}$ maal een kolom van de volgende kolom af te trekken:
    $V_{n+1}={\begin{vmatrix}1&0&0&\ldots &0&0\\1&x_{2}-x_{1}&x_{2}^{2}-x_{2}x_{1}&\ldots &x_{2}^{n-1}-x_{2}^{n-2}x_{1}&x_{2}^{n}-x_{2}^{n-1}x_{1}\\\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\1&x_{n+1}-x_{1}&x_{n+1}^{2}-x_{n+1}x_{1}&\ldots &x_{n+1}^{n-1}-x_{n+1}^{n-2}x_{1}&x_{n+1}^{n}-x_{n+1}^{n-1}x_{1}\end{vmatrix}}$
Omdat op de eerste rij, behalve op de eerste plaats alleen maar 0 staat, volgt:
    $V_{n+1}={\begin{vmatrix}x_{2}-x_{1}&x_{2}^{2}-x_{2}x_{1}&\ldots &x_{2}^{n-1}-x_{2}^{n-2}x_{1}&x_{2}^{n}-x_{2}^{n-1}x_{1}\\\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\x_{n+1}-x_{1}&x_{n+1}^{2}-x_{n+1}x_{1}&\ldots &x_{n+1}^{n-1}-x_{n+1}^{n-2}x_{1}&x_{n+1}^{n}-x_{n+1}^{n-1}x_{1}\end{vmatrix}}$
Uit elke rij kan een gemeenschappelijke factor worden gehaald:
    $V_{n+1}=(x_{2}-x_{1})\ldots (x_{n+1}-x_{1}){\begin{vmatrix}1&x_{2}&\ldots &x_{2}^{n-2}&x_{2}^{n-1}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{n+1}&\ldots &x_{n+1}^{n-2}&x_{n+1}^{n-1}\end{vmatrix}}$
De overblijvende determinant is een Vandermonde-determinant van de orde $n$, die volgens de inductieveronderstelling de juiste vorm heeft.
* ↑ (en) Roger A. Horn en Charles R. Johnson (1991), Topics in matrix analysis, Cambridge University Press. paragraaf 6.1