Generating all primitive Pythagorean triples with linear algebra
A Pythagorean triple is a set of positive integers that can be the lengths of sides of a right triangle, i.e. numbers a, b, and c such that
a^2 + b^2 = c^2.
A primitive Pythagorean triple (PPT) is a Pythagorean triple whose elements are relatively prime. For example, (50, 120, 130) is a Pythagorean triple, but it's not primitive because all the entries are divisible by 10. But (5, 12, 13) is a primitive Pythagorean triple.
A method of generating all PPTs has been known since the time of Euclid, but I recently ran across a different approach to generating all PPTs [1].
Let's standardize things a little by assuming our triples have the form (a, b, c) where a is odd, b is even, and c is the hypotenuse [2]. In every PPT one of the sides is even and one is odd, so we will assume the odd side is listed first.
It turns out that all PPTs can be found by multiplying the column vector [3, 4, 5] repeatedly by matrices M0, M1, or M2. In [1], Romik uses the sequence of matrix multiplications needed to create a PPT as trinary number associated with the PPT.
The three matrices are given as follows.
Note that all three matrices have the same entries, though with different signs. If you number the columns starting at 1 (as mathematicians commonly do and computer scientists may not) then Mk is the matrix whose kth column is negative. There is no 0th column, so M0 is the matrix with no negative columns. The numbering I've used here differs from that used in [1].
For example, the primitive Pythagorean triple [5, 12, 13] is formed by multiplying [3, 4, 5] on the left by M2. The PPT [117, 44, 125] is formed by multiplying [3, 4, 5] by
M1 M1 M2.
[1] The dynamics of Pythagorean triples by Dan Romik
[2] Either a is odd and b is even or vice versa, so we let a be the odd one.
If a and b were both even, c would be even, and the triple would not be primitive. If a and b were both odd, c^2 would be divisible by 2 but not by 4, and so it couldn't be a square.
The post Generating all primitive Pythagorean triples with linear algebra first appeared on John D. Cook.