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 = { [ x y z ] ∈ R 3 : x + y − z = 0 } . P=\left\{\begin{bmatrix}x\\y\\z\end{bmatrix}\in\mathbb R^3:x+y-z=0\right\}. P = ⎩ ⎨ ⎧ ⎣ ⎡ x y z ⎦ ⎤ ∈ R 3 : x + y − z = 0 ⎭ ⎬ ⎫ . This is a subspace: it contains 0 ⃗ \vec0 0 , and adding vectors or taking scalar multiples preserves the equation x + y − z = 0 x+y-z=0 x + y − z = 0 .
One basis of P P P is
v ⃗ 1 = [ 1 0 1 ] , v ⃗ 2 = [ 1 1 2 ] . \vec v_1=\begin{bmatrix}1\\0\\1\end{bmatrix},\qquad
\vec v_2=\begin{bmatrix}1\\1\\2\end{bmatrix}. v 1 = ⎣ ⎡ 1 0 1 ⎦ ⎤ , v 2 = ⎣ ⎡ 1 1 2 ⎦ ⎤ . Both vectors lie on the plane, and neither is a multiple of the other. They span the plane: if z = x + y z=x+y z = x + y , then
[ x y z ] = ( x − y ) [ 1 0 1 ] + y [ 1 1 2 ] . \begin{bmatrix}x\\y\\z\end{bmatrix}
=(x-y)\begin{bmatrix}1\\0\\1\end{bmatrix}
+y\begin{bmatrix}1\\1\\2\end{bmatrix}. ⎣ ⎡ x y z ⎦ ⎤ = ( x − y ) ⎣ ⎡ 1 0 1 ⎦ ⎤ + y ⎣ ⎡ 1 1 2 ⎦ ⎤ . 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.
An orthonormal basis of a subspace is a basis whose vectors are mutually perpendicular and each have length one. If the basis is u ⃗ 1 , … , u ⃗ d \vec u_1,\ldots,\vec u_d u 1 , … , u d , then
u ⃗ i ⋅ u ⃗ i = 1 , u ⃗ i ⋅ u ⃗ j = 0 when i ≠ j . \vec u_i\cdot\vec u_i=1,\qquad
\vec u_i\cdot\vec u_j=0\quad\text{when }i\ne j. u i ⋅ u i = 1 , u i ⋅ u j = 0 when i = j . We’ll use v ⃗ 1 , v ⃗ 2 , … \vec v_1,\vec v_2,\ldots v 1 , v 2 , … for the original basis vectors and u ⃗ 1 , u ⃗ 2 , … \vec u_1,\vec u_2,\ldots u 1 , u 2 , … for the orthonormal ones.
from gram_schmidt_visuals import basis_view, stepper
basis_view(orthonormal=False)The Gram-Schmidt process ¶ Return to our basis of the plane x + y − z = 0 x+y-z=0 x + y − z = 0 :
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 ∥ v 1 ∥ = 2 , set
u ⃗ 1 = v ⃗ 1 ∥ v ⃗ 1 ∥ = 1 2 [ 1 0 1 ] . \vec u_1=\frac{\vec v_1}{\|\vec v_1\|}
=\frac1{\sqrt2}\begin{bmatrix}1\\0\\1\end{bmatrix}. u 1 = ∥ v 1 ∥ v 1 = 2 1 ⎣ ⎡ 1 0 1 ⎦ ⎤ . This vector has length one and points in the same direction as v ⃗ 1 \vec v_1 v 1 .
Subtract the projection: Let ℓ = span ( u ⃗ 1 ) \ell=\operatorname{span}(\vec u_1) ℓ = span ( u 1 ) . Recall from Chapter 2.7 that v ⃗ 2 \vec v_2 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}. v 2 = along ℓ proj ℓ ( v 2 ) + perpendicular to ℓ ( v 2 − proj ℓ ( v 2 ) ) . Since u ⃗ 1 \vec u_1 u 1 has length one, the projection formula simplifies to
proj ℓ ( v ⃗ 2 ) = ( v ⃗ 2 ⋅ u ⃗ 1 ) u ⃗ 1 = 3 2 1 2 [ 1 0 1 ] = 3 2 [ 1 0 1 ] . \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}. proj ℓ ( v 2 ) = ( v 2 ⋅ u 1 ) u 1 = 2 3 2 1 ⎣ ⎡ 1 0 1 ⎦ ⎤ = 2 3 ⎣ ⎡ 1 0 1 ⎦ ⎤ . We want the perpendicular component, so subtract this projection:
w ⃗ 2 = v ⃗ 2 − proj ℓ ( v ⃗ 2 ) = [ 1 1 2 ] − 3 2 [ 1 0 1 ] = 1 2 [ − 1 2 1 ] . \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}. w 2 = v 2 − proj ℓ ( v 2 ) = ⎣ ⎡ 1 1 2 ⎦ ⎤ − 2 3 ⎣ ⎡ 1 0 1 ⎦ ⎤ = 2 1 ⎣ ⎡ − 1 2 1 ⎦ ⎤ . Normalize the remaining vector: The remaining vector is perpendicular to u ⃗ 1 \vec u_1 u 1 , but it doesn’t yet have length one. Its length is
∥ w ⃗ 2 ∥ = 1 4 + 1 + 1 4 = 6 2 . \|\vec w_2\|=\sqrt{\frac14+1+\frac14}=\frac{\sqrt6}{2}. ∥ w 2 ∥ = 4 1 + 1 + 4 1 = 2 6 . Dividing by this length gives
u ⃗ 2 = w ⃗ 2 ∥ w ⃗ 2 ∥ = 1 6 [ − 1 2 1 ] . \vec u_2=\frac{\vec w_2}{\|\vec w_2\|}
=\frac1{\sqrt6}\begin{bmatrix}-1\\2\\1\end{bmatrix}. u 2 = ∥ w 2 ∥ w 2 = 6 1 ⎣ ⎡ − 1 2 1 ⎦ ⎤ . Let’s check:
u ⃗ 1 ⋅ u ⃗ 2 = − 1 + 0 + 1 2 6 = 0 , ∥ u ⃗ 1 ∥ 2 = 1 + 0 + 1 2 = 1 , ∥ u ⃗ 2 ∥ 2 = 1 + 4 + 1 6 = 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. u 1 ⋅ u 2 = 2 6 − 1 + 0 + 1 = 0 , ∥ u 1 ∥ 2 = 2 1 + 0 + 1 = 1 , ∥ u 2 ∥ 2 = 6 1 + 4 + 1 = 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 u 1 , u 2 form an orthonormal basis of P P P .
This is the idea behind the Gram-Schmidt process : subtract the projections along the directions we’ve already found, then normalize what remains.
basis_view(orthonormal=True)Move the slider to follow the Gram-Schmidt process for the two basis vectors of P P P , from the first normalization to the completed orthonormal basis.
Coordinates ¶ Let’s use our new basis to describe another vector on the plane:
b ⃗ = [ 3 2 5 ] . \vec b=\begin{bmatrix}3\\2\\5\end{bmatrix}. b = ⎣ ⎡ 3 2 5 ⎦ ⎤ . It lies on the plane x + y − z = 0 x+y-z=0 x + y − z = 0 because 3 + 2 − 5 = 0 3+2-5=0 3 + 2 − 5 = 0 . We want coefficients c 1 , c 2 c_1,c_2 c 1 , c 2 such that
b ⃗ = c 1 u ⃗ 1 + c 2 u ⃗ 2 . \vec b=c_1\vec u_1+c_2\vec u_2. b = c 1 u 1 + c 2 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 u 1 :
b ⃗ ⋅ u ⃗ 1 = c 1 ( u ⃗ 1 ⋅ u ⃗ 1 ) + c 2 ( u ⃗ 2 ⋅ u ⃗ 1 ) = c 1 . \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. b ⋅ u 1 = c 1 ( u 1 ⋅ u 1 ) + c 2 ( u 2 ⋅ u 1 ) = c 1 . The first dot product is 1 and the second is 0, so only c 1 c_1 c 1 remains. Taking the dot product with u ⃗ 2 \vec u_2 u 2 similarly gives c 2 c_2 c 2 . Therefore,
c 1 = 3 + 0 + 5 2 = 4 2 , c 2 = − 3 + 4 + 5 6 = 6 . c_1=\frac{3+0+5}{\sqrt2}=4\sqrt2,
\qquad
c_2=\frac{-3+4+5}{\sqrt6}=\sqrt6. c 1 = 2 3 + 0 + 5 = 4 2 , c 2 = 6 − 3 + 4 + 5 = 6 . Substituting the vectors back in checks our answer:
4 2 u ⃗ 1 + 6 u ⃗ 2 = 4 [ 1 0 1 ] + [ − 1 2 1 ] = [ 3 2 5 ] = 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. 4 2 u 1 + 6 u 2 = 4 ⎣ ⎡ 1 0 1 ⎦ ⎤ + ⎣ ⎡ − 1 2 1 ⎦ ⎤ = ⎣ ⎡ 3 2 5 ⎦ ⎤ = b . If u ⃗ 1 , … , u ⃗ d \vec u_1,\ldots,\vec u_d u 1 , … , u d form an orthonormal basis of V V V and b ⃗ ∈ V \vec b\in V b ∈ V , then
b ⃗ = ( b ⃗ ⋅ u ⃗ 1 ) u ⃗ 1 + ⋯ + ( b ⃗ ⋅ u ⃗ d ) u ⃗ d . \vec b=(\vec b\cdot\vec u_1)\vec u_1+\cdots+(\vec b\cdot\vec u_d)\vec u_d. b = ( b ⋅ u 1 ) u 1 + ⋯ + ( b ⋅ u d ) u d . So, to find the coefficient of a basis vector, take its dot product with b ⃗ \vec b b .
The vectors
v ⃗ 1 = [ 2 1 3 ] , v ⃗ 2 = [ 3 − 2 1 ] \vec v_1=\begin{bmatrix}2\\1\\3\end{bmatrix},\qquad
\vec v_2=\begin{bmatrix}3\\-2\\1\end{bmatrix} v 1 = ⎣ ⎡ 2 1 3 ⎦ ⎤ , v 2 = ⎣ ⎡ 3 − 2 1 ⎦ ⎤ form a basis of the plane
P = { [ x y z ] ∈ R 3 : x + y − z = 0 } . P=\left\{\begin{bmatrix}x\\y\\z\end{bmatrix}\in\mathbb R^3:x+y-z=0\right\}. P = ⎩ ⎨ ⎧ ⎣ ⎡ x y z ⎦ ⎤ ∈ R 3 : x + y − z = 0 ⎭ ⎬ ⎫ . a) Apply the Gram-Schmidt process to find an orthonormal basis u ⃗ 1 , u ⃗ 2 \vec u_1,\vec u_2 u 1 , u 2 of P P P . Check their lengths and dot product.
b) Use dot products to find coefficients c 1 , c 2 c_1,c_2 c 1 , c 2 such that
b ⃗ = [ 8 − 3 5 ] = c 1 u ⃗ 1 + c 2 u ⃗ 2 . \vec b=\begin{bmatrix}8\\-3\\5\end{bmatrix}=c_1\vec u_1+c_2\vec u_2. b = ⎣ ⎡ 8 − 3 5 ⎦ ⎤ = c 1 u 1 + c 2 u 2 . Check your answer by substituting the vectors back in.
a) Since ∥ v ⃗ 1 ∥ = 14 \|\vec v_1\|=\sqrt{14} ∥ v 1 ∥ = 14 ,
u ⃗ 1 = 1 14 [ 2 1 3 ] , v ⃗ 2 ⋅ u ⃗ 1 = 6 − 2 + 3 14 = 14 2 . \vec u_1=\frac1{\sqrt{14}}\begin{bmatrix}2\\1\\3\end{bmatrix},
\qquad \vec v_2\cdot\vec u_1=\frac{6-2+3}{\sqrt{14}}=\frac{\sqrt{14}}2. u 1 = 14 1 ⎣ ⎡ 2 1 3 ⎦ ⎤ , v 2 ⋅ u 1 = 14 6 − 2 + 3 = 2 14 . Subtracting the projection gives
w ⃗ 2 = v ⃗ 2 − 14 2 u ⃗ 1 = [ 3 − 2 1 ] − 1 2 [ 2 1 3 ] = 1 2 [ 4 − 5 − 1 ] . \vec w_2=\vec v_2-\frac{\sqrt{14}}2\vec u_1
=\begin{bmatrix}3\\-2\\1\end{bmatrix}
-\frac12\begin{bmatrix}2\\1\\3\end{bmatrix}
=\frac12\begin{bmatrix}4\\-5\\-1\end{bmatrix}. w 2 = v 2 − 2 14 u 1 = ⎣ ⎡ 3 − 2 1 ⎦ ⎤ − 2 1 ⎣ ⎡ 2 1 3 ⎦ ⎤ = 2 1 ⎣ ⎡ 4 − 5 − 1 ⎦ ⎤ . Its length is 42 / 2 \sqrt{42}/2 42 /2 , so
u ⃗ 2 = 1 42 [ 4 − 5 − 1 ] . \vec u_2=\frac1{\sqrt{42}}\begin{bmatrix}4\\-5\\-1\end{bmatrix}. u 2 = 42 1 ⎣ ⎡ 4 − 5 − 1 ⎦ ⎤ . Their squared lengths are ( 4 + 1 + 9 ) / 14 = 1 (4+1+9)/14=1 ( 4 + 1 + 9 ) /14 = 1 and ( 16 + 25 + 1 ) / 42 = 1 (16+25+1)/42=1 ( 16 + 25 + 1 ) /42 = 1 . Their dot product is ( 8 − 5 − 3 ) / ( 14 42 ) = 0 (8-5-3)/(\sqrt{14}\sqrt{42})=0 ( 8 − 5 − 3 ) / ( 14 42 ) = 0 . The Gram-Schmidt process preserves the span, so these form an orthonormal basis of P P P .
b) The coefficients are
c 1 = 16 − 3 + 15 14 = 2 14 , c 2 = 32 + 15 − 5 42 = 42 . c_1=\frac{16-3+15}{\sqrt{14}}=2\sqrt{14},\qquad
c_2=\frac{32+15-5}{\sqrt{42}}=\sqrt{42}. c 1 = 14 16 − 3 + 15 = 2 14 , c 2 = 42 32 + 15 − 5 = 42 . Checking:
2 14 u ⃗ 1 + 42 u ⃗ 2 = 2 [ 2 1 3 ] + [ 4 − 5 − 1 ] = [ 8 − 3 5 ] . 2\sqrt{14}\vec u_1+\sqrt{42}\vec u_2
=2\begin{bmatrix}2\\1\\3\end{bmatrix}
+\begin{bmatrix}4\\-5\\-1\end{bmatrix}
=\begin{bmatrix}8\\-3\\5\end{bmatrix}. 2 14 u 1 + 42 u 2 = 2 ⎣ ⎡ 2 1 3 ⎦ ⎤ + ⎣ ⎡ 4 − 5 − 1 ⎦ ⎤ = ⎣ ⎡ 8 − 3 5 ⎦ ⎤ . QR factorization ¶ Return to our worked example with v ⃗ 1 = [ 1 0 1 ] \vec v_1=\begin{bmatrix}1\\0\\1\end{bmatrix} v 1 = ⎣ ⎡ 1 0 1 ⎦ ⎤ and v ⃗ 2 = [ 1 1 2 ] \vec v_2=\begin{bmatrix}1\\1\\2\end{bmatrix} v 2 = ⎣ ⎡ 1 1 2 ⎦ ⎤ . We now have two bases of the same plane. How are they related?
For the first vector, we divided by 2 \sqrt2 2 . For the second, we subtracted 3 2 u ⃗ 1 \frac3{\sqrt2}\vec u_1 2 3 u 1 and divided the remainder by 6 2 \frac{\sqrt6}2 2 6 . Undoing these steps gives
v ⃗ 1 = 2 u ⃗ 1 , v ⃗ 2 = 3 2 u ⃗ 1 + 6 2 u ⃗ 2 . \vec v_1=\sqrt2\vec u_1,\qquad
\vec v_2=\frac3{\sqrt2}\vec u_1+\frac{\sqrt6}2\vec u_2. v 1 = 2 u 1 , v 2 = 2 3 u 1 + 2 6 u 2 . Put the original vectors in the columns of A A A and the orthonormal vectors in the columns of Q Q Q . These two equations become one matrix equation:
[ 1 1 0 1 1 2 ] ⏟ A = [ 1 / 2 − 1 / 6 0 2 / 6 1 / 2 1 / 6 ] ⏟ Q [ 2 3 / 2 0 6 / 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. A ⎣ ⎡ 1 0 1 1 1 2 ⎦ ⎤ = Q ⎣ ⎡ 1/ 2 0 1/ 2 − 1/ 6 2/ 6 1/ 6 ⎦ ⎤ R [ 2 0 3/ 2 6 /2 ] . Remember how matrix multiplication works column by column. The first column of Q R QR QR is 2 u ⃗ 1 + 0 u ⃗ 2 = v ⃗ 1 \sqrt2\vec u_1+0\vec u_2=\vec v_1 2 u 1 + 0 u 2 = v 1 . The second is 3 2 u ⃗ 1 + 6 2 u ⃗ 2 = v ⃗ 2 \frac3{\sqrt2}\vec u_1+\frac{\sqrt6}2\vec u_2=\vec v_2 2 3 u 1 + 2 6 u 2 = v 2 .
A QR factorization of a matrix A A A of shape n × d n\times d n × d writes
where Q Q Q has shape n × d n\times d n × d with orthonormal columns, and R R R has shape d × d d\times d d × d and is upper triangular : all entries below its diagonal are zero.
In our example, Q Q Q has shape 3 × 2 3\times2 3 × 2 and R R R has shape 2 × 2 2\times2 2 × 2 . Each column of R R R records the coefficients for one original basis vector. The zero appears because recovering v ⃗ 1 \vec v_1 v 1 only requires u ⃗ 1 \vec u_1 u 1 ; no u ⃗ 2 \vec u_2 u 2 is needed.
Use the original basis and the orthonormal basis from Activity 1. Let
A = [ v ⃗ 1 v ⃗ 2 ] = [ 2 3 1 − 2 3 1 ] . A=\begin{bmatrix}\vec v_1&\vec v_2\end{bmatrix}
=\begin{bmatrix}2&3\\1&-2\\3&1\end{bmatrix}. A = [ v 1 v 2 ] = ⎣ ⎡ 2 1 3 3 − 2 1 ⎦ ⎤ . a) Write v ⃗ 1 \vec v_1 v 1 and v ⃗ 2 \vec v_2 v 2 as combinations of u ⃗ 1 \vec u_1 u 1 and u ⃗ 2 \vec u_2 u 2 . You can recover these relations from your calculations in the Gram-Schmidt process.
b) Use these relations to write A = Q R A=QR A = QR , where the columns of Q Q Q are u ⃗ 1 , u ⃗ 2 \vec u_1,\vec u_2 u 1 , u 2 and R R R is upper triangular.
c) Check that Q R = A QR=A QR = A .
a) Undoing the normalization and projection steps gives
v ⃗ 1 = 14 u ⃗ 1 , v ⃗ 2 = 14 2 u ⃗ 1 + 42 2 u ⃗ 2 . \vec v_1=\sqrt{14}\vec u_1,\qquad
\vec v_2=\frac{\sqrt{14}}2\vec u_1+\frac{\sqrt{42}}2\vec u_2. v 1 = 14 u 1 , v 2 = 2 14 u 1 + 2 42 u 2 . b) Put the orthonormal vectors in Q Q Q and the coefficients in R R R :
Q = [ 2 / 14 4 / 42 1 / 14 − 5 / 42 3 / 14 − 1 / 42 ] , R = [ 14 14 / 2 0 42 / 2 ] . Q=\begin{bmatrix}
2/\sqrt{14}&4/\sqrt{42}\\
1/\sqrt{14}&-5/\sqrt{42}\\
3/\sqrt{14}&-1/\sqrt{42}
\end{bmatrix},\qquad
R=\begin{bmatrix}\sqrt{14}&\sqrt{14}/2\\0&\sqrt{42}/2\end{bmatrix}. Q = ⎣ ⎡ 2/ 14 1/ 14 3/ 14 4/ 42 − 5/ 42 − 1/ 42 ⎦ ⎤ , R = [ 14 0 14 /2 42 /2 ] . c) The columns of the product are
14 u ⃗ 1 = [ 2 1 3 ] , 14 2 u ⃗ 1 + 42 2 u ⃗ 2 = 1 2 [ 2 1 3 ] + 1 2 [ 4 − 5 − 1 ] = [ 3 − 2 1 ] . \sqrt{14}\vec u_1=\begin{bmatrix}2\\1\\3\end{bmatrix},\qquad
\frac{\sqrt{14}}2\vec u_1+\frac{\sqrt{42}}2\vec u_2
=\frac12\begin{bmatrix}2\\1\\3\end{bmatrix}
+\frac12\begin{bmatrix}4\\-5\\-1\end{bmatrix}
=\begin{bmatrix}3\\-2\\1\end{bmatrix}. 14 u 1 = ⎣ ⎡ 2 1 3 ⎦ ⎤ , 2 14 u 1 + 2 42 u 2 = 2 1 ⎣ ⎡ 2 1 3 ⎦ ⎤ + 2 1 ⎣ ⎡ 4 − 5 − 1 ⎦ ⎤ = ⎣ ⎡ 3 − 2 1 ⎦ ⎤ . These are the columns of A A A , so Q R = A QR=A QR = A .
We can start with a matrix instead of a named subspace. If the columns of A A A are linearly independent, they form a basis of colsp ( A ) \operatorname{colsp}(A) colsp ( A ) . Applying the Gram-Schmidt process gives an orthonormal basis of that same column space. Those vectors become the columns of Q Q Q , and expressing the original columns using them gives R R R .
For example, let’s find a QR factorization of
A = [ 3 − 1 4 7 ] . A=\begin{bmatrix}3&-1\\4&7\end{bmatrix}. A = [ 3 4 − 1 7 ] . Its columns v ⃗ 1 = [ 3 4 ] \vec v_1=\begin{bmatrix}3\\4\end{bmatrix} v 1 = [ 3 4 ] and v ⃗ 2 = [ − 1 7 ] \vec v_2=\begin{bmatrix}-1\\7\end{bmatrix} v 2 = [ − 1 7 ] aren’t multiples of one another, so they form a basis of R 2 \mathbb R^2 R 2 .
Normalize the first vector: The first column has length 5, giving
u ⃗ 1 = 1 5 [ 3 4 ] . \vec u_1=\frac15\begin{bmatrix}3\\4\end{bmatrix}. u 1 = 5 1 [ 3 4 ] . Subtract the projection: For the second column, calculate the projection coefficient and subtract the projection:
v ⃗ 2 ⋅ u ⃗ 1 = − 3 + 28 5 = 5 , w ⃗ 2 = v ⃗ 2 − 5 u ⃗ 1 = [ − 1 7 ] − [ 3 4 ] = [ − 4 3 ] . \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}. v 2 ⋅ u 1 = 5 − 3 + 28 = 5 , w 2 = v 2 − 5 u 1 = [ − 1 7 ] − [ 3 4 ] = [ − 4 3 ] . Normalize the remaining vector: The remaining vector has length 5. We still need to divide by that length:
u ⃗ 2 = 1 5 [ − 4 3 ] . \vec u_2=\frac15\begin{bmatrix}-4\\3\end{bmatrix}. u 2 = 5 1 [ − 4 3 ] . Both vectors now have length one, and their dot product is ( − 12 + 12 ) / 25 = 0 (-12+12)/25=0 ( − 12 + 12 ) /25 = 0 .
We don’t need a new calculation to find R R R . Put back what we subtracted and record the lengths:
v ⃗ 1 = 5 u ⃗ 1 , v ⃗ 2 = 5 u ⃗ 1 + 5 u ⃗ 2 . \vec v_1=5\vec u_1,\qquad \vec v_2=5\vec u_1+5\vec u_2. v 1 = 5 u 1 , v 2 = 5 u 1 + 5 u 2 . Therefore,
[ 3 − 1 4 7 ] = [ 3 / 5 − 4 / 5 4 / 5 3 / 5 ] ⏟ Q [ 5 5 0 5 ] ⏟ 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. [ 3 4 − 1 7 ] = Q [ 3/5 4/5 − 4/5 3/5 ] R [ 5 0 5 5 ] . Here Q Q Q is square: its two columns span all of R 2 \mathbb R^2 R 2 . In our plane example, Q Q Q had two columns with three entries each, spanning a plane inside R 3 \mathbb R^3 R 3 .
Find a QR factorization of
A = [ 5 − 7 12 17 ] . A=\begin{bmatrix}5&-7\\12&17\end{bmatrix}. A = [ 5 12 − 7 17 ] . Call its columns v ⃗ 1 , v ⃗ 2 \vec v_1,\vec v_2 v 1 , v 2 , in that order.
a) Use the Gram-Schmidt process to find an orthonormal basis u ⃗ 1 , u ⃗ 2 \vec u_1,\vec u_2 u 1 , u 2 of the column space. Remember to divide by the length after subtracting the projection.
b) Write the relations between the original vectors and the orthonormal vectors. Use these relations to find Q Q Q and R R R .
c) Check that the columns of Q Q Q are orthonormal and that Q R = A QR=A QR = A .
a) The first column has length 13, so
u ⃗ 1 = 1 13 [ 5 12 ] , v ⃗ 2 ⋅ u ⃗ 1 = − 35 + 204 13 = 13. \vec u_1=\frac1{13}\begin{bmatrix}5\\12\end{bmatrix},\qquad
\vec v_2\cdot\vec u_1=\frac{-35+204}{13}=13. u 1 = 13 1 [ 5 12 ] , v 2 ⋅ u 1 = 13 − 35 + 204 = 13. Then
w ⃗ 2 = v ⃗ 2 − 13 u ⃗ 1 = [ − 7 17 ] − [ 5 12 ] = [ − 12 5 ] . \vec w_2=\vec v_2-13\vec u_1
=\begin{bmatrix}-7\\17\end{bmatrix}-\begin{bmatrix}5\\12\end{bmatrix}
=\begin{bmatrix}-12\\5\end{bmatrix}. w 2 = v 2 − 13 u 1 = [ − 7 17 ] − [ 5 12 ] = [ − 12 5 ] . Its length is also 13, giving u ⃗ 2 = 1 13 [ − 12 5 ] \vec u_2=\frac1{13}\begin{bmatrix}-12\\5\end{bmatrix} u 2 = 13 1 [ − 12 5 ] .
b) The relations are v ⃗ 1 = 13 u ⃗ 1 \vec v_1=13\vec u_1 v 1 = 13 u 1 and v ⃗ 2 = 13 u ⃗ 1 + 13 u ⃗ 2 \vec v_2=13\vec u_1+13\vec u_2 v 2 = 13 u 1 + 13 u 2 . Thus
Q = 1 13 [ 5 − 12 12 5 ] , R = [ 13 13 0 13 ] . Q=\frac1{13}\begin{bmatrix}5&-12\\12&5\end{bmatrix},\qquad
R=\begin{bmatrix}13&13\\0&13\end{bmatrix}. Q = 13 1 [ 5 12 − 12 5 ] , R = [ 13 0 13 13 ] . c) Both columns have squared length ( 25 + 144 ) / 169 = 1 (25+144)/169=1 ( 25 + 144 ) /169 = 1 , and their dot product is ( − 60 + 60 ) / 169 = 0 (-60+60)/169=0 ( − 60 + 60 ) /169 = 0 . Also,
Q R = 1 13 [ 65 65 − 156 156 156 + 65 ] = [ 5 − 7 12 17 ] = A . QR=\frac1{13}\begin{bmatrix}65&65-156\\156&156+65\end{bmatrix}
=\begin{bmatrix}5&-7\\12&17\end{bmatrix}=A. QR = 13 1 [ 65 156 65 − 156 156 + 65 ] = [ 5 12 − 7 17 ] = A . 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 v 1 , v 2 , v 3 in R n \mathbb R^n 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}\|}. u 1 = ∥ v 1 ∥ v 1 . Second vector: Subtract its projection onto the line along u ⃗ 1 \vec u_1 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\|}. w 2 = v 2 − ( v 2 ⋅ u 1 ) u 1 , u 2 = ∥ w 2 ∥ w 2 . Third vector: We now need a vector perpendicular to both u ⃗ 1 \vec u_1 u 1 and u ⃗ 2 \vec u_2 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}. w 3 = v 3 − ( v 3 ⋅ u 1 ) u 1 − ( v 3 ⋅ u 2 ) u 2 . Because u ⃗ 1 \vec u_1 u 1 and u ⃗ 2 \vec u_2 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. w 3 ⋅ u 1 = v 3 ⋅ u 1 − ( v 3 ⋅ u 1 ) ( 1 ) − ( v 3 ⋅ u 2 ) ( 0 ) = 0. Similarly, w ⃗ 3 ⋅ u ⃗ 2 = 0 \vec w_3\cdot\vec u_2=0 w 3 ⋅ u 2 = 0 . Now normalize:
u ⃗ 3 = w ⃗ 3 ∥ w ⃗ 3 ∥ . \vec u_3=\frac{\vec w_3}{\|\vec w_3\|}. u 3 = ∥ w 3 ∥ w 3 . Why can we divide by these lengths? If w ⃗ 3 \vec w_3 w 3 were zero, then v ⃗ 3 \vec v_3 v 3 would be a combination of u ⃗ 1 , u ⃗ 2 \vec u_1,\vec u_2 u 1 , u 2 , and hence of v ⃗ 1 , v ⃗ 2 \vec v_1,\vec v_2 v 1 , v 2 . That would contradict the independence of the original vectors. The same reasoning ensures w ⃗ 2 ≠ 0 ⃗ \vec w_2\ne\vec0 w 2 = 0 .
The same procedure works for any number of linearly independent vectors.
Given d d d linearly independent vectors v ⃗ 1 , … , v ⃗ d \vec v_1,\ldots,\vec v_d v 1 , … , v d in R n \mathbb R^n R n , the Gram-Schmidt process constructs an orthonormal basis u ⃗ 1 , … , u ⃗ d \vec u_1,\ldots,\vec u_d u 1 , … , u d of their span.
For each i = 1 , … , d i=1,\ldots,d i = 1 , … , d , use the current vector v ⃗ i \textcolor{#3d81f6}{\vec v_i} v i and the previously constructed unit vectors u ⃗ 1 , … , u ⃗ i − 1 \textcolor{orange}{\vec u_1,\ldots,\vec u_{i-1}} u 1 , … , u i − 1 :
When i = 1 i=1 i = 1 , there are no projections to subtract, so w ⃗ 1 = v ⃗ 1 \vec w_1=\vec v_1 w 1 = v 1 . Linear independence guarantees that every w ⃗ i \vec w_i w i is nonzero.
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 A A A of shape 3 × 3 3\times3 3 × 3 with linearly independent columns v ⃗ 1 , v ⃗ 2 , v ⃗ 3 \vec v_1,\vec v_2,\vec v_3 v 1 , v 2 , v 3 , we can use these steps to write down Q Q Q and R R R . 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} v 1 v 2 v 3 = ∥ v 1 ∥ u 1 , = ( v 2 ⋅ u 1 ) u 1 + ∥ w 2 ∥ u 2 , = ( v 3 ⋅ u 1 ) u 1 + ( v 3 ⋅ u 2 ) u 2 + ∥ w 3 ∥ u 3 . These three equations give the factorization
[ ∣ ∣ ∣ v ⃗ 1 v ⃗ 2 v ⃗ 3 ∣ ∣ ∣ ] ⏟ A = [ ∣ ∣ ∣ u ⃗ 1 u ⃗ 2 u ⃗ 3 ∣ ∣ ∣ ] ⏟ Q [ ∥ v ⃗ 1 ∥ v ⃗ 2 ⋅ u ⃗ 1 v ⃗ 3 ⋅ u ⃗ 1 0 ∥ w ⃗ 2 ∥ v ⃗ 3 ⋅ u ⃗ 2 0 0 ∥ 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. A ⎣ ⎡ ∣ v 1 ∣ ∣ v 2 ∣ ∣ v 3 ∣ ⎦ ⎤ = Q ⎣ ⎡ ∣ u 1 ∣ ∣ u 2 ∣ ∣ u 3 ∣ ⎦ ⎤ R ⎣ ⎡ ∥ v 1 ∥ 0 0 v 2 ⋅ u 1 ∥ w 2 ∥ 0 v 3 ⋅ u 1 v 3 ⋅ u 2 ∥ w 3 ∥ ⎦ ⎤ . Each column of R R R contains the coefficients for one original column of A A A . 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 v i is a combination of only u ⃗ 1 , … , u ⃗ i \vec u_1,\ldots,\vec u_i u 1 , … , u i .
Let’s apply the procedure to
A = [ 1 2 3 1 0 1 1 1 − 1 ] . A=\begin{bmatrix}1&2&3\\1&0&1\\1&1&-1\end{bmatrix}. A = ⎣ ⎡ 1 1 1 2 0 1 3 1 − 1 ⎦ ⎤ . Call its columns v ⃗ 1 , v ⃗ 2 , v ⃗ 3 \vec v_1,\vec v_2,\vec v_3 v 1 , v 2 , v 3 , in that order.
First column: Its length is 3 \sqrt3 3 , so
u ⃗ 1 = 1 3 [ 1 1 1 ] . \vec u_1=\frac1{\sqrt3}\begin{bmatrix}1\\1\\1\end{bmatrix}. u 1 = 3 1 ⎣ ⎡ 1 1 1 ⎦ ⎤ . Second column: Find its component along u ⃗ 1 \textcolor{orange}{\vec u_1} u 1 and subtract:
v ⃗ 2 ⋅ u ⃗ 1 = 2 + 0 + 1 3 = 3 , w ⃗ 2 = [ 2 0 1 ] − [ 1 1 1 ] = [ 1 − 1 0 ] . \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}. v 2 ⋅ u 1 = 3 2 + 0 + 1 = 3 , w 2 = ⎣ ⎡ 2 0 1 ⎦ ⎤ − ⎣ ⎡ 1 1 1 ⎦ ⎤ = ⎣ ⎡ 1 − 1 0 ⎦ ⎤ . The remaining vector has length 2 \sqrt2 2 , so
u ⃗ 2 = 1 2 [ 1 − 1 0 ] . \vec u_2=\frac1{\sqrt2}\begin{bmatrix}1\\-1\\0\end{bmatrix}. u 2 = 2 1 ⎣ ⎡ 1 − 1 0 ⎦ ⎤ . Third column: This time, we need two coefficients:
v ⃗ 3 ⋅ u ⃗ 1 = 3 + 1 − 1 3 = 3 , v ⃗ 3 ⋅ u ⃗ 2 = 3 − 1 + 0 2 = 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. v 3 ⋅ u 1 = 3 3 + 1 − 1 = 3 , v 3 ⋅ u 2 = 2 3 − 1 + 0 = 2 . Subtract both components:
w ⃗ 3 = [ 3 1 − 1 ] − [ 1 1 1 ] − [ 1 − 1 0 ] = [ 1 1 − 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}. w 3 = ⎣ ⎡ 3 1 − 1 ⎦ ⎤ − ⎣ ⎡ 1 1 1 ⎦ ⎤ − ⎣ ⎡ 1 − 1 0 ⎦ ⎤ = ⎣ ⎡ 1 1 − 2 ⎦ ⎤ . The remaining vector has length 6 \sqrt6 6 , so
u ⃗ 3 = 1 6 [ 1 1 − 2 ] . \vec u_3=\frac1{\sqrt6}\begin{bmatrix}1\\1\\-2\end{bmatrix}. u 3 = 6 1 ⎣ ⎡ 1 1 − 2 ⎦ ⎤ . The three unnormalized directions have pairwise dot products 1 − 1 = 0 1-1=0 1 − 1 = 0 , 1 + 1 − 2 = 0 1+1-2=0 1 + 1 − 2 = 0 , and 1 − 1 = 0 1-1=0 1 − 1 = 0 . After normalization, they form an orthonormal basis of R 3 \mathbb R^3 R 3 .
We have already calculated every entry of R R R :
A = [ 1 / 3 1 / 2 1 / 6 1 / 3 − 1 / 2 1 / 6 1 / 3 0 − 2 / 6 ] ⏟ Q [ 3 3 3 0 2 2 0 0 6 ] ⏟ 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. A = Q ⎣ ⎡ 1/ 3 1/ 3 1/ 3 1/ 2 − 1/ 2 0 1/ 6 1/ 6 − 2/ 6 ⎦ ⎤ R ⎣ ⎡ 3 0 0 3 2 0 3 2 6 ⎦ ⎤ . For example, the last column says
v ⃗ 3 = 3 u ⃗ 1 + 2 u ⃗ 2 + 6 u ⃗ 3 , \vec v_3=\sqrt3\vec u_1+\sqrt2\vec u_2+\sqrt6\vec u_3, v 3 = 3 u 1 + 2 u 2 + 6 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 = 3 i=3 i = 3 , subtract both earlier components before normalizing.
Find a QR factorization of
A = [ 2 5 − 2 − 2 − 2 5 1 4 5 ] . A=\begin{bmatrix}2&5&-2\\-2&-2&5\\1&4&5\end{bmatrix}. A = ⎣ ⎡ 2 − 2 1 5 − 2 4 − 2 5 5 ⎦ ⎤ . Call its columns v ⃗ 1 , v ⃗ 2 , v ⃗ 3 \vec v_1,\vec v_2,\vec v_3 v 1 , v 2 , v 3 , in that order. Use the Gram-Schmidt process and keep your answers exact.
a) Find u ⃗ 1 \vec u_1 u 1 , then subtract the component of v ⃗ 2 \vec v_2 v 2 along u ⃗ 1 \vec u_1 u 1 and normalize to find u ⃗ 2 \vec u_2 u 2 .
b) Subtract the components of v ⃗ 3 \vec v_3 v 3 along both u ⃗ 1 \vec u_1 u 1 and u ⃗ 2 \vec u_2 u 2 , then normalize to find u ⃗ 3 \vec u_3 u 3 .
c) Write the relations between the original vectors and the orthonormal vectors, and assemble Q Q Q and R R R . Check that the columns of Q Q Q are orthonormal and that Q R = A QR=A QR = A .
a) The first column has length 3, so
u ⃗ 1 = 1 3 [ 2 − 2 1 ] , v ⃗ 2 ⋅ u ⃗ 1 = 10 + 4 + 4 3 = 6. \vec u_1=\frac13\begin{bmatrix}2\\-2\\1\end{bmatrix},\qquad
\vec v_2\cdot\vec u_1=\frac{10+4+4}{3}=6. u 1 = 3 1 ⎣ ⎡ 2 − 2 1 ⎦ ⎤ , v 2 ⋅ u 1 = 3 10 + 4 + 4 = 6. Then
w ⃗ 2 = [ 5 − 2 4 ] − 2 [ 2 − 2 1 ] = [ 1 2 2 ] . \vec w_2=\begin{bmatrix}5\\-2\\4\end{bmatrix}
-2\begin{bmatrix}2\\-2\\1\end{bmatrix}
=\begin{bmatrix}1\\2\\2\end{bmatrix}. w 2 = ⎣ ⎡ 5 − 2 4 ⎦ ⎤ − 2 ⎣ ⎡ 2 − 2 1 ⎦ ⎤ = ⎣ ⎡ 1 2 2 ⎦ ⎤ . Its length is 3, so u ⃗ 2 = 1 3 [ 1 2 2 ] \vec u_2=\frac13\begin{bmatrix}1\\2\\2\end{bmatrix} u 2 = 3 1 ⎣ ⎡ 1 2 2 ⎦ ⎤ .
b) The projection coefficients are
v ⃗ 3 ⋅ u ⃗ 1 = − 4 − 10 + 5 3 = − 3 , v ⃗ 3 ⋅ u ⃗ 2 = − 2 + 10 + 10 3 = 6. \vec v_3\cdot\vec u_1=\frac{-4-10+5}{3}=-3,\qquad
\vec v_3\cdot\vec u_2=\frac{-2+10+10}{3}=6. v 3 ⋅ u 1 = 3 − 4 − 10 + 5 = − 3 , v 3 ⋅ u 2 = 3 − 2 + 10 + 10 = 6. Subtracting both components gives
w ⃗ 3 = v ⃗ 3 − ( − 3 ) u ⃗ 1 − 6 u ⃗ 2 = [ − 2 5 5 ] + [ 2 − 2 1 ] − 2 [ 1 2 2 ] = [ − 2 − 1 2 ] . \vec w_3=\vec v_3-(-3)\vec u_1-6\vec u_2
=\begin{bmatrix}-2\\5\\5\end{bmatrix}
+\begin{bmatrix}2\\-2\\1\end{bmatrix}
-2\begin{bmatrix}1\\2\\2\end{bmatrix}
=\begin{bmatrix}-2\\-1\\2\end{bmatrix}. w 3 = v 3 − ( − 3 ) u 1 − 6 u 2 = ⎣ ⎡ − 2 5 5 ⎦ ⎤ + ⎣ ⎡ 2 − 2 1 ⎦ ⎤ − 2 ⎣ ⎡ 1 2 2 ⎦ ⎤ = ⎣ ⎡ − 2 − 1 2 ⎦ ⎤ . Its length is 3, so u ⃗ 3 = 1 3 [ − 2 − 1 2 ] \vec u_3=\frac13\begin{bmatrix}-2\\-1\\2\end{bmatrix} u 3 = 3 1 ⎣ ⎡ − 2 − 1 2 ⎦ ⎤ .
c) The relations are
v ⃗ 1 = 3 u ⃗ 1 , v ⃗ 2 = 6 u ⃗ 1 + 3 u ⃗ 2 , v ⃗ 3 = − 3 u ⃗ 1 + 6 u ⃗ 2 + 3 u ⃗ 3 . \vec v_1=3\vec u_1,\qquad
\vec v_2=6\vec u_1+3\vec u_2,\qquad
\vec v_3=-3\vec u_1+6\vec u_2+3\vec u_3. v 1 = 3 u 1 , v 2 = 6 u 1 + 3 u 2 , v 3 = − 3 u 1 + 6 u 2 + 3 u 3 . Thus
Q = 1 3 [ 2 1 − 2 − 2 2 − 1 1 2 2 ] , R = [ 3 6 − 3 0 3 6 0 0 3 ] . Q=\frac13\begin{bmatrix}2&1&-2\\-2&2&-1\\1&2&2\end{bmatrix},\qquad
R=\begin{bmatrix}3&6&-3\\0&3&6\\0&0&3\end{bmatrix}. Q = 3 1 ⎣ ⎡ 2 − 2 1 1 2 2 − 2 − 1 2 ⎦ ⎤ , R = ⎣ ⎡ 3 0 0 6 3 0 − 3 6 3 ⎦ ⎤ . Each column of Q Q Q has squared length 9 / 9 = 1 9/9=1 9/9 = 1 . The distinct-column dot products are ( 2 − 4 + 2 ) / 9 = 0 (2-4+2)/9=0 ( 2 − 4 + 2 ) /9 = 0 , ( − 4 + 2 + 2 ) / 9 = 0 (-4+2+2)/9=0 ( − 4 + 2 + 2 ) /9 = 0 , and ( − 2 − 2 + 4 ) / 9 = 0 (-2-2+4)/9=0 ( − 2 − 2 + 4 ) /9 = 0 . Finally,
Q R = 1 3 [ 6 15 − 6 − 6 − 6 15 3 12 15 ] = [ 2 5 − 2 − 2 − 2 5 1 4 5 ] = A . QR=\frac13\begin{bmatrix}6&15&-6\\-6&-6&15\\3&12&15\end{bmatrix}
=\begin{bmatrix}2&5&-2\\-2&-2&5\\1&4&5\end{bmatrix}=A. QR = 3 1 ⎣ ⎡ 6 − 6 3 15 − 6 12 − 6 15 15 ⎦ ⎤ = ⎣ ⎡ 2 − 2 1 5 − 2 4 − 2 5 5 ⎦ ⎤ = A . Existence and uniqueness ¶ There is one simple choice we could change: reverse the sign of a column of Q Q Q and reverse the sign of the corresponding row of R R R . The product stays the same. For example,
[ 3 − 1 4 7 ] = [ 3 / 5 − 4 / 5 4 / 5 3 / 5 ] [ 5 5 0 5 ] = [ − 3 / 5 − 4 / 5 − 4 / 5 3 / 5 ] [ − 5 − 5 0 5 ] . \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}. [ 3 4 − 1 7 ] = [ 3/5 4/5 − 4/5 3/5 ] [ 5 0 5 5 ] = [ − 3/5 − 4/5 − 4/5 3/5 ] [ − 5 0 − 5 5 ] . Both choices of Q Q Q have orthonormal columns. But the second R R R 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.
Let A A A be a real matrix of shape n × d n\times d n × d whose columns are linearly independent. There is a unique factorization A = Q R A=QR A = QR in which:
Q Q Q has shape n × d n\times d n × d and has orthonormal columns.
R R R has shape d × d d\times d d × d , is upper triangular, and has positive diagonal entries.
The columns of Q Q Q form an orthonormal basis of colsp ( A ) \operatorname{colsp}(A) colsp ( A ) .
To see why the factorization is unique, start with its first column. Since R R R is upper triangular with positive diagonal entries, v ⃗ 1 \vec v_1 v 1 must be a positive multiple of the unit vector u ⃗ 1 \vec u_1 u 1 . This forces
u ⃗ 1 = v ⃗ 1 ∥ v ⃗ 1 ∥ . \vec u_1=\frac{\vec v_1}{\|\vec v_1\|}. u 1 = ∥ v 1 ∥ v 1 . For the next column, orthonormality forces the coefficient along u ⃗ 1 \vec u_1 u 1 to be v ⃗ 2 ⋅ u ⃗ 1 \vec v_2\cdot\vec u_1 v 2 ⋅ u 1 . Subtracting this component leaves a positive multiple of u ⃗ 2 \vec u_2 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\|}. w 2 = v 2 − ( v 2 ⋅ u 1 ) u 1 , u 2 = ∥ w 2 ∥ 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 Q Q Q is fixed, the coefficients in R R R are fixed as well. So any factorization satisfying these conditions gives the same Q Q Q and R R R 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 A A A , including its column order, and require positive diagonal entries in R R R .