Facts No One Really Checks
Basic theorems that rarely get proved in full detail
Laura Smoller is not a theorist, but a historian at the University of Arkansas at Little Rock. She sports the middle name “Ackerman,” which is one “n” off of the famous mathematician Wilhelm Ackermann. What makes me think of this is her informative page on the history of matrices.
Today I want to discuss an interesting phenomenon: certain bedrock theorems are rarely if ever checked.
Apparently matrices were discovered by the Chinese around 300 BC, while the term “matrix” was only introduced around 1850 by James Sylvester. Matrix theory was then developed by Arthur Cayley in detail, but is unclear who first proved that matrix product, in general, is associative. Smoller points out that “matrix” is the Latin word for womb, which is an interesting choice for this important concept.
The phenomenon we are interested in is that certain basic, critical, fundamental, what else can I say, facts in mathematics are rarely proved. It is not that they are obvious, not at all. It is that they are felt too tedious or technical to prove in a course or even a textbook. A prime example is:
Matrix Product Is Associative: Suppose that are square matrices over the integers. Then we know that
where “” denotes the usual matrix product. This is not hard to prove, but is a bit tedious. Have you checked the details yourself? The following is a typical proof that is given:
A Better Proof of The Associative Law?
Let’s try to give a higher-level proof of this law. Our proof is longer than the usual proof by far, but length is not the only measure of clarity of a proof. I believe that the following proof explains to me in a different way than the usual proof why matrix product is associative.
Let be an algebraic system that is an abelian group under addition denoted by “” and also has a well defined multiplication operation denoted by “.” Suppose that is a subset of that generates under addition: every element of is the sum of a finite number of elements of .
Consider the following two laws:
- The distributive laws: for all in , and .
- The associative law for : for all in , .
We claim that any system with these two laws is associative.
A simple notation convention: If is an element in , then we will use
to denote a representation of as a sum of elements from . We will leave out the limits on the index , since that should cause no confusion. This representation is not necessarily unique, but that has no effect on the remainder of this proof.
So we are all set to start showing that the above two laws imply that multiplication is associative. Suppose that are elements in with representations
Then the product of is equal to
This follows directly from the distributive laws:
The last step uses that addition is cummutative. Now let’s prove the associative law: let be elements in ,
where as before all indexed elements are in .
It follows that is equal to
which is equal to
But is also equal to
Since elements in are associative the later two sums are equal, and we have proved the associative law.
So how do we prove the associative law for square matrices over the natural numbers? We need only check that the above laws are true. The distributive law is easy—it is essentially that matrices are linear operators. Finally what plays the role of ? Just consider matrices of the form
where is the matrix that is all zeroes except that in row and column it is . Here is an example for ,
Clearly these generate the space of matrices by addition. It remains only to show that the associative law holds for these matrices. The key is to note that
is the zero matrix unless and then it is the matrix .
Two More Examples
Here are two additional examples of this phenomenon.
Existence of Universal Turing Machines: We all know that there are universal Turing Machines; this is proved in the original paper of Alan Turing. How many of us have worked through the full details of this theorem, including checking all the details that the universal machine works exactly as claimed? Okay, Ken did—in the late 1980’s he designed a universal Turing Machine using the now out-of-print Turing’s World software developed by John Etchemendy and the late Jon Barwise.
Elliptic Curve Product Is Associative: For any elliptic curve there is a “natural” addition defined on the curve. The proof that this addition is associative is critical to prove that it forms an abelian group. This group is one of the reasons that elliptic curves have such a beautiful theory. Again the checking this is elementary but tedious. Perhaps even more than tedious. Have you checked it yourself?
Here is a comment from a Wikipedia talk page on this very issue:
It’s not obvious to anyone. However, the definition of addition on elliptic curves is quite natural, if you are familiar with Bézout’s theorem, and once you have a commutative binary operation with identity and inverses it’s not hard to conjecture that it constitutes a group operation, and then the proof writes itself (with many computations). The other perspective, that the points of an elliptic curve correspond to divisors of degree 0 in its Picard group, is not so obvious, but once you see it, you immediately get a group operation on the points and you start to wonder whether the other operation which you couldn’t prove associative actually is, and is the same operation. And from the definition of the Picard group it is quite easy to prove they are the same thing. Neither of these qualifies as “obvious,” but they are not obvious in different ways.
The following is a proof of the associative law from the paper, but note it is incomplete. At the end it appeals to a math package. Other proofs state things like, “The proof follows from simple manipulation of the expressions derived in the discussion preceding the theorem.” Okay.
Does the associative law proof given above help in your understanding? I would like to know, please. Also I think it would be good to find other “better” proofs for the other two examples. Also are there are other examples of statements that are fundamental but are rarely checked?