Editing Vandermonde matrix (section)

==Applications==
The [[polynomial interpolation]] problem is to find a polynomial <math>p(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_n x^n</math> which satisfies <math>p(x_0)=y_0, \ldots,p(x_m)=y_m</math> for given data points <math>(x_0,y_0),\ldots,(x_m,y_m)</math>. This problem can be reformulated in terms of [[linear algebra]] by means of the Vandermonde matrix, as follows. <math>V</math> computes the values of <math>p(x)</math> at the points  <math>x=x_0,\ x_1,\dots,\ x_m </math> via a matrix multiplication <math>Va = y</math>, where <math>a = (a_0,\ldots,a_n)</math> is the vector of coefficients and <math>y = (y_0,\ldots,y_m)= (p(x_0),\ldots,p(x_m))</math> is the vector of values (both written as column vectors):

<math display="block">\begin{bmatrix}
1 & x_0 & x_0^2 & \dots & x_0^n\\
1 & x_1 & x_1^2 & \dots & x_1^n\\
1 & x_2 & x_2^2 & \dots & x_2^n\\
\vdots & \vdots & \vdots & \ddots &\vdots \\
1 & x_m & x_m^2 & \dots & x_m^n
\end{bmatrix}
\cdot
\begin{bmatrix}
a_0\\
a_1\\ 
\vdots\\ 
a_n 
\end{bmatrix}
=
\begin{bmatrix}
p(x_0)\\
p(x_1)\\
\vdots\\
p(x_m)
\end{bmatrix}.
</math>If <math>n = m</math> and <math>x_0,\dots,\ x_n </math> 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 <math>p(x)</math> by solving for its coefficients <math>a </math> in the equation <math>Va = y</math>:<ref>François Viète (1540-1603), Vieta's formulas, https://en.wikipedia.org/wiki/Vieta%27s_formulas</ref> <blockquote><math>a = V^{-1}y</math>. </blockquote>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#Over univariate polynomial rings and Euclidean domains|Chinese remainder theorem for polynomials]].

In [[statistics]], the equation <math>Va = y</math> means that the Vandermonde matrix is the [[design matrix]] of [[polynomial regression]].

In [[numerical analysis]], solving the equation <math>Va = y</math> [[System of linear equations#Solving a linear system|naïvely by Gaussian elimination]] results in an algorithm with [[time complexity]] O(''n''<sup>3</sup>). Exploiting the structure of the Vandermonde matrix, one can use [[Newton polynomial|Newton's divided differences method]]<ref>{{Cite journal |last1=Björck |first1=Å. |last2=Pereyra |first2=V. |date=1970 |title=Solution of Vandermonde Systems of Equations |journal=[[American Mathematical Society]] |volume=24 |issue=112 |pages=893–903 |doi=10.1090/S0025-5718-1970-0290541-1|s2cid=122006253 |doi-access=free }}</ref> (or the [[Lagrange polynomials|Lagrange interpolation formula]]<ref>{{Cite book |last1=Press |first1=WH |title=Numerical Recipes: The Art of Scientific Computing |last2=Teukolsky |first2=SA |last3=Vetterling |first3=WT |last4=Flannery |first4=BP |publisher=Cambridge University Press |year=2007 |isbn=978-0-521-88068-8 |edition=3rd |location=New York |chapter=Section 2.8.1. Vandermonde Matrices |chapter-url=http://apps.nrbook.com/empanel/index.html?pg=94}}</ref><ref>Inverse of Vandermonde Matrix (2018), https://proofwiki.org/wiki/Inverse_of_Vandermonde_Matrix</ref>) to solve the equation in O(''n''<sup>2</sup>) time, which also gives the [[LU decomposition|UL factorization]] of <math>V^{-1}</math>. The resulting algorithm produces extremely accurate solutions, even if <math>V</math> is [[Condition number|ill-conditioned]].<ref name=":0" /> (See [[polynomial interpolation]].)

The Vandermonde determinant is used in the [[representation theory of the symmetric group]].<ref>{{Fulton-Harris}} ''Lecture 4 reviews the representation theory of symmetric groups, including the role of the Vandermonde determinant''.</ref>

When the values <math>x_i</math> belong to a [[finite field]], the Vandermonde determinant is also called the [[Moore matrix|Moore determinant]], and has properties which are important in the theory of [[BCH code]]s and [[Reed–Solomon error correction]] codes.

The [[discrete Fourier transform]] is defined by a specific Vandermonde matrix, the [[DFT matrix]], where the <math>x_i</math> are chosen to be {{math|''n''}}th [[roots of unity]]. The [[Fast Fourier transform]] computes the product of this matrix with a vector in <math>O(n\log^2n)</math> time.<ref>Gauthier, J. "Fast Multipoint Evaluation On n Arbitrary Points." ''Simon Fraser University, Tech. Rep'' (2017).</ref> See the article on [[Polynomial_evaluation#Multipoint_evaluation|Multipoint Polynomial evaluation]] for details.

In the [[Physics|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 <math>k</math>-faces of [[cyclic polytope]]s. Specifically, if <math>F = C_{d}(t_{i_{1}}, \dots, t_{i_{k + 1}})</math> is a <math>k</math>-face of the cyclic polytope  <math>C_d(T) \subset \mathbb{R}^{d}</math> corresponding to  <math>T = \{t_{1}< \cdots < t_{N}\} \subset \mathbb{R}</math>, then<math display="block">\mathrm{nvol}(F) = \frac{1}{k!}\prod_{1 \leq m < n \leq k + 1}{(t_{i_{n}} - t_{i_{m}})}.</math>