Editing Eigenvalue algorithm (section)

==Algorithms==

The most reliable and most widely used algorithm for computing eigenvalues is [[John G. F. Francis]]' and [[Vera N. Kublanovskaya]]'s [[QR algorithm]], considered one of the top ten algorithms of 20th century.<ref name="t10">{{cite journal |last1=J. Dongarra and F. Sullivan |title=Top ten algorithms of the century |journal=Computing in Science and Engineering |date=2000 |volume=2 |page=22-23|doi=10.1109/MCISE.2000.814652 }}</ref>

Any monic polynomial is the characteristic polynomial of its [[companion matrix]]. Therefore, a general algorithm for finding eigenvalues could also be used to find the roots of polynomials. The [[Abel–Ruffini theorem]] shows that any such algorithm for dimensions greater than 4 must either be infinite, or involve functions of greater complexity than elementary arithmetic operations and fractional powers. For this reason algorithms that exactly calculate eigenvalues in a finite number of steps only exist for a few special classes of matrices. For general matrices, algorithms are [[Iterative method|iterative]], producing better approximate solutions with each iteration.

Some algorithms produce every eigenvalue, others will produce a few, or only one. However, even the latter algorithms can be used to find all eigenvalues. Once an eigenvalue {{math|''λ''}} of a matrix {{math|''A''}} has been identified, it can be used to either direct the algorithm towards a different solution next time, or to reduce the problem to one that no longer has {{math|''λ''}} as a solution.

Redirection is usually accomplished by shifting: replacing {{math|''A''}} with {{math|''A'' − ''μI''}} for some constant {{math|''μ''}}. The eigenvalue found for {{math|''A'' − ''μI''}} must have {{math|''μ''}} added back in to get an eigenvalue for {{math|''A''}}. For example, for [[power iteration]], {{math|1=''μ'' = ''λ''}}. Power iteration finds the largest eigenvalue in absolute value, so even when {{math|''λ''}} is only an approximate eigenvalue, power iteration is unlikely to find it a second time. Conversely, [[inverse iteration]] based methods find the lowest eigenvalue, so {{math|''μ''}} is chosen well away from {{math|''λ''}} and hopefully closer to some other eigenvalue.

Reduction can be accomplished by restricting {{math|''A''}} to the column space of the matrix {{math|''A'' − ''λI''}}, which {{math|''A''}} carries to itself. Since {{math|''A'' - ''λI''}} is singular, the column space is of lesser dimension. The eigenvalue algorithm can then be applied to the restricted matrix. This process can be repeated until all eigenvalues are found.

If an eigenvalue algorithm does not produce eigenvectors, a common practice is to use an inverse iteration based algorithm with {{math|''μ''}} set to a close approximation to the eigenvalue. This will quickly converge to the eigenvector of the closest eigenvalue to {{math|''μ''}}. For small matrices, an alternative is to look at the column space of the product of {{math|''A'' − ''λ''{{'}}''I''}} for each of the other eigenvalues {{math|''λ''{{'}}}}.

A formula for the norm of unit eigenvector components of normal matrices was discovered by Robert Thompson in 1966 and rediscovered independently by several others.<ref>{{cite journal |last1=Thompson |first1=R. C. |author-link=Robert Charles Thompson |title=Principal submatrices of normal and Hermitian matrices |journal=Illinois Journal of Mathematics |date=June 1966 |volume=10 |issue=2 |pages=296–308 |doi=10.1215/ijm/1256055111 |doi-access=free }}</ref><ref>{{cite journal |author1=Peter Nylen |author2=Tin-Yau Tam |author3=Frank Uhlig |title=On the eigenvalues of principal submatrices of normal, hermitian and symmetric matrices |journal=Linear and Multilinear Algebra |date=1993 |volume=36 |issue=1 |pages=69–78 |doi=10.1080/03081089308818276}}</ref><ref>{{cite journal |vauthors=Bebiano N, Furtado S, da Providência J |title=On the eigenvalues of principal submatrices of J-normal matrices |journal=Linear Algebra and Its Applications |date=2011 |volume=435 |issue=12 |pages=3101–3114 |doi=10.1016/j.laa.2011.05.033 |doi-access=free }}</ref><ref>{{cite journal | vauthors=Forrester PJ, Zhang J | arxiv=1905.05314 | title=Corank-1 projections and the randomised Horn problem | journal=Tunisian Journal of Mathematics | year=2021 | volume=3 | pages=55–73 | doi=10.2140/tunis.2021.3.55 | s2cid=153312446 }}</ref><ref>{{cite journal | vauthors= Denton PB, Parke SJ, Tao T, Zhang X | arxiv=1908.03795 | title=Eigenvectors from eigenvalues: A survey of a basic identity in linear algebra | journal=Bulletin of the American Mathematical Society | year=2021 | volume=59 | page=1 | doi=10.1090/bull/1722 | s2cid=213918682 }}</ref>
If {{math|''A''}} is an <math display="inline"> n \times n</math> normal matrix with eigenvalues {{math|''λ''<sub>''i''</sub>(''A'')}} and corresponding unit eigenvectors {{math|'''v'''<sub>''i''</sub>}} whose component entries are {{math|''v''<sub>''i,j''</sub>}}, let {{math|''A''<sub>''j''</sub>}} be the <math display="inline"> n - 1 \times n - 1</math> matrix obtained by removing the {{math|''i''}}-th row and column from {{math|''A''}}, and let {{math|''λ''<sub>''k''</sub>(''A''<sub>''j''</sub>)}} be its {{math|''k''}}-th eigenvalue. Then
<math display="block"> |v_{i,j}|^2 \prod_{k=1,k\ne i}^n (\lambda_i(A) - \lambda_k(A)) = \prod_{k=1}^{n-1}(\lambda_i(A) - \lambda_k(A_j))</math>

If <math>p, p_j</math> are the characteristic polynomials of <math>A</math> and <math>A_j</math>, the formula can be re-written as 
<math display="block"> |v_{i,j}|^2 = \frac{p_j(\lambda_i(A))}{p'(\lambda_i(A))}</math>
assuming the derivative <math>p'</math> is not zero at <math>\lambda_i(A)</math>.