## 2 The Matrix Diagonalization
### [PERSON]'s Divide and Conquer Approach  
The main idea behind [PERSON]'s algorithm is to solve two more minor problems and join the solution with a rank-one modification. So, we have two independent diagonalizations. Then, to use this strategy, we must have an initial symmetric tridiagonal matrix:  
\[T= \begin{pmatrix}a_{1}&b_{1}&&&0\\ b_{1}&a_{2}&b_{2}&&\\ &\ddots&\ddots&\ddots&\\ &&b_{n-2}&a_{n-1}&b_{n-1}\\ 0&&&b_{n-1}&a_{n}\end{pmatrix} ,\]  
which can be separated as follows [3]  
\[T= \begin{pmatrix}\ddots&\ddots&&\\ \ddots&a_{m-1}&b_{m-1}\\ &b_{m-1}&a_{m}\mp b_{m}\\ \mathit{ine}&&&\\ &&&&\\ &&&\ddots&\ddots\end{pmatrix} + \begin{pmatrix}&&\\ b_{m}&\pm b_{m}\\ &\mathit{ine}\pm b_{m}&b_{m}\\ &&\\ \end{pmatrix} ,\]  
with \(m\approx\dfrac{n}{2}\), so we have two symmetric tridiagonal matrices  
\[T_{1}= \begin{pmatrix}a_{1}&b_{1}&&&0\\ b_{1}&a_{2}&b_{2}&&\\ &\ddots&\ddots&\ddots&\\ &&b_{m-2}&a_{m-1}&b_{m-1}\\ 0&&&b_{m-1}&a_{m}\mp b_{m}\end{pmatrix} \]  
and  
\[T_{2}= \begin{pmatrix}a_{m+1}\mp b_{m}&b_{m+1}&&&0\\ b_{m+1}&a_{m+2}&b_{m+2}&&\\ &\ddots&\ddots&\ddots&\\ &&b_{n-2}&a_{n-1}&b_{n-1}\\ 0&&&b_{n-1}&a_{n}\end{pmatrix} ,\]  
Hence, the original matrix is given by  
\[T= \begin{pmatrix}T_{1}&0\\ 0&T_{2}\end{pmatrix} +\rho\mathbf{u}\mathbf{u}^{T},\]where  
\[\mathbf{u}=\begin{array}{c}m\rightarrow\\ m+1\rightarrow \begin{pmatrix}0\\ \vdots\\ 0\\ 1\\ 0\\ \vdots\\ 0\end{pmatrix} \qquad\text{and}\qquad\rho=\pm b_{m}.\]  
Thus, there are two separate diagonalization problems. \[T_{1}=Q_{1}\Lambda_{1}Q_{1}^{T}\qquad\text{and}\qquad T_{2}=Q_{2}\Lambda_{2}Q_ {2}^{T},\]  
where  
\[\Lambda_{1}= \begin{pmatrix}\lambda_{1}&&&0\\ &\lambda_{2}&&\\ &&\ddots&\\ 0&&&\lambda_{m}\end{pmatrix} ,\qquad\Lambda_{2}= \begin{pmatrix}\lambda_{m+1}&&&0 \\ &\lambda_{m+2}&&\\ &&\ddots&\\ 0&&&\lambda_{n}\end{pmatrix} ,\]  
and  
\[D= \begin{pmatrix}\Lambda_{1}&0\\ 0&\Lambda_{2}\end{pmatrix} .\]  
The original matrix \(T\) can be rewritten as  
\[T= \begin{pmatrix}Q_{1}&0\\ 0&Q_{2}\end{pmatrix} \left\{ \begin{pmatrix}\Lambda_{1}&0\\ 0&\Lambda_{2}\end{pmatrix} +\rho\mathbf{v}\mathbf{v}^{T}\right\} \begin{pmatrix} Q_{1}&0\\ 0&Q_{2}\end{pmatrix} ^{T},\]  
with  
\[\mathbf{v}= \begin{pmatrix}Q_{1}&0\\ 0&Q_{2}\end{pmatrix} ^{T}\]  
The original matrix \(T\) has the same eigenvalues as the rank-one modification \(M\):  
\[M\equiv D+\rho\mathbf{v}\mathbf{v}^{T}, \tag{6}\]  
whose eigenvalues \(\Lambda\) are given by the secular equation  
\[0=1+\rho\sum_{i=1}^{n}\frac{v_{i}^{2}}{d_{i}-\lambda}.\]  
The eigenvectors of \(M\) are  
\[y_{i}=(D-\lambda_{i}I)^{-1}\mathbf{v}. \tag{7}\]  
Eigenvectors associated with the original matrix \(T\) are given by  
\[q_{i}= \begin{pmatrix}Q_{1}&0\\ 0&Q_{2}\end{pmatrix} y_{i}.\]  
A better description of the algorithm can be found in [17; 18; 19; 20]. Principal difficulties when implementing this algorithm are the solving of secular equation [21] and keeping eigenvectors orthogonality [18]. Equation (7) is used to calculate the eigenvectors of \(D+\mathbf{v}\mathbf{v}^{T}\), and we can lose the orthogonality of the eigenvectors. To avoid this, [PERSON] and [PERSON] [18] propose the following equations to compute the vectors \(v_{k}\) for matrix \(\mathbf{v}\) in Equation (6) and the eigenvalues \(q_{i}\) of \(M\) of Equation (6):  
\[v_{k}^{\prime} = \text{sign}\left(v_{k}\right)\sqrt{\frac{\prod_{j=1}^{k-1}\left(d_{ k}-\lambda_{j}\right)\prod_{j=k}^{n}\left(\lambda_{j}-d_{k}\right)}{\prod_{j=1}^{k-1} \left(d_{k}-d_{j}\right)\prod_{j=k+1}^{n}\left(d_{j}-d_{k}\right)}}, \tag{8}\] \[q_{i} = \frac{(D-\lambda_{i}I)^{-1}\mathbf{v}^{\prime}}{\parallel(D- \lambda_{i}I)^{-1}\mathbf{v}^{\prime}\parallel}. \tag{9}\]  
Symmetric Tridiagonal Eigenvalue Solvers are building blocks for general problems such as general eigenvalue solvers [22; 23]. Furthermore, the divide-and-conquer approach can be extended to singular-value solvers [24]. The relevance of our work lies in the many eigenvalue applications in the scientific and engineering fields, especially in electronic structures [25; 26].