8
$\begingroup$

I'm trying to prove a standard result: for a positive $n \times n$ matrix $A$, the powers of $A$ scaled by its leading eigenvalue $\lambda$ converge to a matrix whose columns are just scalar multiples of $A$'s leading eigenvector $\mathbf{v}$. More precisely, $$ \lim_{k \rightarrow \infty} \left(\frac{A}{\lambda}\right)^k = \mathbf{v}\mathbf{u},$$ where $\mathbf{v}$ and $\mathbf{u}$ are the leading right and left eigenvectors of $A$, respectively (scaled so that $\mathbf{u}\mathbf{v} = 1$).

These notes give a nice compact proof, pictured below. (It covers the more general case where $A$ is primitive, but I'm happy to assume it's positive for my purposes.)

I'm stuck on the highlighted step. Having established the existence of a matrix $M$ that (a) fixes $\mathbf{u}$ and $\mathbf{v}$, and (b) annihilates all other generalized eigenvalues of $A$, how do we know $M$ is unique? Why couldn't there be other matrices satisfying (a) and (b)?

I don't know much about generalized eigenvectors. I gather they're linearly independent, hence form a basis for $\mathbb{R}^n$. So each column of $M$ must be a unique linear combination of $A$'s generalized right eigenvectors. Is there some path I'm not seeing from there to the conclusion that only one matrix can satisfy both (a) and (b)?


enter image description here enter image description here

$\endgroup$
  • 1
    $\begingroup$ The generalized eigenvectors of $A$ form a basis of $\mathbb R^n$, and if two linear maps agree on a basis, they're equal. $\endgroup$ – Gunnar Þór Magnússon Jun 12 at 15:22
  • $\begingroup$ Ah! Thank you. If you want to post this as an answer I'll gladly give it a check. (Maybe expand on it a bit for any future readers, if you're willing. E.g. put it in terms of matrices instead of linear transformations; say explicitly what it means for for $A$ and $B$ to agree on a basis; and write out why they must then agree on all vectors.) $\endgroup$ – Jonathan Jun 12 at 16:44
  • $\begingroup$ Actually, on second thought, doesn't this raise the question: why does the proof need to bother with the left generalized eigenvectors? The right ones form a basis, and we know how $M$ behaves on them, so we have $M$ pinned down uniquely. Shouldn't it suffice, then, to verify that $\mathbf{v}\mathbf{u}$ acts on that basis as $M$ does, to conclude $M = \mathbf{v}\mathbf{u}$? $\endgroup$ – Jonathan Jun 13 at 1:21
1
+100
$\begingroup$

You may dispense with left eigenvectors when proving the result, but calling for the one of them is a comfortable path to the explicit expression for $$M=\lim_{k\to\infty}J^k$$ where $\,J=\lambda^{-1}\!A\,\in M_n\big(\mathbb R^{>0}\big)\,$ for notational convenience.
All the good properties from $A$, due to Perron & Frobenius, carry over to $J$: Its leading eigenvalue is $1$, the eigenspace is spanned by one positive vector $v$, and all its other eigenvalues live in the interior of the complex unit disc.
This is the reason why $M\,$ has an $n\!-\!1$-dimensional kernel, as worked out in M. Boyle's notes, cf the question-embedded screen-shot, and only the fixed points of $J$ are not annihilated in the limit, i. e., the $1$-dimensional eigenspace to the eigenvalue $1$ which equals $\operatorname{span}(v)$. Hence $M\,$ has rank $1$, and it is uniquely determined because $M$ is known on all of $\,\mathbb R^n$.

Notice that left eigenvectors of a matrix are in 1-to-1 correspondence to the right eigenvectors of its transpose. The transpose $J^T$ satisfies the assumptions for Perron & Frobenius as well as $J$, whence there exists a positive left eigenvector $u$ of $J$ to the eigenvalue $1$. Analogous to $v$, it survives in the limit.

Since $M\,$ has rank $1$, let's make the ansatz $M=v\,\langle ?|\cdot\rangle\,$. Then $M^T\!=\, ?\,\langle v|\cdot\rangle\,$, and $$Mv =v\,\langle ?|v\rangle = v\quad\text{and}\quad M^T\!u=\, ?\,\langle v|u\rangle = u$$ yield $M=v\,\langle u|\cdot\rangle \equiv vu\,$ with $\,uv\equiv\langle u|v\rangle =1$.

Note that $M$ is idempotent. It is selfadjoint (hence an orthogonal projector) if and only if $v$ and $u$ are scalar multiples of each other (thus linear dependent).

Furthermore, one has $v=\lim\limits_{k\to\infty}\,(J^kw)\,$ where $w>0\,$ is an arbitrary positive vector.

PS & IMHO
$(1)\:$ If you seek to master this result and its proof, you shouldn't consider projectors, kernels, images as "additional machinery" but integrate them into your picture.
$(2)\:$ In this same spirit I'd like to add that loup blanc's answer follows M. Boyle's path more than it's different to it.

$\endgroup$
  • $\begingroup$ Thanks, this is very helpful. (Not trying to avoid mastering add'l machinery incidentally; just looking for as simple and elementary a path to this particular result I can get, for purposes of teaching/communication with others.) $\endgroup$ – Jonathan 5 hours ago
2
$\begingroup$

According to PF theorem, the characteristic polynomial of $A$ is in the form $\chi_A(x)=(x-\lambda)f(x)$ where $\lambda>0$ and the roots of $f$ have modulus $<\lambda$. Moreover, there is a (unique up to a factor) vector $v>0$ s.t. $Av=\lambda v$. Since $A^T$ is primitive, there is a (unique up to a factor) vector $u>0$ s.t. $u^TA=\lambda u^T$. Since $u^Tv>0$, we can choose the above factors s.t. $u^Tv=1$.

There is a basis in the form $v,\cdots$ s.t., for this change of basis of matrix $P\in M_n(\mathbb{R})$, $A=Pdiag(\lambda,B_{n-1})P^{-1}$ where $\chi_B(x)=f(x)$; then $B$ has a spectral radius $\rho(B)<\lambda$, that is, $\rho(\lambda^{-1}B)=\mu<1$.

Thus $(\lambda^{-1}A)^k=Pdiag(1,(\lambda^{-1}B)^k)P^{-1}$ tends, when $k\rightarrow\infty$, to the rank $1$ projector $M=Pdiag(1,0_{n-1})P^{-1}$; moreover, for every $\epsilon>0$, $||(\lambda^{-1}A)^k-M||=O((\dfrac{\mu+\epsilon}{\lambda})^k)$.

A projector is uniquely defined by $im(M)$ and $\ker(M)=(im(M^T))^{\perp}$, that is, by $im(M), im(M^T)$.

Notice that $Mv=\lim_k (\lambda^{-1}A)^kv=v,u^TM=\lim_k u^T(\lambda^{-1}A)^k=u^T$. Then the rank $1$ projector $M$ is uniquely defined by $im(M)=span(v),im(M^T)=span(u)$.

Now $R=vu^T$ is also a projector with image $span(v)$ and $im(R^T)=span(u)$. Then $M=vu^T$.

$\endgroup$
  • $\begingroup$ Thanks for this detailed response! Unless I've misunderstood though, it doesn't quite address the issues listed in the bounty. First is the question why the proof pictured in the OP makes use of the left generalized eigenvectors in addition to the right ones. Given Magnússon's comment, it seems the right ones should suffice. Second, this proof seems more like a different path to the desired result than an explanation of the path cited in the OP. Third, more accessible answers are preferred here, whereas this answer imports a fair amount of additional machinery (projectors, kernels, images). $\endgroup$ – Jonathan Jun 18 at 16:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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