Value of Vandermonde Determinant/Formulation 1/Proof 2

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

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$


Sources

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