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

Explore posts in the same categories: Problem solving

This entry was posted on May 5, 2010 at 18:05 and is filed under Problem solving. You can subscribe via RSS 2.0 feed to this post's comments.

Tags: IMC, Math competitions, Problem solving

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

15 Comments on “IMC09 problem 2”

gowers Says:

May 6, 2010 at 17:43
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.

Reply
- Sune Kristian Jakobsen Says:
  
  May 6, 2010 at 18:18
  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:
  
  May 7, 2010 at 15:31
  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.
- George Lowther Says:
  
  June 27, 2010 at 21:30
  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).
ks Says:

May 11, 2010 at 19:36
i am going to try to solve if $(a-b)c = ba^{-1}$ then $c(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.

Reply
Michael Nielsen Says:

May 12, 2010 at 21:53
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.

Reply
Rod Carvalho Says:

May 22, 2010 at 06:06
Hej Sune!! Great to see you starting a blog :-) I will be following your posts with interest.

Reply
A solution to IMC09 problem 2 « Absolutely useless Says:

September 25, 2011 at 10:34
[…] 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 […]

Reply
homesecuritydeals.com Says:

June 5, 2013 at 19:42
Way cool! Some very valid points! I appreciate you penning this write-up plus the rest of the site is really
good.

Reply
chiropractor back pain Says:

June 24, 2013 at 00:39
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!

Reply
http://www.radioviveonline.com Says:

July 8, 2013 at 16:44
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.

Reply
Carb Back Loading Results Says:

August 2, 2013 at 21:26
Bobbi Leder: Did you take any supplements or
protein shakes? Females’s Wellness.

Reply
tag removal skin Says:

August 3, 2013 at 03:55
There are variousmoles and wart removalmethods that can be employed to safely and practically painlessly eliminate
these undesired skin indentations.

Reply
Roma Says:

August 3, 2013 at 06:08
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.

Reply
http://kangplan.com/ Says:

June 29, 2014 at 19:04
Quality posts is the secret to attract the visitors to go to see the web page, that’s what this web page is providing.

Reply