Value of Vandermonde Determinant/Formulation 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 1

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$


Proof 2

Proof by induction:

Let the Vandermonde determinant be presented in the following form:

$V_n = \begin {vmatrix}

{x_1}^{n - 1} & {x_1}^{n - 2} & \cdots & x_1 & 1 \\ {x_2}^{n - 1} & {x_2}^{n - 2} & \cdots & x_2 & 1 \\ 

      \vdots &        \vdots & \ddots & \vdots & \vdots \\

{x_n}^{n - 1} & {x_n}^{n - 2} & \cdots & x_n & 1 \\ \end {vmatrix}$


For all $n \in \N_{>0}$, let $\map P n$ be the proposition:

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


$\map P 1$ is true, as this just says $\begin {vmatrix} 1 \end {vmatrix} = 1$.


Basis for the Induction

$\map P 2$ holds, as it is the case:

$V_2 = \begin {vmatrix}
 a_1 & 1 \\
 a_2 & 1

\end {vmatrix}$ which evaluates to $V_2 = a_1 - a_2$.

This is our basis for the induction.


Induction Hypothesis

Now we need to show that, if $\map P k$ is true, where $k \ge 2$, then it logically follows that $\map P {k + 1}$ is true.


So this is our induction hypothesis:

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


Then we need to show:

$\ds V_{k + 1} = \prod_{1 \mathop \le i \mathop < j \mathop \le k + 1} \paren {x_i - x_j}$


Induction Step

This is our induction step:


Take the determinant:

$V'_{k + 1} = \begin{vmatrix}
           x^k &            x^{k - 1} & \cdots &            x^2 &         x & 1 \\
       {x_2}^k &        {x_2}^{k - 1} & \cdots &        {x_2}^2 &       x_2 & 1 \\
        \vdots &               \vdots & \ddots &         \vdots &    \vdots & \vdots \\
{x_{k + 1} }^k & {x_{k + 1} }^{k - 1} & \cdots & {x_{k + 1} }^2 & x_{k + 1} & 1

\end{vmatrix}$

where it is seen that $x_1$ has been replaced in $V_{k + 1}$ with $x$.

Let the Expansion Theorem for Determinants‎ be used to expand $V'_{k + 1}$ in terms of the first row.

It can be seen that it is a polynomial in $x$ whose degree is no greater than $k$.

Let that polynomial be denoted $\map f x$.

Let any $x_r$ be substituted for $x$ in the determinant.

Then two of its rows will be the same.

From Square Matrix with Duplicate Rows has Zero Determinant, the value of such a determinant will be $0$.

Such a substitution in the determinant is equivalent to substituting $x_r$ for $x$ in $\map f x$.

Thus it follows that:

$\map f {x_2} = \map f {x_3} = \cdots = \map f {x_{k + 1} } = 0$

So $\map f x$ is divisible by each of the factors $x - x_2, x - x_3, \ldots, x - x_{k + 1}$.

All these factors are distinct, otherwise the original determinant is zero.

So:

$\map f c = \map C {x - x_2} \paren {x - x_3} \cdots \paren {x - x_k} \paren {x - x_{k + 1} }$

As the degree of $\map f x$ is no greater than $k$, it follows that $C$ is independent of $x$.


From the Expansion Theorem for Determinants‎, the coefficient of $x^k$ is:

$\begin{vmatrix}
      {x_2}^{k - 1} & \cdots &        {x_2}^2 &       x_2 & 1 \\
             \vdots & \ddots &         \vdots &    \vdots & \vdots \\

{x_{k + 1} }^{k - 1} & \cdots & {x_{k + 1} }^2 & x_{k + 1} & 1 \end{vmatrix}$

By the induction hypothesis, this is equal to:

$\ds \prod_{2 \mathop \le i \mathop < j \mathop \le k + 1} \paren {x_i - x_j}$

This must be our value of $C$.

So we have:

$\ds \map f x = \paren {x - x_2} \paren {x - x_3} \dotsm \paren {x - x_k} \paren {x - x_{k + 1} } \prod_{2 \mathop \le i \mathop < j \mathop \le k + 1} \paren {x_i - x_j}$

Substituting $x_1$ for $x$, we retrieve the proposition $\map P {k + 1}$.


So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.


Therefore:

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

$\blacksquare$


Proof 3

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}$


Start by replacing number $x_n$ in $V_n$ with the unknown $x$.

Thus $V_n$ is made into a function of $x$.

$\map P x = \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 & x^2 & \cdots & x^{n - 2} & x^{n - 1}

\end{vmatrix}$.

Let $x$ equal a value from the set $\set {x_1,\ldots,x_{n-1} }$.

Then determinant $\map P x$ has equal rows, giving:

\(\ds \map P x\) \(=\) \(\ds 0\) for $x = x_1, \ldots, x_{n - 1}$

Perform row expansion by the last row.

Then $\map P x$ is seen to be a polynomial of degree $n-1$:

$\map P x = \begin {vmatrix}
 x_1 & {x_1}^2 & \cdots & {x_1}^{n - 2} & {x_1}^{n - 1} \\
 x_2 & {x_2}^2 & \cdots & {x_2}^{n - 2} & {x_2}^{n - 1} \\
 x_3 & {x_3}^2 & \cdots & {x_3}^{n - 2} & {x_3}^{n - 1} \\

\vdots & \vdots & \vdots & \ddots & \vdots \\ 

 x_{n - 1} & {x_{n - 1} }^2 & \cdots & {x_{n - 1} }^{n - 2} & {x_{n - 1} }^{n - 1}

\end{vmatrix} + \begin{vmatrix} 

 1 & {x_1}^2 & \cdots & {x_1}^{n - 2} & {x_1}^{n - 1} \\
 1 & {x_2}^2 & \cdots & {x_2}^{n - 2} & {x_2}^{n - 1} \\
 1 & {x_3}^2 & \cdots & {x_3}^{n - 2} & {x_3}^{n - 1} \\

\vdots & \vdots & \vdots & \ddots & \vdots \\ 

 1 & {x_{n - 1} }^2 & \cdots & {x_{n - 1} }^{n - 2} & {x_{n - 1} }^{n - 1}

\end {vmatrix} x + \cdots + \begin {vmatrix} 

 1 & x_1 & {x_1}^2 & \cdots & {x_1}^{n - 2} \\
 1 & x_2 & {x_2}^2 & \cdots & {x_2}^{n - 2} \\
 1 & x_3 & {x_3}^2 & \cdots & {x_3}^{n - 2} \\

\vdots & \vdots & \vdots & \ddots & \vdots \\ 

 1 & x_{n - 1} & {x_{n - 1} }^2 & \cdots & {x_{n - 1} }^{n - 2}

\end{vmatrix} x^{n - 1}$

By the Polynomial Factor Theorem:

$\map P x = \map C {x - x_1} \paren {x - x_2} \dotsm \paren {x - x_{n - 1} }$

where $C$ is the leading coefficient (with $x^{n - 1}$ power).


Thus:

$\map P x = V_{n - 1} \paren {x - x_1} \paren {x - x_2} \dotsm \paren {x - x_{n - 1} }$

which by evaluating at $x = x_n$ gives:

$V_n = V_{n - 1} \paren {x_n - x_1} \paren {x_n - x_2} \dotsm \paren {x_n - x_{n - 1} }$


Repeating the process:

\(\ds V_n\) \(=\) \(\ds \prod_{1 \mathop \le i \mathop < n} \paren {x_n - x_i} V_{n - 1}\)
\(\ds \) \(=\) \(\ds \prod_{1 \mathop \le i \mathop < n} \paren {x_n - x_i} \prod_{1 \mathop \le i \mathop < n - 1} \paren {x_{n - 1} - x_i} V_{n - 2}\)
\(\ds \) \(=\) \(\ds \dotsm\)
\(\ds \) \(=\) \(\ds \prod_{1 \mathop \le i \mathop < j \mathop \le n} \paren {x_j - x_i}\)


which establishes the solution.

$\blacksquare$


Proof 4

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} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 1 & x_n & {x_n}^2 & \cdots & {x_n}^{n - 2} & {x_n}^{n - 1} \end {vmatrix}$

Let $\map f x$ be any monic polynomial of degree $n - 1$:

$\ds \map f x = x^{n - 1} + \sum_{i \mathop = 0}^{n - 2} a_i x^i$

Apply elementary column operations to $V_n$ repeatedly to show:

$V_n = W$

where:

$ W = \begin {vmatrix}

1 & x_1 & {x_1}^2 & \cdots & {x_1}^{n - 2} & \map f {x_1} \\ 1 & x_2 & {x_2}^2 & \cdots & {x_2}^{n - 2} & \map f {x_2} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 1 & x_n & {x_n}^2 & \cdots & {x_n}^{n - 2} & \map f {x_n} \end {vmatrix}$

Select a specific degree $n - 1$ monic polynomial:

$\ds \map f x = \prod_{k \mathop = 1}^{n - 1} \paren {x - x_k}$

The selected polynomial is zero at all values $x_1, \ldots, x_{n - 1}$.

Then the last column of $W$ is all zeros except the entry $\map f {x_n}$.

Expand $\map \det W$ by cofactors along the last column to prove:

\(\text {(1)}: \quad\) \(\ds V_n\) \(=\) \(\ds \map f {x_n} V_{n - 1}\) Expansion Theorem for Determinants for columns
\(\ds \) \(=\) \(\ds V_{n - 1} \prod_{k \mathop = 1}^{n - 1} \paren {x_n - x_k}\)

For $n \ge 2$, let $\map P n$ be the statement:

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

Mathematical induction will be applied.


Basis for the Induction

By definition, determinant $V_1 = 1$.

To prove $\map P 2$ is true, use equation $(1)$ with $n = 2$:

$V_2 = \paren {x_2 - x_1} V_1$

This is the basis for the induction.


Induction Step

This is the induction step:

Let $\map P n$ is be assumed true.

We are to prove that $\map P {n + 1}$ is true.

As follows:

\(\ds V_{n + 1}\) \(=\) \(\ds V_n \prod_{k \mathop = 1}^n \paren {x_{n + 1} - x_k}\) from $(1)$, setting $n \to n + 1$
\(\ds \) \(=\) \(\ds \prod_{1 \mathop \le m \mathop < k \mathop \le n} \paren {x_k - x_m} \prod_{k \mathop = 1}^n \paren {x_{n + 1} - x_k}\) Induction hypothesis with new indexing symbols: $i \to m, j \to k$
\(\ds \) \(=\) \(\ds \prod_{1 \mathop \le i \mathop < j \mathop \le n + 1} \paren {x_j - x_i}\) simplifying

Thus $\map P {n + 1}$ has been shown to be true.

The induction is complete.

$\blacksquare$


Source of Name

This entry was named for Alexandre-Théophile Vandermonde.


Sources

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