From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math.num-analysis Subject: Re: Decompose nxn M as linear combo. of _orthogonal_ matrices ?? Date: 21 Feb 1996 20:45:20 GMT In article , Henry Baker wrote: >I want to express an arbitrary nxn real matrix M as a linear combination of >nxn real _orthogonal_ matrices, such that the 'multipliers' descend in >absolute value. I.e., > >M = a1 U1 + a2 U2 + a3 U3 + ... + am Um, > >where ai is real and Ui is orthogonal. > >If M is 'almost' an orthogonal matrix U, then the first term in the sum >should be aU, where a is very close to 1.0. I don't have a solution but I can offer some comments. There's probably an easy proof that the orthogonal matrices do not lie in any proper linear subspace of M_n(R), but I can't remember it so I'll have to use this: Lemma: If A is a matrix with Tr(BA)=0 for all orthogonal matrices B then A=0. Proof: Writing A = A1*A2 with A1 orthogonal and A2 upper-triangular, we see the condition is equivalent to stating Tr(B*A2) = 0. Taking for B all the diagonal matrices with +1 and -1 on the diagonal, we eventually conclude A2 has all diagonal entries zero. Then taking for B all elementary matrices which interchange two rows, we see all the other entries of A2 are zero, so that A=0, as desired. [] The statement that the orthogonal matrices do not lie in a linear subspace then follows. From this, we deduce that _every_ matrix can be expressed as a linear combination of orthogonal matrices, indeed as a linear combination of at most n^2 of them -- you can even pick n^2 of them in advance if you wish and write every matrix as a linear combination of just these. (Assuming they're linearly independent, of course.) Thus the _existence_ of the poster's decomposition isn't really a problem; I would interpret this question to mean, can we find an algorithm for computing such a decomposition, or a characterization of the resulting coefficients, or an "optimal" decomposition among all the possible choices of such. I don't have an answer, but I can give an analysis of the 2x2 case which may suggest some issues which can be generalized. In the 2 x 2 case, the orthogonal group has two components: the rotation matrices [ c -s ] [ s c ] and the reflection matrices [ c s ] [ s -c ]. (where c^2+s^2=1 in both cases.) Taking linear combinations of matrices in just one of these components will yield another matrix in the same linear subspace, without necessarily having c^2+s^2=1, of course. But it's easy to see that these linear spans are two orthogonal 2-planes in R^4, so that every matrix M is uniquely expressible as a sum of a matrix in each subspace. Thus every matrix M has a unique (up to sign) representation M = a_1 U_1 + a_2 U_2 where U_1 is some specific rotation and U_2 a specific reflection. If I've calculated correctly, U_1 is in fact the rotation matrix closest to M. Naturally, this representation is not unique in the family of all potential expansions meeting the poster's criteria -- one can replace U_1, say, by a linear combination of any two (independent) rotations -- that is, one can use any basis for this 2-plane one wishes. Likewise the other 2-plane can be given many bases; each would lead to a replacement of U_2 by a linear combination of two reflections. Note that the decomposition of M_2 into two orthogonal planes could have been predicted from Lie group theory: the Lie algebra gl_2(R) = R^4 is the direct sum of the symmetric and skew-symmetric subsets. Upon exponentiation we map the first to the symmetric subspace of GL_2(R) and the second to the group SO_2(R) of rotations; locally (near the origin in gl_2) this is an isomorphism, giving the unique decomposition of elements of M_2(R) as a sum of elements in the two orthogonal 2-planes. Unfortunately, in dimensions > 2 we lose commutativity in O_n(R) (or o_n(R) ), making this analysis not carry over. The most helpful thing I can say in the n x n case is to again observe that every matrix can be written as a product M = U*N where U is orthogonal and N is upper-triangular. If M is non-singular, then the diagonal entries of N can be arranged to be positive, in which case both U and N are unique. It suffices then to write N as a sum of orthogonal matrices, since (N = Sum a_i U_i) implies (M = Sum a_i (U*U_i) ). As a bonus, one checks that the action of O_n(R) on M_n(R) is also orthogonal, so that N is just as close to U_1 as M is to U*U_1. Hence, even with the poster's idea to have U_1 "close" to M, we now see it is sufficient to consider the case in which M is upper-triangular and has positive diagonal entries. But although this limits the size of the problem, I don't see that it adds any particular structure to it. I will try clicking the "send" button; that usually makes the right idea pop into my head. :-) dave ============================================================================== From: hbaker@netcom.com (Henry G. Baker) Subject: Re: Decompose nxn M as linear combo. of _orthogonal_ matrices ?? To: rusin@math.niu.edu (Dave Rusin) Date: Wed, 21 Feb 1996 12:15:14 -0800 (PST) > In article you write: > >This may be a totally trivial problem, but I haven't found the right way > >to see it yet. > > Me either -- did you get any responses? > If you get anything interesting I'd like to get a cc: -- thanks > > dave Nothing other than your response so far. I'm actually interested in only the 4x4 case for now. I want to express the mapping Mx, where M is an _arbitrary_ real 4x4 matrix and x is a 4-element real vector, as the sum: Mx = A x B + C x D + E x F + G x H, where A,B,C,D,E,F,G,H are _quaternions_ and x is treated as a quaternion on the right-hand side. I understand that any _orthogonal_ 4x4 matrix U function (Ux) can be expressed as Ux = A x B, where A,B are quaternions and x is treated as a quaternion on the right hand side. It is clear that in the 4x4 case, only 4 terms are required, since by multiplying out the quaternion definition, you can use B=1, D=i, F=j, H=k. However, I'd like to reduce the number of terms to a minimum. One may be able to do slightly better in if one is also given x', where x' is the quaternion _conjugate_. However, since the quaternion conjugate can be expressed as such a sum, it adds nothing essentially new (unlike the case of the complex numbers, where the conjugate _cannot_ be expressed in such a fashion). x' = -0.5 (x + i x i + j x j + k x k) -- Henry Baker www/ftp directory: ftp.netcom.com:/pub/hb/hbaker/home.html ============================================================================== Date: Wed, 21 Feb 1996 21:00:10 -0800 From: hbaker@netcom.com (Henry Baker) To: rusin@vesuvius.math.niu.edu (Dave Rusin) Subject: Re: Decompose nxn M as linear combo. of _orthogonal_ matrices ?? In article <4gg090$977@muir.math.niu.edu>, rusin@vesuvius.math.niu.edu (Dave Rusin) wrote: > In article , > Henry Baker wrote: > >I want to express an arbitrary nxn real matrix M as a linear combination of > >nxn real _orthogonal_ matrices, such that the 'multipliers' descend in > >absolute value. I.e., > > > >M = a1 U1 + a2 U2 + a3 U3 + ... + am Um, > > > >where ai is real and Ui is orthogonal. > > > >If M is 'almost' an orthogonal matrix U, then the first term in the sum > >should be aU, where a is very close to 1.0. > > I don't have a solution but I can offer some comments. [snip] > Note that the decomposition of M_2 into two orthogonal planes could > have been predicted from Lie group theory: the Lie algebra gl_2(R) = R^4 > is the direct sum of the symmetric and skew-symmetric subsets. Upon > exponentiation we map the first to the symmetric subspace of GL_2(R) > and the second to the group SO_2(R) of rotations; locally (near the > origin in gl_2) this is an isomorphism, giving the unique decomposition > of elements of M_2(R) as a sum of elements in the two orthogonal 2-planes. > > Unfortunately, in dimensions > 2 we lose commutativity in O_n(R) (or > o_n(R) ), making this analysis not carry over. > > The most helpful thing I can say in the n x n case is to > again observe that every matrix can be written as a > product M = U*N where U is orthogonal and N is upper-triangular. > If M is non-singular, then the diagonal entries of N can be arranged > to be positive, in which case both U and N are unique. > > It suffices then to write N as a sum of orthogonal matrices, since > (N = Sum a_i U_i) implies (M = Sum a_i (U*U_i) ). As a bonus, one > checks that the action of O_n(R) on M_n(R) is also orthogonal, so > that N is just as close to U_1 as M is to U*U_1. Hence, even > with the poster's idea to have U_1 "close" to M, we now see it is > sufficient to consider the case in which M is upper-triangular and > has positive diagonal entries. This has been very helpful. What if we consider 2x2 matrices over the complex numbers? For my current problem, this is almost as good, since a quaternion q = A + Bj (A,B, complex, i=i, k=ij) can be mapped into the 2x2 matrix [A -B*] [B A*] This has only 1/2 the degrees of freedom of the 4x4 matrix of reals, but it may give enough insight anyway. > But although this limits the size of the problem, I don't see that it > adds any particular structure to it. I will try clicking the "send" > button; that usually makes the right idea pop into my head. :-) :-) I read my mail when I first get up, and the good answers usually hit me afterward while I'm in the shower... Thanks again for your insights. -- www/ftp directory: ftp://ftp.netcom.com/pub/hb/hbaker/home.html ============================================================================== Date: Thu, 22 Feb 96 13:24:52 CST From: rusin (Dave Rusin) To: hbaker@netcom.com Subject: Re: Decompose nxn M as linear combo. of _orthogonal_ matrices ?? Now several posts and emails have crossed each other; I hope this isn't too jumbled. You wrote: >Nothing other than your response so far. I'm actually interested in only >the 4x4 case for now. I want to express the mapping Mx, where M is >an _arbitrary_ real 4x4 matrix and x is a 4-element real vector, as >the sum: > >Mx = A x B + C x D + E x F + G x H, where > >A,B,C,D,E,F,G,H are _quaternions_ and x is treated as a quaternion on >the right-hand side. Ah, this I can do. You are just using the fact that the tensor product H @ H of the ring H of quaternions with itself is the same as the ring M_4(R) of 4 x 4 matrices. Concretely, you can take a basis {1, i, j, k} (say) of H. Then for any fixed quaternion a, the functions v -> av and v -> va are linear transformations of H to itself, and may be written as 4 x 4 matrices. That is, you have two embeddings of H into M_4(R) (one preserves products, the other reverses them). Then the statements H @ H = M_4(R) is equivalent to saying that every matrix may be written as a sum of products of matrices of these forms. You can check this for yourself: try all 16 matrices 1@i, j@k, ... and you'll see they are linearly independent in M_4(R). (Here a@b is the matrix corresponding to the linear map v -> avb.) Collecting the coefficients of @1, @i, @j, and @k, we see that every linear transformation may be written a1@1 + a2@i + a3@j + a4@k for some (unique) quaternions a1, a2, a3, a4. It's even easy to obtain these a_i. The columns of M indicate the values of M(1), M(i), M(j), and M(k). These quaternions you seek must satisfy M(1) = a1 + a2 i + a3 j + a4 k M(i) = a1 i - a2 + a3 k - a4 j M(j) = a1 j - a2 k - a3 + a4 i M(k) = a1 k + a2 j - a3 i - a4 in other words, the row matrix r of the four quaternions on the left is the product of the row matrix a = (a1, a2, a3, a4) and the matrix B = [ 1 i j k ] [ i -1 -k j ] [ j k -1 -i ] [ k -j i -1 ] If C is the quaternionic conjugate of B, then if I've done it right, BC = 4I, so that the equation r = aB implies a = (1/4)(rC). Thus a1 = (1/4)(r1 - r2 i - r3 j - r4 k) and so on. (Again, I'm treating the first column of the original matrix M as a quaternion r1 = m11*1 + m21*i + m31*j + m41*k, and so on to define the ri). So, yes, you _can_ get the decomposition you seek, and you can do so with B = 1, D = i, F = j, H = k; then A, C, E, G are unique and can be computed as linear combinations of the entries in M, with all nonzero coefficients being +-(1/4). As noted, you can re-expand this as a sum of multiples of the 16 matrices u@v, where u and v range over the four standard generators of H. Since each of u@ and @v is an orthogonal matrix, so are the 16 basis matrices. In order to express M _differently_ as a sum of orthogonal matrices, note that u@ and v@ are orthogonal for _any_ unit quaternion, so that for any quaternions a and b, a@b is a scalar multiple of an orthogonal matrix. Thus for example, the decomposition M = A@1 + C@i + E@j + G@k already gives M as a sum of at most 4 orthogonal matrices, in an easily computable way. I don't know how much better you can do. I guess it's true that the matrices which are scalar multiples of one orthogonal matrix are _precisely_ those which may be written a@b for some quaternions a and b. Then the minimal number of orthogonal matrices needed would be the minimal number of summands in an expression M = a1@b1 + a2@b2 +... . We have seen that at most four summands are needed; any nonsingular matrix M shows at least two are sometimes needed. Beyond that I won't hazard a guess. You could bone up on tensor products of division algebras, I suppose, to see if there's some reason to think every element of H@H can be written as a sum of just two tensors a@b + c@d. Interestingly, the 2 x 2 case is _not_ a model for this. There is a 2-dimensional division algebra over the reals, of course, but C@C is isomorphic to the direct sum of two copies of C, not to M_2(R), so little of the preceding analysis carries over. On the other hand, some of this does not depend on the division algebra structure; possibly the use of these tensor products (Kronecker products) would let us pass from M_n(R) to M_{2n}(R) and salvage something. In subsequent email you mentioned the possibility of viewing H not as a subalgebra of M_4(R) but rather as a subalgebra of M_2(C). I'm not quite sure what to say here, since M_2(C) may be viewed as a subalgebra of M_4(R), not the other way around; you would only be able to say things about how _some_ matrices in M_4(R) may be written as linear combinations of orthogonal matrices. But I suppose that give you a place to start with conjectures: Maybe the elements of M_4(R) which can be written as a sum of just two tensor products (i.e. M= a@b + c@d) are precisely those which are in the image of M_2(C)? (I'm dubious, since the latter set is I think dependent on choice of basis while the former is not.) dave