(Real Math) Looking for a fancy matrix trick

C

CptBork

Valued Senior Member
Hi guys, some of you may be familiar with the following result:

Given distinct complex numbers $$a_1,a_2,a_3$$, the following is always true:
$$\frac{1}{\left(a_1-a_2\right)\left(a_1-a_3\right)}+\frac{1}{\left(a_2-a_1\right)\left(a_2-a_3\right)}+\frac{1}{\left(a_3-a_1\right)\left(a_3-a_2\right)}=0$$

It's fairly straightforward to prove, by combining the terms under a common denominator. However there's a generalization of this identity:

$$\sum_{i=1}^k\prod_{j\neq i}\frac{1}{a_i-a_j}=0$$ where the $$a_i\mathrm{\'s}$$ are all distinct complex numbers, and $$k$$ is obviously a natural number $$\geq 2$$.

I know a quick, simple way of proving this generalized identity using a closed contour integration through the complex plane, which I'm willing to share if anyone's interested. However I remember a long time ago this math genius I once knew showed me a divinely clever way of proving it with matrices. I'm pretty sure from memory it's related to diagonalization and from there it's likely a comparison of traces, but the most I've personally been able to get by such methods is a completely obvious, trivial result. So would any of the math whizzes here have any idea how I could prove this via a clever application of matrices?

I believe this problem was once given in a Putnam Prize competition, but I don't have any more info than that. The identity looks similar at a glance to the Vandermonde matrix determinant, but I don't see any meaningful connection upon closer inspection. Does anyone know what this identity is called or where I can find more info on it? Anyone have yet another way of proving it?
 
I'm still hoping someone can come up with a matrix solution for this problem, or identify the name of the identity or an equivalent result, so I can do further research from there. In the meantime, I managed to independenty discover yet another way of proving this identity, which now gives me two that I can produce on demand. I thought there looked to be some sort of connection to Lagrange interpolation, but I just couldn't pin it down until now. Anyhow, here's how it goes:

Set $$a_k=z$$. Then we may write:

$$\sum_{i=1}^k\prod_{j\neq i}\frac{1}{a_i-a_j}=\prod_{j=1}^{k-1}\frac{1}{z-a_j}+\sum_{i=1}^{k-1}\left(\frac{1}{a_i-z}\right)\prod_{\stackrel{j\neq i}{j\neq k}}\frac{1}{a_i-a_j}=f(z)$$

Where $$f(z)$$ is a complex-valued function defined everywhere except at $$z=a_i,\quad i=1,\ldots,k-1$$

We wish to show that $$f(z)$$ is necessarily zero when $$z\neq a_i,\quad i=1,\ldots,k-1$$

Multiply everything by $$\prod_{j=1}^{k-1}(z-a_j)$$ to obtain:

$$1-\sum_{i=1}^{k-1}\prod_{\stackrel{j\neq i}{j\neq k}}\left(\frac{z-a_j}{a_i-a_j}\right)=f(z)\prod_{j=1}^{k-1}(z-a_j)$$

The left-hand side is clearly a complex polynomial in $$z$$ which we may refer to as $$P(z)$$. It's easy to see the $$P(z)$$ has roots at $$z=a_i,\quad i=1,\ldots,k-1$$ and may thus be written as follows:

$$P(z)=A(z)\prod_{j=1}^{k-1}(z-a_j)$$ for some complex polynomial $$A(z)$$.

But clearly,
$$P(z)=1-\sum_{i=1}^{k-1}\prod_{\stackrel{j\neq i}{j\neq k}}\left(\frac{z-a_j}{a_i-a_j}\right)$$
is a polynomial of degree $$\leq k-2$$, which therefore requires that $$A(z)\equiv 0$$.

Thus we see that $$f(z)\prod_{j=1}^{k-1}(z-a_j)\equiv 0$$ and therefore $$f(z)=0\quad\forall\quad z\neq a_i,\quad i=1,\ldots,k-1$$, thereby proving the desired result.

I welcome any questions about this proof, or any other methods of proof you guys might know of. Once again though, I'm really desperately looking for a matrix method of proof, I think in addition to usage of diagonalization it may have also involved an induction step, but again my memory is fuzzy on both of these details.

Edit: Apologies, I should have been more careful with my notation, since I was already using $$k$$ as an integer index. I've replaced $$k(z)$$ with $$f(z)$$ in the notation.
 
Last edited:
CptBork said:
Hi guys, some of you may be familiar with the following result:

Given distinct complex numbers $$a_1,a_2,a_3$$, the following is always true:
$$\frac{1}{\left(a_1-a_2\right)\left(a_1-a_3\right)}+\frac{1}{\left(a_2-a_1\right)\left(a_2-a_3\right)}+\frac{1}{\left(a_3-a_1\right)\left(a_3-a_2\right)}=0$$

It's fairly straightforward to prove, by combining the terms under a common denominator. However there's a generalization of this identity:

$$\sum_{i=1}^k\prod_{j\neq i}\frac{1}{a_i-a_j}=0$$ where the $$a_i\mathrm{\'s}$$ are all distinct complex numbers, and $$k$$ is obviously a natural number $$\geq 2$$.
Click to expand...

If you multiply the LHS with $$\prod_{j\neq i}{a_i-a_j}$$ you get $$\sum_{i=1}^k{a_i-a_j}=0$$. What am I missing?
 
Tach said:
If you multiply the LHS with $$\prod_{j\neq i}{a_i-a_j}$$ you get $$\sum_{i=1}^k{a_i-a_j}=0$$. What am I missing?
Click to expand...

What value would $$i$$ take in this case? You can't multiply the LHS like that to get your result, you would have to multiply each term in the sum by that amount even though the sum runs over $$i$$ as a variable index.

Edit: Would it help if I wrote it as $$0=\sum_{i=1}^k\prod_{j\neq i}\left(\frac{1}{a_i-a_j}\right)$$?
 
CptBork said:
What value would $$i$$ take in this case? You can't multiply the LHS like that to get your result, you would have to multiply each term in the sum by that amount even though the sum runs over $$i$$ as a variable index.

Edit: Would it help if I wrote it as $$0=\sum_{i=1}^k\prod_{j\neq i}\left(\frac{1}{a_i-a_j}\right)$$?
Click to expand...

Not quite, look at your starting point:

$$\frac{1}{\left(a_1-a_2\right)\left(a_1-a_3\right)}+\frac{1}{\left(a_2-a_1\right)\left(a_2-a_3\right)}+\frac{1}{\left(a_3-a_1\right)\left(a_3-a_2\right)}$$

Multiply by $$(a_1-a_2)(a_2-a_3)(a_3-a_1)$$ , you get 0.

Now, move to:

$$\frac{1}{(a_1-a_2)(a_2-a_3)(a_3-a_4)}+\frac{1}{(a_2-a_3)(a_3-a_4)(a_4-a_1)}+.....$$

The same approach will show that the above equal 0.
 
Tach said:
Not quite, look at your starting point:

$$\frac{1}{\left(a_1-a_2\right)\left(a_1-a_3\right)}+\frac{1}{\left(a_2-a_1\right)\left(a_2-a_3\right)}+\frac{1}{\left(a_3-a_1\right)\left(a_3-a_2\right)}$$

Multiply by $$(a_1-a_2)(a_2-a_3)(a_3-a_1)$$ , you get 0.

Now, move to:

$$\frac{1}{(a_1-a_2)(a_2-a_3)(a_3-a_1)}+\frac{1}{(a_2-a_3)(a_3-a_4)(a_4-a_1)}+.....$$

The same approach will show that the above equal 0.
Click to expand...

But is there an obvious way to see that without doing the brute force multiplication and collecting terms? We need to do it for arbitrary values of $$k$$. As I said your generalized multiplication above doesn't give a nice, clean result because in that multiplication it's not even clear what index $$i$$ represents, since you've multiplied from outside the indexed sum.
 
CptBork said:
But is there an obvious way to see that without doing the brute force multiplication and collecting terms? We need to do it for arbitrary values of $$k$$. As I said your generalized multiplication above doesn't give a nice, clean result because in that multiplication it's not even clear what index $$i$$ represents, since you've multiplied from outside the indexed sum.
Click to expand...

Sorry, there was a typo, what I wanted was:

Now, move to:

$$\frac{1}{(a_1-a_2)(a_2-a_3)(a_3-a_4)}+\frac{1}{(a_2-a_3)(a_3-a_4)(a_4-a_1)}+.....$$
 
Tach said:
Sorry, there was a typo, what I wanted was:

Now, move to:

$$\frac{1}{(a_1-a_2)(a_2-a_3)(a_3-a_4)}+\frac{1}{(a_2-a_3)(a_3-a_4)(a_4-a_1)}+.....$$
Click to expand...

That can't be right, the denominator in the first term should be $$(a_1-a_2)(a_1-a_3)(a_1-a_4)$$, does that make a difference to you?
 
CptBork said:
That can't be right, the denominator in the first term should be $$(a_1-a_2)(a_1-a_3)(a_1-a_4)$$, does that make a difference to you?
Click to expand...

Aren't you doing circular permutations through the combinations of differences? Why don't you write down what you think the case for $$k=4$$ looks like, this should expedite things.
 
Now that I think of it, multiplying to get rid of the denominators and switching the order of the product and sum might yield a third method of proof, I'll have to try that...
 
Tach said:
Aren't you permuting through combinations? Why don't you write down what you think the case for $$k=4$$ looks like, this should expedite things.
Click to expand...

For $$k=4$$:

$$\frac{1}{(a_1-a_2)(a_1-a_3)(a_1-a_4)}+\frac{1}{(a_2-a_1)(a_2-a_3)(a_2-a_4)}+\frac{1}{(a_3-a_1)(a_3-a_2)(a_3-a_4)}+\frac{1}{(a_4-a_1)(a_4-a_2)(a_4-a_3)}=0$$
 
CptBork said:
For $$k=4$$:

$$\frac{1}{(a_1-a_2)(a_1-a_3)(a_1-a_4)}+\frac{1}{(a_2-a_1)(a_2-a_3)(a_2-a_4)}+\frac{1}{(a_3-a_1)(a_3-a_2)(a_3-a_4)}+\frac{1}{(a_4-a_1)(a_4-a_2)(a_4-a_3)}=0$$
Click to expand...


Ok,

Let's multiply with $$(a_1-a_2)(a_1-a_3)(a_1-a_4)(a_2-a_3)(a_2-a_4)(a_3-a_4)$$
 
Tach said:
Sure, you just showed a couple. But I don't see multiplying be the smallest common .... brute force, it is just a different way.
Click to expand...

Can you show how it would be done quickly for the general case? That way we don't need to work out the details term by term (brute force), since we can't do that for all possible values of $$k$$.
 
CptBork said:
Hi guys, some of you may be familiar with the following result:

Given distinct complex numbers $$a_1,a_2,a_3$$, the following is always true:
$$\frac{1}{\left(a_1-a_2\right)\left(a_1-a_3\right)}+\frac{1}{\left(a_2-a_1\right)\left(a_2-a_3\right)}+\frac{1}{\left(a_3-a_1\right)\left(a_3-a_2\right)}=0$$
Click to expand...

Ok, here is another way:

$$\frac{1}{(a_1-a_2)(a_1-a_3)}=\frac{A}{a_1-a_2}+\frac{B}{a_1-a_3}$$

The above triggers $$(A+B)a_1-A a_3-B a_2=1$$ , valid for any $$a_i$$.
This triggers $$A+B=0$$ , $$Aa_3+Ba_2=-1$$, with the immediate consequence $$A=-B=\frac{1}{a_2-a_3}$$ so:

$$\frac{1}{(a_1-a_2)(a_1-a_3)}=\frac{1}{a_2-a_3}(\frac{1}{a_1-a_2}-\frac{1}{a_1-a_3})$$
 
Last edited:
Tach said:
Ok, here is another way:

$$\frac{1}{(a_1-a_2)(a_1-a_3)}=\frac{A}{a_1-a_2}+\frac{B}{a_1-a_3}$$

The above triggers $$(A+B)a_1-A a_3-B a_2=1$$ , valid for any $$a_i$$.
This triggers $$A+B=0$$ with the immediate consequence $$A=-B=\frac{1}{a_2-a_3}$$ so:

$$\frac{1}{(a_1-a_2)(a_1-a_3)}=\frac{1}{a_2-a_3}(\frac{1}{a_1-a_2}-\frac{1}{a_1-a_3})$$
Click to expand...

So far so good, where do I go from there?
 
CptBork said:
So far so good, where do I go from there?
Click to expand...

So, this proves the initial problem. The next step is :

$$\frac{1}{(a_1-a_2)(a_1-a_3)(a_1-a_4)}=\frac{A}{(a_1-a_2)(a_1-a_3)}+\frac{B}{(a_1-a_3)(a_1-a_4)}+\frac{C}{(a_1-a_4)(a_1-a_2)}$$

Same reasoning should produce A,B,C and the problem reduces to the previous case:

$$A(a_1-a_4)+B(a_1-a_2)+C(a_1-a_3)=1$$

Again $$A+B+C=0$$ and $$Aa_4+Ba_2+Ca_3=-1$$
 
Tach said:
So, this proves the initial problem. The next step is :

$$\frac{1}{(a_1-a_2)(a_1-a_3)(a_1-a_4)}=\frac{A}{a_1-a_2}+\frac{B}{a_1-a_3}+\frac{C}{a_1-a_4}$$

Same reasoning should produce A,B,C
Click to expand...

Can you explain how your method solves the original problem? I still can't see how to do it this way without a term-by-term computation. And then there's also the problem of computing A, B, C, D,... without term-by-term computations too, I can't see how it would work for the general case.
 
CptBork said:
Can you explain how your method solves the original problem? I still can't see how to do it this way without a term-by-term computation. And then there's also the problem of computing A, B, C, D,... without term-by-term computations too, I can't see how it would work for the general case.
Click to expand...


I wasn't finished with the post, look up.
 
You must log in or register to reply here.
Back
Top