Householder transformation

A Householder transformation of a vector ${\bf x}$ is its reflection (mirror image) with respect to a plane or hyperplane (as a mirror) through the origin with unit normal vector ${\bf v}$ ( $\vert\vert{\bf v}\vert\vert=1$):

$${\bf x}'={\bf x}-2 {\bf p}_{\bf v}({\bf x}) ={\bf x}-2{\bf v}{\bf v}^T{\bf x} =({\bf I}-2{\bf v}{\bf v}^T){\bf x}={\bf Px}$$ (51)

where ${\bf p}_{\bf v}({\bf x})={\bf v}{\bf v}^T{\bf x}$ is the projection of ${\bf x}$ onto the unit vector ${\bf v}$, and ${\bf P}={\bf I}-2{\bf v}{\bf v}^T$ is the Householder matrix that converts ${\bf x}$ to its reflection ${\bf x}'$. Given the desired reflection ${\bf x}'$, we can get the normal direction of the reflection plane ${\bf u}={\bf x}-{\bf x}'$, and then normalize it to get ${\bf v}={\bf u}/\vert\vert{\bf u}\vert\vert$. Although the Householder transformation is expressed as a linear transformation ${\bf x}'={\bf Px}$, its computational complexity is $O(N)$, instead of $O(N^2)$ for a general matrix multiplication ${\bf Ax}$.

The Householder matrix ${\bf P}$ is symmetric

$${\bf P}^T=({\bf I}-2{\bf v}{\bf v}^T)^T={\bf I}-2{\bf v}{\bf v}^T={\bf P}$$ (52)

and orthogonal:

$${\bf P}^T{\bf P}={\bf P}{\bf P} = ({\bf I}-2{\bf v}{\bf v}^T)({\bf I}-2{\bf v}{\bf v}^T) ={\bf I}-2{\bf v}{\bf v}^T-2{\bf v}{\bf v}^T +4{\bf v}{\bf v}^T{\bf v}{\bf v}^T$$

$$= {\bf I}-4{\bf v}{\bf v}^T+4{\bf v}{\bf v}^T={\bf I}$$ (53)

i.e., ${\bf P}={\bf P}^T={\bf P}^{-1}$. As vector norm is preserved by an orthogonal transform, we have $\vert\vert{\bf x}\vert\vert=\vert\vert{\bf Px}\vert\vert=\vert\vert{\bf x}'\vert\vert$.

We can verify that ${\bf P}$ indeed converts the given ${\bf x}$ into the desired ${\bf x}'$ if ${\bf u}={\bf x}-{\bf x}'$, or $-{\bf x}'$ if ${\bf u}={\bf x}+{\bf x}'$:

$${\bf P}{\bf x} = \left( {\bf I}-\frac{2{\bf u}({\bf x}\pm{\bf x}')^T} {({\bf x}\pm... ...m{\bf x}'^T{\bf x})} {{\bf x}^T{\bf x}\pm2{\bf x}^T{\bf x}'+{\bf x}'^T{\bf x}'}$$

$$= {\bf x}-\frac{{\bf u}({\bf x}^T{\bf x}\pm{\bf x}'^T{\bf x})} {({\... ...pm{\bf x}'^T{\bf x})} ={\bf x}-{\bf u}={\bf x}-({\bf x}\pm{\bf x}')=\mp{\bf x}'$$ (54)

The Householder transformation is typically used to convert a given vector ${\bf x}=[x_1,\cdots,x_N]^T$ into a vector with all but the first one of its components converted to zero:

$${\bf x}'=[x'_1,0,\cdots,0]^T=\vert\vert{\bf x}\vert\vert{\bf e}_1$$ (55)

where ${\bf e}_1=[1,0,\cdots,0]^T$ is the first standard basis vector. In this case, the normal vector needs to be:

$${\bf u}={\bf x}\pm{\bf x}' ={\bf x}\pm\vert\vert\;{\bf x}\vert\vert{\bf e}_1$$ (56)

We note that the reflection ${\bf x}'=\vert\vert{\bf x}\vert\vert\;[1,0,\cdots,0]^T$ is always a real vector. However, when the given vector ${\bf x}$ is complex, the reflection needs to be kept complex as well, instead of being forced to be real. In this case, we should use ${\bf x}'=\vert\vert{\bf x}\vert\vert\;[x_1/\vert x_1\vert,0,\cdots,0]^T$, where $x_1/\vert x_1\vert$ is a normalized complex value based on the first entry of the given vector ${\bf x}$.

By applying a sequence of Householder transformations to the rows and columns of a given square matrix ${\bf A}$, we can convert it into certain desired form, such as a tridiagonal matrix if ${\bf A}$ is symmetric, or a Hessenberg matrix if ${\bf A}$ is non-symmetric. This process is actually a similarity transformation ${\bf Q}{\bf A}{\bf Q}^{-1}$, which preserves the eigenvalues of ${\bf A}$. Some subsequent algorithm can be further applied to solve the eigenvalue problem an arbitrary matrix ${\bf A}$.

We first consider converting a symmetric matrix ${\bf A}={\bf A}^T$ to a tridiagonal matrix. To start, we construct an $N\times N$ square matrix:

$${\bf Q}_1=\left[\begin{array}{c\vert ccc} 1&0&\cdots&0\\ \hline 0& & & \\ \vdots & &{\bf P}_{N-1} & \\ 0& & & \end{array}\right]$$ (57)

where ${\bf P}_{N-1}$ is an $N-1$ dimensional Householder matrix that converts $[a_{21},\cdots,a_{N1}]^T$ containing the last $N-1$ elements of the first column of ${\bf A}$ into $[a'_{21},0,\cdots,0]^T$. Note that ${\bf Q}_1={\bf Q}_1^T={\bf Q}_1^{-1}$ is also symmetric and orthogonal. Pre-multiplying ${\bf Q}_1$ to ${\bf A}$ we get:

$${\bf Q}_1{\bf A} = \left[\begin{array}{c\vert ccc} 1&0&\cdots&0\\ \hline 0& & & \\ \... ...ine a_{21}& & & \\ \vdots & &{\bf A}_{N-1} & \\ a_{N1} & & & \end{array}\right]$$

$$= \left[\begin{array}{c\vert ccc}a_{11}&a_{12}&\cdots&a_{1N}\\ \hli... ...\\ a_{N1}\end{array}\right) & & {\bf P}_{N-1}{\bf A}_{N-1} & \end{array}\right]$$

$$= \left[\begin{array}{c\vert ccc}a_{11}&a_{12}&\cdots&a_{1N}\\ \hli... ...0 & & & \\ \vdots & &{\bf P}_{N-1}{\bf A}_{N-1} & \\ 0 & & & \end{array}\right]$$ (58)

where ${\bf A}_{N-1}$ is an $N-1$ dimensional submatrix containing the lower-right $N-1$ by $N-1$ elements of ${\bf A}$. We see that the last $N-2$ components of the first column of the resulting matrix ${\bf Q}_1{\bf A}$ are zero. We next post-multiply ${\bf Q}_1$ to modify the first row:

$${\bf A}'={\bf Q}_1{\bf A}{\bf Q}_1 = \left[\begin{array}{c\vert ccc} a_{11}&a_{12}&\cdots&a_{1N}\\... ...{\bf P}_{N-1}&\\ \vdots & & & \\ 0& & & \\ \end{array}\right]$$

$$= \left[\begin{array}{c\vert ccc}a_{11}& & [a_{12},\cdots,a_{1N}]{\... ...dots & &{\bf P}_{N-1}{\bf A}_{N-1}{\bf P}_{N-1} & \\ 0 & & & \end{array}\right]$$

$$= \left[\begin{array}{c\vert cccc}a_{11}&a'_{12}&0&\cdots&0\\ \hlin... ...ts &&&{\bf P}_{N-1}{\bf A}_{N-1}{\bf P}_{N-1} & \\ 0 & & & & \end{array}\right]$$ (59)

We see that the last $N-2$ components of the first row and column of ${\bf A}'$ become zero.

This process is then repeated for the lower-right submatrix ${\bf P}_{N-1}{\bf A}_{N-1}{\bf P}_{N-1}$ of ${\bf A}'$. Pre and post multiplying ${\bf A}'$ by

$${\bf Q}_2=\left[\begin{array}{cc\vert ccc} 1&0&0&\cdots&0\\ 0&1&0... ...ne 0&0& & & \\ \vdots &\vdots& &{\bf P}_{N-2} & \\ 0&0& & & \end{array}\right]$$ (60)

we get

$${\bf A}''={\bf Q}_2{\bf A}'{\bf Q}_2={\bf Q}_2{\bf Q}_1{\bf A}{\b... ...{\bf P}_{N-2}{\bf A}_{N-2}{\bf P}_{N-2}& \\ 0 &0& & & & \\ \end{array}\right]$$ (61)

We see that the last $N-3$ components of the second row and column of ${\bf A}''$ become zero. This process is repeated until after $N-1$ iterations the N-D matrix ${\bf A}$ is converted into a tridiagonal matrix, with all entries $a_{ij}$ equal to zero except those along the sub-diagonal ($i=j+1$), the superdiagonal ($i=j-1$) as well as the main diagonal ($i=j$):

$${\bf Q}_{N-1}\cdots{\bf Q}_1{\bf A}{\bf Q}_1\cdots{\bf Q}_{N-1} ={\bf QAQ}^T={\bf QAQ}^{-1}$$ (62)

where we have defined ${\bf Q}={\bf Q}_{N-1}\cdots{\bf Q}_1$. Note that ${\bf Q}$ is not symmetric (a product of symmetric matrices is not symmetric), but it is orthogonal:

$${\bf Q}^T = ({\bf Q}_{N-1}\cdots{\bf Q}_1)^T ={\bf Q}_1^T\cdots{\bf Q}_{N-1}^T$$

$$= {\bf Q}_1^{-1}\cdots{\bf Q}_{N-1}^{-1} =({\bf Q}_{N-1}\cdots{\bf Q}_1)^T={\bf Q}^{-1}$$ (63)

The resulting matrix ${\bf QAQ}^{-1}$, a similarity transformation of ${\bf A}$, has the same eigenvalues as ${\bf A}$.

Based on the example tridiagonalization above, we make a few notes

• One may wonder if the method for tridiagonalizing a symmetric matrix could also diagonalize the matrix, so that all entries become zero, except those on the main diagonal, which become the eigenvalues. Unfortunately, this is impossible, as the entire N-D matrix, instead an (N-1)-D submatrix, needs to be Householder transformed. After the pre-multiplication of a Householder matrix to convert a column, the following post-multiplication of the Householder matrix to convert a row will modify the entire matrix, including the column, thereby destroying the previous results.

• The same algorithm for tridiagonalization of a symmetric matrix can also be applied to a non-symmetric matrix ${\bf A}\ne{\bf A}^T$. However, as its rows are not the same as its columns, while the pre-multiplication of the Householder matrices can convert all entries below the sub-diagonal to zero, the post-multiplication by the the same matrices can no longer convert all entries above the super-diagonal to zero. The resulting matrix ${\bf H}={\bf Q}{\bf A}{\bf Q}^T$, called Hessenberg matrix, is not tridiagonal, as the entries above the super-diagonal are non-zero. The non-symmetric matrix could still be tridiagonalized by post-multiplying the Householder matrices based on its rows (instead its columns). However, as the post-multiplying matrix is not the same as pre-multiplying matrix, this is not a similarity transformation, and the eigenvalues are not preserved.

• We can also convert a non-symmetric matrix ${\bf A}$ into a upper triangular matrix ${\bf R}$ by a sequence of Householder transformations applied only to the columns of ${\bf A}$. This is the QR decomposition to be considered in the next section. Note that this is not a similarity transformation, ${\bf R}$ and ${\bf A}$ do not have the same eigenvalues. However, it can be used as an iterative step in an algorithm for solving the eigenvalue problem.

• The method of Gauss-Jordan elimination based on the elementary row operations can also convert a given matrix ${\bf A}$ into a lower of upper triangular matrix, or even a diagonal matrix. However, this is not a similarity transformation, and the eigenvalues are not preserved. While this method can be used to find the inverse of ${\bf A}$, it cannot be used for solving eigenvalue problem.

Examples: Consider two matrices, one symmetric, one non-symmetric:

• The following symmetric matrix can be converted into a tridiagonal matrix:
  $${\bf A}=\left[\begin{array}{rrrr} 3 & 1 & -4 & 2\\ 1 & 4 & 3 & -1\\ -4 & 3 & -2 & 3\\ 2 & -1 & 3 & 2\end{array}\right]$$
  by
  $${\bf Q}=\left[\begin{array}{rrrr} 1 & 0 & 0 & 0 \\ 0 & -0.218 ... ... 0 & -0.973 & -0.230 & 0.026\\ 0 & -0.078 & 0.430 & 0.899\end{array}\right]$$
  $${\bf QAQ}^T=\left[\begin{array}{rrrr} 3.000 & -4.583 & 0 & 0 \\ ... ...\\ 0 & -1.218 & 5.039 & -0.364\\ 0 & 0 & -0.364 & 3.532\end{array}\right]$$
  The tridiagonal matrix ${\bf QAQ}^T$ and the symmetric matrix ${\bf A}$ share the same eigenvalues $5.6980,\;4.688,\;3.4467,\;-6.832$.

• The following non-symmetric ${\bf A}$ can be converted into a Hessenberg matrix
  $${\bf A}=\left[\begin{array}{rrrr} 3 & 1 & -4 & 2 \\ -2 & 4 & 3 & -1\\ 1 & 2 & -2 & 3 \\ 1 & -1 & 4 & 2\end{array}\right]$$
  by
  $${\bf Q}=\left[\begin{array}{rrrr} 1 & 0 & 0 & 0 \\ 0 & -0.817 ... ... 0 & -0.043 & -0.748 & 0.662\\ 0 & 0.576 & 0.523 & 0.628\end{array}\right]$$
  $${\bf H}={\bf QAQ}^T=\left[\begin{array}{rrrr} 3.000 & -1.633 & 4... ...05\\ 0 & 3.184 &-3.485 & 0.211\\ 0 & 0 &-1.013 & 4.652 \end{array}\right]$$
  The Hessenberg matrix ${\bf H}$ and the non-symmetric matrix ${\bf A}$ share the same eigenvalues $4.961,\;4.0,\;2.219,\;-4.180$.