# One observation of special type of square matrix exponentiation

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.

• are the $x_{ij} \geq 0 \; ? \;$ Dec 27, 2022 at 18:48
• Am I right that it follows from your description that $x_{nn} = 1$? Wouldn't it remain the same for all powers? Dec 27, 2022 at 18:51
• $x_{nn} \in [0,1]$ @tsnao. Because $\sum^n_{i=1}x_{ni} = 1$. Dec 27, 2022 at 18:56
• @WillJagy yes $x_{ij} \in [0,1]$. You may consider them as mere probabilities. Dec 27, 2022 at 18:57
• @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). Dec 27, 2022 at 19:22

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}.$$

• A typo: should be $v u^\top$ instead of $u v^\top$. This approach is very elegant! Dec 28, 2022 at 9:40
• @tsnao I think $uv^T$ is correct, because then $Au=(uv^T)u=u(v^Tu)=u$. Dec 28, 2022 at 10:19
• @DenisSerre what is $\rho(B)$ Jan 25, 2023 at 15:31
• @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. Jan 25, 2023 at 15:50

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.

• 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$. Dec 27, 2022 at 21:30
• @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. Dec 27, 2022 at 21:42
• @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. Dec 27, 2022 at 21:48

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

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

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.

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

• 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$. Dec 28, 2022 at 4:17

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.