One way is to view this as a geometry problem, 2d for convenience: a column represents a point in the plane, and matrices are transformations that can be applied to that point. Then the problem becomes, find a pair of transformations such that the point ends up in two opposite locations if the transformations are applied in different order.

a solution, under rot13: n ersyrpgvba naq ebgngvba jbexf, V guvax ol naq nobhg nal natyr gung vfa'g avargl qrterrf be nal nkvf gung vfa'g gur k be l nkvf.

I'd be interested in an explanation for exactly why the exceptions to my solution don't work, I don't really understand why they shouldn't.

I read this this morning and haven't been able to get the problem out of my head since, glad this thread exists :)

That's exactly the sort of interpretation I was looking for. I don't remember how to represent geometrical transformations as matrices, but that's really just a technical detail; one can understand your solution without it. That being said, I still don't understand your solution. Are you saying that any such pair of transformations as you describe has the desired anticommutative property, except for the exceptions? I don't see either part of that - the general claim or the exceptions.

My solution exploits the fact that in CD, C combines the rows of D, while in DC, C combines the columns of D. Here's the rest:

Yrg P or gur vqragvgl zngevk rkprcg jvgu -1 nf vgf obggbz-evtug ryrzrag. Gura PQ vf Q jvgu vgf obggbz ebj artngrq. Fvzvyneyl, QP vf Q jvgu vgf evtug pbyhza artngrq naq -QP vf Q jvgu vgf yrsg pbyhza artngrq. Fb gb trg PQ = -QP, jr whfg arrq gb svaq n Q fhpu gung artngvat vgf obggbz ebj unf gur fnzr rssrpg nf artngvat vgf yrsg pbyhza. Sbe 2k2 zngevprf, guvf vf nal Q jvgu mreb va gur gbc-yrsg naq obggbz-evtug cbfvgvbaf.

Rot13 don't work so good for specifying matrices!

I apparently entered my test cases wrong in lots of interesting ways. I think I've actually found essentially the same solution you have, it turns out I had the exceptions and the actual solution backwards:

n avargl qrterr ebgngvba naq n ersyrpgvba nobhg, nf sne nf V pna gryy nal, yvar guebhtu gur bevtva frrzf gb tvir gur evtug erfhyg.

Are we sure this is the correct meaning for "A = -B", where A and B are matrices? Some things I've read seem to be saying that that should be equivalent to AB = identity matrix, rather than Av = -1(Bv), where v is some vector.

It's the correct meaning, as indicated by the solution on p. 430. You're thinking not of -B but of the inverse of B, which is denoted B^-1 ("B to the power of -1") and when multiplied by B gives I.

There is a brute force solution, you get equations in eight variables (the matrix entries) which you can solve. Not elegant, but it works.

Also, WLOG (without loss of generality) the top left entry of C and D is either 0 or 1, because you can multiply either matrix by any number other than 0 without changing whether the equation is true.

Right, the brute force way is better than sheer guesswork, but it's still too low-level. Kind of like solving the problem in assembly language. The intention of the text is clearly to get one thinking about these operations at a higher level, "at the level of the problem" as we would say in software.

Your WLOG is elegant, though, in that it gives a simpler starting point that's guaranteed to work if anything does. I'll have to remember that trick.

I feel like there is unlikely to be a solution which doesn't involve (1) brute force, or (2) higher-level theory (i.e. eigenvectors and eigenvalues).

Prove me wrong, and I will be tripping over myself to upvote you ;)

Certainly it's artificial to restrict oneself to primitive concepts, unless of course you don't know about eigenvalues yet or forgot it all. :) And it is an exercise from the earliest chapter, so we're supposed to stay in simple-land.

Did you look at my solution (http://news.ycombinator.com/item?id=3129023)? There's no higher-level theory in it. Is it brute force? Not sure. At least it doesn't require solving any element-wise equations.

It's elegant, but as far as I can see, your argument only holds for the single matrix C which you describe.

Oh, absolutely. The exercise is to construct one example.

If you were talking about solving the general case (For any C, find D such that CD = -DC) I can see why you wanted more powerful tools.

oh! that's easier :)