Householder transformation
In linear algebra, a Householder transformation (also known as a Householder reflection or elementary reflector) is a linear transformation that describes a reflection about a plane or hyperplane containing the origin. The Householder transformation was used in a 1958 paper by Alston Scott Householder. Its analogue over general inner product spaces is the Householder operator. Definition. Transformation. The reflection hyperplane can be defined by its "normal vector", a unit vector formula_1 (a vector with length formula_2) that is orthogonal to the hyperplane. The reflection of a point formula_3 about this hyperplane is the linear transformation: where formula_1 is  given as a column unit vector with Hermitian transpose formula_6. Householder matrix. The matrix constructed from this transformation can be expressed in terms of an outer product as: is known as the Householder matrix, where formula_8 is the identity matrix Properties. The Householder matrix has the following properties: Applications. Geometric optics. In geometric optics, specular reflection can be expressed in terms of the Householder matrix (see ""). Numerical linear algebra. Householder transformations are widely used in numerical linear algebra, for example, to annihilate the entries below the main diagonal of a matrix, to perform QR decompositions and in the first step  of the QR algorithm. They are also widely used for transforming to a Hessenberg form. For symmetric or Hermitian matrices, the symmetry can be preserved, resulting in tridiagonalization. QR decomposition. 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 formula_26 minors of that product. Tridiagonalization. This procedure is presented in Numerical Analysis by Burden and Faires. It uses a slightly altered formula_27 function with formula_28. In the first step , to form the Householder matrix in each step we need to determine formula_29 and formula_30, which are: From formula_29 and formula_30, construct vector formula_1: where formula_36, formula_37, and Then compute: Having found formula_41 and computed formula_42 the process is repeated for formula_43 as follows: Continuing in this manner, the tridiagonal and symmetric matrix is formed. Examples. In this example, also from Burden and Faires, the given matrix is transformed to the similar tridiagonal matrix A by using the Householder method. Following those steps in the Householder method, we have: The first Householder matrix: Used formula_47 to form As we can  see, the final result is a tridiagonal symmetric matrix which is similar to the original one. The process is finished after two steps. Computational and theoretical relationship to other unitary transformations. The Householder transformation is a reflection about a hyperplane with unit normal vector formula_1, as stated earlier. An formula_50-by-formula_50 unitary transformation formula_52 satisfies formula_53. Taking the determinant (formula_50-th power of the geometric mean) and trace (proportional to arithmetic mean) of a unitary matrix reveals that its eigenvalues formula_55 have unit modulus. This can be seen directly and swiftly: Since arithmetic and geometric means are equal if  the variables are constant (see inequality of arithmetic and geometric means), we establish the claim of unit modulus. For the case of real valued unitary matrices we obtain orthogonal matrices, formula_57. It follows rather readily (see orthogonal matrix) that any orthogonal matrix can be decomposed into a product of 2 by 2 rotations, called Givens Rotations, and Householder reflections. This is appealing intuitively since multiplication of a vector by an orthogonal matrix preserves the length of that vector, and rotations and reflections exhaust the set of (real valued) geometric operations that render invariant a vector's length. The Householder transformation  was shown to have a one-to-one relationship with the canonical coset decomposition of unitary matrices defined in group theory, which can be used to parametrize unitary operators in a very efficient manner. Finally we note that a single Householder transform, unlike a solitary Givens transform, can act on all columns of a matrix, and as such exhibits the lowest computational cost for QR decomposition and tridiagonalization. The penalty for this "computational optimality" is, of course, that Householder operations cannot be as deeply or efficiently parallelized. As such Householder is preferred for dense matrices on sequential machines, whilst  Givens is preferred on sparse matrices, and/or parallel machines.