A Note on Matrix Factorizations of Orthogonal Matrices

Last edited October 9th, 2023i - John Halleck

Last signifcant edit was on June 4th, 2022 - John Halleck

Requires: Basic Familiarity with Matrices (transposes, inverses, identities, ...)

Assumptions:
   If we multiply matrices below, we assume that they are conformable.
   If we we take the inverse of a matrix below , we assume that the matrix has an inverse.

Notation review:
   Identity Matrix: I
   Zero Matrix: 0
   Matrix [multiplicative] Inverse of A: A^-1
   Matrix Transpose of A: A^T
   Matrix Both Inverse and Transpose applied to A: A^-T
     (Since the inverse of the transpose of a matrix equals the transpose of the inverse of matrix.)

Definitions:
   A matrix Q is orthogonal if it, multiplied by its transpose, is the identity matrix.
Examples:
   Q^TQ = I and QQ^T = I
   it follows that the transpose of an orthogonal matrix is equal to its inverse.
   Q^T = Q^-1 And so it follows that Q = Q^-T

In a prior post I introduced Orthogonal Matrices, and it is probably past time to say something interesting about them in the context of factoring matrices.

Factoring a matrix just means finding two or more matrices (called factors) that, when multiplied together, give the original matrix as a product. (This is also called a decomposition of the matrix.) An LU factorization, for example, produces an L matrix that is a unit lower triangular matrix, multiplied by an upper triangular matrix U. This particular factorization is one of the most famous in Linear Algebra.

I have heard it argued that if you have a orthogonal matrix, there is little point in forming an LU factorization of it, because you *already* have what you need to solve problems with it efficiently. Well, that does happen to be true, but I'm *not* solving systems... I'm playing with these matrices looking for interesting relationships. :)

So, let's examine the LU factorization (also called a decomposition) of an orthogonal matrix Q: we know that Q = Q^-T, so if Q = LU, we have LU = (LU)^-T = (U^-1L^-1)^T = L^-T U^-T. It is true, in general, for any matrix that has an LU decomposition, we have:
(LU)^-T = L^-T U^-T
*BUT* with an orthogonal matrix both are also equal to LU.

Side note: There was nothing in that little derivation that depended on the factorization being triangular matrices... This can be done with ANY matrix factorization of Q, Given a factorization ABCD... of Q you would get the obvious A^-TB^-TC^-TD^-T...

The LU demo did show that that if LU is orthogonal, then L^-T U^-T is also orthogonal. L^-T U^-T is actually a UL factorization (with a different L and U) instead of LU factorization of the *same* matrix when the matrix is orthogonal. L is lower triangular,and L^-T (because of the transpose) is upper triangular. And U^-T is (because of the transpose) lower triangular. So, for what it is worth, if LU is a unit lower triangular matrix is a unit lower triangular matrix, then L^-T is after an inverse and a transpose.

---- LU versus QR:

QR to LU: Solving a matrix problem like Ax=d is often done by finding a factorization of A which is QR where Q is orthogonal and R is upper triangular. If there is an LU factorization of Q, then this is (LU)R and if you re-associated it you would have L(UR), The U and R are both upper triangular, and could be multiplied together into a single upper triangular matrix, making the result of the form of an LU factorization.

*This side of the argument is a bit of a "hand wave", I need to make this a bit more rigorous -JH*
LU to QR: And, if you had Ax = d, and A = LU, you could convert this into a QR factorization by finding an upper triangular matrix E such that LE is orthogonal. Then insert EE^-1 into LU to get L EE^-1 U. Re-associate this as (LE)(E^-1U) which you can see (by inspection) is a QR factorization. [Note that E^-1U is upper triangular because both of it's terms are.] Finding such an E is probably as hard, or harder, than producing a QR factoring from scratch... interesting theoretical fact, not even worth it practically.

Navigation:

next post | previous post

Division by "Just in Time" Subtraction II

(Last edited July 25th, 2023 by John Halleck - fix arithmetic error.) Topics:     Division by "Just in Time" subtraction II
Requires: The information in The prior article in this series.
Definition: x mod y (called x modulo y), is just the remainder if you do integer divide of x by y
Disclaimer: The presentation below is mine, the ideas are from the late LeRoy N. Eide.

In my prior post on dividing by "Just in Time" subtraction [JITS], I pointed out that it did something bizarre if you were dividing by nine, and the number was not a multiple of nine. In this column I'll cover what it really does. And two different ways to look at that result that can make proper use of it.

The basic problem:

Given 9x = 1332, JITS properly produces 148 for x. And it produces the obvious (and correct) answer for any multiple of 9. So... let's look at the case where the given number is NOT a multiple of nine. As an example we can take 9x = 1336.

10x - 9x = x, so we try the subtraction:

Borrows:
   10x = ?  ?  ?  ?  ?  0
   -9x =       1  3  3  6
   ======================
     x = ?  ?  ?  ?  ?  ?

And we try to proceed as before...

Borrows:            -1
   10x = ?  ?  ?  ?  4  0
   -9x =       1  3  3  6
   ======================
     x = ?  ?  ?  ?  0  4

Digit by digit...

Borrows:            -1
   10x = ?  ?  ?  ?  4  0
   -9x =       1  3  3  6
   ======================
     x = ?  ?  ?  ?  0  4

... until we get to:

Borrows:          -1    -1
   10x = ... 5  5  7  0  4  0
   -9x =           1  3  3  6
   ==========================
     x = ... 5  5  5  7  0  4

And off to (countable) infinity producing 5's to the left. When this is shown to most people, they object at this point that that is *** not *** the right answer, and it doesn't even look meaningful. And when LeRoy first showed this to me I had a similar reaction. We are used to numbers trailing off to infinity to the right, but not trailing off to the left. [Except for Mathematicians that deal with p-adic numbers, who have seen this before. But that is a topic for a much later time.]

Our normal integers are represented by a series that may run off to smaller powers of the base, but only a finite distance into larger powers. So 123 is really 1x10²+2*10¹+3*10⁰, but if there are infinite powers we don't have much experience. It is easier to not think about these, then to think about this sort of infinite series.

There are several ways of looking at this state of affairs. On is that there is something we can do to "fix" this to match our normal interpretation. The other (and LeRoy's favorite) is to take this as an unfamiliar representation with it's own "virtues".

We'll just show the result from here on, instead of showing the computation of every step.

First, lets look at some very simple cases of dividing some small integers by 9. (And I'll assume everyone is happy with zeros trailing off infinitely to the left.)

0/9
borrows:
10x = ...  0  0  0  0
-9x =               0
=====================
  x = ...  0  0  0  0

1/9                    
borrows:        -1
10x = ...  8  8  9  0
-9x =               1
=====================
  x = ...  8  8  8  9

2/9
borrows:        -1
10x = ...  7  7  8  0
-9x =               2
=====================
  x = ...  7  7  7  8

3/9
borrows:        -1
10x = ...  6  6  7  0
-9x =               3
=====================
  x = ...  6  6  6  7

...

8/9
borrows:        -1
10x = ...  1  1  2  0
-9x =               8
=====================
  x = ...  1  1  1  2

9/9
borrows:        -1
10x = ...  0  0  1  0
-9x =               9
=====================
  x = ...           1

10/9
borrows:     -1
10x = ...  8  9  0  0
-9x =            1  0
=====================
  x = ...  8  8  9  0

That mysterious digit running to infinity on the left (call it d), is nothing but the distance to the next multiple of 9, and 9-d is nothing but the remainder when our 9x number is divided by 9. So, for example, if we have 9x = 1, the number running off is 8, so the remainder is 9-8 = 1. Subtract the remainder from the 9x value, to get it to be a multiple of 9, and use JITS to divide that by 9. A picky and astute student may question why we don't just add the 8 in to the 9x value and use JITS. Well, that would, for 9x=19, give not x=2 with remainder 1, but x=1 with remainder, 10.

On the other hand

While the above is a perfectly good way to view the integer problem, and it reduces to our traditional view, there is another view that looks at it not as divisor and remainder, but as a representation of numbers divided by nine. For example, we can take the "fractions above, and add them.

 Carrys: ...  +1 +1 +1 +1
 1/9 =   ...   8  8  8  8  9
+8/9 =   ...   1  1  1  1  2
============================
 9/9 =  ...    0  0  0  0  1

And

 Carrys: ...  +1 +1 +1 +1
 1/9 =   ...   8  8  8  8  9
+1/9 =   ...   8  8  8  8  9
============================
 2/9 =   ...   7  7  7  7  8

...

LeRoy went on to develop a full theory of rational numbers based on this, and it used to exist out on the net, but like his site, my site, and copies in places like the UK, those sites have long since gone away. I have posted a copy of those notes on the Pages section of my blog at https://eccentric-math.blogspot.com/p/jits-rational-representations-notes.html.
Prior Post

Coming attractions:Why was LeRoy actually doing this in balanced ternary rather than decimal anyway? What is balanced ternary? What has this got to do with a somewhat obscure early series of Russian computers no longer in use? And why did the US not legally exporting transistors lead to that series? That, and more can be found in my Balanced Ternary post

Navigation:

next post | previous post