Householder transformation

Householder transformation

In mathematics, a Householder transformation in 3-dimensional space is the reflection of a vector in a plane. In general Euclidean space it is a linear transformation that describes a reflection in a hyperplane (containing the origin).

The Householder transformation was introduced in 1958 by Alston Scott Householder.

It can be used to obtain a QR decomposition of a matrix, as described in the QR algorithm, and to bring a matrix A to upper Hessenberg matrix form ( which costs ) with a finite sequence of orthogonal similarity transforms.

Over general inner product spaces, this is known as the Householder operator.

Definition and properties

The reflection hyperplane can be defined by a unit vector $v$ (a vector with length 1), that is orthogonal to the hyperplane.

If $v$ is given as a column unit vector and $I$ is the identity matrix the linear transformation described above is given by the Householder matrix ($v^*$ denotes the Hermitian transpose of the vector $v$)

: $Q = I - 2 vv^*.,$

The Householder matrix has the following properties:
* it is Hermitian: $Q = Q^*,$
* it is unitary: $Q^\left\{-1\right\}=Q^*,$
* therefore it is also involutary: $Q^2=I,$.

Furthermore, $Q$ really reflects a point $X$ (which we will identify with its position vector $x$) as described above, since

: $Qx = x-2vv^*x = x - 2langle v,x angle v,$

where $langle angle$ denotes the dot product. Note that $|langle v, x angle|$ is equal to the distance from "X" to the hyperplane.

Application

Householder reflections can be used to calculate QR decompositions by reflecting first one column of a matrix onto a multiple of a standard basis vector, calculating the transformation matrix, multiplying it with the original matrix and then recursing down the ("i", "i") minors of that product.

They're also widely used for tridiagonalization of symmetric matrices and for transforming non-symmetric matrices to a Hessenberg form.

References

* Alston S. Householder, Unitary Triangularization of a Nonsymmetric Matrix, "Journal ACM", 5 (4), 1958, 339-342. [http://dx.doi.org/10.1145/320941.320947 DOI:10.1145/320941.320947]
* David D. Morrison, Remarks on the Unitary Triangularization of a Nonsymmetric Matrix, "Journal ACM", 7 (2), 1960, 185-186. [http://dx.doi.org/10.1145/321021.321030 DOI:10.1145/321021.321030]
* C.D. LaBudde, [http://www.jstor.org/stable/view/2004005?seq=1 The reduction of an arbitrary real square matrix to tridiagonal form using similarity transformations] , Math. Comp. 17(1963) 433-437.

* [http://www.maths.lancs.ac.uk/~gilbert/m306c/node21.html Householder's Method]
* [http://math.fullerton.edu/mathews/n2003/HouseholderMod.html Householder Transformations]

Wikimedia Foundation. 2010.

Look at other dictionaries:

• Householder-Transformation — In der Mathematik beschreibt die Householdertransformation die Spiegelung eines Vektors an der Hyperebene durch Null in einem euklidischen Raum. Im dreidimensionalen Raum ist sie eine lineare Abbildung, die eine Spiegelung an einer Ebene (durch… …   Deutsch Wikipedia

• Transformation (Mathematik) — Die Mathematik versteht unter einer Transformation eine Art Abbildung. Die Verwendung dieses Wortes lässt sich grob in drei Bereiche unterteilen: Koordinatentransformationen und Abbildungen, die mit gewissen geometrischen Eigenschaften kompatibel …   Deutsch Wikipedia

• Householder — A householder is a person who is the head of a household ; see House.Householder is also a family name: *Alston Scott Householder, American mathematician Mathematical topics named after A.S. Householder: ** Householder transformation in geometry… …   Wikipedia

• Householder operator — In Linear Algebra, define the Householder operator as follows.Let V, be a finite dimensional inner product space with unit vector uin V Then, the Householder operator is an operator H u : V o V, defined by: H u(x) = x 2langle x,u angle u, where… …   Wikipedia

• Transformation matrix — In linear algebra, linear transformations can be represented by matrices. If T is a linear transformation mapping Rn to Rm and x is a column vector with n entries, then for some m×n matrix A, called the transformation matrix of T. There is an… …   Wikipedia

• Alston Scott Householder — (Rockford, Illinois, USA, 5 May 1904 – Malibu, California, USA, 4 July 1993) was an American mathematician who specialized in mathematical biology and numerical analysis, inventor of the Householder transformation and of Householder s method.… …   Wikipedia

• QR algorithm — In numerical linear algebra, the QR algorithm is an eigenvalue algorithm; that is, a procedure to calculate the eigenvalues and eigenvectors of a matrix. The QR transformation was developed in 1961 by John G.F. Francis (England) and by Vera N.… …   Wikipedia

• Funktionaltransformation — Die Mathematik versteht unter einer Transformation eine Art Abbildung. Die Verwendung dieses Wortes lässt sich grob in drei Bereiche unterteilen: Koordinatentransformationen und Abbildungen, die mit gewissen geometrischen Eigenschaften kompatibel …   Deutsch Wikipedia

• Eigenvalues and eigenvectors — For more specific information regarding the eigenvalues and eigenvectors of matrices, see Eigendecomposition of a matrix. In this shear mapping the red arrow changes direction but the blue arrow does not. Therefore the blue arrow is an… …   Wikipedia

• List of mathematics articles (H) — NOTOC H H cobordism H derivative H index H infinity methods in control theory H relation H space H theorem H tree Haag s theorem Haagerup property Haaland equation Haar measure Haar wavelet Haboush s theorem Hackenbush Hadamard code Hadamard… …   Wikipedia