A Vandermonde matrix is defined in terms of scalars , , …, by

The are called *points* or *nodes*. Note that while we have indexed the nodes from , they are usually indexed from in papers concerned with algorithms for solving Vandermonde systems.

Vandermonde matrices arise in polynomial interpolation. Suppose we wish to find a polynomial of degree at most that interpolates to the data , that is, , . These equations are equivalent to

where is the vector of coefficients. This is known as the *dual problem*. We know from polynomial interpolation theory that there is a unique interpolant if the are distinct, so this is the condition for to be nonsingular.

The problem

is called the *primal problem*, and it arises when we determine the weights for a quadrature rule: given moments find weights such that , .

## Determinant

The determinant of is a function of the points . If for some then has identical th and th columns, so is singular. Hence the determinant must have a factor . Consequently, we have

where, since both sides have degree in the , is a constant. But contains a term (from the main diagonal), so . Hence

This formula confirms that is nonsingular precisely when the are distinct.

## Inverse

Now assume that is nonsingular and let . Equating elements in the th row of gives

where is the Kronecker delta (equal to if and otherwise). These equations say that the polynomial takes the value at and at , . It is not hard to see that this polynomial is the Lagrange basis polynomial:

We deduce that

where denotes the sum of all distinct products of of the arguments (that is, is the th elementary symmetric function).

From (1) and (3) we see that if the are real and positive and arranged in increasing order and has a checkerboard sign pattern: the element has sign .

Note that summing (2) over gives

where the second equality follows from the fact that is a degree polynomial that takes the value at the distinct points . Hence

so the elements in the th column of the inverse sum to for and for .

## Example

To illustrate the formulas above, here is an example, with and :

for which .

## Conditioning

Vandermonde matrices are notorious for being ill conditioned. The ill conditioning stems from the monomials being a poor basis for the polynomials on the real line. For arbitrary distinct points , Gautschi showed that satisfies

with equality on the right when for all with a fixed (in particular, when for all ). Note that the upper and lower bounds differ by at most a factor . It is also known that for any set of real points ,

and that for we have , where the lower bound is an extremely fast growing function of the dimension!

These exponential lower bounds are alarming, but they do not necessarily rule out the use of Vandermonde matrices in practice. One of the reasons is that there are specialized algorithms for solving Vandermonde systems whose accuracy is not dependent on the condition number , and which in some cases can be proved to be highly accurate. The first such algorithm is an operation algorithm for solving of Björck and Pereyra (1970). There is now a long list of generalizations of this algorithm in various directions, including for confluent Vandermonde-like matrices (Higham, 1990), as well as for more specialized problems (Demmel and Koev, 2005) and more general ones (Bella et al., 2009). Another important observation is that the exponential lower bounds are for real nodes. For complex nodes can be much better conditioned. Indeed when the are the roots of unity, is the unitary Fourier matrix and so is perfectly conditioned.

## Generalizations

Two ways in which Vandermonde matrices have been generalized are by allowing confluency of the points and by replacing the monomials by other polynomials. Confluency arises when the are not distinct. If we assume that equal are contiguous then a confluent Vandermonde matrix is obtained by “differentiating” the previous column for each of the repeated points. For example, with points we obtain

The transpose of a confluent Vandermonde matrix arises in Hermite interpolation; it is nonsingular if the points corresponding to the “nonconfluent columns” are distinct (that is, if in the case of (4)).

A *Vandermonde-like matrix* is defined in terms of a set of polynomials with having degree :

Of most interest are polynomials that satisfy a three-term recurrence, in particular, orthogonal polynomials. Such matrices can be much better conditioned than general Vandermonde matrices.

## Notes

Algorithms for solving confluent Vandermonde-like systems and their rounding error analysis are described in the chapter “Vandermonde systems” of Higham (2002).

Gautschi has written many papers on the conditioning of Vandermonde matrices, beginning in 1962. We mention just his most recent paper on this topic: Gautschi (2011).

## References

This is a minimal set of references, which contain further useful references within.

- T. Bella, Y. Eidelman. I. Gohberg. I. Koltracht, and V. Olshevsky, A Fast Björck–Pereyra-Type Algorithm for Solving Hessenberg-Quasiseparable-Vandermonde Systems, SIAM J. Matrix Anal. Appl. 31(2), 790–815, 2009.
- James W. Demmel and Plamen Koev, The Accurate and Efficient Solution of a Totally Positive Generalized Vandermonde Linear System, SIAM J. Matrix Anal. Appl. 2791, 142–152, 2005.
- Walter Gautschi, Optimally Scaled and Optimally Conditioned Vandermonde and Vandermonde-like matrices, BIT 51, 103–125, 2011.
- Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, second edition, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2002.
- Nicholas J. Higham, Stability Analysis of Algorithms for Solving Confluent Vandermonde-like Systems, SIAM J. Matrix Anal. Appl. 11, 23–41, 1990.

## Related Blog Posts

- What Is a Condition Number? (2020)

This article is part of the “What Is” series, available from https://nhigham.com/category/what-is and in PDF form from the GitHub repository https://github.com/higham/what-is.

A few interesting tidbits regarding Vandermonde matrices.

Since det V has a nice closed form Vandermonde systems are one of the few places where one can meaningfully apply Cramer’s rule.

If a set of nodes maximize |det V| they are known as Fekete points. In one dimension the Fekete points are the Gauss-Legendre-Lobatto nodes (GLL); a result which I believe was first shown by Fejér. The proof is tedious. A cottage industry exists around trying to find Fekete points in higher dimensional domains with applications to multi-variate Lagrange interpolation.