Vandermonde matrix: Difference between revisions

Content deleted Content added

Inline

Revision as of 07:26, 4 April 2018

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

V={\begin{bmatrix}1&\alpha _{1}&\alpha _{1}^{2}&\dots &\alpha _{1}^{n-1}\\1&\alpha _{2}&\alpha _{2}^{2}&\dots &\alpha _{2}^{n-1}\\1&\alpha _{3}&\alpha _{3}^{2}&\dots &\alpha _{3}^{n-1}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&\alpha _{m}&\alpha _{m}^{2}&\dots &\alpha _{m}^{n-1}\end{bmatrix}},

or

V_{i,j}=\alpha _{i}^{j-1}\,

for all indices i and j.^[1] (Some authors use the transpose of the above matrix.)

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

\det(V)=\prod _{1\leq i<j\leq n}(\alpha _{j}-\alpha _{i}).

This is called the Vandermonde determinant or Vandermonde polynomial. If all the numbers $\alpha _{i}$ 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 $\alpha _{i}$ , meaning that exchanging two $\alpha _{i}$ changes the sign, while permuting the $\alpha _{i}$ by an even permutation does not change the value of the determinant. It thus depends on the choice of an order on the $\alpha _{i}$ , 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 $\alpha _{i}$ as roots.

Proof

The main property of a square Vandermonde matrix

V={\begin{bmatrix}1&x_{1}&x_{1}^{2}&\dots &x_{1}^{n-1}\\1&x_{2}&x_{2}^{2}&\dots &x_{2}^{n-1}\\1&x_{3}&x_{3}^{2}&\dots &x_{3}^{n-1}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{n}&x_{n}^{2}&\dots &x_{n}^{n-1}\end{bmatrix}}

is that its determinant has the simple form

\det(V)=\prod _{1\leq i<j\leq n}(x_{j}-x_{i}).

This may be proved either by using proprieties 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 $x_{i},$ with integer coefficients. All entries of the $i$ th column have the total degree $i - 1$ . Thus, again by Leibniz formula, all terms of the determinant have the total degree

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

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

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

\det(V)=Q\prod _{1\leq i<j\leq n}(x_{j}-x_{i}),

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

\det(V)=\prod _{1\leq i<j\leq n}(x_{j}-x_{i}).

By row and columns 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.

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

{\begin{bmatrix}1&\mathbf {L} \\\mathbf {0} &A\end{bmatrix}},

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

\det(A)=\det(V).

The entry of the $(i - 1)$ th row and the $(j - 1)$ th column of $A$ (that is the $i$ th row and the $j$ th column of the whole matrix) is

x_{i}^{j-1}-x_{1}^{j-1}=(x_{i}-x_{1})\sum _{k=0}^{j-2}x_{i}^{k}x_{1}^{j-2-k}.

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

\det(V)=\det(A)=\det(B)\prod _{i=2}^{n}(x_{i}-x_{1}).

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

b_{i,j}=\sum _{k=0}^{j-2}x_{i}^{k}x_{1}^{j-2-k}=x_{i}^{j-2}+x_{1}b_{i,j-1},

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

Thus, subtracting, for $j$ running from $n$ down to 2, the $(j - 2)$ th column of $B$ multiplied by $a_{1}$ from the the $(j - 1)$ th column, one gets a $(n - 1) \times (n - 1)$ Vandermonde matrix in $x_{2},\ldots ,x_{n},$ 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 $x_{j}-x_{i}.$

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

W={\begin{bmatrix}w_{1,1}&w_{1,2}&w_{1,3}&\dots &w_{1,n}\\0&w_{2,2}&w_{2,3}&\dots &w_{2,n}\\0&0&w_{3,3}&\dots &w_{3,n}\\\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&0&\dots &w_{n,n}\end{bmatrix}},

which has the same determinant as $V$ .

A proof by induction on the steps of Gaussian elimination allows showing that, for $1 \leq i \leq j \leq n$ , one has

w_{i,j}=M_{j-i}(\mathbf {x} _{i-1},x_{i})\prod _{k=1}^{i-1}(x_{i}-x_{k}),

where $\mathbf {x} _{i-1}$ is an abbreviation for $x_{1},\ldots ,x_{i-1}$ , and $M_{d}(\mathbf {x} _{i-1},x_{i})$ is the sum of all monomials of degree $d$ in $\mathbf {x} _{i-1},x_{i}.$ In particular, the first rows of $V$ and $W$ are equal, and the factor $M_{j-i}(\mathbf {x} _{i-1},x_{i})$ 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$

M_{d}(\mathbf {x} _{i-1},x_{h})-M_{d}(\mathbf {x} _{i-1},x_{i})=(x_{h}-x_{i})M_{d-1}(\mathbf {x} _{i-1},x_{i},x_{h})

For the recursion, one has to describe the matrix at each step of the Gaussian elimination. Let $a_{i,j}$ be the entry of the $i$ th row and $j$ th column of this variable matrix. Before the $i$ th 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 $i \leq j \leq n$ and $i \leq h \leq n$ , one has

a_{h,j}=M_{j-i}(\mathbf {x} _{i-1},x_{h})\prod _{k=1}^{i-1}(x_{h}-x_{k}).

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

{\begin{aligned}a_{h,j}&=M_{j-i}(\mathbf {x} _{i-1},x_{h})\prod _{k=1}^{i-1}(x_{h}-x_{k})-{\frac {M_{0}(\mathbf {x} _{i-1},x_{h})\prod _{k=1}^{i-1}(x_{h}-x_{k})}{M_{0}(\mathbf {x} _{i-1},x_{i})\prod _{k=1}^{i-1}(x_{i}-x_{k})}}M_{j-i}(\mathbf {x} _{i-1},x_{i})\prod _{k=1}^{i-1}(x_{i}-x_{k})\\&=\left(M_{j-i}(\mathbf {x} _{i-1},x_{h})-M_{j-i}(\mathbf {x} _{i-1},x_{i})\right)\prod _{k=1}^{i-1}(x_{h}-x_{k})\\&=M_{j-(i+1)}(\mathbf {x} _{i-1},x_{i},x_{h})\prod _{k=1}^{i}(x_{h}-x_{k}).\end{aligned}}

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

It follows from the structure of $W$ that $\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 \times n$ rectangular Vandermonde matrix such that $m \leq n$ has maximum rank $m$ if and only if all $x i$ are distinct.

A $m \times n$ rectangular Vandermonde matrix such that $m \geq n$ has maximum rank $n$ if and only if there are $n$ of the $x i$ that are distinct.

A square Vandermonde matrix is invertible if and only if the $x i$ are distinct. An explicit formula for the inverse is known.^[2]^[3]^[4]

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 $\alpha _{i}$ 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 $\alpha _{i}$ and the values of the polynomial at the $\alpha _{i}.$ However, the interpolation polynomial is generally easier to compute with the Lagrange interpolation formula.^[5]

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

When the values $\alpha _{k}$ belong to a finite field, then the Vadermonde determinant is also called Moore determinant, and has specific properties that are used, for example for 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.

Confluent Vandermonde matrices

When two or more α_i are equal, the corresponding polynomial interpolation problem (see below) is underdetermined. In that case one may use a generalization called confluent Vandermonde matrices, which makes the matrix non-singular while retaining most properties. If α_i = α_i + 1 = ... = α_i+k and α_i ≠ α_i − 1, then the (i + k)th row is given by

V_{i+k,j}={\begin{cases}0,&{\text{if }}j\leq k;\\{\frac {(j-1)!}{(j-k-1)!}}\alpha _{i}^{j-k-1},&{\text{if }}j>k.\end{cases}}

The above formula for confluent Vandermonde matrices can be readily derived by letting two parameters $\alpha _{i}$ and $\alpha _{j}$ go arbitrarily close to each other. The difference vector between the rows corresponding to $\alpha _{i}$ and $\alpha _{j}$ scaled to a constant yields the above equation (for k = 1). Similarly, the cases k > 1 are obtained by higher order differences. Consequently, the confluent rows are derivatives of the original Vandermonde row.

References

^ Roger A. Horn and Charles R. Johnson (1991), Topics in matrix analysis, Cambridge University Press. See Section 6.1.
^ Turner, L. Richard. Inverse of the Vandermonde matrix with applications (PDF).
^ Macon, N.; A. Spitzbart (February 1958). "Inverses of Vandermonde Matrices". The American Mathematical Monthly. 65 (2). The American Mathematical Monthly, Vol. 65, No. 2: 95–100. doi:10.2307/2308881. JSTOR 2308881.
^ Inverse of Vandermonde Matrix (ProofWiki)
^ 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 Template:Inconsistent citations{{cite book}}: CS1 maint: postscript (link)
^ Fulton, William; Harris, Joe (1991). Representation theory. A first course. Graduate Texts in Mathematics, Readings in Mathematics. Vol. 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.

External links

Vandermonde matrix at ProofWiki

[1] Roger A. Horn and Charles R. Johnson (1991), Topics in matrix analysis, Cambridge University Press. See Section 6.1.

[2] Turner, L. Richard. Inverse of the Vandermonde matrix with applications (PDF).

[3] Macon, N.; A. Spitzbart (February 1958). "Inverses of Vandermonde Matrices". The American Mathematical Monthly. 65 (2). The American Mathematical Monthly, Vol. 65, No. 2: 95–100. doi:10.2307/2308881. JSTOR 2308881.

[4] Inverse of Vandermonde Matrix (ProofWiki)

[5] 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 Template:Inconsistent citations{{cite book}}: CS1 maint: postscript (link)

[6] Fulton, William; Harris, Joe (1991). Representation theory. A first course. Graduate Texts in Mathematics, Readings in Mathematics. Vol. 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.

[1]

[2]

[3]

[4]

[5]

[6]

@@ Line 17: / Line 17: @@
 This is called the '''Vandermonde determinant''' or '''[[Vandermonde polynomial]].''' If all the numbers <math>\alpha_i</math> are distinct, then it is non-zero.
-The Vandermonde determinant is sometimes called the [[discriminant]], although many sources, including this article, refer to the discriminant as the square of this determinant. Note that the Vandermonde determinant is ''alternating'' in the entries, meaning that permuting the <math>\alpha_i</math> by an [[odd permutation]] changes the sign, while permuting them by an [[even permutation]] does not change the value of the determinant. It thus depends on the order, while its square (the discriminant) does not depend on the order.
+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]] <math>\alpha_i</math>, meaning that exchanging two <math>\alpha_i</math> changes the sign, while permuting the <math>\alpha_i</math> by an [[even permutation]] does not change the value of the determinant. It thus depends on the choice of an order on the <math>\alpha_i</math>, 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 <math>\alpha_i</math> as roots.
+==Proof==
-When two or more α<sub>''i''</sub> are equal, the corresponding [[polynomial interpolation]] problem (see below) is <!-- [[Well-posed problem|ill-posed]] --> [[underdetermined system|underdetermined]].  In that case one may use a generalization called '''confluent Vandermonde matrices''', which makes the matrix <!-- [[positive-definite matrix|positive definite]] --> [[Invertible matrix|non-singular]] while retaining most properties. If α<sub>''i''</sub>&nbsp;=&nbsp;α<sub>''i''&nbsp;+&nbsp;1</sub>&nbsp;=&nbsp;...&nbsp;=&nbsp;α<sub>''i''+''k''</sub> and α<sub>''i''</sub>&nbsp;≠&nbsp;α<sub>''i''&nbsp;−&nbsp;1</sub>, then the (''i''&nbsp;+&nbsp;''k'')th row is given by
+The main property of a square Vandermonde matrix
+:<math>V=\begin{bmatrix}
+& x_1 & x_1^2 & \dots & x_1^{n-1}\\
+& x_2 & x_2^2 & \dots & x_2^{n-1}\\
+& x_3 & x_3^2 & \dots & x_3^{n-1}\\
+\vdots & \vdots & \vdots & \ddots &\vdots \\
+& x_n & x_n^2 & \dots & x_n^{n-1}
+\end{bmatrix}</math>
+is that its determinant has the simple form
+:<math>\det(V)=\prod_{1\le i<j\le n} (x_j-x_i).</math>
+This may be proved either by using proprieties of polynomials or [[elementary matrix|elementary row and column operations]]. The former is simpler but it is non-constructive and uses [[unique factorization domain|unique factorization property]] of [[multivariate polynomial]]s. 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.
-:<math> V_{i+k,j} = \begin{cases} 0, & \text{if } j \le k; \\ \frac{(j-1)!}{(j-k-1)!} \alpha_i^{j-k-1}, & \text{if } j > k. \end{cases} </math>
+===Using polynomial properties===
-The above formula for confluent Vandermonde matrices can be readily derived by letting two parameters <math>\alpha_i</math> and <math>\alpha_j</math> go arbitrarily close to each other. The difference vector between the rows corresponding to <math>\alpha_i</math> and <math>\alpha_j</math> scaled to a constant yields the above equation (for ''k''&nbsp;=&nbsp;1). Similarly, the cases ''k''&nbsp;>&nbsp;1 are obtained by higher order differences. Consequently, the confluent rows are derivatives of the original Vandermonde row.
+By [[Leibniz formula (determinant)|Leibniz formula]], {{math|det(''V'')}} is a polynomial in the <math>x_i,</math> with integer coefficients. All entries of the {{mvar|i}}th column have the [[total degree]] {{math|''i'' – 1}}. Thus, again by Leibniz formula, all terms of the determinant have the total degree
-==Properties==
+:<math>0 + 1 + 2 + \cdots + (n-1) = \frac{n(n-1)}2;</math>
-In the case of a square Vandermonde matrix, the [[Leibniz formula (determinant)|Leibniz formula]] for the determinant gives
+(that is the determinant is a [[homogeneous polynomial]] of this degree).
+If, for {{math|''i'' ≠ ''j''}}, one substitutes <math>x_i</math> for <math>x_j</math>, one gets a matrix with two equal columns, which has thus a zero determinant. Thus, by [[factor theorem]], <math>x_j-x_j</math> is a divisor of {{math|det(''V'')}}. By [[unique factorization domain|unique factorization property]] of [[multivariate polynomial]]s, the product of all <math>x_j-x_j</math> divides {{math|det(''V'')}}, that is
-:<math> \det(V) = \sum_{\sigma \in S_n} \sgn(\sigma) \prod_{i = 1}^n \alpha_i^{\sigma(i)-1}, </math>
+:<math>\det(V)=Q\prod_{1\le i<j\le n} (x_j-x_i),</math>
+where {{mvar|Q}} is a polynomial. As the product of all <math>x_j-x_j</math> and {{math|det(''V'')}} have the same degree <math>n(n -1)/2,</math> the polynomial {{mvar|Q}} is, in fact, a constant. This constant is one, because the product of the diagonal entries of {{mvar|V}} is
+<math>x_2x_3^2\cdots x_n^{n-1},</math>
+which is also the monomial that is obtained by taking the first term of all factors in <math>\textstyle \prod_{1\le i<j\le n} (x_j-x_i).</math> This proves that
+:<math>\det(V)=\prod_{1\le i<j\le n} (x_j-x_i).</math>
+===By row and columns operations===
-where ''S''<sub>''n''</sub> denotes the set of [[permutation]]s of <math>\{1,\ldots,n\}</math>, and <math>\sgn(\sigma)</math> denotes the [[even and odd permutations|signature]] of the permutation&nbsp;''σ''. This determinant factors as
+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.
-:<math>\sum_{\sigma \in S_n} \sgn(\sigma) \prod_{i = 1}^n \alpha_i^{\sigma(i)-1}=\prod_{1\le i<j\le n} (\alpha_j-\alpha_i). </math>
+I one subtracts the first row of {{mvar|V}} to all the other rows, the determinant is not changed, and the new matrix has the form
-Each of these factors must divide the determinant, because the latter is an [[alternating polynomial]] in the ''n'' variables. It also follows that the Vandermonde determinant divides any other alternating polynomial; the quotient will be a [[symmetric polynomial]].
+:<math>\begin{bmatrix}
+&\mathbf L\\\mathbf 0& A
+\end{bmatrix},</math>
+where <math>\mathbf L</math> is a row matrix, <math>\mathbf 0</math> is a column of zeros, and {{mvar|A}} is a square matrix, such that
+:<math>\det(A) = \det(V).</math>
+The entry of the {{math|(''i'' – 1)}}th row and the {{math|(''j'' – 1)}}th column of {{mvar|A}} (that is the {{mvar|i}}th row and the {{mvar|j}}th column of the whole matrix) is
+:<math>x_i^{j-1} -x_1^{j-1}=(x_i-x_1)\sum_{k=0}^{j-2} x_i^kx_1^{j-2-k}.</math>
+Dividing out <math>x_i-x_1</math> from the {{math|(''i'' – 1)}}th row of {{mvar|A}}, for {{math|1=''i'' = 2, ..., ''n''}}, one gets a matrix {{mvar|B}} such that
+:<math>\det(V)=\det(A)=\det(B)\prod_{i=2}^n (x_i-x_1).</math>
+The coefficient of the  {{math|(''i'' – 1)}}th row and the {{math|(''j'' – 1)}}th column of {{mvar|B}} is
+:<math>b_{i,j}=\sum_{k=0}^{j-2} x_i^kx_1^{j-2-k}=x_i^{j-2} + x_1b_{i,j-1},</math>
+for {{math|1=''i'' = 2, ..., n}}, and setting <math>b_{i,1}=1.</math>
+Thus, subtracting, for {{mvar|j}} running from {{mvar|n}} down to 2, the {{math|(''j'' – 2)}}th column of {{mvar|B}} multiplied by <math>a_1</math> from the the {{math|(''j'' – 1)}}th column, one gets a {{math|(''n'' – 1) × (''n'' – 1)}} Vandermonde matrix in <math>x_2,\ldots, x_n,</math> which has the same determinant as {{mvar|B}}. Iterating this process on this smaller Vandermonde matrix, one gets eventually the desired expression of {{math|det(''V'')}} as the product of the <math>x_j-x_i.</math>
-If ''m''&nbsp;≤&nbsp;''n'', then the matrix ''V'' has maximum [[rank of a matrix|rank]] (''m'') [[if and only if]] all α<sub>''i''</sub> are distinct. A square Vandermonde matrix is thus [[invertible matrix|invertible]] if and only if the α<sub>''i''</sub> are distinct. An explicit formula for the inverse is known.<ref>{{Cite book
+=== 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
+:<math>W=\begin{bmatrix}
+ w_{1,1}& w_{1,2} & w_{1,3} & \dots & w_{1,n}\\
+& w_{2,2} & w_{2,3} & \dots & w_{2,n}\\
+& 0 & w_{3,3} & \dots & w_{3,n}\\
+\vdots & \vdots & \vdots & \ddots &\vdots \\
+& 0 & 0 & \dots & w_{n,n}
+\end{bmatrix},</math>
+which has the same determinant as {{mvar|V}}.
+A [[proof by induction]] on the steps of Gaussian elimination allows showing that, for {{math|1 ≤ ''i'' ≤ ''j'' ≤ ''n''}}, one has
+:<math>w_{i,j}=M_{j-i}(\mathbf x_{i-1}, x_i)\prod_{k=1}^{i-1}(x_i-x_k),</math>
+where <math>\mathbf x_{i-1}</math> is an abbreviation for <math>x_1,\ldots, x_{i-1}</math>, and <math>M_{d}(\mathbf x_{i-1}, x_i)</math> is the sum of all [[monomial]]s of degree {{math|''d''}} in <math>\mathbf x_{i-1}, x_i.</math> In particular, the first rows of {{mvar|V}} and {{mvar|W}} are equal, and the factor <math>M_{j-i}(\mathbf x_{i-1}, x_i)</math> 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 {{math|''k'' > ''i''}}
+:<math>M_{d}(\mathbf x_{i-1}, x_h)-M_{d}(\mathbf x_{i-1}, x_i)=(x_h-x_i)M_{d-1}(\mathbf x_{i-1}, x_i,x_h)</math>
+For the recursion, one has to describe the matrix at each step of the Gaussian elimination. Let <math>a_{i,j}</math> be the entry of the {{mvar|i}}th row and {{mvar|j}}th column of this variable matrix. Before the {{mvar|i}}th step, the entries that belong either to the {{math|''i''}} first rows or the {{math|''i'' – 1}} first columns have the values that they will have at the end of Gaussian elimination, and, for {{math|''i'' ≤ ''j'' ≤ ''n''}} and {{math|''i'' ≤ ''h'' ≤ ''n''}}, one has
+:<math>a_{h,j}=M_{j-i}(\mathbf x_{i-1}, x_h)\prod_{k=1}^{i-1}(x_h-x_k).</math>
+This is true before the first step, and one has to prove that this remains true during Gaussian elimination.
+The {{mvar|i}}th step does not change the {{mvar|i}} first rows nor the {{math|''i'' – 1}} first columns. It changes <math>a_{h,i}</math> to zero for {{math|1=''i'' < ''h'' ≤ ''n''}}. For {{math|''i'' < ''j'' ≤ ''n''}} and {{math|''i'' < ''h'' ≤ ''n''}}, it changes <math>a_{h,j}</math> into <math>a_{h,j}-a_{i,j}a_{h,i}/a_{i,i}.</math> That is, the new <math>a_{h,j}</math> is
+:<math>\begin{align}
+a_{h,j}&=M_{j-i}(\mathbf x_{i-1}, x_h)\prod_{k=1}^{i-1}(x_h-x_k)-
+\frac{M_{0}(\mathbf x_{i-1}, x_h)\prod_{k=1}^{i-1}(x_h-x_k)}
+{M_{0}(\mathbf x_{i-1}, x_i)\prod_{k=1}^{i-1}(x_i-x_k)}
+M_{j-i}(\mathbf x_{i-1}, x_i)\prod_{k=1}^{i-1}(x_i-x_k)\\
+&=\left(M_{j-i}(\mathbf x_{i-1}, x_h)-M_{j-i}(\mathbf x_{i-1}, x_i)\right)\prod_{k=1}^{i-1}(x_h-x_k)\\
+&=M_{j-(i+1)}(\mathbf x_{i-1}, x_i,x_h)\prod_{k=1}^{i}(x_h-x_k).
+\end{align}</math>
+This shows that the structure of the <math>a_{h,j}</math> is kept during Gaussian elimination, and thus the form of {{mvar|W}}.
+It follows from the structure of {{mvar|W}} that <math>\det(V)=\det(W)</math> is the product of the diagonal entries of {{mvar|W}}, which proves again the formula for the determinant of a Vandermonde matrix.
+===Resulting properties===
+A {{math|''m'' × ''n''}} rectangular Vandermonde matrix such that {{math|''m'' ≤ ''n''}} has maximum [[rank of a matrix|rank]] {{math|''m''}} [[if and only if]] all {{math|''x''<sub>''i''</sub>}} are distinct.
+A {{math|''m'' × ''n''}} rectangular Vandermonde matrix such that {{math|''m'' ≥ ''n''}} has maximum [[rank of a matrix|rank]] {{math|''n''}} if and only if there are {{mvar|n}} of the {{math|''x''<sub>''i''</sub>}} that are distinct.
+A square Vandermonde matrix is [[invertible matrix|invertible]] if and only if the {{math|''x''<sub>''i''</sub>}} are distinct. An explicit formula for the inverse is known.<ref>{{Cite book
 | title = Inverse of the Vandermonde matrix with applications
 | last = Turner
@@ Line 54: / Line 126: @@
 | doi = 10.2307/2308881
 | publisher = The American Mathematical Monthly, Vol. 65, No. 2
-}}</ref><ref>[https://proofwiki.org/wiki/Inverse_of_Vandermonde%27s_Matrix Inverse of Vandermonde Matrix (ProofWiki)]</ref>
+}}</ref><ref>[https://proofwiki.org/wiki/Inverse_of_Vandermonde_Matrix Inverse of Vandermonde Matrix (ProofWiki)]</ref>
 ==Applications==
-The Vandermonde matrix ''evaluates'' a polynomial at a set of points; formally, it transforms ''coefficients'' of a polynomial <math>a_0+a_1x+a_2x^2+\cdots+a_{n-1}x^{n-1}</math> to the ''values'' the polynomial takes at the points <math>\alpha_i.</math> The non-vanishing of the Vandermonde determinant for distinct points <math>\alpha_i</math> 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 unique solution; this result is called the ''[[unisolvence theorem]].''
+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 <math>\alpha_i</math> 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 <math>\alpha_i</math> and the values of the polynomial at the <math>\alpha_i.</math> However, the interpolation polynomial is generally easier to compute with the [[Lagrange polynomials|Lagrange interpolation formula]].<ref>{{Cite book |last1=Press|first1=WH|last2=Teukolsky|first2=SA|last3=Vetterling|first3=WT|last4=Flannery|first4=BP|year=2007|title=Numerical Recipes: The Art of Scientific Computing|edition=3rd|publisher=Cambridge University Press| publication-place=New York|isbn=978-0-521-88068-8|chapter=Section 2.8.1. Vandermonde Matrices|chapter-url=http://apps.nrbook.com/empanel/index.html?pg=94 |postscript={{inconsistent citations}}}}</ref>
-They are thus useful in [[polynomial interpolation]], since solving the [[system of linear equations]] ''Vu''&nbsp;=&nbsp;''y'' for ''u'' with ''V'' an ''m''&nbsp;×&nbsp;''n'' Vandermonde matrix is equivalent to finding the [[coefficient]]s ''u''<sub>''j''</sub> of the polynomial(s)
+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>
-:<math> P(x)=\sum_{j=0}^{n-1} u_j x^j </math>
+When the values <math>\alpha_k</math> belong to a [[finite field]], then the Vadermonde determinant is also called
-of degree ≤&nbsp;''n''&nbsp;−&nbsp;1 which has (have) the property
+[[Moore matrix|Moore determinant]], and has specific properties that are used, for example for 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 α<sub>''i''</sub> are chosen to be [[roots of unity]].
-:<math> P(\alpha_i) = y_i \quad\text{for } i=1,\ldots, m. \, </math>
+==Confluent Vandermonde matrices==
-The Vandermonde matrix can be inverted in terms of [[Lagrange polynomials|Lagrange basis polynomials]]:<ref>{{Cite book |last1=Press|first1=WH|last2=Teukolsky|first2=SA|last3=Vetterling|first3=WT|last4=Flannery|first4=BP|year=2007|title=Numerical Recipes: The Art of Scientific Computing|edition=3rd|publisher=Cambridge University Press| publication-place=New York|isbn=978-0-521-88068-8|chapter=Section 2.8.1. Vandermonde Matrices|chapter-url=http://apps.nrbook.com/empanel/index.html?pg=94 |postscript=<!-- Bot inserted parameter. Either remove it; or change its value to "." for the cite to end in a ".", as necessary. -->{{inconsistent citations}}}}</ref> each ''column'' is the coefficients of the Lagrange basis polynomial, with terms in increasing order going down. The resulting solution to the interpolation problem is called the [[Lagrange polynomial]].
+{{confusing section|date=April 2018}}
+When two or more α<sub>''i''</sub> are equal, the corresponding [[polynomial interpolation]] problem (see below) is <!-- [[Well-posed problem|ill-posed]] --> [[underdetermined system|underdetermined]].  In that case one may use a generalization called '''confluent Vandermonde matrices''', which makes the matrix <!-- [[positive-definite matrix|positive definite]] --> [[Invertible matrix|non-singular]] while retaining most properties. If α<sub>''i''</sub>&nbsp;=&nbsp;α<sub>''i''&nbsp;+&nbsp;1</sub>&nbsp;=&nbsp;...&nbsp;=&nbsp;α<sub>''i''+''k''</sub> and α<sub>''i''</sub>&nbsp;≠&nbsp;α<sub>''i''&nbsp;−&nbsp;1</sub>, then the (''i''&nbsp;+&nbsp;''k'')th row is given by
+:<math> V_{i+k,j} = \begin{cases} 0, & \text{if } j \le k; \\ \frac{(j-1)!}{(j-k-1)!} \alpha_i^{j-k-1}, & \text{if } j > k. \end{cases} </math>
-The Vandermonde determinant plays a central role in the [[Induced representation|Frobenius formula]], which gives the [[character theory|character]] of [[conjugacy class]]es of [[representation theory of the symmetric group|representation]]s of the [[symmetric group]].<ref>{{Fulton-Harris}} ''Lecture 4 reviews the representation theory of symmetric groups, including the role of the Vandermonde determinant''.</ref>
+The above formula for confluent Vandermonde matrices can be readily derived by letting two parameters <math>\alpha_i</math> and <math>\alpha_j</math> go arbitrarily close to each other. The difference vector between the rows corresponding to <math>\alpha_i</math> and <math>\alpha_j</math> scaled to a constant yields the above equation (for ''k''&nbsp;=&nbsp;1). Similarly, the cases ''k''&nbsp;>&nbsp;1 are obtained by higher order differences. Consequently, the confluent rows are derivatives of the original Vandermonde row.
-When the values <math>\alpha_k</math> range over powers of a [[finite field]], then the determinant
-<!-- is more commonly known as the [[Moore determinant]], which -->
-has a number of interesting properties: for example, in proving the properties of a [[BCH code]].
-Confluent Vandermonde matrices are used in [[Hermite interpolation]].
-A commonly known special Vandermonde matrix is the [[discrete Fourier transform]] matrix ([[DFT matrix]]), where the numbers α<sub>''i''</sub> are chosen to be the ''m'' different ''m''th [[root of unity|roots of unity]].
-The Vandermonde matrix diagonalizes the [[companion matrix]].
-The Vandermonde matrix is used in some forms of [[Reed–Solomon error correction]] codes.
 ==See also==

v t e Numerical linear algebra
Key concepts	Floating point Numerical stability
Problems	System of linear equations Matrix decompositions Matrix multiplication (algorithms) Matrix splitting Sparse problems
Hardware	CPU cache TLB Cache-oblivious algorithm SIMD Multiprocessing
Software	ATLAS MATLAB Basic Linear Algebra Subprograms (BLAS) LAPACK Specialized libraries General purpose software