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 matrix with entries, the jth power of the number x_i, for all zero-based indices i and j. Some authors define the Vandermonde matrix as the transpose of the above matrix. The determinant of a square Vandermonde matrix (when n=m) is called a Vandermonde determinant or Vandermonde polynomial. Its value is: This is non-zero if and only if all x_i are distinct (no two are equal), making the Vandermonde matrix invertible.

Applications

The polynomial interpolation problem is to find a polynomial which satisfies for given data points. This problem can be reformulated in terms of linear algebra by means of the Vandermonde matrix, as follows. V computes the values of p(x) at the points via a matrix multiplication Va = y, where is the vector of coefficients and is the vector of values (both written as column vectors): If n = m and are distinct, then V is a square matrix with non-zero determinant, i.e. an invertible matrix. Thus, given V and y, one can find the required p(x) by solving for its coefficients a in the equation Va = y: "a = V^{-1}y."That is, the map from coefficients to values of polynomials is a bijective linear mapping with matrix V, and the interpolation problem has a unique solution. This result is called the unisolvence theorem, and is a special case of the Chinese remainder theorem for polynomials. In statistics, the equation Va = y means that the Vandermonde matrix is the design matrix of polynomial regression. In numerical analysis, solving the equation Va = y 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 (or the Lagrange interpolation formula ) to solve the equation in O(n2) time, which also gives the UL factorization of V^{-1}. The resulting algorithm produces extremely accurate solutions, even if V is ill-conditioned. (See polynomial interpolation.) The Vandermonde determinant is used in the representation theory of the symmetric group. When the values x_i 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 discrete Fourier transform is defined by a specific Vandermonde matrix, the DFT matrix, where the x_i are chosen to be n th roots of unity. The Fast Fourier transform computes the product of this matrix with a vector in O(n\log^2n) time. 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 k-faces of cyclic polytopes. Specifically, if is a k-face of the cyclic polytope corresponding to , then

Determinant

The determinant of a square Vandermonde matrix is called a Vandermonde polynomial or Vandermonde determinant. Its value is the polynomial which is non-zero if and only if all x_i are distinct. The Vandermonde determinant was formerly sometimes called the discriminant, but in current terminology the discriminant of a polynomial is the square of the Vandermonde determinant of the roots x_i. The Vandermonde determinant is an alternating form in the x_i, meaning that exchanging two x_i changes the sign, and \det(V) thus depends on order for the x_i. By contrast, the discriminant \det(V)^2 does not depend on any order, so that Galois theory implies that the discriminant is a polynomial function of the coefficients of p(x). The determinant formula is proved below in three ways. The first 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 is based on the linear algebra concepts of change of basis in a vector space and the determinant of a linear map. In the process, it computes the LU decomposition of the Vandermonde matrix. The third proof is more elementary but more complicated, using only elementary row and column operations.

First proof: Polynomial properties

The first proof relies on properties of polynomials. By the Leibniz formula, \det(V) is a polynomial in the x_i, with integer coefficients. All entries of the (i-1)-th column have total degree i. Thus, again by the Leibniz formula, all terms of the determinant have total degree (that is, the determinant is a homogeneous polynomial of this degree). If, for i \neq j, one substitutes x_i for x_j, one gets a matrix with two equal rows, which has thus a zero determinant. Thus, considering the determinant as univariate in x_i, the factor theorem implies that x_j-x_i is a divisor of \det(V). It thus follows that for all i and j, x_j-x_i is a divisor of \det(V). This will now be strengthened to show that the product of all those divisors of \det(V) is a divisor of \det(V). Indeed, let p be a polynomial with x_i-x_j as a factor, then for some polynomial q. If x_k-x_l is another factor of p, then p becomes zero after the substitution of x_k for x_l. If the factor q becomes zero after this substitution, since the factor x_i-x_j remains nonzero. So, by the factor theorem, x_k-x_l divides q, and divides p. Iterating this process by starting from \det(V), one gets that \det(V) is divisible by the product of all x_i-x_j with i<j; that is where Q is a polynomial. As the product of all x_j-x_i and \det(V) have the same degree 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, which is also the monomial that is obtained by taking the first term of all factors in This proves that Q=1, and finishes the proof.

Second proof: linear maps

Let F be a field containing all x_i, and P_n the F vector space of the polynomials of degree less than or equal to n with coefficients in F. Let be the linear map defined by The Vandermonde matrix is the matrix of \varphi with respect to the canonical bases of P_n and F^{n+1}. Changing the basis of 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 1, x-x_0,, …, 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 matrix is thus a change-of-basis matrix of determinant one. The matrix of \varphi on this new basis is 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 V=LU^{-1}.

Third proof: row and column operations

The 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 x_0, 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 Applying the Laplace expansion formula along the first row, we obtain, with As all the entries in the i-th row of B have a factor of x_{i+1}-x_0, one can take these factors out and obtain where V' is a Vandermonde matrix in. Iterating this process on this smaller Vandermonde matrix, one eventually gets the desired expression of \det(V) as the product of all x_j-x_i such that i<j.

Rank of the Vandermonde matrix

m × n rectangular Vandermonde matrix such that m ≤ n has rank m if and only if all xi are distinct. m × n rectangular Vandermonde matrix such that m ≥ n has rank n if and only if there are n of the xi that are distinct. xi are distinct. An explicit formula for the inverse is known (see below).

Inverse Vandermonde matrix

As explained above in Applications, the polynomial interpolation problem for satisfying is equivalent to the matrix equation Va = y, which has the unique solution a = V^{-1}y. There are other known formulas which solve the interpolation problem, which must be equivalent to the unique a = V^{-1}y, so they must give explicit formulas for the inverse matrix V^{-1}. In particular, Lagrange interpolation shows that the columns of the inverse matrix are the coefficients of the Lagrange polynomials where. This is easily demonstrated: the polynomials clearly satisfy for i\neq j while, so we may compute the product , the identity matrix.

Confluent Vandermonde matrices

As described before, a Vandermonde matrix describes the linear algebra interpolation problem of finding the coefficients of a polynomial p(x) of degree n - 1 based on the values, where are distinct points. If x_i 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. For example, the problem where, has a unique solution for all y_1,y_2,y_3 with y_1\neq y_3. In general, suppose that are (not necessarily distinct) numbers, and suppose for simplicity that equal values are adjacent: where and are distinct. Then the corresponding interpolation problem is The corresponding matrix for this problem is called a confluent Vandermonde matrix, given as follows. If, then for a unique (denoting m_0 = 0). 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. Its rows are derivatives (of some order) of the original Vandermonde rows. Another way to derive this formula is by taking a limit of the Vandermonde matrix as the x_i's approach each other. For example, to get the case of x_1 = x_2, take subtract the first row from second in the original Vandermonde matrix, and let x_2\to x_1: this yields the corresponding row in the confluent Vandermonde matrix. This derives the generalized interpolation problem with given values and derivatives as a limit of the original case with distinct points: giving is similar to giving for small \varepsilon. Geometers have studied the problem of tracking confluent points along their tangent lines, known as compacitification of configuration space.