Editing Divide-and-conquer eigenvalue algorithm (section)

==Conquer==

The ''conquer'' part of the algorithm is the unintuitive part.  Given the diagonalizations of the submatrices, calculated above, how do we find the diagonalization of the original matrix?

First, define <math>z^{T} = (q_{1}^{T},q_{2}^{T})</math>, where <math>q_{1}^{T}</math> is the last row of <math>Q_{1}</math> and <math>q_{2}^{T}</math> is the first row of <math>Q_{2}</math>.  It is now elementary to show that
:<math>T = \begin{bmatrix} Q_{1} & \\ & Q_{2} \end{bmatrix} \left( \begin{bmatrix} D_{1} & \\ & D_{2} \end{bmatrix} + \beta z z^{T} \right) \begin{bmatrix} Q_{1}^{T} & \\ & Q_{2}^{T} \end{bmatrix}</math>

The remaining task has been reduced to finding the eigenvalues of a diagonal matrix plus a rank-one correction.  Before showing how to do this, let us simplify the notation.  We are looking for the eigenvalues of the matrix <math>D + w w^{T}</math>, where <math>D</math> is diagonal with distinct entries and <math>w</math> is any vector with nonzero entries. In this case <math>w = \sqrt{|\beta|}\cdot z</math>.

The case of a zero entry is simple, since if w<sub>i</sub> is zero, (<math>e_i</math>,d<sub>i</sub>) is an eigenpair (<math>e_i</math> is in the standard basis) of <math>D + w w^{T}</math> since
<math>(D + w w^{T})e_i = De_i = d_i e_i</math>.

If <math>\lambda</math> is an eigenvalue, we have:
:<math>(D + w w^{T})q = \lambda q</math>
where <math>q</math> is the corresponding eigenvector.  Now
:<math>(D - \lambda I)q + w(w^{T}q) = 0</math>
:<math>q + (D - \lambda I)^{-1} w(w^{T}q) = 0</math>
:<math>w^{T}q + w^{T}(D - \lambda I)^{-1} w(w^{T}q) = 0</math>
Keep in mind that <math>w^{T}q</math> is a nonzero scalar. Neither <math>w</math> nor <math>q</math> are zero. If <math>w^{T}q</math> were to be zero, <math>q</math> would be an eigenvector of <math>D</math> by <math>(D + w w^{T})q = \lambda q</math>. If that were the case, <math>q</math> would contain only one nonzero position since <math>D</math> is distinct diagonal and thus the inner product <math>w^{T}q</math> can not be zero after all. Therefore, we have:
:<math>1 + w^{T}(D - \lambda I)^{-1} w = 0</math>
or written as a scalar equation,
:<math>1 + \sum_{j=1}^{m} \frac{w_{j}^{2}}{d_{j} - \lambda} = 0.</math>
This equation is known as the ''secular equation''. The problem has therefore been reduced to finding the roots of the [[rational function]] defined by the left-hand side of this equation.

All general eigenvalue algorithms must be iterative,{{Citation needed|date=April 2024}} and the divide-and-conquer algorithm is no different.  Solving the [[nonlinear]] secular equation requires an iterative technique, such as the [[Newton's method|Newton–Raphson method]].  However, each root can be found in [[Big O notation|O]](1) iterations, each of which requires <math>\Theta(m)</math> flops (for an <math>m</math>-degree rational function), making the cost of the iterative part of this algorithm <math>\Theta(m^{2})</math>.