4

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?

Aurelius
  • 2,365
  • 1
  • 15
  • 19
  • 3
    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. – Lutz Lehmann Sep 03 '23 at 14:47
  • 1
    Closely related, perhaps a duplicate: What is the most efficient way to diagonalize small matrices? – hardmath Sep 03 '23 at 15:31
  • 1
    @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. – Acccumulation Sep 04 '23 at 04:11
  • Although even algebraic solutions are iterative, I believe. I don't know of any non-iterative methods of finding square roots, for instance. – Acccumulation Sep 04 '23 at 17:44
  • @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? – Lutz Lehmann Sep 05 '23 at 06:29

1 Answers1

10

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.

Federico Poloni
  • 11,344
  • 1
  • 31
  • 59
  • 4
    In this old (10+ years) Answer I gave some references to direct methods for exact representation of polynomial roots of degree $\gt 4$. – hardmath Sep 03 '23 at 15:33
  • Thanks, the connection to the characteristic polynomial makes it perfectly clear. – Aurelius Sep 03 '23 at 18:51
  • 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". – leftaroundabout Sep 04 '23 at 13:05
  • @leftaroundabout Even if you reduce the problem to special functions, you will still need some sort of iteration to compute their value. – Federico Poloni Sep 04 '23 at 13:18
  • @FedericoPoloni even if you reduce the problem to radicals, you will still need some sort of iteration to compute their value. – leftaroundabout Sep 04 '23 at 13:26
  • @leftaroundabout Yes, I agree with what you are implying: in the end, it boils down to what we consider iteration and what we do not, so the line between direct and iterative is very blurred. – Federico Poloni Sep 04 '23 at 14:25