# Gram-Schmidt orthogonalization

Any set of linearly independent vectors $v_{1},\ldots,v_{n}$ can be converted into a set of orthogonal vectors $q_{1},\ldots,q_{n}$ by the Gram-Schmidt process. In three dimensions, $v_{1}$ determines a line; the vectors $v_{1}$ and $v_{2}$ determine a plane. The vector $q_{1}$ is the unit vector in the direction $v_{1}$. The (unit) vector $q_{2}$ lies in the plane of $v_{1},v_{2}$, and is normal to $v_{1}$ (on the same side as $v_{2}$. The (unit) vector $q_{3}$ is normal to the plane of $v_{1},v_{2}$, on the same side as $v_{3}$, etc.

In general, first set $u_{1}=v_{1}$, and then each $u_{i}$ is made orthogonal to the preceding $u_{1},\ldots u_{i-1}$ by subtraction of the projections of $v_{i}$ in the directions of $u_{1},\ldots,u_{i-1}$ :

 $u_{i}=v_{i}-\sum_{j=1}^{i-1}\frac{u_{j}^{T}v_{i}}{u_{j}^{T}u_{j}}u_{j}$

The $i$ vectors $u_{i}$ span the same subspace as the $v_{i}$. The vectors $q_{i}=u_{i}/||u_{i}||$ are orthonormal. This leads to the following theorem:

Theorem.

Any $m\times n$ matrix $A$ with linearly independent columns can be factorized into a product, $A=QR$. The columns of $Q$ are orthonormal and $R$ is upper triangular and invertible.

This “classical” Gram-Schmidt method is often numerically unstable, see [Golub89] for a “modified” Gram-Schmidt method.

• Originally from The Data Analysis Briefbook (http://rkb.home.cern.ch/rkb/titleA.htmlhttp://rkb.home.cern.ch/rkb/titleA.html)

• Golub89

Gene H. Golub and Charles F. van Loan: Matrix Computations, 2nd edn., The John Hopkins University Press, 1989.

 Title Gram-Schmidt orthogonalization Canonical name GramSchmidtOrthogonalization Date of creation 2013-03-22 12:06:14 Last modified on 2013-03-22 12:06:14 Owner akrowne (2) Last modified by akrowne (2) Numerical id 9 Author akrowne (2) Entry type Algorithm Classification msc 65F25 Synonym Gram-Schmidt decomposition Synonym Gram-Schmidt orthonormalization Synonym Gram-Schmidt process Related topic HouseholderTransformation Related topic GivensRotation Related topic QRDecomposition Related topic AnExampleForSchurDecomposition