Re: [math-fun] Orthogonal group generators
From: Fred Lunnon <fred.lunnon@gmail.com> The following questions arose as a result of an enquiry raised on the list Geometric_Algebra <geometric_algebra@googlegroups.com> ---
SO(n) denotes the proper isometries of an (n-1)-sphere, embedded in standard fashion in a Cartesian coordinate basis (x_1,...,x_n); R_i(t) denotes rotation through angle t about axis the coline meet of coordinate hyperplanes x_(i-1), x_i . [ Ambiguity in rotation sense need not concern us just now. ] Question (A) : Does the set G = { R_2, ..., R_n } generate SO(n) (irredundantly)? --you forgot to say which t. Question (B) : Given an arbitrary isometry, is its minimum length as a word over G necessarily at most n_C_2 = n(n-1)/2 (sharply)? --first of all, letting R_ij(t) denote rotation in plane generated by i and j coordinates, thru angle t: any member of SO(n) is generated by the R_ij(t)'s, in fact is a word with n_C_2 factors, each an R_ij(t). The t's will all differ in general. The (i,j) will also all differ. Standard Givens rotation matrix factoring/reduction algorithms show this. You seem interested not in general (i,j) but want only to allow j=i+1. So obviously, if we could express R_ab(t) in terms of the R_(a, a+1) we would be done. In fact it obviously suffices to express R_(1,3) in terms of R_(1,2) and R_(2,3). In quaternion terms it suffices to express k in terms of i and j. Well, uh, gee. k = j*i. Proof done? Well, not quite. More precisely, R_12(t) is i^(2*t/pi) in quaternion terms. So we need to express k^p in terms of i^q and j^r for arbitrary real p and some real q and r. But, well, look. Plainly, we can PERMUTE the coordinates arbitrarily using only the R_{a, a+1}(pi). Proof: Bubble sort. Therefore plainly we can permute to move any two coordinates adjacent, then use an R_{a,a+1} to rotate just those two coords, then unpermute. Therefore, the R_{a,a+1} generate the full set of R_{a,b} which in turn via standard Givens algorithms generate the full SO(n). Question (C) : Is there a practical algorithm expressing an isometry, given in the form (say) of a numerical matrix, as a word over G ? --yes.
FWL: So the word / composition of R_i is required to have bounded length, of order n_C_2 . Iterative processes such as Jacobi or Givens reduction (which anyway apply to symmetric rather than orthogonal matrices) seem unserviceable in this context. WDS: No no no. First, given an orthogonal matrix one can, in a NON iterative, totally deterministic totally obvious manner, apply Givens rotations to it from the left to zero the lower triangle elements one by one in raster scan order going down columns. Now it is lower triangular orthogonal, which means it is the identity. OK? So in this way any orthogonal matrix is a product of Givens 2x2s. Second, an orthogonal nXn obviously has (n-1)*n/2 degrees of freedom, and hence cannot be factored into fewer than that number of Givens 2x2 matrices (since each contains one degree of freedom) unless we were doing something weird like a spacefilling curve (which it seems plain we aren't), and this procedure meets that bound so bound is tight. Now in my first post I described a way to do it using only ADJACENT Givens 2x2s, i.e. only involving coordinates i and i+1. That involved n*(n-1)/2 having continuously variable angles, but a cubic(n) number of others each with fixed angle=pi. So it fails to meet Lunnon's desire for a quadratic(n) number, but that might merely be because I was being very crude in my approach. OK, here, try this. Start with an orthogonal nXn. Now zero the lower triangle in the order shown: 7 48 259 136... each by means of one adjacent-Givens applied from the left. Doesn't that work, and further do the whole job with only (n-1)*n/2 of them? -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
<< 7 48 259 136...
Rotation #3 destroys the result of #1 ?! As I pointed out previously, Givens etc. reduction is _iterative_ --- each operation destroys previous entries, though leaving those smaller than they had been earlier. WFL On 5/17/16, Warren D Smith <warren.wds@gmail.com> wrote:
FWL: So the word / composition of R_i is required to have bounded length, of order n_C_2 . Iterative processes such as Jacobi or Givens reduction (which anyway apply to symmetric rather than orthogonal matrices) seem unserviceable in this context.
WDS: No no no. First, given an orthogonal matrix one can, in a NON iterative, totally deterministic totally obvious manner, apply Givens rotations to it from the left to zero the lower triangle elements one by one in raster scan order going down columns. Now it is lower triangular orthogonal, which means it is the identity. OK? So in this way any orthogonal matrix is a product of Givens 2x2s.
Second, an orthogonal nXn obviously has (n-1)*n/2 degrees of freedom, and hence cannot be factored into fewer than that number of Givens 2x2 matrices (since each contains one degree of freedom) unless we were doing something weird like a spacefilling curve (which it seems plain we aren't), and this procedure meets that bound so bound is tight.
Now in my first post I described a way to do it using only ADJACENT Givens 2x2s, i.e. only involving coordinates i and i+1. That involved n*(n-1)/2 having continuously variable angles, but a cubic(n) number of others each with fixed angle=pi. So it fails to meet Lunnon's desire for a quadratic(n) number, but that might merely be because I was being very crude in my approach.
OK, here, try this. Start with an orthogonal nXn. Now zero the lower triangle in the order shown:
7 48 259 136...
each by means of one adjacent-Givens applied from the left. Doesn't that work, and further do the whole job with only (n-1)*n/2 of them?
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
LUNNON replying to WDS: 7 48 259 136...
Rotation #3 destroys the result of #1 ?! As I pointed out previously, Givens etc. reduction is _iterative_ --- each operation destroys previous entries, though leaving those smaller than they had been earlier. WFL --WDS. You're totally wrong. First of all Givens transforms need NOT be done "iteratively" meaning an infinite process. A finite number of them can be used, and are used, in the schemes I described, to exactly zero all the entries of the lower triangle of any desired starting orthogonal nXn matrix, one by one, without ever destroying any previous zero. To accomplish that it is key to perform the zeroings in a feasible well-chosen order. Second, rotation #3 does NOT destroy the zero-result caused by rotation 1 because when 3 is used, entries labeled 1 and 2 have already been zeroed by the two prior Givens's. Therefore this rotation, affecting the bottom two rows only, does not alter that fact the entries labeled 1 and 2 already both contain 0s, because of the amazing mathematical facts that 0+0=0 and x*0=0 and 0-0=0. Next? As should have been obvious, each GIvens, because of your demand it only affect rows i and i+1 of the nXn matrix, only affects rows i and i+1 of the nXn matrix, for different i each time of course. You appear (trying to read your mind) to have the idea that Givens's can be used iteratively from both the left and the right (conjugately) to zero the strict lower and upper triangle of a symmetric matrix, eventually yielding its eigenvalues on diagonal and rest 0s. That is true. That iterative method was first suggested by Jacobi. It generally requires an infinite number of Givens's to complete, although a finite number suffice to accomplish the zeroing to any particular number of decimal places accuracy. However, that all is completely irrelevant. I am working on an orthogonal, not a symmetric, nXn matrix, and multiplying by Givens's only from the left not both left & right, and zeroing entries one at a time, not an iterative approximate-zeroing. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
See https://en.wikipedia.org/wiki/Givens_rotation (one may take a horse to water ... ) WFL On 5/17/16, Warren D Smith <warren.wds@gmail.com> wrote:
LUNNON replying to WDS: 7 48 259 136...
Rotation #3 destroys the result of #1 ?!
As I pointed out previously, Givens etc. reduction is _iterative_ --- each operation destroys previous entries, though leaving those smaller than they had been earlier. WFL
--WDS. You're totally wrong. First of all Givens transforms need NOT be done "iteratively" meaning an infinite process. A finite number of them can be used, and are used, in the schemes I described, to exactly zero all the entries of the lower triangle of any desired starting orthogonal nXn matrix, one by one, without ever destroying any previous zero. To accomplish that it is key to perform the zeroings in a feasible well-chosen order.
Second, rotation #3 does NOT destroy the zero-result caused by rotation 1 because when 3 is used, entries labeled 1 and 2 have already been zeroed by the two prior Givens's. Therefore this rotation, affecting the bottom two rows only, does not alter that fact the entries labeled 1 and 2 already both contain 0s, because of the amazing mathematical facts that 0+0=0 and x*0=0 and 0-0=0.
Next?
As should have been obvious, each GIvens, because of your demand it only affect rows i and i+1 of the nXn matrix, only affects rows i and i+1 of the nXn matrix, for different i each time of course.
You appear (trying to read your mind) to have the idea that Givens's can be used iteratively from both the left and the right (conjugately) to zero the strict lower and upper triangle of a symmetric matrix, eventually yielding its eigenvalues on diagonal and rest 0s. That is true. That iterative method was first suggested by Jacobi. It generally requires an infinite number of Givens's to complete, although a finite number suffice to accomplish the zeroing to any particular number of decimal places accuracy. However, that all is completely irrelevant. I am working on an orthogonal, not a symmetric, nXn matrix, and multiplying by Givens's only from the left not both left & right, and zeroing entries one at a time, not an iterative approximate-zeroing.
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
<< one may lead a horse to water ... >> --- and if one leaves the dumb animal there long enough, it may eventually get the idea! Warren's algorithm doesn't quite work as presented: I did try it, by the way. However, working column-by-column instead it succeeds: eliminate in order 21, 31, 31, ..., 32, 42, ..., 43, ... and an even isometry is indeed magically reduced a product of (general rather than adjacent) Givens rotations. The Wikipedia page paragraph "Stable calculation" discusses tinkering with the sign of the rotation angle in order to ensure "continuity". Does anyone understand what this is about? WFL On 5/17/16, Fred Lunnon <fred.lunnon@gmail.com> wrote:
See https://en.wikipedia.org/wiki/Givens_rotation (one may take a horse to water ... )
WFL
On 5/17/16, Warren D Smith <warren.wds@gmail.com> wrote:
LUNNON replying to WDS: 7 48 259 136...
Rotation #3 destroys the result of #1 ?!
As I pointed out previously, Givens etc. reduction is _iterative_ --- each operation destroys previous entries, though leaving those smaller than they had been earlier. WFL
--WDS. You're totally wrong. First of all Givens transforms need NOT be done "iteratively" meaning an infinite process. A finite number of them can be used, and are used, in the schemes I described, to exactly zero all the entries of the lower triangle of any desired starting orthogonal nXn matrix, one by one, without ever destroying any previous zero. To accomplish that it is key to perform the zeroings in a feasible well-chosen order.
Second, rotation #3 does NOT destroy the zero-result caused by rotation 1 because when 3 is used, entries labeled 1 and 2 have already been zeroed by the two prior Givens's. Therefore this rotation, affecting the bottom two rows only, does not alter that fact the entries labeled 1 and 2 already both contain 0s, because of the amazing mathematical facts that 0+0=0 and x*0=0 and 0-0=0.
Next?
As should have been obvious, each GIvens, because of your demand it only affect rows i and i+1 of the nXn matrix, only affects rows i and i+1 of the nXn matrix, for different i each time of course.
You appear (trying to read your mind) to have the idea that Givens's can be used iteratively from both the left and the right (conjugately) to zero the strict lower and upper triangle of a symmetric matrix, eventually yielding its eigenvalues on diagonal and rest 0s. That is true. That iterative method was first suggested by Jacobi. It generally requires an infinite number of Givens's to complete, although a finite number suffice to accomplish the zeroing to any particular number of decimal places accuracy. However, that all is completely irrelevant. I am working on an orthogonal, not a symmetric, nXn matrix, and multiplying by Givens's only from the left not both left & right, and zeroing entries one at a time, not an iterative approximate-zeroing.
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I think that refers to finding a continuous map from SO(n) to the torus T^N = (S^1)^N (N = (n^2-n)/2) of the same dimension (where S^1 is the unit circle), such that the angles in the torus, when plugged into Givens rotations in a fixed order of indices, give the same element of SO(n) that one started with. (The problem, when this does not happen in 3D, is called gimbal lock.) —Dan
On May 18, 2016, at 2:29 PM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
The Wikipedia page paragraph "Stable calculation" discusses tinkering with the sign of the rotation angle in order to ensure "continuity". Does anyone understand what this is about?
Gimbal lock is another relevant issue I have never understood to my own satisfaction, although at one point I remember discussing it with a software engineer and coming to the conclusion that it constitutes an excellent reason for religiously avoiding the Euler angles he had been unsuccessfully attempting to deploy. Especially if you're designing (say) a transmission systems for a helicopter ... But it seems this business is something different again. I followed up the Wikipedia reference to Anderson (2000) at http://www.netlib.org/lapack/lawnspdf/lawn150.pdf where it appears that in an attempt to avoid numerical overflow, software adopts a more complicated method of determining the angle which results in the square root acquiring an unpredictable sign, so that the rotation matrix computed is a discontinuous function of the input isometry. Algorithm 4 on page 10 employs a 4-way branch to correct this in turn --- nothing is simple! Fred Lunnon On 5/18/16, Dan Asimov <asimov@msri.org> wrote:
I think that refers to finding a continuous map from SO(n) to the torus
T^N = (S^1)^N
(N = (n^2-n)/2) of the same dimension (where S^1 is the unit circle), such that the angles in the torus, when plugged into Givens rotations in a fixed order of indices, give the same element of SO(n) that one started with. (The problem, when this does not happen in 3D, is called gimbal lock.)
—Dan
On May 18, 2016, at 2:29 PM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
The Wikipedia page paragraph "Stable calculation" discusses tinkering with the sign of the rotation angle in order to ensure "continuity". Does anyone understand what this is about?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Basically, gimbal lock is caused by the nonexistence of any map SO(n) —> T^N such as I described. In fact, such a map would have to be of degree = 1. A continuous map SO(n) —> T^k of degree 1 cannot exist unless n = k = 1. —Dan
On May 18, 2016, at 5:24 PM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
Gimbal lock is another relevant issue I have never understood to my own satisfaction, although at one point I remember discussing it with a software engineer and coming to the conclusion that it constitutes an excellent reason for religiously avoiding the Euler angles he had been unsuccessfully attempting to deploy. Especially if you're designing (say) a transmission systems for a helicopter ...
But it seems this business is something different again. I followed up the Wikipedia reference to Anderson (2000) at http://www.netlib.org/lapack/lawnspdf/lawn150.pdf where it appears that in an attempt to avoid numerical overflow, software adopts a more complicated method of determining the angle which results in the square root acquiring an unpredictable sign, so that the rotation matrix computed is a discontinuous function of the input isometry.
Algorithm 4 on page 10 employs a 4-way branch to correct this in turn --- nothing is simple!
Fred Lunnon
On 5/18/16, Dan Asimov <asimov@msri.org> wrote:
I think that refers to finding a continuous map from SO(n) to the torus
T^N = (S^1)^N
(N = (n^2-n)/2) of the same dimension (where S^1 is the unit circle), such that the angles in the torus, when plugged into Givens rotations in a fixed order of indices, give the same element of SO(n) that one started with. (The problem, when this does not happen in 3D, is called gimbal lock.)
—Dan
On May 18, 2016, at 2:29 PM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
The Wikipedia page paragraph "Stable calculation" discusses tinkering with the sign of the rotation angle in order to ensure "continuity". Does anyone understand what this is about?
_______________________________________________ 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
In one design of inertial guidance system, three mechanical spinning gyroscopes with orthogonal input axes are employed to stabilize a platform that remains fixed in inertial space even as the craft rotates around it. Gimbals isolate the platform from the craft. Angle encoders on the gimbals provide orientation information to the navigational controller. The gyros output a signal when they sense a rotation about their input axes, and the gimbals can be torqued to null out that signal and maintain the platform stability. Nominally, three gimbals, initially along orthogonal axes, suffice to compensate for arbitrary orientation. However, if the middle gimbal rotates 90 degrees, the inner and outer gimbal axes become coincident, and control is lost. This is called gimbal lock. Systems that must navigate through gimbal lock make use of a forth gimbal to maintain control. A completely different methodology is strapdown inertial guidance. Here, the inertial platform is strapped to, and rotates with, the craft, so gimbal lock can't happen. With mechanical gyros as the rotation sensor, the gyros themselves are torqued to maintain a null output signal, and the torque signal provides the rotational information to the navigation controller. There are also optical gyros that use counter-rotating light beams (Sagnac interferometer). Strapdown inertial navigation is necessarily dependent on the use of a computer, but this allows for clever designs. One such redundant system uses six gyros and six accelerometers with axes along the face normals of a dodecahedron. The unit could function with the loss of three of either type of sensor. -- Gene From: Fred Lunnon <fred.lunnon@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Sent: Wednesday, May 18, 2016 5:24 PM Subject: Re: [math-fun] Orthogonal group generators Gimbal lock is another relevant issue I have never understood to my own satisfaction, although at one point I remember discussing it with a software engineer and coming to the conclusion that it constitutes an excellent reason for religiously avoiding the Euler angles he had been unsuccessfully attempting to deploy. Especially if you're designing (say) a transmission systems for a helicopter ... But it seems this business is something different again. I followed up the Wikipedia reference to Anderson (2000) at http://www.netlib.org/lapack/lawnspdf/lawn150.pdf where it appears that in an attempt to avoid numerical overflow, software adopts a more complicated method of determining the angle which results in the square root acquiring an unpredictable sign, so that the rotation matrix computed is a discontinuous function of the input isometry. Algorithm 4 on page 10 employs a 4-way branch to correct this in turn --- nothing is simple! Fred Lunnon On 5/18/16, Dan Asimov <asimov@msri.org> wrote:
I think that refers to finding a continuous map from SO(n) to the torus
T^N = (S^1)^N
(N = (n^2-n)/2) of the same dimension (where S^1 is the unit circle), such that the angles in the torus, when plugged into Givens rotations in a fixed order of indices, give the same element of SO(n) that one started with. (The problem, when this does not happen in 3D, is called gimbal lock.)
—Dan
On May 18, 2016, at 2:29 PM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
The Wikipedia page paragraph "Stable calculation" discusses tinkering with the sign of the rotation angle in order to ensure "continuity". Does anyone understand what this is about?
Clearing entries column-by-column, as opposed to in increasing triangles. I tried to illustrate the the order, but managed to mistype it: should have read 21, 31, 41, ..., 32, 42, ..., 43, ... WFL
On 5/18/16, Warren D Smith <warren.wds@gmail.com> wrote:
to FWL, perhaps your working by columns not rows is since you transposed the matrices versus my convention? In any case, doesn't really matter.
On 5/18/16, Fred Lunnon <fred.lunnon@gmail.com> wrote:
<< one may lead a horse to water ... >> --- and if one leaves the dumb animal there long enough, it may eventually get the idea!
Warren's algorithm doesn't quite work as presented: I did try it, by the way. However, working column-by-column instead it succeeds: eliminate in order 21, 31, 31, ..., 32, 42, ..., 43, ... and an even isometry is indeed magically reduced a product of (general rather than adjacent) Givens rotations.
The Wikipedia page paragraph "Stable calculation" discusses tinkering with the sign of the rotation angle in order to ensure "continuity". Does anyone understand what this is about?
WFL
On 5/17/16, Fred Lunnon <fred.lunnon@gmail.com> wrote:
See https://en.wikipedia.org/wiki/Givens_rotation (one may take a horse to water ... )
WFL
On 5/17/16, Warren D Smith <warren.wds@gmail.com> wrote:
LUNNON replying to WDS: 7 48 259 136...
Rotation #3 destroys the result of #1 ?!
As I pointed out previously, Givens etc. reduction is _iterative_ --- each operation destroys previous entries, though leaving those smaller than they had been earlier. WFL
--WDS. You're totally wrong. First of all Givens transforms need NOT be done "iteratively" meaning an infinite process. A finite number of them can be used, and are used, in the schemes I described, to exactly zero all the entries of the lower triangle of any desired starting orthogonal nXn matrix, one by one, without ever destroying any previous zero. To accomplish that it is key to perform the zeroings in a feasible well-chosen order.
Second, rotation #3 does NOT destroy the zero-result caused by rotation 1 because when 3 is used, entries labeled 1 and 2 have already been zeroed by the two prior Givens's. Therefore this rotation, affecting the bottom two rows only, does not alter that fact the entries labeled 1 and 2 already both contain 0s, because of the amazing mathematical facts that 0+0=0 and x*0=0 and 0-0=0.
Next?
As should have been obvious, each GIvens, because of your demand it only affect rows i and i+1 of the nXn matrix, only affects rows i and i+1 of the nXn matrix, for different i each time of course.
You appear (trying to read your mind) to have the idea that Givens's can be used iteratively from both the left and the right (conjugately) to zero the strict lower and upper triangle of a symmetric matrix, eventually yielding its eigenvalues on diagonal and rest 0s. That is true. That iterative method was first suggested by Jacobi. It generally requires an infinite number of Givens's to complete, although a finite number suffice to accomplish the zeroing to any particular number of decimal places accuracy. However, that all is completely irrelevant. I am working on an orthogonal, not a symmetric, nXn matrix, and multiplying by Givens's only from the left not both left & right, and zeroing entries one at a time, not an iterative approximate-zeroing.
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (5)
-
Dan Asimov -
Dan Asimov -
Eugene Salamin -
Fred Lunnon -
Warren D Smith