Difficult polynomial and determinant formula

jostpuur · Nov 18, 2008

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 · Nov 19, 2008

Look up the Vandermonde determinant.

jostpuur · Dec 10, 2008

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. :devil:

Anthony · Dec 10, 2008

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 · Dec 10, 2008

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 · Dec 10, 2008

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

jostpuur · Dec 10, 2008

Anthony · Dec 11, 2008

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

jostpuur · Dec 11, 2008

epenguin · Dec 11, 2008

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 · Dec 11, 2008

jostpuur said:

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.

jostpuur said:

Anthony said:

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

Yes.

jostpuur said:

Anthony said:

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 · Dec 11, 2008

epenguin said:

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 · Dec 11, 2008

jostpuur said:

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 · Dec 11, 2008

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 · Dec 11, 2008

Anthony said:

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 · Dec 11, 2008

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 · Dec 11, 2008

Glad to be of service.

jostpuur · Dec 11, 2008

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 · Dec 11, 2008

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 · Dec 11, 2008

jostpuur said:

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 · Dec 11, 2008

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 · Dec 11, 2008

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

jostpuur said:

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 · Dec 12, 2008

jostpuur said:

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 · Dec 12, 2008

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

jostpuur said:

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 · Dec 12, 2008

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 · Dec 12, 2008

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 · Dec 12, 2008

jostpuur said:

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.

Difficult polynomial and determinant formula

Discussion Overview

Discussion Character

Main Points Raised

Areas of Agreement / Disagreement

Contextual Notes

Similar threads

Graduate Confusion about the Moyal-Weyl twist

Undergrad How to define a vector field?

Undergrad The vector to which a dual vector corresponds

Undergrad 2 interpretations of bra-ket expression: equal, & isomorphic, but...

Undergrad Erroneously finding discrepancy in transpose rule

Insights Remote Operated Gate Control System

Insights AI Enriched Problem Solving

Insights Thinking Outside The Box Versus Knowing What’s In The Box

Insights Why Entangled Photon-Polarization Qubits Violate Bell’s Inequality

Insights Quantum Entanglement is a Kinematic Fact, not a Dynamical Effect

Insights What Exactly is Dirac’s Delta Function? - Insight