Householder Transformation

  The most frequently applied algorithm for QR decomposition uses the Householder transformation u = H v, where the Householder matrix H is a symmetric and orthogonal matrix of the form:

with the identity matrix I and any normalized vector x with .

Householder transformations zero the m-1 elements of a column vector v below the first element:

One can verify that

fulfils and that with one obtains the vector .

To perform the decomposition of the (m,n) matrix A = QR (with ) we construct in this way an (m,m) matrix H⁽¹⁾ to zero the m-1 elements of the first column. An (m-1,m-1) matrix G⁽²⁾ will zero the m-2 elements of the second column. With G⁽²⁾ we produce the (m,m) matrix

After n (n-1 for m = n) such orthogonal transforms H⁽ⁱ⁾ we obtain:

R is upper triangular and the orthogonal matrix Q becomes:

In practice the H⁽ⁱ⁾ are never explicitely computed.