Value of Vandermonde Determinant/Formulation 1/Proof 1

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $V_n$ be the Vandermonde determinant of order $n$ defined as the following formulation:

$V_n = \begin {vmatrix} 1 & x_1 & {x_1}^2 & \cdots & {x_1}^{n - 2} & {x_1}^{n - 1} \\ 1 & x_2 & {x_2}^2 & \cdots & {x_2}^{n - 2} & {x_2}^{n - 1} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 1 & x_n & {x_n}^2 & \cdots & {x_n}^{n - 2} & {x_n}^{n - 1} \end {vmatrix}$


Its value is given by:

$\ds V_n = \prod_{1 \mathop \le i \mathop < j \mathop \le n} \paren {x_j - x_i}$


Proof

Let $V_n = \begin{vmatrix} 1 & x_1 & {x_1}^2 & \cdots & {x_1}^{n - 2} & {x_1}^{n - 1} \\ 1 & x_2 & {x_2}^2 & \cdots & {x_2}^{n - 2} & {x_2}^{n - 1} \\ 1 & x_3 & {x_3}^2 & \cdots & {x_3}^{n - 2} & {x_3}^{n - 1} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 1 & x_{n - 1} & {x_{n - 1} }^2 & \cdots & {x_{n - 1} }^{n - 2} & {x_{n - 1} }^{n - 1} \\ 1 & x_n & {x_n}^2 & \cdots & {x_n}^{n - 2} & {x_n}^{n - 1} \end{vmatrix}$.


By Multiple of Row Added to Row of Determinant, we can subtract row 1 from each of the other rows and leave $V_n$ unchanged:

$V_n = \begin{vmatrix} 1 & x_1 & {x_1}^2 & \cdots & {x_1}^{n - 2} & {x_1}^{n - 1} \\ 0 & x_2 - x_1 & {x_2}^2 - {x_1}^2 & \cdots & {x_2}^{n - 2} - {x_1}^{n - 2} & {x_2}^{n - 1} - {x_1}^{n - 1} \\ 0 & x_3 - x_1 & {x_3}^2 - {x_1}^2 & \cdots & {x_3}^{n - 2} - {x_1}^{n - 2} & {x_3}^{n - 1} - {x_1}^{n - 1} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & x_{n-1} - x_1 & {x_{n - 1} }^2 - {x_1}^2 & \cdots & {x_{n - 1} }^{n - 2} - {x_1}^{n - 2} & {x_{n - 1} }^{n - 1} - {x_1}^{n - 1} \\ 0 & x_n - x_1 & {x_n}^2 - {x_1}^2 & \cdots & {x_n}^{n - 2} - {x_1}^{n - 2} & {x_n}^{n - 1} - {x_1}^{n - 1} \end{vmatrix}$


Similarly without changing the value of $V_n$, we can subtract, in order:

$x_1$ times column $n - 1$ from column $n$
$x_1$ times column $n - 2$ from column $n - 1$

and so on, till we subtract:

$x_1$ times column $1$ from column $2$.

The first row will vanish all apart from the first element $a_{11} = 1$.

On all the other rows, we get, with new $i$ and $j$:

$a_{i j} = \paren {x_i^{j - 1} - x_1^{j - 1} } - \paren {x_1 x_i^{j - 2} - x_1^{j - 1} } = \paren {x_i - x_1} x_i^{j - 2}$:
$V_n = \begin {vmatrix} 1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & x_2 - x_1 & \paren {x_2 - x_1} x_2 & \cdots & \paren {x_2 - x_1} {x_2}^{n - 3} & \paren {x_2 - x_1} {x_2}^{n - 2} \\ 0 & x_3 - x_1 & \paren {x_3 - x_1} x_3 & \cdots & \paren {x_3 - x_1} {x_3}^{n - 3} & \paren {x_3 - x_1} {x_3}^{n - 2} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & x_{n - 1} - x_1 & \paren {x_{n - 1} - x_1} x_{n - 1} & \cdots & \paren {x_{n - 1} - x_1} {x_{n - 1} }^{n - 3} & \paren {x_{n - 1} - x_1} {x_{n - 1} }^{n - 2} \\ 0 & x_n - x_1 & \paren {x_n - x_1} x_n & \cdots & \paren {x_n - x_1} {x_n}^{n - 3} & \paren {x_n - x_1} {x_n}^{n - 2} \end {vmatrix}$


For all rows apart from the first, the $k$th row has the constant factor $\paren {x_k - x_1}$.

So we can extract all these as factors, and from Determinant with Row Multiplied by Constant, we get:

$\ds V_n = \prod_{k \mathop = 2}^n \paren {x_k - x_1} \begin {vmatrix} 1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & 1 & x_2 & \cdots & {x_2}^{n - 3} & {x_2}^{n - 2} \\ 0 & 1 & x_3 & \cdots & {x_3}^{n - 3} & {x_3}^{n - 2} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 1 & x_{n - 1} & \cdots & {x_{n - 1} }^{n - 3} & {x_{n - 1} }^{n - 2} \\ 0 & 1 & x_n & \cdots & {x_n}^{n - 3} & {x_n}^{n - 2} \end {vmatrix}$


From Determinant with Unit Element in Otherwise Zero Row, we can see that this directly gives us:

$\ds V_n = \prod_{k \mathop = 2}^n \paren {x_k - x_1} \begin {vmatrix} 1 & x_2 & \cdots & {x_2}^{n - 3} & {x_2}^{n - 2} \\ 1 & x_3 & \cdots & {x_3}^{n - 3} & {x_3}^{n - 2} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 1 & x_{n - 1} & \cdots & {x_{n - 1} }^{n - 3} & {x_{n - 1} }^{n - 2} \\ 1 & x_n & \cdots & {x_n}^{n - 3} & {x_n}^{n - 2} \end{vmatrix}$

and it can be seen that:

$\ds V_n = \prod_{k \mathop = 2}^n \paren {x_k - x_1} V_{n - 1}$


$V_2$, by the time we get to it (it will concern elements $x_{n - 1}$ and $x_n$), can be calculated directly using the formula for calculating a Determinant of Order 2:

$V_2 = \begin {vmatrix} 1 & x_{n - 1} \\ 1 & x_n \end {vmatrix} = x_n - x_{n - 1}$


The result follows.

$\blacksquare$


Sources