Householder transformation: Information from Answers.com

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 decompositions and in the first step of the QR algorithm. The Householder transformation was introduced in 1958 by Alston Scott Householder.^[1]

Its analogue over general inner product spaces is the Householder operator.

1 Definition and properties
2 Applications
- 2.1 Tridiagonalization
- 2.2 Examples
3 Notes
4 References
5 External links

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 point x about this hyperplane is:

$x - 2\langle v,x\rangle v = x - 2 v (v^* x),$

where v is given as a column unit vector with Hermitian transpose v^*. This is a linear transformation given by the Householder matrix:

$P = I - 2 vv^*.\,$

where I is the identity matrix.

The Householder matrix has the following properties:

it is Hermitian: $P = P^*\,$
it is unitary: $P^{-1}=P^*\,$
hence it is involutary: $P^2=I\,$ .

Applications

Main article: 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 (i, i) minors of that product.

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

Tridiagonalization

Main article: tridiagonal matrix

This procedure is taken from the book: Numerical Analysis, Burden and Faires, 8th Edition. In the first step, to form the household matrix in each step we need to determine $\displaystyle \alpha$ and r, which are:

$\displaystyle \alpha = -sgn(a_{21})\sqrt{\sum_{j=2}^{n}a_{j1}^2}$ ;

$r = \sqrt{\frac{1}{2}(\alpha^{2}-a_{21}\alpha)}$ ;

From $\displaystyle \alpha$ and r, construct vector v:

$v^{(1)} = \begin{bmatrix} v_1\\v_2\\...\\v_n \end{bmatrix}$ , where $v 1 = 0;$ , $v_2 = \frac{a_{21}-\alpha}{2r}$ , and $v_k = \frac{a_{k1}}{2r}$ for each k=3,4 ..n

Then compute:

$\displaystyle P^{1} = I - 2v^{(1)}(v^{(1)})^t$

$\displaystyle A^{(1)} = P^{1}AP^{1}$

Having found $\displaystyle P^{1}$ and compute $\displaystyle A^{(1)}$ the process is repeated for k =2; 3 ..n as follow:

$\displaystyle \alpha = -sgn(a_{k+1,k})\sqrt{\sum_{j=k+1}^{n}a_{jk}^2}$ ;

$r = \sqrt{\frac{1}{2}(\alpha^{2}-a_{k+1,k}\alpha)}$ ;

$v^{k}_1=v^{k}_2=..=v^{k}_k=0;$

$v^{k}_{k+1} = \frac{a^{k}_{k+1,k}-\alpha}{2r}$

$v^{k}_j = \frac{a^{k}_{jk}}{2r}$ for j=k+2; k+3,..., n

$\displaystyle P^{k} = I - 2v^{(k)}(v^{(k)})^t$

$\displaystyle A^{(k+1)} = P^{k}A^{(k)}P^{k}$

Continuing 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 A₂ by using Householder Method.

$\mathbf{A} = \begin{bmatrix} 4&1&-2&2 \\ 1 & 2 &0&1 \\ -2 & 0 &3& -2 \\ 2 & 1 & -2&-1 \end{bmatrix},$

Following those step in Householder Method. We have:

The first Householder matrix:

Q₁ $\mathbf{} = \begin{bmatrix} 1&0&0&0 \\ 0 &-1/3&2/3&-2/3 \\ 0 & 2/3 &2/3& 1/3 \\ 0 & -2/3 &1/3& 2/3 \end{bmatrix},$

A₁ = Q₁AQ₁ = $\mathbf{}\begin{bmatrix} 4&-3&0&0 \\ -3 & 10/3 &1&4/3 \\ 0 & 1 &5/3& -4/3 \\ 0 & 4/3 & -4/3&-1 \end{bmatrix},$

Used A₁ to form Q₂ = $\mathbf{}\begin{bmatrix} 1&0&0&0 \\ 0&1 &0&0 \\ 0 & 0 &-3/5&-4/5 \\ 0 & 0 & -4/5&3/5 \end{bmatrix},$

A₂ = Q₂A₁Q₂= $\mathbf{}\begin{bmatrix} 4&-3&0&0 \\ -3 &10/3 &-5/3&0 \\ 0 & -5/3 &-33/25& 68/75 \\ 0 &0 & 68/75&149/75 \end{bmatrix},$

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.

Notes

^ Householder, A. S. (1958). "Unitary Triangularization of a Nonsymmetric Matrix". Journal of the ACM 5 (4): 339–342. doi:10.1145/320941.320947. MR 0111128.

References

Morrison, D.D. (1960). "Remarks on the Unitary Triangularization of a Nonsymmetric Matrix". Journal of the ACM 7 (2): 185–186. doi:10.1145/321021.321030. MR 0114291.
LaBudde, C.D. (1963). "The reduction of an arbitrary real square matrix to tridiagonal form using similarity transformations". Mathematics of Computation 17 (84): 433–437. MR 0156455. JSTOR 2004005.
Francesco Mezzadri, How to Generate Random Matrices from the Classical Compact Groups, Notices of the AMS, May 2007, Volume 54, Issue 5, pp. 592-604. arXiv:math-ph/0609050

External links

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

Donate to Wikimedia

	What are the energy transformations nuclear energy goes through to become household electricity? Read answer...
	What is transformation? Read answer...
	What does transformer do? Read answer...

	A transformer decreases household voltage from 120V to 6V to power a 4W electric motor?
	Why do transformers transform?
	What is AN on a transformer?

Householder transformation

Contents