A very quick and easy to understand introduction to Gram-Schmidt Orthogonalization (Orthonormalization) and how to obtain QR decomposition of a matrix using it.
\begin
Discover why 18 million people worldwide trust Overleaf with their work.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Welcome to overleaf, (formerly writeLaTeX) --- just edit
% your LaTeX on the left, and we'll compile it for you on
% the right. If you give someone the link to this page, they
% can edit at the same time. If you create a free overleaf
% account, all your projects will be saved. See the help
% menu above for more info. Enjoy!
% -----------------------------------------------------------
% My thanks to Dana Ernst of Northern Arizona University
% for sharing his template with me. This is largely his work.
% -----------------------------------------------------------
% This is all preamble stuff that you don't have to worry about.
% Head down to where it says "Start here"
% -----------------------------------------------------------
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[12pt]{article}
\usepackage[margin=0.7in]{geometry}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{mathpazo}
\newenvironment{theorem}[2][Theorem]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}\hskip \labelsep {\bfseries #2.}]}{\end{trivlist}}
\newenvironment{lemma}[2][Lemma]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}\hskip \labelsep {\bfseries #2.}]}{\end{trivlist}}
\newenvironment{conjecture}[2][Conjecture]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}\hskip \labelsep {\bfseries #2.}]}{\end{trivlist}}
\newenvironment{question}[2][Question]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}\hskip \labelsep {\bfseries #2.}]}{\end{trivlist}}
\newenvironment{corollary}[2][Corollary]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}\hskip \labelsep {\bfseries #2.}]}{\end{trivlist}}
\newenvironment{definition}[2][Definition]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}\hskip \labelsep {\bfseries #2.}]}{\end{trivlist}}
\newenvironment{problem}[2][Problem]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}\hskip \labelsep {\bfseries #2.}]}{\end{trivlist}}
\begin{document}
% --------------------------------------------------------------
% Start here
% --------------------------------------------------------------
\title{\bf{Gram-Schmidt Orthogonalization \\and QR Decomposition }}
%\subtitle{Version 3.0---Final Version}
\author{Mohammad Umar Rehman \\ PhD Student, Control Group, \\ EE Department, IIT Delhi \\ \tt{umar.ee.iitd@gmail.com}} % replace with your name
\date{} % for a fixed date, uncomment this line and replace date, otherwise, today's date will be used.
\maketitle
\noindent \textbf{Abstract} A very quick and easy to understand introduction to Gram-Schmidt Orthogonalization (Orthonormalization) and how to obtain QR decomposition of a matrix using it. A basic background in linear algebra is assumed. \\
\noindent \textbf{Aim} Given a basis $\mathbb{B}$ of a vector subspace $\mathbf{V}$ spanned by vectors $\{v_1, v_2, \dotso, v_{n}\}$ it is required to find an orthonormal basis $\{q_1, q_2, \dotso, q_{n}\}$ (A basis that is orthogonal with unit length of constituent vectors). Thus, \[ q_\mathrm{i}^\mathrm{T}q_\mathrm{j} = \left\{
\begin{array}{ll}
1, & \quad i=j \\
0, & \quad i\neq j
\end{array}
\right.
\]
\begin{proof}
Note that span$\{v_1, v_2, \dotso, v_{n}\} = \textrm{span}\{q_1, q_2, \dotso, q_{n}\}$ (successive spanning) \\
Lets start with one vector $v_1$, normalize this to obtain vector $q_1$ as
\begin{equation}
q_1 = \frac{v_1}{\left\lVert v_1 \right\Vert}
\end{equation}
Now, lets include another vector, $v_2$ to the picture (See Fig. 1) \footnote{This is an improved version of the document with the figures included, it would have been better if a successive series of figures were included showing the process step by step. An animation of the GS process can be found on Wikipedia here: \url{https://en.wikipedia.org/wiki/Gram-Schmidt_process} \\ Please contact for any clarifications, or found errors. Thanks!}. We have already obtained $q_1$, now we need $q_2$, which can be obtained by normalizing a vector that is orthogonal to $v_1 (q_1)$. Suppose, this vector is $\tilde{v}_2$. By triangle law of vectors, it can be seen that
$$\tilde{v}_2 = v_2 - v_1$$
But, to be more formal in lines with the algorithm we write $\tilde{v}_2$ as
\begin{equation}\tilde{v}_2 = v_2 - \mathrm{proj}_{v_1} \left(v_2\right) = v_2 - \left\langle v_2,q_1 \right\rangle q_1
\end{equation}
and, \[q_2 = \frac{\tilde{v}_2}{\left\lVert \tilde{v}_2 \right\Vert} \]
where, $\left\langle a,b \right\rangle = a^\mathrm{T} b$ is the inner product.\\
\begin{figure}[ht]
\centering
\includegraphics[scale=0.4]{Proj1.JPG}
\caption{Obtaining an orthonormal basis--2D case}
\end{figure}
Going one step further we include $v_3$ and proceed on similar lines to obtain $\tilde{v}_3$ as
\begin{equation}
\begin{aligned}
\tilde{v}_3 &= v_3 - \mathrm{proj}_{q_1} \left(v_3\right) - \mathrm{proj}_{q_2} \left(v_3\right) \\
&= v_3 - \left\langle v_3, q_1 \right\rangle q_1 - \left\langle v_3, q_2 \right\rangle q_2 \\ q_3 &= \tilde{v}_3 / \left\lVert \tilde{v}_3 \right\rVert
\end{aligned}
\end{equation}
\begin{figure}[ht]
\centering
\includegraphics[scale=0.4]{Proj2.JPG}
\caption{Obtaining an orthonormal basis--3D case}
\end{figure}
Similarly,
\begin{equation}
\tilde{v}_4 = v_4 - \left\langle v_4, q_1 \right\rangle q_1 - \left\langle v_4, q_2 \right\rangle q_2 - \left\langle v_4, q_3 \right\rangle q_3 , \,\, q_4 = \tilde{v}_4 / \left\lVert \tilde{v}_4 \right\rVert
\end{equation}
%\newpage
\noindent So, this process continues and we are in a position to write the expression for $\tilde{v}_{n}$
\begin{equation}
\tilde{v}_{n} = v_{n} - \left\langle v_{n}, q_1 \right\rangle q_1 - \left\langle v_{n}, q_2 \right\rangle q_2 - \cdots -\left\langle v_{n}, q_{n-1} \right\rangle q_{n-1} , \,\, q_n = \tilde{v}_n / \left\lVert \tilde{v}_n \right\rVert
\end{equation}
In compact form,
%\framebox
\[
\tilde{v}_{n} = v_{n} - \sum_{i = 0}^{n-1}\left\langle v_{n},q_\mathrm{i} \right\rangle q_\mathrm{i}
\]
\end{proof}
\bigskip
\noindent Hence, we have obtained an orthonormal basis from a regular basis for the vector subspace \textbf{V}.
\bigskip
\noindent \textbf{Obtaining QR decomposition} \\
Now, let us rearrange the equations (1) to (5) in terms of $v$'s only
\begin{eqnarray}
v_1 &=& \quad \left\lVert v_1 \right\Vert q_1 \\
v_2 &=& \left\langle v_2,q_1 \right\rangle q_1 + \tilde{v}_2 = \left\langle v_2,q_1 \right\rangle q_1 + \left\lVert \tilde{v}_2 \right\Vert q_2 \\
v_3 &=& \left\langle v_3,q_1 \right\rangle q_1 + \left\langle v_3,q_2 \right\rangle q_2 + \tilde{v}_3 = \left\langle v_3,q_1 \right\rangle q_1 + \left\langle v_3,q_2 \right\rangle q_2 + \left\lVert \tilde{v}_3 \right\Vert q_3 \\
v_4 &=& \left\langle v_4,q_1 \right\rangle q_1 + \left\langle v_4,q_2 \right\rangle q_2 + \left\langle v_4,q_3 \right\rangle q_3 + \left\lVert\tilde{v}_4 \right\Vert q_4
\end{eqnarray}
\[
\vdots
\]
\begin{equation}
\hspace{-2em} v_n = \left\langle v_{n}, q_1 \right\rangle q_1 + \left\langle v_{n}, q_2 \right\rangle q_2 + \cdots +\left\langle v_{n-1}, q_{n-1} \right\rangle q_{n-1} + \left\lVert\tilde{v}_{n}\right\Vert q_{n}
\end{equation}
\vspace{1cm}
\noindent And rewrite these equations in the matrix form, we get
\begin{equation}
\begin{aligned}
\begin{bmatrix}
v_1 & v_2 &\dotso &v_{n} \\
\end{bmatrix}
&=
\begin{bmatrix}
q_1 & q_2 &\dotso &q_{n} \\
\end{bmatrix}
\begin{bmatrix}
\left\lVert v_1 \right\rVert & \left\langle v_2,q_1 \right\rangle & \left\langle v_3,q_1 \right\rangle & \dotso & \left\langle v_{n},q_1 \right\rangle \\
0& \left\lVert \tilde{v}_2 \right\rVert & \left\langle v_3,q_2 \right\rangle & \dotso & \left\langle v_{n},q_2 \right\rangle \\
0& 0 & \left\lVert \tilde{v}_3 \right\rVert & \dotso & \left\langle v_{n},q_3 \right\rangle \\
0& 0 &0 & \ddots & \vdots \\
0& 0 &0 & \left\lVert\tilde{v}_{n-1} \right\rVert & \left\langle v_{n-1},q_{n-1} \right\rangle \\
0& 0 &0 & 0 & \left\lVert \tilde{v}_{n} \right\rVert\\
\end{bmatrix} \\
\mathrm{or}, V &= QR
\end{aligned}
\end{equation}
Thus, we have obtained the QR decomposition of the matrix $A$ starting from the Gram-Schmidt process, where $Q$ is an orthonormal matrix and $R$ is an upper triangular matrix.
%\begin{figure}[ht]
%\centering
%\includegraphics[width=.25\textwidth]{myimage.png}
%\caption{This is a picture of math.}
%\end{figure}
% --------------------------------------------------------------
% Leave this at the bottom and replace URL with your own
% --------------------------------------------------------------
%\vfill
%\small{Read-only document can be found online at \url{https://www.overleaf.com/lotasymbols}} %copy and paste the READ-ONLY URL of your document into this line. Then others with this pdf can also access the .tex file. Avoid editing or deleting the project once you've shared this URL. (create a copy of this project to start a revised version of the same.) I'll use this mostly when a result gets published to the online class journal.
% --------------------------------------------------------------
% You don't have to mess with anything below this line.
% --------------------------------------------------------------
\end{document}