Orthonormal Matrices Q and Gram-Schmidt

Using orthonormal matrices $Q$ is highly rewarding in all domains of linear algebra as it simplifies calculations a lot. Every $q\_i$ in $Q$ satisfies ${\sum }^j\_1q\_i,j\le 1$ (normal vectors) and $q\_i\perp q\_n\text{with}i\ne n$ (perpendicular to all other columns in $Q$).

q\_{i}^Tq\_{j} = \left{\begin{matrix} 0 & i \ne j \\ 1 & i = j \end{matrix}\right.

The most transformative properties of $Q$ are

$$Q^{T}Q=I\text{(implies}{Q}^T=Q^{-1}\text{if Q is square)}$$

Projection

Projection is are simplified significantly by $Q$.

Gram-Schmidt

Gram-Schmidt constructs an orthonormal matrix $Q$ out of a matrix $A$ with independent columns using projection. For the set of vectors $a\_1,\dots ,a\_n$ in $A$, we generate $q\_1,\dots ,q\_n$ in $Q$, where a newly formed vector $A\_i$ is orthonormal to all other earlier vectors $A\_i-n$.

$$q\_i=\frac{A\_i}{||A\_i||}$$

For columns $a,b,c$ in $A$ we choose our first vector $A=a$ as given. We now must find $B$ such that $B\perp A$. The solution is to find the error $e$ of the Projection of $b$ onto $A$, as per definition any vector $\vec{v}$ projected onto space $S$ splits into $\vec{v}=v\_projected+v\_error$ with $v\_error\perp S$. The error of projecting $b$ onto $A$, and thus our $B$ is $B=b\_error=b-\frac{A^{T}b}{A^{T}A}A$. Then $B\perp A$.

We next need to create $C$ such that $C\perp A\text{and}C\perp B$. The formula is similar in that we deduct projections of $c$ onto $A$ and $B$ from c to arrive at $C$.

$$C=c-\frac{A^{T}c}{A^{T}A}A-\frac{B^{T}c}{B^{T}B}B$$

We then normalize all orthogonal vectors $A,B,C$ to be orthonormal. For example $q\_1=\frac{A}{||A||}$. We thus arrive at orthonormal vectors $q\_1,\dots ,q\_n=\left[\begin{array}{c}q\_n,1⋮q\_n,j\end{array}\right]$.These are the columns of $Q=\left[\begin{array}{ccc}q\_1& \cdots & q\_n\end{array}\right]$ and they are orthonormal.

Factorization of $A=QR$

$A=QR$ relates original matrix $A$ and orthonormal matrix $Q$.

A = QR \hspace{1cm} \begin{bmatrix} a\_{1} & a\_{2} \end{bmatrix} \= \begin{bmatrix} q\_{1} & q\_{2} \end{bmatrix} \begin{bmatrix} a\_{1}^Tq\_{1} & \ \\ \underbrace{ a\_{1}^Tq\_{2} }_{\text{must} = 0 } & a_{2}^Tq\_{2} \end{bmatrix}

Due to the method we used to create $Q$, every vector $q\_n$ of $Q$ must be perpendicular to all earlier vectors $a\_n-mm\ge 1$ that were used to create previous $q$‘s. Therefore entries $a\_{n-m}^{T}q\_n=0m\ge 1$ and $R$ is in upper triangular form $\left[\begin{array}{cccccc}a& a\&a0& a& a0& 0& a\end{array}\right]$.