Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Difficult polynomial and determinant formula

  1. Nov 18, 2008 #1
    Anyone having any ideas about how this formula could be proved?

    [tex]
    \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|
    [/tex]

    I tried induction without success. The induction step seems to only require other difficult formulas.
     
  2. jcsd
  3. Nov 19, 2008 #2

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    Look up the Vandermonde determinant.
     
  4. Dec 10, 2008 #3
    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:
     
  5. Dec 10, 2008 #4
    What can you say about the ith and jth columns if [tex]x_i=x_j[/tex]? Can you see how to construct a proof from there?
     
  6. Dec 10, 2008 #5
    I can see that in the equation I wrote, both sides are zero precisely when [itex]x_i=x_j[/itex] for some [itex]i\neq j[/itex], but I don't see how this remark would help with a proof yet.
     
  7. Dec 10, 2008 #6
    Do you agree that the determinant is a polynomial in the variables [tex]x_i[/tex]?
     
  8. Dec 10, 2008 #7
  9. Dec 11, 2008 #8
    What order will the polynomial be in each of the [tex]x_i[/tex]?
     
  10. Dec 11, 2008 #9
  11. Dec 11, 2008 #10

    epenguin

    User Avatar
    Homework Helper
    Gold Member

    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.
     
  12. Dec 11, 2008 #11
    This seems to imply that there exists some constant [itex]C\in\mathbb{R}[/itex] so that

    [tex]
    \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|
    [/tex]

    I'll continue thinking.
     
  13. Dec 11, 2008 #12
    By using the formula

    [tex]
    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})
    [/tex]

    I managed to do this:

    [tex]
    \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
    [/tex]
    [tex]
    \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|
    [/tex]

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

    [tex]
    0 - 0 = 0
    [/tex]

    [tex]
    1 - 1 = 0
    [/tex]

    [tex]
    (x_3+x_1) - (x_2+x_1) = x_3 - x_2
    [/tex]

    but what about the rows below these? It becomes an algebraic mess. :confused:
     
  14. Dec 11, 2008 #13
    Hurrah! So all you need do is find the constant [tex]C[/tex]. Can you do that?
     
  15. Dec 11, 2008 #14
    The fourth row will be

    [tex]
    (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).
    [/tex]

    This looks good, and most obviously [itex]x_3-x_2[/itex] 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.
     
  16. Dec 11, 2008 #15
    Maybe. I'll try induction with choice [itex]x_n=0[/itex], and see what happens.
     
  17. Dec 11, 2008 #16
    Yes, it seems that a recursion formula

    [tex]
    C_n = (-1)^{n+1} C_{n-1}
    [/tex]

    holds, and by checking the case [itex]n=2[/itex] first, the constants

    [tex]
    C_n = (-1)^{n(n-1)/2}
    [/tex]

    follow.

    Good job Anthony :wink:
     
  18. Dec 11, 2008 #17
    Glad to be of service.
     
  19. Dec 11, 2008 #18
    I must admit I suspected that you had underestimated the problem at the time of your first post. You made it sound too simple. :wink:
     
  20. Dec 11, 2008 #19
    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

    [tex]
    \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)
    [/tex]

    are linearly dependent, then [itex]x_i=x_j[/itex] with some [itex]i\neq j[/itex]?
     
  21. Dec 11, 2008 #20

    epenguin

    User Avatar
    Homework Helper
    Gold Member



    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), ... ?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?