MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
    
What's N? ..... – Scott Morrison Dec 14 '09 at 18:07
4  
The spectral radius is a continuous function of the matrix (for the roots of a polynomial depend continuously on tits coefficients). By using explicit continuity results (like those given in [Marden, Morris. The Geometry of the Zeros of a Polynomial in a Complex Variable. Mathematical Surveys, No. 3. American Mathematical Society, New York, N. Y., 1949. ix+183 pp.]) you may find explicit expressions for open intervals contained in the set $\{a:\rho(\hat A)<1\}$. – Mariano Suárez-Alvarez Dec 14 '09 at 19:29
1  
Scott: I think $N=n$. – Greg Kuperberg Dec 14 '09 at 23:30
3  
I am used to thinking of complex vector spaces, but do you mean the maximum of the absolute values of the real eigenvalues? If so, the spectral radius will often be $-\infty$ I guess. In any case, I'll give you an example where the spectral radius is increased by replacing an element by 0, which by scaling shows that 0 will not generally be in the set. Let n=N=2 and let A be the matrix with -1 in the bottom right and 1 elsewhere. Let i=2. Then the spectral radius of A is $\sqrt2$, but replacing $A_{22}$ by 0 yields a matrix whose spectral radius is $(1+\sqrt5)/2$. – Jonas Meyer Dec 15 '09 at 5:40
2  
You can edit your answer. Please correct it and state all of your relevant hypotheses. For instance, are you assuming as in mathoverflow.net/questions/10885 that the matrix is a pseudometric? And the elements that are supposed to replace an entry, are they also assumed to be positive? And did you mean to be replacing entries by a, or perturbing them by a as the answers below assumed? – Jonas Meyer Jan 6 '10 at 5:38

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$.

share|cite|improve this answer

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$.)

share|cite|improve this answer

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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