Editing Divide-and-conquer eigenvalue algorithm (section)

==Divide==

The ''divide'' part of the divide-and-conquer algorithm comes from the realization that a tridiagonal matrix is "almost" block diagonal.
<!-- For original TeX, see image description page -->
:[[Image:Almost block diagonal.png]]

The size of submatrix <math>T_{1}</math> we will call <math>n \times n</math>, and then <math>T_{2}</math> is <math>(m - n) \times (m - n)</math>.  <math>T</math> is almost block diagonal regardless of how <math>n</math> is chosen.  For efficiency we typically choose <math>n \approx m/2</math>.

We write <math>T</math> as a block diagonal matrix, plus a [[Rank (linear algebra)|rank-1]] correction:
<!-- For original TeX, see image description page -->
:[[Image:Block diagonal plus correction.png]]

The only difference between <math>T_{1}</math> and <math>\hat{T}_{1}</math> is that the lower right entry <math>t_{nn}</math> in <math>\hat{T}_{1}</math> has been replaced with <math>t_{nn} - \beta</math> and similarly, in <math>\hat{T}_{2}</math> the top left entry <math>t_{n+1,n+1}</math> has been replaced with <math>t_{n+1,n+1} - \beta</math>.

The remainder of the divide step is to solve for the eigenvalues (and if desired the eigenvectors) of <math>\hat{T}_{1}</math> and <math>\hat{T}_{2}</math>, that is to find the [[diagonalizable matrix|diagonalization]]s <math>\hat{T}_{1} = Q_{1} D_{1} Q_{1}^{T}</math> and <math>\hat{T}_{2} = Q_{2} D_{2} Q_{2}^{T}</math>.  This can be accomplished with recursive calls to the divide-and-conquer algorithm, although practical implementations often switch to the QR algorithm for small enough submatrices.