Householder Method for Tridiagonalization: Ver. 1.0

Taisuke Ozaki, ISSP, the Univ. of Tokyo

The Householder method [1] is a way of transforming a Hermitian matrix $B$ to a real symmetric tridiagonalized matrix $B_{\rm TD}$ . Let ${\bf b}$ be a column vector of $B$ , and consider that the vector ${\bf b}$ consists of the real part ${\bf b}_{r}$ and the imaginary part ${\bf b}_{i}$ as

\displaystyle|{\bf b}\rangle=|{\bf b}_{r}\rangle+i|{\bf b}_{i}\rangle.

(1)

Also let us introduce a vector ${\bf s}$ of which real part has just one non-zero component $s(=\sqrt{\langle{\bf b}|{\bf b}\rangle})$ and imaginary part is a zero vector as

\displaystyle|{\bf s}\rangle=\left(\begin{array}[]{c}s\\ 0\\ \cdot\\ \cdot\\ 0\end{array}\right)+i\left(\begin{array}[]{c}0\\ 0\\ \cdot\\ \cdot\\ 0\end{array}\right).

(2)

Then, consider a mirror transform $Q^{{\dagger}}$ bridging the two vectors ${\bf b}$ and ${\bf s}$ by

\displaystyle Q^{{\dagger}}=I-\alpha^{*}|{\bf v}\rangle\langle{\bf v}|,

(3)

where let us assume that

\displaystyle|{\bf s}\rangle=Q^{{\dagger}}|{\bf b}\rangle.

(4)

Putting Eq. (3) into Eq. (4), and solving it with respect to $|{\bf v}\rangle$ , we have

\displaystyle|{\bf v}\rangle=\frac{1}{\alpha^{*}\langle{\bf v}|{\bf b}\rangle}% \left(|{\bf b}\rangle-|{\bf s}\rangle\right).

(5)

Thus, Eq. (5) allows us to write $|{\bf v}\rangle$ as

\displaystyle|{\bf v}\rangle=\beta\left(|{\bf b}\rangle-|{\bf s}\rangle\right)% =\beta|{\bf u}\rangle.

(6)

If ${\bf v}$ is normalized, $\beta$ is given by

$\displaystyle\beta$	$\displaystyle=$	$\displaystyle\frac{1}{\sqrt{(\langle{\bf b}\|-\langle{\bf s}\|)(\|{\bf b}\rangle-% \|{\bf s}\rangle)}},$	(7)
	$\displaystyle=$	$\displaystyle\frac{1}{\sqrt{\langle{\bf b}\|{\bf b}\rangle+\langle{\bf s}\|{\bf s% }\rangle-\langle{\bf b}\|{\bf s}\rangle-\langle{\bf s}\|{\bf b}\rangle}},$
	$\displaystyle=$	$\displaystyle\frac{1}{\sqrt{2s^{2}-\langle{\bf b}\|{\bf s}\rangle-\langle{\bf s% }\|{\bf b}\rangle}}.$

Comparing Eqs. (5) with (6) and making use of Eq. (7), we have

\displaystyle\alpha^{*}=\frac{2a_{r}}{a_{r}^{2}+a_{i}^{2}}(a_{r}-ia_{i})

(8)

with $a_{r}$ and $a_{i}$ given by

\displaystyle a_{r}=\frac{1}{2}\left(2s^{2}-\langle{\bf b}|{\bf s}\rangle-% \langle{\bf s}|{\bf b}\rangle\right)

(9)

and

\displaystyle a_{i}=\langle{\bf b}_{i}|{\bf s}\rangle.

(10)

Then, it is verified that

$\displaystyle QQ^{{\dagger}}$	$\displaystyle=$	$\displaystyle\left(I-\alpha\|{\bf v}\rangle\langle{\bf v}\|\right)\left(I-\alpha% ^{*}\|{\bf v}\rangle\langle{\bf v}\|\right),$	(11)
	$\displaystyle=$	$\displaystyle I-\alpha^{}\|{\bf v}\rangle\langle{\bf v}\|-\alpha\|{\bf v}\rangle% \langle{\bf v}\|+\alpha\alpha^{}\|{\bf v}\rangle\langle{\bf v}\|{\bf v}\rangle% \langle{\bf v}\|,$
	$\displaystyle=$	$\displaystyle I-\frac{(2a_{r})^{2}}{a_{r}^{2}+a_{i}^{2}}\|{\bf v}\rangle\langle% {\bf v}\|+\frac{(2a_{r})^{2}}{a_{r}^{2}+a_{i}^{2}}\|{\bf v}\rangle\langle{\bf v}\|,$
	$\displaystyle=$	$\displaystyle I.$

Thus, the transformation $Q^{{\dagger}}BQ$ for the Hermitian matrix $B$ is a similarity transformation, and given by

	$\displaystyle Q^{{\dagger}}BQ$	$\displaystyle=$	$\displaystyle\left(I-\alpha^{*}\|{\bf v}\rangle\langle{\bf v}\|\right)B\left(I-% \alpha\|{\bf v}\rangle\langle{\bf v}\|\right),$		(12)
		$\displaystyle=$	$\displaystyle B-\alpha^{}\|{\bf v}\rangle\langle{\bf v}\|B-\alpha B\|{\bf v}% \rangle\langle{\bf v}\|+\alpha^{}\alpha\|{\bf v}\rangle\langle{\bf v}\|B\|{\bf v}% \rangle\langle{\bf v}\|.$		(12)

By defining

\displaystyle|{\bf p}\rangle\equiv B|{\bf v}\rangle,

(13)

Eq. (12) becomes

	$\displaystyle Q^{{\dagger}}BQ$	$\displaystyle=$	$\displaystyle B-\alpha^{}\|{\bf v}\rangle\langle{\bf p}-\alpha\|{\bf p}\rangle% \langle{\bf v}\|+\alpha^{}\alpha\|{\bf v}\rangle\langle{\bf v}\|{\bf p}\rangle% \langle{\bf v}\|,$		(14)
		$\displaystyle=$	$\displaystyle B-\alpha^{}\|{\bf v}\rangle\left(\langle{\bf p}\|-\frac{\alpha}{2% }\langle{\bf v}\|{\bf p}\rangle\langle{\bf v}\|\right)-\alpha\left(\|{\bf p}% \rangle-\frac{\alpha^{}}{2}\|{\bf v}\rangle\langle{\bf v}\|{\bf p}\rangle\right% )\langle{\bf v}\|.$		(14)

Moreover, by defining

\displaystyle|{\bf q}\rangle\equiv\alpha\left(|{\bf p}\rangle-\frac{\alpha^{*}% }{2}|{\bf v}\rangle\langle{\bf v}|{\bf p}\rangle\right),

(15)

we have a compact form:

\displaystyle Q^{{\dagger}}BQ=B-|{\bf v}\rangle\langle{\bf q}|-|{\bf q}\rangle% \langle{\bf v}|.

(16)

For the numerical stability, we furthermore modify Eq. (16) as shown below. Let us introduce a vector ${\bf p}^{\prime}$ as.

\displaystyle|{\bf p}^{\prime}\rangle=\frac{B|{\bf u}\rangle}{\frac{|{\bf u}|^% {2}}{2}}.

(17)

Then, ${\bf p}$ can be written by ${\bf p}^{\prime}$ as

$\displaystyle\|{\bf p}\rangle$	$\displaystyle=$	$\displaystyle B\|{\bf v}\rangle,$	(18)
	$\displaystyle=$	$\displaystyle\frac{B\|{\bf u}\rangle}{\sqrt{2a_{r}}},$
	$\displaystyle=$	$\displaystyle\frac{\|{\bf p}^{\prime}\rangle a_{r}}{\sqrt{2a_{r}}},$
	$\displaystyle=$	$\displaystyle\frac{\sqrt{2a_{r}}}{2}\|{\bf p}^{\prime}\rangle.$

Also, noting that

\displaystyle|{\bf v}\rangle=\frac{1}{\sqrt{2a_{r}}}|{\bf u}\rangle,

(19)

${\bf q}$ can be rewritten by

\displaystyle|{\bf q}\rangle=\alpha\frac{\sqrt{2a_{r}}}{2}\left(|{\bf p}^{% \prime}\rangle-\frac{\alpha^{*}}{4a_{r}}|{\bf u}\rangle\langle{\bf u}|{\bf p}^% {\prime}\rangle\right).

(20)

Putting Eqs. (19) and (20) into Eq. (16), we have

\displaystyle Q^{{\dagger}}BQ=B-|{\bf u}\rangle\langle{\bf q}^{\prime}|-|{\bf q% ^{\prime}}\rangle\langle{\bf u}|

(21)

with ${\bf q^{\prime}}$ defined by

\displaystyle|{\bf q}^{\prime}\rangle=\frac{\alpha}{2}\left(|{\bf p}^{\prime}% \rangle-\frac{\alpha^{*}}{4a_{r}}|{\bf u}\rangle\langle{\bf u}|{\bf p}^{\prime% }\rangle\right),

(22)

where

\displaystyle|{\bf p}^{\prime}\rangle=\frac{1}{a_{r}}B|{\bf u}\rangle.

(23)

The transformation by Eq. (21) can be applied to each column vector step by step in which the place occupied by $s$ in Eq. (2) is shifted one by one. Then, the tridiagonalized matrix $B_{\rm TD}$ is given by

\displaystyle B_{\rm TD}=Q_{n-1}^{{\dagger}}Q_{n-2}^{{\dagger}}\cdots Q_{3}^{{% \dagger}}Q_{2}^{{\dagger}}Q_{1}^{{\dagger}}BQ_{1}Q_{2}Q_{3}\cdots Q_{n-2}Q_{n-% 1}.

(24)

References

[1] A. S. Householder, J. ACM 5, 339 (1958).