A Vandermonde matrix of order n has the form
1 1 1 . . . 1
x1 x2 x3 . . . xn
x12 x22 x32 . . . xn2
. . . . . . .
. . . . . . .
. . . . . . .
x1n-1 x2n-1 x3n-1 . . . xnn-1
Although the transpose of this may be used as the definition; and it may also be referred to as an alternant matrix. Whilst solving an equation with an nXn Vandermonde matrix requires O(n2) operations, it turns out that the determinant is very easy to calculate, using the formula:
_____
| |
| | (xj-xi)
| |
1≤i<j≤n
For example, the matrix
1 1 1
x y z
x2 y2 z2
Or its transpose, has determinant (y-x)(z-x)(z-y). This could be proved by multiplying out this expression and checking that it gives the same result as a
row expansion of the above matrix, but a more
elegant solution (which also illustrates why the general nXn result holds) is to use
elementary column operations to obtain a
lower-triangular matrix, for which the determinant is simply the product of the
diagonal.
|1 1 1 | |1 0 0 |
|x y z | = |x y-x z-x |
|x2 y2 z2 | |x2 y2-x2 z2-x2 |
By subtracting column 1 from each of columns 2 and 3. Then
factorising the bottom row we get
|1 0 0 |
|x y-x z-x |
|x2 (y-x)(y+x) (z-x)(z+x) |
So we can pull out
factors of (y-x) and (z-x) by the
multilinearity of the
determinant function:
|1 0 0 |
(y-x)(z-x) |x 1 1 |
|x2 (y+x) (z+x) |
Now we perform a further
column operation, subtracting the second column from the third, which cancels the 1 and x:
|1 0 0 |
(y-x)(z-x) |x 1 0 |
|x2 (y+x) (z-y) |
Again pull a factor forward:
|1 0 0 |
(y-x)(z-x)(z-y) |x 1 0 |
|x2 (y+x) 1 |
Observe that this is a
triangular matrix, so its determinant is the product of the diagonal =1*1*1 =1. So we are left with simply the factors (y-x)(z-x)(z-y) as desired.