Decompositions of matrices (QR, SVD, LU) | Step 8

Problem Description
Prove that for any matrix M \in \mathbb{C}^{n \times n} there exists a unitary matrix Q and a lower-triangular matrix L such that M=LQ .
Source: Stepic Linear Algebra: Problems and Methods.

Problem Dissection
The proof it is almost equal to the QR decomposition:
Case 1: M is non degenerate
Let Q be a matrix of the normalized columns in reverse order of M using Gram-Schmidt orthogonalization algorithm.
In other words: If M=[c_1 | c_2 | ... | c_{n-1} c_n] where c_i is a column vector, after Gram-Schmidt algorithm, we get an ONB Q'=[q_1 | q_2 | ... | q_n] .
Remember that in the i-th iteration of Gram-Schmidt algorithm, we subtract from the i-th vector the projections of all the previous vectors, so the transition matrix S’ from M to Q’ is upper triangular
If we reverse the order of the columns in S’ we get a lower triangular matrix S. However, now S will transform the matrix [c_1 | c_2 | ... | c_n] to Q=[q_n | ... | q_2 | q_1].
So S \times M=Q since S is lower triangular and non degenerate, it’s inverse will be lower triangular too: M=S^{-1}Q.
It just remains to prove that Q is unitary. If Q is unitary, then Q* \overline{ Q^{T} }=E (E is the identity matrix). note that the cell (i,j) of Q* \overline{ Q^{T} }=E is the inner product of the column i with the conjugate of the column j (both columns from matrix Q).
Note that each pair of columns of Q are perpendicular (because it is an ONB) so if i \neq j , then
(column_ i, column_j)=(\overline{ column_j },column_i)=0
(column_j, column_i)=(\overline{ column_i },column_j)=0 .
Also note that if i=j , then (column_i, column_j) is just the modulo of the column i, and it is one (again by definition of an ONB). So Q* \overline{ Q^{T} } is the identity matrix and therefore Q is unitary.

Case 2: M is degenerate
Let’s apply the same algorithm, but just with the linearly independent columns of M, and complete the remaining columns in order to get a base of C^{n}

Author: Alei Reyes

I know that I know nothing

Leave a comment