analytic approximation of a non-negative matrix by a sequence of positive matrices - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T18:08:23Z http://mathoverflow.net/feeds/question/90430 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/90430/analytic-approximation-of-a-non-negative-matrix-by-a-sequence-of-positive-matrice analytic approximation of a non-negative matrix by a sequence of positive matrices Ngoc Mai Tran 2012-03-07T06:58:30Z 2013-05-03T16:22:00Z <p>Let $L \in \{0,1\}^{n \times n}$ be a non-negative matrix whose row sum is 1. ($L$ stands for "limit"). It is known that there exists a unique $r \times r$ principal minor of $L$ that is a permutation matrix for some $r$, $1 \leq r \leq n$. Fix an $n \times n$ non-negative matrix $\epsilon$ such that $$\epsilon_{ij} = 0 \Leftrightarrow L_{ij} = 1.$$ For $k > 0$, let $$T(k) = L + E(k)$$ be an analytic perturbation of $L$, where <code>$$E(k)_{ij} = \exp(-kE_{ij}).$$</code> Then $T(k)$ is a positive operator, thus it has a unique principal (Perron) eigenvalue and eigenvector, denoted $\rho(k)$ and $v(k)$, respectively. It is known that as $k \to \infty$, $\rho(k)^{1/k}$ converges to 1 and $v(k)^{1/k}$ (elementwise) converges to the all 1's vector. (This is because we forced the row sum of $L$ to be 1. In general these guys converge to the tropical max-times eigenvalue and eigenvector of $L$, respectively, but this is not important to the question). </p> <p>My question is: for large $k$, what we can say about the "rate of convergence" of the quantities $\rho(k)^{1/k}$ and $v(k)^{1/k}$? By this I mean I want to know have an expansion of the type $$\rho(k)^{1/k} = 1 + \mbox{ (higher order terms in k and \epsilon_{ij})},$$ and I'd like to know the expansion to as much precision as possible. </p> <p>Some thoughts: the eigenvalues of $L$ are the $r$ roots of unity, each with multiplicity 1, and $0$ with multiplicity $n - r$. Thus easy off-the-shelf bounds on the operator norm of $E(k)$ (and Grioschinn-disks type of arguments) give a rate that is dependent on $r$. However, $\rho(k)^{1/k}$ is a real number bigger than 1, thus this sequence is converging towards the real eigenvalue $1$ from above on the real axis in $\mathbb{C}$. Thus the "correct" convergence rate should not depend on $r$ (and this is true in simulations). The reason is these theorems do not take into account the fact that the perturbed operator is positive and that we really have an analytic perturbation. </p> <p>Some pointers on how to handle this problem would be much appreciated. I feel that this type of perturbation must have been studied in the literature (especially physics?) I'm also not familiar with analytic perturbation of operators myself - I've read a little of Baumgartel's book but didn't see immediately relevant results. Reference pointers would also be great. </p> <p>Thanks!</p> <p>Ngoc</p> http://mathoverflow.net/questions/90430/analytic-approximation-of-a-non-negative-matrix-by-a-sequence-of-positive-matrice/90463#90463 Answer by Igor Rivin for analytic approximation of a non-negative matrix by a sequence of positive matrices Igor Rivin 2012-03-07T14:36:09Z 2012-03-07T14:36:09Z <p>I might be misunderstanding something, but why is this not a standard perturbation estimate, of the sort studied exhaustively in the first chapter of Kato's perturbation theory, or Golub-Van Loan, or Horn-Johnson? There will be a difference depending on whether the Perron-Frobenius eigenvalue has multiplicity 1, or higher than one (in the latter case the matrix can be block diagonalized into permutation matrices).</p>