# 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), ... ?

21. Dec 11, 2008

### jostpuur

I'm not sure I want to try to complete that calculation now, because the other proof is almost complete.

The way I first thought about it was probably not fully right, because I had ignored the problem I mentioned in the post #19. It could be, however, that this problem can be solved by examining later steps in the proof more carefully.

22. Dec 11, 2008

### jostpuur

hmhmh... I think I made it too difficult now.

Here, I might as well have said that the determinant is zero at least when $x_i=x_j$ for some $i\neq j$, and the proof would have worked the same way.

23. Dec 12, 2008

### Anthony

Exactly. The point is that you know the determinant is a polynomial of degree X say, and you can easily read off X roots, so you are done, modulo a constant.

24. Dec 12, 2008

### jostpuur

Argh! Argh! This has been sleight of hand!

It follows with simple arguments that

$$\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| =\Big(\underset{k<l}{\prod_{k,l=1}^n} (x_k - x_l)\Big) p(x_1,\ldots, x_n)$$

with some polynomial $p$, and then, again with simple arguments it follows that $p$ must be a constant (a polynomial of degree zero).

Before we can set $C=\frac{1}{p}$, it must be shown that $p\neq 0$. In order to show that $p\neq 0$, it must be shown that the determinant is zero only if $x_i=x_j$ with some $i\neq j$. This means that we must show that if 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$.

25. Dec 12, 2008

### jostpuur

hmhm.. no, I merely got confused with one little earlier mistake. I should have originally said that there exists a constant $C_n$ such that

$$C_n\underset{k<l}{\prod_{k,l=1}^n} (x_k-x_l) = \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|$$

Now there is no need to start worrying about possibility $C_n=0$, because the recursion formula

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

can be proven in exactly the same way as earlier, and then $C_n\neq 0$ follows.

pfuuf... could it be that it is now done....