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: an
are distinct (no two are equal), making the Vandermonde matrix invertible.
This problem can be reformulated in terms of linear algebra by means of the Vandermonde matrix, as follows.
naïvely by Gaussian elimination results in an algorithm with time complexity O(n3).
Exploiting the structure of the Vandermonde matrix, one can use Newton's divided differences method[5] (or the Lagrange interpolation formula[6][7]) to solve the equation in O(n2) time, which also gives the UL factorization of
The resulting algorithm produces extremely accurate solutions, even if
The Vandermonde determinant is used in the representation theory of the symmetric group.
belong to a finite field, the Vandermonde determinant is also called the Moore determinant, and has properties which are important in the theory of BCH codes and Reed–Solomon error correction codes.
The Fast Fourier transform computes the product of this matrix with a vector in
In the physical theory of the quantum Hall effect, the Vandermonde determinant shows that the Laughlin wavefunction with filling factor 1 is equal to a Slater determinant.
This is no longer true for filling factors different from 1 in the fractional quantum Hall effect.
In the geometry of polyhedra, the Vandermonde matrix gives the normalized volume of arbitrary
does not depend on any order, so that Galois theory implies that the discriminant is a polynomial function of the coefficients of
Although conceptually simple, it involves non-elementary concepts of abstract algebra.
In the process, it computes the LU decomposition of the Vandermonde matrix.
, which is also the monomial that is obtained by taking the first term of all factors in
are monic of respective degrees 0, 1, …, n. 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 gives the matrix Applying the Laplace expansion formula along the first row, we obtain
Iterating this process on this smaller Vandermonde matrix, one eventually gets the desired expression of
To find the constant in front, simply calculate the coefficient of the term
There are other known formulas which solve the interpolation problem, which must be equivalent to the unique
In particular, Lagrange interpolation shows that the columns of the inverse matrix
are not distinct, then this problem does not have a unique solution (and the corresponding Vandermonde matrix is singular).
However, if we specify the values of the derivatives at the repeated points, then the problem can have a unique solution.
are (not necessarily distinct) numbers, and suppose for simplicity that equal values are adjacent: where
We let This generalization of the Vandermonde matrix makes it non-singular, so that there exists a unique solution to the system of equations, and it possesses most of the other properties of the Vandermonde matrix.
There exists an algorithm for the inverse of the confluent Vandermonde matrix that works in quadratic time for every input allowed by the definition.
[12][13] Another way to derive the above formula is by taking a limit of the Vandermonde matrix as the
, take subtract the first row from second in the original Vandermonde matrix, and let
Geometers have studied the problem of tracking confluent points along their tangent lines, known as compacitification of configuration space.