Solving Hard Matrix Prob: A+kB Invertible w/ Integer Entries

[barbiemathgurl]

i just can't 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?

 

[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.

 

[Kummer]

i just can't 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?

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).

 

[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.

 

[Kummer]

Kummer, we try not to give complete solutions here, just hints.

Okay.

Also it remains to show that all integer matrices with determinant +-1 are invertible with integer entries.

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.