IMC09 problem 2

For a couple of years I have thought about starting a mathematical blog, but I decided not to, because I thought I didn’t have enough time and ideas to keep a high enough post rate. But now and then I have something I want to say, and no place to say it, so I have finally decided to start this blog anyway, but also that I won’t have to post something every month.

This post and the next are partly inspired by these two posts by Gowers, where he tries to explore how people think when they do math, by asking his readers to solve a very simple equation, and explain how they solved it. In this and my next post I will consider a more difficult problem: It is problem 2 from IMC09 (IMC, International Mathematics Competition, is a math completion for university students). The reason I’m using an IMC-problem is that University of Copenhagen is going to participate in IMC for the first time this year, and I hope that talking about how we solve problems will be a good preparation for the contest both for me and for the rest of the team. Still, I hope that this discussion will be of interest to both IMO contestants and to professional mathematicians.

I solved this problem about two months ago, but I thought a lot about what problem solving strategies I used, so I still remember most of my thoughts. I have chosen to write about this particular problem because I noticed that I used many general problem solving strategies, that are good to know. You are welcome to post your thoughts on the problem in a comment, even if you haven’t solved the problem. If you have solved the problem, please try to describe the whole thought process, not just the thoughts that led you to the solution. I will post a description of how I solved it in a couple of days.

The problem is:
Let A, B, and C be real square matrices of the same size, and suppose that A is invertible. Prove that if (A-B)C=BA^{-1} then C(A-B)=A^{-1} B.

Advertisements
Explore posts in the same categories: Problem solving

Tags: , ,

You can comment below, or link to this permanent URL from your own site.

16 Comments on “IMC09 problem 2”

  1. gowers Says:

    Great to see you starting up a blog, whether or not posts turn out to be only occasional.

    I think I’ve just solved the problem, almost certainly not by the best method, and I don’t feel I fully understand it. Also, I don’t know whether I can remember my thought processes all that well.

    My overriding thought to start with was, “This can’t be true — it seems to contradict the fact that matrices commute.” Of course, I knew that wasn’t really the case, but it was still a useful thought, since it indicated that there was something I didn’t understand and should sort out first. So I focused on trying to produce a counterexample.

    I decided that I preferred to do a substitution and replace A-B by A and A by A+B. At some stage I realized that by doing this I now knew not that A was invertible but that A+B was. In any case, the two equations now read

    AC = B(A+B)^{-1}

    and

    CA = (A+B)^{-1}B.

    I then thought it would be nicer if I could “take the reciprocal of both sides” so that A+B would be “on the top”. But I wasn’t guaranteed invertibility everywhere.

    At that point I fell back on a “cheat” that I know: assume that everything is invertible, prove the statement in that case, and then use the fact that every matrix is a limit of invertible matrices to deduce it in the general case. Luckily you said that the matrices were real …

    So that got me to

    C^{-1}A^{-1} = (A+B)B^{-1}

    and

    A^{-1}C^{-1} = B^{-1}(A+B),

    and simplifying I reached

    C^{-1}A^{-1} = AB^{-1} + I

    and

    A^{-1}C^{-1} = B^{-1}A + I.

    I then thought, “Surely I can contradict this by just solving for B in the first equation,” before realizing that that didn’t prove the result false: perhaps when I substituted the answer into the second equation I would get 0=0 rather than a contradiction. This seemed worth trying.

    I didn’t actually do this, but now I think I’ll make things nicer by renaming all the matrices by what their inverses used to be called. So now the two equations are

    CA = A^{-1}B + I

    and

    AC = BA^{-1} + I.

    Solving the first for B gives B=A(CA-I). Substituting that into the right-hand side of the second gives us A(CA-I)A^{-1}+I, which equals AC-I+I=AC. But that’s exactly what it is supposed to equal. Since B had to be what it was from the first equation, this seems to be a proof. (I don’t quite completely rule out the possibility of having made a mistake.)

    An interesting aspect of this thought process is that I did quite a lot of those substitutions without any clear idea of where I was going — I just wanted the problem to feel simpler. And also I was guided by an intuition that I knew to be wrong.


    • Assuming that everything is invertible, and then using a limit argument is an nice trick. I too assumed that everything was invertible when I started to think about the problem, but this was only to get an idea of what a proof could look like. When I had found a proof that worked for invertible matrices, I modified it, to make it work in the general case.

    • gowers Says:

      I have known that limiting-argument trick ever since someone showed me the following proof of the Cayley-Hamilton theorem. It is trivially true for diagonal matrices, and therefore true for diagonalizable matrices. But every matrix is a limit of diagonalizable matrices, so we are done.

      A disadvantage of the proof is that it doesn’t obviously work if your matrices are over a finite field.


    • gowers – but, the Cayley-Hamilton theorem is just a polynomial identity with integer coefficients (and indeterminates being the matrix elements). If it holds over the rationals then it has to hold over *every* field (in fact, every commutative ring).

  2. ks Says:

    i am going to try to solve if (a-b)c = ba^{-1} thenc(a-b)=a^{-1}b before reading your solution
    method. solving (a-b)c = ba^{-1} for c
    i get c = x + y c where
    x = a^{-1}ba^{-1}, y = a^{-1}b. note that xa = y, xb = y^2. expanding c = x + yc recursively we find that c = x + yx + y^2x + \ldots with the big assumption that the series converges ca = y + y^2 +\ldots and
    cb = y^2 + y^3 + \ldots so ca - cb is then y which is what we needed to show.

    i have to think about the convergence of the series.


  3. I started with a completely wrong idea: I decided to start with the idea that C was invertible — such assumptions can often be fixed later — and to premultiply the equation (A-B)C = BA^{-1} by C and postmultiply by C^{-1} to get:

    C(A-B) = CBA^{-1} C^{-1}

    I had no idea how to get the right hand side into the correct form, so I decided to start over with another idea, writing D = B-A, and then removing B from the picture, using B = D+A. I did this rather instinctively and it was perhaps somewhat lucky – it’s only with the benefit of hindsight that this is a good idea. The equation (A-B)C = BA^{-1} becomes:

    -DC = I + D A^{-1}

    which I realized meant

    -D(C+A^{-1}) = I

    At this point I was sure the problem would drop out, because matrices commute with their inverses. Actually, a slightly more accurate way of saying it is that I put the equation in this form because I saw the “I” appear in the equation and got excited, realizing that it would likely let me use the surprisingly useful identity X X^{-1} = X^{-1} X.

    Everything is simple now. The same ideas show that the equation to be derived is equivalent to -(C+A^{-1})D = I, and so the result follows.

    A “cleaned up” solution is as follows:

    Define D := B-A. Then a substitution and rearrangement shows that(A-B)C = BA^{-1} is equivalent to -D(C+A^{-1}) = I, and thus -D and C+A^{-1} are inverses matrices of one another. A similar substitution and rearrangement shows that the equation to derived is equivalent to -(C+A^{-1})D = I, which is equivalent to -D and (C+A^{-1}) being inverses. QED

    I’m pretty sure that with a bit of thought it’d be possible to see through what’s going on here, but I can’t say I quite understand it.

  4. Rod Carvalho Says:

    Hej Sune!! Great to see you starting a blog 🙂 I will be following your posts with interest.


  5. […] this assumption, we have to do something else. (We could use a limit argument, like Gowers did in a comment to my last post, but I didn’t think of this trick when I solved the […]


  6. Way cool! Some very valid points! I appreciate you penning this write-up plus the rest of the site is really
    good.


  7. Woah! I’m really digging the template/theme of this blog. It’s simple, yet effective.
    A lot of times it’s very difficult to get that “perfect balance” between superb usability and appearance. I must say that you’ve done
    a great job with this. Additionally, the blog loads extremely
    fast for me on Opera. Excellent Blog!


  8. I think the admin of this web page is in fact working hard in favor of his web site, since
    here every information is quality based data.


  9. Bobbi Leder: Did you take any supplements or
    protein shakes? Females’s Wellness.


  10. There are variousmoles and wart removalmethods that can be employed to safely and practically painlessly eliminate
    these undesired skin indentations.

  11. Roma Says:

    Aside from the protein, eggs also have a wholesome reserve of Omega 3 fatty acids, which is very good for the heart
    and boosts power levels.


  12. Quality posts is the secret to attract the visitors to go to see the web page, that’s what this web page is providing.

  13. Norman Meatel Says:

    To solve this problem you need to observe that it is a problem of commutation: The first identity is (A-B)C and the second is C(A-B).
    To solve this problem you need to add and subtract 1 to the right
    hand side of both identities:
    (A-B)C = B A^-1 -AA^-1 +1
    C(A-B) = A^-1B -A^-1A +1
    Then factorize A-B oi the left had side
    you get:
    (A-B)(C+A^-1) =1
    (C+A^-1)(A-B) =1
    CQFD


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: