Choosing a Matrix Factorization for a Task

Start With the Task and the Matrix

A matrix can often be factored in more than one way, but the useful choice depends on what you need to learn or compute. If a matrix is symmetric positive definite and the task is to solve a system, Cholesky exposes a triangular solve. If the task is least squares or an orthonormal basis for the columns, QR is often the natural choice. If you need to see rank, null directions, or the relative importance of directions, the singular value factorization (SVD) makes those features explicit.

These choices are not interchangeable. Cholesky has a strong definiteness requirement; QR is designed around orthonormal columns and triangular structure; the SVD applies to every real matrix and describes its action in orthogonal coordinates. The first decision is therefore not “Which factorization is best?” but “Which property does this task require me to expose?”

Definition: For a real symmetric positive definite matrix \(A\), a Cholesky factorization is \(A=LL^T\), where \(L\) is lower triangular with positive diagonal entries. A thin QR factorization of an \(m\times n\) matrix \(A\), with \(m\ge n\) and full column rank, is \(A=QR\), where \(Q^TQ=I_n\) and \(R\) is an invertible upper triangular \(n\times n\) matrix. A thin SVD is \(A=U_r\Sigma_r V_r^T\), where the columns of \(U_r\) and \(V_r\) are orthonormal, and \(\Sigma_r\) is diagonal with the positive singular values; \(r=\operatorname{rank}(A)\).

The SVD also has a full form \(A=U\Sigma V^T\), with square orthogonal \(U\) and \(V\); zero singular values can be included in \(\Sigma\). The compact form above omits the zero directions. This tutorial uses real matrices. The same selection principles extend to complex matrices by replacing transposes with conjugate transposes.

Cholesky: Use Positive Definiteness

Cholesky is suited to a symmetric positive definite matrix, especially when solving \(Ax=b\) or working with a quadratic form. For \(A=LL^T\), solving \(Ax=b\) reduces to two triangular systems: first \(Ly=b\), then \(L^Tx=y\). This avoids treating the original system as an unstructured dense solve.

The factorization also translates the quadratic form into squared length. For every vector \(x\),

x^TAx=x^TLL^Tx=(L^Tx)^T(L^Tx)=\|L^Tx\|_2^2.

If \(L\) is nonsingular, this quantity is positive whenever \(x\ne 0\), as required for positive definiteness. Thus Cholesky is not just a convenient way to store \(A\): its factor encodes the geometry of the quadratic form.

Worked Example: Solve a Positive Definite System by Cholesky

Let \(A=\begin{pmatrix}4&2\\2&3\end{pmatrix}\) and \(b=\begin{pmatrix}6\\5\end{pmatrix}\). The matrix is symmetric, and its leading principal minors are \(4>0\) and \(4(3)-2(2)=8>0\), so it is positive definite. Try \(L=\begin{pmatrix}2&0\\1&\sqrt{2}\end{pmatrix}\). Direct multiplication gives

LL^T= \begin{pmatrix}2&0\\1&\sqrt{2}\end{pmatrix} \begin{pmatrix}2&1\\0&\sqrt{2}\end{pmatrix} = \begin{pmatrix}4&2\\2&3\end{pmatrix}=A.

Solve \(Ly=b\). The first equation is \(2y_1=6\), so \(y_1=3\). The second is \(y_1+\sqrt{2}y_2=5\), so \(y_2=2/\sqrt{2}=\sqrt{2}\). Now solve \(L^Tx=y\). The second equation gives \(\sqrt{2}x_2=\sqrt{2}\), hence \(x_2=1\). The first gives \(2x_1+x_2=3\), hence \(x_1=1\). Checking, \(A\begin{pmatrix}1\\1\end{pmatrix}=\begin{pmatrix}6\\5\end{pmatrix}=b\).

Result: If \(A=LL^T\) with \(L\) nonsingular, then \(A\) is symmetric positive definite. Indeed, \(A^T=LL^T=A\). For \(x\ne0\), nonsingularity implies \(L^Tx\ne0\), so \(x^TAx=\|L^Tx\|_2^2>0\). Conversely, every real symmetric positive definite matrix has a Cholesky factorization with positive diagonal entries, by the Cholesky existence theorem. Therefore, for a symmetric matrix, the existence of such a factor is equivalent to positive definiteness.

This is a useful selection check: Cholesky is not the general-purpose choice for a symmetric matrix merely because it is symmetric. Positive definiteness is required. A symmetric positive semidefinite matrix may be singular and need not have a nonsingular Cholesky factor; a general rectangular matrix does not meet Cholesky’s form at all.

QR: Preserve Orthogonality for Least Squares

For a full-column-rank \(m\times n\) matrix \(A\), with \(m\ge n\), thin QR writes its columns in an orthonormal basis \(Q\), with their coordinates recorded in \(R\). This structure is useful when finding an orthonormal basis for the column space or solving a least-squares problem. The requirement \(Q^TQ=I_n\) means \(Q\) preserves lengths of vectors in \(\mathbb{R}^n\).

To see why QR solves least squares, consider minimizing \(\|b-A\beta\|_2\) over \(\beta\in\mathbb{R}^n\). Since \(A=QR\), write \(c=Q^Tb\). Decompose \(b\) into its projection onto the columns of \(Q\) and its orthogonal remainder: \(b=Qc+(I-QQ^T)b\). The two terms \(Q(c-R\beta)\) and \((I-QQ^T)b\) are orthogonal. Thus

\|b-A\beta\|_2^2 =\|Q(c-R\beta)\|_2^2+\|(I-QQ^T)b\|_2^2 =\|c-R\beta\|_2^2+\|(I-QQ^T)b\|_2^2.

The second equality uses \(Q^TQ=I_n\), which gives \(\|Qz\|_2^2=z^TQ^TQz=\|z\|_2^2\). The second term does not depend on \(\beta\), and the first is minimized to zero by the unique solution \(R\hat{\beta}=c\), because \(R\) is invertible. Hence \(\hat{\beta}=R^{-1}Q^Tb\) is the unique least-squares minimizer. The residual is \((I-QQ^T)b\), which is orthogonal to every column of \(A\). \(\square\)

This derivation also explains why QR is preferable to forming \(A^TA\) in many numerical least-squares computations. If the singular values of \(A\) are \(\sigma_1,\ldots,\sigma_n>0\), the eigenvalues of \(A^TA\) are \(\sigma_1^2,\ldots,\sigma_n^2\). Consequently, the ratio of largest to smallest eigenvalue becomes the square of the corresponding singular-value ratio. Forming \(A^TA\) can therefore magnify conditioning problems.

Worked Example: Use QR for a Least-Squares Fit

Take \(A=\begin{pmatrix}1&1\\1&0\\0&1\end{pmatrix}\) and \(b=\begin{pmatrix}2\\1\\0\end{pmatrix}\). The columns are \(a_1=(1,1,0)^T\) and \(a_2=(1,0,1)^T\). Normalizing the first column gives \(q_1=(1,1,0)^T/\sqrt{2}\), so \(r_{11}=\sqrt{2}\). Then \(r_{12}=q_1^Ta_2=1/\sqrt{2}\). Removing the component along \(q_1\) leaves \(a_2-r_{12}q_1=(1/2,-1/2,1)^T\), whose norm is \(\sqrt{6}/2\). Therefore \(q_2=(1,-1,2)^T/\sqrt{6}\), and

Q=\begin{pmatrix} 1/\sqrt{2}&1/\sqrt{6}\\ 1/\sqrt{2}&-1/\sqrt{6}\\ 0&2/\sqrt{6} \end{pmatrix}, \qquad R=\begin{pmatrix}\sqrt{2}&1/\sqrt{2}\\0&\sqrt{6}/2\end{pmatrix}.

The least-squares right-hand side is \(Q^Tb=(3/\sqrt{2},1/\sqrt{6})^T\). Solving \(R\hat{\beta}=Q^Tb\), the second equation gives \(\hat{\beta}_2=(1/\sqrt{6})/(\sqrt{6}/2)=1/3\). The first gives \(\sqrt{2}\hat{\beta}_1+1/(3\sqrt{2})=3/\sqrt{2}\), so \(\hat{\beta}_1=4/3\). The fitted vector is \(A\hat{\beta}=(5/3,4/3,1/3)^T\), and the residual is \(b-A\hat{\beta}=(1/3,-1/3,-1/3)^T\). Its dot products with \(a_1\) and \(a_2\) are both zero, verifying the least-squares orthogonality condition.

SVD: Expose Rank and Directional Structure

The SVD applies to every real matrix, whether square or rectangular, full rank or rank deficient. Each positive singular value describes the factor by which the matrix scales a particular orthogonal input direction; the corresponding columns of \(V_r\) give input directions, and the columns of \(U_r\) give output directions. The number of positive singular values is the rank.

This rank statement follows directly from the factorization. In the full SVD, multiplication by orthogonal \(U\) and \(V^T\) does not change rank, since each is invertible. The diagonal matrix \(\Sigma\) has rank equal to its number of nonzero diagonal entries. Therefore \(\operatorname{rank}(A)\) equals the number of positive singular values. In the compact SVD, \(A=U_r\Sigma_rV_r^T\), the diagonal matrix \(\Sigma_r\) is invertible, and the orthonormal columns show that the factorization has rank \(r\). This gives an explicit representation of the rank-\(r\) structure, not just a test for it. \(\square\)

Worked Example: Reveal Rank With an SVD

Consider \(A=\begin{pmatrix}1&2\\2&4\\0&0\end{pmatrix}\). Set \(u=(1,2,0)^T/\sqrt{5}\) and \(v=(1,2)^T/\sqrt{5}\). Both are unit vectors, and

5uv^T =5\left(\frac{1}{\sqrt{5}}\begin{pmatrix}1\\2\\0\end{pmatrix}\right) \left(\frac{1}{\sqrt{5}}\begin{pmatrix}1&2\end{pmatrix}\right) = \begin{pmatrix}1&2\\2&4\\0&0\end{pmatrix}=A.

Thus this is a compact SVD with one singular value, \(5\), and \(A\) has rank one. It also shows the directional action: \(Av=5u\). A unit vector perpendicular to \(v\) is \(w=(-2,1)^T/\sqrt{5}\); here \(Aw=0\), since each row of \(A\) is proportional to \((1,2)\). The SVD makes both the single active direction and the null direction visible.

Choosing Among the Three

Task or structure	Natural choice	What the factorization provides	Important condition
Solve a symmetric positive definite system	Cholesky	Two triangular systems and a factor encoding the quadratic form	The matrix must be positive definite
Find a least-squares solution or orthonormal column basis	QR	Orthonormal column coordinates and a triangular solve	Thin QR with invertible \(R\) requires full column rank
Identify rank, null directions, or direction-specific scaling	SVD	Singular values and paired input/output directions	No definiteness or full-rank assumption is required

The table is a guide, not a rule that each matrix has only one usable factorization. A positive definite matrix can also have an SVD, for example, but if the task is a linear solve, Cholesky usually provides the needed structure more directly. Conversely, when rank is uncertain or a matrix is rectangular, the SVD may answer questions that Cholesky cannot address.

Common Mistake: Choose by Familiarity Instead of Structure

A frequent error is to apply Cholesky just because a matrix is symmetric, or to use a thin full-column-rank QR formula when the columns are dependent. Symmetry alone does not imply positive definiteness, and rank deficiency means the \(R\) factor in that QR setup is not invertible. The correction is to check the hypotheses before choosing: verify positive definiteness for Cholesky, verify full column rank when relying on the invertible-\(R\) least-squares argument, and consider SVD when the rank or null space is central.

Another pitfall is to choose SVD automatically because it is the most general factorization. Generality is valuable when rank and directional structure matter, but it may be more computation than is needed for a positive definite solve or a well-conditioned full-rank least-squares problem. Match the factorization to the information the analysis requires.

Key takeaway: Choose Cholesky for positive definite structure, QR for orthonormal columns and least squares, and SVD for rank and directional structure. A useful factorization is one whose assumptions fit the matrix and whose output fits the task.

Check Your Understanding

For each question, identify the relevant matrix property and explain which factorization best exposes what is needed.

A symmetric matrix is known to be positive definite, and the goal is to solve \(Ax=b\). Which factorization is the natural choice, and what two systems does it produce?
Why does the QR least-squares derivation require \(R\) to be invertible for its unique-solution conclusion?
A rectangular matrix may be rank deficient, and the goal is to identify its null directions. Which factorization is most informative, and what part of it reveals the rank?
Why is symmetry alone insufficient to justify using Cholesky factorization?
Explain why forming \(A^TA\) can make conditioning worse in a least-squares calculation.