3
$\begingroup$

Question:

let $A$ is Doubly stochastic matrix,and the eigenvalue such $$\lambda_{1}=1,|\lambda_{j}|<1,(j=2,3,\cdots,n)$$ and the $$e=(1,1,1,\cdots,1)^T$$ show that : for any vector $$x=(a_{1},a_{2},\cdots,a_{n})^T,a_{1}+a_{2}+\cdots +a_{n}=1,a_{i}\ge 0$$, have $$\lim_{m\to\infty}A^mx=\left(\dfrac{e}{n}\right)$$

where Doubly stochastic matrix some properties and some result can see this

My idea: since $$|A|=\lambda_{2}\lambda_{3}\cdots\lambda_{n}<1$$

then I can't find this limit.

and can't solve this problem,

$\endgroup$
  • $\begingroup$ UStrangely phrased question since the RHS (AMD the answer) is the zero vector. They are asking you to prove that $A$ goes to the zero matrix, which might be an easier way to think about it. $\endgroup$ – Stella Biderman Mar 18 '14 at 13:31
  • 2
    $\begingroup$ @nanchangjian, something seems to be wrong in your question: the limit depending on $\;n\;$ , $\;\lim_{n\to\infty} A^nx\;$ cannot be something with $\;n\;$ again ...! $\endgroup$ – DonAntonio Mar 18 '14 at 13:41
  • 1
    $\begingroup$ @GitGud, I see the Very same $\;n\;$ in both sides...and this is wrong. Perhaps you mean he could switch the LHS $\;n\;$ to $\;m\;$ , say? $\endgroup$ – DonAntonio Mar 18 '14 at 13:44
  • 1
    $\begingroup$ Oh,sorry! I have edit.Thank you @DonAntonio $\endgroup$ – user94270 Mar 18 '14 at 13:52
  • 2
    $\begingroup$ No, it is not ok, @GitGud: an expression $$\lim_{n\to\infty}x_n=y_n$$ is intrinsically wrong if the RHS actually depends on $\;n\;$ as was the case in the question. $\endgroup$ – DonAntonio Mar 18 '14 at 14:00
3
$\begingroup$

As hinted in the comments, this is false.

Set $A:=\begin{bmatrix} \frac 1 2 & \frac 1 2\\ \frac 1 2 & \frac 1 2\end{bmatrix}$. Clearly $A^m=A$, for all $m\in \mathbb N$. Therefore with $x=\begin{bmatrix} 1\\ -1\end{bmatrix}$ the equality doesn't hold.

You need to require $x\ge 0$.


Layout of answer to the question post edit: The proof goes something like this.

  1. Firstly prove that the sequence $\left(A^m\right)_{n\in \mathbb N}$ converges. To do this you need to use the fact $1$ is the only eigenvalue of absolute value $1$, that $1$ is the largest eigenvalue and that its algebraic multiplicity is $1$.
  2. The above implies that $\lim \limits_{m\to +\infty}\left(A^my\right)$ exists for all $y\in \mathbb R^{n\times 1}$. Next, letting $B$ be $\lim \limits_{m\to +\infty}\left(A^m\right)$, prove that $AB=B$. This shows that $B$'s columns are all eigenvectors of $A$ associated to the eigenvalue $1$.
  3. Prove that $B$ is stochastic by columns. To do this first prove that for all $m\in \mathbb N$, $A^m$ is stochastic by columns.
  4. From the fact that the columns of $B$ are eigenvectors associated to the eigenvalue $1$ and from the fact that $B$ is column-stochastic, using the hypothesis that $x$'s entries when summed equal $1$, conclude.

You could have asked me for more details instead of wasting reputation points in an unawarded bounty.


Answer: There exists $n\in \mathbb N$ such that $A$ is $n\times n$.

  1. The sequence $\left(A^m\right)_{n\in \mathbb N}$ converges if, and only if, $\left(J^m\right)_{n\in \mathbb N}$, where $J$ is a canonical jordan normal form of $A$. Since $1$ is the only eigenvalue of absolute value $1$, since $1$ is the largest eigenvalue and its algebraic multiplicity is $1$, it's clear from looking at the powers of $J$ that $\left(J^m\right)_{n\in \mathbb N}$ converges and consequently so does $\left(A^m\right)_{n\in \mathbb N}$.
  2. Therefore $\lim \limits_{m\to +\infty}\left(A^my\right)$ exists for all $y\in \mathbb R^{n\times 1}$. Define $B:=\lim \limits_{m\to +\infty}\left(A^m\right)$. Multiplying this definition by $A$ on the left yields $AB=A\lim \limits_{m\to +\infty}\left(A^m\right)=\lim \limits_{m\to +\infty}\left(A^{m+1}\right)=B$. Since $AB=A\left[\text{Col}_1(B)\mid \ldots \mid \text{Col}_n(B) \right]=\left[A\text{Col}_1(B)\mid \ldots \mid A\text{Col}_n(B) \right]$, it follows that the columns of $B$ are eigenvectors of $A$ associated to $1$.
  3. Note that any $n\times n$ matrix $M$ is column-stochastic if, and only if, $(1,e)$ is an eigenpair of $M^T$. It's easy to prove by induction that $\forall m\in \mathbb N\left((A^m)^Te=e\right)$. This fact justifies the third equality below: $$B^Te=\lim \limits_{m\to +\infty}\left((A^m)^T\right)e=\lim \limits_{m\to +\infty}\left((A^m)^Te\right)=\lim \limits_{m\to +\infty}\left(e\right)=e.$$ Therefore $B$ is column-stochastic.
  4. From 2. and 3. follows that $B=\left[\frac en\mid \ldots \mid \frac en\right]$. Given $x$ as in the question, it holds that $$\lim \limits_{m\to +\infty}\left(A^mx\right)=Bx=\begin{bmatrix}\frac 1 n(a_1+\ldots +a_n)\\ \vdots \\ \frac 1 n(a_1+\ldots +a_n)\end{bmatrix}=\dfrac e n.$$
$\endgroup$
  • $\begingroup$ Oh,Thank you, if $x\ge 0$,then this problem is true? $\endgroup$ – user94270 Mar 18 '14 at 14:30
  • $\begingroup$ @nanchangjian Yes, it is. $\endgroup$ – Git Gud Mar 18 '14 at 14:30
  • $\begingroup$ Why? can you post you solution? Thank you $\endgroup$ – user94270 Mar 18 '14 at 14:34
  • $\begingroup$ @nanchangjian I will not post a solution without knowing more about what you know. I asked you something in the comments to the question which facilitates the answer and you ignored my question. For this reason, I don't post a solution. $\endgroup$ – Git Gud Mar 18 '14 at 14:36
  • 1
    $\begingroup$ sorry,My English is poor,and I am not understand your meaning $\endgroup$ – user94270 Mar 18 '14 at 14:52

Your Answer

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