Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Hard matrix prob

  1. Jul 1, 2007 #1
    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,
    Is also invertible with integer enties for any integer k.

    who the heck do you solve this?
  2. jcsd
  3. Jul 1, 2007 #2


    User Avatar
    Homework Helper

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


    User Avatar
    Homework Helper

    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.
  6. Jul 2, 2007 #5

    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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Threads - Hard matrix prob Date
Very hard problems about work May 24, 2015
Evaluating the Svein-Graham Sum Apr 28, 2015
Solving for a variable. Hard to do in this simple equation. Feb 4, 2015
Hard half life equation Jul 7, 2014