Determinants, Vandermonde Matrix

Vandermonde Matrix

The matrix M is a Vandermonde matrix (biography) if M_i,j = M_i,0^j. Here is a simple example.

   1  1  1  1
   1  2  4  8
   1  3  9 27
   1  4 16 64

As you can see, the j^th column is the first column raised to the j power. Let x be the first column vector, so that M_i,j = x_i^j. In fact, let the elements of x be unknowns, variables that we will fill in later. Thus the determinant of M becomes a polynomial in n variables, x₀ through x_n-1.

Evaluate the Vandermonde determinant via det₂(M), the sum of permutation products. Consider the binomial x_l-x_k for any l > k. For every product with x_kⁱ×x_l^j there is another with x_k^j×x_lⁱ. These products come from permutations with opposite parity, so subtract them and find something divisible by x_l-x_k. This holds for every l > k.

Multivariable polynomials over the integers exhibit unique factorization (not proved here), so the unique factorization of the determinant includes x_l-x_k for each l > k. Furthermore, their product gives an expression of degree (n²-n)/2. Consider any permutation product in the determinant of M. It's degree is 0+1+2+…+n-1 = (n²-n)/2. The factors identified thus far create an expression that divides the determinant, and has the same degree, hence we can only be off by a constant.

run down the main diagonal and note that the product of x_iⁱ appears in the determinant with coefficient 1. Multiply the binomials together: (x₁-x₀) × (x₂-x₀) × (x₂-x₁) × (x₃-x₀) × …, and one of the resulting terms, taking the first variable from each binomial, gives the same expression, with a coefficient of 1. Therefore the determinant of M is the product of x_l-x_k, for 0 ≤ k < l < n.

In our example, the determinant is
(2-1)×(3-1)×(4-1)×(3-2)×(4-2)×(4-3) = 12.

As a corollary, any set of distinct Vandermonde vectors, drawn from any integral domain, is linearly independent. The determinant is the product of nonzero differences, and is nonzero.

Variations on the Theme

In the earlier 4×4 example, scale the second row by 2¹⁷. Now the row runs from 2¹⁷ to 2²⁰, yet the matrix remains nonsingular. Do this for every row, and the matrix starts at exponent 17 instead of exponent 0.

Let's use the matrix to evaluate the functions s_i^x*p(x), where s_i is the base for the i^th row, and p() is a fixed polynomial. To start, replace x with 0 through n-1, whence s_i^x gives a vandermonde matrix. If some of the integers from 0 to n-1 are roots of p, advance the exponents, as we did above. Make sure the exponents, from left to right, are not roots of p. This can always be done, since p has finitely many roots. Now, multiply the j^th column by p(x), where x is the exponent associated with the j^th column. Scaling a column keeps the matrix nonsingular. The exponential functions, represented by the rows, are multiplied by a particular polynomial, and the result is evaluated at n successive integers in the domain. Since the matrix remains nonsingular, the functions are linearly independent. Different exponentials, times a fixed polynomial, become linearly independent functions.