Given a matrix , its QR decomposition is to find matrices and such that

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


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

is measuring the length of projected to the unit vector . Thus is a vector orthogonal to , which the unit vector of such is represented by .

Subsequently, we decompose column vector into components parallel to and a component that is orthogonal to all of them. For example, on , we have

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


Assume we have a system of linear equations , for which is the vector of unknown and is a vector of constants. If we decompose , we have

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