1
$\begingroup$

Let $A \in \mathbb{R^{n \times n}}$ be an nonsingular matrix and $LL^T$ the Cholesky decomposition of $A^TA$.

How to show that it exists a QR factorization with $Q=A(L^T)^{-1}$?

I tried this:

$A^TA=R^TQ^TQR=L^TL \Leftrightarrow (R^T)^{-1}A^TA=Q^TQR=(R^T)^{-1}L^TL$

Here I don't see how to continue. I tried to rearrange this equality, but I don't get the result.

$\endgroup$
  • $\begingroup$ Apparently you were asked to show existence of a particular $QR$ factorization of $A$. Start by showing the $Q$ you have defined is orthogonal. Then come up with a way to define an upper triangular $R$ that makes $A=QR$. $\endgroup$ – hardmath Jan 16 at 13:04
  • 1
    $\begingroup$ It's $Q^TQ=(A(L^T)^{-1})^T(A(L^T)^{-1})=L^{-1}A^TA(L^T)^{-1}=L^{-1}LL^T(L^T)^{-1}=I$, so $Q$ is orthogonal. Then $A=QL^T$ and $R=L^T$. Is that all to prove the existence of a QR factorization with $Q=A(L^T)^{-1}$ when $LL^T$ is the Cholesky decomposition of $A^TA$? $\endgroup$ – Tartulop Jan 16 at 16:51
  • 1
    $\begingroup$ Yes, you are correct. If you know that nonsingular $A^T A = L L^T$ where $L$ is lower triangular, then you easily construct a $QR$ factorization just as your Comment shows. I suggest you write it up with a bit more detail as an Answer to your own Question. $\endgroup$ – hardmath Jan 16 at 17:28
1
$\begingroup$

Let's unpack the solution that the OP arrived at in Comments, for the sake of completeness. We assume $A$ is a nonsingular $n\times n$ (square) real matrix.

Suppose that $A^TA$ has Cholesky decomposition $LL^T$ where $L$ is lower triangular. We will show that $A = QR$ is a factorization with $Q$ orthogonal and $R$ upper triangular when $Q=A(L^T)^{-1}$ and $R = L^T$.

First note that by our assumption $A^TA$ is symmetric positive definite and thus has the required Cholesky decomposition, and that $L$ is also nonsingular. The definition of $Q$ therefore makes sense, and the calculation that it is orthogonal is straightforward:

$$ \begin{align*} QQ^T &= A(L^T)^{-1} L^{-1} A^T \\ &= A(LL^T)^{-1} A^T \\ &= A(A^TA)^{-1} A^T \\ &= AA^{-1}(A^T)^{-1} A^T \\ &= I \end{align*} $$

Here we've used familiar facts that both inverse and transpose of a matrix product reverse the order of that product, and that inverse commutes with transpose.

Since $R = L^T$ is obviously upper triangular, it remains only to verify the factorization of $A$ that results:

$$ QR = A(L^T)^{-1} L^T = A $$

In this last calculation only the associativity of matrix multiplication is needed.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.