Proof. Let $\boldsymbol{A}$ be an $m\times{n}$ matrix with $n$ linearly independent column vectors and let $\boldsymbol{Q}$ be an $m\times{n}$ orthogonal matrixlink whose column vectors are constructed by applying the Gram-Schmidt process on the columns of $\boldsymbol{A}$. These matrices are shown below:

Note that for the Gram-Schmidt process to work, the column vectors of $\boldsymbol{A}$ must be linearly independent.

The set $\{\boldsymbol{q}_1,\boldsymbol{q}_2, \cdots,\boldsymbol{q}_n\}$ is an orthonormal basislink for $\mathbb{R}^n$. By theoremlink, each column vector of $\boldsymbol{A}$ can be expressed using this orthonormal basis like so:

By theoremlink, this can be written as:

By the propertylink of the Gram-Schmidt process, we have that:

Therefore, \eqref{eq:LOwUNEaa0XTeKlhE1sn} becomes:

Notice how the right-hand side is now a product of an orthogonal matrix $\boldsymbol{Q}$ and an upper triangular matrix which we denote as $\boldsymbol{R}$. Let's rewrite \eqref{eq:YO3WKNRMjx6l4ScZ6pw} in short-hand:

Next, by theoremlink, we have that $\boldsymbol{x}_i \cdot \boldsymbol{q}_i =\Vert\boldsymbol{v}_i\Vert$ for $i=1,2,\cdots,n$ where $\boldsymbol{v}_i$ is an orthogonal basis vector. Therefore, \eqref{eq:YO3WKNRMjx6l4ScZ6pw} can be written as:

Note the following:

• magnitude cannot be negative by definitionlink.

• a basis vector cannot be zero by definitionlink.

This means that $\Vert\boldsymbol{v}_i\Vert\gt0$ for $i=1,2,\cdots,n$. By theoremlink, a triangular matrix with non-zero diagonal entries is invertible. This completes the proof.

Proof. By theoremlink, if $\boldsymbol{A}$ is an invertible matrix, then the columns of $\boldsymbol{A}$ are linearly independent. By theoremlink, $\boldsymbol{A}$ can be $\boldsymbol{QR}$-factorized. This completes the proof.

Proof. The first step is to obtain an orthogonal matrix using the Gram-Schmidt process:

We start as follows:

Next, we find $\boldsymbol{v}_2$ that is orthogonal to $\boldsymbol{v}_1$ like so:

Let's turn $\boldsymbol{v}_1$ and $\boldsymbol{v}_2$ into unit vectors $\boldsymbol{q}_1$ and $\boldsymbol{q}_2$ respectively. $\boldsymbol{q}_1$ is:

Next, $\boldsymbol{q}_2$ is:

Therefore, the associated orthogonal matrix of $\boldsymbol{A}$ is:

Next, the upper triangular matrix $\boldsymbol{R}$ is:

Therefore, the $\boldsymbol{QR}$ factorization of $\boldsymbol{A}$ is:

Solution. We first must obtain the associated orthogonal matrix $\boldsymbol{Q}$ of $\boldsymbol{A}$ using the Gram-Schmidt process. Let $\boldsymbol{q}_1$ be:

The second vector $\boldsymbol{v}_2$ that is orthogonal to $\boldsymbol{q}_1$ is:

Let's convert $\boldsymbol{v}_2$ into an unit vector:

Therefore, the associated orthogonal matrix is:

The upper triangular matrix $\boldsymbol{R}$ is:

Therefore, the $\boldsymbol{QR}$ factorization of $\boldsymbol{A}$ is:

Proof. Suppose $\boldsymbol{A}$ can be $\boldsymbol{QR}$-factorized into $\boldsymbol{A}=\boldsymbol{Q}_1\boldsymbol{R}_1$ and $\boldsymbol{A}= \boldsymbol{Q}_2 \boldsymbol{R}_2$. Equating the two equations gives:

By theoremlink, because $\boldsymbol{R}_2$ is an upper triangular matrix, its inverse $\boldsymbol{R}^{-1}_2$ is also an upper triangular matrix. By theoremlink, $\boldsymbol{R}_1\boldsymbol{R}^{-1}_2$ is upper triangular because the product of two upper triangular matrices is also upper triangular.

Next, by theoremlink, the inverse of an orthogonal matrix is also orthogonal, which means $\boldsymbol{Q}^{-1}_1$ is orthogonal. By theoremlink, $\boldsymbol{Q}^{-1}_1\boldsymbol{Q}_2$ is also orthogonal because the product of two orthogonal matrices is orthogonal.

Therefore, the left-hand side of \eqref{eq:ueU7wc2mRd2QCZaVdNM} is upper triangular while the right-hand side is orthogonal. By theoremlink, upper triangular orthogonal matrices are diagonal matrices with diagonal entries $\pm1$. However, because the diagonal entries of $\boldsymbol{R}_1$ and $\boldsymbol{R}_2^{-1}$ are strictly positive, the diagonal entries of $\boldsymbol{R}_1\boldsymbol{R}^{-1}_2$ are also strictly positive by theoremlink. This means that:

Where $\boldsymbol{I}_n$ is the $n\times{n}$ identity matrix. Now, \eqref{eq:V8pFSzlUhOsQTF5m6aG} implies:

Also, \eqref{eq:V8pFSzlUhOsQTF5m6aG} implies:

Because $\boldsymbol{R}_1=\boldsymbol{R}_2$ and $\boldsymbol{Q}_1=\boldsymbol{Q}_2$, we conclude that $\boldsymbol{QR}$-factorization is unique. This completes the proof.

Proof. Recalllink that the least squares solution of the system $\boldsymbol{Ax}=\boldsymbol{b}$ is given by:

Now, we substitute $\boldsymbol{A}=\boldsymbol{QR}$ to get:

Here, we used theoremlink and theoremlink. This completes the proof.

Proof. We found the least squares solution by solving:

The least squares solution was:

Let's arrive at the same solution using $\boldsymbol{QR}$ factorization. As found in examplelink, the $\boldsymbol{QR}$ factorization of $\boldsymbol{A}$ is:

In this case, $\boldsymbol{R}$ is a diagonal matrix. By theoremlink, the inverse of $\boldsymbol{R}$ is another diagonal matrix whose diagonal entries are the reciprocals:

By theoremlink, the least squares solution is:

Great, this aligns with \eqref{eq:tfLTHmD6bgmLeH74dOt}.

Benefits of using QR factorization

We won't go into the technical details here but it turns out that solving certain problems such as the least squares problem via $\boldsymbol{QR}$ factorization offers higher numerical accuracy. In contrast, the standard approach of computing \eqref{eq:YwRlrMsBKoQdhcvtdix} using computer programs is that the result may be inaccurate due to rounding-off errors. In addition, an iterative algorithm called the $\boldsymbol{QR}$ algorithm, which is based on $\boldsymbol{QR}$ factorization, is also widely used to find eigenvalues of larger matrices efficiently.