[math-fun] N-dimensional rotation matrix decomposition
I have a question about a particular type of decomposition of N-dimensional rotation matrices. The specific types of matrices I am considering are orthogonal matrices (the rows form a set of orthogonal unit vectors, as do the columns). Further, I am only considering the case where the determinant is 1 (as opposed to -1). I.e., I am disallowing reflections. I am interested in factoring such a matrix into a sequence of "primitive rotations" (I'm not sure what the proper term is). By this I mean rotations which only affect two coordinate axes. This defines a rotation within a plane, with the restriction that the plane be the product of two of the standard coordinate axes. For an N-dimensional matrix, there are (N take 2) = N*(N-1)/2 possible pairs of axes. For example, in 3 dimensions they are XY, XZ, and YZ. Any such rotation matrix, as defined above, can be factored into a sequence of N*(N-1)/2 primitive rotations, which each pair of axes occurring exactly once. I know certain orderings will work. One such ordering is to first perform all rotations involving some particular axis, then perform all remaining rotations involving some other particular axis, etc. For instance, in 4 dimensions, the sequence could be (a1,a2), (a1,a3), (a1,a4), (a2,a3), (a2,a4), (a3,a4). The opposite ordering can easily be shown to work as well, i.e. (a3,a4), (a2,a4), (a2,a3), (a1,a4), (a1,a3), (a1,a2). My question is this: Can *any* fixed ordering be made to work, for any such rotation matrix? Or do only some orderings work? Some observations: There are a number of transformations that can be performed on any ordering to produce a new ordering which will work. In some cases the rotation amounts can be preserved. In others, the rotation amounts need to change. Here's an example of a transformation that works in 4 dimensions: (a1,a2), (a1,a3), (a2,a3), (a1,a4), (a2,a4), (a3,a4) Here I have have swapped adjacent primitive rotations (a1,a4) and (a2,a3). This can always be done, without changing the rotation amounts, since they have no coordinates in common. But what about the case where they do have a coordinate in common? In three dimensions, we know that any order works, so XY, XZ, YZ works, and so does XY, YZ, XZ, although when switching from one to the other, in general all *three* rotation amounts must be changed. Does anyone know the answer to this? In N dimensions, will any fixed ordering work? Or do only some fixed orderings work? Tom
On 12/03/2016 00:15, Tom Karzes wrote:
I have a question about a particular type of decomposition of N-dimensional rotation matrices. The specific types of matrices I am considering are orthogonal matrices (the rows form a set of orthogonal unit vectors, as do the columns). Further, I am only considering the case where the determinant is 1 (as opposed to -1). I.e., I am disallowing reflections.
I am interested in factoring such a matrix into a sequence of "primitive rotations" (I'm not sure what the proper term is). By this I mean rotations which only affect two coordinate axes. This defines a rotation within a plane, with the restriction that the plane be the product of two of the standard coordinate axes.
The usual term is "Givens rotation". (I don't know the answer to your question about what orderings of axis-pairs "work".) -- g
Thanks Gareth. It does indeed sound like a "Givens rotation" is the term I was looking for for what I was calling a "primitive rotation". Tom Gareth McCaughan writes:
On 12/03/2016 00:15, Tom Karzes wrote:
I have a question about a particular type of decomposition of N-dimensional rotation matrices. The specific types of matrices I am considering are orthogonal matrices (the rows form a set of orthogonal unit vectors, as do the columns). Further, I am only considering the case where the determinant is 1 (as opposed to -1). I.e., I am disallowing reflections.
I am interested in factoring such a matrix into a sequence of "primitive rotations" (I'm not sure what the proper term is). By this I mean rotations which only affect two coordinate axes. This defines a rotation within a plane, with the restriction that the plane be the product of two of the standard coordinate axes.
The usual term is "Givens rotation".
(I don't know the answer to your question about what orderings of axis-pairs "work".)
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
For every rotation F: R^n —> R^n, there is a decomposition of R^n into floor(n/2) orthogonal 2-planes that are each invariant under F. And if n is odd, an additional orthogonal R^1 that is fixed under F. I think this is proved by first showing it for n = 2k, where F is a special case of an element of SU(k) on C^k. —Dan
On Mar 11, 2016, at 4:15 PM, Tom Karzes <karzes@sonic.net> wrote:
I have a question about a particular type of decomposition of N-dimensional rotation matrices. The specific types of matrices I am considering are orthogonal matrices (the rows form a set of orthogonal unit vectors, as do the columns). Further, I am only considering the case where the determinant is 1 (as opposed to -1). I.e., I am disallowing reflections.
I am interested in factoring such a matrix into a sequence of "primitive rotations" (I'm not sure what the proper term is). By this I mean rotations which only affect two coordinate axes. This defines a rotation within a plane, with the restriction that the plane be the product of two of the standard coordinate axes.
For an N-dimensional matrix, there are (N take 2) = N*(N-1)/2 possible pairs of axes. For example, in 3 dimensions they are XY, XZ, and YZ.
Any such rotation matrix, as defined above, can be factored into a sequence of N*(N-1)/2 primitive rotations, which each pair of axes occurring exactly once.
I know certain orderings will work. One such ordering is to first perform all rotations involving some particular axis, then perform all remaining rotations involving some other particular axis, etc. For instance, in 4 dimensions, the sequence could be (a1,a2), (a1,a3), (a1,a4), (a2,a3), (a2,a4), (a3,a4).
The opposite ordering can easily be shown to work as well, i.e. (a3,a4), (a2,a4), (a2,a3), (a1,a4), (a1,a3), (a1,a2).
My question is this: Can *any* fixed ordering be made to work, for any such rotation matrix? Or do only some orderings work?
Some observations:
There are a number of transformations that can be performed on any ordering to produce a new ordering which will work. In some cases the rotation amounts can be preserved. In others, the rotation amounts need to change.
Here's an example of a transformation that works in 4 dimensions:
(a1,a2), (a1,a3), (a2,a3), (a1,a4), (a2,a4), (a3,a4)
Here I have have swapped adjacent primitive rotations (a1,a4) and (a2,a3). This can always be done, without changing the rotation amounts, since they have no coordinates in common. But what about the case where they do have a coordinate in common?
In three dimensions, we know that any order works, so XY, XZ, YZ works, and so does XY, YZ, XZ, although when switching from one to the other, in general all *three* rotation amounts must be changed.
Does anyone know the answer to this? In N dimensions, will any fixed ordering work? Or do only some fixed orderings work?
Tom
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Thanks Dan. It sounds like you're referring to the "Canonical form" of an orthogonal matrix: https://en.wikipedia.org/wiki/Orthogonal_matrix#Canonical_form This addresses the effect of the rotation, ignoring the coordinate system (i.e. it allows you to transform to a different coordinate system, apply the canonical rotation, then transform back). Unfortunately, this does not address the question I asked. When I first asked the question, I assumed it was well-known and that I was merely ignorant of the result. Now, however, I'm beginning to wonder if this is in fact an unresolved research problem? To me it seems like a very basic question, but perhaps that's not the case... Tom Dan Asimov writes:
For every rotation
F: R^n —> R^n,
there is a decomposition of R^n into floor(n/2) orthogonal 2-planes that are each invariant under F. And if n is odd, an additional orthogonal R^1 that is fixed under F.
I think this is proved by first showing it for n = 2k, where F is a special case of an element of SU(k) on C^k.
—Dan
On Mar 11, 2016, at 4:15 PM, Tom Karzes <karzes@sonic.net> wrote:
I have a question about a particular type of decomposition of N-dimensional rotation matrices. The specific types of matrices I am considering are orthogonal matrices (the rows form a set of orthogonal unit vectors, as do the columns). Further, I am only considering the case where the determinant is 1 (as opposed to -1). I.e., I am disallowing reflections.
I am interested in factoring such a matrix into a sequence of "primitive rotations" (I'm not sure what the proper term is). By this I mean rotations which only affect two coordinate axes. This defines a rotation within a plane, with the restriction that the plane be the product of two of the standard coordinate axes.
For an N-dimensional matrix, there are (N take 2) = N*(N-1)/2 possible pairs of axes. For example, in 3 dimensions they are XY, XZ, and YZ.
Any such rotation matrix, as defined above, can be factored into a sequence of N*(N-1)/2 primitive rotations, which each pair of axes occurring exactly once.
I know certain orderings will work. One such ordering is to first perform all rotations involving some particular axis, then perform all remaining rotations involving some other particular axis, etc. For instance, in 4 dimensions, the sequence could be (a1,a2), (a1,a3), (a1,a4), (a2,a3), (a2,a4), (a3,a4).
The opposite ordering can easily be shown to work as well, i.e. (a3,a4), (a2,a4), (a2,a3), (a1,a4), (a1,a3), (a1,a2).
My question is this: Can *any* fixed ordering be made to work, for any such rotation matrix? Or do only some orderings work?
Some observations:
There are a number of transformations that can be performed on any ordering to produce a new ordering which will work. In some cases the rotation amounts can be preserved. In others, the rotation amounts need to change.
Here's an example of a transformation that works in 4 dimensions:
(a1,a2), (a1,a3), (a2,a3), (a1,a4), (a2,a4), (a3,a4)
Here I have have swapped adjacent primitive rotations (a1,a4) and (a2,a3). This can always be done, without changing the rotation amounts, since they have no coordinates in common. But what about the case where they do have a coordinate in common?
In three dimensions, we know that any order works, so XY, XZ, YZ works, and so does XY, YZ, XZ, although when switching from one to the other, in general all *three* rotation amounts must be changed.
Does anyone know the answer to this? In N dimensions, will any fixed ordering work? Or do only some fixed orderings work?
Tom
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Yeah, Tom, I knew it didn't address your question but thought it was an interesting fact about rotations in R^n. Yes, indeed, the Wikipedia page you mention describes this very geometrically cool fact. Which I still find very non-obvious, but also very satisfying. Incidentally, I invented Givens rotations (long after Givens did) to use in the first implementation of the "grand tour" method of rotating n-dimensional data and then projecting it onto the computer screen, creating an animation. See the "Torus Method", p. 7, at http://www.slac.stanford.edu/cgi-wrap/getdoc/slac-pub-3211.pdf. At that time (ca. 1983), I also wondered about your question but never solved it. Since the order(s) of (i, j) that you describe worked, I didn't have a need for other orderings. —Dan
On Mar 11, 2016, at 8:30 PM, Tom Karzes <karzes@sonic.net> wrote:
Thanks Dan. It sounds like you're referring to the "Canonical form" of an orthogonal matrix:
https://en.wikipedia.org/wiki/Orthogonal_matrix#Canonical_form
This addresses the effect of the rotation, ignoring the coordinate system (i.e. it allows you to transform to a different coordinate system, apply the canonical rotation, then transform back). Unfortunately, this does not address the question I asked.
When I first asked the question, I assumed it was well-known and that I was merely ignorant of the result. Now, however, I'm beginning to wonder if this is in fact an unresolved research problem? To me it seems like a very basic question, but perhaps that's not the case...
Tom
Dan Asimov writes:
For every rotation
F: R^n —> R^n,
there is a decomposition of R^n into floor(n/2) orthogonal 2-planes that are each invariant under F. And if n is odd, an additional orthogonal R^1 that is fixed under F.
I think this is proved by first showing it for n = 2k, where F is a special case of an element of SU(k) on C^k.
—Dan
On Mar 11, 2016, at 4:15 PM, Tom Karzes <karzes@sonic.net> wrote:
I have a question about a particular type of decomposition of N-dimensional rotation matrices. The specific types of matrices I am considering are orthogonal matrices (the rows form a set of orthogonal unit vectors, as do the columns). Further, I am only considering the case where the determinant is 1 (as opposed to -1). I.e., I am disallowing reflections.
I am interested in factoring such a matrix into a sequence of "primitive rotations" (I'm not sure what the proper term is). By this I mean rotations which only affect two coordinate axes. This defines a rotation within a plane, with the restriction that the plane be the product of two of the standard coordinate axes.
For an N-dimensional matrix, there are (N take 2) = N*(N-1)/2 possible pairs of axes. For example, in 3 dimensions they are XY, XZ, and YZ.
Any such rotation matrix, as defined above, can be factored into a sequence of N*(N-1)/2 primitive rotations, which each pair of axes occurring exactly once.
I know certain orderings will work. One such ordering is to first perform all rotations involving some particular axis, then perform all remaining rotations involving some other particular axis, etc. For instance, in 4 dimensions, the sequence could be (a1,a2), (a1,a3), (a1,a4), (a2,a3), (a2,a4), (a3,a4).
The opposite ordering can easily be shown to work as well, i.e. (a3,a4), (a2,a4), (a2,a3), (a1,a4), (a1,a3), (a1,a2).
My question is this: Can *any* fixed ordering be made to work, for any such rotation matrix? Or do only some orderings work?
Some observations:
There are a number of transformations that can be performed on any ordering to produce a new ordering which will work. In some cases the rotation amounts can be preserved. In others, the rotation amounts need to change.
Here's an example of a transformation that works in 4 dimensions:
(a1,a2), (a1,a3), (a2,a3), (a1,a4), (a2,a4), (a3,a4)
Here I have have swapped adjacent primitive rotations (a1,a4) and (a2,a3). This can always be done, without changing the rotation amounts, since they have no coordinates in common. But what about the case where they do have a coordinate in common?
In three dimensions, we know that any order works, so XY, XZ, YZ works, and so does XY, YZ, XZ, although when switching from one to the other, in general all *three* rotation amounts must be changed.
Does anyone know the answer to this? In N dimensions, will any fixed ordering work? Or do only some fixed orderings work?
Tom
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I agree Dan, the "canonical form" of an orthogonal matrix is a nice result. In three dimensions, it basically just says that any rotation can be defined as rotation about some one-dimensional axis. To bring it into canonical form, one need merely rotate that axis onto, for instance, the Z axis, confining the rotation to the XY plane. In higher dimensions, it's a little more complicated. I remember you mentioning your work in visualizing N-dimensional data, and your "grand tour" method before. My situation is very similar. I want to specify a sequence of Givens rotations that is capable of supporting universal rotation in N-space, and while it is easy to find such sequences, it is not clear to me whether any such sequence works vs. only some sequences. I don't *need* to know the answer, but I'd like to. Honestly, when I posted this question I thought I'd immediately get several replies saying "Oh, don't you know that? Didn't you take freshman linear algebra?" But it seems like the answer isn't common knowledge after all. I'm honestly wondering if the answer is even known. Seems hard to imagine that it wouldn't be (or at least, that the question wouldn't be well known). Tom Dan Asimov writes:
Yeah, Tom, I knew it didn't address your question but thought it was an interesting fact about rotations in R^n. Yes, indeed, the Wikipedia page you mention describes this very geometrically cool fact. Which I still find very non-obvious, but also very satisfying.
Incidentally, I invented Givens rotations (long after Givens did) to use in the first implementation of the "grand tour" method of rotating n-dimensional data and then projecting it onto the computer screen, creating an animation. See the "Torus Method", p. 7, at http://www.slac.stanford.edu/cgi-wrap/getdoc/slac-pub-3211.pdf.
At that time (ca. 1983), I also wondered about your question but never solved it. Since the order(s) of (i, j) that you describe worked, I didn't have a need for other orderings.
—Dan
On Mar 11, 2016, at 8:30 PM, Tom Karzes <karzes@sonic.net> wrote:
Thanks Dan. It sounds like you're referring to the "Canonical form" of an orthogonal matrix:
https://en.wikipedia.org/wiki/Orthogonal_matrix#Canonical_form
This addresses the effect of the rotation, ignoring the coordinate system (i.e. it allows you to transform to a different coordinate system, apply the canonical rotation, then transform back). Unfortunately, this does not address the question I asked.
When I first asked the question, I assumed it was well-known and that I was merely ignorant of the result. Now, however, I'm beginning to wonder if this is in fact an unresolved research problem? To me it seems like a very basic question, but perhaps that's not the case...
Tom
Dan Asimov writes:
For every rotation
F: R^n —> R^n,
there is a decomposition of R^n into floor(n/2) orthogonal 2-planes that are each invariant under F. And if n is odd, an additional orthogonal R^1 that is fixed under F.
I think this is proved by first showing it for n = 2k, where F is a special case of an element of SU(k) on C^k.
—Dan
On Mar 11, 2016, at 4:15 PM, Tom Karzes <karzes@sonic.net> wrote:
I have a question about a particular type of decomposition of N-dimensional rotation matrices. The specific types of matrices I am considering are orthogonal matrices (the rows form a set of orthogonal unit vectors, as do the columns). Further, I am only considering the case where the determinant is 1 (as opposed to -1). I.e., I am disallowing reflections.
I am interested in factoring such a matrix into a sequence of "primitive rotations" (I'm not sure what the proper term is). By this I mean rotations which only affect two coordinate axes. This defines a rotation within a plane, with the restriction that the plane be the product of two of the standard coordinate axes.
For an N-dimensional matrix, there are (N take 2) = N*(N-1)/2 possible pairs of axes. For example, in 3 dimensions they are XY, XZ, and YZ.
Any such rotation matrix, as defined above, can be factored into a sequence of N*(N-1)/2 primitive rotations, which each pair of axes occurring exactly once.
I know certain orderings will work. One such ordering is to first perform all rotations involving some particular axis, then perform all remaining rotations involving some other particular axis, etc. For instance, in 4 dimensions, the sequence could be (a1,a2), (a1,a3), (a1,a4), (a2,a3), (a2,a4), (a3,a4).
The opposite ordering can easily be shown to work as well, i.e. (a3,a4), (a2,a4), (a2,a3), (a1,a4), (a1,a3), (a1,a2).
My question is this: Can *any* fixed ordering be made to work, for any such rotation matrix? Or do only some orderings work?
Some observations:
There are a number of transformations that can be performed on any ordering to produce a new ordering which will work. In some cases the rotation amounts can be preserved. In others, the rotation amounts need to change.
Here's an example of a transformation that works in 4 dimensions:
(a1,a2), (a1,a3), (a2,a3), (a1,a4), (a2,a4), (a3,a4)
Here I have have swapped adjacent primitive rotations (a1,a4) and (a2,a3). This can always be done, without changing the rotation amounts, since they have no coordinates in common. But what about the case where they do have a coordinate in common?
In three dimensions, we know that any order works, so XY, XZ, YZ works, and so does XY, YZ, XZ, although when switching from one to the other, in general all *three* rotation amounts must be changed.
Does anyone know the answer to this? In N dimensions, will any fixed ordering work? Or do only some fixed orderings work?
Tom
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I had not encountered Tom Karzes' problem before, and currently have no intelligent and relevant comment to offer; but since this topic has arisen, I shall seize the opportunity to rabbit on about it being one of those not uncommon (double negative --- hah!) situations wherein resides the temptation to regurgitate some standard piece of college mathematics (here decomposition of a real orthonormal matrix into block diagonal form), then trot merrily away under a comforting delusion of having actually grasped what is going on. Cloaked in invisibility, the resulting lacunae stalk one's intellectual landscape at large, assured of perpetual persistence. So here's a little "something for the weekend, sir?" (long ago, the salutation delivered by a hairdresser on conclusion of his labours, in traditional nauseatingly confidential and lugubriously creepy fashion). What lugubrious features of their corresponding (projective) matrices distinguish the following nauseatingly traditional and creepily continuous transformations in (say) Euclidean 3-space? (A) Rotation by an angle about a coline; (B) Translation by a distance along a vector; (C) Dilation by a ratio with respect to a centre point; and (rather less common) in 4-space, (D) Transport along Clifford parallels (aka Hopf fibration). The answers provide (part of) a rationale explaining exactly how these various types arise in the first place, along with what additional exotica might lurk unintuited in other quadratic spaces. At the same time, it does need to be emphasised that matrices provide a less than ideal framework for such an investigation, compared to my preferred option of Clifford algebra. Fred Lunnon On 3/12/16, Tom Karzes <karzes@sonic.net> wrote:
I agree Dan, the "canonical form" of an orthogonal matrix is a nice result. In three dimensions, it basically just says that any rotation can be defined as rotation about some one-dimensional axis. To bring it into canonical form, one need merely rotate that axis onto, for instance, the Z axis, confining the rotation to the XY plane. In higher dimensions, it's a little more complicated.
I remember you mentioning your work in visualizing N-dimensional data, and your "grand tour" method before. My situation is very similar. I want to specify a sequence of Givens rotations that is capable of supporting universal rotation in N-space, and while it is easy to find such sequences, it is not clear to me whether any such sequence works vs. only some sequences. I don't *need* to know the answer, but I'd like to.
Honestly, when I posted this question I thought I'd immediately get several replies saying "Oh, don't you know that? Didn't you take freshman linear algebra?" But it seems like the answer isn't common knowledge after all. I'm honestly wondering if the answer is even known. Seems hard to imagine that it wouldn't be (or at least, that the question wouldn't be well known).
Tom
participants (5)
-
Dan Asimov -
Dan Asimov -
Fred Lunnon -
Gareth McCaughan -
Tom Karzes