Householder transformation
Encyclopedia
In linear algebra
, a Householder transformation (also known as Householder reflection or elementary reflector) is a linear transformation
that describes a reflection
about a plane
or hyperplane
containing the origin. Householder transformations are widely used in numerical linear algebra
, to perform QR decomposition
s and in the first step of the QR algorithm
. The Householder transformation was introduced in 1958 by Alston Scott Householder
.
Its analogue over general inner product spaces is the Householder operator
.
x about this hyperplane is:
where v is given as a column unit vector with Hermitian transpose vH. This is a linear transformation
given by the Householder matrix:
The Householder matrix has the following properties:
can be expressed in terms of the Householder matrix.
Householder reflections can be used to calculate QR decomposition
s 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) minor
s of that product.
They are also widely used for tridiagonalization of symmetric matrices and for transforming non-symmetric matrices to a Hessenberg
form.
In the first step, to form the Householder matrix in each step we need to determine
and r, which are:
;
;
From
and r, construct vector v:
where
, 
, and
for each k=3,4 ..n
Then compute:
Having found
and computed 
the process is repeated for k =2, 3, ..., n as follows:
;
;
for j=k+2; k+3,..., n
Continuing in this manner, the tridiagonal and symmetric matrix is formed.
Following those step in Householder Method. We have:
The first Householder matrix:
Q1
A1 = Q1AQ1 =
Used A1 to form Q2 =
A2 = Q2A1Q2=
As we can see, the final result is a tridiagonal symmetric matrix which is similar to the original one. The process finished after 2 steps.
Linear algebra
Linear algebra is a branch of mathematics that studies vector spaces, also called linear spaces, along with linear functions that input one vector and output another. Such functions are called linear maps and can be represented by matrices if a basis is given. Thus matrix theory is often...
, a Householder transformation (also known as Householder reflection or elementary reflector) is a linear transformation
Linear transformation
In mathematics, a linear map, linear mapping, linear transformation, or linear operator is a function between two vector spaces that preserves the operations of vector addition and scalar multiplication. As a result, it always maps straight lines to straight lines or 0...
that describes a reflection
Reflection (mathematics)
In mathematics, a reflection is a mapping from a Euclidean space to itself that is an isometry with a hyperplane as set of fixed points; this set is called the axis or plane of reflection. The image of a figure by a reflection is its mirror image in the axis or plane of reflection...
about a plane
Plane (mathematics)
In mathematics, a plane is a flat, two-dimensional surface. A plane is the two dimensional analogue of a point , a line and a space...
or hyperplane
Hyperplane
A hyperplane is a concept in geometry. It is a generalization of the plane into a different number of dimensions.A hyperplane of an n-dimensional space is a flat subset with dimension n − 1...
containing the origin. Householder transformations are widely used in numerical linear algebra
Numerical linear algebra
Numerical linear algebra is the study of algorithms for performing linear algebra computations, most notably matrix operations, on computers. It is often a fundamental part of engineering and computational science problems, such as image and signal processing, Telecommunication, computational...
, to perform QR decomposition
QR decomposition
In linear algebra, a QR decomposition of a matrix is a decomposition of a matrix A into a product A=QR of an orthogonal matrix Q and an upper triangular matrix R...
s and in the first step of the QR algorithm
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 the late 1950s by John G.F. Francis and by Vera N. Kublanovskaya , working independently...
. The Householder transformation was introduced in 1958 by Alston Scott Householder
Alston Scott Householder
Alston Scott Householder was an American mathematician who specialized in mathematical biology and numerical analysis, inventor of the Householder transformation and of Householder's method...
.
Its analogue over general inner product spaces is the Householder operator
Householder operator
In Linear Algebra, define the Householder operator as follows.Let V\, be a finite dimensional inner product space with unit vector u\in V Then, the Householder operator is an operator H_u : V \to V\, defined by H_u = x - 2\langle x,u \rangle u\,...
.
Definition and properties
The reflection hyperplane can be defined by a unit vector v (a vector with length 1) which is orthogonal to the hyperplane. The reflection of a pointPoint (geometry)
In geometry, topology and related branches of mathematics a spatial point is a primitive notion upon which other concepts may be defined. In geometry, points are zero-dimensional; i.e., they do not have volume, area, length, or any other higher-dimensional analogue. In branches of mathematics...
x about this hyperplane is:
where v is given as a column unit vector with Hermitian transpose vH. This is a linear transformation
Linear transformation
In mathematics, a linear map, linear mapping, linear transformation, or linear operator is a function between two vector spaces that preserves the operations of vector addition and scalar multiplication. As a result, it always maps straight lines to straight lines or 0...
given by the Householder matrix:
-
, where I is the identity matrixIdentity matrixIn linear algebra, the identity matrix or unit matrix of size n is the n×n square matrix with ones on the main diagonal and zeros elsewhere. It is denoted by In, or simply by I if the size is immaterial or can be trivially determined by the context...
.
The Householder matrix has the following properties:
- it is Hermitian:
- it is unitary:
- hence it is involutary:
. - A Householder matrix has eigenvalues
. To see this, notice that if 
is orthogonal to the vector 
which was used to create the reflector, then 
, i.e., 1 is an eigenvalue of multiplicity 
, since there are 
vectors orthogonal to 
. Also, notice 
, and so -1 is an eigenvalue with multiplicity 1. - The determinant of a Householder reflector is -1, since the determinant of a matrix is the product of its eigenvalues.
Applications
In geometric optics, specular reflectionSpecular reflection
Specular reflection is the mirror-like reflection of light from a surface, in which light from a single incoming direction is reflected into a single outgoing direction...
can be expressed in terms of the Householder matrix.
Householder reflections can be used to calculate QR decomposition
QR decomposition
In linear algebra, a QR decomposition of a matrix is a decomposition of a matrix A into a product A=QR of an orthogonal matrix Q and an upper triangular matrix R...
s 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) minor
Minor (linear algebra)
In linear algebra, a minor of a matrix A is the determinant of some smaller square matrix, cut down from A by removing one or more of its rows or columns...
s of that product.
They are also widely used for tridiagonalization of symmetric matrices and for transforming non-symmetric matrices to a Hessenberg
Hessenberg matrix
In linear algebra, a Hessenberg matrix is a special kind of square matrix, one that is "almost" triangular. To be exact, an upper Hessenberg matrix has zero entries below the first subdiagonal, and a lower Hessenberg matrix has zero entries above the first superdiagonal...
form.
Tridiagonalization
This procedure is taken from the book: Numerical Analysis, Burden and Faires, 8th Edition.In the first step, to form the Householder matrix in each step we need to determine
and r, which are:;;From
and r, construct vector v:where
, , and for each k=3,4 ..nThen compute:
Having found
and computed the process is repeated for k =2, 3, ..., n as follows:;; for j=k+2; k+3,..., nContinuing in this manner, the tridiagonal and symmetric matrix is formed.
Examples
This example is taken from the book "Numerical Analysis" by Richard L. Burden (Author), J. Douglas Faires. In this example, the given matrix is transformed to the similar tridiagonal matrix A2 by using Householder Method.Following those step in Householder Method. We have:
The first Householder matrix:
Q1
A1 = Q1AQ1 =
Used A1 to form Q2 =
A2 = Q2A1Q2=
As we can see, the final result is a tridiagonal symmetric matrix which is similar to the original one. The process finished after 2 steps.