If an LU factorization of a non-sigular matrix exists, then a QR factorization of that matrix exists. [Constructive proof.]
A' is used for transpose(A)
inv(A) is used for the matrix inverse of A
Cholesky(A) for a symmetric matrix A is used to mean the UPPER triangular factor of A=U'U
Cholesky'(A) means [Cholesky(A)]'
I will be using both the LU and UL factorizations in the derivation below, although only the LU factorization is used in the final result. [I think it is obvious that if the LU factorization exists, then the UL does also.]
Obviously, U can't be used for the Upper factors of both LU and UL, and likewise L can't be used for both L's. So L and U will be used in the traditional manner for the LU factorization, and T (top) and B (bottom) will be used for the UL [TB] factorization.
Consider a matrix A = TB, where B is non-singular lower triangular, and T is (possibly degenerate) upper triangular.
If a matrix with a TB factorization is orthogonal, then the matrix multiplied by its transpose must be the identity:
A' A = I
(TB)'(TB) = I [A = TB]
B'T' TB = I [(xy)' = y'x']
T' T = inv(B')inv(B)
T' T = inv(BB')
Cholesky(T' T) = Cholesky(inv(BB'))
T = Cholesky(inv(BB')) [Since T is upper triangular]
So if a non-singular lower trianguler matrix B is given, a matching upper trianguler T needed to form an orthogonal matrix is uniquely determined...
A = TB = Cholesky(inv(BB')) B
So any matrix of the form Cholesky(inv(BB'))B for any non-singular lower triangular B must be 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)
(for any non-singular lower triangular B) are also orthogonal. And their transposes are also, obviously, orthogonal also.
[Note that this has B'B and not the BB' of the non-inverse case.]
Consider A = LU, where L is non-singular lower triangular, and U is (possibly degenerate) upper triangular
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) 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]
And, oddly enough, the final QR factorization doesn't depend on U being non-singular.
This page is http://www.cc.utah.edu/~nahaj/math/luul2qr.html © Copyright 2003-2010 by John Halleck, All Rights Reserved. This snapshot was last modified on August 19th, 2011 And the underlying file was last modified on January 20th, 2010