0
$\begingroup$

I am learning numerical linear algebra and curious about one thing. It is possible to reduce any matrix to the Hessenberg form in finite steps with a unitary matrix. But why is it impossible to reduce it further into an upper triangular form in finite step?

What is the fundamental barrier?

$\endgroup$

1 Answer 1

1
$\begingroup$

If you could reduce to a triangular matrix $A = QTQ^*$ (a Schur factorization) in a finite number of steps (involving elementary arithmetic operations and n-th roots only), this would violate the Abel-Ruffini theorem: it would allow you to exactly (neglecting roundoff errors) compute roots of arbitrary polynomials in a finite number of steps.

The reason is that the diagonal entries of the triangular matrix $T$ are equal to the eigenvalues of $A$, and for any degree-$n$ polynomial $p(z)$ you can find the roots by transforming $p$ into a corresponding $n \times n$ matrix (a companion matrix).

The Abel–Ruffini theorem says that it is impossible to find the roots of an arbitrary polynomial of degree 5 or higher in a finite number of elementary steps (there is no "quintic formula"). That tells us that it is impossible to find the Schur factorization of an arbitrary matrix (exactly) in a finite number of steps for matrices $5 \times 5$ or larger. Hence, all Schur algorithms (unlike Hessenberg reductions) are approximate "iterative" algorithms that approach the factor $T$ but never exactly reach it (but in practice can quickly approximate $T$ to any desired precision).

(Proving the Abel–Ruffini theorem is nontrivial! It was one of the great triumphs of 19th-century mathematics, resolving a question that had puzzled mathematicians for 2000 years.)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .