# Show matrix $A+5B$ has an inverse with integer entries given the following conditions

Let $A$ and $B$ be 2×2 matrices with integer entries such that each of $A$, $A + B$, $A + 2B$, $A + 3B$, $A + 4B$ has an inverse with integer entries. Show that the same is true for $A + 5B$.

-
This is problem A4 from the 55th Putnam Exam (1994). You can find a solution here: math.niu.edu/~rusin/problems-math/putnam.94 –  Byron Schmuland Jul 26 '12 at 18:48
@Byron What a coincidence. You posted the link precisely $2$ secs after I posted my answer! Also, the answer given there is essentially the same as mine. Such properties of polynomials are frequently used to devise competition problems. But there are only so many ways one can attempt to disguise them... –  Bill Dubuque Jul 26 '12 at 19:11
@BillDubuque You were impressively quick! –  Byron Schmuland Jul 26 '12 at 19:42

First note that a matrix $X$ with integer entries is invertible and its inverse has integer entries if and only if $\det(X)=\pm1$.

Let $P(x)=\det(A+xB)$. Then $P(x)$ is a polynomial of degree at most $4$, with integer coefficients, and $P(0),P(1),P(2),P(3),P(4) \in \{ \pm 1 \}$.

Claim: $P(0)=P(1)=P(3)=P(4)$.

Proof: It is known that $b-a|P(b)-P(a)$ for $a,b$ integers.

Then $3|P(4)-P(1), 3|P(3)-P(0)$ and $4|P(4)-P(0)$. Since the RHS of each division is $0$ or $\pm 2$, it follows it is zero. This proves the claim.

Now, $P(x)-P(0)$ is a polynomial of degree at most four which has the roots $0,1,3,4$. Thus

$$P(x)-P(0)=ax(x-1)(x-3)(x-4) \,.$$

hence $P(2)=P(0)-4a$. Since $P(2), P(0) \in \{ \pm 1 \}$, it follows that $a=0$, and hence $P(x)$ is the constant polynomial $1$ or $-1$.

Extra One can actually deduce further from here that $\det(A)=\pm 1$ and $A^{-1}B$ is nilpotenet.

Indeed $A$ is invertible and since $\det(A+xB)=\det(A)\det(I+xA^{-1}B)$ you get from here that $\det(I+xA^{-1}B)=1$. It is trivial to deduce next that the characteristic polynomial of $A^{-1}B$ is $x^2$.

-

Hint $\rm\:det(A\!+\!xB)\:$ is a quadratic polynomial with value $\pm1$ at $5$ points so it has value $1$ or $-1$ at $3$ points, so the polynomial must be constant, either $1$ or $-1,\:$ so $\rm\:A\!+\!xB\:$ has integer inverse for all $\rm\:x.$

-
I missed the obvious, LOL. I think my solution then works for matrices up to 4 by 4 :) –  N. S. Jul 26 '12 at 18:53