Vandermonde matrix

Article on other languages:

del.icio.us del.icio.us
Digg Digg
Furl Furl
Reddit Reddit
Rojo Rojo
Add to OnlyWire

In linear algebra, a Vandermonde matrix, named after Alexandre-Théophile Vandermonde, is a matrix with the monomial 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. (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\le i<j\le n} (\alpha_j-\alpha_i).

The above determinant is sometimes called the discriminant, although many sources, including this article, refer to the discriminant as the square of this determinant.

Using the Leibniz formula

\det(V) = \sum_{\sigma \in S_n} \sgn(\sigma) \, \alpha_1^{\sigma(1)-1} \cdots \alpha_n^{\sigma(n)-1},

for the determinant, we can rewrite this formula as

\prod_{1\le i<j\le n} (\alpha_j-\alpha_i) = \sum_{\sigma \in S_n} \sgn(\sigma) \, \alpha_1^{\sigma(1)-1} \cdots \alpha_n^{\sigma(n)-1},

where Sn denotes the set of permutations of {1, 2, ..., n}, and sgn(σ) denotes the signature of the permutation σ.

If m≤n, then the matrix V has maximum rank (m) if and only if all αi are distinct.

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, & \mbox{if } j \le k; \\ \frac{(j-1)!}{(j-k-1)!} \alpha_i^{j-k-1}, & \mbox{if } j > k. \end{cases}

The above formula for confluent Vandermonde matrices can be readily derived by letting two parameters αi and αj go arbitrarily close to each other. The difference vector between the rows corresponding to αi and α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.

Applications

These matrices are useful in polynomial interpolation, since solving the system of linear equations Vu = y for u with V an n × n Vandermonde matrix is equivalent to finding the coefficients uj of the polynomial

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

of degree ≤ n−1 which has the values yi at αi.

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

When the values α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, where the numbers αi are chosen equal to the m different mth roots of unity.

The Vandermonde matrix diagonalizes a companion matrix.

See also

References

  • Roger A. Horn and Charles R. Johnson, Topics in matrix analysis, (1991) Cambridge University Press. See Section 6.1.
Retrieved from "http://en.wikipedia.org/wiki/Vandermonde_matrix"

This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License.

Giant Panda

Mercedes Car
James Bond Guide
This site monitored by SitePinger.net