Raising a matrix to the infinite power

Question

How do I raise a matrix to the infinite power? I know that the main method for doing this is by diagonalizing the matrix, but what if I can't?

For example, let's say I have the matrix

\begin{bmatrix}0&0&0&0&0\\2/3&0&0&0&0\\1/3&0&1&0&0\\0&3/7&0&1&0\\0&4/7&0&0&1\end{bmatrix}

You can see that when I try diaganolizing the matrix in Mathematica, the eigenvector matrix is singular, so I'm unable to take its inverse.

---

---

However, I know that when I raise this matrix to the power of infinity, I know I get the following matrix

\begin{bmatrix}0&0&0&0&0\\0&0&0&0&0\\1/3&0&1&0&0\\2/7&3/7&0&1&0\\8/21&4/7&0&0&1\end{bmatrix}

Is there any general algorithm or formula or steps I can take to get there?

Answer 1

This depends on the spectral radius $\rho(M)$ of your matrix $M$.

• If $\rho(M)<1$, then $\lim_{k\to \infty} M^k=0$.
• If $\rho(M)>1$, then $\lim_{k\to \infty} \|M^k\|=\infty$ so the limit does not exists.
• If $\rho(M)=1$, then the limit may or may not converge.

Answer 2

$ \def\idx{{\rm index}(A)} $For a Markov/stochastic matrix $M\in{\mathbb R}^{n\times n}$, you could calculate the limit in terms of the Drazin inverse.

First, define the auxiliary matrix $$A = I-M$$ Then, the limit is $$\lim_{\ell\to\infty}M^\ell = \big(I-AA^D\big)$$ For a small matrix like yours, the Drazin inverse can be readily calculated in terms of the pseudoinverse of an appropriate power of $A$ $$A^D = A^k\Big(A^{2k+1}\Big)^+A^k,\qquad k\ge\idx$$ Since $\,(0\le\idx\le n),\,$ if you are unable to calculate $\idx$, just use $k=n$.

Answer 3

Being lower triangular, the characteristic polynomial of the matrix, call it $M$, is easy to calculate: $p(z)=\det(M-zI) = z^2(z-1)^3$. The Hamilton-Cayley theorem stipulates that $M$ is a root of $p$, i.e. $$p(M)= M^2(M-I)^3=0.$$ The minimal polynomial for $M$ is the polynomial $q$ of smallest degree so that $q(M)=0$. You may find it by trial and error looking for the smallest powers (instead of 2 and 3) for which you get the zero matrix. Trying out you find here $M^2(M-I)=0$ or equivalently $M^3=M^2$ which implies that $M^n=M^2$ for all $n\geq 2$.

This solves the problem for the given matrix. In the general case, it works as follows: Calculate the characteristic polynomial, and by trial and error the minimal polynomial (as above). Then $M^n$ to converge to a non-zero matrix iff $1$ is a simple root of the minimal polynomial and all other roots (simple or not) are strictly smaller than one in absolute values. So if for example $M^2(M-I)^2=0$ had been the minimal polynomial then $M^n$ would not converge (which may be interpreted as the presence of a non-trivial Jordan block associated to the eigenvalue 1).

Answer 4

Introduction

In this answer, we cover

• How to solve the OP's question using a clever $D,N$-decomposition.

• Using the Jordan canonical form to take infinite powers of matrices (and when can an infinite power be taken?)

• Infinite powers of stochastic matrices.

• Infinite powers of matrices using the concept of generalized inverses.

• An introduction to interval matrices and a brief idea of why studying infinite powers for such matrices can help capture infinite powers for large classes of matrices.

An ad-hoc observation

Your matrix is of the form $D+N$ where $D$ is a diagonal matrix with entries $[0,0,1,1,1]$, and $$ N = \begin{pmatrix} 0&0&0&0&0\\ \frac 23 &0&0&0&0\\ \frac 13&0&0&0&0\\ 0&\frac 37&0&0&0\\ 0&\frac 47&0&0&0 \end{pmatrix} $$

In particular, observe that $ND = 0$ (note : $DN \neq 0$) and $N^3=0$ (Note : $N^2\neq 0$). One can explicitly compute the non-zero matrices $DN$ and $N^2$ for reference.

Therefore , imagine that we are computing $(D+N)^k$. For simplicity, take $k=2$. We get the terms $D^2+DN+ND+N^2$ which simplifies to $D^2+DN+N^2$.

Now let's take $k=3$. We get $$ D^3+D^2N+DND+DN^2+ND^2+NDN+N^2D+N^3 $$ Every term containing either an $ND$ or $N^3$ will vanish. This leaves exactly $$ D^3+D^2N+DN^2 $$

Are you seeing a pattern?

---

Generalizing the pattern $+$ completing the problem

Indeed, which terms of the summation will survive from $(D+N)^k$? For starters, you can't have a $D$ following an $N$ because $ND = 0$. Therefore, the only terms that will survive must have a run of $D$s followed by a run of $N$s i.e. it must be of the form $D^{l}N^{k-l}$.

However, because $N^3 = 0$ we know that $k-l \leq 2$! That leaves us with $$ D^{k-2}N^2+D^{k-1}N + D^k $$

However, here's the interesting part : $D$ is diagonal with entries $[0,0,1,1,1]$, and therefore $D^k$ (for any $k$) is diagonal with entries $[0^k,0^k,1^k,1^k,1^k]$ : which is just equal to $D$!

Finally, we get for ANY $k$ that $$ (D+N)^k = D(N^2+N+I) $$

and therefore, rather obviously, $$ \lim_{k \to \infty} (D+N)^k = D(N^2+N+I) $$

as desired. Compute this quantity for your $D$ and $N$ to see what you get.

---

Jordan canonical form and N&S condition for power convergence

We did not use a standard method to solve this question. Indeed, what we did was relatively ad-hoc : breaking the matrix into two parts that are easy to exponentiate and whose commutative properties are nice.

There does exist a standard method of infinite exponentiation : the Jordan Canonical form.

Indeed, according to the Jordan normal form, for any matrix $M$ with possibly complex entries you can write $$ M = P^{-1}(D+N)P $$ where

• $D$ is a diagonal matrix with complex entries, whose entries are the eigenvalues of $M$ listed with their algebraic multiplicity.

• $N$ is a nilpotent matrix i.e. $N^m = 0$ where $M$ is an $m \times m$ matrix. Furthermore, $N$ has only the entries $0$ and $1$.

• $DN = ND$.

• $P$ is an invertible matrix with complex entries.

Note that the $D,N$ we used were diagonalizable and nilpotent respectively, but they didn't come from the Jordan decomposition since $DN \neq ND$.

Once this is done, then you can use the binomial theorem to see that $$ M^k = P^{-1} \left(\sum_{i=0}^m \binom{k}{i} N^{i}D^{k-i} \right)P $$

whence (by the continuity of matrix multiplication and sum-of-limits rule) $$ \lim_{k \to \infty} P^{-1} \left(\sum_{i=0}^m \binom{k}{i} N^{i}D^{k-i} \right)P = P^{-1} \left(\sum_{i=0}^m \lim_{k \to \infty}\left(\binom{k}{i}N^iD^{k-i}\right) \right)P $$

where the limit $\lim_{k \to \infty} \binom{k}{i}N^iD^{k-i}$ is to be treated as a pointwise limit of matrices.

However, this limit is quite easy to study in most cases (because $D$ is diagonal and $\binom{k}{i}$ is a polynomial in $k$ so we pretty much have something like $p(k)a^k$ for a complex number $a$, if the effect of $N^i$ is treated "like a constant"), and one easily sees that if every entry of $D$ is less than $1$ in modulus, convergence to the $0$ matrix occurs for this limit, and consequently for $M^k$. If even one entry of $D$ is greater than $1$ in modulus, then convergence fails for this limit, and consequently for $M^k$.

However, if entries of $D$ are of modulus exactly $1$, then subtleties appear based on how $N$ and $D$ interact. For example, even if $N = 0$ then $M^k = P^{-1}D^kP$ can converge for $D=I$ and diverge for other $D$. This is, nevertheless, a good way to get the pointwise limit of matrices.

For a detailed expression of the power of a matrix using the Jordan form, see [4].

Using the Jordan canonical form, one can assert limit existence using the following theorem[6] :

For a matrix $A$, $\lim_{k \to \infty} A^k$ exists if and only if for every eigenvalue $\lambda$ of $A$,

• Either $|\lambda|<1$, or
• $\lambda=1$, and $\lambda$ is regular (i.e. the algebraic and geometric multiplicities of $\lambda$ as an eigenvalue of $A$ coincide) and dominant (i.e. every other eigenvalue $\mu \neq \lambda$ satisfies $|\mu|<1$).

This would be reflected in the "Jordan" matrix $D+N$ as follows : every diagonal entry is either of modulus smaller than $1$, or has $1$, where the corresponding entry above the $1$ is equal to $0$.

---

Stochastic matrices and matrices with positive entries

A large class of matrices where a limit can be asserted and found under some conditions, is the class of matrices with strictly positive entries (all entries $>0$). Here, we have a theorem of Perron and Frobenius to assist us.

Theorem[7] : Let $A$ be a matrix with strictly positive entries. Then, there exists a positive real number $r>0$ with the following property : $r$ is a eigenvalue of $A$ of multiplicity $1$, and every other eigenvalue is smaller than $r$ in modulus. Furthermore, the eigenvector corresponding to $r$ has strictly positive entries.

This can be used to prove a very famous limit theorem for certain kinds of matrices[6].

Let $A$ be a stochastic irreducible aperiodic matrix i.e. $A$ is a matrix with the following two properties given below. Then $1$ is always an eigenvalue of $A$ and $\lim_{k \to \infty} A^k$ exists and equals the matrix $xy^T$, where $x,y$ are the unique right and left (both column vectors) eigenvectors with positive entries summing to $1$.

• $A$ has non-negative entries and every row of $A$ sums to $1$. (stochastic)
• There exist two positive co-prime integers $k,l$ such that $A^k,A^l$ have strictly positive entries (irreducible aperiodic).

This remarkable result is used in the analysis of finite-time Markov chains, whose transition matrices often have the suggested property.

---

The relation with generalized inverses

Generalized inverses are quite an interesting concept because they can exist even if a matrix is not invertible. See [2] for details.

Definition : A matrix $A$ is said to have a generalized inverse if and only if there exists a matrix $X$ such that $$ A= AXA \quad ; \quad X = XAX\quad ; \quad AX = XA $$ all hold. $X = A^{\#}$ is unique if these are satisfied and is called the generalized inverse of $A$.

It is a linear-algebraic problem to find $A^{\#}$. Note that if $A$ is invertible then $A^{\#}$ exists and equals $A^{-1}$. The existence of $A^{\#}$ for general $A$ is given by the following theorem :

The following are equivalent for a square matrix $A$ :

• $A$ has a generalized inverse.
• $\mbox{rank}(A^2) = \mbox{rank}(A)$.
• The range and null space of $A$ are complementary to each other.

Once $A$ has a generalized inverse, we can use the following theorem :

$\lim_{k \to \infty} A^k$ exists if and only if every eigenvalue that is not equal to $1$ has modulus smaller than $1$, and $I-A$ admits a generalized inverse. Furthermore, $$ \lim_{k \to \infty} A^k = I - (I-A)(I-A)^{\#} $$

One more very interesting theorem will give equivalent conditions for a particular kind of matrix to have a limit.

Let $B$ be a matrix with non-negative entries of the form $B = I-A$ where $A$ has the property that $a_{ij} \leq 0$ for $i \neq j$ (non-positive diagonal entries). The following are equivalent , and if any one of them holds then $\lim_{k \to \infty} B^k = I-AA^{\#}$.

• $\lim_{k \to \infty} B^k$ exists.
• $0$,if it is an eigenvalue of $A$, is a regular eigenvalue of $A$, and every eigenvalue of $A$ has positive real part.
• $0$,if it is an eigenvalue of $A$, is a regular eigenvalue of $A$, and all principal minors$^*$ of $A$ are non-negative.
• $A^{\#}$ exists, and for every $x \in \mbox{Ran}(A)$ with non-negative entries, $A^{\#}x$ also has non-negative entries.
• For every $x \in \mbox{Ran}(A)$, if $Ax$ has non-negative entries, then $x$ also has non-negative entries.

($^*$) A principal minor of a matrix is defined here.

For more details on such matrices and their powers , see [3].

---

Interval matrices

A very interesting concept is one of interval matrices. These are matrices whose entries are not real numbers, but actually real intervals. These are used to prove results for matrices whose entries lie within the depicted intervals. For example, $$ \begin{pmatrix} 2 & 3\\ 4 & 5 \end{pmatrix} \in \begin{pmatrix} [-1,3] & \{3\}\\ [2,5] & [1.5,7.65] \end{pmatrix} $$ where $\in$ doesn't mean "belongs to", but rather means "is covered in" , so that a result for that particular interval matrix would hold for the real matrix as well. We'll use $[\cdot]$ to indicate an interval matrix.

We can multiply interval matrices using the usual rule for matrices, along with simple interval arithmetic, which yields $[a,b] * [c,d] = \{xy : x \in [a,b], y \in [c,d]\}$ and $[a,b]+[c,d] = [a+c,b+d]$. However, note that interval multiplication is not associative, so we need to be careful in defining matrix powers. Usually, it's multiplication from the right, so that $[X]^1 = [X]$ and $[X]^{n+1} = [X^n]X$.

It turns out that there are results which can prove the convergence of powers for these interval matrices as well , thereby proving the convergence of powers for many matrices at once. Some of these are discussed in [1].

It is difficult to mention the criteria, but they are very powerful and hold applications in the computerized checking of the stability of solutions of linear differential equations with periodic coefficients (which typically lie in some compact interval, hence the need for interval analysis).

---

References

[1] Arndt, Hans-Robert; Mayer, Günter, New criteria for the semiconvergence of interval matrices, SIAM J. Matrix Anal. Appl. 27, No. 3, 689-711 (2005). ZBL1129.65029.

[2] Plemmons, R. J., M-matrices leading to semiconvergent splittings, Linear Algebra Appl. 15, 243-252 (1976). ZBL0358.15016.

[3] Meyer, Carl D. jun.; Plemmons, R. J., Convergent powers of a matrix with applications to iterative methods for singular linear systems, SIAM J. Numer. Anal. 14, 699-705 (1977). ZBL0366.65017.

[4] Power of a matrix, given its Jordan form

[5] Limiting Distribution of a Markov Chain

[6] Powers of Matrices

[7] Perron-Frobenius Theorem