# 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={\begin1&\alpha _&\alpha _^&\dots &\alpha _^\\1&\alpha _&\alpha _^&\dots &\alpha _^\\1&\alpha _&\alpha _^&\dots &\alpha _^\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&\alpha _&\alpha _^&\dots &\alpha _^\end},}$

or

${\displaystyle V_=\alpha _^\,}$

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[2] satisfies both definitions.

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

${\displaystyle \det(V)=\prod _(\alpha _-\alpha _).}$

This is called the Vandermonde determinant or Vandermonde polynomial. If all the numbers ${\displaystyle \alpha _}$ are distinct, then it is non-zero.

The Vandermonde determinant was sometimes called the discriminant, although, presently, the discriminant is the square of the Vandermonde determinant. The Vandermonde determinant is an alternating form in the ${\displaystyle \alpha _}$, meaning that exchanging two ${\displaystyle \alpha _}$ changes the sign, while permuting the ${\displaystyle \alpha _}$ by an even permutation does not change the value of the determinant. It thus depends on the choice of an order on the ${\displaystyle \alpha _}$, 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 \alpha _}$ as roots.

## Proof

The main property of a square Vandermonde matrix

${\displaystyle V={\begin1&x_&x_^&\dots &x_^\\1&x_&x_^&\dots &x_^\\1&x_&x_^&\dots &x_^\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&x_&x_^&\dots &x_^\end}}$

is that its determinant has the simple form

${\displaystyle \det(V)=\prod _(x_-x_).}$

This may be proved either by using properties of polynomials or elementary row and column operations. The former is simpler but it is non-constructive and uses unique factorization property of multivariate polynomials. The latter is constructive and more elementary, at the price of being more complicated. A third proof, based on Gaussian elimination, is sketched. It is still more complicated, if written in details, but provides the U-part of the LU decomposition of Vandermonde matrices.

### Using polynomial properties

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

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

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

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

${\displaystyle \det(V)=Q\prod _(x_-x_),}$

where Q is a polynomial. As the product of all ${\displaystyle x_-x_}$ 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_x_^\cdots x_^,}$ which is also the monomial that is obtained by taking the first term of all factors in ${\displaystyle \textstyle \prod _(x_-x_).}$ This proves that

${\displaystyle \det(V)=\prod _(x_-x_).}$

### By row and column operations

This second proof is based on the fact that, if one adds to a row (or a column) of a matrix the product by a scalar of another row (or column), the determinant remains unchanged.

If one subtracts the first row of V to all the other rows, the determinant is not changed, and the new matrix has the form

${\displaystyle {\begin1&\mathbf \\\mathbf &A\end},}$

where ${\displaystyle \mathbf }$ is a row matrix, ${\displaystyle \mathbf }$ is a column of zeros, and A is a square matrix, such that

${\displaystyle \det(A)=\det(V).}$

The entry of the (i – 1)th row and the (j – 1)th column of A (that is the ith row and the jth column of the whole matrix) is

${\displaystyle x_^-x_^=(x_-x_)\sum _^x_^x_^.}$

Dividing out ${\displaystyle x_-x_}$ from the (i – 1)th row of A, for i = 2, ..., n, one gets a matrix B such that

${\displaystyle \det(V)=\det(A)=\det(B)\prod _^(x_-x_).}$

The coefficient of the (i – 1)th row and the (j – 1)th column of B is

${\displaystyle b_=\sum _^x_^x_^=x_^+x_b_,}$

for i = 2, ..., n, and setting ${\displaystyle b_=1.}$

Thus, subtracting, for j running from n down to 2, the (j – 2)th column of B multiplied by ${\displaystyle x_}$ from the (j – 1)th column, one gets a (n – 1) × (n – 1) Vandermonde matrix in ${\displaystyle x_,\ldots ,x_,}$ which has the same determinant as B. Iterating this process on this smaller Vandermonde matrix, one gets eventually the desired expression of det(V) as the product of the ${\displaystyle x_-x_.}$

### By Gaussian elimination, U-part of LU decomposition

The determinant of Vandermonde matrices may also be computed using Gaussian elimination. This provides an explicit form of the upper triangular matrix of the LU decomposition of the matrix. For this computation one uses only the elementary row operations consisting of adding to a row a scalar multiple of a preceding row. This means than one multiplies the matrix by a lower triangular matrix with a diagonal consisting only of 1. In particular, the determinant is not changed by these transformations.

Applying Gaussian elimination to a square Vandermonde matrix, one gets eventually an upper triangular matrix

${\displaystyle W={\beginw_&w_&w_&\dots &w_\\0&w_&w_&\dots &w_\\0&0&w_&\dots &w_\\\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&0&\dots &w_\end},}$

which has the same determinant as V.

A proof by induction on the steps of Gaussian elimination allows showing that, for 1 ≤ ijn, one has

${\displaystyle w_=M_(\mathbf _,x_)\prod _^(x_-x_),}$

where ${\displaystyle \mathbf _}$ is an abbreviation for ${\displaystyle x_,\ldots ,x_}$, and ${\displaystyle M_(\mathbf _,x_)}$ is the sum of all monomials of degree d in ${\displaystyle \mathbf _,x_.}$ In particular, the first rows of V and W are equal, and the factor ${\displaystyle M_(\mathbf _,x_)}$ equals 1 for the entries of the diagonal (since 1 is the only monomial of degree 0).

A key ingredient of this proof is that, for k > i

${\displaystyle M_(\mathbf _,x_)-M_(\mathbf _,x_)=(x_-x_)M_(\mathbf _,x_,x_)}$

For the recursion, one has to describe the matrix at each step of the Gaussian elimination. Let ${\displaystyle a_}$ be the entry of the ith row and jth column of this variable matrix. Before the ith step, the entries that belong either to the i first rows or the i – 1 first columns have the values that they will have at the end of Gaussian elimination, and, for ijn and ihn, one has

${\displaystyle a_=M_(\mathbf _,x_)\prod _^(x_-x_).}$

This is true before the first step, and one has to prove that this remains true during Gaussian elimination. The ith step does not change the i first rows nor the i – 1 first columns. It changes ${\displaystyle a_}$ to zero for i < hn. For i < jn and i < hn, it changes ${\displaystyle a_}$ into ${\displaystyle a_-a_a_/a_.}$ That is, the new ${\displaystyle a_}$ is

${\displaystyle {\begina_&=M_(\mathbf _,x_)\prod _^(x_-x_)-{\frac (\mathbf _,x_)\prod _^(x_-x_)}(\mathbf _,x_)\prod _^(x_-x_)}}M_(\mathbf _,x_)\prod _^(x_-x_)\\&=\left(M_(\mathbf _,x_)-M_(\mathbf _,x_)\right)\prod _^(x_-x_)\\&=M_(\mathbf _,x_,x_)\prod _^(x_-x_).\end}}$

This shows that the structure of the ${\displaystyle a_}$ is kept during Gaussian elimination, and thus the form of W.

It follows from the structure of W that ${\displaystyle \det(V)=\det(W)}$ is the product of the diagonal entries of W, which proves again the formula for the determinant of a Vandermonde matrix.

### Resulting properties

A m × n rectangular Vandermonde matrix such that mn has maximum rank m if and only if all xi are distinct.

A m × n rectangular Vandermonde matrix such that mn has maximum rank n if and only if there are n of the xi that are distinct.

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

## 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 _}$ 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.

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 _}$[6] and the values of the polynomial at the ${\displaystyle \alpha _}$. However, the interpolation polynomial is generally easier to compute with the Lagrange interpolation formula,[7] which may be used for deriving a formula for the inverse of a Vandermonde matrix.[8]

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

When the values ${\displaystyle \alpha _}$ 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.

## 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 _),...,p(\alpha _)}$, where ${\displaystyle \alpha _,...,\alpha _}$ are distinct points. If ${\displaystyle \alpha _}$ 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 {\beginp(0)=a\\p'(0)=b\\p(1)=c\end}}$

where ${\displaystyle p}$ is a polynomial of degree ${\displaystyle \leq 2}$, has a unique solution for all ${\displaystyle a,b,c}$. In general, suppose that ${\displaystyle \alpha _,\alpha _,...,\alpha _}$ 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 _=\cdots =\alpha _},\alpha _+1}=\cdots =\alpha _},\ldots ,\alpha _+1}=\cdots =\alpha _}}$

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

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

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 } for some (unique) ${\displaystyle 0\leq \ell \leq k-1}$ (we consider ${\displaystyle m_=0}$). Then, we have

${\displaystyle V_={\begin0,&{\text}j

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 _}$'s go arbitrarily close to each other. For example, if ${\displaystyle \alpha _=\alpha _}$, then letting ${\displaystyle \alpha _\to \alpha _}$ 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.

## References

1. ^ Roger A. Horn and Charles R. Johnson (1991), Topics in matrix analysis, Cambridge University Press. See Section 6.1.
2. ^ DFT matrix,https://en.wikipedia.org/en/DFT_matrix
3. ^ Turner, L. Richard (August 1966). Inverse of the Vandermonde matrix with applications (PDF).
4. ^ Macon, N.; A. Spitzbart (February 1958). "Inverses of Vandermonde Matrices". The American Mathematical Monthly. 65 (2): 95–100. doi:10.2307/2308881. JSTOR 2308881.
5. ^
6. ^ François Viète (1540-1603), Vieta's formulas, https://en.wikipedia.org/en/Vieta%27s_formulas
7. ^ Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 2.8.1. Vandermonde Matrices". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8
8. ^ Inverse of Vandermonde Matrix (2018),https://proofwiki.org/en/Inverse_of_Vandermonde_Matrix
9. ^ Fulton, William; Harris, Joe (1991). Representation theory. A first course. Graduate Texts in Mathematics, Readings in Mathematics. 129. New York: Springer-Verlag. doi:10.1007/978-1-4612-0979-9. ISBN 978-0-387-97495-8. MR 1153249. OCLC 246650103. Lecture 4 reviews the representation theory of symmetric groups, including the role of the Vandermonde determinant.