Look at small cases

Quick description

A standard question of Gel'fond's, when listening to a talk, is: "What is the simplest nontrivial example?" This article shows how useful this principle can be.

Example 1: Counting and the Lagrange Identity

This example is borrowed from this blog post. It is a prime example of how a proof for a general argument can be worked out by considering simple cases.^◊ The Lagrange identity for $\mathbb{C}$ says that

$|\sum_{i=0}^{n} a_{i}b_{i}|^{2}=\sum_{i=0}^{n} |a_{i}|^{2}\sum_{i=0}^{n} |b_{i}|^{2}-\sum_{1 \leq{i}<j\leq{n}} |a_{i}\overline{b_{j}}-a_{j}\overline{b_{i}}|^{2}$ (1)

We will analyze the case for n=3. It will provide a beautiful outline for a general proof.

The left hand side of the equality (1) will be equal to

$|a_{1}b_{1} +a_{2}b_{2}+a_{3}b_{3}|^{2}=(a_{1}b_{1} +a_{2}b_{2}+a_{3}b_{3})(\overline{a_{1}b_{1}}+\overline{a_{2}b_{2}}+\overline{a_{3}b_{3}})$ (2)

It would be helpful indeed to consider the following 3 x 3 matrix for the sum of all the elements of this matrix is equal to the LHS of (2).

$\left(\begin{array}{ccc}a_{1}\overline{a_{1}}b_{1}\overline{b_{1}}&a_{1}\overline{a_{2}}b_{1}\overline{b_{2}}&a_{1}\overline{a_{3}}b_{1}\overline{b_{3}}\\ a_{2}\overline{a_{1}}b_{2}\overline{b_{1}}&a_{2}\overline{a_{2}}b_{2}\overline{b_{2}}&a_{2}\overline{a_{3}}b_{2}\overline{b_{3}}\\ a_{3}\overline{a_{1}}b_{3}\overline{b_{1}}&a_{3}\overline{a_{2}}b_{3}\overline{b_{2}}&a_{3}\overline{a_{3}}b_{3}\overline{b_{3}}\end{array}\right)$

In fact, the elements of the matrix are the terms on the RHS in (2).

Each term of the matrix above can thus be represented as

$A_{ij}=a_{i}\overline{a_{j}}b_{i}\overline{b_{j}}$

Now consider the first term on the RHS in (1). For n=3, it is

$(|a_{1}|^{2}+|a_{2}|^{2}+|a_{3}|^{2})(|b_{1}|^{2}+|b_{2}|^{2}+|b_{3}|^{2})=(a_{1}\overline{a_{1}}+a_{2}\overline{a_{2}}+a_{3}\overline{a_{3}})(b_{1}\overline{b_{1}}+b_{2}\overline{b_{2}}+b_{3}\overline{b_{3}})$ (3)

Again, as above, it would be helpful to consider the following matrix.

$\left(\begin{array}{ccc}a_{1}\overline{a_{1}}b_{1}\overline{b_{1}}&a_{1}\overline{a_{1}}b_{2}\overline{b_{2}}&a_{1}\overline{a_{1}}b_{3}\overline{b_{3}}\\ a_{2}\overline{a_{2}}b_{1}\overline{b_{1}}&a_{2}\overline{a_{2}}b_{2}\overline{b_{2}}&a_{2}\overline{a_{2}}b_{3}\overline{b_{3}}\\ a_{3}\overline{a_{3}}b_{1}\overline{b_{1}}&a_{3}\overline{a_{3}}b_{2}\overline{b_{2}}&a_{3}\overline{a_{3}}b_{3}\overline{b_{3}}\end{array}\right)$

The elements of this matrix are again the terms on RHS in (3).

We can thus call each of them

$B_{ij}=a_{i}\overline{a_{i}}b_{j}\overline{b_{j}}$

The last term in (1) is

$-(|a_{1}\overline{b_{2}}-a_{2}\overline{b_{1}}|^{2}+|a_{1}\overline{b_{3}}-a_{3}\overline{b_{1}}|^{2}+|a_{2}\overline{b_{3}}-a_{3}\overline{b_{2}}|^{2})$ (4)

This time we use two matrices to organize the terms in (4).

$\left(\begin{array}{ccc}0&a_{1}\overline{a_{2}}b_{1}\overline{b_{2}}&a_{1}\overline{a_{3}}b_{1}\overline{b_{3}}\\ a_{2}\overline{a_{1}}b_{2}\overline{b_{1}}&0&a_{2}\overline{a_{3}}b_{2}\overline{b_{3}}\\ a_{3}\overline{a_{1}}b_{3}\overline{b_{1}}&a_{3}\overline{a_{2}}b_{3}\overline{b_{2}}&0\end{array}\right)$

and

$\left(\begin{array}{ccc}0&a_{1}\overline{a_{1}}b_{2}\overline{b_{2}}&a_{1}\overline{a_{1}}b_{3}\overline{b_{3}}\\ a_{2}\overline{a_{2}}b_{1}\overline{b_{1}}&0&a_{2}\overline{a_{2}}b_{3}\overline{b_{3}}\\ a_{3}\overline{a_{3}}b_{1}\overline{b_{1}}&a_{3}\overline{a_{3}}b_{2}\overline{b_{2}}&0\end{array}\right)$

And we thus define elements of the first and the second matrix as $C_{ij}$ and $D_{ij}$ respectively where

$C_{ij}=a_{i}\overline{a_{j}}b_{i}\overline{b_{j}}\sigma_{ij}$

$D_{ij}=a_{i}\overline{a_{i}}b_{j}\overline{b_{j}}\sigma_{ij}$

and where $\sigma_{ij}$ is defined to be $0$ if i=j and is equal to unity otherwise.

Now let $T_{ij}=A_{ij}+D_{ij}-B_{ij}-C_{ij}$

Therefore,

$T_{ij}=A_{ij}(\delta_{ij}+\sigma_{ij})+D_{ij}-B_{ij}(\delta_{ij}+\sigma_{ij})-C_{ij}$

where we have used $\delta_{ij}+\sigma_{ij}=1$ ( $\delta_{ij}$ is the Kronecker delta)

And so,

$T_{ij}=a_{i}\overline{a_{j}}b_{i}\overline{b_{j}}\delta_{ij}+a_{i}\overline{a_{j}}b_{i}\overline{b_{j}}\sigma_{ij}+a_{i}\overline{a_{i}}b_{j}\overline{b_{j}}\sigma_{ij}$

$-a_{i}\overline{a_{i}}b_{j}\overline{b_{j}}\delta_{ij}-a_{i}\overline{a_{i}}b_{j}\overline{b_{j}}\sigma_{ij}-a_{i}\overline{a_{j}}b_{i}\overline{b_{j}}\sigma_{ij}$

$T_{ij}=a_{i}\overline{a_{i}}b_{i}\overline{b_{i}}-a_{i}\overline{a_{i}}b_{i}\overline{b_{i}}=0$

Since each $T_{ij}$ is zero, the sum $\sum_{i,j=1}^{n}T_{ij}=0$

which automatically implies the Lagrange Identity in $\mathbb{C}$ .

8531 reads
Subscribe

Comments

This article should not be a

Wed, 29/04/2009 - 19:46 — Sameed

This article should not be a stub. It is infact the best suggestion I have come across here. To see how it can lead to some 'mathematically interesting information',I suggest this webpage- http://disquisitionesmathematicae.wordpress.com

I marked it as a stub because

Wed, 29/04/2009 - 20:13 — gowers

I marked it as a stub because it had neither a "General discussion" section nor any examples. It is certainly interesting and valuable advice, but doesn't quite count as "mathematically interesting information" in the intended sense, because it doesn't yet contain any actual mathematics. But if, say, you were to add the example that is explained on the page you suggest, then it would instantly lose its stub status.

Just to repeat, it is possible for a Tricki article to contain something interesting, but still to count as a stub. So you should not take the stub designation as in any way suggesting that Gel'fond's suggestion is uninteresting. But I would see the quotation as the beginning of what should ultimately be a quite long article with several examples: a principle this important deserves nothing less.

Absolutely.There should be a

Wed, 29/04/2009 - 20:24 — Sameed

Absolutely.There should be a string of articles.Hopefully, many more articles would come up with an explanation.Tricky is going to be a great ride.

I have added the example

Thu, 30/04/2009 - 13:10 — Sameed

I have added the example mentioned above. It might still require some editing though. You may state some prerequisites for the above example but I personally think that it's fairly straightforward and that elementary linear algebra would suffice.

Inline comments

The following comments were made inline in the article. You can click on 'view commented text' to see precisely where they were made.

I know I suggested putting

Thu, 30/04/2009 - 14:37 — gowers

I know I suggested putting this example here, but now I look at it carefully, I wonder whether it really is a prime example of Gel'fond's advice. It seems to me that the basic proof (even if you dress it up with matrices) is this: expand out both sides and observe that you get the same answer. And it's not clear to me that doing that for $n=3$ is any easier than doing it for the general case.

A truly convincing example of this trick is one where the only realistic way of doing the general case is to do small cases and spot a non-obvious pattern.

Maybe you are right. There

Thu, 30/04/2009 - 14:52 — Sameed

Maybe you are right. There are loads of problems that can be solved by doing specific cases only. Lucas's identity in elementary number theory might be a good example.(Adding the terms in the Pascal's triangle diagonally yields the Fibonacci numbers)

I just noticed that there is

Sat, 09/05/2009 - 18:26 — Sameed

I just noticed that there is a topic in 'What kind of problem are you trying to solve' titled 'Prove the result for some cases and deduce it for the rest'. It would be nice if we could link that topic to this article in some way.

I think there is an important

Sat, 09/05/2009 - 20:03 — gowers

I think there is an important distinction between the idea of that article and the idea of this. It's the distinction between proving a result for a few simple cases and deducing the rest, and proving it in a few special cases in order to get ideas about how to prove the general result. I think putting a link might blur this distinction in an unhelpful way.

Post new comment

(Note: commenting is not possible on this snapshot.)