6
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Who is this Grioschinn, of whom you speak? $\endgroup$
    – Igor Rivin
    Commented Mar 7, 2012 at 14:32
  • $\begingroup$ @IgorRivin: Probably the OP means Gerschgorin. $\endgroup$
    – Federico Poloni
    Commented Mar 7, 2012 at 15:25
  • $\begingroup$ Yes, sorry for the mutated spelling... $\endgroup$
    – Ngoc Mai Tran
    Commented Mar 8, 2012 at 2:46

2 Answers 2

Reset to default
1
$\begingroup$

The paper

  • Dmitri Alekseevky, Andreas Kriegl, Mark Losik, Peter W. Michor: Choosing roots of polynomials smoothly, Israel J. Math 105 (1998), p. 203-233. (pdf)

given an algorithmic approach to the real analytic parameterization of eigenvalues. Maybe this can help. See also here for a later overview of available results.

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ To my understanding this is why: in this case the limiting eigenvalue always has multiplicity 1, but there are r-1 other guys of the same modulus. If the perturbation was not known to be of the above form, then these other eigenvalues play a role in the estimate, and hence the standard theory gives a bound on the error term that depends on $r$. But in this case, the perturbation is such that the perturbed eigenvalue always live on the real axis, and it approaches the limit from the right-hand side. Thus I think the bound on the error term should not depend on $r$, and... $\endgroup$
    – Ngoc Mai Tran
    Commented Mar 8, 2012 at 2:52
  • $\begingroup$ And the convergence should be faster than that can be obtained from Kato chapter 1. Also, this is an analytic perturbation, so we should be able to write down some series expansion explicitly in terms of $\epsilon_{ij}$ and $k$. I don't think these immediately come out of Kato's chapter 1. (But I suspect that it can be obtained elsewhere) $\endgroup$
    – Ngoc Mai Tran
    Commented Mar 8, 2012 at 2:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .