spectral radius of a matrix as one element changes

Question

Here's my question --

Let $A$ be an $n \times n$ real matrix, and suppose that the spectral radius $\rho(A)$ is less than one (spectral radius = max eigenvalue). Let's choose some $1 \leq i \leq N$ and look at $A_{N,i}$. Namely, let's replace $A_{N,i}$ with some new value, $a$, to give us a new matrix $\hat A$. I want to characterize the set $\lbrace a : \rho(\hat A) < 1 \rbrace$. It pretty clear that this set is of the form $[0, a_{max})$, but I want to be able to compute $a_{max}$ analytically, given $A$ and $i$. (Also clearly $a_{max} \geq A_{N,i}$, since $\rho(A) < 1$ by assumption.)

This seems like it should be a fairly easy exercise but I haven't been able to make any useful progress on it.

Thanks!

-h

Answer 1

Under your assumptions (all matrix elements positive), the spectral radius is the same as the largest positive eigenvalue, so you just need to figure out for which $a$ the determinant of $\widehat A-I$ is zero, which is a linear equation in $a$.

Answer 2

What you are asking is what some people (like me :-)) call a stability radius problem. The one that you are asking for is indeed a special case of solved problems. The key is to formulate you perturbation in a structured way. So assume we want to perturb the entry in position $(i,j)$ and write $$ A_{j,i} = A + e_i \delta e_j^T$$ where $e_i,e_j$ denote the standard unit vectors with a $1$ at position $i$, resp. $j$ and zero else; and $\delta$ is real. If you really only want to perturb entries in row $N$, just choose $i=N$.

I am unfortunately not sure what you really want to assume. If indeed all entries of the unperturbed matrix are nonnegative, then the problem is particularly simple. Also whether the entry of the unperturbed matrix is $0$ or some other value is a bit unclear (to me that is, unfortunately). Anyway, I will just carry on and mention when these problems become of interest. In any case, it is not "pretty clear" that the interval of interest is of the form $[0,a_\max)$, unless a nonnegativity constraint is imposed. Otherwise, the interval would have to be open, as the set of matrices with spectral radius less than $1$ is open.

The key to the problem is to consider the rational function $$ G(s) = e_j^T(sI - A)^{-1} e_i .$$

If indeed all entries of the unperturbed matrix $A$ are nonnegative and the entry at position $(i,j)$ is zero, then for $a_\max$ as you defined it, we have $$ a_\max = 1/G(1) .$$ The formulation in your case is particularly simple as your perturbation is $1$-dimensional. The result extends to higher dimensional structured perturbation. This is a result of Hinrichsen and Son here

The same formula applies in the case that the value of the unperturbed matrix $A$ is in fact some other positive value, say $a_{ij}$, just that in this case the result would be that $$ a_{\max} = a_{ij} + G(1).$$

Now, if it was indeed the intention that $A$ is a general matrix with real entries and no positivity constraints, then the picture changes. On the one hand the claim in the original problem that the set we are looking form is "clearly" of the form $[0,a_\max)$ is not true. It is not hard to come by real matrices whose spectral radius turns from less than $1$ to larger than $1$ if you set one entry to $0$.

This aside, if the question is to determine the interval around an entry for which the matrix is stable, the key is still the function $G(s)$ it just becomes a bit more involved. All this is discussed in detail in Hinrichsen and Pritchard, Mathematical Systems Theory I, Springer 2005. Look for "real stability radius" (as you are considering real perturbations $\delta$.)

Answer 3

Compute the SVD of A: A = U D V.

Now solve E_{ij} = U B V; getting B= U^* E_{ij} V^*.

Assuming that you mean that your a is the perturbation, and not the value at ij, You are trying to find the the spectral radius of D + a B. This might be a little easier (from a numerical point of) then your original problem if your B is simple enough.

Answer 4

I'll assume that A is positive. I'll also assume as in the previous answer that a is the perturbation. The eigenvalues of high powers of a matrix are dominated by its largest eigenvalue. Thus, we obtain the following close expression of the ratio of the larget eigenvalue of the perturbed and nonperturbed matrices:

ratio = lim_n-->inf (trace((A + a *E_Ni)^n/trace(A^n))^(1/n))

In general, this expression converges very fast.