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


This page may be the result of a refactoring operation.
As such, the following source works, along with any process flow, will need to be reviewed.
When this has been completed, the citation of that source work (if it is appropriate that it stay on this page) is to be placed above this message, into the usual chronological ordering.
In particular: Technically this is the proof for Formulation 2, so needs to be moved to a proof on that page.
If you have access to any of these works, then you are invited to review this list, and make any necessary corrections.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{SourceReview}} from the code.


Retrieved from "https://proofwiki.org/w/index.php?title=Value_of_Vandermonde_Determinant/Formulation_1/Proof_1&oldid=726042"