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), ... ?
     
  22. Dec 11, 2008 #21
    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.
     
  23. Dec 11, 2008 #22
    hmhmh... I think I made it too difficult now.

    Here, I might as well have said that the determinant is zero at least when [itex]x_i=x_j[/itex] for some [itex]i\neq j[/itex], and the proof would have worked the same way.
     
  24. Dec 12, 2008 #23
    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.
     
  25. Dec 12, 2008 #24
    Argh! Argh! This has been sleight of hand!

    It follows with simple arguments that

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

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

    Before we can set [itex]C=\frac{1}{p}[/itex], it must be shown that [itex]p\neq 0[/itex]. In order to show that [itex]p\neq 0[/itex], it must be shown that the determinant is zero only if [itex]x_i=x_j[/itex] with some [itex]i\neq j[/itex]. This means that we must show that if 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].
     
  26. Dec 12, 2008 #25
    hmhm.. no, I merely got confused with one little earlier mistake. I should have originally said that there exists a constant [itex]C_n[/itex] such that

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

    Now there is no need to start worrying about possibility [itex]C_n=0[/itex], because the recursion formula

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

    can be proven in exactly the same way as earlier, and then [itex]C_n\neq 0[/itex] follows.

    pfuuf... could it be that it is now done....
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook