Vandermonde matrix

In linear algebra, a Vandermonde matrix, named after Alexandre-Théophile Vandermonde, is a matrix with the terms of a geometric progression in each row, i.e., an m × n matrix

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

or

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

for all indices i and j.^[1] The identical term Vandermonde matrix was used for the transpose of the above matrix by Macon and Spitzbart (1958). The Vandermonde matrix used for the discrete Fourier transform matrix satisfies both definitions.

The determinant of a square Vandermonde matrix (where m = n) can be expressed as

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

This is called the Vandermonde determinant or Vandermonde polynomial. It is non-zero if and only if all ${\displaystyle x_{i}}$ are distinct.

The Vandermonde determinant was sometimes called the discriminant, although, presently, the discriminant of a polynomial is the square of the Vandermonde determinant of the roots of the polynomial. The Vandermonde determinant is an alternating form in the ${\displaystyle x_{i}}$, meaning that exchanging two ${\displaystyle x_{i}}$ changes the sign, while permuting the ${\displaystyle x_{i}}$ by an even permutation does not change the value of the determinant. It thus depends on the choice of an order for the ${\displaystyle x_{i}}$, while its square, the discriminant, does not depend on any order, and this implies, by Galois theory, that the discriminant is a polynomial function of the coefficients of the polynomial that has the ${\displaystyle x_{i}}$ as roots.

Proofs[]

The main property of a square Vandermonde matrix

${\displaystyle 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}}}$

is that its determinant has the simple form

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

Three proofs of this equality are given below. The first one uses polynomial properties, especially the unique factorization property of multivariate polynomials. Although conceptually simple, it involves non-elementary concepts of abstract algebra. The second proof does not require any explicit computation, but involves the concepts of the determinant of a linear map and change of basis. It provides also the structure of the LU decomposition of the Vandermonde matrix. The third one is more elementary and more complicated, using only elementary row and column operations.

Using polynomial properties[]

By the Leibniz formula, det(V) is a polynomial in the ${\displaystyle x_{i},}$ with integer coefficients. All entries of the ith column have total degree i – 1. Thus, again by the Leibniz formula, all terms of the determinant have total degree

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

(that is the determinant is a homogeneous polynomial of this degree).

If, for i ≠ j, one substitutes ${\displaystyle x_{i}}$ for ${\displaystyle x_{j}}$, one gets a matrix with two equal rows, which has thus a zero determinant. Thus, by the factor theorem, ${\displaystyle x_{j}-x_{i}}$ is a divisor of det(V). By the unique factorization property of multivariate polynomials, the product of all ${\displaystyle x_{j}-x_{i}}$ divides det(V), that is

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

where Q is a polynomial. As the product of all ${\displaystyle x_{j}-x_{i}}$ and det(V) have the same degree ${\displaystyle n(n-1)/2,}$ the polynomial Q is, in fact, a constant. This constant is one, because the product of the diagonal entries of V is ${\displaystyle x_{2}x_{3}^{2}\cdots x_{n}^{n-1},}$ which is also the monomial that is obtained by taking the first term of all factors in ${\displaystyle \textstyle \prod _{1\leq i<j\leq n}(x_{j}-x_{i}).}$ This proves that

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

Using linear maps[]

Let F be a field containing all ${\displaystyle x_{i},}$ and ${\displaystyle P_{n}}$ the F vector space of the polynomials of degree less than n with coefficients in F. Let

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

be the linear map defined by

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

The Vandermonde matrix is the matrix of ${\displaystyle \varphi }$ with respect to the canonical bases of ${\displaystyle P_{n}}$ and ${\displaystyle F^{n}.}$

Changing the basis of ${\displaystyle P_{n}}$ amounts to multiplying the Vandermonde matrix by a change-of-basis matrix M (from the right). This does not change the determinant, if the determinant of M is 1.

The polynomials ${\displaystyle 1}$, ${\displaystyle x-x_{1}}$, ${\displaystyle (x-x_{1})(x-x_{2})}$, …, ${\displaystyle (x-x_{1})(x-x_{2})\cdots (x-x_{n-1})}$ are monic of respective degrees 0, 1, …, n – 1. Their matrix on the monomial basis is an upper-triangular matrix U (if the monomials are ordered in increasing degrees), with all diagonal entries equal to one. This matrix is thus a change-of-basis matrix of determinant one. The matrix of ${\displaystyle \varphi }$ on this new basis is

${\displaystyle 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}}.}$

Thus Vandermonde determinant equals the determinant of this matrix, which is the product of its diagonal entries.

This proves the desired equality. Moreover, one gets the LU decomposition of V as

${\displaystyle V=LU^{-1}.}$

By row and column operations[]

This third proof is based on the fact that if one adds to a column of a matrix the product by a scalar of another column then the determinant remains unchanged.

So, by subtracting to each column – except the first one – the preceding column multiplied by ${\displaystyle x_{1},}$ the determinant is not changed. (These subtractions must be done by starting from last columns, for subtracting a column that has not yet been changed). This gives the matrix

${\displaystyle {\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}}.}$

Applying the Laplace expansion formula along the first row, we obtain ${\displaystyle \det(V)=\det(B)}$, with

${\displaystyle 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}}.}$

As all the entries in the ${\displaystyle i}$-th row of ${\displaystyle B}$ have a factor of ${\displaystyle x_{i+1}-x_{1},}$ one can take these factors out and obtain

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

where ${\displaystyle V'}$ is a Vandermonde matrix in ${\displaystyle x_{2},\ldots ,x_{n}.}$ Iterating this process on this smaller Vandermonde matrix, one eventually gets the desired expression of det(V) as the product of all ${\displaystyle x_{j}-x_{i}}$ such that i < j.

Resulting properties[]

An m × n rectangular Vandermonde matrix such that m ≤ n has maximum rank m if and only if all x_i are distinct.

An m × n rectangular Vandermonde matrix such that m ≥ n has maximum rank n if and only if there are n of the x_i that are distinct.

A square Vandermonde matrix is invertible if and only if the x_i are distinct. An explicit formula for the inverse is known.^[2][3][4]

Applications[]

The Vandermonde matrix evaluates a polynomial at a set of points; formally, it is the matrix of the linear map that maps the vector of coefficients of a polynomial to the vector of the values of the polynomial at the values appearing in the Vandermonde matrix. The non-vanishing of the Vandermonde determinant for distinct points ${\displaystyle \alpha _{i}}$ shows that, for distinct points, the map from coefficients to values at those points is a one-to-one correspondence, and thus that the polynomial interpolation problem is solvable with a unique solution; this result is called the unisolvence theorem, and is a special case of the Chinese remainder theorem for polynomials.

This may be useful in polynomial interpolation, since inverting the Vandermonde matrix allows expressing the coefficients of the polynomial in terms of the ${\displaystyle \alpha _{i}}$^[5] and the values of the polynomial at the ${\displaystyle \alpha _{i}}$. However, the interpolation polynomial is generally easier to compute with the Lagrange interpolation formula,^[6] which may also be used for deriving a formula for the inverse of a Vandermonde matrix.^{[7][better source needed]}

The Vandermonde determinant is used in the representation theory of the symmetric group.^[8]

When the values ${\displaystyle \alpha _{k}}$ belong to a finite field, then the Vandermonde determinant is also called a Moore determinant and has specific properties that are used, for example, in the theory of BCH code and Reed–Solomon error correction codes.

The discrete Fourier transform is defined by a specific Vandermonde matrix, the DFT matrix, where the numbers α_i are chosen to be roots of unity.

The Laughlin wavefunction with filling factor one (appearing in the Quantum Hall effect), by the formula for the Vandermonde determinant, can be seen to be a Slater determinant. This is not true anymore for filling factors different from one, i.e., in the fractional Quantum Hall effect.

It is the design matrix of polynomial regression.

Confluent Vandermonde matrices[]

As described before, a Vandermonde matrix describes the linear algebra interpolation problem of finding the coefficients of a polynomial ${\displaystyle p(x)}$ of degree ${\displaystyle n-1}$ based on the values ${\displaystyle p(\alpha _{1}),\,...,\,p(\alpha _{n})}$, where ${\displaystyle \alpha _{1},\,...,\,\alpha _{n}}$ are distinct points. If ${\displaystyle \alpha _{i}}$ are not distinct, then this problem does not have a unique solution (which is reflected by the fact that the corresponding Vandermonde matrix is singular). However, if we give the values of the derivatives at the repeated points, then the problem can have a unique solution. For example, the problem

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

where ${\displaystyle p}$ is a polynomial of degree ≤ 2, has a unique solution for all ${\displaystyle a,b,c}$. In general, suppose that ${\displaystyle \alpha _{1},\alpha _{2},...,\alpha _{n}}$ are (not necessarily distinct) numbers, and suppose for ease of notation that equal values come in continuous sequences in the list. That is

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

where ${\displaystyle m_{k}=n,}$ ${\displaystyle m_{1}<m_{2}<\cdots <m_{k},}$ and ${\displaystyle \alpha _{m_{1}},\ldots ,\alpha _{m_{k}}}$ are distinct. Then the corresponding interpolation problem is

${\displaystyle {\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}}}$

And the corresponding matrix for this problem is called a confluent Vandermonde matrices. In our case (which is the general case, up to permuting the rows of the matrix) the formula for it is given as follows: if ${\displaystyle 1\leq i,j\leq n}$, then ${\displaystyle m_{\ell }<i\leq m_{\ell +1}}$ for some (unique) ${\displaystyle 0\leq \ell \leq k-1}$ (we consider ${\displaystyle m_{0}=0}$). Then, we have

${\displaystyle 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}}}$

This generalization of the Vandermonde matrix makes it non-singular (such that there exists a unique solution to the system of equations) while retaining most properties of the Vandermonde matrix. Its rows are derivatives (of some order) of the original Vandermonde rows.

Another way to receive this formula is to let some of the ${\displaystyle \alpha _{i}}$'s go arbitrarily close to each other. For example, if ${\displaystyle \alpha _{1}=\alpha _{2}}$, then letting ${\displaystyle \alpha _{2}\to \alpha _{1}}$ in the original Vandermonde matrix, the difference between the first and second rows yields the corresponding row in the confluent Vandermonde matrix. This allows us to link the generalized interpolation problem (given value and derivatives on a point) to the original case where all points are distinct: Being given ${\displaystyle p(\alpha ),p'(\alpha )}$ is similar to being given ${\displaystyle p(\alpha ),p(\alpha +\varepsilon )}$ where ${\displaystyle \varepsilon }$ is very small.

See also[]

• Schur polynomial – a generalization
• Alternant matrix
• Lagrange polynomial
• Wronskian
• List of matrices
• Moore determinant over a finite field
• Vieta's formulas

References[]

Further reading[]

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

External links[]

• Vandermonde matrix at ProofWiki