The great merchant, Hypatia of Alexandria, was dead. In her will, she left her vast fortune not to a person, but to a puzzle. Her wealth was locked in a magnificent chest with not one, but three complex locks.
Her will stipulated: "My fortune shall go to the first of my former
students who can provide the number of coins in this chest. To aid you, I
can say this: the number is more than 100 but less than 200. If you
attempt to count the coins by twos, threes, fours, up to tens, there
will always be a specific number of coins left over."
A young scholar, Euclid, was the first to arrive. He listened to the
executor read the conditions and immediately asked for the remainders.
"The remainders are as follows," the executor said, unrolling a scroll.
Divisible by 2: Remainder 1
Divisible by 3: Remainder 2
Divisible by 4: Remainder 3
Divisible by 5: Remainder 4
Divisible by 6: Remainder 5
Divisible by 7: Remainder 0
Divisible by 8: Remainder 1
Divisible by 9: Remainder 2
Divisible by 10: Remainder 3
Euclid's face fell. "This is chaos! The conditions are not coprime.
Four, six, eight, nine, and ten are all composite! This will take me a
week of calculations!"
Just then, his rival, the quick-witted Sun Tzu, arrived. He glanced at
the list and chuckled. "You are thinking like a laborer, Euclid, not a
mathematician. You are looking at the locks; I am looking at the key."
"And what key is that?" Euclid scoffed.
"The key," said Sun Tzu, "is to see what the number almost is, not what it is. Look at the list. What do you see?"
I will skip the rest of the story. Stories from the past are fine,
but we have a story of the present, and it needs your full attention.
Here it is.
In this note we continue the discussion started in An SO(2,2) Iterated Function System Part 3 - Weyl spinors and null vectors, but now replacing the field of real numbers R by the ring of integers Z. We will show that the following Proposition holds:
Proposition 1. Let A = A = {{a,b},{c,d}} be a non-zero matrix with integer entries, A ∈ Z2⨉2, with det(A) = ad - bc = 0. Then there exist vectors v,w ∈ Z2 such that
A = vwT. (1)
The factorization is unique up to a sign: if A = vwT, then A = (-v)(-wT) is the only other (trivial) variation.
The proof of this Proposition uses the concept of the Greatest Common Divisor (gcd). The standard definition of gcd is:
Definition. For any two integers a,b, at least one of which is nonzero, we denote by gcd(a,b) their greatest common divisor, that is the greatest integer d such that there exist integers e,f such that a = de, b = df. In particular, if (a) is nonzero, we have gcd(0,a) = gcd(a,0) = |a|.
But that definition is tailored for integers, while the concept of gcd is more general, and it has to do with the Unique Factorization Property. So here is a deeper and more formal definition (for non-zero integers)
In other words gcd(a,b) is the product it's the product of all common primes, each raised to the power of the smallest exponent found in either number. The signs of the original integers do not affect the result.
Before proving the Proposition, we first prove the following Lemma
Lemma 1. Let a,b,c,d be integers such that gcd(a,b)=1 and ad = bc. Then there is an integer k such that
c = ka,
d = kb. (1)
Proof. First note that if a = 0 and b = 0, then gcd(a,b) is
undefined, therefore this case is implicitly excluded by the assumption
that gcd(a,b) = 1. Suppose a = 0 and b ≠ 0. Then gcd(0,b) = |b|, and,
since gcd(a,b) = 1, it follows that b = ± 1. From ad = bc it follows
that c = 0. Take k = ±d. Then d = kb and c = ka. Similarly if b = 0 and
a ≠ 0. Let us now assume that both a ≠ 0 and b ≠ 0. By assumption
gcd(a,b) = 1 and ad = bc. Think of the unique prime decomposition of (b)
on the right hand side of ad = bc. None of these primes entering the
composition of b is in (a), since gcd(ab)=1. Therefore they must be all
contained in d. Therefore there is an integer k such that d = kb. But
then, from ad = bc, it follows kab = bc, and, since b ≠ 0, we have c =
ka. QED
We can now return to proving Proposition 1.
Proof (of Proposition 1). Since A is a nonzero
matrix, at least one of it rows is nonzero. Suppose it is the first row:
(a,b). For the second row the proof goes in a complete analogy.
Let g = gcd(a,b). Since at least one of a,b is nonzero, g = gcd(a,b) is well defined. Thus g is a positive integer, and there exist integers a',b' such that
a = ga',
b= gb', (2)
and gcd(a',b') = 1. Since ad = bc, and g is positive, from ad = bc it
follows that a'd = b'c. We can now apply Lemma 1 to deduce that there
exist an integer k such that
c = ka',
d = k b'. (3)
From (2) and (3) it follows that A is of the form:
A = {{ga',gb'},{ka',kb'}}. Setting v = (g,k)T, w = (a',b') we have A = vwT. QED
It follows also from the proof that the decomposition is unique if we require the two components of (w) to be coprime (i.e. if their gcd is 1).
Exercise 1. Find the decomposition of the matrix x^, where x = (3,14,6,13) as mentioned in the Example Part 2.
To be continued...
