Vandermonde matrix

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}},

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 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 $\alpha _{i}$ 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.

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 \le 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.

Properties

In the case of a square Vandermonde matrix, the Leibniz formula for the determinant gives

\det(V) = \sum_{\sigma \in S_n} \sgn(\sigma) \prod_{i = 1}^n \alpha_i^{\sigma(i)-1},

where S_n denotes the set of permutations of $\{1,\ldots,n\}$ , and $\sgn(\sigma)$ denotes the signature of the permutation σ. This determinant factors as

\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).

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.

If m ≤ n, then the matrix V has maximum rank (m) if and only if all α_i are distinct. A square Vandermonde matrix is thus invertible if and only if the α_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 transforms coefficients of a polynomial $a_0+a_1x+a_2x^2+\cdots+a_{n-1}x^{n-1}$ to the values the polynomial takes at the points $\alpha_i.$ 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 unique solution; this result is called the unisolvence theorem.

They are thus useful in polynomial interpolation, since solving the system of linear equations Vu = y for u with V an m × n Vandermonde matrix is equivalent to finding the coefficients u_j of the polynomial(s)

P(x)=\sum_{j=0}^{n-1} u_j x^j

of degree ≤ n − 1 which has (have) the property

P(\alpha_i) = y_i \quad\text{for } i=1,\ldots, m. \,

The Vandermonde matrix can be inverted in terms of Lagrange basis polynomials:^[5] 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.

The Vandermonde determinant plays a central role in the Frobenius formula, which gives the character of conjugacy classes of representations of the symmetric group.^[6]

When the values $\alpha _{k}$ range over powers of a finite field, then the determinant 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 α_i are chosen to be the m different mth roots of unity.

The Vandermonde matrix diagonalizes the companion matrix.

The Vandermonde matrix is used in some forms of Reed–Solomon error correction codes.

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. The American Mathematical Monthly, Vol. 65, No. 2. 65 (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
↑ Fulton, William; Harris, Joe (1991). Representation theory. A first course. Graduate Texts in Mathematics, Readings in Mathematics. 129. New York: Springer-Verlag. ISBN 978-0-387-97495-8. MR 1153249, ISBN 978-0-387-97527-6. Lecture 4 reviews the representation theory of symmetric groups, including the role of the Vandermonde determinant.

External links

Vandermonde Determinant at ProofWiki

Numerical linear algebra

Key concepts	Floating point Numerical stability

Problems	Matrix multiplication (algorithms) Matrix decompositions Linear equations Sparse problems

Hardware	CPU cache TLB Cache-oblivious algorithm SIMD Multiprocessing

Software	BLAS Specialized libraries General purpose software

This article is issued from Wikipedia - version of the 6/21/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Vandermonde matrix

Properties

Applications

See also

References

Further reading

External links