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?

$\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$ Sep 3, 2023 at 14:47
  • 1
    $\begingroup$ Closely related, perhaps a duplicate: What is the most efficient way to diagonalize small matrices? $\endgroup$
    – hardmath
    Sep 3, 2023 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$ Sep 4, 2023 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$ Sep 4, 2023 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$ Sep 5, 2023 at 6:29

1 Answer 1

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.

$\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, 2023 at 15:33
  • $\begingroup$ Thanks, the connection to the characteristic polynomial makes it perfectly clear. $\endgroup$
    – Aurelius
    Sep 3, 2023 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$ Sep 4, 2023 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$ Sep 4, 2023 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$ Sep 4, 2023 at 13:26

Your Answer

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

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