2 Operators and Fixed Points

This chapter discusses techniques that underlie the optimization and fixed-point methods used throughout the book. Many of these techniques relate to order. Order-theoretic concepts will prove valuable not only for fixed-point methods but also for understanding the main concepts in dynamic programming. Chapter 8 will show core components of dynamic programming can be expressed in terms of simple order-theoretic constructs.

2.1Stability¶

In this section, we discuss algorithms for computing fixed points and analyze their convergence.

2.1.1Conjugate Maps¶

First we treat a technique for simplifying analysis of stability and fixed points that we’ll apply in applications.

To illustrate the idea, suppose that we want to study dynamics induced by a self-map $T$ on $U \subset \RR^n$. We might want to know if a unique fixed point of $T$ exists and if iterates of $T$ converge to a fixed point. One approach is to apply fixed-point theory to $T$.

However, sometimes there is an easier approach: Transform $T$ into a “simpler” map $\hat T$ and study its the fixed-point properties. For this to work, we need to be sure that useful properties we discover about $\hat T$ will transmit themselves back to properties of $T$, the map that actually interests us.

This section explains a notion of conjugacy that formalizes these ideas. The study of conjugate relationships originated in the field of dynamical systems theory. Later we will apply this approach to operators that arise in contexts of dynamic programming and recursive preferences.

2.1.1.1Conjugacy¶

A dynamical system is a pair $(U, T)$, where $U$ is any set and $T$ is a self-map on $U$. Two dynamical systems $(U, T)$ and $(\hat U, \hat T)$ are said to be conjugate under $\Phi$ if $\Phi$ is a bijection from $U$ into $\hat U$ such that $T = \Phi^{-1} \circ \hat T \circ \Phi$ on $U$.

Conjugacy of $(U, T)$ and $(\hat U, \hat T)$ under $\Phi$ can be understood as follows: Shifting a point $u \in U$ to $T u$ via $T$ is equivalent to moving $u$ into $\hat U$ via $\hat u = \Phi u$, applying $\hat T$, and then moving the result back using $\Phi^{-1}$:

The next two exercises illustrate benefits of establishing a conjugate relationship between two dynamical systems.

The next result summarizes the most important consequences of our findings.

In particular, if $T$ has a unique fixed point on $U$ if and only if $\hat T$ has a unique fixed point on $\hat U$.

2.1.1.2Topological Conjugacy¶

Let $U$ and $\hat U$ be two subsets of $\RR^n$. A function $\Phi$ from $U$ to $\hat U$ is called a homeomorphism if it is continuous, bijective, and its inverse $\Phi^{-1}$ is also continuous.

Assume again that $U$ and $\hat U$ are subsets of $\RR^n$. In this setting, we say that dynamical systems $(U, T)$ and $(\hat U, \hat T)$ are topologically conjugate under $\Phi$ if $(U, T)$ and $(\hat U, \hat T)$ are conjugate under $\Phi$ and, in addition, $\Phi$ is a homeomorphism.

The next exercise asks you to show that topologically conjugacy is an equivalence relation, as defined in Section A.1.

From the preceding exercises we can state the following useful result:

2.1.2Local Stability¶

In Section 1.2.2.2 we investigated global stability. Here we introduce local stability and provide a sufficient condition for situations in which the map is smooth.

Let $U$ be a subset of $\RR^n$ and let $T$ be a self-map on $U$. A fixed point $u^*$ of $T$ in $U$ is called locally stable for the dynamical system $(U, T)$ if there exists an open set $O \subset U$ such that $u^* \in O$ and $T^k u \to u^*$ as $k \to \infty$ for every $u \in O$. In other words, the domain of attraction for $u^*$ contains an open neighborhood of $u^*$.

For an interior fixed point $x^*$ of a smooth self-map $g$ on an interval of $\RR$, local stability holds whenever $|g'(x^*)| < 1$. The proof strategy proceeds as follows: When $|g'(x^*)| < 1$, the first-order linear approximation

is a contraction of modulus $|g'(x^*)|$ with unique fixed point $x^*$. Hence all trajectories of $\hat g$ converge to $x^*$. Moreover, since $g$ and $\hat g$ are similar in a neighborhood of $x^*$, the same is true for trajectories of $g$ starting close to $x^*$.

The next theorem formalizes this line of argument and extends it to multiple dimensions. In stating the theorem, we take $T$ to be a self-map on $U$ with fixed point $u^*$ in $U$ and assume that $T$ is continuously differentiable on $U$. Recall that the Jacobian of $T$ at $u \in U$ is

and let $\hat T$ be the first-order approximation to $T$ at $u^*$:

Combining this theorem with the result of Exercise 2.6, we see that, under the conditions of the theorem, $u^*$ is globally stable for $(O, T)$, and hence locally stable for $(U, T)$, whenever $(O, \hat T)$ is globally stable. By the Neumann series lemma, the first-order approximation will be globally stable whenever $J_T(u^*)$ has spectral radius less than one. Thus, we have

2.1.3Convergence Rates¶

To discuss relative rates of convergence we fix a norm $\| \cdot \|$ on $\RR^n$ and take a sequence $(u_k)_{k \geq 0} \subset \RR^n$ converging to $u^* \in \RR^n$. Set $e_k \coloneq \| u_k - u^* \|$ for all $k$. We say that $(u_k)$ converges to $u^*$ at rate at least $q$ if $q \geq 1$ and, for some $\beta \in (0, \infty)$ and $N \in \NN$, we have

We say that convergence occurs at rate $q$ if, in addition,

In addition,

• If $q=2$, then we say that convergence is (at least) quadratic.

• If $q=1$ and $\beta < 1$, then we say that convergence is (at least) linear.

Orders of convergence are studied in the neighborhood of zero, implying that higher orders are faster. For example, suppose $\epsilon_k \coloneq \| u_k - u^* \|$ is the size of the error and that $u_k$ converges to $u^*$ quadratically. If, say, $\epsilon_k = 10^{-5}$, then $\epsilon_{k+1} \approx \beta 10^{-10}$. Provided that $\beta$ is not large, the number of accurate digits roughly doubles at each step.

Successive approximations typically converge at a linear rate. To see this in one dimension, try the following exercise.

(The restriction that $0 < |T' u^*| < 1$ in Exercise 2.7 is mild. For example, given convergence of successive approximation to the fixed point, we expect $|T' u^*| < 1$, since this inequality implies that $u^*$ is locally stable.)

2.1.4Gradient-Based Methods¶

While successive approximation always converges when global stability holds, faster fixed-point algorithms can often be obtained by leveraging extra information, such as gradients. Newton’s method is an important gradient-based technique. (As we discuss in Section 5.1.4.2, Newton’s method is a key component of algorithms for solving dynamic programs.)

While Newton’s method is often used to solve for roots of a given function, here we use it to find fixed points.

2.1.4.1Newton Fixed-Point Iteration¶

Suppose first that $T$ is a differentiable self-map on an open set $U \subset \RR^n$ and that we want to find a fixed point of $T$. Our plan is to start with a guess $u_0$ of the fixed point and then update it to $u_1$. To do this we use the first-order approximation $\hat T$ of $T$ around $u_0$ and solve for the fixed point of $\hat T$ -- which we can do exactly since $\hat T$ is linear. We take this new point as $u_1$ and then continue.

If $T$ is one-dimensional then $\hat T u \coloneq T u_0 + T' u_0 (u - u_0)$. For $n > 1$ we replace $T' u_0$ with the Jacobian of $T$ at $u_0$, which we write as $J_T(u_0)$. We then solve $\hat T u_1 = u_1$ for $u_1$, which gives

Figure Figure 2.2 shows $u_0$ and $u_1$ when $n=1$ and $Tu = 1 + u/(u + 1)$ and $u_0 = 0.5$. The value $u_1$ is the fixed point of the first-order approximation $\hat T$. It is closer to the fixed point of $T$ than $u_0$, as desired.

Newton’s (fixed-point) method continues in the same way, from $u_1$ to $u_2$ and so on, leading to the sequence of points

We need not write a new solver, since the successive approximation function in Listing 4 can be applied to $Q$ defined in (2.13).

2.1.4.2Rates of Convergence¶

Figure Figure 2.3 shows both the Newton approximation sequence and the successive approximation sequence applied to computing the fixed point of the Solow--Swan model from Section 1.2.3.2. We use two different initial conditions (top and bottom subfigures). Both sequences converge, but the Newton sequences converge faster.

A fast rate of convergence for Newton scheme can be confirmed theoretically: Under mild conditions, there exists a neighborhood of the fixed point within which the Newton iterates converge quadratically. See, for example, Theorem 5.4.1 of Atkinson & Han (2005). Some dynamic programming algorithms take advantage of this fast rate of convergence (see Section 5.1.4.3).

2.1.4.3Speed versus Robustness¶

Sometimes we can accelerate computations by exploiting a problem’s special structure (e.g., differentiability, convexity, monotonicity). But we often face a trade-off between speed and robustness to details of problem specification. More robust methods impose less structure.

Relative to other algorithms, successive approximation tends to be robust but slow. We saw one illustration of the relatively slow rate of convergence in Figure Figure 2.3. But we can also see its relatively strong robustness properties via the same example, by inspecting Figure Figure 2.4, which compares the update rule of successive approximation (the function $g$) with the update rule for Newton’s method (the function $Q$ in (2.13)). Also plotted is the dashed 45 degree line.

The parameterization is the same as for the top subfigure in Figure Figure 1.7. As previously discussed, the shape of $g$ implies global convergence of successive approximation. However, $Q$ is well-behaved near the fixed point (i.e., very flat and hence strongly contractive) but poorly behaved away from the fixed point. This illustrates that Newton’s method is fast but generally less robust.

2.1.4.4Parallelization¶

We have discussed rates of convergence for fixed-point methods. Mathematicians and computer scientists also analyze algorithms via worst-case complexity, which measures the number of fundamental operations (e.g., addition and multiplication of floating point numbers) when an algorithm acts on data that is least favorable for good performance. These measures are attractive because they are independent of the software and hardware platforms on which algorithms are implemented.

Software and hardware matter not just for absolute performance of algorithms but also for relative performance. For example, although a single update step in successive approximation can often be partially parallelized, the algorithm is inherently serial, in the sense that the $(k+1)$-th iterate cannot be computed until iterate $k$ is available. Moreover, because the rate of convergence is typically slow (i.e., linear), there can be many small serial steps. This limits parallelization.

Newton’s method is also serial to some degree, since we are just iterating with a different map (the operator $Q$ in (2.13)). However, because it involves inverting matrices of possibly high dimension, each step is computationally intensive. At the same time, since the rate of convergence is faster, we have to take fewer steps. In this sense, the algorithm is less serial -- it involves a smaller number of more expensive steps. Because it is less serial, Newton’s method offers far more potential for parallelization. Thus, the speed gain associated with Newton’s method can become very large when using effective parallelization.

2.2Order¶

This section reviews key concepts from order theory.

2.2.1Partial Orders¶

We define partial orders and examine some of their basic properties.

2.2.1.1Partially Ordered Sets¶

A partial order on a nonempty set $P$ is a relation $\preceq$ on $P \times P$ that, for any $p, q, r$ in $P$, satisfies

2

1. $p \preceq p$

2. $p \preceq q$ and $q \preceq p$ implies $p = q$ and

3. $p \preceq q$ and $q \preceq r$ implies $p \preceq r$

4. (reflexivity),

5. (antisymmetry), and

6. (transitivity).

The pair $(P, \preceq)$ is called a partially ordered set. For convenience, we sometimes write $P$ for $(P, \preceq)$ and $q \succeq p$ for $p \preceq q$. The statement $p \preceq q \preceq r$ means $p \preceq q$ and $q \preceq r$.

In what follows, for $u, v \in \RR^\Xsf$, we write $u \ll v$ if $u(x) < v(x)$ for all $x \in \Xsf$.

The preceding pointwise concepts extend immediately to vectors, since vectors are just real-valued functions under the identification asserted in Lemma 1.2.4. In particular, for vectors $u = (u_1, \ldots, u_n)$ and $v = (v_1, \ldots, v_n)$ in $\RR^n$, we write

• $u \leq v$ if $u_i \leq v_i$ for all $i \in \natset{n}$ and

• $u \ll v$ if $u_i < v_i$ for all $i \in \natset{n}$.

Statements $u \geq v$ and $u \gg v$ are defined analogously. Figure Figure 2.5 illustrates. Naturally, $\leq$ is called the pointwise order on $\RR^n$.

A partial order $\preceq$ on $P$ is called total if, for all $p, q \in P$, either $p \preceq q$ or $q \preceq p$.

2.2.1.2Least and Greatest Elements¶

Given a partially ordered set $(P, \preceq)$ and $A \subset P$, we say that $g \in P$ is a greatest element of $A$ if $g \in A$ and, in addition, $a \in A \implies a \preceq g$. We call $\ell \in P$ a least element of $A$ if $\ell \in A$ and, in addition, $a \in A \implies \ell \preceq a$.

If $A$ is totally ordered, then a greatest element $g$ of $A$ is also called a maximum of $A$, whereas a least element $\ell$ of $A$ is also called a minimum. See Appendix Appendix A for more about maxima and minima.

2.2.1.3Sup and Inf¶

Concepts of suprema and infima on the real line (Appendix Appendix A) extend naturally to partially ordered sets. Given a partially ordered set $(P, \preceq)$ and a nonempty subset $A$ of $P$, we call $u \in P$ an upper bound of $A$ if $a \preceq u$ for all $a$ in $A$. Letting $U_P(A)$ be the set of all upper bounds of $A$ in $P$, we call $\bar u \in P$ a supremum of $A$ if

Thus, $\bar u$ is the least element (see Section 2.2.1.2) of the set of upper bounds $U_P(A)$, whenever it exists.

If $P \subset \RR$ and $\preceq$ is $\leq$, then the notion of supremum on a partially ordered set reduces to the elementary definition of the supremum for subsets of the real line discussed in Appendix Appendix A.

Letting $A$ be a subset of partially ordered space $P$,

• the supremum of $A$ is typically denoted $\bigvee A$.

• If $A = \{a_i\}_{i \in I}$ for some index set $I$, we also write $\bigvee A$ as $\bigvee_i \, a_i$.

• If $A = \{a, b\}$, then $\bigvee A$ is also written as $a \vee b$.

Suprema and greatest elements are clearly related. The next exercise clarifies this.

We call $\ell \in P$ a lower bound of $A$ if $a \succeq \ell$ for all $a$ in $A$. An element $\bar \ell$ of $P$ is called a infimum of $A$ if $\bar \ell$ is a lower bound of $A$ and $\bar \ell \succeq \ell$ for every lower bound $\ell$ of $A$. We use analogous notation to denote the infimum. For example, if $A = \{a, b\}$, then $\bigwedge A$ is also written as $a \wedge b$.

2.2.2The Case of Pointwise Order¶

For us, the pointwise partial order $\leq$ introduced in Example 2.2.2 is especially useful. In this section, we review some properties of this order. Throughout, $\Xsf$ is an arbitrary finite set.

2.2.2.1Suprema and Infima under a Pointwise Order¶

Given $u, v \in \RR^\Xsf$, the symbol $u \wedge v$ is possibly ambiguous because we used the symbol both for a pointwise minimum in Section 1.2.4.1 and an infimum of $\{u, v\}$ in Section 2.2.1.3. Fortunately, for elements of the partially ordered set $(\RR^\Xsf, \leq)$, these two definitions coincide. Indeed, if $f(x) \coloneq \min\{u(x), v(x)\}$ for all $x \in \Xsf$, then

1. $f$ is a lower bound for $\{u, v\}$ in $(\RR^\Xsf, \leq)$, and

2. $g \leq u$ and $g \leq v$ implies $g \leq f$.

Hence $f$ is the infimum of $\{u, v\}$ in $(\RR^\Xsf, \leq)$.

A subset $V$ of $\RR^\Xsf$ is called a sublattice of $\RR^\Xsf$ if

$u, v \in V$ implies $u \vee v \in V$ and $u \wedge v \in V$.

Above we discussed the fact that, for a pair of functions $\{u, v\}$, the supremum in $(\RR^\Xsf, \leq)$ is the pointwise maximum, whereas the infimum in $(\RR^\Xsf, \leq)$ is the pointwise minimum. The same principle holds for finite collections of functions. Thus, if $\{ v_i \} \coloneq \{ v_i \}_{i \in I}$ is a finite subset of $\RR^\Xsf$, then, for all $x \in \Xsf$,

The next example discusses greatest elements in the setting of pointwise order.

Figure Figure 2.6 helps illustrate Example 2.2.7. In this case, $v^*$ is not in $\{v_\sigma\}$ and $\{v_\sigma\}$ has no greatest element (since neither $v_{\sigma'} \leq v_{\sigma''}$ nor $v_{\sigma''} \leq v_{\sigma'}$).

Given a partially ordered set $(P, \preceq)$ and $a, b \in P$, the order interval $[a, b]$ is defined as all $p\in P$ such that $a \preceq p \preceq b$. (If $a \preceq b$ fails, the order interval is empty.)

2.2.2.2Inequalities and Identities¶

In this section, we note some useful inequalities and identities related to the pointwise partial order on $\RR^\Xsf$. As before, $\Xsf$ is any finite set.

These results follow immediately from proofs of corresponding claims when $f,g$, and $h$ are in $\RR$. For example, by the usual triangle inequality for scalars, we have $|f(x) + g(x)| \leq |f(x)| + |g(x)|$ for all $x \in \Xsf$. This is equivalent to the statement $|f+g| \leq |f|+|g|$ in (i). Similarly, inequality (v) follows directly from a corresponding scalar inequality that was already proved in Exercise 1.32,.

A complete proof of lemma Lemma 2.2.1 can be found with Theorem 30.1 of Aliprantis & Burkinshaw (1998).

It is also true that, if $f, g, h \in \RR_+^\Xsf$, then

We note the following useful inequality.

The inequality in Lemma 2.2.2 helps with dynamic programming problems that involve maximization. The next exercise concerns minimization.

We end this section with a discussion of upper envelopes. To frame the discussion, we take $\{ T_\sigma \} \coloneq \{ T_\sigma \}_{\sigma \in \Sigma}$ to be a finite family of self-maps on a sublattice $V$ of $\RR^\Xsf$. Consider some properties of the operator $T$ on $V$ defined by

It follows from the sublattice property that $T$ is a self-map on $V$. In some sources, $T$ is called the upper envelope of the functions $\{ T_\sigma \}$. The following lemma will be useful for dynamic programming.

2.2.3Order-Preserving Maps¶

Order-preserving maps appear throughout the theory of dynamic programming. Here we define them and state a condition for contractivity that requires the order preserving property.

2.2.3.1Definition¶

Given two partially ordered sets $(P, \preceq)$ and $(Q, \trianglelefteq)$, a map $T$ from $P$ to $Q$ is called order-preserving if, given $p, p' \in P$, we have

$T$ is called order-reversing if, instead,

2.2.3.2Increasing and Decreasing Functions¶

Regarding the definitions in (2.28) and (2.29), when $(Q, \trianglelefteq) = (\RR, \leq)$, it is common to say “increasing” instead of order-preserving, and “decreasing” instead of order-reversing. We adopt this terminology. In particular, given partially ordered set $(P, \preceq)$, we call $h \in \RR^P$

• increasing if $p \preceq p'$ implies $h(p) \leq h(p')$ and

• decreasing if $p \preceq p'$ implies $h(p) \geq h(p')$.

We use the symbol $i\RR^P$ for the set of increasing functions in $\RR^P$.

The next exercise shows that, in a totally ordered setting, an increasing function can be represented as the sum of increasing binary functions.

As usual, if $h \colon P \to Q$ and $P, Q \subset \RR$, then we will call $h$

• strictly increasing if $x < y$ implies $h(x) < h(y)$, and

• strictly decreasing if $x < y$ implies $h(x) > h(y)$.

2.2.3.3Blackwell’s Condition¶

Our discussion of Banach’s Theorem in Section 1.2.2.3 showed the usefulness of contractivity. For an order-preserving operator on a subset of $\RR^\Xsf$, the following condition often simplifies establishing this property. In the statement of the lemma, $U$ is a subset of $\RR^\Xsf$, partially ordered by $\leq$, and $\Xsf$ is finite. Also, $U$ has the property that $u \in U$ and $c \in \RR_+$ implies $u

• c \in U$.

2.2.4Stochastic Dominance¶

So far we have discussed partial orders over vectors, functions and sets. It is also useful to have a partial order over distributions that tells us when one distribution is in some sense “larger” than another. In this section, we introduce a partial order over some distributions commonly used in economics and finance.

Let’s start with an example. Recall that a random variable $X$ is binomial $B(n,0.5)$ if it counts the number of heads in $n$ flips of a fair coin. Figure Figure 2.7 shows two distributions, $\phi \eqdist X \sim B(10, 0.5)$ and $\psi \eqdist Y \sim B(18, 0.5)$. Since $Y$ counts over more flips, we expect it to take larger values in some sense, and we also expect its distribution $\psi$ to reflect this. How can we make these thoughts precise?

A standard order over distributions that captures this idea is defined as follows: Given finite set $\Xsf$ partially ordered by $\preceq$ and $\phi, \psi \in \dD(\Xsf)$, we say that $\psi$ stochastically dominates $\phi$ and write $\phi \lefsd \psi$ if

The relation $\lefsd$ is also called first-order stochastic dominance to differentiate it from other forms of stochastic order.

A good way to interpret first-order stochastic dominance is to suppose that an agent has preferences over outcomes in $\Xsf$ described by a utility function $u \in \RR^\Xsf$. Suppose in addition that the agent prefers more to less, in the sense that $u \in i\RR^\Xsf$, and that the agent ranks lotteries over $\Xsf$ according to expected utility, so that the agent evaluates $\phi \in \dD(\Xsf)$ according to $\sum_x u(x) \phi(x)$. Then the agent (weakly) prefers $\psi$ to $\phi$ whenever $\phi \lefsd \psi$.

We can say more. Consider the class $\aA$ of all agents who (a) have preferences over outcomes in $\Xsf$, (b) prefer more to less, and (c) rank lotteries over $\Xsf$ according to expected utility. Then $\phi \lefsd \psi$ if and only if every agent in $\aA$ prefers $\psi$ to $\phi$.

To state another useful perspective on stochastic dominance, we introduce the notation

For a given distribution $\phi$, the function $G^\phi$ is sometimes called the counter CDF (counter cumulative distribution function) of $\phi$.

The proof is given. Figure Figure 2.8 helps to illustrate. Here $\Xsf \subset \RR$ and $\phi$ and $\psi$ are distributions on $\Xsf$. We can see that $\phi \lefsd \psi$ because the counter CDFs are ordered in the sense that $G^\phi \leq G^\psi$ pointwise on $\Xsf$.

2.2.5Parametric Monotonicity¶

We are often interested in whether a change in a parameter shifts an outcome up or down. For example, a parameter might appear in a central bank decision rule for pegging an interest rate, and we want to know whether increasing that parameter will increase steady state inflation. By providing sufficient conditions for monotone shifts in fixed points, results in this section can help answer such questions.

Let $(P, \preceq)$ be a partially ordered set. Given two self-maps $S$ and $T$ on a set $P$, we write $S \preceq T$ if $S u \preceq T u$ for every $u \in P$ and say that $T$ dominates $S$ on $P$.

One might assume that, in a setting where $T$ dominates $S$, the fixed points of $T$ will be larger. This can hold, as in Figure Figure 2.9, but it can also fail, as in Figure Figure 2.10. A difference between these two situations is that in Figure Figure 2.9 the map $T$ is globally stable. This leads us to our next result.

As an application of Proposition 2.2.7, consider again the Solow--Swan growth model $k_{t+1} = g(k_t) \coloneq s f(k_t) + (1 - \delta) k_t$. We saw in Section 1.2.3.2 that if $f(k) = Ak^\alpha$ where $A > 0$ and $\alpha \in (0, 1)$, then $g$ is globally stable on $M \coloneq (0,\infty)$. Clearly $k \mapsto g(k)$ is order-preserving on $M$. If we now increase, say, the savings rate $s$, then $g$ will be shifted up everywhere, implying, via Proposition 2.2.7, that the fixed point also rises. Exercise 2.45 asks you to step through the details.

Figure Figure 2.11 helps illustrate the results of Exercise 2.45. The top left sub-figure shows a baseline parameterization, with $A=2.0$, $s = \alpha = 0.3$ and $\delta=0.4$. The other sub-figures show how the steady state changes as parameters deviate from that baseline.

Figure Figure 2.12 gives an illustration of the result in Exercise 2.46. Here an increase in $\beta$ leads to a larger continuation value. This seems reasonable, since larger $\beta$ indicates more concern about outcomes in future periods.

While the preceding examples of parametric monotonicity are all one-dimensional, we will soon see that Proposition 2.2.7 can also be applied in high-dimensional settings.

2.3Matrices and Operators¶

Many aspects of dynamic programming are most clearly framed using operator theory. In this section, we discuss linear operators and their connections to matrices. We emphasize nonnegative matrices and so-called positive linear operators that arise naturally in dynamic programming.

2.3.1Nonnegative Matrices¶

We begin by reviewing basic properties of nonnegative matrices.

2.3.1.1Nonnegative Matrices and Their Powers¶

We call a matrix $A$ nonnegative and write $A \geq 0$ if all elements of $A$ are nonnegative. We call $A$ everywhere positive and write $A \gg 0$ if all elements of $A$ are strictly positive. A square matrix $A$ is called irreducible if $A \geq 0$ and $\sum_{k=1}^\infty A^k \gg 0$. An interpretation in terms of connected networks is given in Chapter 1 of Sargent & Stachurski (2023).

Let $A$ be $n \times n$. It is not always true that the spectral radius $\rho(A)$ is an eigenvalue of $A$.^[1] However, when $A \geq 0$, the spectral radius is always an eigenvalue. The following theorem states this result and several extensions.

The convergence in (2.43) provides a sharp characterization of large powers of $A$ that will prove useful in what follows. The assumption that $A$ is everywhere positive can be weakened without affecting this convergence. A complete statement and full proof of the Perron--Frobenius theorem can be found in Meyer (2000).

We can use the Perron--Frobenius theorem to provide bounds on the spectral radius of a nonnegative matrix. Fix $n \times n$ matrix $A = (a_{ij})$ and set

• $\rsum_i(A) \coloneq \sum_j a_{ij} =$ the $i$-th row sum of $A$ and

• $\csum_j(A) \coloneq \sum_i a_{ij} =$ the $j$-th column sum of $A$.

2.3.1.2A Local Spectral Radius Result¶

Let $A$ be an $n \times n$ matrix. We know from Gelfand’s formula that if $\| \cdot \|$ is any matrix norm, then $\|A^k\|^{1/k} \to \rho(A)$ as $k \to \infty$. While useful, this lemma can be difficult to apply because it involves matrix norms. Fortunately, when $A$ is nonnegative, we have the following variation, which only involves vector norms.

The expression on the left of (2.44) is sometimes called the local spectral radius of $A$ at $h$. Lemma 2.3.3 gives one set of conditions under which a local spectral radius equals the spectral radius. This result will be useful when we examine state-dependent discounting in Chapter 6.

For a proof of Lemma 2.3.3 see Theorem 9.1 of Krasnosel’skii et al. (1972).

2.3.1.3Markov Matrices¶

An $n \times n$ matrix $P$ is called a stochastic matrix or Markov matrix if

where $\1$ is a column vector of ones, so that $P$ is nonnegative and has unit row sums. The Perron--Frobenius theorem will be useful for the following exercise.

The vector $\psi$ in part (iii) of Exercise 2.48 is called a stationary distribution for $P$. Such distributions play an important role in the theory of Markov chains. We discuss their interpretation and significance in Section 3.1.2.

2.3.2A Lake Model¶

We illustrate the power of the Perron--Frobenius theorem by showing how it helps us analyze a model of employment and unemployment flows in a large population.

The model is sometimes called a “lake model” because there are two pools of workers: those who are currently employed and those who are currently unemployed but still seeking work. The flows between states are as follows:

• Workers exit the labor market at rate $d$.

• New workers enter the labor market at rate $b$.

• Employed workers separate from their jobs and become unemployed at rate $\alpha$.

• Unemployed workers find jobs at rate $\lambda$.

We assume that all parameters lie in $(0, 1)$. New workers are initially unemployed.

Transition rates between two pools appear in Figure Figure 2.13. For example, the rate of flow from employment to unemployment is $\alpha (1-d)$, which equals the fraction of employed workers who remained in the labor market and separated from their jobs.

Let $e_t$ and $u_t$ be the number of employed and unemployed workers at time $t$ respectively. The total population (of workers) is $n_t \coloneq e_t + u_t$. In view of the rates just stated, the number of unemployed workers evolves according to

The three terms on the right correspond to the newly unemployed (due to separation), the unemployed who failed to find jobs last period, and new entrants into the labor force. The number of employed workers evolves according to

Evolution of the time series for $u_t$, $e_t$ and $n_t$ is illustrated in Figure Figure 2.14. We set parameters to $\alpha = 0.01$, $\lambda = 0.1$, $d = 0.02$, and $b = 0.025$. The initial population of unemployed and employed workers are $u_0 = 0.6$ and $e_0 =1.2$, respectively. The series grow over the long run due to net population growth.

Can we say more about the dynamics of this system? For example, what long-run unemployment rate should we expect? Also, do long-run outcomes depend heavily on the initial conditions $u_0$ and $e_0$? Can we make some general statements that hold regardless of the initial state?

To begin to address these questions, we first organize the linear system for $(e_t)$ and $(u_t)$ by setting

With these definitions, we can write the dynamics as $x_{t+1} = A x_t$. As a result, $x_t = A^t x_0$, where $x_0 = (u_0 \; e_0)^\top$.

The overall growth rate of the total labor force is $g = b - d$, in the sense that $n_{t+1} = (1+g) n_t$ for all $t$.

In the language of Perron--Frobenius theory, the right eigenvector $\bar x$ is called the dominant eigenvector, since it corresponds to the dominant (i.e., largest) eigenvalue $\rho(A)$. This eigenvector plays an important role in determining long-run outcomes. In the remainder of this section we illustrate this fact.

To begin, recall that $\alpha \bar x$ is also a right eigenvector corresponding to the eigenvalue $\rho(A)$ when $\alpha > 0$. The set $D \coloneq \setntn{x \in \RR^2}{x = \alpha \bar x \text{ for some } \alpha > 0}$ is shown as a dashed black line in Figure Figure 2.15. The figure also shows two time paths, each of the form $(x_t)_{t \geq 0} = (A^t x_0)_{t \geq 0}$, generated from two different initial conditions. In both cases, we see that both paths converge to $D$ over time. The figure suggests that paths share strong similarities in the long run that are determined by the dominant eigenvector $\bar x$.

To see why this is so, we return (2.43) from to the Perron--Frobenius theorem, which tells us that, since $A \gg 0$, we have

As a result, for any initial condition $x_0 = (u_0 \; e_0)^\top$, we have

where $n_t =(1 + g)^t n_0$ and $n_0 = u_0 + e_0$. This says that, regardless of the initial condition, the state $x_t$ scales along $\bar x$ at the rate of population growth. This is precisely what we saw in Figure Figure 2.15.

We can provide additional interpretations to the components $\bar u$ and $\bar e$ of $\bar x$. Since $n_t$ is the size of the workforce at time $t$, the rate of unemployment is $u_t / n_t$. As just shown, for large $t$ this is close to $(n_t \bar u) / n_t = \bar u$. Hence $\bar u$ is the long-term rate of unemployment along the stable growth path. Similarly, the other component $\bar e$ of the dominant eigenvector is the long-run employment rate.

In summary, the dominant eigenvector provides with both the long-run rate of unemployment and the stable growth path, to which all trajectories with positive initial conditions converge over time.

2.3.3Linear Operators¶

There are two ways to think about a matrix. In one definition, an $n \times k$ matrix $A$ is an $n \times k$ array of (real) numbers. In the second, $A$ is a linear operator from $\RR^k$ to $\RR^n$ that takes a vector $u \in \RR^k$ and sends it to $Au$ in $\RR^n$. Let’s clarify these ideas in a setting where $n=k$. While the matrix representation is important, the linear operator representation is more fundamental and more general.

2.3.3.1Matrices versus Linear Operators¶

A linear operator on $\RR^n$ is a map $L$ from $\RR^n$ to $\RR^n$ such that

(We write $Lu$ instead of $L(u)$, etc.) For example, if $A$ is an $n \times n$ matrix, then the map from $u$ to $Au$ defines a linear operator, since the rules of matrix algebra yield $A(\alpha u + \beta v) = \alpha Au + \beta Av$.

We just showed that each matrix can be regarded as a linear operator. In fact the converse is also true:

A proof of Theorem 2.3.4 can be found in Kreyszig (1978) and many other sources.

Why introduce linear operators if they are essentially the same as matrices? One reason is that, while a one-to-one correspondence between linear operators and matrices holds in $\RR^n$, the concept of linear operators is far more general. Linear operators can be defined over many different kinds of sets whose elements have vector-like properties. This is related to the point that we made about function spaces in Remark 1.2.2.

Another reason is computational: The matrix representation of a linear operator can be tedious to construct and difficult to instantiate in memory in large problems. We illustrate this point in Section 2.3.3.3.

2.3.3.2Linear Operators on Function Space¶

The definition of linear operators on $\RR^n$ extends naturally to linear operators on $\RR^\Xsf$ when $\Xsf = \{x_1, \ldots, x_n\}$: A linear operator on $\RR^\Xsf$ is a map $L$ from $\RR^\Xsf$ to itself such that, for all $u, v \in \RR^\Xsf$ and $\alpha, \beta \in \RR$, we have $L(\alpha u + \beta v) = \alpha Lu + \beta Lv$. In what follows,

Let $L$ be a function from $\Xsf \times \Xsf$ to $\RR$. This function induces an operator $L$ from $\RR^\Xsf$ to itself via

We use the same symbol $L$ on both sides of the equals sign because both represent essentially the same object (in the sense that a matrix $A$ can be viewed as a collection of numbers $(A_{ij})$ or as a linear map $u \mapsto Au$).

The function $L$ on the right-hand side of (2.56) is sometimes called the “kernel” of the operator $L$. However, we will call it a matrix in what follows, since $L(x, x') = L(x_i, x_j)$ is just an $n \times n$ array of real numbers. When more precision is required, we will call it the matrix representation of $L$.