analytic approximation of a non-negative matrix by a sequence of positive matrices

2012-03-07T06:58:30Z

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 $$ E(k)_{ij} = \exp(-kE_{ij}). $$ 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).

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.

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.

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.

Thanks!

Ngoc

Answer by Igor Rivin for analytic approximation of a non-negative matrix by a sequence of positive matrices

2012-03-07T14:36:09Z

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

analytic approximation of a non-negative matrix by a sequence of positive matrices - MathOverflow

analytic approximation of a non-negative matrix by a sequence of positive matrices

Answer by Igor Rivin for analytic approximation of a non-negative matrix by a sequence of positive matrices