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,
    A+kB
    Is also invertible with integer enties for any integer k.

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

    StatusX

    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

    StatusX

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

Have something to add?



Similar Discussions: Hard matrix prob
  1. Prob. question (Replies: 3)

  2. Math prob (Replies: 4)

  3. Current prob (Replies: 1)

Loading...