4
$\begingroup$

I have small dense square matrices for which I would like to compute the inverse by singular value decomposition, or equivalently solve the eigenvalue problem.

While there are many direct methods for the solution or inverse of square matrices (eg gaussian elimination or LU decomposition) there is no such thing for the eigenvalue problem.

Is there an intuitive reason why such an algorithm doesn't exist?

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ Computing the characteristic polynomial is expensive. And for degree greater there are no direct solution formulas, so you would be back at iterative methods anyway. It has been tried, but bulk-chasing implicit QR methods are just to efficient. // But study again the need to compute and use the inverse, SVD or any other way. Linear solver work well with just the factorization/decomposition. $\endgroup$
    – Lutz Lehmann
    Sep 3 at 14:47
  • 1
    $\begingroup$ Closely related, perhaps a duplicate: What is the most efficient way to diagonalize small matrices? $\endgroup$
    – hardmath ♦
    Sep 3 at 15:31
  • 1
    $\begingroup$ @LutzLehmann I think you're missing a "four" between "And for degree greater than" than "there are no direct solution fomulas", as degree five is where there are no longer algebraic solutions in general. $\endgroup$
    – Acccumulation
    Sep 4 at 4:11
  • $\begingroup$ Although even algebraic solutions are iterative, I believe. I don't know of any non-iterative methods of finding square roots, for instance. $\endgroup$
    – Acccumulation
    Sep 4 at 17:44
  • $\begingroup$ @Acccumulation : That depends on what you understand as the "bad kind " of "iterative". There exist algorithms for the roots/surds that compute them digit-by-digit. This is still iterative, unavoidably so, but has a precise complexity that is not worse than a multiplication of the same precision. Then again, it is also unavoidably close to the "bad" Newton or Newton-like iterations. // The same hair-splitting applies to the reduction of (linear) differential equations to quadrature. Does that count under symbolic/analytical solution? $\endgroup$
    – Lutz Lehmann
    Sep 5 at 6:29

1 Answer 1

Reset to default
10
$\begingroup$

There is simply no closed-form expression in terms of the four operations and radicals for the eigenvalues of a matrix greater than $4\times 4$.

This follows from the facts that (1) there are polynomials of degree 5 with integer coefficients whose solutions do not have a closed formula, and (2) the roots of a polynomial can be expressed as the eigenvalues of a suitable matrix.

Improve this answer
$\endgroup$
6
  • 4
    $\begingroup$ In this old (10+ years) Answer I gave some references to direct methods for exact representation of polynomial roots of degree $\gt 4$. $\endgroup$
    – hardmath ♦
    Sep 3 at 15:33
  • $\begingroup$ Thanks, the connection to the characteristic polynomial makes it perfectly clear. $\endgroup$
    – Aurelius
    Sep 3 at 18:51
  • $\begingroup$ Abel-Ruffini is certainly relevant to the question, but it's wrong to imply that "no solution in radicals is available" is equivalent to "an iterative algorithm must be used". $\endgroup$
    – leftaroundabout
    Sep 4 at 13:05
  • $\begingroup$ @leftaroundabout Even if you reduce the problem to special functions, you will still need some sort of iteration to compute their value. $\endgroup$
    – Federico Poloni
    Sep 4 at 13:18
  • $\begingroup$ @FedericoPoloni even if you reduce the problem to radicals, you will still need some sort of iteration to compute their value. $\endgroup$
    – leftaroundabout
    Sep 4 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.