8
$\begingroup$

I was studying the following type of matrices, $$ A = \begin{pmatrix} 1 & x_{12} & \cdots &x_{1n}\\ 0 & x_{22} & \cdots &x_{2n}\\ \vdots\\ 0&\cdots&0&x_{nn} \end{pmatrix},$$ where

  • $x_{ij} \in [0,1];$
  • $x_{jj} \neq 1$ for all $j > 1;$
  • $\displaystyle \sum^n_{i=1}x_{ji} = 1$ for all $j \in \{1,2,\cdots,n\}.$

On random simulation, I am getting $$ \lim_{N \rightarrow \infty} A^N \rightarrow \begin{pmatrix} 1 & 1 & \cdots &1\\ 0 & 0 & \cdots &0\\ \vdots\\ 0&\cdots&0&0 \end{pmatrix}. $$ My question is, what is the cause of this behavior?

I tried the following:
Let $A = \mathbf{1} + U$, where $\mathbf{1}$ is the identity matrix of size $n \times n.$
$$ A^N = (\mathbf{1} + U)^N = \sum^N_{k = 0}\binom{N}{k}U^k $$ but this is certainly not helping much.
Note that: A can be understood as the State transition matrix of a Markov Chain, where one can stay in its state or go to a lower state with a probability.
Additional Observation: $\displaystyle \lim_{N\rightarrow \infty} U^N = \mathbf{0}$
Special Thanks: @tsnao for enhancing clarity and pointing errors.

$\endgroup$
14
  • $\begingroup$ are the $x_{ij} \geq 0 \; ? \; $ $\endgroup$
    – Will Jagy
    Dec 27, 2022 at 18:48
  • $\begingroup$ Am I right that it follows from your description that $x_{nn} = 1$? Wouldn't it remain the same for all powers? $\endgroup$
    – tsnao
    Dec 27, 2022 at 18:51
  • $\begingroup$ $x_{nn} \in [0,1]$ @tsnao. Because $\sum^n_{i=1}x_{ni} = 1$. $\endgroup$ Dec 27, 2022 at 18:56
  • $\begingroup$ @WillJagy yes $x_{ij} \in [0,1]$. You may consider them as mere probabilities. $\endgroup$ Dec 27, 2022 at 18:57
  • 1
    $\begingroup$ @SubhankarGhosal, I see. You probably should not use $n$ as the variable in which you are taking the limit, because it is already used right above in the definition of $A$, thus suggesting that your matrices grow in size with $n$ (it's just that there is a precise sense in which such limits also make sense). $\endgroup$
    – tsnao
    Dec 27, 2022 at 19:22

7 Answers 7

13
$\begingroup$

The answer is quite simple. First observe that $A$ is triangular, hence the spectrum is on the diagonal. From your assumptions, $1$ is a simple eigenvalue and the other eigenvalues belong to $[0,1)$. Decompose $$A=uv^T+B$$ where $u,v$ are the left/right eigenvectors associated with the eigenvalue $1$ ($Au=u$ and $A^Tv=v$, $v^Tu=1$) and $Bu=0$, $B^Tv=0$. Then $$A^N=uv^T+B^N$$ where $B^N\to0_n$ as $N\to+\infty$, because $\rho(B)<1$. Hence $A^N\to uv^T$. Conclude by remarking that $$u=\begin{pmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{pmatrix},\qquad v=\begin{pmatrix} 1 \\ \vdots \\ 1 \end{pmatrix}.$$

$\endgroup$
6
  • $\begingroup$ A typo: should be $v u^\top$ instead of $u v^\top$. This approach is very elegant! $\endgroup$
    – tsnao
    Dec 28, 2022 at 9:40
  • $\begingroup$ @tsnao I think $uv^T$ is correct, because then $Au=(uv^T)u=u(v^Tu)=u$. $\endgroup$ Dec 28, 2022 at 10:19
  • $\begingroup$ yes, you are right! I misread your answer. $\endgroup$
    – tsnao
    Dec 28, 2022 at 10:24
  • $\begingroup$ @DenisSerre what is $\rho(B)$ $\endgroup$ Jan 25, 2023 at 15:31
  • $\begingroup$ @SubhankarGhosal $\rho(M)$ is the standard notation for the spectral radius of the square matrix $M$. It is the maximum of the moduli of its eigenvalues. $\endgroup$ Jan 25, 2023 at 15:50
5
$\begingroup$

This is not a full answer, but observe that with $$ A_0 = \begin{pmatrix} 1 & 0 & \ldots & 0 \\ 0 & 0 & \ldots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \ldots & 0 \end{pmatrix} \quad \text{and} \quad A_1 = \begin{pmatrix} 0 & x_{12} & \ldots & x_{1n} \\ 0 & x_{22} & \ldots & x_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \ldots & x_{nn} \end{pmatrix} $$ we have $$ A = A_0 + A_1. $$

Note next that $A_1 A_0 = 0$, and therefore (using induction) $$ A^k = A_0 + A_0 A_1 + A_0 A_1^2 + \ldots + A_0 A_1^{k - 1} + A_1^k. $$

Since $A_1^k \to 0$, it seems that $$ \lim_{k \to \infty} A^k = A_0 ( I - A_1 )^{-1}. $$

That is, if I didn't make some stupid mistake.


Update. After giving it some thought, I have doubts about $A_1^k \to 0$. It is immediate for $2 \times 2$ matrices, but I am not sure whether it holds for other dimensions. Its diagonal surely does converge to zero, but there still are the off-diagonal entries. Maybe I wrote this a little hastily, probably requires some thinking over.

$\endgroup$
3
  • $\begingroup$ Something is not right: you "prove" the result without any condition on the entries $x_{ij}$; nevertheless, the OP's conjecture is clearly false if $x_{1j} = 0$ for all $j \ge 2$. $\endgroup$
    – Alex M.
    Dec 27, 2022 at 21:30
  • $\begingroup$ @AlexM. : The conclusion in this answer (which is true under the OP conditions -- see my second answer) differs in general from the desired conclusion by the OP. $\endgroup$ Dec 27, 2022 at 21:42
  • $\begingroup$ @AlexM., without some condition on the entries $A_1^k \to 0$ may not be true, so I do use it. Secondly, I am not claiming to have proven the OP's conjecture, but rather seek for a closed expression for the limit. $\endgroup$
    – tsnao
    Dec 27, 2022 at 21:48
4
$\begingroup$

(As is also now seen from your answer) I think in your question you actually wanted to impose the condition $$\sum_{i=1}^j x_{ij} = 1\ \forall j \in \{2,\dots,n\} \tag{1}\label{1} $$ on the column sums of $A$ instead of the condition $$\sum^n_{i=1}x_{ji} = 1\ \forall j \in \{1,2,\dots,n\} \tag{2}\label{2}$$ on the row sums of $A$.

Condition \eqref{2} makes no sense, already because we do not have $x_{j1}$'s for any $j$. If now the row-sum condition \eqref{2} were replaced by the row-sum condition that the matrix $A$ be stochastic, then $A^N$ would be stochastic for all natural $N$ and hence the limit of $A^N$ as $N\to\infty$ (if this limit exists) would also be a stochastic matrix and thus would differ from your conjectured limit if $n\ge2$.

So, let us assume \eqref{1}. Then your desired conclusion will hold.

Indeed, note that $P:=A^\top=:[p_{ij}]$ is a stochastic matrix, which is the transition matrix of a Markov chain with absorbing state $1$.

Since $p_{ii}<1$ for all $i\ge2$ and $p_{ij}=0$ if $j>i$, we see that for each $i\ge2$ there is some $j<i$ such that $p_{ij}>0$. So, for each $i$ there is some natural number $k$ such that $p^{(k)}_{i1}>0$, where $p^{(k)}_{ij}$ is the $ij$-entry of the matrix $P^k$. So, the singleton set $\{1\}$ is the only closed class. Therefore and because the state space $\{1,\dots,n\}$ of the chain is finite, the only absorbing state $1$ is reached from any state in a finite time with probability $1$ -- see e.g. Section 2.11, p. 102. So, for each $i$ we have $p^{(N)}_{i1}\to1$ as $N\to\infty$ (and hence $p^{(N)}_{ij}\to0$ as $N\to\infty$ for each $j\ge2$).

Thus, your desired conclusion follows.

$\endgroup$
3
$\begingroup$

This is to complete the nice answer by tsnao by showing that $A_1^k\to0$ as $k\to\infty$.

To get that conclusion it is enough to assume that the $x_{ij}$'s are any complex numbers such that $$t:=\max_i|x_{ii}|<1. \tag{10}\label{10}$$

Indeed, $$|A_1|\le tI+|B|, \tag{20}\label{20} $$ where $|X|$ is the matrix of the moduli of the entries of a matrix $X$, $I$ is the identity matrix, $B$ is a matrix with zeros on and below the diagonal (so that $|B|^n=0$), and the matrix comparison in \eqref{20} (and in what follows) is entry-wise.

So, for $k>n$, $$|A_1^k|\le|A_1|^k\le(tI+|B|)^k =\sum_{m=0}^k \binom km t^{k-m}|B|^m =\sum_{m=0}^{n-1} \binom km t^{k-m}|B|^m \le n k^{n-1} t^{k-(n-1)}|B|^m\to0$$ by \eqref{10} as $k\to\infty$.


A possibly somewhat simpler way to see that $A_1^k\to0$ as $k\to\infty$ is to note that the eigenvalues of the upper-triangular matrix $A_1$ are the $x_{ii}$'s and $0$, and then use the Jordan form of $A_1$ and \eqref{10}.

$\endgroup$
3
$\begingroup$

Based on the previous answers by tsnao and myself, one gets another, more elementary proof of your desired conclusion (and actually of a more general statement).

Indeed, by those previous answers, $$L:=\lim_{k\to\infty}A^k=A_0(I-A_1 )^{-1},$$ where $$ A_0= \begin{pmatrix} 1 & 0 & \ldots & 0 \\ 0 & 0 & \ldots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \ldots & 0 \end{pmatrix}, $$ so that rows $2,\dots,n$ of the matrix $A_0$ are zero. So, rows $2,\dots,n$ of the matrix $L$ are zero as well. But $A^\top$ is a stochastic matrix. So, $L^\top=\lim_{k\to\infty}(A^\top)^k$ is a stochastic matrix, too, and columns $2,\dots,n$ of the matrix $L$ are zero. Thus, we have your desired conclusion.


Looking again back at the previous answer, we see that, for your desired conclusion to hold, it is actually enough that the $x_{ij}$'s be any complex numbers such that $$\max_i|x_{ii}|<1$$ and $$\sum_{i=1}^j x_{ij} = 1\ \forall j \in \{2,\dots,n\}.$$ In particular, the nonnegativity of the $x_{ij}$'s is not needed.

$\endgroup$
0
$\begingroup$

I have the following observation. Possibly it could help a bit.

Let $\alpha(n) = (1,1,\cdots,1)$.

If $N \geq 1$, $\alpha(n) A^N = \alpha(n)\times A \times A^{N-1}=\alpha(n)\times A^{N-1}=\cdots= \alpha(n).$

$\endgroup$
1
  • 2
    $\begingroup$ This just means that the matrix $A^\top$ is stochastic (which is condition (1) in my answer at mathoverflow.net/a/437364/36721 ), and then of course $(A^N)^\top=(A^\top)^N$ is stochastic for each natural $N$. $\endgroup$ Dec 28, 2022 at 4:17
0
$\begingroup$

Another approach of this problem would be like this. If $A$ and $B$ be two commuting matrices such that $\sum_{i} A_{ij}=1$ and $\sum_{i} B_{ij}=1$ then $\sum_{i} (AB)_{ij}=\sum_{i,k} A_{ik}B_{kj}=\sum_{k} (\sum_{i} A_{ik})B_{kj}=1$. So, the column sum is preserved for all $A^{n}$ (the upper triangular matrix in question).

Now, we can break the matrix as

$A = \begin{pmatrix} 1 & X\\ 0 & B\\ \end{pmatrix}$. Where $X=(x_{12},x_{13},...,x_{1n})$ and $B$ is the leftover $(n-1)\times(n-1)$ matrix.

We will show $\lim\limits_{n \to \infty} B^n=0$. Then the 'column sum preserving property' implies that all entries in the first row of $A^n$ tend to $1$.

We have, $\sum_{i} B_{ij}=\alpha_j\leq 1$ as $x_{1j} \geq 0 ,j>1$ (with at least one of $x_{ij}$ being non-zero) . Now, say sum of $j$-th column of $B^{l}, l>1$ is $\beta^{(l)}_j$. So, $\beta^{(l+1)}_j=\sum_{i,k} B_{ik}B^{(l)}_{kj}=\sum_{k}\alpha_{k} B^{(l)}_{kj}$.

As, $\alpha_{k} \leq 1$ (at least one of them is strictly less than 1) ,$\beta^{(l+1)}_j<\sum_{k}B^{(l)}_{kj}=\beta^{(l)}_j$. Now, $\beta^{(l)}_j-\beta^{(l+1)}_j=\sum_{k} \Delta_kB^{(l)}_{kj} ; \Delta_k=1-\alpha_k\geq 0$ (at least one being non-zero) $;B^{(l)}_{kj}>0$.

This directly implies that $B^{(l)}_{kj} \to 0$ as $l \to \infty$ and so, $B^n \to 0$ as $n \to 0$, which completes the proof.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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