2.9 Gram-Schmidt Orthogolization

Gram-Schdmit method allows us to constructively transform any basis $(b_1,b_2,....,b_n)$ of an $n$-dimensional vector space $V$ into an orthogonal/orthonormal basis $(u_1,u_2,....u_n)$ of $V$. The method interactively constructs an orthogonal basis as follows

$u_1=b_1$

$u_2=b_2- \frac{u_1.u_1^T b_2}{u_1^T.u_1}$

..

$u_k=b_k - $ projection of $u_k$ onto the span of $(u_1,u_2,...u_{k-1})$

The $k$ th basis vector $b_k$ is projected onto the subspace spanned by the first $k-1$ constructed orthogonal vectors $u_1,u_2,......u_{k-1}$. This projection is then subtracted from $b_k$ and yields a vector $u_k$ that is orthogonal to the $(k-1)$ dimensional subspace spanned by $u_1,u_2,......u_{k-1}$.Repeating this procedure for all $n$ basis vectors $(b_1,b_2,....,b_n)$ yields an orthogonal basis $(u_1,u_2,....u_n)$ of V. If we normalize $u_k$, we obtain a ortho normal basis where $||u_k||=1$ for $k=1\ldots n $

Consider a simple example

import numpy as np
b1=np.array([2,0])
b2=np.array([1,1])
u1=b1
u2=b2-((np.outer(u1,u1)/np.dot(u1,u1)).dot(b2))
print("b1")
print(b1)

print("b2")
print(b2)
print("orthogonal vectors")
print("u1")
print(u1)
print("u2")
print(u2)

print("dot product of u1 and u2")

print(u1.dot(u2))

o/p
b1 

[2 0] 

b2 

[1 1] 

orthogonal vectors 

u1 

[2 0]

 u2 

[0. 1.]

dot product of u1 and u2 

0.0

Orthogonalization in three dimension

import numpy as np

np.set_printoptions(precision=4)

b1=np.array([1,2,2])

b2=np.array([-1,0,2])

b3=np.array([0,0,1])

u1=b1

u2=b2-((np.outer(u1,u1)/np.dot(u1,u1)).dot(b2))

u3=b3-((np.outer(u1,u1)/np.dot(u1,u1)).dot(b3))-((np.outer(u2,u2)/np.dot(u2,u2)).dot(b3))

print("b1")

print(b1)

print("b2")

print(b2)

print("b3")

print(b3)

print("orthogonal vectors")

print("u1")

print(u1)

print("u2")

print(u2)

print("u3")

print(u3)

print("length of u1 u2 u3")

lu1=np.sqrt(u1.dot(u1))

lu2=np.sqrt(u2.dot(u2))

lu3=np.sqrt(u3.dot(u3))

print(lu1,lu2,lu3)

print("normalized vectors u1 u2 u3")

u1=u1/lu1

u2=u2/lu2

u3=u3/lu3

print(u1)

print(u2)

print(u3)

np.set_printoptions(suppress=True)

print("dot product of u1 and u2")

display(round(u1.dot(u2)))

print("dot product of u1 and u3")

print(round(u1.dot(u3)))

print("dot product of u2 and u3")

display(round(u2.dot(u3)))

o/p
b1 

[1 2 2] 

b2

 [-1 0 2]

 b3 

[0 0 1] 

orthogonal vectors 

u1 

[1 2 2]

u2 

[-1.3333 -0.6667 1.3333] 

u3 

[ 0.2222 -0.2222 0.1111] 

length of u1 u2 u3 

3.0 2.0 0.3333333333333333

 normalized vectors u1 u2 u3

 [0.3333 0.6667 0.6667] 

[-0.6667 -0.3333 0.6667] 

[ 0.6667 -0.6667 0.3333] 

dot product of u1 and u2
0
dot product of u1 and u3 

0 

dot product of u2 and u3
0

Compact code

import numpy as np

def gram_schmidt(A):

    """Orthogonalize a set of vectors stored as the columns of matrix A."""

    # Get the number of vectors.

    n = A.shape[1]

    for j in range(n):

        # To orthogonalize the vector in column j with respect to the

        # previous vectors, subtract from it its projection onto

        # each of the previous vectors.

        for k in range(j):

            A[:, j] -= np.dot(A[:, k], A[:, j]) * A[:, k]

        A[:, j] = A[:, j] / np.linalg.norm(A[:, j])

    return A

if __name__ == '__main__':

    A = np.array([[1.0, 0.0, 1.0], [1.0, 0.0, -1.0], [0.0, 3.0, 4.0]])

    print(gram_schmidt(A))

Example ( university question)

Use the Gram-Schmidt process to find an orthogonal basis for the column space of the following matrix.

$\begin{bmatrix}
2 & 1& 0\\
1 & -1&1 \\
0 & 3 & 1\\
1 & 1 & 1
\end{bmatrix}$

here

$u_1=b_1=\begin{bmatrix}
2\\
1\\
0\\
1
\end{bmatrix}$

$u_2=b_2-\frac{(u_1u_1^T)}{||u_1||^2}.b_2$

$u_2=\begin{bmatrix}
1\\
-1\\
3\\
1
\end{bmatrix}-\frac{1}{6}\begin{bmatrix}
4 & 2 & 0 & 2\\
2 & 1 & 0 & 1\\
0& 0 & 0 & 0\\
2 & 1 & 0 & 1
\end{bmatrix}\begin{bmatrix}
1\\
-1\\
3\\
1
\end{bmatrix}$
$u_2=\begin{bmatrix}
0.3333\\
-1.3333\\
3.\\
0.6667
\end{bmatrix}$

$u_3=b_3-\frac{(u_1u_1^T)}{||u_1||^2}.b_3-\frac{(u_2u_2^T)}{||u_2||^2}.b_3$

$u_3=\begin{bmatrix}
-0.7353\\
0.9412\\
0.3824\\
0.5294
\end{bmatrix}$

Example ( University Question)

Use Gram-Schmidt process to find an orthonormal basis from the ordered basis $B=\{b_1,b_2\}$, where $b_1=\begin{bmatrix}1\\ 1\\ 1 \end{bmatrix}$  and  $b_2=\begin{bmatrix} -1\\ 2\\ 0 \end{bmatrix}$

$u_1=b_1=\begin{bmatrix} 1\\1\\1\end{bmatrix}$

$u_2=b_2-\frac{u_1.u_1^T}{||u_1^2||}.b_2$

$=\begin{bmatrix} -1\\2\\0\end{bmatrix} - \frac{1}{3} \begin{bmatrix}1 &1 &1 \\ 1&1&1\\ 1 &1 &1\end{bmatrix}\begin{bmatrix}-1 \\ 2 \\ 0 \end{bmatrix}$

$=\begin{bmatrix} -1\\2\\0\end{bmatrix} - \frac{1}{3} \begin{bmatrix}1 \\ 1 \\ 1 \end{bmatrix}$

$=\begin{bmatrix} -4/3\\5/3\\-1/3\end{bmatrix}$

length of $u_1=\sqrt{3}$

length of $u_2=\frac{\sqrt{42}}{3}$

So the normalized vectors are

$u_1=\frac{1}{\sqrt{3}}.\begin{bmatrix} 1\\1\\1\end{bmatrix}$

$u_2=\frac{1}{\sqrt{42}}.\begin{bmatrix} -4\\5\\-1\end{bmatrix}$

Note that $u_1.u_2=0$

Example ( University Question)

Obtain  an orthonormal basis with respect to the standard inner space for the subspace of $R^3$ generated by $(1,0,1), (1,0,-1)$ and $(0,3,4)$

$u_1=b_1=\begin{bmatrix} 1\\0\\1\end{bmatrix}$
$u_2=b_2-\frac{u_1.u_1^T}{||u_1^2||}.b_2$
$=\begin{bmatrix} 1\\0\\-1\end{bmatrix} - \frac{1}{2} \begin{bmatrix}1 &0 &1 \\ 0&0&0\\ 1 &0 &1\end{bmatrix}\begin{bmatrix}1 \\ 0 \\ -1 \end{bmatrix}$
$=\begin{bmatrix} 1\\0\\-1\end{bmatrix} - \frac{1}{2} \begin{bmatrix}0 \\ 0 \\ 0 \end{bmatrix}$
$=\begin{bmatrix} 1\\0\\-1\end{bmatrix}$

$u_3=b_3-\frac{(u_1u_1^T)}{||u_1||^2}.b_3-\frac{(u_2u_2^T)}{||u_2||^2}.b_3$

$u_3=\begin{bmatrix}
0\\
3\\
0\\
\end{bmatrix}$

length of $u_1=\sqrt{2}$
length of $u_2=\sqrt{2}$

length of $u_3=3$

So the normalized vectors are
$u_1=\frac{1}{\sqrt{2}}.\begin{bmatrix} 1\\0\\1\end{bmatrix}$
$u_2=\frac{1}{\sqrt{2}}.\begin{bmatrix}1\\0\\-1\end{bmatrix}$
$u_3=\frac{1}{3}.\begin{bmatrix}0\\3\\0\end{bmatrix}$

Example ( University Question)

Using the Gram-Schmidt method, construct the orthonormal basis $(u1,u2,u3)$ to the following sequence of vectors $w_1=\begin{bmatrix}
1\\
1\\
1\\
1
\end{bmatrix}, w_2=\begin{bmatrix}
1\\
1\\
-1\\
-1

\end{bmatrix},w_3=\begin{bmatrix}
0\\
-1\\
2\\
1

\end{bmatrix}$ of $R^4$

$u_1=w_1=\begin{bmatrix}1\\
1\\
1\\
1
\end{bmatrix}$

$u_2=w_2-\frac{u_1.u_1^T}{||u_1^2||}.w_2$
$u_2=\begin{bmatrix} 1\\1\\-1\\-1 \end{bmatrix} - \frac{1}{4} \begin{bmatrix}1 &1 &1&1 \\ 1&1&1 &1\\
1 &1 &1 &1\end{bmatrix}\begin{bmatrix} -1 \\ -1 \\ 1 \\1 \end{bmatrix}$

$u_2=\begin{bmatrix} 1\\1\\-1\\-1 \end{bmatrix}$

$u_3=w_3-\frac{(u_1u_1^T)}{||u_1||^2}.w_3-\frac{(u_2u_2^T)}{||u_2||^2}.w_3$

$u_3=\begin{bmatrix}0\\
-1\\
2\\
1
\end{bmatrix}-\frac{1}{4} \begin{bmatrix}1 &1 &1&1 \\ 1&1&1 &1\\
1 &1 &1 &1\end{bmatrix}\begin{bmatrix} 0 \\ -1 \\ 2 \\1 \end{bmatrix}-\frac{1}{4} \begin{bmatrix}
1 &1 &-1&-1 \\ 1&1&-1 &-1\\
-1 &-1 &1 &1\\
-1 &-1 &1 &1\\
\end{bmatrix}\begin{bmatrix} 0 \\ -1 \\ 2 \\1 \end{bmatrix}$$u_3=\begin{bmatrix}0\\
-1\\
2\\
1
\end{bmatrix}-\begin{bmatrix}
1/2\\
1/2\\
1/2\\
1/2
\end{bmatrix}-\begin{bmatrix}
-1\\
-1\\
1\\
1
\end{bmatrix}$

$u_3=\begin{bmatrix}
1/2\\
-1/2\\
1/2\\
-1/2
\end{bmatrix}$

The length of vectors

$||u_1||=2, ||u_2||=2,||u_3||=1$

So the normalized orthogonal vectors ( orthonormal vectors) are

$u_1=\begin{bmatrix}
1/2\\
1/2\\
1/2\\
1/2
\end{bmatrix},u_2=\begin{bmatrix}
1/2\\
1/2\\
-1/2\\
-1/2

\end{bmatrix},u_3=\begin{bmatrix}
1/2\\
-1/2\\
1/2\\
-1/2
\end{bmatrix}$