Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

6.1: Orthonormal bases and QR factorization

In Chapter 5.3, we saw that a subspace can have many different bases. Our focus in Chapter 6 will be finding a special type of basis – an orthonormal basis – for a given subspace. Orthonormal bases are not new; we studied them in Chapter 2, and they are convenient to work with. We’ll recap their usefulness as we go.


Orthonormal bases

Let’s start with the plane

P={[xyz]∈R3:x+y−z=0}.P=\left\{\begin{bmatrix}x\\y\\z\end{bmatrix}\in\mathbb R^3:x+y-z=0\right\}.

This is a subspace: it contains 0⃗\vec0, and adding vectors or taking scalar multiples preserves the equation x+y−z=0x+y-z=0.

One basis of PP is

v⃗1=[101],v⃗2=[112].\vec v_1=\begin{bmatrix}1\\0\\1\end{bmatrix},\qquad \vec v_2=\begin{bmatrix}1\\1\\2\end{bmatrix}.

Both vectors lie on the plane, and neither is a multiple of the other. They span the plane: if z=x+yz=x+y, then

[xyz]=(x−y)[101]+y[112].\begin{bmatrix}x\\y\\z\end{bmatrix} =(x-y)\begin{bmatrix}1\\0\\1\end{bmatrix} +y\begin{bmatrix}1\\1\\2\end{bmatrix}.

But these two basis vectors aren’t perpendicular: their dot product is 3. Let’s find a basis that’s more convenient for calculating lengths and coordinates.

We’ll use v⃗1,v⃗2,…\vec v_1,\vec v_2,\ldots for the original basis vectors and u⃗1,u⃗2,…\vec u_1,\vec u_2,\ldots for the orthonormal ones.

Loading...

The Gram-Schmidt process

Return to our basis of the plane x+y−z=0x+y-z=0:

v⃗1=[101],v⃗2=[112].\vec v_1=\begin{bmatrix}1\\0\\1\end{bmatrix},\qquad \vec v_2=\begin{bmatrix}1\\1\\2\end{bmatrix}.

We’ll keep the direction of the first vector and adjust the second to make it perpendicular to the first.

  • Normalize the first vector: Dividing a nonzero vector by its length is called normalizing it. Since ∥v⃗1∥=2\|\vec v_1\|=\sqrt2, set

    u⃗1=v⃗1∥v⃗1∥=12[101].\vec u_1=\frac{\vec v_1}{\|\vec v_1\|} =\frac1{\sqrt2}\begin{bmatrix}1\\0\\1\end{bmatrix}.

    This vector has length one and points in the same direction as v⃗1\vec v_1.

  • Subtract the projection: Let ℓ=span⁡(u⃗1)\ell=\operatorname{span}(\vec u_1). Recall from Chapter 2.7 that v⃗2\vec v_2 splits into a component along ℓ\ell and a component perpendicular to ℓ\ell:

    v⃗2=proj⁡ℓ(v⃗2)⏟along ℓ+(v⃗2−proj⁡ℓ(v⃗2))⏟perpendicular to ℓ.\vec v_2= \underbrace{\operatorname{proj}_{\ell}(\vec v_2)}_{\text{along }\ell} +\underbrace{\bigl(\vec v_2-\operatorname{proj}_{\ell}(\vec v_2)\bigr)}_{\text{perpendicular to }\ell}.

    Since u⃗1\vec u_1 has length one, the projection formula simplifies to

    proj⁡ℓ(v⃗2)=(v⃗2⋅u⃗1)u⃗1=3212[101]=32[101].\operatorname{proj}_{\ell}(\vec v_2) =(\vec v_2\cdot\vec u_1)\vec u_1 =\frac3{\sqrt2}\frac1{\sqrt2}\begin{bmatrix}1\\0\\1\end{bmatrix} =\frac32\begin{bmatrix}1\\0\\1\end{bmatrix}.

    We want the perpendicular component, so subtract this projection:

    w⃗2=v⃗2−proj⁡ℓ(v⃗2)=[112]−32[101]=12[−121].\vec w_2=\vec v_2-\operatorname{proj}_{\ell}(\vec v_2) =\begin{bmatrix}1\\1\\2\end{bmatrix} -\frac32\begin{bmatrix}1\\0\\1\end{bmatrix} =\frac12\begin{bmatrix}-1\\2\\1\end{bmatrix}.
  • Normalize the remaining vector: The remaining vector is perpendicular to u⃗1\vec u_1, but it doesn’t yet have length one. Its length is

    ∥w⃗2∥=14+1+14=62.\|\vec w_2\|=\sqrt{\frac14+1+\frac14}=\frac{\sqrt6}{2}.

    Dividing by this length gives

    u⃗2=w⃗2∥w⃗2∥=16[−121].\vec u_2=\frac{\vec w_2}{\|\vec w_2\|} =\frac1{\sqrt6}\begin{bmatrix}-1\\2\\1\end{bmatrix}.

Let’s check:

u⃗1⋅u⃗2=−1+0+126=0,∥u⃗1∥2=1+0+12=1,∥u⃗2∥2=1+4+16=1.\vec u_1\cdot\vec u_2=\frac{-1+0+1}{\sqrt2\sqrt6}=0, \qquad \|\vec u_1\|^2=\frac{1+0+1}{2}=1, \qquad \|\vec u_2\|^2=\frac{1+4+1}{6}=1.

The span hasn’t changed. Each new vector is a combination of the old ones, and we can recover the old vectors by undoing the subtraction and rescaling. Thus u⃗1,u⃗2\vec u_1,\vec u_2 form an orthonormal basis of PP.

This is the idea behind the Gram-Schmidt process: subtract the projections along the directions we’ve already found, then normalize what remains.

Loading...

Move the slider to follow the Gram-Schmidt process for the two basis vectors of PP, from the first normalization to the completed orthonormal basis.

Loading...

Coordinates

Let’s use our new basis to describe another vector on the plane:

b⃗=[325].\vec b=\begin{bmatrix}3\\2\\5\end{bmatrix}.

It lies on the plane x+y−z=0x+y-z=0 because 3+2−5=03+2-5=0. We want coefficients c1,c2c_1,c_2 such that

b⃗=c1u⃗1+c2u⃗2.\vec b=c_1\vec u_1+c_2\vec u_2.

We could solve a system of equations, but orthonormality gives us a quicker way. Take the dot product with u⃗1\vec u_1:

b⃗⋅u⃗1=c1(u⃗1⋅u⃗1)+c2(u⃗2⋅u⃗1)=c1.\vec b\cdot\vec u_1 =c_1(\vec u_1\cdot\vec u_1)+c_2(\vec u_2\cdot\vec u_1) =c_1.

The first dot product is 1 and the second is 0, so only c1c_1 remains. Taking the dot product with u⃗2\vec u_2 similarly gives c2c_2. Therefore,

c1=3+0+52=42,c2=−3+4+56=6.c_1=\frac{3+0+5}{\sqrt2}=4\sqrt2, \qquad c_2=\frac{-3+4+5}{\sqrt6}=\sqrt6.

Substituting the vectors back in checks our answer:

42u⃗1+6u⃗2=4[101]+[−121]=[325]=b⃗.4\sqrt2\vec u_1+\sqrt6\vec u_2 =4\begin{bmatrix}1\\0\\1\end{bmatrix} +\begin{bmatrix}-1\\2\\1\end{bmatrix} =\begin{bmatrix}3\\2\\5\end{bmatrix}=\vec b.

QR factorization

Return to our worked example with v⃗1=[101]\vec v_1=\begin{bmatrix}1\\0\\1\end{bmatrix} and v⃗2=[112]\vec v_2=\begin{bmatrix}1\\1\\2\end{bmatrix}. We now have two bases of the same plane. How are they related?

For the first vector, we divided by 2\sqrt2. For the second, we subtracted 32u⃗1\frac3{\sqrt2}\vec u_1 and divided the remainder by 62\frac{\sqrt6}2. Undoing these steps gives

v⃗1=2u⃗1,v⃗2=32u⃗1+62u⃗2.\vec v_1=\sqrt2\vec u_1,\qquad \vec v_2=\frac3{\sqrt2}\vec u_1+\frac{\sqrt6}2\vec u_2.

Put the original vectors in the columns of AA and the orthonormal vectors in the columns of QQ. These two equations become one matrix equation:

[110112]⏟A=[1/2−1/602/61/21/6]⏟Q[23/206/2]⏟R.\underbrace{\begin{bmatrix}1&1\\0&1\\1&2\end{bmatrix}}_A =\underbrace{\begin{bmatrix} 1/\sqrt2&-1/\sqrt6\\ 0&2/\sqrt6\\ 1/\sqrt2&1/\sqrt6 \end{bmatrix}}_Q \underbrace{\begin{bmatrix}\sqrt2&3/\sqrt2\\0&\sqrt6/2\end{bmatrix}}_R.

Remember how matrix multiplication works column by column. The first column of QRQR is 2u⃗1+0u⃗2=v⃗1\sqrt2\vec u_1+0\vec u_2=\vec v_1. The second is 32u⃗1+62u⃗2=v⃗2\frac3{\sqrt2}\vec u_1+\frac{\sqrt6}2\vec u_2=\vec v_2.

In our example, QQ has shape 3×23\times2 and RR has shape 2×22\times2. Each column of RR records the coefficients for one original basis vector. The zero appears because recovering v⃗1\vec v_1 only requires u⃗1\vec u_1; no u⃗2\vec u_2 is needed.

We can start with a matrix instead of a named subspace. If the columns of AA are linearly independent, they form a basis of colsp⁡(A)\operatorname{colsp}(A). Applying the Gram-Schmidt process gives an orthonormal basis of that same column space. Those vectors become the columns of QQ, and expressing the original columns using them gives RR.

For example, let’s find a QR factorization of

A=[3−147].A=\begin{bmatrix}3&-1\\4&7\end{bmatrix}.

Its columns v⃗1=[34]\vec v_1=\begin{bmatrix}3\\4\end{bmatrix} and v⃗2=[−17]\vec v_2=\begin{bmatrix}-1\\7\end{bmatrix} aren’t multiples of one another, so they form a basis of R2\mathbb R^2.

  • Normalize the first vector: The first column has length 5, giving

    u⃗1=15[34].\vec u_1=\frac15\begin{bmatrix}3\\4\end{bmatrix}.
  • Subtract the projection: For the second column, calculate the projection coefficient and subtract the projection:

    v⃗2⋅u⃗1=−3+285=5,w⃗2=v⃗2−5u⃗1=[−17]−[34]=[−43].\vec v_2\cdot\vec u_1=\frac{-3+28}{5}=5, \qquad \vec w_2=\vec v_2-5\vec u_1 =\begin{bmatrix}-1\\7\end{bmatrix}-\begin{bmatrix}3\\4\end{bmatrix} =\begin{bmatrix}-4\\3\end{bmatrix}.
  • Normalize the remaining vector: The remaining vector has length 5. We still need to divide by that length:

    u⃗2=15[−43].\vec u_2=\frac15\begin{bmatrix}-4\\3\end{bmatrix}.

Both vectors now have length one, and their dot product is (−12+12)/25=0(-12+12)/25=0.

We don’t need a new calculation to find RR. Put back what we subtracted and record the lengths:

v⃗1=5u⃗1,v⃗2=5u⃗1+5u⃗2.\vec v_1=5\vec u_1,\qquad \vec v_2=5\vec u_1+5\vec u_2.

Therefore,

[3−147]=[3/5−4/54/53/5]⏟Q[5505]⏟R.\begin{bmatrix}3&-1\\4&7\end{bmatrix} =\underbrace{\begin{bmatrix}3/5&-4/5\\4/5&3/5\end{bmatrix}}_Q \underbrace{\begin{bmatrix}5&5\\0&5\end{bmatrix}}_R.

Here QQ is square: its two columns span all of R2\mathbb R^2. In our plane example, QQ had two columns with three entries each, spanning a plane inside R3\mathbb R^3.


The general process

Suppose we start with three linearly independent vectors v⃗1,v⃗2,v⃗3\vec v_1,\vec v_2,\vec v_3 in Rn\mathbb R^n. At each step, we’ll show the current original vector in blue and the previously constructed unit vectors in orange.

  • First vector: Divide by its length:

    u⃗1=v⃗1∥v⃗1∥.\vec u_1=\frac{\textcolor{#3d81f6}{\vec v_1}}{\|\textcolor{#3d81f6}{\vec v_1}\|}.
  • Second vector: Subtract its projection onto the line along u⃗1\vec u_1, then normalize:

    w⃗2=v⃗2−(v⃗2⋅u⃗1)u⃗1,u⃗2=w⃗2∥w⃗2∥.\vec w_2=\textcolor{#3d81f6}{\vec v_2}-(\textcolor{#3d81f6}{\vec v_2}\cdot\textcolor{orange}{\vec u_1})\textcolor{orange}{\vec u_1}, \qquad \vec u_2=\frac{\vec w_2}{\|\vec w_2\|}.
  • Third vector: We now need a vector perpendicular to both u⃗1\vec u_1 and u⃗2\vec u_2. Subtract both projections:

    w⃗3=v⃗3−(v⃗3⋅u⃗1)u⃗1−(v⃗3⋅u⃗2)u⃗2.\vec w_3=\textcolor{#3d81f6}{\vec v_3}-(\textcolor{#3d81f6}{\vec v_3}\cdot\textcolor{orange}{\vec u_1})\textcolor{orange}{\vec u_1}-(\textcolor{#3d81f6}{\vec v_3}\cdot\textcolor{orange}{\vec u_2})\textcolor{orange}{\vec u_2}.

    Because u⃗1\vec u_1 and u⃗2\vec u_2 are perpendicular, subtracting a component along one doesn’t change the component along the other. For example,

    w⃗3⋅u⃗1=v⃗3⋅u⃗1−(v⃗3⋅u⃗1)(1)−(v⃗3⋅u⃗2)(0)=0.\vec w_3\cdot\vec u_1 =\vec v_3\cdot\vec u_1-(\vec v_3\cdot\vec u_1)(1)-(\vec v_3\cdot\vec u_2)(0)=0.

    Similarly, w⃗3⋅u⃗2=0\vec w_3\cdot\vec u_2=0. Now normalize:

    u⃗3=w⃗3∥w⃗3∥.\vec u_3=\frac{\vec w_3}{\|\vec w_3\|}.

Why can we divide by these lengths? If w⃗3\vec w_3 were zero, then v⃗3\vec v_3 would be a combination of u⃗1,u⃗2\vec u_1,\vec u_2, and hence of v⃗1,v⃗2\vec v_1,\vec v_2. That would contradict the independence of the original vectors. The same reasoning ensures w⃗2≠0⃗\vec w_2\ne\vec0.

The same procedure works for any number of linearly independent vectors.

Each new unit vector is a combination of the original vectors, and putting back the projections expresses each original vector using the unit vectors. Their spans therefore agree.

QR factorization with three columns

For a matrix AA of shape 3×33\times3 with linearly independent columns v⃗1,v⃗2,v⃗3\vec v_1,\vec v_2,\vec v_3, we can use these steps to write down QQ and RR. Rearranging the equations above gives

v⃗1=∥v⃗1∥u⃗1,v⃗2=(v⃗2⋅u⃗1)u⃗1+∥w⃗2∥u⃗2,v⃗3=(v⃗3⋅u⃗1)u⃗1+(v⃗3⋅u⃗2)u⃗2+∥w⃗3∥u⃗3.\begin{aligned} \vec v_1&=\|\vec v_1\|\vec u_1,\\ \vec v_2&=(\vec v_2\cdot\vec u_1)\vec u_1+\|\vec w_2\|\vec u_2,\\ \vec v_3&=(\vec v_3\cdot\vec u_1)\vec u_1+(\vec v_3\cdot\vec u_2)\vec u_2+\|\vec w_3\|\vec u_3. \end{aligned}

These three equations give the factorization

[∣∣∣v⃗1v⃗2v⃗3∣∣∣]⏟A=[∣∣∣u⃗1u⃗2u⃗3∣∣∣]⏟Q[∥v⃗1∥v⃗2⋅u⃗1v⃗3⋅u⃗10∥w⃗2∥v⃗3⋅u⃗200∥w⃗3∥]⏟R.\underbrace{\begin{bmatrix}|&|&|\\\vec v_1&\vec v_2&\vec v_3\\|&|&|\end{bmatrix}}_A =\underbrace{\begin{bmatrix}|&|&|\\\vec u_1&\vec u_2&\vec u_3\\|&|&|\end{bmatrix}}_Q \underbrace{\begin{bmatrix} \|\vec v_1\|&\vec v_2\cdot\vec u_1&\vec v_3\cdot\vec u_1\\ 0&\|\vec w_2\|&\vec v_3\cdot\vec u_2\\ 0&0&\|\vec w_3\| \end{bmatrix}}_R.

Each column of RR contains the coefficients for one original column of AA. The diagonal entries are the lengths we divided by, and the entries above the diagonal are the dot products used to find the projections. The zeros below the diagonal appear because each v⃗i\vec v_i is a combination of only u⃗1,…,u⃗i\vec u_1,\ldots,\vec u_i.

Let’s apply the procedure to

A=[12310111−1].A=\begin{bmatrix}1&2&3\\1&0&1\\1&1&-1\end{bmatrix}.

Call its columns v⃗1,v⃗2,v⃗3\vec v_1,\vec v_2,\vec v_3, in that order.

  • First column: Its length is 3\sqrt3, so

    u⃗1=13[111].\vec u_1=\frac1{\sqrt3}\begin{bmatrix}1\\1\\1\end{bmatrix}.
  • Second column: Find its component along u⃗1\textcolor{orange}{\vec u_1} and subtract:

    v⃗2⋅u⃗1=2+0+13=3,w⃗2=[201]−[111]=[1−10].\textcolor{#3d81f6}{\vec v_2}\cdot\textcolor{orange}{\vec u_1}=\frac{2+0+1}{\sqrt3}=\sqrt3,\qquad \vec w_2=\begin{bmatrix}2\\0\\1\end{bmatrix}-\begin{bmatrix}1\\1\\1\end{bmatrix} =\begin{bmatrix}1\\-1\\0\end{bmatrix}.

    The remaining vector has length 2\sqrt2, so

    u⃗2=12[1−10].\vec u_2=\frac1{\sqrt2}\begin{bmatrix}1\\-1\\0\end{bmatrix}.
  • Third column: This time, we need two coefficients:

    v⃗3⋅u⃗1=3+1−13=3,v⃗3⋅u⃗2=3−1+02=2.\textcolor{#3d81f6}{\vec v_3}\cdot\textcolor{orange}{\vec u_1}=\frac{3+1-1}{\sqrt3}=\sqrt3,\qquad \textcolor{#3d81f6}{\vec v_3}\cdot\textcolor{orange}{\vec u_2}=\frac{3-1+0}{\sqrt2}=\sqrt2.

    Subtract both components:

    w⃗3=[31−1]−[111]−[1−10]=[11−2].\vec w_3=\begin{bmatrix}3\\1\\-1\end{bmatrix} -\begin{bmatrix}1\\1\\1\end{bmatrix} -\begin{bmatrix}1\\-1\\0\end{bmatrix} =\begin{bmatrix}1\\1\\-2\end{bmatrix}.

    The remaining vector has length 6\sqrt6, so

    u⃗3=16[11−2].\vec u_3=\frac1{\sqrt6}\begin{bmatrix}1\\1\\-2\end{bmatrix}.

The three unnormalized directions have pairwise dot products 1−1=01-1=0, 1+1−2=01+1-2=0, and 1−1=01-1=0. After normalization, they form an orthonormal basis of R3\mathbb R^3.

We have already calculated every entry of RR:

A=[1/31/21/61/3−1/21/61/30−2/6]⏟Q[333022006]⏟R.A= \underbrace{\begin{bmatrix} 1/\sqrt3&1/\sqrt2&1/\sqrt6\\ 1/\sqrt3&-1/\sqrt2&1/\sqrt6\\ 1/\sqrt3&0&-2/\sqrt6 \end{bmatrix}}_Q \underbrace{\begin{bmatrix}\sqrt3&\sqrt3&\sqrt3\\0&\sqrt2&\sqrt2\\0&0&\sqrt6\end{bmatrix}}_R.

For example, the last column says

v⃗3=3u⃗1+2u⃗2+6u⃗3,\vec v_3=\sqrt3\vec u_1+\sqrt2\vec u_2+\sqrt6\vec u_3,

which puts back the two projections and the remaining vector.

Move the slider to follow the three columns in this example. In iteration i=3i=3, subtract both earlier components before normalizing.

Loading...

Existence and uniqueness

There is one simple choice we could change: reverse the sign of a column of QQ and reverse the sign of the corresponding row of RR. The product stays the same. For example,

[3−147]=[3/5−4/54/53/5][5505]=[−3/5−4/5−4/53/5][−5−505].\begin{bmatrix}3&-1\\4&7\end{bmatrix} =\begin{bmatrix}3/5&-4/5\\4/5&3/5\end{bmatrix}\begin{bmatrix}5&5\\0&5\end{bmatrix} =\begin{bmatrix}-3/5&-4/5\\-4/5&3/5\end{bmatrix}\begin{bmatrix}-5&-5\\0&5\end{bmatrix}.

Both choices of QQ have orthonormal columns. But the second RR has a negative diagonal entry. The Gram-Schmidt process gives positive diagonal entries because they are lengths of nonzero vectors. Requiring those entries to be positive removes the ambiguity.

To see why the factorization is unique, start with its first column. Since RR is upper triangular with positive diagonal entries, v⃗1\vec v_1 must be a positive multiple of the unit vector u⃗1\vec u_1. This forces

u⃗1=v⃗1∥v⃗1∥.\vec u_1=\frac{\vec v_1}{\|\vec v_1\|}.

For the next column, orthonormality forces the coefficient along u⃗1\vec u_1 to be v⃗2⋅u⃗1\vec v_2\cdot\vec u_1. Subtracting this component leaves a positive multiple of u⃗2\vec u_2, so

w⃗2=v⃗2−(v⃗2⋅u⃗1)u⃗1,u⃗2=w⃗2∥w⃗2∥.\vec w_2=\vec v_2-(\vec v_2\cdot\vec u_1)\vec u_1, \qquad \vec u_2=\frac{\vec w_2}{\|\vec w_2\|}.

The same argument continues for each column: dot products determine its components along the previous unit vectors, and normalizing what remains determines the next unit vector. Independence ensures that the remaining vector is nonzero. Once QQ is fixed, the coefficients in RR are fixed as well. So any factorization satisfying these conditions gives the same QQ and RR as the Gram-Schmidt process.

This does not mean that a subspace has only one orthonormal basis. Choosing a different starting basis, or changing its order, can change the orthonormal basis we get. Uniqueness applies once we fix AA, including its column order, and require positive diagonal entries in RR.