### Putnam 1994

Problem A4

A and B are 2 x 2 matrices with integral values. A, A + B, A + 2B, A + 3B, and A + 4B all have inverses with integral values. Show that A + 5B does also.

Solution

Let A = (aij), B = (bij). Given any matrix C = (cij), C is invertible iff the determinant d = c11c22 - c12c21 is non-zero and the inverse is then (dij) where d11 = c22/d, d12 = -c12/d, d21 = -c21/d, d22 = c11/d. Thus if the inverse has integer entries, then d divides all the entries in the original matrix and hence d2 divides d, so d = 1 or -1.

Multiplying out, we find that det(A + nB) = a + nh + n2k, where a = det A = 1 or -1, h = (a11b22 - a12b21 - a21b12 + a22b11), and k = det B. Since A + B has integral entries, a + h + k = 1 or -1 (1). Similarly, A + 2B has integral entries, so a + 2h + 4k = 1 or -1 (2). We find that the only solutions to (1) and (2) are a, h, k = 1,0,0; 1,1,-1; 1,-3,1; 1,-4,2; -1,0,0; -1,-1,1; -1,3,-1; -1,4,-2 (*).

But A + 3B also has integral entries, so in the same way we conclude that a + 3h + 9k = 1 or -1 and hence h + 5k = 0, 2, or -2 (3). The only solutions (*) which also satisfy (3) are 1,0,0 and -1,0,0. Hence det(A + nB) = det A for all n, and so A + nB is invertible and has integer entries for all integers n.

Note that we do not need to use A + 4B. Note also that the fact of integer entries is essential. It is easy to find counter-examples with non-integer entries, eg take a11 = 4, a12 = a21 = 0, a22 = 1, and b11 = -1, b12 = b21 = b22 = 0.

On reflection, the reason for including A + 4B was probably to allow the following simpler solution: a + hn + kn2 takes the values 1 or -1 for the 5 values n = 0, 1, 2, 3, 4. Hence it must take one value at least 3 times. But that is impossible for a quadratic unless it is constant. Hence it is constant. Then as before.