Matrix Algebra

QR Factorization

Extending an orthonormal basis. Suppose that $\{\mathbf{u}_1,\ldots,\mathbf{u}_{k-1}\}$ be an orthonormal basis, and that a vector $\mathbf{v}$ does not belong to the subspace spanned by $\{\mathbf{u}_1,\ldots,\mathbf{u}_{k-1}\}$ . Then the orthogonal projection $\hat{\mathbf{v}}$ onto span $\{\mathbf{u}_1,\ldots,\mathbf{u}_{k-1}\}$ is given by

$\displaystyle \hat{\mathbf{v}} = r_1 \mathbf{u}_1 + \cdots + r_{k-1} \mathbf{u}_{k-1}$

where $r_i = \langle \mathbf{u}_i, \mathbf{v} \rangle$ for $i = 1,\ldots,k-1$ . Furthermore, we can introduce

$\displaystyle \mathbf{u}_{k} = (\mathbf{v} - \hat{\mathbf{v}}) / r_{k}$

where $r_{k} = \Vert\mathbf{v} - \hat{\mathbf{v}}\Vert$ . So that the set $\{\mathbf{u}_1,\ldots,\mathbf{u}_{k-1},\mathbf{u}_{k}\}$ becomes an orthonormal basis, and it uniquely determines

$\displaystyle \mathbf{v} = r_1 \mathbf{u}_1 + \cdots + r_{k-1} \mathbf{u}_{k-1} + r_{k} \mathbf{u}_{k}$

Gram-Schmidt Process. We can start with a set $\{\mathbf{a}_1,\ldots,\mathbf{a}_m\}$ of independent vectors in $\mathbb{R}^n$ , and construct an orthonormal basis $\{\mathbf{u}_1,\ldots,\mathbf{u}_m\}$ using the above procedure. Here we compute $r_{ij}$ 's and then build $\mathbf{u}_i$ 's by iteration.
Step 1: Compute $r_{11} = \Vert\mathbf{a}_1\Vert$ and obtain the unit vector $\mathbf{u}_1 = \mathbf{a}_1/r_{11}$ .
Step 2: Compute $r_{12} = \langle\mathbf{u}_1,\mathbf{a}_2\rangle$ and obtain the orthogonal projection

$\displaystyle \hat{\mathbf{a}}_2 = r_{12} \mathbf{u}_1$

onto $\mathbf{u}_1$ ; then compute $r_{22} = \Vert\mathbf{a}_2 - \hat{\mathbf{a}}_2\Vert$ and obtain the unit vector $\mathbf{u}_2 = (\mathbf{a}_2 - \hat{\mathbf{a}}_2)/r_{22}$ .
$\cdots\cdots\cdots$
Step : Compute $r_{i,m} = \langle\mathbf{u}_i,\mathbf{a}_m\rangle$ for $i=1,\ldots,m-1$ and obtain the orthogonal projection

$\displaystyle \hat{\mathbf{a}}_m = r_{1,m} \mathbf{u}_1 + \cdots + r_{m-1,m} \mathbf{u}_{m-1}$

onto span $\{\mathbf{u}_1,\ldots,\mathbf{u}_{m-1}\}$ , and compute $r_{mm} = \Vert\mathbf{a}_m - \hat{\mathbf{a}}_m\Vert$ and obtain the unit vector $\mathbf{u}_m = (\mathbf{a}_m - \hat{\mathbf{a}}_m)/r_{mm}$ .
The whole process is called the Gram-Schmidt process.

QR Factorization. The Gram-Schmidt process introduces the following relations:

$\mathbf{a}_1 = r_{11} \mathbf{u}_1$
$\mathbf{a}_2 = r_{12} \mathbf{u}_1 + r_{22} \mathbf{u}_2$ ( $= \hat{\mathbf{a}}_2 + r_{22} \mathbf{u}_2$ )
$\cdots\cdots\cdots$
$\mathbf{a}_m = r_{1m} \mathbf{u}_1 + \cdots + r_{mm} \mathbf{u}_m$ ( $= \hat{\mathbf{a}}_m + r_{mm} \mathbf{u}_m$ )

Here we can introduce the $n\times m$ matrices and by

$\displaystyle A = [\mathbf{a}_1 \cdots \mathbf{a}_m]$ and $\displaystyle Q = [\mathbf{u}_1 \cdots \mathbf{u}_m]$

and define the $m\times m$ upper triangular matrix

$\displaystyle R = \begin{bmatrix} r_{11} & r_{12} & \cdots & r_{1m} \\ 0 & r... ...\cdots & r_{2m} \\ \hdotsfor{4} \\ 0 & 0 & \cdots & r_{mm} \end{bmatrix}$

Then the set of the above vector equations is summarized as

, and it is called a QR factorization.

EXAMPLE 5. Let $A = \begin{bmatrix} 1 & -2 & -3 \\ 2 & 0 & -3 \\ 2 & 4 & 3 \end{bmatrix}$ . (a) Using the column vectors of the matrix , construct an orthonormal basis $\{\mathbf{u}_1,\mathbf{u}_2,\mathbf{u}_3\}$ by applying the Gram–Schmidt Process. (b) Obtain the QR factorization.