# Induction for Vandermonde Matrix

Given real numbers $x_1<x_2<\cdots<x_n$, define the Vandermonde matrix by $V=(V_{ij}) = (x^j_i)$. That is, $$V = \left(\begin{array}{cccccc} 1 & x_1 & x^2_1 & \cdots & x^{n-1}_1 & x^n_1 \\ 1 & x_2 & x^2_2 & \cdots & x^{n-1}_2 & x^n_2 \\ \vdots & \vdots & \vdots & & \vdots & \vdots \\ 1 & x_{n-1}& x^2_{n-1} & \cdots & x^{n-1}_{n-1} & x^n_{n-1} \\ 1 & x_n & x^2_n & \cdots & x^{n-1}_n & x^n_n \end{array}\right).$$ Prove that $\det(V) = \prod_{1\le i<j\le n} (x_j-x_i)$ by the following inductive steps. Recall first that adding a multiple of one row to another will not change the determinant of a matrix. This is also true if you add a multiple of one column to another. Finally remember that the determinant is linear in each row when you leave the other ones fixed.

a. Subtract $x_1$ times each column from the column to its right, starting with the last column. That is, subtract $x_1$ times the $(n-1)$-st column from the $n$-th column, $x_1$ times the $(n-2)$-nd column from the $(n-1)$-st column, etc.

b. Then subtract the first row from all of the other rows.

c. Finally observe that each row has a common factor that can be pulled out of the determinant.

d. After these three steps are done, expand the resulting determinant in cofactors across the first row.

e. You should see at this point how to apply the induction step.

What I have so far: I have been told that for the induction step I have to first first show that it is true for an $(n-1)$$\times$$(n-1)$ matrix and then show that it is true for an $n$$\times$$n$ matrix (I believe?). I kind of think that my resulting matrix after the steps is incorrect...

Add the last row multiplied by -1 to all other rows, and we get,

det$|V|$=det$\left|\begin{array}{} 0 & x_1-x_n & x_1^2-x_n^2 & \cdots & x_1^n-x_n^n \\ 0 & x_2-x_n & x_2^2-x_n^2 & \cdots & x_2^n-x_n^n \\ \vdots & \vdots & \vdots & & \vdots \\ 0 & x_{n-1}-x_n & x_{n-1}^2-x_n^2 & \cdots & x_{n-1}^n-x_n^n \\ 1 & x_n & x_n^2 & \cdots & x_n^n \\ \end{array} \right|$

=det$\left|\begin{array}{} x_1-x_n & x_1^2-x_n^2 & \cdots & x_1^n-x_n^n \\ x_2-x_n & x_2^2-x_n^2 & \cdots & x_2^n-x_n^n \\ \vdots & \vdots & & \vdots \\ x_{n-1}-x_n & x_{n-1}^2-x_n^2 & \cdots & x_{n-1}^n-x_n^n \\ \end{array} \right|$

=$\prod\limits_{k=1}^{n-1}(x_k-x_n)$ det$\left|\begin{array}{} 1 & x_1+x_n & x_1^2+x_1x_n+x_n^2 & \cdots & \sum \limits_{k=0}^{n-1}x_1^{n-k-1}x_n^{k} \\ 1 & x_2+x_n & x_2^2+x_2x_n+x_n^2 & \cdots & \sum \limits_{k=0}^{n-1}x_2^{n-k-1}x_n^{k} \\ \vdots & \vdots & \vdots & & \vdots \\ 1 & x_{n-1}+x_n & x_{n-1}^2+x_{n-1}x_n+x_n^2 & \cdots & \sum \limits_{k=0}^{n-1}x_{n-1}^{n-k-1}x_n^{k} \\ \end{array} \right|$

=$\prod\limits_{k=1}^{n-1}(x_k-x_n)$ det$|V_1|$

In $V_1$, first add 1st column multiplied by $-x_n$ to 2nd column, and add 1st column multiplied by $-x_n^2$ to 3nd column, ..., and add 1st column multiplied by $-x_n^{n-1}$ to $(n-1)$'s column, we get

det$|V_1|$ = det$\left|\begin{array}{} 1 & x_1 & x_1^2+x_1x_n & \cdots & \sum \limits_{k=0}^{n-2}x_1^{n-k-1}x_n^{k} \\ 1 & x_2 & x_2^2+x_2x_n & \cdots & \sum \limits_{k=0}^{n-2}x_2^{n-k-1}x_n^{k} \\ \vdots & \vdots & \vdots & & \vdots \\ 1 & x_{n-1} & x_{n-1}^2+x_{n-1}x_n & \cdots & \sum \limits_{k=0}^{n-2}x_{n-1}^{n-k-1}x_n^{k} \\ \end{array} \right|$

Then add 2nd column multiplied by $-x_n$ to 3rd column, ..., and add 2nd column multiplied by $-x_n^{n-2}$ to $(n-1)$'s column, we get

det$|V_1|$ = det$\left|\begin{array}{} 1 & x_1 & x_1^2 & \cdots & \sum \limits_{k=0}^{n-3}x_1^{n-k-1}x_n^{k} \\ 1 & x_2 & x_2^2 & \cdots & \sum \limits_{k=0}^{n-3}x_2^{n-k-1}x_n^{k} \\ \vdots & \vdots & \vdots & & \vdots \\ 1 & x_{n-1} & x_{n-1}^2 & \cdots & \sum \limits_{k=0}^{n-3}x_{n-1}^{n-k-1}x_n^{k} \\ \end{array} \right|$

Repeat above process, and use induction hypothesis, we have

det$|V_1|$ = det$\left|\begin{array}{} 1 & x_1 & x_1^2 & \cdots & x_1^{n-1} \\ 1 & x_2 & x_2^2 & \cdots & x_2^{n-1} \\ \vdots & \vdots & \vdots & & \vdots \\ 1 & x_{n-1} & x_{n-1}^2 & \cdots & x_{n-1}^{n-1} \\ \end{array} \right|$ = $\prod_{1\le i<j\le n-1} (x_j-x_i)$

So finally

det$|V|$ =$\prod\limits_{k=1}^{n-1}(x_k-x_n)$ det$|V_1|$ = $\prod_{1\le i<j\le n} (x_j-x_i)$

• Sorry, I just saw this. And I marked it as an answer. Thank you! Apr 19 '15 at 20:29

File 1 - file i, i from 2 to n. Then use Laplace (cofactors, i dont know how it is said in english). Then use the principle of inclusión-exclusión.