Hacker News Reader

Comment by nialo | Hacker News Reader

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 :)

View on HN

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.

Reply on news.ycombinator.com