# Hard matrix prob

1. Jul 1, 2007

### barbiemathgurl

i just cant figure this out.

given a n x n matrix (with n>1) "A" such that all entries are integers and A is invertible such that A^{-1} also has integer entries. Let B be another matrix with integer coefficients so that:
A+B, A+2B, A+3B, ... A+(n^2)B
Are all invertible with integer entries.

Show that,
A+kB
Is also invertible with integer enties for any integer k.

who the heck do you solve this?

2. Jul 1, 2007

### StatusX

What can you say about the determinants of those matrices? Once you get this, use the fact that det(A+kB), with A,B known and k a variable, is a polynomial in k.

3. Jul 1, 2007

### Kummer

Let M be an arbitrary square invertible matrix whose inverse and itself has integer entires. Then $$1=\det (MM^{-1}) = \det(M)\det (M^{-1})$$ shows that $$\det (M) = \pm 1$$ because the determinant of this matrix must be an integer. Now define the function $$f(x) = \det (A+xB)$$. This is a polyomial of at most $$n$$ degree. Notice that $$f(0),f(1),f(2),...,f(n^2)$$ are either $$1 \mbox{ or }-1$$. By the strong form of the Pigeonhole Principle at least $$n+1$$ of them are either $$1$$ or $$-1$$. Without lose of generality say its $$1$$. That means $$f(x)$$ must in fact be a constant polynomial because a polynomial of at most $$n$$ degree cannot produce the same values for $$n+1$$ different values. So $$f(x)=1$$. That means $$f(k)=1$$ for no matter what $$k$$. So $$\det (A+kB)=1$$. Since the determinant is 1, it must mean the matrix is irreducible with integer coefficients (by the adjoint matrix formula).

4. Jul 2, 2007

### StatusX

Kummer, we try not to give complete solutions here, just hints. And incidentally, a slightly easier way to get the last step is to note that f(k)^2 is a polynomial of degreen n^2 which is 1 at n^2+1 points, so must be 1 identically, and so f(k)=+-1. Also it remains to show that all integer matrices with determinant +-1 are invertible with integer entries.

5. Jul 2, 2007

### Kummer

Okay.

Last line in my first post in paranthesis. I was being sloppy on that last line because I assumed that result was trivial. I should have been more explicit.