3 ms·

Consider 1.4.13c: Find 2x2 matrices such that CD = -DC, not allowing the case CD = 0. Of course one can just take a shotgun approach, i.e. come up with some

by gruseom 15y ago

Consider 1.4.13c: Find 2x2 matrices such that CD = -DC, not allowing the case CD = 0. Of course one can just take a shotgun approach, i.e. come up with some arbitrary possibilities and then manipulate their elements individually until the equation holds. But what's more interesting is to view the matrices as operations on columns or rows, come up with operations that have the desired effect, then encode them as matrices to answer the question. What such ways are there to look at this little problem?

nialo 15y ago
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 :)
- gruseom 15y ago
  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!
  - nialo 15y ago
    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.
    - gruseom 15y ago
      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.
impendia 15y ago
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.
- gruseom 15y ago
  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.
  - impendia 15y ago
    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 ;)
    - gruseom 15y ago
      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 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.
      - impendia 15y ago
        It's elegant, but as far as I can see, your argument only holds for the single matrix C which you describe.

by gruseom 15y ago

nialo 15y ago

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

gruseom 15y ago
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!
- nialo 15y ago
  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.
  - gruseom 15y ago
    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.

impendia 15y ago

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.

gruseom 15y ago
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.
- impendia 15y ago
  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 ;)
  - gruseom 15y ago
    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 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.
    - impendia 15y ago
      It's elegant, but as far as I can see, your argument only holds for the single matrix C which you describe.