38. The Perron-Frobenius Theorem

In addition to what’s in Anaconda, this lecture will need the following libraries:

In this lecture we will begin with the foundational concepts in spectral theory.

Then we will explore the Perron-Frobenius theorem and connect it to applications in Markov chains and networks.

We will use the following imports:

38.1Nonnegative matrices¶

Often, in economics, the matrix that we are dealing with is nonnegative.

Nonnegative matrices have several special and useful properties.

In this section we will discuss some of them --- in particular, the connection between nonnegativity and eigenvalues.

An $n \times m$ matrix $A$ is called nonnegative if every element of $A$ is nonnegative, i.e., $a_{ij} \geq 0$ for every $i,j$.

We denote this as $A \geq 0$.

38.1.1Irreducible matrices¶

We introduced irreducible matrices in the Markov chain lecture.

Here we generalize this concept:

Let $a^{k}_{ij}$ be element $(i,j)$ of $A^k$.

An $n \times n$ nonnegative matrix $A$ is called irreducible if $A + A^2 + A^3 + \cdots \gg 0$, where $\gg 0$ indicates that every element in $A$ is strictly positive.

In other words, for each $i,j$ with $1 \leq i, j \leq n$, there exists a $k \geq 0$ such that $a^{k}_{ij} > 0$.

38.1.2Left eigenvectors¶

Recall that we previously discussed eigenvectors in Eigenvalues and Eigenvectors.

In particular, λ is an eigenvalue of $A$ and $v$ is an eigenvector of $A$ if $v$ is nonzero and satisfy

In this section we introduce left eigenvectors.

To avoid confusion, what we previously referred to as “eigenvectors” will be called “right eigenvectors”.

Left eigenvectors will play important roles in what follows, including that of stochastic steady states for dynamic models under a Markov assumption.

A vector $w$ is called a left eigenvector of $A$ if $w$ is a right eigenvector of $A^\top$.

In other words, if $w$ is a left eigenvector of matrix $A$, then $A^\top w = \lambda w$, where λ is the eigenvalue associated with the left eigenvector $v$.

This hints at how to compute left eigenvectors

We can also use scipy.linalg.eig with argument left=True to find left eigenvectors directly

The eigenvalues are the same while the eigenvectors themselves are different.

(Also note that we are taking the nonnegative value of the eigenvector of dominant eigenvalue, this is because eig automatically normalizes the eigenvectors.)

We can then take transpose to obtain $A^\top w = \lambda w$ and obtain $w^\top A= \lambda w^\top$.

This is a more common expression and where the name left eigenvectors originates.

38.1.3The Perron-Frobenius theorem¶

For a square nonnegative matrix $A$, the behavior of $A^k$ as $k \to \infty$ is controlled by the eigenvalue with the largest absolute value, often called the dominant eigenvalue.

For any such matrix $A$, the Perron-Frobenius theorem characterizes certain properties of the dominant eigenvalue and its corresponding eigenvector.

(This is a relatively simple version of the theorem --- for more details see here).

We will see applications of the theorem below.

Let’s build our intuition for the theorem using a simple example we have seen before.

Now let’s consider examples for each case.

38.1.3.1Example: irreducible matrix¶

Consider the following irreducible matrix $A$:

We can compute the dominant eigenvalue and the corresponding eigenvector

Now we can see the claims of the Perron-Frobenius theorem holds for the irreducible matrix $A$:

1. The dominant eigenvalue is real-valued and non-negative.
2. All other eigenvalues have absolute values less than or equal to the dominant eigenvalue.
3. A non-negative and nonzero eigenvector is associated with the dominant eigenvalue.
4. As the matrix is irreducible, the eigenvector associated with the dominant eigenvalue is strictly positive.
5. There exists no other positive eigenvector associated with the dominant eigenvalue.

38.1.4Primitive matrices¶

We know that in real world situations it’s hard for a matrix to be everywhere positive (although they have nice properties).

The primitive matrices, however, can still give us helpful properties with looser definitions.

Let $A$ be a square nonnegative matrix and let $A^k$ be the $k^{th}$ power of $A$.

A matrix is called primitive if there exists a $k \in \mathbb{N}$ such that $A^k$ is everywhere positive.

We can see that if a matrix is primitive, then it implies the matrix is irreducible but not vice versa.

Now let’s step back to the primitive matrices part of the Perron-Frobenius theorem

38.1.4.1Example 1: primitive matrix¶

Consider the following primitive matrix $B$:

We compute the dominant eigenvalue and the corresponding eigenvector

Now let’s give some examples to see if the claims of the Perron-Frobenius theorem hold for the primitive matrix $B$:

1. The dominant eigenvalue is real-valued and non-negative.
2. All other eigenvalues have absolute values strictly less than the dominant eigenvalue.
3. A non-negative and nonzero eigenvector is associated with the dominant eigenvalue.
4. The eigenvector associated with the dominant eigenvalue is strictly positive.
5. There exists no other positive eigenvector associated with the dominant eigenvalue.
6. The inequality $|\lambda| < r(B)$ holds for all eigenvalues λ of $B$ distinct from the dominant eigenvalue.

Furthermore, we can verify the convergence property (7) of the theorem on the following examples:

The convergence is not observed in cases of non-primitive matrices.

Let’s go through an example

The result shows that the matrix is not primitive as it is not everywhere positive.

These examples show how the Perron-Frobenius theorem relates to the eigenvalues and eigenvectors of positive matrices and the convergence of the power of matrices.

In fact we have already seen the theorem in action before in the Markov chain lecture.

38.1.4.2Example 2: connection to Markov chains¶

We are now prepared to bridge the languages spoken in the two lectures.

A primitive matrix is both irreducible and aperiodic.

So Perron-Frobenius theorem explains why both Imam and Temple matrix and Hamilton matrix converge to a stationary distribution, which is the Perron projection of the two matrices

We can also verify other properties hinted by Perron-Frobenius in these stochastic matrices.

Another example is the relationship between convergence gap and convergence rate.

In the exercise, we stated that the convergence rate is determined by the spectral gap, the difference between the largest and the second largest eigenvalue.

This can be proven using what we have learned here.

Please note that we use $\mathbb{1}$ for a vector of ones in this lecture.

With Markov model $M$ with state space $S$ and transition matrix $P$, we can write $P^t$ as

This is proven in Sargent & Stachurski (2023) and a nice discussion can be found here.

In this formula $\lambda_i$ is an eigenvalue of $P$ with corresponding right and left eigenvectors $v_i$ and $w_i$ .

Premultiplying $P^t$ by arbitrary $\psi \in \mathscr{D}(S)$ and rearranging now gives

Recall that eigenvalues are ordered from smallest to largest from $i = 1 ... n$.

As we have seen, the largest eigenvalue for a primitive stochastic matrix is one.

This can be proven using Gershgorin Circle Theorem, but it is out of the scope of this lecture.

So by the statement (6) of Perron-Frobenius theorem, $\lambda_i<1$ for all $i<n$, and $\lambda_n=1$ when $P$ is primitive.

Hence, after taking the Euclidean norm deviation, we obtain

Thus, the rate of convergence is governed by the modulus of the second largest eigenvalue.

38.2Exercises¶

A = np.array([[0.3, 0.2, 0.3],
              [0.2, 0.4, 0.3],
              [0.2, 0.5, 0.1]])

evals, evecs = eig(A)

r = max(abs(λ) for λ in evals)   #dominant eigenvalue/spectral radius
print(r)

0.8444086477164554

I = np.identity(3)
B = I - A

d = np.array([4, 5, 12])
d.shape = (3,1)

B_inv = np.linalg.inv(B)
x_star = B_inv @ d
print(x_star)

[[38.30189]
 [44.33962]
 [46.47799]]