In
linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrix (mathemat ...
, a Vandermonde matrix, named after
Alexandre-Théophile Vandermonde
Alexandre-Théophile Vandermonde (28 February 1735 – 1 January 1796) was a French mathematician, musician, and chemist who worked with Bézout and Lavoisier; his name is now principally associated with determinant theory in mathematics. He was ...
, is a
matrix
Matrix (: matrices or matrixes) or MATRIX may refer to:
Science and mathematics
* Matrix (mathematics), a rectangular array of numbers, symbols or expressions
* Matrix (logic), part of a formula in prenex normal form
* Matrix (biology), the m ...
with the terms of a
geometric progression
A geometric progression, also known as a geometric sequence, is a mathematical sequence of non-zero numbers where each term after the first is found by multiplying the previous one by a fixed number called the ''common ratio''. For example, the s ...
in each row: an
matrix
:
with entries
, the ''j''
th power of the number
, for all
zero-based indices
and
. Some authors define the Vandermonde matrix as the
transpose
In linear algebra, the transpose of a Matrix (mathematics), matrix is an operator which flips a matrix over its diagonal;
that is, it switches the row and column indices of the matrix by producing another matrix, often denoted by (among other ...
of the above matrix.
The
determinant
In mathematics, the determinant is a Scalar (mathematics), scalar-valued function (mathematics), function of the entries of a square matrix. The determinant of a matrix is commonly denoted , , or . Its value characterizes some properties of the ...
of a
square
In geometry, a square is a regular polygon, regular quadrilateral. It has four straight sides of equal length and four equal angles. Squares are special cases of rectangles, which have four equal angles, and of rhombuses, which have four equal si ...
Vandermonde matrix (when
) is called a Vandermonde determinant or
Vandermonde polynomial In algebra, the Vandermonde polynomial of an ordered set of ''n'' variables X_1,\dots, X_n, named after Alexandre-Théophile Vandermonde, is the polynomial:
:V_n = \prod_ (X_j-X_i).
(Some sources use the opposite order (X_i-X_j), which changes the s ...
. Its value is:
:
This is non-zero if and only if all
are distinct (no two are equal), making the Vandermonde matrix
invertible
In mathematics, the concept of an inverse element generalises the concepts of opposite () and reciprocal () of numbers.
Given an operation denoted here , and an identity element denoted , if , one says that is a left inverse of , and that ...
.
Applications
The
polynomial interpolation
In numerical analysis, polynomial interpolation is the interpolation of a given data set by the polynomial of lowest possible degree that passes through the points in the dataset.
Given a set of data points (x_0,y_0), \ldots, (x_n,y_n), with no ...
problem is to find a polynomial
which satisfies
for given data points
. This problem can be reformulated in terms of
linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrix (mathemat ...
by means of the Vandermonde matrix, as follows.
computes the values of
at the points
via a matrix multiplication
, where
is the vector of coefficients and
is the vector of values (both written as column vectors):
If
and
are distinct, then ''V'' is a square matrix with non-zero determinant, i.e. an
invertible matrix
In linear algebra, an invertible matrix (''non-singular'', ''non-degenarate'' or ''regular'') is a square matrix that has an inverse. In other words, if some other matrix is multiplied by the invertible matrix, the result can be multiplied by a ...
. Thus, given ''V'' and ''y'', one can find the required
by solving for its coefficients
in the equation
:
.
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
Statistics (from German language, German: ', "description of a State (polity), state, a country") is the discipline that concerns the collection, organization, analysis, interpretation, and presentation of data. In applying statistics to a s ...
, the equation
means that the Vandermonde matrix is the
design matrix
In statistics and in particular in regression analysis, a design matrix, also known as model matrix or regressor matrix and often denoted by X, is a matrix of values of explanatory variables of a set of objects. Each row represents an individual o ...
of
polynomial regression
In statistics, polynomial regression is a form of regression analysis in which the relationship between the independent variable ''x'' and the dependent variable ''y'' is modeled as a polynomial in ''x''. Polynomial regression fits a nonlinear ...
.
In
numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic computation, symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of ...
, solving the equation
naïvely by Gaussian elimination results in an algorithm with
time complexity
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations ...
O(''n''
3). 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(''n''
2) time, which also gives the
UL factorization of
. The resulting algorithm produces extremely accurate solutions, even if
is
ill-conditioned
In numerical analysis, the condition number of a function measures how much the output value of the function can change for a small change in the input argument. This is used to measure how sensitive a function is to changes or errors in the inpu ...
.
(See
polynomial interpolation
In numerical analysis, polynomial interpolation is the interpolation of a given data set by the polynomial of lowest possible degree that passes through the points in the dataset.
Given a set of data points (x_0,y_0), \ldots, (x_n,y_n), with no ...
.)
The Vandermonde determinant is used in the
representation theory of the symmetric group
In mathematics, the representation theory of the symmetric group is a particular case of the representation theory of finite groups, for which a concrete and detailed theory can be obtained. This has a large area of potential applications, from sy ...
.
When the values
belong to a
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field (mathematics), field that contains a finite number of Element (mathematics), elements. As with any field, a finite field is a Set (mathematics), s ...
, the Vandermonde determinant is also called the
Moore determinant, and has properties which are important in the theory of
BCH code
In coding theory, the Bose–Chaudhuri–Hocquenghem codes (BCH codes) form a class of cyclic error-correcting codes that are constructed using polynomials over a finite field (also called a '' Galois field''). BCH codes were invented in ...
s and
Reed–Solomon error correction
In information theory and coding theory, Reed–Solomon codes are a group of error-correcting codes that were introduced by Irving S. Reed and Gustave Solomon in 1960.
They have many applications, including consumer technologies such as MiniDiscs, ...
codes.
The
discrete Fourier transform
In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced Sampling (signal processing), samples of a function (mathematics), function into a same-length sequence of equally-spaced samples of the discre ...
is defined by a specific Vandermonde matrix, the
DFT matrix
In applied mathematics, a DFT matrix is a ''square matrix'' as an expression of a discrete Fourier transform (DFT) as a transformation matrix, which can be applied to a signal through matrix multiplication.
Definition
An ''N''-point DFT is expres ...
, where the
are chosen to be th
roots of unity
In mathematics, a root of unity is any complex number that yields 1 when raised to some positive integer power . Roots of unity are used in many branches of mathematics, and are especially important in number theory, the theory of group char ...
. The
Fast Fourier transform
A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). A Fourier transform converts a signal from its original domain (often time or space) to a representation in ...
computes the product of this matrix with a vector in
time. See the article on
Multipoint Polynomial evaluation for details.
In the
physical theory of the
quantum Hall effect
The quantum Hall effect (or integer quantum Hall effect) is a quantized version of the Hall effect which is observed in two-dimensional electron systems subjected to low temperatures and strong magnetic fields, in which the Hall resistance exhi ...
, 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
The fractional quantum Hall effect (fractional QHE or FQHE) is the observation of precisely quantized plateaus in the Hall conductance of 2-dimensional (2D) electrons at fractional values of e^2/h, where ''e'' is the electron charge and ''h'' i ...
.
In the geometry of
polyhedra
In geometry, a polyhedron (: polyhedra or polyhedrons; ) is a three-dimensional figure with flat polygonal faces, straight edges and sharp corners or vertices. The term "polyhedron" may refer either to a solid figure or to its boundary su ...
, the Vandermonde matrix gives the normalized volume of arbitrary
-faces of
cyclic polytopes. Specifically, if
is a
-face of the cyclic polytope
corresponding to
, then
Determinant
The
determinant
In mathematics, the determinant is a Scalar (mathematics), scalar-valued function (mathematics), function of the entries of a square matrix. The determinant of a matrix is commonly denoted , , or . Its value characterizes some properties of the ...
of a
square
In geometry, a square is a regular polygon, regular quadrilateral. It has four straight sides of equal length and four equal angles. Squares are special cases of rectangles, which have four equal angles, and of rhombuses, which have four equal si ...
Vandermonde matrix is called a ''
Vandermonde polynomial In algebra, the Vandermonde polynomial of an ordered set of ''n'' variables X_1,\dots, X_n, named after Alexandre-Théophile Vandermonde, is the polynomial:
:V_n = \prod_ (X_j-X_i).
(Some sources use the opposite order (X_i-X_j), which changes the s ...
'' or ''Vandermonde determinant''. Its value is the
polynomial
In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...
:
which is non-zero if and only if all
are distinct.
The Vandermonde determinant was formerly sometimes called the ''discriminant'', but in current terminology the
discriminant
In mathematics, the discriminant of a polynomial is a quantity that depends on the coefficients and allows deducing some properties of the zero of a function, roots without computing them. More precisely, it is a polynomial function of the coef ...
of a polynomial
is the ''square'' of the Vandermonde determinant of the
roots
A root is the part of a plant, generally underground, that anchors the plant body, and absorbs and stores water and nutrients.
Root or roots may also refer to:
Art, entertainment, and media
* ''The Root'' (magazine), an online magazine focusin ...
. The Vandermonde determinant is an
alternating form
In mathematics, the exterior algebra or Grassmann algebra of a vector space V is an associative algebra that contains V, which has a product, called exterior product or wedge product and denoted with \wedge, such that v\wedge v=0 for every vector ...
in the
, meaning that exchanging two
changes the sign, and
thus depends on order for the
. By contrast, the discriminant
does not depend on any order, so that
Galois theory
In mathematics, Galois theory, originally introduced by Évariste Galois, provides a connection between field (mathematics), field theory and group theory. This connection, the fundamental theorem of Galois theory, allows reducing certain problems ...
implies that the discriminant is a
polynomial function
In mathematics, a polynomial is a mathematical expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication and exponentiation to nonnegative int ...
of the coefficients of
.
The determinant formula is proved below in three ways. The first uses polynomial properties, especially the
unique factorization property of
multivariate polynomial
In mathematics, a polynomial is a mathematical expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication and exponentiation to nonnegative intege ...
s. Although conceptually simple, it involves non-elementary concepts of
abstract algebra
In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures, which are set (mathematics), sets with specific operation (mathematics), operations acting on their elements. Algebraic structur ...
. The second proof is based on the
linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrix (mathemat ...
concepts of
change of basis
In mathematics, an ordered basis of a vector space of finite dimension allows representing uniquely any element of the vector space by a coordinate vector, which is a sequence of scalars called coordinates. If two different bases are conside ...
in a vector space and the determinant of a
linear map
In mathematics, and more specifically in linear algebra, a linear map (also called a linear mapping, linear transformation, vector space homomorphism, or in some contexts linear function) is a mapping V \to W between two vector spaces that p ...
. In the process, it computes the
LU decomposition
In numerical analysis and linear algebra, lower–upper (LU) decomposition or factorization factors a matrix as the product of a lower triangular matrix and an upper triangular matrix (see matrix multiplication and matrix decomposition). The produ ...
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,
is a polynomial in the
, with
integer
An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
coefficients. All entries of the
-th column have
total degree . Thus, again by the Leibniz formula, all terms of the determinant have total degree
:
(that is, the determinant is a
homogeneous polynomial
In mathematics, a homogeneous polynomial, sometimes called quantic in older texts, is a polynomial whose nonzero terms all have the same degree. For example, x^5 + 2 x^3 y^2 + 9 x y^4 is a homogeneous polynomial of degree 5, in two variables ...
of this degree).
If, for
, one substitutes
for
, one gets a matrix with two equal rows, which has thus a zero determinant. Thus, considering the determinant as
univariate
In mathematics, a univariate object is an expression (mathematics), expression, equation, function (mathematics), function or polynomial involving only one Variable (mathematics), variable. Objects involving more than one variable are ''wikt:multi ...
in
the
factor theorem
In algebra, the factor theorem connects polynomial factors with polynomial roots. Specifically, if f(x) is a polynomial, then x - a is a factor of f(x) if and only if f (a) = 0 (that is, a is a root of the polynomial). The theorem is a special cas ...
implies that
is a divisor of
It thus follows that for all
and
,
is a divisor of
This will now be strengthened to show that the product of all those divisors of
is a divisor of
Indeed, let
be a polynomial with
as a factor, then
for some polynomial
If
is another factor of
then
becomes zero after the substitution of
for
If
the factor
becomes zero after this substitution, since the factor
remains nonzero. So, by the factor theorem,
divides
and
divides
Iterating this process by starting from
one gets that
is divisible by the product of all
with