2

I have a real matrix whose two largest eigenvalues are two conjugate complex numbers. I need to check if their absolute value is greater than 1.

Since the largest by absolute value eigenvalue is complex, the power method, and any other method that can only output real eigenvalues, doesn't apply.

I looked into using numerical methods. Scipy, numpy and tensorflow libraries have an "eigvals" function. It outputs an eigenvalue with absolute value 1.02. I need to know the error bounds of the eigvals function, to understand if this proves that the absolute value is greater than 1.

What I found from documentation: tensorflow.linalg.eigvals uses the C++ Eigen library, which computes eigenvalues using the Shur decomposition. Documentation says: "The Schur decomposition is computed by first reducing the matrix to Hessenberg form using the class HessenbergDecomposition. The Hessenberg matrix is then reduced to triangular form by performing Francis QR iterations with implicit double shift." Wikipedia says that a bound on the error of the QR algorithm is provided by the Gerschgorin circle theorem. I'd like to know how can I practically compute this error bound, and how does the floating point precision factor into it?

If there are other approaches to checking if the spectral radius is greater than 1, I'm insterested in them, too.

UPD: Just occured to me I could use Gelfand's formula: r(A) = \lim_{n\to\infty} ||A^n||^{1\n}, so if powers of A have big eigenvalues, then the spectral radius is above 1? But then how do I prove that numerical errors during matrix multiplication didn't alter the result?

seed
  • 131
  • 1
    see this wiki page for application of the power method to complex eigenpairs. https://en.wikiversity.org/wiki/Numerical_Analysis/Power_iteration_examples#Example:_Complex_eigenvalue (in short: your initial guess just can't be strictly real) – John Madden Jun 23 '23 at 21:15
  • 1
    oh PS the folks on Mathematics SE probably have more interesting things to say about this than we do. – John Madden Jun 23 '23 at 21:16
  • This question is off-topic, but I’ll attempt to answer it anyway. Given a square matrix $A$, if there exists a positive-definite matrix $P$ such that $A^TPA - P < 0$, then all of the eigenvalues of $A$ are less than or equal to $1$ in magnitude. If there does not exist such $P$, then at least one of the eigenvalues has a magnitude greater than $1$. For details, see https://en.m.wikibooks.org/wiki/LMIs_in_Control/Click_here_to_continue/LMIs_in_system_and_stability_Theory/Discrete-time_Lyapunov_Stability. – mhdadk Jun 23 '23 at 21:20
  • 1
    Multiply the putative eigenvector by the original matrix. You should get back the eigenvector multiplied by its eigenvalue plus some noise. Project this onto the eigenvector (presumably you can control the magnitude of the numerical errors for this step). If the magnitude of the projection still exceeds $1,$ then perforce the eigenvalue must have magnitude greater than $1,$ too. Thus, unless you're really close to the unit circle, all you really need is a reasonably accurate method to obtain the first eigenvector of the matrix. – whuber Jun 23 '23 at 22:22

0 Answers0