I use A' for A transpose here.
I use Cholesky(A) to mean the UPPER triangular factor in A=U'U
inv(A) is matrix inverse of A
I will be using both the LU and UL factorizations below. Obviously, I can't use U for both U's or L for both L's. So I'll use L and U in the traditional manner for the LU factorization, and I'll use T (top) and B (bottom) for the UL [TB] factorization.
If a matrix with a TB factorization is orthogonal, then the matrix multiplied by its transpose must be the identity:
(TB)'(TB) = I B'T'TB = I T'T = inv(B')inv(B) = inv(BB')
So, if you have a lower triangular B you can build an orthogonal matrix TB by using
T = Cholesky(inv( BB' ))
Therefore
Cholesky(inv(BB')) B
is orthogonal.
And [uniformly substituting inv(B) for B] we have that matrices of the form
Cholesky(inv( inv(B)inv(B)' )) inv(B)
= Cholesky(inv (inv(B)inv(B') )) inv(B)
= Cholesky(inv ( inv(B'B) )) inv(B)
= Cholesky( B'B ) inv(B)
are also orthogonal. (And their transposes are also, obviously, orthogonal)
[Note that this has x'x and not the xx' of the non-inverse case.]
Now for the punch line: Consider
A = LU
Left multiply through by the matrix ( Cholesky(L'L) inv (L) )
[which we just showed was orthogonal]
(Cholesky(L'L) inv(L)) A = (Cholesky(L'L) inv(L)) L U
= Cholesky(L'L) U
And then left multiply through by its transpose (which is its inverse) so it vanishes from the left hand side and produces:
A = (Cholesky(L'L) inv(L) )' (Cholesky(L'L) U)
= ((inv(L))' (Cholesky(L'L))') (Cholesky(L'L) U)
= ( inv(L') (Cholesky(L'L))') (Cholesky(L'L) U)
This is now in the standard form A = QR, with
Q = inv(L') (Cholesky(L'L))' [orthogonal] R = Cholesky(L'L) U [upper triangular]
[Assuming I've not, somewhere above, blotched it.]
This page is http://www.cc.utah.edu/~nahaj/math/luul2qr.html © Copyright 2003 by John Halleck, All Rights Reserved. This snapshot was last modified on April 21st, 2008