Given a matrix $A$, its QR decomposition is to find matrices $Q$ and $R$ such that

i.e., $Q$ is an orthogonal matrix and $R$ is a upper-triangular matrix.


Gramm-Schmidt orthogonalization is a method to perform QR decomposition: Consider matrix $A$ of $m$ columns, as denoted above. We first normalize the first column $x_1$ into unit length, Then decompose the second column $x_2$ into components parallel and orthogonal to column vector $\epsilon_1$,

$r_{12}$ is measuring the length of $x_2$ projected to the unit vector $\epsilon_1$. Thus $x_2 - r_{12}\epsilon_1$ is a vector orthogonal to $x_1$, which the unit vector of such is represented by $\epsilon_2$.

Subsequently, we decompose column vector $x_k$ into components parallel to $x_1,x_2,\cdots,x_{k-1}$ and a component that is orthogonal to all of them. For example, on $x_3$, we have

Note, matrices $A$ and $Q$ are of the same dimension, and may not be a square shape, but matrix $R$ is always a square matrix.


Assume we have a system of linear equations $Ax=b$, for which $x$ is the vector of unknown and $b$ is a vector of constants. If we decompose $A=QR$, we have

Now since $R$ is a upper-triangular matrix, we can use Gaussian elimination to find $x$.