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