# Difficult polynomial and determinant formula

1. Nov 18, 2008

### jostpuur

Anyone having any ideas about how this formula could be proved?

$$\underset{k<l}{\prod_{k,l=1}^n} (x_k - x_l) = (-1)^{n(n-1)/2} \left|\begin{array}{ccc} 1 & \cdots & 1 \\ x_1 & \cdots & x_n \\ \vdots & & \vdots \\ x_1^{n-1} & \cdots & x_n^{n-1} \\ \end{array}\right|$$

I tried induction without success. The induction step seems to only require other difficult formulas.

2. Nov 19, 2008

### morphism

Look up the Vandermonde determinant.

3. Dec 10, 2008

### jostpuur

I have now seen this Vandermonde determinant been mentioned in several places, but I've still not encountered the proof. It seems that most authors prefer mentioning the result instead of proving it.

4. Dec 10, 2008

### Anthony

What can you say about the ith and jth columns if $$x_i=x_j$$? Can you see how to construct a proof from there?

5. Dec 10, 2008

### jostpuur

I can see that in the equation I wrote, both sides are zero precisely when $x_i=x_j$ for some $i\neq j$, but I don't see how this remark would help with a proof yet.

6. Dec 10, 2008

### Anthony

Do you agree that the determinant is a polynomial in the variables $$x_i$$?

7. Dec 10, 2008

### jostpuur

Yes.

8. Dec 11, 2008

### Anthony

What order will the polynomial be in each of the $$x_i$$?

9. Dec 11, 2008

### jostpuur

n-1.

10. Dec 11, 2008

### epenguin

Subtract x1 (or if you prefer xn) times each row from the next row. You'll then find you get a factor in each column which you can take out and is (x2-x1)(x3-x1)...(xn-x1) and the other factor is the next smallest Vandermonde determinant on x2, x3,... xn. You can also formulate the above as matrix multiplication.

The fiddly may be is getting the expression for sign right. Actually I am not sure you have.

11. Dec 11, 2008

### jostpuur

This seems to imply that there exists some constant $C\in\mathbb{R}$ so that

$$\underset{k<l}{\prod_{k,l=1}^n} (x_k-x_l) = C \left|\begin{array}{ccc} 1 & \cdots & 1 \\ x_1 & \cdots & x_n \\ \vdots & & \vdots \\ x_1^{n-1} & \cdots & x_n^{n-1} \\ \end{array}\right|$$

I'll continue thinking.

12. Dec 11, 2008

### jostpuur

By using the formula

$$x_k^m - x_l^m = (x_k - x_l)(x_k^{m-1} + x_k^{m-2}x_l + \cdots + x_k x_l^{m-2} + x_l^{m-1})$$

I managed to do this:

$$\left|\begin{array}{ccc} 1 & \cdots & 1 \\ x_1 & \cdots & x_n \\ \vdots & & \vdots \\ x_1^{n-1} & \cdots & x_n^{n-1} \\ \end{array}\right| = (x_2 - x_1)\left|\begin{array}{ccccc} 1 & 0 & 1 & \cdots & 1 \\ x_1 & 1 & x_3 & \cdots & x_n \\ x_1^2 & x_2+x_1 & x_3^2 & \cdots & x_n^2 \\ \vdots & \vdots & \vdots & & \vdots \\ x_1^{n-1} & x_2^{n-2} + x_2^{n-3}x_1 + \cdots + x_1^{n-2} & x_3^{n-1} & \cdots & x_n^{n-1} \\ \end{array}\right| = \cdots$$
$$\cdots = (-1)^{n-2}\Big(\prod_{k=2}^n (x_1 - x_k)\Big)\left|\begin{array}{cccc} 1 & 0 & \cdots & 0 \\ x_1 & 1 & \cdots & 1 \\ x_1^2 & x_2 + x_1 & \cdots & x_n + x_1 \\ \vdots & \vdots & & \vdots \\ x_1^{n-1} & x_2^{n-2} + \cdots + x_1^{n-2} & \cdots & x_n^{n-2} + \cdots + x_1^{n-2} \\ \end{array}\right|$$

It looks like difficult to proceed. If I subtract the second column from the third column, the three first rows will become this

$$0 - 0 = 0$$

$$1 - 1 = 0$$

$$(x_3+x_1) - (x_2+x_1) = x_3 - x_2$$

but what about the rows below these? It becomes an algebraic mess.

13. Dec 11, 2008

### Anthony

Hurrah! So all you need do is find the constant $$C$$. Can you do that?

14. Dec 11, 2008

### jostpuur

The fourth row will be

$$(x_3^2 + x_3x_1 + x_1^2) - (x_2^2 + x_2x_1 + x_1^2) = (x_3-x_2)(x_3 + x_2 + x_1).$$

This looks good, and most obviously $x_3-x_2$ will become a common factor, but it is a mystery to me how one proves this. When one proceeds like this, the algebraic expressions at some arbitrary step seem to be complicated.

15. Dec 11, 2008

### jostpuur

Maybe. I'll try induction with choice $x_n=0$, and see what happens.

16. Dec 11, 2008

### jostpuur

Yes, it seems that a recursion formula

$$C_n = (-1)^{n+1} C_{n-1}$$

holds, and by checking the case $n=2$ first, the constants

$$C_n = (-1)^{n(n-1)/2}$$

follow.

Good job Anthony

17. Dec 11, 2008

### Anthony

18. Dec 11, 2008

### jostpuur

I must admit I suspected that you had underestimated the problem at the time of your first post. You made it sound too simple.

19. Dec 11, 2008

### jostpuur

Actually this is not all clear to me yet. There was one result that I considered trivial earlier, but which turned out to be more difficult. How does on prove that if the vectors

$$\left(\begin{array}{c} 1 \\ x_1 \\ \vdots \\ x_1^{n-1} \\ \end{array}\right), \left(\begin{array}{c} 1 \\ x_2 \\ \vdots \\ x_2^{n-1} \\ \end{array}\right),\cdots, \left(\begin{array}{c} 1 \\ x_n \\ \vdots \\ x_n^{n-1} \\ \end{array}\right)$$

are linearly dependent, then $x_i=x_j$ with some $i\neq j$?

20. Dec 11, 2008

### epenguin

I can't do tex determinants, but if you subtract x1 X (penultimate row) from last row,..., x1 X first row from second row, then don't you get for first column {1, 0, 0, ...}, for second column {1, (x2-x1), x2(x2-x1), x22(x2-x1), ... ?