View Question
 Dear Sir/Madam, Let M be a real square matrix with only non-negative entries. Let t be a scalar such that t>=0. Let M_t be defined as the matrix resulting from addition of t to all null entries in M. I believe that the spectral radius of M_t is a continuous function of t (in particular, continuous at 0). Can this proven? Thanking you in anticipation, d Request for Question Clarification by mathtalk-ga on 13 Jun 2005 07:50 PDT Hi, dvd03-ga: By "null entries" in M, should a Researcher understand you to mean the zero entries of M? regards, mathtalk-ga Clarification of Question by dvd03-ga on 13 Jun 2005 08:05 PDT Dear mathtalk Yes, zero entries. Your thoughts? At the mo I'm working along the following lines: I'm defining, B as a matrix with 1s where M, correspondingly, has 0s, and 0s where M, correspondingly, has non-zeros. I'm then saying that the eigenvalues \lambda_{M_t} are given as the roots of det(M+t*B-lambda*I)=0. If we let t -> 0 then (though I've not yet got a tidy proof of this) the eigenvalues tend to the roots of det(M-lambda*I)=0 which are the eigenvalues of M. From which, if we concern ourselves purely with max |\lambda_M|, the spectral radius of M_t is continuous at 0 with respect to t. What do you reckon? D Request for Question Clarification by mathtalk-ga on 13 Jun 2005 17:20 PDT Hi, dvd03-ga: As I'm sure you recall from this previous Question: [Page Rank Definition - Proof of convergence and uniqueness] http://answers.google.com/answers/threadview?id=379557 by Perron's theorem, once the (square) matrix is strictly positive, it has a unique (positive) maximum eigenvalue, which thus equals the spectral radius. It is true that the spectral radius of M_t is a continuous function of t (continuous at 0 in particular), but the function is not in general analytic or even differentiable there. A simple example illustrates what can happen if M has a "largest" eigenvalue of multiplicity > 1. Take first a symmetric 2 by 2 case, M = I. Then: det(xI - M_t) = (x-1)^2 - t^2 and we have roots x = 1 + t, 1 - t. Thus spectral radius of M_t is 1 + |t| and fails to be differentiable at t = 0 (but is continuous there, of course). Slightly worse behavior can be obtained with a nonsymmtric matrix: / 1 1 \ M_t = | | \ t 1 / where the characteristic polynomial will have two real roots for t > 0 or two complex conjugate roots for t < 0, so in effect the "paths" of the roots take a right angle turn (in the complex plane0 at t = 0. If you are simply interested in the continuity of the roots of the characteristic equation (as a function of the coefficients), and hence of the continuity of the spectral radius of M_t as a function of t, I'd be happy to post an Answer that focuses on this proof. regards, mathtalk-ga Clarification of Question by dvd03-ga on 14 Jun 2005 08:38 PDT Dear mathtalk, have you an email address? Request for Question Clarification by mathtalk-ga on 15 Jun 2005 18:35 PDT Hi, dvd03-ga: The Terms of Service at Google Answers do not permit Researchers to contact Customers other than through the mechanisms provided on the site (Answers, Comments, Request for Clarification, etc.). The basic idea you have is correct, that the roots of the characteristic polynomial depend continuously on its coefficients (which of course in this case are "nice" functions of the parameter t that you've introduced), and in particular the spectral radius of M_t is continuous as a function of t. More can be said in this particular case, because the spectral radius of M_t corresponds by Perron's Thm. to a simple positive (real) eigenvalue, but without knowing what applications you may have in mind, I don't know what additional facts might be of interest. regards, mathtalk-ga Clarification of Question by dvd03-ga on 20 Jun 2005 08:18 PDT Dear mathtalk, I think I've managed to concoct a proof - please see https://www.doc.ic.ac.uk/~dvd03/chaoticRelaxation.pdf (page 5) for my efforts. Your thoughts? The concocted proof serves as the final part of my proof to part 2 of Chazan & Miranker's main theorem (Chaotic Relaxation, Linear Algebra Applications, 2: 199-222, 1969). I didn't understand the proof given by Chazan and Miranker. Could you please explain their proof to me? Also, and probably even more importantly, could you please expain their proof to part 3 of the theorem. I'm currently stuck. Many thanks. dvd Clarification of Question by dvd03-ga on 20 Jun 2005 08:20 PDT Or, rather: http://www.doc.ic.ac.uk/~dvd03/chaoticRelaxation.pdf Clarification of Question by dvd03-ga on 22 Jun 2005 10:59 PDT The paper to which I refer, Chaotic Relaxation, may be found at: http://www.doc.ic.ac.uk/~dvd03/cm.pdf