Generating Generalized Pythagorean Tuples

by Lisa Henkel, February 25, 2005

==============================

Generating Pythagorean Triples

==============================

A Pythagorean triple is a triple of integers such that x² + y² = z².  The Pythagorean theorem states that in a right triangle, the sum of the squares of the legs equals the square of the hypotenuse.

First, we need to learn to generate Pythagorean triples.  Hadwin & Teigen had the following way to generate Pythagorean triples (1971, Math Monthly):

Choose an even q, and m and n such that q²=2mn. Let x = q + m, y = q + n, and z = q + m + n.  Then (x, y, z) is a Pythagorean triple.   In particular x² + y² = z² if and only if q²=2mn.  This can be proved by substituting x = q + m, y = q + n, and z = q + m + n into x² + y² = z², and multiplying and canceling like terms.

Furthermore, this method generates all Pythagorean triples, both primitive and non-primitive. A primitive Pythagorean triple is a Pythagorean triple (x, y, z) where GCD (x, y, z) = 1, that is a triple in which there is no factor bigger than 1 in (x, y, z) that all three numbers has in common.

    q    q^2  m    n    x    y    z
   ===  ===  ===  ===  ===  ===  ===   
    2    4    1    2    3    4    5
    4    16   1    8    5    12   13
    4    16   2    4    6    8    10

Some other sites that talk about Pythagorean triples are:

http://mathworld.wolfram.com/PythagoreanTriple.html

http://www.cut-the-knot.com/pythagoras/PT_matrix.shtml.

http://www.cut-the-knot.org/pythagoras/pythTriple.shtml

http://www.math.clemson.edu/~rsimms/neat/math/pyth/

==============================================

Quadratic Functions Instead of Perfect Squares

==============================================

Similar to generating square numbers that add to another square to equal a square, you can generate triangle numbers that add to another triangle number to equal a triangle number.   Triangle numbers are numbers such as 1, 3, 6, 10, 15, that are sums of the first x integers.  Note that the xth triangle number is given by the function T(x) = (x² + x) / 2.

In fact, if f(x) = ax² + bx + c is any quadratic and x = q + m, y = q + n, and z = q + m + n, then f(x) + f(y) = f(z) if and only if f(q) = 2amn.  The proof is to substitute in for x, y, and z and calculate.

This gives a way to generate all triples of numbers (x, y, z) where f(x) + f(y) = f(z), by solving f(q) = 2amn and setting x = q + m, y = q + n, and z = q + m +n.  You can see that all such triples are generated by this method since if (x, y, z) is such a tuple of integers, then q = x + y – z, m = z – y, and n = z – x are integers that are able to be generated by the relation f(q) = 2amn.

Since triangle numbers satisfy T(x) = (x² + x) / 2, solving T(q) = mn and setting x = q + m, y = q + n, and z = q + m + n will give all triples (x, y, z) where T(x) + T(y) = T(z)

Triangle Number Triples

q    T(q)  m    n      x    y    z    T(x)   T(y)   T(z)
==   ===  ===  ===    ===  ===  ===   ===    ===    ===
1    1     1    1      2    2    3     3      3      6
2    3     1    3      3    5    6     6      15     21
3    6     1    6      4    9    10    10     45     55
3    6     2    3      5    6    8     15     21     36

Also, you can generate Pythagorean quadruples by this method.   Suppose you want to generate (w, x, y, z) where w² + x² + y² = z².  This makes z the diagonal of a box of dimensions w, x, and y.  Choose w, let f(t) = t² + w², and solve f(q) = 2mn, and set x = q + m, y = q + n, and z = q + m +n to get your Pythagorean quadruple.  This can be easily generalized to generate Pythagorean tuples of any dimension.

======================

Further Generalization

======================

This is a brief paragraph.  If the reader does not understand this stuff, they should not hesitate to go on.

Let (G,+) and (H,+) be Abelian groups, and let [,]:GxG->H be a homomorphism in each coordinate.  Further let q = x + y – z, m = z – y, and n = z – x.   Then [x,x] + [y,y] = [z,z] if and only if [q,q] = [m,n] + [n,m].  The result above about quadratic function triples (x, y, z) where f(x)+ f(y) = f(z) can be derived as a corollary of this, as well as deriving it independently.

==================================================

Lonnemo Trinary Trees (Triples by a Matrix Method)

==================================================

See H. Anders Lonnemo's page on cut-the-knot, after which this page is modeled: http://www.cut-the-knot.com/pythagoras/PT_matrix.shtml. I will summarize his work here.

Given a Pythagorean triple (x, y, z), this gives a specific q = x + y - z, m = z - y, and n = z - x.  Because they solve q² = 2mn, you can negate q setting q' = -q, and solve x' = q' + m, y' = q' + n, and z' = q' + m + n, to get a brand new triple (x', y', z')

In linear algebra form, let L = (Matrix from q'mn to x'y'z')*(Matrix that negates q)*(Matrix from xyz to qmn)

      [ -1   -2   2   ]       [ 1 1 0 ]   [-1 0 0 ]   [  1  1 -1 ]
L  =  [ -2   -1   2   ]   =   [ 1 0 1 ] * [ 0 1 0 ] * [  0 -1  1 ]
      [ -2   -2   3   ]       [ 1 1 1 ]   [ 0 0 1 ]   [ -1  0  1 ]

Then (x', y', z')^T = L(x, y, z)^T. (The T, standing for "transpose", means that you take the column vector instead of the row vector of x, y, and z.)  Note that Lonnemo's original work does the matrix multiplying the vector with the matrix on the right, and this here does it on the left. His way made it so he didn't have to do the transpose. We end up working with L which is the transpose of the matrix he had.

Build the Trinary Tree as follows:  Start with a valid primitive Pythagorean triple and use all three additional sign combinations on x and y.  Then use the matrix L on all of these combinations. (This means you transform x, y, z into m, n, q, negate q, and transform back to x', y', z'.)

               x    y    z      m    n    q    q'     x'   y'   z'
              ===  ===  ===    ===  ===  ===  ===    ===  ===  ===
      PPT       3    4    5      1    2    2   -2     -1    0    1   (Root)
      SPPT     -3    4    5      1    8   -4    4      5   12   13   PPT
      SPPT      3   -4    5      9    2   -6    6     15    8   17   PPT
      SPPT     -3   -4    5      9    8  -12   12     21   20   29   PPT

Note that the original primitive Pythagorean triple gets mapped to a triple with smaller z, whereas the other three get mapped to a Pythagorean triple with bigger z.

Additional things to note:

1. L*L = the identity matrix.  This is clear from the construction of L.  This means that if (x', y', z')^T = L(x, y, z)^T, then (x, y, z)^T = L(x', y', z')^T.

2. If (x, y, z) are all positive, then (x', y', z')^T = L(x, y, z)^T has z' < z. (Since x, y, z forms a triangle, q = x + y - z > 0.  Therefore 2z < 2x + 2y, and therefore z' = 3z - 2x - 2y < z.)

3. Note that primitive Pythagorean triples always get mapped to other primitive Pythagorean triples.   This is because GCD(x, y, z) = GCD(x', y', z') because if something divides all three coordinates then it divides the three coordinates after using L, and L*L = the Identity.

Theorem: Starting with the triples (1, 0, 1) and (0, 1, 1), we can generate all the (signed) primitive Pythagorean triples by using the matrix L and the matrices

     [-1 0 0]        [ 1  0 0]        [ 1 0  0]
S1 = [ 0 1 0] , S2 = [ 0 -1 0] , S3 = [ 0 1  0]
     [ 0 0 1]        [ 0  0 1]        [ 0 0 -1] .

Proof: Suppose (X, Y, Z) is the first primitive Pythagorean triple (the one with the smallest Z > 0) with X, Y, and Z all greater than 0 that is not generated by this method. Let (X', Y', Z')^T = L(X, Y, Z)^T.  Then Z' < Z, and (X', Y', Z') was therefore one of the triples that had been generated by this method.   But then (X, Y, Z) is able to be generated by this method by the application of the matrix L.

=======================================================

First Stab at Pythagorean Quadruples by a Matrix Method

=======================================================

Let L1 = [1 0] = [ 1  0  0  0]
         [0 L]   [ 0 -1 -2  2]
                 [ 0 -2 -1  2]
                 [ 0 -2 -2  3]

Theorem: If (w, x, y, z) is a primitive Pythagorean quadruple, then L1(w, x, y, z)^T is a primitive Pythagorean quadruple.

Proof: Let f(t) = t² + w², and let q = x + y - z, m = z - y, n = z - x.  We know f(q) = 2mn, so if you then let q' = -q, then f(-q) = 2mn.  Let w' = w, x' = q' + m, y' = q' + n, z' = q' + m + n.  This is a new Pythagorean quadruple.  But this is precisely the application (w', x', y', z')^T = L1(w, x, y, z)^T. L1 maps primitive quadruples to primitive quadruples because GCD(w, x, y, z) = GCD(w', x', y', z') because if something divides all four coordinates then it divides the four coordinates after using L1, and L1*L1 = the Identity.

Let S1, S2, S3, S4 each be the matrix that changes the sign on the jth coordinate. That is 

   S1 = [-1 0 0 0]   S2 = [1  0 0 0]   
        [ 0 1 0 0]        [0 -1 0 0]
        [ 0 0 1 0]        [0  0 1 0]
        [ 0 0 0 1]        [0  0 0 1]

and similarly for S3 and S4. 

Let R12, R13, and R23 be the matrices that swap the appropriate two coordinates.  That is

   R12 = [0 1 0 0]   R13 = [0 0 1 0]   R23 = [1 0 0 0]
         [1 0 0 0]         [0 1 0 0]         [0 0 1 0]
         [0 0 1 0]         [1 0 0 0]         [0 1 0 0]
         [0 0 0 1]         [0 0 0 1]         [0 0 0 1]   .

Theorem: Using the matrices L1, S1, S2, S3, S4, R12, R13, R23, and starting with the Pythagorean quadruple (1, 0, 0, 1), you can generate all the (signed) primitive Pythagorean quadruples.

To prove this we need the following lemma: (Lemma 1) If w² + x² + y² = z², and each of w, x, y, and z is positive, then one of the following holds:
w + x > z, w + y > z, x + y > z, or two of the w, x, y coordinates are equal to 0.

Proof of Lemma: Suppose 0 <= w <= x <= y.  This means that w² <= xy.  Therefore 2w² <= 2xy. Adding x² + y² to both sides gives z² + w² = 2w² + x² + y² <= 2xy + x² + y² = (x + y)².  This means that x + y >= z, with equality only if w=x=0.

Proof of Theorem: Suppose (W, X, Y, Z) is the first (the one with smallest positive z) all-positive primitive Pythagorean quadruple that is not generated by this method which has W <= X <= Y.   Since all the W, X, Y are non-zero, we know from the lemma that X + Y > Z.  But this means that if (W', X', Y', Z')^T = L1 (W, X, Y, Z)^T then Z' = 3Z - 2X - 2Y < Z.  So that means we were able to generate this quadruple using L1 from the previous quadruples, since L1 * L1 = the identity matrix.

==================================

Pythagorean Quintuples by Matrices

==================================

By a similar process (using matrices

     [1 0 0]   [1 0  0  0  0]
L2 = [0 1 0] = [0 1  0  0  0]
     [0 0 L]   [0 0 -1 -2  2]
               [0 0 -2 -1  2]
               [0 0 -2 -2  3]

S1, S2, S3, S4, S5, R12, R13, R14, R23, R24, R34)

you can get all primitive Pythagorean quintuples starting with tuples (1, 0, 0, 0, 1) and (1, 1, 1, 1, 2).

The proof hinges on the following lemma:  Suppose v² + w² + x² + y² = z² and v <= w <= x <= y.  Then x + y >= z with equality only if v=w=x=y or v=w=x=0.

Sketch of proof of Lemma:  Note that v² + w² <= 2xy and add x² + y² to both sides.

=======================================================

Second Stab at Pythagorean Quadruples by a Matrix Method

=======================================================

We use x₁² + x₂² + x₃² = z² in this section.

From H. Anders Lonnemo (private communication) we use the matrix K generated by the following transformation

q  = (x₁ + x₂ + x₃ - z) / 2
m₁ = x₁ - q
m₂ = x₂ - q
m₃ = x₃ - q
q' = -q
x₁'= q' + m₁ 
x₂'= q' + m₂
x₃'= q' + m₃ 
z' = q' + m₁ + m₂ + m₃

This transformation can be shortened to

t  = z - (x₁ + x₂ + x₃)
x₁'= t + x₁ 
x₂'= t + x₂
x₃'= t + x₃
z' = t + z.

We call the matrix that does this transformation K.

Notes:

1. Let (x1', x2', x3', z') = K(x1, x2, x3, z).  If (x1, x2, x3, z) is a primitive Pythagorean quadruple then so is (x1', x2', x3', z').  To prove this use substitution of the new coordinates into x₁² + x₂² + x₃² = z^2, and also note that the GCD of the original quadruple is the GCD of the manufactured one.

2. Note that K*K = the identity matrix.

3. Note that if x1, x2, x3, z are all positive then (x1', x2', x3', z') = K(x1, x2, x3, z) has z' < z.

Theorem: Starting with (1, 0, 0, 1), (0, 1, 0, 1), and (0, 0, 1, 1) and using K and S1, S2, S3, and S4 which are the matrices that induce sign changes on the appropriate coordinate, we can generate all primitive Pythagorean quadruples.  I think it also generates them uniquely.

==========================================

Quadratic Functions on this Transformation

==========================================

Let f(x) = ax² + bx + c, and

x₁= q + m₁ 
x₂= q + m₂
x₃= q + m₃  
z = q + m₁ + m₂ + m₃.

Then f(x₁) + f(x₂) + f(x₃) = f(z) if and only if 2f(q) = m₁m₂ + m₁m₃ + m₂m₃

Note that if b=0 (if there is no linear term to the quadratic function f) you can do the same transformation as in the previous section substituting -q for q, and get a perfectly good quadruple that satisfies f(x₁) + f(x₂) + f(x₃) = f(z).

========================================

Pythagorean 10-tuples by a Matrix Method

========================================

We use x₁² + x₂² + ... + x₉² = z² in this section.

Let I(6x6) be the 6x6 matrix that is the identity matrix, and K be the matrix mentioned above as the 4x4 transformation matrix that brings a Pythagorean quadruple into a new quadruple as per the transformation discussed above.

Let K1 = [I(6x6) 0     ]
         [0      K(4x4)]

Suppose x₁² + x₂² + ... + x₉² = z² . Let f(t) = t² + (x₁² + x₂² + ... + x₆²)/2 and

x₇= q + m₁
x₈= q + m₂
x₉= q + m₃ 
z = q + m₁ + m₂ + m₃.

Then f(x₇) + f(x₈) + f(x₉) = f(z).  But this is true if and only if 2f(q) = m₁m₂ + m₁m₃ + m₂m₃.  But then if we apply K to (x₇, x₈, x₉, z) we get a new quadruple that satisfies f(x₇) + f(x₈) + f(x₉) = f(z) by the previous section.  But then K1(x₁, ... , x₉, z)^T is a new Pythagorean 10-tuple.

Notes:

1. K1 * K1 = the identity matrix.

2. K1 maps primitive Pythagorean 10-tuples into primitive Pythagorean 10-tuples.

Theorem: If all the coordinates are positive, and unless all the coordinates except the hypotenuse are equal or all but one are equal to 0, then z' < z, where z' is the hypotenuse of the mapping and z is the hypotenuse of the original. 

The proof of this depends upon the following lemma: If x₁² + x₂² + ... + x₉² = z² and 0 <= x₁ <= x₂ <= ... <= x₉, then x₇ + x₈ + x₉ >= h, with equality only if all x's are 0 except x₉ or if all x's are equal.

Proof of Lemma:  Suppose x₁² + x₂² + ... + x₉² = z² and 0 <= x₁ <= x₂ <= ... <= x₉. Then x₁² + x₂² + ... + x₆² <= 2x₇x₈ + 2x₇x₉ + 2x₈x₉ .  Adding the sum of the last three squares gives x₁² + x₂² + ... + x₉² = z² <= (x₇ + x₈ + x₉)².  You get equality only if all x's are 0 except x₉ or if all x's are equal.

Proof of Theorem: Suppose x₁² + x₂² + ... + x₉² = z² and 0 <= x₁ <= x₂ <= ... <= x₉. Further suppose that more than one of the x's are nonzero and that the x's are not all equal. Then from the lemma we know x₇ + x₈ + x₉ > h.  Using the transformation by K1, which is the transformation on K on the last four coordinates, which has been shortened above to

t  = z - (x₇ + x₈ + x₉)
x₇'= t + x₇ 
x₈'= t + x₈
x₉'= t + x₉
z' = t + z 

we can see that z' < z exactly when t is negative, which occurs since x₇ + x₈ + x₉ > h.

Theorem: Starting with 10-tuples (1, 0, 0, 0, 0, 0, 0, 0, 0, 1) and (1, 1, 1, 1, 1, 1, 1, 1, 1, 3) and using the matrix K1, and the matrices that change the sign of each coordinate, and the matrices that swap each coordinate except for the last (hypotenuse) coordinate, we can generate all primitive Pythagorean 10-tuples.

========================

Comments or Questions about this site should be sent to pythagorean_tuples@yahoo.com