# Estimating the spectral radius of a matrix, noniteratively

Morris Marden's "Geometry of Polynomials" displays a number of formulae that allow one to estimate bounds on the largest root of a polynomial that do not involve actual rootfinding. Having been inspired by this, and since this particular problem crops up in one of the things I'm working on, I was wondering if one could get good estimates of the spectral radius of a general dense n-by-n matrix A that has been previously processed as follows:

1. a similarity transformation to upper Hessenberg form ($A=QHQ^T$, $Q$ orthogonal and $H$ upper Hessenberg); and
2. subtracting the identity multiplied by the mean of the eigenvalues from $H$ ($H'=H-\frac{trace(H)}{n}I$, this corresponds geometrically to centering the eigenvalues around the origin of the complex plane).

As much as possible, I am trying to avoid having to resort to an eigenvalue method (e.g. QR (too much effort!), power method (the power method can misbehave when there is more than one eigenvalue whose modulus is equal to the spectral radius)) since I only need a quick 2-3 digit approximation of the spectral radius. I have considered actually expanding $H'$ to its characteristic polynomial (equivalently, a similarity transformation of $H'$ to a Frobenius companion matrix) so that the formulae listed in Marden can apply, but after reading Wilkinson's wonderful book "The Algebraic Eigenvalue Problem" where he details how unstable the computation of coefficients of the characteristic polynomial can get from a matrix, I suppose that idea is shot.

My other naïve attempts at estimating the spectral radius include using $||H'||_\infty$ as an estimate, and deriving rough bounds using Gerschgorin's theorem; the problem I've seen is that both attempts tend to overestimate the spectral radius by a significant factor.

Is there a way to estimate the spectral radius more cheaply and noniteratively than actually computing eigenvalues?

-
I would guess no. The matrix $A = \begin{pmatrix} 0 & N \\ 0 & 0 \end{pmatrix}$ has spectral radius $0$, whereas the matrix $B = \begin{pmatrix} 0 & N \\ \frac{1}{\sqrt{N}} & 0 \end{pmatrix}$ has spectral radius $\sqrt{N}$. So in order to compute the spectral radius you need to look at all entries, and not ignore small ones. –  Helge Aug 13 '10 at 9:19
Well I am certainly not expecting an O(n) algorithm for this to exist! ;) As I had already mentioned, all the matrices I will be dealing with have already undergone a preliminary reduction to upper Hessenberg form, and I suppose the problem eases slightly if the Hessenberg matrix is reducible (in that I can consider diagonal blocks separately). –  J. M. Aug 13 '10 at 9:27
So you want something between better than O(n^3), I guess. The example above shows that one at least needs O(n^2). I guess the method based on Gerschgorin's theorem is a O(n^2) algorithm ... –  Helge Aug 13 '10 at 12:41
Then compute $B = A^* A$, which is O(n^3) many operations, and then compute the largest eigenvalue of $B$, should work. –  Helge Aug 13 '10 at 17:36
Er... A* is the conjugate transpose here, right? So this is a prescription to find the largest singular value (a.k.a. the 2-norm) of A. I need the modulus of the largest eigenvalue of A, and that's not the same thing unless A is symmetric (which on the other hand does succumb to a Gerschgorin-based algorithm (since all eigenvalues of a symmetric matrix are real ;) ), as I have found). Symmetric matrices really are so much nicer! –  J. M. Aug 13 '10 at 23:25