Difficult polynomial and determinant formula

[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.

 

[morphism]

Look up the Vandermonde determinant.

 

[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.

 

[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?

 

[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.

 

[Anthony]

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

 

[jostpuur]

Yes.

 

[Anthony]

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

 

[jostpuur]

n-1.

 

[epenguin]

Subtract x₁ (or if you prefer x_n) 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 (x₂-x₁)(x₃-x₁)...(x_n-x₁) and the other factor is the next smallest Vandermonde determinant on x₂, x₃,... x_n. 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.

 

[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.

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

Yes.

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

n-1.

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.

 

[jostpuur]

Subtract x₁ (or if you prefer x_n) 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 (x₂-x₁)(x₃-x₁)...(x_n-x₁) and the other factor is the next smallest Vandermonde determinant on x₂, x₃,... x_n. 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.

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.

 

[Anthony]

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

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

 

[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.

 

[jostpuur]

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

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

 

[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

 

[Anthony]

Glad to be of service.

 

[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.

 

[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$?

 

[epenguin]

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.

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

 

[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.

 

[jostpuur]

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

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.

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.

 

[Anthony]

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.

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.

 

[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).

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.

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

 

[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...

 

[Anthony]

You're making a lot of work of this jostpuur! You know that both sides are the same modulo a constant of proportionality. And finding out the constant is easy. You were done many posts ago!

 

[epenguin]

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.

IMHO because you are doing it on the columns. Do it on the rows like I said. I cannot see that a (-1)^anything comes into it though, someone correct me if I am mistaken.