Vandermonde matrix

The polynomial interpolation problem is to find a polynomial $p(x)\; =\; a\_0\; +\; a\_1\; x\; +\; a\_2\; x^2\; +\; \backslash dots\; +\; a\_n\; x^n$ which satisfies $p(x\_0)=y\_0,\; \backslash ldots,p(x\_m)=y\_m$ for given data points $(x\_0,y\_0),\backslash ldots,(x\_m,y\_m)$. 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 $x=x\_0,\backslash \; x\_1,\backslash dots,\backslash \; x\_m$ via a matrix multiplication $Va\; =\; y$, where $a\; =\; (a\_0,\backslash ldots,a\_n)$ is the vector of coefficients and $y\; =\; (y\_0,\backslash ldots,y\_m)=\; (p(x\_0),\backslash ldots,p(x\_m))$ is the vector of values (both written as column vectors):

$$\backslash 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}.

If $n\; =\; m$ and $x\_0,\backslash dots,\backslash \; x\_n$ 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$:François Viète (1540-1603), Vieta's formulas, https://en.wikipedia.org/wiki/Vieta%27s_formulas

$a\; =\; V^\{-1\}y$.

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(n³). Exploiting the structure of the Vandermonde matrix, one can use Newton's divided differences method{{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 }} (or the Lagrange interpolation formula{{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}}Inverse of Vandermonde Matrix (2018), https://proofwiki.org/wiki/Inverse_of_Vandermonde_Matrix) to solve the equation in O(n²) 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.{{Fulton-Harris}} Lecture 4 reviews the representation theory of symmetric groups, including the role of the Vandermonde determinant.

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 {{math|n}}th roots of unity. The Fast Fourier transform computes the product of this matrix with a vector in $O(n\backslash log^2n)$ time.Gauthier, J. "Fast Multipoint Evaluation On n Arbitrary Points." Simon Fraser University, Tech. Rep (2017). See the article on Multipoint Polynomial evaluation for details.

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 $F\; =\; C\_\{d\}(t\_\{i\_\{1\}\},\; \backslash dots,\; t\_\{i\_\{k\; +\; 1\}\})$ is a $k$-face of the cyclic polytope $C\_d(T)\; \backslash subset\; \backslash mathbb\{R\}^\{d\}$ corresponding to , then

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 $p(x)=(x-x\_0)\backslash cdots(x-x\_n)$ 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 $\backslash det(V)$ thus depends on order for the $x\_i$. By contrast, the discriminant $\backslash 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.

The first proof relies on properties of polynomials.

By the Leibniz formula, $\backslash 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

:$0\; +\; 1\; +\; 2\; +\; \backslash cdots\; +\; n\; =\; \backslash frac\{n(n+1)\}2;$

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

If, for $i\; \backslash 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 $\backslash det(V).$ It thus follows that for all $i$ and $j$, $x\_j-x\_i$ is a divisor of $\backslash det(V).$

This will now be strengthened to show that the product of all those divisors of $\backslash det(V)$ is a divisor of $\backslash det(V).$ Indeed, let $p$ be a polynomial with $x\_i-x\_j$ as a factor, then $p=(x\_i-x\_j)\backslash ,q,$ 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 $\backslash \{x\_i,x\_j\backslash \}\backslash neq\; \backslash \{x\_k,\; x\_l\backslash \},$ 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 $(x\_i-x\_j)\backslash ,(x\_k-x\_l)$ divides $p.$

Iterating this process by starting from $\backslash det(V),$ one gets that $\backslash det(V)$ is divisible by the product of all $x\_i-x\_j$ with

:

where $Q$ is a polynomial. As the product of all $x\_j-x\_i$ and $\backslash 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 $x\_1\; x\_2^2\backslash cdots\; x\_n^n$, which is also the monomial that is obtained by taking the first term of all factors in

:

Let {{mvar|F}} be a field containing all $x\_i,$ and $P\_n$ the {{mvar|F}} vector space of the polynomials of degree at most {{mvar|n}} with coefficients in {{mvar|F}}. Let

:$\backslash varphi:P\_n\backslash to\; F^\{n+1\}$

be the linear map that maps every polynomial in $P\_n$ to the {{tmath|(n+1)}}-tuple of its values at the {{math|x_i}} that is,

:$\backslash phi(p)\; \backslash mapsto\; (p(x\_0),\; p(x\_1),\; \backslash ldots,\; p(x\_n))$.

The Vandermonde matrix is the matrix of $\backslash 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 {{mvar|M}} (from the right). This does not change the determinant, if the determinant of {{mvar|M}} is {{val|1}}.

The polynomials $1$, $x-x\_0$, $(x-x\_0)(x-x\_1)$, …, $(x-x\_0)\; (x-x\_1)\; \backslash cdots\; (x-x\_\{n-1\})$ are monic of respective degrees 0, 1, …, {{mvar|n}}. Their matrix on the monomial basis is an upper-triangular matrix {{mvar|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 $\backslash varphi$ on this new basis is

:$\backslash begin\{bmatrix\}$

1 & 0 & 0 & \ldots & 0 \\

1 & x_1-x_0 & 0 & \ldots & 0 \\

1 & x_2-x_0 & (x_2-x_0)(x_2-x_1) & \ldots & 0 \\

\vdots & \vdots & \vdots & \ddots & \vdots \\

1 & x_n-x_0 & (x_n-x_0)(x_n-x_1) & \ldots &

(x_n-x_0)(x_n-x_1)\cdots (x_n-x_{n-1})

\end{bmatrix}.

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 {{mvar|V}} as $V=LU^\{-1\}$.

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

:$V\; =\; \backslash begin\{bmatrix\}$

1&0&0&0&\cdots&0\\

1&x_1-x_0&x_1(x_1-x_0)&x_1^2(x_1-x_0)&\cdots&x_1^{n-1}(x_1-x_0)\\

1&x_2-x_0&x_2(x_2-x_0)&x_2^2(x_2-x_0)&\cdots&x_2^{n-1}(x_2-x_0)\\

\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\

1&x_n-x_0&x_n(x_n-x_0)&x_n^2(x_n-x_0)&\cdots&x_n^{n-1}(x_n-x_0)\\

\end{bmatrix}

Applying the Laplace expansion formula along the first row, we obtain $\backslash det(V)=\backslash det(B)$, with

:$B\; =\; \backslash begin\{bmatrix\}$

x_1-x_0&x_1(x_1-x_0)&x_1^2(x_1-x_0)&\cdots&x_1^{n-1}(x_1-x_0)\\

x_2-x_0&x_2(x_2-x_0)&x_2^2(x_2-x_0)&\cdots&x_2^{n-1}(x_2-x_0)\\

\vdots&\vdots&\vdots&\ddots&\vdots\\

x_n-x_0&x_n(x_n-x_0)&x_n^2(x_n-x_0)&\cdots&x_n^{n-1}(x_n-x_0)\\

\end{bmatrix}

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

:$\backslash det(V)=(x\_1-x\_0)(x\_2-x\_0)\backslash cdots(x\_n-x\_0)\backslash begin\{vmatrix\}$

1&x_1&x_1^2&\cdots&x_1^{n-1}\\

1&x_2&x_2^2&\cdots&x_2^{n-1}\\

\vdots&\vdots&\vdots&\ddots&\vdots\\

1&x_n&x_n^2&\cdots&x_n^{n-1}\\

\end{vmatrix}=\prod_{1,

where $V\text{'}$ is a Vandermonde matrix in $x\_1,\backslash ldots,\; x\_n$. Iterating this process on this smaller Vandermonde matrix, one eventually gets the desired expression of $\backslash det(V)$ as the product of all $x\_j-x\_i$ such that

• An {{math|m × n}} rectangular Vandermonde matrix such that {{math|m ≤ n}} has rank {{math|m}} if and only if all {{math|x_i}} are distinct.
• An {{math|m × n}} rectangular Vandermonde matrix such that {{math|m ≥ n}} has rank {{math|n}} if and only if there are {{mvar|n}} of the {{math|x_i}} that are distinct.
• A square Vandermonde matrix is invertible if and only if the {{math|x_i}} are distinct. An explicit formula for the inverse is known (see below).{{Cite book

| title = Inverse of the Vandermonde matrix with applications

| last = Turner

| first = L. Richard

| date = August 1966

| url =https://ntrs.nasa.gov/api/citations/19660023042/downloads/19660023042.pdf

}}{{Cite journal

| volume = 65

| issue = 2

| pages = 95–100

| last = Macon

| first = N.

|author2=A. Spitzbart

| title = Inverses of Vandermonde Matrices

| journal = The American Mathematical Monthly

| date = February 1958

| jstor = 2308881

| doi = 10.2307/2308881}}

If the columns of the Vandermonde matrix, instead of $1,\; x,\; x^2,\; ...$, are general polynomials $p\_0,\; p\_1,\; ...,\; p\_n$, such that each one has degree $0,\; 1,\; ...,\; n$, that is, if $V\; =\; [p\_i(x\_j)]\_\{i,\; j\; \backslash in\; 0:n\}$, $$\backslash det\; V(x\_\{0:n\})\; =\; \backslash prod\_k\; c\_k\; \backslash Delta(x)$$where $c\_0,\; ...,\; c\_n$ are the head coefficients of $p\_0,\; p\_1,\; ...,\; p\_n$, and $\backslash Delta(x)\; =\; \backslash prod\_\{j>k\}\; (x\_j\; -\; x\_k)$ is the Vandermonde determinant.

{{Math proof|title=Proof|proof=

$\backslash det\; V(x\_\{0:n\})$ is zero whenever $x\_j\; =\; x\_k$, and has degree $\backslash frac\; 12\; n(n+1)$, so it is a multiple of $\backslash prod\_\{j>k\}\; (x\_j\; -\; x\_k)$. To find the constant in front, simply calculate the coefficient of the term $x\_0^0\; \backslash dots\; x\_n^n$, which is $c\_0\; \backslash dots\; c\_n$.

}}

By multiplying with the Hermitian conjugate, we find that $$$$

\det \left[\sum_l p_j(z_l) p_k(z_l^*)\right] = \prod_k |c_k|^2 |\Delta(z)|^2

{{Math theorem

| math_statement = Fix $x$, and at the $y\; \backslash to\; 0$ limit, $$\backslash det\; [e^\{x\_i\; y\_j\}]\; =\; \backslash frac\{1\}\{1!\; \backslash dots\; n!\; (n+1)!\}\backslash Delta(x)\; \backslash Delta(y)\; +\; o(\backslash Delta(y))$$ uniformly for $y$

| note = Tao 2012, page 251

}}

{{hidden begin|style=width:100%|ta1=center|border=1px #aaa solid|title=Proof}}

{{Math proof|title=Proof|proof=

If any $x\_j\; =\; x\_k$ or $y\_j\; =\; y\_k$, then the determinant is zero, so it has the form $$\backslash det\; [e^\{x\_i\; y\_j\}]\; =\; C(x,y)\; \backslash Delta(x)\; \backslash Delta(y)$$ where $C(x,y)$ is some power series in $x,\; y$.

The left side is a sum of the form $$$$

\sum_{\sigma} (-1)^

Expand them by Taylor expansion. For fixed $x$, the series is uniformly convergent in $y$ in a neighborhood of zero.

To find the constant term of $C(x,\; y)$, simply calculate the coefficient of the term $x\_0^0\; y\_0^0\; \backslash dots\; x\_n^n\; y\_n^n$, which is $\backslash frac\{1\}\{1!\; \backslash cdots\; (n+1)!\}$.

By the symmetry of the determinant, the next lowest-powered term of $C(x,\; y)$ is of form $a(x\_0y\_0\; +\; \backslash dots\; +\; x\_n\; y\_n)$, which is $o(1)$ as $y\; \backslash to\; 0$.

}}{{hidden end}}

As explained above in Applications, the polynomial interpolation problem for $p(x)\; =\; a\_0\; +\; a\_1\; x\; +\; a\_2\; x^2\; +\; \backslash dots\; +\; a\_n\; x^n$satisfying $p(x\_0)=y\_0,\; \backslash ldots,p(x\_n)=y\_n$ 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

$$V^\{-1\}=$$

\begin{bmatrix}

1 & x_0 & \dots & x_0^n\\

\vdots & \vdots & &\vdots \\[.5em]

1 & x_n & \dots & x_n^n

\end{bmatrix}^{-1}

= L =

\begin{bmatrix}

L_{00} & \!\!\!\!\cdots\!\!\!\! & L_{0n}

\\

\vdots & & \vdots

\\

L_{n0} & \!\!\!\!\cdots\!\!\!\! & L_{nn}

\end{bmatrix}

are the coefficients of the Lagrange polynomials

$L\_j(x)=L\_\{0j\}+L\_\{1j\}x+\backslash cdots+L\_\{nj\}x^\{n\}$

= \prod_{0\leq i\leq n \atop i\neq j}\frac{x-x_i}{x_j-x_i}

= \frac{f(x)}{(x-x_j)\,f'(x_j)}\,,

{{see also|Hermite interpolation}}

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 $p(x\_1),\backslash ,\; ...,\backslash ,\; p(x\_n)$, where $x\_1,\backslash ,\; ...,\backslash ,\; x\_n$ 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

:$\backslash begin\{cases\}$

p(0) = y_1 \\

p'(0) = y_2 \\

p(1) = y_3

\end{cases}

where $p(x)\; =\; ax^2+bx+c$, has a unique solution for all $y\_1,y\_2,y\_3$ with $y\_1\backslash neq\; y\_3$. In general, suppose that $x\_1,\; x\_2,\; ...,\; x\_n$ are (not necessarily distinct) numbers, and suppose for simplicity that equal values are adjacent:

:$$

x_1 = \cdots = x_{m_1},\

x_{m_1+1} = \cdots = x_{m_2},\

\ldots,\

x_{m_{k-1}+1} = \cdots = x_{m_k}

where and $x\_\{m\_1\},\; \backslash ldots\; ,x\_\{m\_k\}$ are distinct. Then the corresponding interpolation problem is

:$\backslash begin\{cases\}$

p(x_{m_1}) = y_1, & p'(x_{m_1}) = y_2, & \ldots, & p^{(m_1-1)}(x_{m_1}) = y_{m_1}, \\

p(x_{m_2}) = y_{m_1+1}, & p'(x_{m_2})=y_{m_1+2}, & \ldots, & p^{(m_2-m_1-1)}(x_{m_2}) = y_{m_2}, \\

\qquad \vdots & & & \qquad\vdots \\

p(x_{m_k}) = y_{m_{k-1}+1}, & p'(x_{m_k}) = y_{m_{k-1}+2}, & \ldots, & p^{(m_k-m_{k-1}-1)}(x_{m_k}) = y_{m_k}.

\end{cases}

The corresponding matrix for this problem is called a confluent Vandermonde matrix, given as follows.{{Cite journal | volume = 57| issue = 1| pages = 15–21| last = Kalman| first = D.| title = The Generalized Vandermonde Matrix| journal = Mathematics Magazine| date = 1984| doi = 10.1080/0025570X.1984.11977069}} If $1\; \backslash leq\; i,j\; \backslash leq\; n$, then for a unique $0\; \backslash leq\; \backslash ell\; \backslash leq\; k-1$ (denoting $m\_0\; =\; 0$). We let

:$V\_\{i,j\}\; =\; \backslash begin\{cases\}$

0 & \text{if } j < i - m_\ell, \\[6pt]

\dfrac{(j-1)!}{(j - (i - m_\ell))!} x_i^{j-(i-m_\ell)} & \text{if } j \geq i - m_\ell.

\end{cases}

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 the above 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\backslash 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 $p(x\_i),\; p\text{'}(x\_i)$ is similar to giving $p(x\_i),\; p(x\_i\; +\; \backslash varepsilon)$ for small $\backslash varepsilon$. Geometers have studied the problem of tracking confluent points along their tangent lines, known as compacitification of configuration space.

• {{slink|Companion matrix#Diagonalizability}}
• Schur polynomial – a generalization
• Alternant matrix
• Lagrange polynomial
• Wronskian
• List of matrices
• Moore determinant over a finite field
• Vieta's formulas

{{reflist}}

• {{Cite book |last=Tao |first=Terence |title=Topics in random matrix theory |date=2012 |publisher=American Mathematical Society |isbn=978-0-8218-7430-1 |series=Graduate studies in mathematics |location=Providence, R.I}}

• {{Citation |last=Ycart |first=Bernard |title=A case of mathematical eponymy: the Vandermonde determinant |journal=Revue d'Histoire des Mathématiques |volume=13 |year=2013 |arxiv=1204.4716|bibcode=2012arXiv1204.4716Y }}.

{{Matrix classes}}

Category:Matrices (mathematics)

Category:Determinants

Category:Numerical linear algebra