Lanczos tridiagonalization made simple

on 2021/08/23

Given a real symmetric matrix $A$, one way to tridigonalize $A$ is the Lanczos procedure which I will introduce below. To transform $A$ into a tridiagonal matrix $T$, we need an orthogonal matrix $U$: $U^\dagger A U = T$ which implies $UT=AU$. Here,
$$ T = \begin{pmatrix} \alpha_1 & \beta_2 & & & \\ \beta_2 & \alpha_2 & \beta_3 & & \\ & \ddots & \ddots & \ddots &\\ & & \beta_{N-1} & \alpha_{N-1} &\beta_{N}\\ & & & \beta_N &\alpha_{N}\\ \end{pmatrix}. $$

We set $U=[\vec v_1,\vec v_2,\vec v_3,\cdots,\vec v_N]$ where $\vec v_i$ is a column of $U$ and the $\vec v_i$’s are orthogonal to each other. We further use the equation $UT=AU$ to obtain the relationships of the vectors $\vec v_1,\vec v_2,\vec v_3,\cdots,\vec v_N$. The left side of the equation $UT=AU$, $U T$ is equal to
$$ \left[ \begin{array}{c|c|c|c|c} \alpha_1\vec v_1 + \beta_2\vec v_2 & \beta_2\vec v_1 + \alpha_2\vec v_2 + \beta_3 \vec v_3 & \cdots & \beta_{N-1}\vec v_{N-2} + \alpha_{N-1}\vec v_{N-1} + \beta_N \vec v_N & \beta_N\vec v_{N-1} + \alpha_N\vec v_N \end{array}\right] $$
where the vertical bars separate each column from the others. On the right side of the equation $UT=AU$, $AU$ is equal to
$$ \left[ \begin{array}{c|c|c|c|c} A\vec v_1 & A\vec v_2 & \cdots & A \vec v_{N-1} & A \vec v_{N} \end{array}\right]. $$

As a result, we have a set of equations of $v_i$’s:
$$ \begin{align} \alpha_1\vec v_1 + \beta_2\vec v_2 &= A\vec v_1 \\ \beta_2\vec v_1 + \alpha_2\vec v_2 + \beta_3 \vec v_3 &= A\vec v_2 \\ \vdots\\ \beta_{N-1}\vec v_{N-2} + \alpha_{N-1}\vec v_{N-1} + \beta_N \vec v_N &= A \vec v_{N-1}\\ \beta_N\vec v_{N-1} + \alpha_N\vec v_N &= A \vec v_N \end{align} $$
which can be used to recursively solve for the columns ($v_i$’s) of the matrix $U$. This is what Lanczos tridiagonalization does.

References

[1] https://blog.csdn.net/seventonight/article/details/116450549.