(Real Math) Looking for a fancy matrix trick

[CptBork]

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?

 

[CptBork]

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.

 

[Tach]

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

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?

 

[CptBork]

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?

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

 

[Tach]

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

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.

 

[CptBork]

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.

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.

 

[Tach]

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.

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)}+.....$$

 

[CptBork]

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)}+.....$$

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?

 

[Tach]

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?

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.

 

[CptBork]

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

 

[CptBork]

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.

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

 

[Tach]

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

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

 

[CptBork]

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

Is there a way to work out the result without brute force?

 

[Tach]

Is there a way to work out the result without brute force?

Sure, you just showed a couple. But I don't see multiplying be the smallest common .... brute force, it is just a different way.

 

[CptBork]

Sure, you just showed a couple. But I don't see multiplying be the smallest common .... brute force, it is just a different way.

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

 

[Tach]

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

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

 

[CptBork]

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

So far so good, where do I go from there?

 

[Tach]

So far so good, where do I go from there?

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

 

[CptBork]

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

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.

 

[Tach]

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.

I wasn't finished with the post, look up.