are met, subject to capacity constraints. The fact that orders are met means
that $o_{ij}=z_{ij}=a_{ij}x_{j}$. Substituting this equality into (5.6) and
rewriting as a vector equality, (5.6) can equivalently be formulated as

$x=Gx\quad\text{where}\quad Gx:=(Ax+d)\wedge\bar{x}.$ (5.7)

The following exercise is key to solving the fixed point problem (5.7). Prove
that, for any $x,y\in\mathbbm{R}^{n}_{+}$ and $k\in\mathbbm{N}$, we have

$|Gx-Gy|\leqslant A|x-y|.$ (5.8)

Fix $x,y\in\mathbbm{R}^{n}_{+}$ and $k\in\mathbbm{N}$. By the inequalities in
§6.1.1.1, applied pointwise to vectors, we have

$|Gx-Gy|=|(Ax+d)\wedge\bar{x}-(AGy+d)\wedge\bar{x}|\leqslant|Ax+d-(Ay+d)|.$

This proves the claim because, by Exercise 6.1.2.2,

$|Ax+d-(Ay+d)|=|A(x-y)|\leqslant A|x-y|.$

We are now ready to prove existence of a unique fixed point under the
assumption that every sector has positive value added.

######  Proposition 5.1.4.

If Assumption 2.1.1 holds, then $G$ is globally stable in
$\mathbbm{R}^{n}_{+}$. In particular, the constrained production model has a
unique equilibrium $x^{*}\in\mathbbm{R}^{n}_{+}$.

###### Proof.

As shown in Exercise 2.1.2.2, Assumption 2.1.1 yields $r(A)<1$. Moreover,
$A\geqslant 0$. Hence, by Exercise 5.1.3.1 and Proposition 5.1.3, $G$ is
eventually contracting on $\mathbbm{R}_{+}$. In consequence, a unique
equilibrium exists. ∎

######  Remark 5.1.1.

In Proposition 5.1.4, the weaker conditions on production discussed in
§2.3.4.1 can be used in place of Assumption 2.1.1, which requires positive
value added in every sector. As explained in §2.3.4.1, for $r(A)<1$ it is
enough that value added is nonnegative in each sector and, in addition, every
sector has an upstream supplier with positive value added.

#####  5.1.4 Fixed Points and Monotonicity

Banach’s fixed point theorem and its extensions are foundations of many
central results in pure and applied mathematics. For our purposes, however, we
need to search a little further, since not all mappings generated by network
models have the contraction property. In this section, we investigate two
fixed point results that drop contractivity in favor of monotonicity.

######  5.1.4.1 Existence

Without contractivity, one needs to work harder to obtain even existence of
fixed points, let alone uniqueness and convergence. This is especially true of
the map in question fails to be continuous. If, however, the map is order
preserving, then existence can often be obtained via some variation on the
Knaster–Tarski fixed point theorem. Here we present a version of this
existence result that is optimized to our setting, while avoiding unnecessary
excursions into order theory. In stating the theorem, we recall that a closed
order interval in $\mathbbm{R}^{n}$ is a set of the form

$[a,b]:=\\{x\in\mathbbm{R}^{n}:a\leqslant x\leqslant b\\}$

where $a$ and $b$ are vectors in $\mathbbm{R}^{n}$. Also, we call
$(x_{k})\subset\mathbbm{R}^{n}$ increasing (resp., decreasing) if
$x_{k}\leqslant x_{k+1}$ (resp., $x_{k}\geqslant x_{k+1}$) for all $k$. Let
$[a,b]$ be a closed order interval in $\mathbbm{R}^{n}$ and let $G$ be an
order-preserving self-map on $[a,b]$. Prove the following:

  1. (i)

$(G^{k}a)$ is increasing and $(G^{k}b)$ is decreasing.

  2. (ii)

If $x$ is a fixed point of $G$ in $[a,b]$, then $G^{k}a\leqslant x\leqslant
G^{k}b$ for all $k\in\mathbbm{N}$.

Since $G$ is a self-map on $[a,b]$, we have $Ga\in[a,b]$ and hence $a\leqslant
Ga$. As $G$ is order preserving, applying $G$ to this inequality yields
$Ga\leqslant G^{2}a$. Continuing in this way (or using induction) proves that
$(G^{k}a)$ is increasing. The proof for $(G^{k}b)$ is similar. If $Gx=x$ for
some $x\in[a,b]$, then, since $a\leqslant x$, we have $Ga\leqslant Gx=x$.
Iterating on this inequality gives $G^{k}a\leqslant x$ for all $k$. For a
self-map $G$ on $S\subset\mathbbm{R}^{n}$, we say that $x^{*}$ is a least
fixed point (resp., greatest fixed point) of $G$ on $S$ if $x^{*}$ is a fixed
point of $G$ in $S$ and $x^{*}\leqslant x$ (resp., $x\leqslant x^{*}$) for
every fixed point $x$ of $G$ in $S$. Finally, we say that $G$ is

  * •

continuous from below if $x_{k}\uparrow x$ in $S$ implies $Gx_{k}\uparrow Gx$
in $S$.

  * •

continuous from above if $x_{k}\downarrow x$ in $S$ implies $Gx_{k}\downarrow
Gx$ in $S$.

Here $x_{k}\uparrow x$ means that $(x_{k})$ is increasing and $x_{k}\to x$.
The definition of $x_{k}\downarrow x$ is analogous. In the next theorem,
$S:=[a,b]$ is a closed order interval in $\mathbbm{R}^{n}$ and $G$ is a self-
map on $S$.

######  Theorem 5.1.5.

If $G$ is order-preserving on $S$, then $G$ has a least fixed point $x^{*}$
and a greatest fixed point $x^{**}$ in $S$. Moreover,

  1. (i)

if $G$ is continuous from below, then $G^{k}a\uparrow x^{*}$ and

  2. (ii)

if $G$ is continuous from above, then $G^{k}b\downarrow x^{**}$.

######  Remark 5.1.2.

As alluded to above, fixed point results for order preserving maps can be
obtained in more general settings than the ones used in Theorem 5.1.5 (see,
e.g., Davey and Priestley, (2002), Theorem 2.35). Theorem 5.1.5 is sufficient
for our purposes, given our focus on finite networks.

###### Proof of Theorem 5.1.5.

Under the stated conditions, existence of least and greatest fixed points
$x^{*}$ and $x^{**}$ follow from the Knaster–Tarski fixed point theorem. (This
holds because $[a,b]$ is a complete lattice. For a definition of complete
lattices and a proof of the Knaster–Tarski theorem, see, e.g., Davey and
Priestley, (2002).) Regarding claim (i), suppose that $G$ is continuous from
below and consider the sequence $(x_{k}):=(G^{k}a)_{k\geqslant 1}$. Since $G$
is order-preserving (and applying Exercise 5.1.4.1), this sequence is
increasing and bounded above by $x^{*}$. Since bounded monotone sequences in
$\mathbbm{R}$ converge, each individual component of the vector sequence
$x^{k}$ converges in $\mathbbm{R}$. Hence, by Lemma 2.3.1, the vector sequence
$x^{k}$ converges in $\mathbbm{R}^{n}$ to some $\bar{x}\in[a,x^{*}]$. Finally,
by continuity from below, we have

$\bar{x}=\lim_{k}G^{k}a=\lim_{k}G^{k+1}a=G\lim_{k}G^{k}a=G\bar{x},$

so that $\bar{x}$ is a fixed point. We have now shown that $(G^{k}a)$
converges up to a fixed point $\bar{x}$ of $G$ satisfying $\bar{x}\leqslant
x^{*}$. Since $x^{*}$ is the least fixed point of $G$ in $S$, we also have
$x^{*}\leqslant\bar{x}$. Hence $\bar{x}=x^{*}$. The proof of claim (ii) is
similar to that of claim (i) and hence omitted. ∎

######  Remark 5.1.3.

In the preceding theorem, $x^{*}$ and $x^{**}$ can be equal, in which case $G$
has only one fixed point in $S$.

Consider the map $Gx=(Ax+d)\wedge\bar{x}$ from the constrained production
model. In §5.1.3.1, we showed that $G$ has a unique fixed point in
$\mathbbm{R}^{n}_{+}$ when $r(A)<1$. Show now that $G$ has at least one fixed
point in $\mathbbm{R}^{n}_{+}$, even when $r(A)<1$ fails. (Continue to assume
that $A\geqslant 0$, $d\geqslant 0$ and $\bar{x}\geqslant 0$.) Clearly $G$ is
a self-map on $S:=[0,\bar{x}]$. Since $A\geqslant 0$, we have $Gx\leqslant Gy$
for all $x,y\in S$. From this it follows easily that $G$ is order-preserving.
Theorem 5.1.5 now guarantees existence of at least one fixed point.

######  5.1.4.2 Du’s Theorem

Theorem 5.1.5 is useful because of its relatively weak assumptions. At the
same time, it fails to deliver uniqueness. Hence its conclusions are
considerably weaker than the results we obtained from contractivity
assumptions in §5.1.1. In order to recover uniqueness without imposing
contractivity, we now consider order-preserving maps that have additional
shape properties. In doing so, we use the definition of concave and convex
functions in §6.1.5.2.

######  Theorem 5.1.6 (Du).

Let $G$ be an order-preserving self-map on order interval
$S=[a,b]\subset\mathbbm{R}^{n}$. In this setting, if either

  1. (i)

$G$ is concave and $Ga\gg a$ or

  2. (ii)

$G$ is convex and $Gb\ll b$,

then $G$ is globally stable on $S$.

A proof of Theorem 5.1.6 was obtained in an more abstract setting in Du,
(1990). Interested readers can consult that article for a proof. To illustrate
how this results can be applied, consider the constrained production model
without assuming positive value added, so that $r(A)<1$ is not enforced. In
Exercise 5.1.4.1 we obtained existence. With Theorem 5.1.6 in hand, we can
also show uniqueness whenever $d\gg 0$ and $\bar{x}\gg 0$. Indeed, we have
already seen that $G$ is a self-map on $S:=[0,\bar{x}]$ and, when this last
condition holds, we have $G0=d\wedge\bar{x}\gg 0$. Hence the conclusions of
Theorem 5.1.6 will hold if we can establish that $G$ is concave. Prove that
$G$ is concave on $S$. [Hint: Review §6.1.5.2.] By Exercise 6.1.5.2, the
minimum of two concave functions is concave. Since $Fx=\bar{x}$ and $Hx=Ax+b$
are both concave, the claim holds. Here is a small extension of Du’s theorem
that will prove useful soon:

######  Corollary 5.1.7.

Let $G$ be an order-preserving self-map on $S=[a,b]$. If $G$ is concave and
there exists an $\ell\in\mathbbm{N}$ such that $G^{\ell}a\gg a$, then $G$ is
globally stable on $S$.

###### Proof.

Assume the conditions of Corollary 5.1.7. Since compositions of increasing
concave operators are increasing and concave, Theorem 5.1.6 implies that
$G^{\ell}$ is globally stable on $[a,b]$. Denote its fixed point by $\bar{v}$.
Since $\\{G^{m}a\\}_{m\in\mathbbm{N}}$ is increasing and since the subsequence
$\\{G^{m\ell}a\\}_{m\in\mathbbm{N}}$ converges up to $\bar{v}$ as
$m\to\infty$, we must have $G^{m}a\to\bar{v}$. A similar argument gives
$G^{m}b\to\bar{v}$. For any $v\in[a,b]$ we have $G^{m}a\leqslant
G^{m}v\leqslant G^{m}b$, so $G^{m}v\to\bar{v}$ as $m\to\infty$. The last step
is to show that $\bar{v}$ is the unique fixed point of $G$. From Theorem
5.1.5, we know that at least one fixed point exists. Now suppose $v\in[a,b]$
is such a point. Then $v=G^{m}v$ for all $m$. At the same time,
$G^{m}v\to\bar{v}$ by the results just established. Hence $v=\bar{v}$. The
proof is now complete. ∎

####  5.2 Financial Networks

Given the long history of crises in financial markets around the globe,
economists and business analysts have developed many tools for assessing the
credit-worthiness of banks and other financial institutions. After the major
financial crises of 2007-2008, originating in the subprime market in the US
and the sudden collapse of Lehmann Brothers, it became clear that the
financial health of individual institutions cannot be assessed in isolation.
Rather, it is essential to analyze solvency and credit-worthiness in terms of
the entire network of claims and liabilities within a highly interconnected
financial system. In this section, we review financial crises and apply
network analysis to study how they evolve.

#####  5.2.1 Contagion

Some financial crises have obvious causes external to the banking sector. A
prominent example is the hyperinflation that occured in Weimar Germany around
1921–1923, which was driven by mass printing of bank notes to meet war
reparations imposed under the Treaty of Versailles. Here the monetary
authority played the central role, while the actions of private banks were
more passive. Other crises seem to form within the financial sector itself,
driven by interactions between banks, hedge funds, and asset markets. In many
cases, the crisis follows a boom, where asset prices rise and economic growth
is strong. Typically, the seeds of the crisis are laid during this boom phase,
when banks extend loans and firms raise capital on the basis of progressively
more speculative business plans. At some point it becomes clear to investors
that these business will fail to meet expectations, leading to a rush for the
exit. The last phase of this cycle is painful for the financial sector, since
rapidly falling asset values force banks and other financial institutions to
generate short-term capital by liquidating long-term loans, typically with
large losses, as well as selling assets in the face of falling prices,
hoarding cash and refusing to roll over or extend short term loans to other
institutions in the financial sector. The financial crisis of 2007–2008
provides a textbook example of these dynamics. One key aspect of the financial
crisis of 2007–2008, as well as other similar crises, is contagion, which
refers to the way that financial stress spreads across a network of financial
institutions. If one institution becomes stressed, that stress will often
spread to investors or counterparties to which this institution is indebted.
The result of this process is not easy to predict, since, like equilibrium in
the production networks studied in Chapter 2, there is a tail chasing problem:
stress spreads from institution $A$ to institutions $B$, $C$ and $D$, which
may in turn increase stress on $A$, and so on. In this section we study
financial contagion, beginning with a now-standard model of default cascades.

#####  5.2.2 Default Cascades

Default cascades are a form of financial contagion, in which default by a node
in a network leads to default by some of its counterparties, which then
spreads across the network. Below we present a model of default cascades and
analyze its equilibria.

######  5.2.2.1 Network Valuation

Consider a financial network $\mathscr{G}=(V,E,w)$, where $V=[n]$ is a list of
$n$ financial institutions called _banks_ , with an edge $(i,j)\in E$
indicating that $j$ has extended credit to $i$. The size of that loan is
$w(i,j)$. Thus, an edge points in the direction of a liability, as in Figure
1.17 on page 1.17: edge $(i,j)$ indicates a liability for $i$ and an asset for
$j$. As in §1.4.1, the set of all direct predecessors of $i\in V$ will be
written as $\mathscr{I}(i)$, while the set of all direct successors will be
denoted $\mathscr{O}(i)$. Banks in the network have both internal and external
liabilities, as well as internal and external assets. Internal (i.e.,
interbank) liabilities and assets are given by the weight function $w$, in the
sense that $w(i,j)$ is a liability for $i$, equal to the size of its loan from
$j$, and also an asset for $j$. Positive weights indicate the presence of
counterparty risk: when $j$ holds an asset of book value $w(i,j)$, whether or
not the loan is repaid in full depends on the stress placed on bank $i$ and
rules that govern repayment in the event of insolvency. We use the following
notation for the primitives of the model:
$x_{i}:=\sum_{j\in\mathscr{O}(i)}w(i,j)$ is total interbank liabilities of
bank $i$,

$\Pi_{ij}:=\begin{cases}w(i,j)/x_{i}&\text{ if }x_{i}>0\\\ 0&\text{
otherwise}\end{cases}$ (5.9)

is the matrix of relative interbank liabilities, $a_{i}$ is external assets
held by bank $i$ and $d_{i}$ is external liabilities. When considering the
interbank assets of bank $j$, we need to distinguish between the book value
$\sum_{i\in\mathscr{I}(j)}w(i,j)$ of its claims on other banks and the
realized value in the face of partial or complete default by its
counterparties $\mathscr{I}(j)$. To this end, we introduce a clearing vector
$p\in\mathbbm{R}^{n}_{+}$, which is a list of proposed payments by each bank
in the network. In particular, $p_{i}$ is total payments made by bank $i$ to
its counterparties within the banking sector. Under the choice of a particular
clearing vector, the actual payments received by bank $j$ on its internal loan
portfolio are $\sum_{i\in V}p_{i}\Pi_{ij}$. The last statement is an
assumption about the legal framework for the banking sector. It means that the
actual payment $p_{i}\Pi_{ij}$ from $i$ to $j$ is proportional to the amount
that $i$ owes $j$, relative to its total interbank obligations. The idea is
that all counterparties in the banking sector have equal seniority, so that
residual funds are spread across claimants according to the relative size of
the claims. Let $\hat{p}_{j}$ be the amount of funds bank $j$ makes available
to repay all of its debts, both interbank and external. This quantity is

$\hat{p}_{j}=\min\left\\{a_{j}+\sum_{i\in
V}p_{i}\Pi_{ij},\;d_{j}+x_{j}\right\\}.$ (5.10)

The right hand term inside the $\min$ operator is total debts of bank $j$. The
left hand side is the amount on hand to repay those debts, including external
assets and repayments by other banks. The bank repays up to—but not beyond—its
ability to pay. External liabilities are assumed to be senior to interbank
liabilities, which means that for bank $j$ we also have

$p_{j}=\max\\{\hat{p}_{j}-d_{j},\;0\\}.$ (5.11)

Thus, interbank payments by $j$ are a remainder after external debts are
settled. If these debts exceed the bank’s ability to pay, the bank becomes
insolvent and pays nothing to internal creditors. This is a form of limited
liability. Combining (5.10) and (5.11) and rearranging slightly yields

$p_{j}=\max\left\\{\min\left\\{a_{j}-d_{j}+\sum_{i\in
V}p_{i}\Pi_{ij},\;x_{j}\right\\},\;0\right\\}$

Now let’s take $p$, $a$, $d$ and $x$ as row vectors in $\mathbbm{R}^{n}$ and
write this collection of equations, indexed of $j$, in vector form. With
$\max$ and $\min$ taken pointwise, and using the symbols $\vee$ and $\wedge$
for max and min, we get

$p=((a-d+p\Pi)\wedge x)\vee 0.$ (5.12)

A solution to this equation is called an equilibrium clearing vector for the
banking system.

######  Remark 5.2.1.

An equilibrium clearing vector captures impacts of contagion within the
specified banking system, in the sense that it traces out the full network
effects of interbank lending within the model. We shall studying this
equilibrium, while also recognizing that the model is restrictive in the sense
that it assumes a specific form for seniority and implicitly rules out some
kinds of nonlinear phenomena. We return to this theme in §5.2.3.

######  5.2.2.2 Existence and Uniqueness of Fixed Points

In order to analyze existence and uniqueness of equilibria, we introduce the
operator $T\colon\mathbbm{R}^{n}\to\mathbbm{R}^{n}$ defined by

$Tp=((e+p\Pi)\wedge x)\vee 0,$ (5.13)

where $e:=a-d$ represents net external assets. Evidently
$p\in\mathbbm{R}^{n}_{+}$ is an equilibrium clearing vector if and only if it
is a fixed point of $T$. Prove that the operator $T$ is continuous on
$\mathbbm{R}^{n}$. In essence, this holds because compositions of continuous
functions are continuous. Nonetheless, here is a more explicit proof:
Recalling the inequalities in §6.1.1.1, applied pointwise to vectors, we have,
for any $p,q\in\mathbbm{R}^{n}$,

$|Tp-Tq|\leqslant|(e+p\Pi)\wedge x)-(e+q\Pi)\wedge x)|\leqslant|(p-q)\Pi|.$

Since, for the Euclidean norm, $\||u|\|=\|u\|$ and $u,v\geqslant 0$ with
$u\leqslant v$ implies $\|u\|\leqslant\|v\|$, we then have $\|Tp-
Tq\|\leqslant\|(p-q)\Pi\|\leqslant\|p-q\|\|\Pi\|_{o}$. It follows easily that
if $\|p_{n}-p\|\to 0$, then $\|Tp_{n}-Tp\|\to 0$ also holds. Using this
operator, establishing existence of at least one equilibrium clearing vector
is not problematic for this model, regardless of the values of the primitives
and configuration of the network: Show that the banking model described above
always has at least one equilibrium clearing vector. What else can you say
about equilibria in this general case? Since $\Pi\geqslant 0$, we always have
$p\Pi\leqslant q\Pi$ whenever $p\leqslant q$. As a result, $p\mapsto a-d+p\Pi$
is order-preserving and hence so is $T$. Moreover, for any $p\in S:=[0,x]$, we
have $Tp\in S$. Hence, by Theorem 5.1.5, $T$ has a fixed point in $S$. What
else can we say about equilibria in this setting? By the same theorem, $T$ has
a least fixed point $p^{*}$ and a greatest fixed point $p^{**}$ in $S$.
Moreover, since $T$ is continuous, $T^{k}0\uparrow p^{*}$ and
$T^{k}x\downarrow p^{**}$. While existence is automatic in this model,
uniqueness is not:

######  Example 5.2.1.

If $n=2$, $e=(0,0)$ and $(1,1)$ and $\Pi=\begin{pmatrix}0&1\\\
1&0\end{pmatrix}$, then $Tp=p$ is equivalent to

$\begin{pmatrix}p_{1}\\\ p_{2}\end{pmatrix}=\begin{pmatrix}p_{2}\\\
p_{1}\end{pmatrix}\wedge\begin{pmatrix}1\\\ 1\end{pmatrix}.$

Both $p=(1,1)$ and $p=(0,0)$ solve this equation.

There are several approaches to proving uniqueness of fixed points of $T$.
Here is one: Prove that $T$ is globally stable on $S:=[0,x]$ whenever
$r(\Pi)<1$.222Here’s a hint, if you get stuck: show that $r(\Pi)<1$ implies
$T$ is an eventual contraction on $[0,x]$ using one of the propositions
presented in this chapter. Fix $p,q\in S$. Using the inequalities for min and
max in §6.1.1.1, applied pointwise, we have

$|Tp-Tq|\leqslant|e+p\Pi-(e+q\Pi)|=|(p-q)\Pi|\leqslant|p-q|\Pi$

After transposing both sides of this equation, we see that, when $r(\Pi)<1$,
the conditions of of Proposition 5.1.3 hold. The result follows. (If you
prefer, instead of taking transposes, just use the proof of Proposition 5.1.3
directly, modified slightly to use the fact that we are operating on row
vectors.) This leads us to the following result:

######  Proposition 5.2.1.

Let $\mathscr{G}$ be a financial network. If, for each bank $i\in V$, there
exists a bank $j\in V$ with $i\to j$ and such that $j$ has zero interbank
liabilities, then $T$ is globally stable on $S$ and $\mathscr{G}$ has a unique
equilibrium clearing vector.

###### Proof.

By construction, the matrix $\Pi$ is substochastic. Suppose that $\Pi$ is also
weakly chained substochastic. Then, by Proposition 2.3.5, we have $r(\Pi)<1$
and, by Exercise 5.2.2.2, $T$ is globally stable on $S$. Hence the proof will
be complete if we can show that, under the stated conditions, $\Pi$ is weakly
chained substochastic. To see that this is so, let $\mathscr{G}$ be a
financial network such that satisfying the conditions of Proposition 5.2.1.
Now fix $i\in V$. We know that there exists a bank $j\in V$ with $i\to j$ and
$j$ has no interbank liabilities. If $w(i,j)>0$, then $\Pi_{ij}>0$, so $i\to
j$ under digraph $\mathscr{G}$ implies $i\to j$ in the digraph induced by the
substochastic matrix $\Pi$. Also, since $j$ has no interbank liabilities, we
have $x_{j}=0$, and hence row $j$ of $\Pi$ is identically zero. In particular,
$\sum_{k}\Pi_{jk}=0$. Hence $\Pi$ is weakly chained substochastic, as
required. ∎

######  Remark 5.2.2.

The proof of Proposition 5.2.1 also shows that $T$ is eventually contracting,
so we can compute the unique fixed point by taking the limit of $T^{k}p$ for
any choice of $p\in S$.

There are several possible assumptions about the structure of the bank network
$\mathscr{G}$ that imply the conditions of Proposition 5.2.1. For example, it
would be enough that $\mathscr{G}$ is strongly connected and has at least one
bank with zero interbank liabilities. Below we investigate another sufficient
condition, related to cyclicality. A digraph $\mathscr{D}$ is called a
directed acyclic graph if $\mathscr{D}$ contains no cycles. Prove the
following: If $\mathscr{D}$ is a directed acyclic graph, then, for any node
$i$ in $\mathscr{D}$, there exists a node $j$ such that $i\to j$ and
$\mathscr{O}(j)=0$. Let $\mathscr{D}$ be a directed acyclic graph and fix $i$
in $\mathscr{D}$. Suppose to the contrary that every node reachable from $i$
has positive out-degree. In this case, we can construct a walk from $i$ of
arbitrary length. But $\mathscr{D}$ has only finitely many nodes, so any such
walk must eventually cycle. Contradiction. Let $\mathscr{G}$ be a financial
network. Show that $\mathscr{G}$ has a unique equilibrium clearing vector
whenever $\mathscr{G}$ is a directed acyclic graph. Let $\mathscr{G}=(V,E,w)$
be a financial network and a directed acyclic graph. By Proposition 5.2.1, it
suffices to show that, for each bank $i\in V$, there exists a bank $j\in V$
with $i\to j$ and such that $j$ has zero interbank liabilities. To this end,
fix $i\in V$. By the directed acyclic graph property, we know that there
exists a $j\in V$ with $i\to j$ and $\mathscr{O}(j)=0$. But if
$\mathscr{O}(j)=0$, then $j$ has no interbank liabilities. The claim follows.

######  5.2.2.3 Nonnegative External Equity

In this section we investigate the special case in which

  1. (E1)

each bank has nonzero interbank debt, so that $\Pi$ is a stochastic matrix,
and

  2. (E2)

external net assets are nonnegative, in the sense that $e=a-d\geqslant 0$.

In view of (E1), we cannot hope to use Proposition 5.2.1, since we always have
$r(\Pi)=1$ when $\Pi$ is stochastic. Nonetheless, we can still obtain global
stability certain restrictions on $e$ and the topology of the network. Here is
a relatively straightforward example, which we will later try to refine: Let
$\mathscr{G}$ be a financial network such that (E1)–(E2) hold. Using Du’s
theorem (page 5.1.6), prove that $T$ has a unique fixed point in $S:=[0,x]$
whenever $e\gg 0$. Let $\mathscr{G}$ be a financial network such that
(E1)–(E2) hold. Since $e\gg 0$, we have

$p\in S\quad\implies\quad Tp:=((e+p\Pi)\wedge x)\vee 0=(e+p\Pi)\wedge x.$

By an argument identical to that employed for Exercise 5.1.4.2 on page
5.1.4.2, $T$ is a concave operator on $S=[0,x]$. Evidently $T$ is order
preserving. Finally, by (E1), we have $x_{i}>0$ for all $i$, so $x\gg 0$ and
hence $T0=e\wedge x\gg 0$. It now follows directly from Du’s theorem that $T$
has a unique fixed point in $S$. The condition $e\gg 0$ is rather strict.
Fortunately, it turns out that we can obtain global stability under
significantly weaker conditions. To this end, we will say that node $j$ in a
financial system $\mathscr{G}$, is _cash accessible_ if there exists an $i\in
V$ such that $i\to j$ and $e(i)>0$. In other words, $j$ is downstream in the
liability chain from at least one bank with positive net assets outside of the
banking sector. Prove the following result: If (E1)–(E2) hold and every node
in $\mathscr{G}$ is cash-accessible, then $T^{k}0\gg 0$ for some
$k\in\mathbbm{N}$. [This is a relatively challenging exercise.] Let
$\mathscr{G}$ be such that every node is cash-accessible. Set

$\delta:=\frac{1}{n^{2}}\cdot\min\left\\{\\{x_{i}:i\in V\\}\cup\\{e_{i}:i\in
V\,\ \mathrm{s.t.}\ e_{i}>0\\}\right\\}.$

Let $\hat{e}$ be defined by $\hat{e}_{i}=1$ if $e_{i}>0$ and zero otherwise.
We claim that, for all $m\leqslant n$,

$T^{m}0\geqslant\delta(\hat{e}+\hat{e}\Pi+\cdots+\hat{e}\Pi^{m-1}).$ (5.14)

This holds at $m=1$ because $T0=e\wedge x\geqslant\delta\hat{e}$. Now suppose
(5.14) holds at some $m\leqslant n-1$. Then, since $T$ is order-preserving, we
obtain

$\displaystyle T^{m+1}0$
$\displaystyle\geqslant(\delta(\hat{e}+\hat{e}\Pi+\cdots+\hat{e}\Pi^{m-1})\Pi+e)\wedge
x$
$\displaystyle\geqslant(\delta(\hat{e}+\hat{e}\Pi+\cdots+\hat{e}\Pi^{m}))\wedge
x$

Since $\hat{e}+\hat{e}\Pi+\cdots+\hat{e}\Pi^{m}\leqslant n^{2}\mathbbm{1}$,
where $\mathbbm{1}$ is a vector of ones, and since $(\delta
n^{2}\mathbbm{1})\leqslant x$ by the definition of $\delta$, we have
$T^{m+1}0\geqslant\delta(\hat{e}+\hat{e}\Pi+\cdots+\hat{e}\Pi^{m})$. This
argument confirms that (5.14) holds for all $m\leqslant n$. We now claim that
$T^{n}0\gg 0$. In view of (5.14), it suffices to show that, for any $j\in V$,
there exists a $k<n$ with $(\hat{e}\Pi^{k})(j)=\sum_{i\in
V}\hat{e}_{i}\Pi^{k}_{ij}>0$. Since every node in $S$ is cash accessible, we
know there exists an $i\in V$ with $e_{i}>0$ and $j$ is accessible from $i$.
For this $i$ we can choose $k\in\mathbbm{N}$ with $k<n$ and
$\Pi^{k}_{ij}=\hat{e}_{i}\Pi^{k}_{ij}>0$. We conclude that $T^{n}0\gg 0$, as
claimed. With the result from Exercise 5.2.2.3 in hand, the next lemma is easy
to establish.

######  Lemma 5.2.2.

If (E1)–(E2) hold and every node in $\mathscr{G}$ is cash accessible, then $T$
is globally stable and $\mathscr{G}$ has a unique clearing vector $p^{*}\gg
0$.

###### Proof.

Let $\mathscr{G}$ be as described. By Corollary 5.1.7, it suffices to show
that $T$ is an order-preserving concave self-map on $[0,x]$ with $T^{k}0\gg 0$
for some $k\in\mathbbm{N}$. The solution to Exercise 5.2.2.3 shows that $T$ is
order-preserving and concave. The existence of a $k\in\mathbbm{N}$ with
$T^{k}0\gg 0$ was verified in Exercise 5.2.2.3. ∎

Stronger results are available, with a small amount of effort. In fact, under
(E1)–(E2), there is a strong sense in which uniqueness of the fixed point is
obtained without any further assumptions, provided that we rule out an
ambiguity related to what happens when $e=0$. That ambiguity is discussed in
the next exercise and further references that can be found in §5.3. Conditions
(E1) and (E2) cannot by themselves pin down outcomes for the extreme case
where every firm in the network has zero net external assets. Illustrate this
with an example.333Hint: every stochastic matrix has at least one stationary
distribution. Let $\psi$ be a stationary distribution for $\Pi$. Suppose
$\lambda$ is a constant in $[0,1]$, $p=\lambda\psi$ and $x=\psi$. Then $e=0$
implies $Tp=(e+\lambda\psi\Pi)\wedge x=(\lambda\psi)\wedge\psi=\lambda\psi=p$.
Since $\lambda$ was arbitrary in $[0,1]$, there is a continuum of equilibria.
Although Exercise 5.2.2.3 suggests ambiguity about outcomes when $e=0$, it is
natural to adopt the convention that the equilibrium clearing vector $p^{*}$
obeys $p^{*}=0$ whenever $e=0$. If the entire banking sector has no zero net
assets, then no positive payment sequence can be initiated (without outside
capital). In the next exercise, we say that $U\subset V$ is accessible from
$i\in V$ if there exists a $j\in U$ such that $j$ is accessible from $i$. Let
$P$ be the set of all nodes in $V$ that are cash accessible. Let $A$ be all
$i$ in $P^{c}$ such that $P$ is accessible from $i$. Let $N$ be all $i$ in
$P^{c}$ such that $P$ is not accessible from $i$. Note that $V=P\cup A\cup N$
and that these sets are disjoint. Show that $N$ and $P$ are both absorbing
sets. The set $N$ is an absorbing set, since, by definition, $P$ is not
accessible from $N$, and $A$ cannot be accessible because otherwise $P$ would
also be accessible. The set $P$ is also absorbing because, if $j\in P^{c}$ is
accessible from some $i\in P$, then $j$ is cash accessible. But then $j\in P$,
which is a contradiction.

#####  5.2.3 Equity-Cross Holdings

In this section we analyze the model of default cascades constructed by
(Elliott et al.,, 2014). The model differs from the one studied in §5.2.2 in
several ways. One is that financial institutions are linked by share cross-
holdings: firm $i$ owns a fraction $c_{ij}$ of firm $j$ for $i,j\in V:=[n]$.
This implies that failure of firm $j$ reduces the market value of firm $i$,
which in turn reduces the market value of other firms, and so on. The
second—and ultimately more significant—difference is the introduction of
failure costs that add significant nonlinearities to the model. Failure costs
reinforce the impact of each firm failure, leading to greater shock
propagation across the network. This feature ties into the intuitive idea
that, when many firms are financially stressed, a failure by one firm can
trigger a wave of bankruptcies.

######  5.2.3.1 Book and Market Value

We now describe the features of the model. Let $C=(c_{ij})_{i,j\in V}$ be the
matrix of fractional cross-holdings, as mentioned above, with $0\leqslant
c_{ij}\leqslant 1$ for all $i,j$.

######  Assumption 5.2.1.

The matrix of cross-holdings satisfies $\sum_{k}c_{ki}<1$ for all $i\in V$.

Assumption 5.2.1 implies that firms are not solely owned by other firms in the
network: investors outside the network hold at least some fraction of firm $i$
for all $i$. The book value of firm $i$ is given by

$b_{i}=e_{i}+\sum_{j}c_{ij}b_{j}\qquad(i\in V).$ (5.15)

Here the first term $e_{i}\geqslant 0$ is external assets of firm $i$ and the
second represents the value of firm $i$’s cross-holdings. In vector form, the
last equation becomes $b=e+Cb$. Let $I$ be the $n\times n$ identity. Prove
that, under Assumption 5.2.1, the matrix $I-C$ is invertible and the equation
$b=e+Cb$ has the unique solution

$b=(I-C)^{-1}e.$ (5.16)

Prove also that $b\geqslant 0$. Since $C\geqslant 0$, Lemma 1.2.7, we have
$r(C)\leqslant\max_{j}\operatorname{colsum}_{j}(C)$. In view of Assumption
5.2.1, this maximum is strictly less than one. Hence $r(C)<1$ and, by the
Neumann series lemma $I-C$ is invertible and $(I-C)^{-1}=\sum_{k\geqslant
0}C^{k}$. The last equality implies $b\geqslant 0$ when $b=(I-C)^{-1}e$.
Provide a weaker condition on $C$ such that $I-C$ is invertible. Consider the
condition $\sum_{i\in V}c_{ij}\leqslant 1$ for all $j\in V$, with strict
inequality for at least one $j$. Since $C\geqslant 0$, this implies that
$C^{\top}$ is weakly chained substochastic, by Exercise 2.3.4.1. Hence
$r(C)=r(C^{\top})<1$, by Proposition 2.3.5. Hence $I-C$ is invertible, by the
Neumann series lemma. There is a widely used argument that cross-holdings
artificially inflate the value of firms, in the sense that the sum of book
values of firms exceeds $\sum_{i}e_{i}$, the sum of underlying equity values.
The next exercise illustrates: Show that $e\gg 0$ and $\min_{i,j}c_{ij}>0$
implies $\sum_{i}b_{i}>\sum_{i}e_{i}$. We have

$\sum_{i}b_{i}=\mathbbm{1}^{\prime}b=\mathbbm{1}^{\prime}e+\mathbbm{1}^{\prime}Ce+\mathbbm{1}^{\prime}C^{2}e+\cdots\geqslant\mathbbm{1}^{\prime}e+\mathbbm{1}^{\prime}Ce.$

Hence it suffices to show that $\mathbbm{1}^{\prime}Ce>0$. This will be true
if at least one column of $Ce$ has a nonzero entry. Since $e\gg 0$, we require
only that $c_{ij}>0$ for some $i,j$, which is true by assumption. Due to this
artificial inflation, we distinguish between the book value $b_{i}$ of a firm
and its market value $\bar{v}_{i}$, which is defined as $r_{i}b_{i}$ with
$r_{i}:=1-\sum_{k}c_{ki}$. The value $r_{i}$, which gives the share of firm
$i$ held by outsider investors, is strictly positive for all $i$ by Assumption
5.2.1. With $R:=\operatorname{diag}(r_{1},\ldots,r_{n})$, we can write the
vector of market values as $\bar{v}=Rb$. Substituting in (5.16) gives

$\bar{v}:=Ae,\quad\text{where}\quad A:=R(I-C)^{-1}.$ (5.17)

######  5.2.3.2 Failure Costs

So far the model is very straightforward, with the market value of firms being
linear in external assets $e$. However, since bankruptcy proceedings are
expensive, it is reasonable to assume that firm failures are costly. Moreover,
when the market value of a firm falls significantly, the firm will experience
difficulty raising short term funds, and will often need to cease revenue
generating activities and sell illiquid assets well below their potential
value. We now introduce failure costs. As before, $\bar{v}_{i}$ is market
value without failure costs, as determined in (5.17), while $v_{i}$ will
represent market value in the presence of failure costs. Failure costs for
firm $i$ are modeled as a threshold function

$f(v_{i})=\beta\mathbbm{1}\\{v_{i}<\theta\bar{v}_{i}\\}\qquad(i=1,\ldots,n),$

where $\theta\in(0,1)$ and $\beta>0$ are parameters. Thus, costs are zero when
$v_{i}$ is large and $-\beta$ when they fall below the threshold
$\theta\bar{v}_{i}$. In particular, a discrete failure cost of $-\beta$ is
incurred when firm value falls far enough below the no-failure market value
$\bar{v}_{i}$. The larger is $\theta$, more prone firms are to failure. The
book value of firm $i$ without failure costs was defined in (5.15). The book
value of firm $i$ in the presence of failure costs is defined as

$b_{i}=e_{i}+\sum_{j}c_{ij}b_{j}-f(v_{i}).$

Written in vector form, with $f$ applied pointwise to the vector $v$, we get
$b=e+Cb-f(v)$. Solving for $b$ gives $b=(I-C)^{-1}(e-f(v))$. The corresponding
market value is

$v=Rb=A(e-f(v)).$ (5.18)

Notice that, when no firms fail, we have $v_{i}=\bar{v}_{i}$, as expected.

######  5.2.3.3 Equilibria

Equation (5.18) is a nonlinear equation in $n$ unknowns. A vector
$v\in\mathbbm{R}^{n}$ solves (5.18) if and only if it is a fixed point of the
operator $T\colon\mathbbm{R}^{n}\to\mathbbm{R}^{n}$ defined by

$Tv=A(e-f(v)).$ (5.19)

In what follows we set $d:=A(e-\beta\mathbbm{1})$ and $S:=[d,\bar{v}]$.

######  Proposition 5.2.3.

$T$ is a self-map on $S$ with least fixed point $v^{*}$ and greatest fixed
point $v^{**}$ in $S$. Moreover,

  1. (i)

the sequence $(T^{k}d)_{k\in\mathbbm{N}}$ converges up to $v^{*}$ in a finite
number of steps and

  2. (ii)

the sequence $(T^{k}\bar{v})_{k\in\mathbbm{N}}$ converges down to $v^{**}$ in
a finite number of steps.

Note that $v^{*}=v^{**}$ is a possibility, in which case $T$ has a unique
fixed point in $S$. Prove the first claim in Proposition 5.2.3. Observe that
$v_{i}\leqslant v^{\prime}_{i}$ implies $f(v_{i})\geqslant f(v^{\prime}_{i})$.
As a result, the vector-valued map $v\mapsto-f(v)$ is order-preserving, and
hence so is $T$. Moreover, for $v\in[d,\bar{v}]$, we have

$d=A(e-\beta\mathbbm{1})\leqslant Tv:=A(e-f(v))\leqslant Ae=\bar{v},$

so $T$ is a self-map on $[d,\bar{v}]$. It follows directly from Theorem 5.1.5
that $T$ has a least and greatest fixed point in $S$. Why does
$(T^{k}d)_{k\in\mathbbm{N}}$ converge up to $v^{*}$ in a finite number of
steps? First, as you saw in the solution to Exercise 5.2.3.3, the map $T$ is
an order-preserving self-map on $[d,\bar{v}]$, so $Td\in[d,\bar{v}]$. In
particular, $d\leqslant Td$. Iterating on this inequality and using the order-
preserving property gives $d\leqslant Td\leqslant T^{2}d\leqslant\cdots$, so
$(T^{k}d)$ is indeed increasing. Moreover, the range of $T$ is a finite set,
corresponding to all vectors of the form

$u=A(e-\beta w),$

where $w$ is an $n$-vector containing only zeros and ones. Finiteness holds
because there are only finitely many binary sequences of length $n$. Given the
above facts, prove that $(T^{k}d)_{k\in\mathbbm{N}}$ converges up to $v^{*}$
in a finite number of steps. First, $v_{k}:=T^{k}d$ is increasing, as just
discussed. Second, this sequence can take only finitely many values, since $T$
has finite range. As $(v_{k})$ is increasing, it cannot cycle, so it must
converge in finitely many steps. Let $v^{\prime}$ be this limiting value and
let $K$ be the number of steps required for $(v_{k})$ to attain $v^{\prime}$.
Since $v_{k}=v^{\prime}$ for all $k\geqslant K$, we have

$Tv^{\prime}=TT^{K}v^{\prime}=T^{K+1}v^{\prime}=v^{\prime},$

so $v^{\prime}$ is a fixed point of $T$ in $S$. Moreover, if
$v^{\prime\prime}$ is any other fixed point of $T$ in $S$, then $d\leqslant
v^{\prime\prime}$ and hence, by the order-preserving property,
$v_{k}=T^{k}d\leqslant T^{k}v^{\prime\prime}=v^{\prime\prime}$ for all $k$.
Hence $v^{\prime}\leqslant v^{\prime\prime}$. Thus, $v^{\prime}$ is the least
fixed point of $T$. Similar logic can be applied to prove that
$(T^{k}\bar{v})_{k\in\mathbbm{N}}$ converges down to $v^{**}$ in a finite
number of steps. If we set $v^{0}=\bar{v}$ and $v^{k+1}=Tv^{k}$, we can
consider the sequence of valuations $(v^{k})$ as a dynamic process, and the
number of currently failing firms
$m^{k}:=\sum_{i}\mathbbm{1}\\{v^{k}_{i}<\theta\\}$ can be understood as
tracking waves of bankruptcies. Failures of firms in the first wave put stress
on otherwise healthy firms that have exposure to the failed firms, which in
turn causes further failures and so on. Prove that the sequence $(m_{k})$ is
monotone increasing. As discussed in Proposition 5.2.3, the sequence
$(v^{k})$, which can also be written as $(T^{k}\bar{v})$, is decreasing
pointwise. In other words, the value of each firm is non-increasing. Hence, if
$v^{k}_{i}<\theta$ for some $k$, then $v^{k+j}_{i}<\theta$ for all $j\geqslant
0$. Figure 5.1 illustrates a growing wave of failures that can arise in a
financial network. Firms with lighter colors have better balance sheets. Black
firms have failed. The code for generating this figure, along with details on
parameters, can be found in the code book.

Figure 5.1:  Waves of bankruptcies in a financial network

####  5.3 Chapter Notes

Shin, (2010) gives an excellent overview of systemic risk and the financial
crisis of 2007–2008. Battiston et al., (2012) study connectedness in financial
networks and introduce a measure of systemic impact called DebtRank. Bardoscia
et al., (2015) provide a dynamic theory of instability related to DebtRank.
Demange, (2018) provides a threat index for contagion in financial networks
related to Katz centrality. Bardoscia et al., (2019) analyze risks associated
with solvency contagion during crises. Jackson and Pernoud, (2019) study
investment in risky portfolios by banks in financial networks with debt and
equity interdependencies. Jackson and Pernoud, (2020) analyze optimal bailouts
in financial networks. Amini and Minca, (2020) offer an introduction to
modeling of clearing systems, analyzing equilibria for network payments and
asset prices. Jackson and Pernoud, (2021) provide a survey of the relationship
between financial networks and systemic risk. The setting in §5.2.2.3 was
investigated by Eisenberg and Noe, (2001), one of the first papers on a
network approach to default cascades. Additional details on stability
properties can be found in Stachurski, 2022b . As already mentioned, §5.2.3 is
based on (Elliott et al.,, 2014), which also includes an interesting
discussion of how the level of integration across a network affects
equilibria. Klages-Mundt and Minca, (2021) discuss optimal intervention in
economic networks via influence maximization methods, using Elliott et al.,
(2014) as an example. Acemoglu et al., 2021b  study how anticipation of future
defaults can result in “credit freezes." A general discussion of contraction
maps and related fixed point theory can be found in Goebel and Kirk, (1990)
and Cheney, (2013). For more on fixed point methods for order preserving
operators, see, for example, Guo et al., (2004), Zhang, (2012), Marinacci and
Montrucchio, (2019) or Deplano et al., (2020),

##  Part I Appendices

###  Chapter 6 Appendix

####  6.1 Math Review

This section provides a brief review of basic analysis and linear algebra. The
material contained here should be covered in intermediate mathematical
economics courses or, if not, in math boot camp at the very start of a
graduate program. (For those who want a slower treatment of the analysis
section, we recommend Bartle and Sherbert, (2011), which is carefully
constructed and beautifully written. High quality texts on linear algebra at
the right level for this course include Jänich, (1994), Meyer, (2000),
Aggarwal, (2020) and Cohen, (2021).)

#####  6.1.1 Sets and Functions

As a first step, let’s clarify elementary terminology and notation.

######  6.1.1.1 Sets

A set is an arbitrary collection of objects. Individual objects are called
elements of the set. We assume the reader is familiar with basic set
operations such as intersections and unions. If $A$ is a finite set, then
$|A|$ is the number of elements in $A$. Powers applied to sets indicate
Cartesian products, so that

$A^{2}:=A\times A:=\\{(a,a^{\prime}):a\in A,\;a^{\prime}\in
A\\},\;\;\text{etc.}$

Throughout, $\wp(A)$ is the power set of $A$, consisting of all subsets of
$A$. For example,

$A=\\{1,2\\}\quad\implies\quad\wp(A)=\\{\emptyset,\\{1\\},\\{2\\},A\\}.$

Let $\mathbbm{N}$ be the natural numbers, $\mathbbm{Z}$ be the integers,
$\mathbbm{Q}$ be the rational numbers and $\mathbbm{R}$ be the reals (i.e.,
the union of the rational and irrational numbers). For $x,y$ in $\mathbbm{R}$,
we let

$x\vee y:=\max\\{x,y\\}\quad\text{and}\quad x\wedge y:=\min\\{x,y\\}.$ (6.1)

Absolute value is $|x|:=x\vee(-x)$. For $n\in\mathbbm{N}$ we set
$[n]:=\\{1,\ldots,n\\}$. We make use of the following elementary facts: For
all $a,b,c\in\mathbbm{R}$,

  * •

$|a+b|\leqslant|a|+|b|$.

  * •

$(a\wedge b)+c=(a+c)\wedge(b+c)$ and $(a\vee b)+c=(a+c)\vee(b+c)$.

  * •

$(a\vee b)\wedge c=(a\wedge c)\vee(b\wedge c)$ and $(a\wedge b)\vee c=(a\vee
c)\wedge(b\vee c)$.

  * •

$|a\wedge c-b\wedge c|\leqslant|a-b|$.

  * •

$|a\vee c-b\vee c|\leqslant|a-b|$.

The first item is called the triangle inequality. Also, if
$a,b\in\mathbbm{R}_{+}$ and $c\in\mathbbm{R}$, then

$(a+b)\wedge c\leqslant(a\wedge c)+(b\wedge c).$ (6.2)

Prove: If $a,b\in\mathbbm{R}_{+}$ and $c\in\mathbbm{R}$, then $|a\wedge
c-b\wedge c|\leqslant|a-b|\wedge c$. Fix $a,b\in\mathbbm{R}_{+}$ and
$c\in\mathbbm{R}$. By (6.2), we have

$a\wedge c=(a-b+b)\wedge c\leqslant(|a-b|+b)\wedge
c\leqslant|a-b|\wedge+b\wedge c.$

Thus, $a\wedge c-b\wedge c\leqslant|a-b|\wedge c$. Reversing the roles of $a$
and $b$ gives $b\wedge c-a\wedge c\leqslant|a-b|\wedge c$. This proves the
claim in Exercise 6.1.1.1.

######  6.1.1.2 Equivalence Classes

Let $S$ be any set. A relation $\sim$ on $S$ is a nonempty subset of $S\times
S$. It is customary to write $x\sim y$ rather than $(x,y)\in\,\sim$ to
indicate that $(x,y)$ is in $\sim$. A relation $\sim$ on $S$ is called an
equivalence relation if, for all $x,y,z\in S$, we have

  * (reflexivity) $x\sim x$,

  * (symmetry) $x\sim y$ implies $y\sim x$ and

  * (transitivity) $x\sim y$ and $y\sim z$ implies $x\sim z$.

Any equivalence relation on $S$ induces a partition of $S$ into a collection
of mutually disjoint subsets such that their union exhausts $S$. These subsets
are called equivalence classes. They can be constructed by taking, for each
$x\in S$, the set of all elements that are equivalent to $x$.

######  Example 6.1.1.

Let $S$ be the set of all people in the world. If $x\sim y$ indicates that $x$
and $y$ live in the same country, then $\sim$ is an equivalence relation.
(Check the axioms.) The equivalence classes are the population of each
country. The partition induced on $S$ is the set of these classes, which we
can identify with the set of all countries in the world.

######  6.1.1.3 Functions

A function $f$ from set $A$ to set $B$ is a rule, written $f\colon A\to B$ or
$a\mapsto f(a)$, that associates each element $a$ of $A$ with one and only one
element $f(a)$ of $B$. The set $A$ is called the domain of $f$ and $B$ is
called the codomain. The range or image of $f$ is

$\operatorname{range}(f):=\\{b\in B:b=f(a)\text{ for some }a\in A\\}.$

A function $f\colon A\to B$ is called

  * •

one-to-one if $f(a)=f(a^{\prime})$ implies $a=a^{\prime}$,

  * •

onto if $\operatorname{range}(f)=B$, and

  * •

a bijection or one-to-one correspondence if $f$ is both onto and one-to-one.

######  Example 6.1.2.

If $S$ is a nonempty set, then the identity map on $S$ is the map $I\colon
S\to S$ such that $I(x)=x$ for all $x\in S$. The identity map is a bijection
for any choice of $S$.

The left panel of Figure 6.1 shows a one-to-one function on $(0,1)$. This
function is not onto, however. For example, there exists no $x\in(0,1)$ with
$f(x)=1/4$. The right panel of Figure 6.1 shows an onto function, with
$\operatorname{range}(f)=(0,1)$. This function is not one-to-one, however. For
example, $f(1/4)=f(3/4)=3/4$.

Figure 6.1:  Different types of functions on $(0,1)$

The left panel of Figure 6.2 gives an example of a function which is neither
one-to-one nor onto. The right panel of Figure 6.2 gives an example of a
bijection.

Figure 6.2:  Some functions are bijections and some are not

######  6.1.1.4 Inverse Functions

One motivation for our interest in the basic properties of functions is that
we wish to solve inverse problems. For an arbitrary nonempty set $S$ and a
function $f\colon S\to S$, an abstraction of an inverse problem is solving
$y=f(x)$ for $x\in S$. Prior to stating the next result, we recall that an
inverse function for $f\colon S\to S$ is a function $g\colon S\to S$ such that
$f\circ g=g\circ f=I$, where $I$ is the identity map on $S$. The inverse
function of $f$ is often written as $f^{-1}$.

######  Lemma 6.1.1.

For $f\colon S\to S$, the following statements are equivalent:

  1. (i)

$f$ is a bijection on $S$.

  2. (ii)

For each $y\in S$, there exists a unique $x\in S$ such that $f(x)=y$.

  3. (iii)

$f$ has an inverse on $S$.

###### Proof.

((i) $\implies$ (ii)) Fix $y\in S$. Since $f$ is onto, there exists an $x\in
S$ such that $f(x)=y$. Since $f$ is one-to-one, there is at most one such $x$.
((ii) $\implies$ (iii)) Let $g\colon S\to S$ map each $y\in S$ into the unique
$x\in S$ such that $f(x)=y$. By the definition of $g$, for fixed $x\in S$, we
have $g(f(x))=x$. Moreover, for each $y\in S$, the point $g(y)$ is the point
that $f$ maps to $y$, so $f(g(y))=y$. ((iii) $\implies$ (i)) Let $g$ be the
inverse of $f$. To see that $f$ must be onto, pick any $y\in S$. Since $f\circ
g$ is the identity, we have $f(g(y))=y$. Hence there exists a point $g(y)$ in
$S$ that is mapped into $y\in S$. To see that $f$ is one-to-one, fix $x,y\in
S$. If $f(x)=f(y)$, then $g(f(x))=g(f(y))$. But $g\circ f$ is the identity, so
$x=y$. ∎

Here is a nice logical exercise that turns out to be useful when we solve
linear inverse problems. Let $S$ and $T$ be nonempty sets. For $f\colon S\to
T$, a function $g\colon T\to S$ is called a left inverse of $f$ if $g\circ
f=I$, where $I$ is the identity on $S$. Prove that $f$ is one-to-one if and
only if $f$ has a left inverse. Suppose first that $f$ is one-to-one. We
construct a left inverse $g$ as follows. For $y\in\operatorname{range}(f)$,
let $g(y)$ be the unique $x$ such that $f(x)=y$. (Uniqueness is by the one-to-
one property.) For $y\notin\operatorname{range}(f)$, let $g(y)=\bar{x}$, where
$\bar{x}$ is any point in $S$. The function $g$ is a left inverse of $f$
because, for any $x\in S$, the point $y=f(x)$ is in $\operatorname{range}(f)$,
and $g(y)=x$. Hence $g(f(x))=x$. Suppose next that $f$ has a left inverse $g$.
Suppose further that $x$ and $x^{\prime}$ are points in $S$ with
$f(x)=f(x^{\prime})$. Then $g(f(x))=g(f(x^{\prime}))$. Since $g$ is a left
inverse, this yields $x=x^{\prime}$. Hence $f$ is one-to-one.

######  6.1.1.5 Real-Valued Functions

If $S$ is any set and $f\colon S\to\mathbbm{R}$, we call $f$ a real-valued
function. The set of all real-valued functions on $S$ is denoted
$\mathbbm{R}^{S}$. When $S$ has $n$ elements, $\mathbbm{R}^{S}$ is the same
set as $\mathbbm{R}^{n}$ expressed in different notation. The next lemma
clarifies.

######  Lemma 6.1.2.

If $|S|=n$, then

$\mathbbm{R}^{S}\;\ni\;h=(h(x_{1}),\ldots,h(x_{n}))\quad\longleftrightarrow\quad\begin{pmatrix}h_{1}\\\
\vdots\\\ h_{n}\end{pmatrix}\;\in\;\mathbbm{R}^{n}$ (6.3)

is a one-to-one correspondence between $\mathbbm{R}^{n}$ and the function
space $\mathbbm{R}^{S}$.

The lemma just states that a function $h$ can be identified by the set of
values that it takes on $S$, which is an $n$-tuple of real numbers. We use
this identification routinely in what follows. The indicator function of
logical statement $P$ is denoted $\mathbbm{1}\\{P\\}$ and takes value 1
(resp., 0) if $P$ is true (resp., false).

######  Example 6.1.3.

If $x,y\in\mathbbm{R}$, then

$\mathbbm{1}\\{x\leqslant y\\}=\begin{cases}1&\text{ if }x\leqslant y\\\
0&\text{ otherwise}.\end{cases}$

If $A\subset S$, where $S$ is any set, then
$\mathbbm{1}_{A}(x):=\mathbbm{1}\\{x\in A\\}$ for all $x\in S$. A nonempty set
$S$ is called countable if it is finite or can be placed in one-to-one
correspondence with the natural numbers $\mathbbm{N}$. In the second case we
can enumerate $S$ by writing it as $\\{x_{1},x_{2},\ldots\\}$. Any nonempty
set $S$ that fails to be countable is called uncountable. For example,
$\mathbbm{Z}$ and $\mathbbm{Q}$ are countable, whereas $\mathbbm{R}$ and every
nontrivial interval in $\mathbbm{R}$ are uncountable. In general, if $f$ and
$g$ are real-valued functions defined on some common set $S$ and $\alpha$ is a
scalar, then $f+g$, $\alpha f$, $fg$, etc., are functions on $S$ defined by

$(f+g)(x)=f(x)+g(x),\quad(\alpha f)(x)=\alpha f(x),\quad\text{etc.}$ (6.4)

for each $x\in S$. Similarly, $f\vee g$ and $f\wedge g$ are functions on $S$
defined by

$(f\vee g)(x)=f(x)\vee g(x)\;\;\text{ and }\;\;(f\wedge g)(x)=f(x)\wedge
g(x).$ (6.5)

Figure 6.3 illustrates.

$f$$g$$f\vee g$$f\wedge g$ Figure 6.3:  Functions $f\vee g$ and $f\wedge g$
when defined on a subset of $\mathbbm{R}$

If $f\colon A\to B$ and $g\colon B\to C$, then $g\circ f$ is called the
composition of $f$ and $g$. It is the function mapping $a\in A$ to $g(f(a))\in
C$.

######  6.1.1.6 Fixed Points

Let $S$ be any set. A self-map on $S$ is a function $G$ from $S$ to itself.
When working with self-maps in arbitrary sets it is common to write the image
of $x$ under $G$ as $Gx$ rather than $G(x)$. We often follow this convention.
Given a self-map $G$ on $S$, a point $x\in S$ is called a fixed point of $G$
if $Gx=x$.

######  Example 6.1.4.

Every point of arbitrary $S$ is fixed under the identity map $I\colon x\mapsto
x$.

######  Example 6.1.5.

If $S=\mathbbm{N}$ and $Gx=x+1$, then $G$ has no fixed point.

Figure 6.4 shows another example, for a self-map $G$ on $S=[0,2]$. Fixed
points are numbers $x\in[0,2]$ where $G$ meets the 45 degree line. In this
case there are three. One of the most common techniques for solving systems of
nonlinear equations in applied mathematics—and quantitative economics—is to
convert them into fixed point problems and then apply fixed point theory. We
will see many applications of this technique.

Figure 6.4:  Graph and fixed points of $G\colon x\mapsto 2.125/(1+x^{-4})$

Let $S$ be any set and let $G$ be a self-map on $S$. Suppose there exists an
$\bar{x}\in S$ and an $m\in\mathbbm{N}$ such that $G^{k}x=\bar{x}$ for all
$x\in S$ and $k\geqslant m$. Prove that, under this condition, $\bar{x}$ is
the unique fixed point of $G$ in $S$. Let $G$ and $S$ be as stated in the
exercise. Regarding uniqueness, suppose that $G$ has two distinct fixed points
$x$ and $y$ in $S$. Since $G^{m}x=\bar{x}$ and $G^{m}y=\bar{x}$, we have
$G^{m}x=G^{m}y$. But $x$ and $y$ are distinct fixed points, so $x=G^{m}x$ must
be distinct from $y=G^{m}y$. Contradiction. Regarding the claim that $\bar{x}$
is a fixed point, we recall that $G^{k}x=\bar{x}$ for $k\geqslant m$. Hence
$G^{m}\bar{x}=\bar{x}$ and $G^{m+1}\bar{x}=\bar{x}$. But then

$G\bar{x}=GG^{m}\bar{x}=G^{m+1}\bar{x}=\bar{x},$

so $\bar{x}$ is a fixed point of $G$.

######  6.1.1.7 Vectors

An $n$-vector $x$ is a tuple of $n$ numbers $x=(x_{1},\ldots,x_{n})$ where
$x_{i}\in\mathbbm{R}$ for each $i\in[n]$. In general, $x$ is neither a row
vector nor a column vector—which coincides with the perspective of most
scientific computing environments, where the basic vector structure is a flat
array. When using matrix algebra, vectors are treated as column vectors unless
otherwise stated. The two most fundamental vector operations are vector
addition and scalar multiplication. These operations act pointwise, so that,
when $\alpha\in\mathbbm{R}$ and $x,y\in\mathbbm{R}^{n}$,

$x+y=\left(\begin{array}[]{c}x_{1}\\\ x_{2}\\\ \vdots\\\
x_{n}\end{array}\right)+\left(\begin{array}[]{c}y_{1}\\\ y_{2}\\\ \vdots\\\
y_{n}\end{array}\right):=\left(\begin{array}[]{c}x_{1}+y_{1}\\\ x_{2}+y_{2}\\\
\vdots\\\ x_{n}+y_{n}\end{array}\right)\quad\text{and}\quad\alpha
x:=\left(\begin{array}[]{c}\alpha x_{1}\\\ \alpha x_{2}\\\ \vdots\\\ \alpha
x_{n}\end{array}\right).$

We let $\mathbbm{R}^{n}$ be the set of all $n$-vectors and
$\mathbbm{M}^{n\times k}$ be all $n\times k$ matrices. If $A$ is a matrix then
$A^{\top}$ is its transpose.

  * •

The inner product of $x,y\in\mathbbm{R}^{n}$ is defined as
$\left\langle{x,y}\right\rangle:=\sum_{i=1}^{n}x_{i}y_{i}$.

  * •

The Euclidean norm of $x\in\mathbbm{R}^{n}$ is
$\|x\|:=\sqrt{\left\langle{x,x}\right\rangle}$.

The norm and inner product satisfy the triangle inequality and Cauchy–Schwarz
inequality, which state that, respectively,

$\|x+y\|\leqslant\|x\|+\|y\|\quad\text{and}\quad|\left\langle{x,y}\right\rangle|\leqslant\|x\|\|y\|\quad\text{for
all }x,y\in\mathbbm{R}^{n}.$

######  6.1.1.8 Complex Numbers

We recall some elementary facts about $\mathbbm{C}$, the set of complex
numbers. Each element of $\mathbbm{C}$ can be understood as a point
$(a,b)\in\mathbbm{R}^{2}$. In fact $\mathbbm{C}$ is just $\mathbbm{R}^{2}$
endowed with a special form of multiplication. The point $(a,b)$ is more often
written as $a+ib$. We elaborate below. The first and second projections of
$(a,b)$ are written as $\operatorname{Re}(a,b)=a$ and
$\operatorname{Im}(a,b)=b$ and called the real and nonreal (or imaginary) part
respectively. The symbol $i$ represents the point $(0,1)\in\mathbbm{C}$. As is
traditional, in the context of complex numbers, the complex number
$(a,0)\in\mathbbm{C}$ is often written more simply as $a$. With addition and
scalar multiplication defined pointwise, this means that, as expected,

$(a,b)=(a,0)+(0,b)=(a,0)+(0,1)b=a+ib.$

Let $z=(a,b)$. The modulus of $z$ is written $|z|$ and defined as the
Euclidean norm $(a^{2}+b^{2})^{1/2}$ of the tuple $(a,b)$. The two-dimensional
Euclidean space is then endowed with a new operation called multiplication,
which is defined by

$(a,b)(c,d)=(ac-bd,ad+bc).$ (6.6)

Note that, under this rule and our conventions, $i^{2}=(0,1)(0,1)=(-1,0)=-1$.
As in the real case, the exponential $\mathrm{e}^{z}$ is defined for
$z\in\mathbbm{C}$ by $\sum_{k\geqslant 0}z^{k}/(k!)$. It can be shown that,
under this extension, the exponential function continues to enjoy the additive
property $\mathrm{e}^{z_{1}+z_{2}}=\mathrm{e}^{z_{1}}\mathrm{e}^{z_{2}}$. As a
result, $\mathrm{e}^{a+ib}=\mathrm{e}^{a}\mathrm{e}^{ib}$. Rather than
providing its coordinates, another way to represent a vector
$z=(a,b)\in\mathbbm{R}^{2}$, and hence in $\mathbbm{C}$, is by providing a
pair $(r,\varphi)$ where $r>0$ is understood as the length of the vector and
$\varphi\in[0,2\pi)$ is the angle. This translates to Euclidean coordinates
via

$a+ib=(a,b)=(r\cos\varphi,r\sin\varphi)=r(\cos\varphi+i\sin\varphi).$

Figure 6.5:  The complex number $(a,b)=r\mathrm{e}^{i\varphi}$

The representation $(r,\varphi)$ is called the polar form of the complex
number. By Euler’s formula
$\cos(\varphi)+i\sin(\varphi)=\mathrm{e}^{i\varphi}$, we can also write

$r(\cos\varphi+i\sin\varphi)=r\mathrm{e}^{i\varphi}.$

Figure 6.5 translates $\mathbbm{C}\ni(1,\sqrt{3})=1+i\sqrt{3}$ into polar
coordinates $2\mathrm{e}^{i(\pi/3)}$. The advantage of these representations
is clear when we multiply, since the rule

$r\mathrm{e}^{i\varphi}\,s\mathrm{e}^{i\psi}=rs\,\mathrm{e}^{i(\varphi+\psi)}$
(6.7)

is easier to remember and apply than (6.6). Calculating the modulus is also
easy, since, by the trigonometric formula $\cos^{2}\varphi+\sin^{2}\varphi=1$,

$|r\mathrm{e}^{i\varphi}|=|r(\cos(\varphi)+i\sin(\varphi))|=r\left(\cos^{2}\varphi+\sin^{2}\varphi\right)^{1/2}=r.$
(6.8)

Show that, for any $u,v\in\mathbbm{C}$ we have $|uv|=|u||v|$. In polar form,
we have $u=r\mathrm{e}^{i\varphi}$ and $v=s\mathrm{e}^{i\psi}$, so
$uv=rs\,\mathrm{e}^{i(\varphi+\psi)}$. Hence $|uv|=rs$ (see (6.8)), which is
equal to $|u||v|$.

#####  6.1.2 Order

Order structure is of great importance in economics—typically more so than
other fields such as physics or chemistry. Here we review the basics.

######  6.1.2.1 Partial Orders

It was mentioned in the preface that order-theoretic methods form a core part
of the text. In this section we introduce some key concepts. Let $P$ be a
nonempty set. A partial order on $P$ is a relation $\preceq$ on $P\times P$
satisfying, for any $p,q,r$ in $P$,

  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)

  6. (transitivity)

When paired with a partial order $\preceq$, the set $P$ (or the pair
$(P,\preceq)$) is called a partially ordered set.

######  Example 6.1.6.

The usual order $\leqslant$ on $\mathbbm{R}$ is a partial order on
$\mathbbm{R}$. Unlike other partial orders we consider, it has the additional
property that either $x\leqslant y$ or $y\leqslant x$ for every $x,y$ in
$\mathbbm{R}$. For this reason, $\leqslant$ is also called a total order on
$\mathbbm{R}$.

Let $P$ be any set and consider the relation induced by equality, so that
$p\preceq q$ if and only if $p=q$. Show that this relation is a partial order
on $P$. Let $M$ be any set. Show that $\subset$ is a partial order on
$\wp(M)$, the set of all subsets of $M$.

######  Example 6.1.7 (Pointwise order over functions).

Let $S$ be any set. For $f,g$ in $\mathbbm{R}^{S}$, we write

$f\leqslant g\text{ if }f(x)\leqslant g(x)\text{ for all }x\in S.$

This relation $\leqslant$ on $\mathbbm{R}^{S}$ is a partial order called the
pointwise order on $\mathbbm{R}^{S}$.

A subset $B$ of a partially ordered set $(P,\preceq)$ is called

  * •

increasing if $x\in B$ and $x\preceq y$ implies $y\in B$.

  * •

decreasing if $x\in B$ and $y\preceq x$ implies $y\in B$.

Describe the set of increasing sets in $(\mathbbm{R},\leqslant)$.

######  Example 6.1.8 (Pointwise order over vectors).

For vectors $x=(x_{1},\ldots,x_{d})$ and $y=(y_{1},\ldots,y_{d})$, we write

  * •

$x\leqslant y$ if $x_{i}\leqslant y_{i}$ for all $i\in[d]$ and

  * •

$x\ll y$ if $x_{i}<y_{i}$ for all $i\in[d]$.

The statements $x\geqslant y$ and $x\gg y$ are defined analogously.111The
notation $x\leqslant y$ over vectors is standard, while $x\ll y$ is less so.
In some fields, $n\ll k$ is used as an abbreviation for “$n$ is much smaller
than $k$.” Our usage lines up with most of the literature on partially ordered
vector spaces. See, e.g., Zhang, (2012). The relation $\leqslant$ is a partial
order on $\mathbbm{R}^{n}$, also called the pointwise order. (In fact, the
present example is a special case of Example 6.1.7 under the identification in
Lemma 6.1.2 (page 6.1.2).) On the other hand, $\ll$ is not a partial order on
$\mathbbm{R}^{n}$. (Which axiom fails?)

Recall from Example 6.1.11 that limits in $\mathbbm{R}$ preserve weak
inequalities. Prove that the same is true in $\mathbbm{R}^{d}$. In particular,
show that, for vectors $a,b\in\mathbbm{R}^{d}$ and sequence $(x_{n})$ in
$\mathbbm{R}^{d}$, we have $a\leqslant x_{n}\leqslant b$ for all
$n\in\mathbbm{N}$ and $x_{n}\to x$ implies $a\leqslant x\leqslant b$.

######  6.1.2.2 Pointwise Operations on Vectors

In this text, operations on real numbers such as $|\cdot|$ and $\vee$ are
applied to vectors pointwise. For example, for vectors $a=(a_{i})$ and
$b=(b_{i})$ in $\mathbbm{R}^{d}$, we set

$|a|=(|a_{i}|),\quad a\wedge b=(a_{i}\wedge b_{i})\quad\text{and}\quad a\vee
b=(a_{i}\vee b_{i})$

(The last two are special cases of (6.5).) A small amount of thought will
convince you that, with this convention plus the pointwise order over vectors,
the order-theoretic inequalities and identities listed in §6.1.1.1 also hold
for vectors in $\mathbbm{R}^{d}$. (For example, $|a+b|\leqslant|a|+|b|$ for
any $a,b,c\in\mathbbm{R}^{d}$.) Prove: If $B$ is $m\times k$ and $B\geqslant
0$, then $|Bx|\leqslant B|x|$ for all $k\times 1$ column vectors $x$. Fix
$B\in\mathbbm{M}^{m\times k}$ with $b_{ij}\geqslant 0$ for all $i,j$. Pick any
$i\in[m]$ and $x\in\mathbbm{R}^{k}$. By the triangle inequality, we have
$|\sum_{j}b_{ij}x_{j}|\leqslant\sum_{j}b_{ij}|x_{j}|$. Stacking these
inequalities yields $|Bx|\leqslant B|x|$, as was to be shown.

######  6.1.2.3 Monotonicity

Given two partially ordered sets $(P,\preceq)$ and $(Q,\trianglelefteq)$, a
function $G$ from $P$ to $Q$ is called order-preserving if

$p,q\in P\text{ and }p\preceq q\quad\implies\quad Gp\trianglelefteq Gq.$ (6.9)

######  Example 6.1.9.

Let $\mathscr{C}$ be all continuous functions from $S=[a,b]$ to $\mathbbm{R}$
and let $\leqslant$ be the pointwise partial order on $\mathscr{C}$. Define

$I\colon\mathscr{C}\ni f\to\int_{a}^{b}f(x)dx\in\mathbbm{R}.$

Since $f\leqslant g$ implies $\int_{a}^{b}f(x)dx\leqslant\int_{a}^{b}g(x)dx$,
the integral map $I$ is order-preserving on $\mathscr{C}$.

Let $X$ be a random variable mapping $\Omega$ to finite $S$. Define
$\ell\colon\mathbbm{R}^{S}\to\mathbbm{R}$ by $\ell h=\mathbbm{E}h(X)$. Show
that $\ell$ is order-preserving when $\mathbbm{R}^{S}$ has the pointwise
order. If $P=Q=\mathbbm{R}$ and $\preceq$ and $\trianglelefteq$ are both equal
to $\leqslant$, the standard order on $\mathbbm{R}$, then the order-preserving
property reduces to the usual notion of an increasing function (i.e.,
nondecreasing function), and we will use the terms “increasing” and “order-
preserving” interchangeably in this setting.222Other common terms for order-
preserving in the literature include “monotone increasing,” “monotone” and
“isotone.” In addition, if $S=g$ maps $A\subset\mathbbm{R}$ into
$\mathbbm{R}$, then we will call $g$

  * •

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

  * •

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

#####  6.1.3 Convergence

Let’s now recall the basics of convergence and continuity. Given any set $S$,
an $S$-valued sequence $(x_{n}):=(x_{n})_{n\in\mathbbm{N}}$ is a function
$n\mapsto x_{n}$ from $\mathbbm{N}$ to $S$. If $S=\mathbbm{R}$, we call
$(x_{n})$ a real-valued sequence. A subsequence of $(x_{n})_{n\in\mathbbm{N}}$
is a sequence of the form $(x_{\sigma(n)})_{n\in\mathbbm{N}}$ where $\sigma$
is a strictly increasing function from $\mathbbm{N}$ to itself. You can think
of forming a subsequence from a sequence by deleting some of its
elements—while still retaining infinitely many. In computer science and
statistics, it is common to classify sequences according to their asymptotic
behavior. Often this is done via big O notation, where, for a real-valued
sequence $(x_{n})$, we write $(x_{n})=O(g_{n})$ if there exists a nonnegative
sequence $(g_{n})$ and a constant $M<\infty$ such that $|x_{n}|\leqslant
Mg_{n}$ for all $n\in\mathbbm{N}$. Let $x_{n}=-5n+n^{2}$ for all
$n\in\mathbbm{N}$. Show that $(x_{n})=O(n^{2})$ holds but $(x_{n})=O(n)$
fails. Let $x_{n}=-5n+n^{2}$. Then $|x_{n}|\leqslant 5n+n^{2}\leqslant
6n^{2}$. Hence $(x_{n})=O(n^{2})$. Regarding the second claim, suppose to the
contrary that $(x_{n})=O(n)$. Then we can take an $M$ such that
$|x_{n}|\leqslant Mn$ for all $n\in\mathbbm{N}$. But then
$x_{n}=-5n+n^{2}\leqslant Mn$ for all $n$. Dividing by $n$ yields $n\leqslant
5+M$ for all $n$. Contradiction.

######  6.1.3.1 Metric Properties of the Real Line

The following definition is fundamental to what follows: a real-valued
sequence $(x_{n})$ converges to $x\in\mathbbm{R}$ and write $x_{n}\to x$ if

for each $\varepsilon>0$, there is an $N\in\mathbbm{N}$ such that
$|x_{n}-x|<\varepsilon$ whenever $n\geqslant N$.

######  Example 6.1.10.

If $x_{n}=1-1/n$, then $x_{n}\to 1$. Indeed, for any $\varepsilon>0$, the
statement $|x_{n}-1|<\varepsilon$ is equivalent to $n>1/\varepsilon$. This
clearly holds whenever $n$ is sufficiently large.

Prove: If $a,b\in\mathbbm{R}$, $x_{n}\to a$ and $x_{n}\to b$, then $a=b$.
Let’s state some elementary limit laws that are used without comment
throughout. (You can review the proofs in sources such as Bartle and Sherbert,
(2011)). A sequence $(x_{n})$ is called bounded if there is an
$M\in\mathbbm{R}$ such that $|x_{n}|\leqslant M$ for all $n\in\mathbbm{N}$. It
is called

  * •

monotone increasing if $x_{n}\leqslant x_{n+1}$ for all $n\in\mathbbm{N}$, and

  * •

monotone decreasing if $x_{n}\geqslant x_{n+1}$ for all $n$.

The sequence is called monotone if it is either monotone increasing or
decreasing. The next theorem, concerning monotone sequences, is a deep result
about the structure of $\mathbbm{R}$.

######  Theorem 6.1.3.

A real-valued monotone sequence converges in $\mathbbm{R}$ if and only if it
is bounded.

The intuitive meaning of the “if” part of Theorem 6.1.3 is that monotone
bounded sequences always converge to some point in $\mathbbm{R}$ because
$\mathbbm{R}$ contains no gaps. This statement is closely related to the
“completeness” property of the real line, which is discussed in Bartle and
Sherbert, (2011) and many other texts on real analysis. Next let’s consider
series. Given a sequence $(x_{n})$ in $\mathbbm{R}$, we set

$\sum_{n\geqslant 1}x_{n}:=\lim_{N\to\infty}\sum_{n=1}^{N}x_{n}\text{ whenever
the limit exists in $\mathbbm{R}$}.$

More generally, given arbitrary countable $S$ and $g\in\mathbbm{R}^{S}$, we
write $\sum_{x\in S}g(x)=M$ if there exists an enumeration
$(x_{n})_{n\in\mathbbm{N}}$ of $S$ such that $\sum_{n\geqslant 1}|g(x_{n})|$
is finite and, in addition, $\sum_{n\geqslant 1}g(x_{n})=M$.333This definition
is not ambiguous because every possible enumeration leads to the same value
when the absolute sum is finite (see, e.g., the rearrangement theorem in
Bartle and Sherbert, (2011), §9.1). Show that, if $S$ is countable,
$g\in\mathbbm{R}^{S}$, and there exist $x^{\prime},x^{\prime\prime}\in S$ such
that $g(x^{\prime})>0$ and $g(x^{\prime\prime})<0$, then $\left|\sum_{x\in
S}g(x)\right|<\sum_{x\in S}|g(x)|$.444Hint: Start with the case $|S|=2$. Argue
that the case with $n$ elements follows from this case and the ordinary (weak)
triangle inequality $|\sum_{x\in S}g(x)|\leqslant\sum_{x\in S}|g(x)|$.

######  6.1.3.2 Metric Properties of Euclidean Space

Now we review the metric properties of $\mathbbm{R}^{d}$, for some
$d\in\mathbbm{N}$, when distance between vectors $x,y\in\mathbbm{R}^{d}$ is
understood in terms of Euclidean norm deviation $\|x-y\|$. The notion of
convergence for real-valued sequences extends naturally to this setting:
sequence $(x_{n})$ in $\mathbbm{R}^{d}$ is said to converge to
$x\in\mathbbm{R}^{d}$ if

for each $\varepsilon>0$, there is an $N\in\mathbbm{N}$ such that
$\|x_{n}-x\|<\varepsilon$ whenever $n\geqslant N$.

In this case we write $x_{n}\to x$. Figure 6.6 shows a sequence converging to
the origin in $\mathbbm{R}^{3}$, with colder colors being later in the
sequence.

Figure 6.6:  Convergence of a sequence to the origin in $\mathbbm{R}^{3}$

Prove that limits in $\mathbbm{R}^{d}$ are unique. In other words, show that,
if $(x_{n})$ is a sequence converging to $x\in\mathbbm{R}^{d}$ and
$y\in\mathbbm{R}^{d}$, then $x=y$. Given any point $u\in\mathbbm{R}^{d}$ and
$\varepsilon>0$, the $\varepsilon$-ball around $u$ is the set

$B_{\varepsilon}(u):=\\{v\in\mathbbm{R}^{d}:\|u-v\|<\varepsilon\\}.$

With this terminology, we can say that $(x_{n})$ converges to
$x\in\mathbbm{R}^{d}$ if the sequence $(x_{n})$ is eventually in any
$\varepsilon$-ball around $x$.

######  Proposition 6.1.4.

If $(x_{n})$ and $(y_{n})$ are sequences in $\mathbbm{R}^{d}$ with $x_{n}\to
x$ and $y_{n}\to y$, then

  1. (i)

$x_{n}+y_{n}\to x+y$ and $x_{n}y_{n}\to xy$

  2. (ii)

$x_{n}\leqslant y_{n}$ for all $n\in\mathbbm{N}$ implies $x\leqslant y$

  3. (iii)

$\alpha x_{n}\to\alpha x$ for any $\alpha\in\mathbbm{R}$

  4. (iv)

$x_{n}\vee y_{n}\to x\vee y$ and $x_{n}\wedge y_{n}\to x\wedge y$.

A sequence $(x_{n})\subset\mathbbm{R}^{d}$ is called Cauchy if, for all
$\varepsilon>0$, there exists an $N\in\mathbbm{N}$ with
$|x_{n}-x_{m}|<\varepsilon$ whenever $n,m\geqslant N$. Let $d=1$ and suppose
$x_{n}=1/n$. Prove that $(x_{n})$ is Cauchy. Prove that every convergent
sequence in $\mathbbm{R}^{d}$ is Cauchy. It is a fundamental result of
analysis, stemming from axiomatic properties of the reals, that the converse
is also true:

######  Theorem 6.1.5.

A sequence in $\mathbbm{R}^{d}$ converges to a point in $\mathbbm{R}^{d}$ if
and only if it is Cauchy.

######  6.1.3.3 Topology

A point $u\in A\subset\mathbbm{R}^{d}$ is called interior to $A$ if there
exists an $\varepsilon>0$ such that $B_{\varepsilon}(u)\subset A$. Let $d=1$
so that $\|x-y\|=|x-y|$. Show that $0.5$ is interior to $A:=[0,1)$ but $0$ is
not. Show that $\mathbbm{Q}$, the set of rational numbers in $\mathbbm{R}$,
contains no interior points. A subset $G$ of $\mathbbm{R}^{d}$ is called open
in $\mathbbm{R}^{d}$ if every $u\in G$ is interior to $G$. A subset $F$ of
$\mathbbm{R}^{d}$ is called closed if, given any sequence $(x_{n})$ satisfying
$x_{n}\in F$ for all $n\in\mathbbm{N}$ and $x_{n}\to x$ for some
$x\in\mathbbm{R}^{d}$, the point $x$ is in $F$. In other words, $F$ contains
the limit points of all convergent sequences that take values in $F$.

######  Example 6.1.11.

Limits in $\mathbbm{R}$ preserve orders, so $a\leqslant x_{n}\leqslant b$ for
all $n\in\mathbbm{N}$ and $x_{n}\to x$ implies $a\leqslant x\leqslant b$.
Thus, any closed interval $[a,b]$ in $\mathbbm{R}$ is closed in the standard
(one dimensional Euclidean) metric.

Prove that $G\subset\mathbbm{R}^{d}$ is open if and only if $G^{c}$ is closed.
A subset $B$ of $\mathbbm{R}^{d}$ is called bounded if there exists a finite
$M$ such that $\|b\|\leqslant M$ for all $b\in B$. A subset $K$ of
$\mathbbm{R}^{d}$ is called compact in $\mathbbm{R}^{d}$ if every sequence in
$K$ has a subsequence converging to some point in $K$. The Bolzano–Weierstrass
theorem tells us that $K$ is compact if and only if $K$ is closed and bounded.

######  6.1.3.4 Continuity in Vector Space

If $A\subset\mathbbm{R}^{d}$, then $f\colon A\to\mathbbm{R}^{k}$ is called
continuous at $x\in A$ if, for each sequence $(x_{n})\subset A$ with $x_{n}\to
x$, we have $f(x_{n})\to f(x)$ in $\mathbbm{R}^{k}$. If $f$ is continuous at
all $x\in A$ then we call $f$ continuous on $A$.

######  Example 6.1.12.

If $f(x)=x^{2}$ on $A=\mathbbm{R}$, then $f$ is continuous at all
$x\in\mathbbm{R}$ because, by Proposition 6.1.4, $x_{n}\to x$ implies
$x_{n}^{2}=x_{n}\cdot x_{n}\to x\cdot x=x^{2}$.

More generally, every polynomial function is continuous on $\mathbbm{R}$. The
elementary functions $\sin$, $\cos$, $\exp$ and $\log$ are all continuous on
their domains. Prove: If $\alpha,\beta\in\mathbbm{R}$ and $f,g$ are continuous
functions from $A\subset\mathbbm{R}^{d}$ to $\mathbbm{R}^{k}$, then so is
$\alpha f+\beta g$. If $x_{n}\to x$ in $\mathbbm{R}^{d}$ and $f$ and $g$ are
continuous, then $f(x_{n})\to f(x)$ and $g(x_{n})\to g(x)$ in
$\mathbbm{R}^{k}$. But then, by Proposition 6.1.4, $\alpha f(x_{n})+\beta
g(x_{n})$ converges to $\alpha f(x)+\beta g(x)$ in $\mathbbm{R}^{k}$, as was
to be shown. Fix $a\in\mathbbm{R}^{d}$. Prove that
$f,g\colon\mathbbm{R}^{d}\to\mathbbm{R}^{d}$ defined by $f(x)=x\wedge a$ and
$g(x)=x\vee a$ are both continuous functions on $\mathbbm{R}^{d}$. Here’s the
answer for $f$: Take $(x_{n})$ converging to $x$ in $\mathbbm{R}^{d}$.
Applying the inequalities in 6.1.1.1 pointwise to vectors, we have

$0\leqslant|f(x_{n})-f(x)|=|x_{n}\wedge a-x\wedge a|\leqslant|x_{n}-x|.$

Taking the Euclidean norm over these vectors and using $|u|\leqslant|v|$
implies $\|u\|\leqslant\|v\|$ yields $\|f(x_{n})-f(x)\|\leqslant\|x_{n}-x\|\to
0$. Similar arguments can be applied to $g$. The next lemma is helpful in
locating fixed points.

######  Lemma 6.1.6.

Let $F$ be a self-map on $S\subset\mathbbm{R}^{d}$. If $F^{m}u\to u^{*}$ as
$m\to\infty$ for some pair $u,u^{*}\in S$ and, in addition, $F$ is continuous
at $u^{*}$, then $u^{*}$ is a fixed point of $F$.

###### Proof.

Assume the hypotheses of Lemma 6.1.6 and let $u_{m}:=F^{m}u$ for all
$m\in\mathbbm{N}$. By continuity and $u_{m}\to u^{*}$ we have $Fu_{m}\to
Fu^{*}$. But the sequence $(Fu_{m})$ is just $(u_{m})$ with the first element
omitted, so, given that $u_{m}\to u^{*}$, we must have $Fu_{m}\to u^{*}$.
Since limits are unique, it follows that $u^{*}=Fu^{*}$. ∎

#####  6.1.4 Linear Algebra

Next we review fundamental concepts and definitions from linear algebra.

######  6.1.4.1 Subspaces and Independence

A subset $E$ of $\mathbbm{R}^{n}$ is called a linear subspace of
$\mathbbm{R}^{n}$ if

$x,y\in E\text{ and }\alpha,\beta\in\mathbbm{R}\;\implies\;\alpha x+\beta y\in
E.$

In other words, $E$ is closed under the operations of addition and scalar
multiplication; that is, (i) $\alpha\in\mathbbm{R}$ and $x\in E$ implies
$\alpha x\in E$ and (ii) $x,y\in E$ implies $x+y\in E$. Fix
$c\in\mathbbm{R}^{n}$ and $C\in\mathbbm{M}^{n\times k}$. Show that

  * •

$H:=\\{x\in\mathbbm{R}^{n}:\left\langle{c,x}\right\rangle=0\\}$ and

  * •

$\operatorname{range}C:=\\{y\in\mathbbm{R}^{n}:y=Cx\text{ for some
}x\in\mathbbm{R}^{k}\\}$

are linear subspaces of $\mathbbm{R}^{n}$. Show that
$S:=\\{x\in\mathbbm{R}^{n}:\left\langle{c,x}\right\rangle\geqslant 0\\}$ is
not. A linear combination of vectors $v_{1},\ldots,v_{k}$ in $\mathbbm{R}^{n}$
is a vector of the form

$\alpha_{1}v_{1}+\cdots+\alpha_{k}v_{k}\text{ where
}(\alpha_{1},\ldots,\alpha_{k})\in\mathbbm{R}^{k}.$

The set of all linear combinations of elements of $F\subset\mathbbm{R}^{n}$ is
called the span of $F$ and written as $\operatorname{span}F$.

######  Example 6.1.13.

The set $\operatorname{range}C$ in Exercise 6.1.4.1 is the span of the columns
of the matrix $C$, viewed as a set of vectors in $\mathbbm{R}^{n}$. The set
$\operatorname{range}C$ is also called the column space of $C$.

Let $F$ be a nonempty subset of $\mathbbm{R}^{n}$. Prove that

  1. (i)

$\operatorname{span}F$ is a linear subspace of $\mathbbm{R}^{n}$ and

  2. (ii)

$\operatorname{span}F$ is the intersection of all linear subspaces
$S\subset\mathbbm{R}^{n}$ with $S\supset F$.

Figure 6.7 shows the linear subspace spanned by the three vectors

$u=\begin{pmatrix}3\\\ 4\\\ 1\end{pmatrix},\quad v=\begin{pmatrix}3\\\ -4\\\
0.2\end{pmatrix},\quad\text{and }w=\begin{pmatrix}-3.5\\\ 3\\\
-0.4\end{pmatrix}.$ (6.10)

The subspace $H$ in which these vectors lie is, in fact, the set of all
$x\in\mathbbm{R}^{3}$ such that $\left\langle{x,c}\right\rangle=0$, with
$c=(-0.2,-0.1,1)$. This plane is a two-dimensional object. While we make this
terminology precise in §6.1.4.2, the key idea is that

  * •

at least two vectors are required to span $H$ and

  * •

any additional vectors will not increase the span.

Figure 6.7:  The span of vectors $u,v,w$ in $\mathbbm{R}^{3}$

A finite set of vectors $F:=\\{v_{1},\ldots,v_{k}\\}\subset\mathbbm{R}^{n}$ is
called linearly independent if, for real scalars
$\alpha_{1},\ldots,\alpha_{k}$,

$\alpha_{1}v_{1}+\cdots+\alpha_{k}v_{k}=0\;\implies\;\alpha_{1}=\cdots=\alpha_{k}=0.$

If $F$ is not linearly independent it is called linearly dependent. Show that
$F$ is linearly dependent if and only if there exists a vector in $F$ that can
be written as a linear combination of other vectors in $F$. Prove the
following:

  1. (i)

Every subset of a linearly independent set in $\mathbbm{R}^{n}$ is linearly
independent.555By the law of the excluded middle, the empty set must be
linearly independent too.

  2. (ii)

Every finite superset of a linearly dependent set in $\mathbbm{R}^{n}$ is
linearly dependent.

Regarding the first claim, let $E=\\{u_{1},\ldots,u_{k}\\}$ be linearly
independent. Suppose that $\\{u_{1},\ldots,u_{m}\\}$ is linearly dependent for
some $m<k$. Then we can find a nonzero vector $(\alpha_{1},\ldots,\alpha_{m})$
such that $\sum_{i=1}^{m}\alpha_{i}u_{i}=0$. Setting $\alpha_{i}=0$ for $i$ in
$\\{m+1,\ldots,k\\}$ yields $\sum_{i=1}^{k}\alpha_{i}u_{i}=0$, contradicting
independence of $E$. Regarding the second claim, suppose that $E\subset F$ and
$E$ is linearly dependent. If $F$ is linearly independent, then we have a
violation of the first claim. Hence $F$ is linearly dependent.

######  Example 6.1.14.

It is easy to check that the set
$E:=\\{\delta_{1},\ldots,\delta_{n}\\}\subset\mathbbm{R}^{n}$ defined by

$\delta_{1}:=\left(\begin{array}[]{c}1\\\ 0\\\ \vdots\\\
0\end{array}\right),\quad\delta_{2}:=\left(\begin{array}[]{c}0\\\ 1\\\
\vdots\\\
0\end{array}\right),\;\cdots,\;\delta_{n}:=\left(\begin{array}[]{c}0\\\ 0\\\
\vdots\\\ 1\end{array}\right)$

is linearly independent. Its elements are called the canonical basis vectors
of $\mathbbm{R}^{n}$.

The span of the canonical basis vectors in $\mathbbm{R}^{n}$ is equal to all
of $\mathbbm{R}^{n}$. In particular, each $x\in\mathbbm{R}^{n}$ can be
expressed as

$x=\sum_{i=1}^{n}\alpha_{i}\delta_{i}\quad\text{where
}\alpha_{i}:=\left\langle{x,\delta_{i}}\right\rangle.$ (6.11)

On the other hand, we cannot omit an element of the basis
$\\{\delta_{1},\ldots,\delta_{n}\\}$ and still span $\mathbbm{R}^{n}$. The
next theorem generalizes this idea.

######  Theorem 6.1.7.

If $E=\\{u_{1},\ldots,u_{n}\\}$ is a set of $n$ vectors in $\mathbbm{R}^{n}$,
then $\operatorname{span}E=\mathbbm{R}^{n}$ if and only if $E$ is linearly
independent.

See, for example, Jänich, (1994). Theorem 6.1.7 captures the notion that
linear independence of a set of vectors means linear diversity, which allows
the span to be large. The null space or kernel of a matrix
$A\in\mathbbm{M}^{n\times k}$ is the set

$\operatorname{null}A:=\\{x\in\mathbbm{R}^{k}:Ax=0\\}.$

Show that (i) $\operatorname{null}A$ is a linear subspace of $\mathbbm{R}^{k}$
and (ii) $\operatorname{null}A=\\{0\\}$, where $0$ is the origin in
$\mathbbm{R}^{k}$, if and only if the columns of $A$ form a linearly
independent subset of $\mathbbm{R}^{n}$. Regarding (i), if $Ax=Ay=0$, then
$A(\alpha x+\beta y)=\alpha Ax+\beta Ay=0$, so $\operatorname{null}A$ is a
linear subspace. Regarding (ii), suppose that $\operatorname{null}A=\\{0\\}$.
This means that the only $x\in\mathbbm{R}^{k}$ satisfying $Ax=0$ is the zero
vector, which is equivalent to linear independence of the columns of $A$.

######  6.1.4.2 Basis Vectors and Dimension

Let $V$ be a linear subspace of $\mathbbm{R}^{n}$. A set $B\subset V$ is
called a basis for $V$ if $B$ is linearly independent and
$\operatorname{span}B=V$. The key idea behind a basis is this: If
$S=\\{v_{1},\ldots,v_{k}\\}$ spans some linear subspace $V$, then each element
of $V$ can be written as a linear combination of elements of $S$. If $S$ is,
in addition, linearly independent (and hence a basis), then this
representation is _unique_ : for each $u\in V$, there is exactly one
$(\alpha_{1},\ldots,\alpha_{k})\in\mathbbm{R}^{k}$ such that

$u=\alpha_{1}v_{1}+\cdots+\alpha_{k}v_{k}.$

Indeed, if $u=\beta_{1}v_{1}+\cdots+\beta_{k}v_{k}$ is another representation,
then, subtracting this equality from the last, we have

$(\alpha_{1}-\beta_{1})v_{1}+\cdots+(\alpha_{k}-\beta_{k})v_{k}=0.$

Because $S$ is assumed to be linearly independent, this yields
$\alpha_{i}=\beta_{i}$ for all $i\in[k]$. Not surprisingly, given their name,
the canonical basis vectors $E:=\\{\delta_{1},\ldots,\delta_{n}\\}$ serve as a
basis for the whole space $\mathbbm{R}^{n}$. The representation (6.11), with
coefficients $\alpha_{i}=\left\langle{x,\delta_{i}}\right\rangle$, is unique.

######  Theorem 6.1.8.

If $V$ is a nonzero linear subspace of $\mathbbm{R}^{n}$, then

  1. (i)

$V$ has at least one basis and

  2. (ii)

every basis of $V$ has the same number of elements.

Theorem 6.1.8 is a relatively deep result. See, for example, Jänich, (1994).
The common number of bases in (ii) is called the dimension of $V$ and written
as $\dim V$. The “nonzero” qualification in Theorem 6.1.8 is included for the
case $V=\\{0\\}$, which is a linear subspace that lacks any basis. It is
sensible, and standard, to agree that the linear subspace
$\\{0\\}\subset\mathbbm{R}^{n}$ has dimension zero. Dimensionality is one
measure of the “size” of a linear subspace. To illustrate, consider the system
$Ax=b$ where $A\in\mathbbm{M}^{n\times k}$, $x\in\mathbbm{R}^{k}$ and
$b\in\mathbbm{R}^{n}$. Is there an $x$ that solves this system? This will be
more likely if the column space of $A$ is large (see Example 6.1.13). A large
span will be obtained when the columns are linearly “diverse.” In other words,
our hope is that there exists a large subset of the columns of $A$ that is
linearly independent, which in turn will be true when the span of $A$ is high-
dimensional. To quantify these ideas, we define the rank of $A$ as

$\operatorname{rank}A:=\dim(\operatorname{range}A)=\text{ dimension of the
column space of }A.$

######  Theorem 6.1.9.

For any matrix $A$, the following quantities are equal:

  1. (i)

$\operatorname{rank}A$

  2. (ii)

the maximal number of linearly independent columns of $A$, and

  3. (iii)

the maximal number of linearly independent rows of $A$.

See, for example, Chapter 2 of Aggarwal, (2020) or Chapter 5 of Jänich,
(1994). In view of Exercise 6.1.4.2, for $A\in\mathbbm{M}^{n\times k}$, we
have $\operatorname{rank}A\leqslant k$. If $\operatorname{rank}A=k$, then $A$
is said to have full column rank. In general, a linear subspace $V$ contains
within itself many other linear subspaces. (For example, a plane passing
through the origin contains many lines that pass through the origin, each one
of which is a linear subspace.) However, there is no proper subspace of $V$
(i.e., no linear subspace contained in and distinct from $V$) with the same
dimension as $V$. The next theorem records this fact.

######  Theorem 6.1.10.

If $U,V$ are linear subspaces of $\mathbbm{R}^{n}$, then $U\subset V$ implies
$\dim U\leqslant\dim V$ with equality if and only if $U=V$.

Let $U$ be a linear subspace of $\mathbbm{R}^{n}$. Using the results given
above, prove the following statements:

  1. (i)

The only $n$-dimensional linear subspace of $\mathbbm{R}^{n}$ is
$\mathbbm{R}^{n}$.

  2. (ii)

If $A\subset U$ is finite and $|A|>\dim U$, then $A$ is linearly dependent.

For part (i) just set $V=\mathbbm{R}^{n}$ in Theorem 6.1.10. Regarding part
(ii), let $A$ and $U$ be as stated, with $|A|=:m>\dim U$. Suppose to the
contrary that $A$ is linearly independent. Then $A$ is a basis for
$\operatorname{span}A$ and, therefore, $\dim\operatorname{span}A=m>\dim U$. At
the same time, since $A\subset U$ and $U$ is a linear subspace, we have
$\operatorname{span}A\subset U$. Hence, by Theorem 6.1.10, we have
$m\leqslant\dim U$. Contradiction. Part (ii) is related to Figure 6.7. The
plane in that figure is 2-dimensional, as we confirm in §6.1.4.3 below. Any
three vectors lying in the plane are linearly dependent.

######  6.1.4.3 Linear Maps Are Matrices

We will see in the following chapters that many nonlinear dynamic models and
estimation problems can be expressed in terms of linear operations in high-
dimensional spaces. We now state the definition of linear maps and their
connection to matrices. A function $u\mapsto Au$ from $\mathbbm{R}^{k}$ to
$\mathbbm{R}^{n}$ is called linear if

$A(\alpha u+\beta v)=\alpha Au+\beta Av\quad\text{ for all
$\alpha,\beta\in\mathbbm{R}$ and all $u,v$ in $\mathbbm{R}^{k}$}.$

In this context, $A$ is sometimes called an operator rather than a function,
but the meaning is the same. Fix $s,t\in\mathbbm{R}$. Show that
$A\colon\mathbbm{R}\to\mathbbm{R}$ defined by $Au=su+t$ is a linear function
on $\mathbbm{R}$ if and only if $t=0$. Let
$A\colon\mathbbm{R}^{n}\to\mathbbm{R}^{n}$ be a linear bijection. By Lemma
6.1.1, the operator $A$ has an inverse $A^{-1}$ mapping $\mathbbm{R}^{n}$ to
itself. Prove that $A^{-1}$ is linear. Here’s a proof by contradiction: Let
$A$ be as stated. Suppose to the contrary that $A^{-1}$ fails to be linear.
Then we can find $\alpha,\beta\in\mathbbm{R}$ and $x,y\in\mathbbm{R}^{n}$ such
that $A^{-1}(\alpha x+\beta y)$ and $\alpha A^{-1}x+\beta A^{-1}y$ are
distinct points. Since $A$ is a bijection, their images under $A$ are also
distinct, so

$\alpha x+\beta y\not=A(\alpha A^{-1}x+\beta A^{-1}y).$

Linearity of $A$ leads to a contradiction. One of the most striking and useful
properties of linear operators is that the one-to-one property and the onto
property are equivalent when the domain and codomain agree:

######  Theorem 6.1.11.

Let $A\colon\mathbbm{R}^{n}\to\mathbbm{R}^{n}$ be linear. The operator $A$ is
a one-to-one function if and only if it is onto.

The proof can be found in Jänich, (1994) or Stachurski, (2016). Figure 6.8
illustrates in the one-dimensional case. The linear map $f(x)=\alpha x$ is
onto if and only if it is one-to-one, which occurs if and only if
$\alpha\not=0$.

Figure 6.8:  Equivalence of the onto and one-to-one properties

A matrix $A\in\mathbbm{M}^{n\times k}$ is a linear function from
$\mathbbm{R}^{k}$ to $\mathbbm{R}^{n}$ when identified with the mapping that
sends a (column) vector $u$ in $\mathbbm{R}^{k}$ into the vector $Au$ in
$\mathbbm{R}^{n}$. In fact it is fundamental that, for _every_ linear map
$A\colon\mathbbm{R}^{k}\to\mathbbm{R}^{n}$, there exists a unique
$M_{A}\in\mathbbm{M}^{n\times k}$ such that

$Au=M_{A}u\quad\text{for all}\quad u\in\mathbbm{R}^{k}$ (6.12)

(see, e.g., Kreyszig, (1978), §2.9). Thus, the set of linear maps and the set
of matrices are in one-to-one correspondence in the finite dimensional
setting.

######  6.1.4.4 Linear Hyperplanes

In Exercise 6.1.4.1, you confirmed that, for a given nonzero
$c\in\mathbbm{R}^{n}$, the subset of $\mathbbm{R}^{n}$ defined by
$H:=\\{x\in\mathbbm{R}^{n}:\left\langle{c,x}\right\rangle=0\\}$ is a linear
subspace of $\mathbbm{R}^{n}$. Any set $H$ of this form is called a linear
hyperplane in $\mathbbm{R}^{n}$. The vector $c$ is called the normal vector of
the hyperplane.

######  Theorem 6.1.12 (Rank-Nullity Theorem).

For each $A\in\mathbbm{M}^{n\times k}$, we have

$\operatorname{rank}A+\dim(\operatorname{null}A)=k.$

######  Example 6.1.15.

If $A$ has linearly independent columns, then $\operatorname{rank}A=k$ and $A$
is said to have full column rank. Recall from Exercise 6.1.4.1 that this is
precisely the setting where $\operatorname{null}A=\\{0\\}$. Hence
$\dim(\operatorname{null}A)=0$, and Theorem 6.1.12 holds.

In the discussion after Figure 6.7, we claimed that the linear hyperplane has
shown there is a two-dimensional subset of $\mathbbm{R}^{3}$. The next example
generalizes this idea.

######  Example 6.1.16.

A linear hyperplane
$H=\\{x\in\mathbbm{R}^{n}:\left\langle{x,c}\right\rangle=0\\}$ with $c\not=0$
has dimension $n-1$. To see this, just set $A$ in Theorem 6.1.12 to $c$,
treated as a $1\times n$ row vector. Then $H=\operatorname{null}A$, and

$\dim H=\dim\operatorname{null}A=n-\operatorname{rank}A=n-1.$

(Here $\operatorname{rank}A=1$ follows from Theorem 6.1.9.)

######  6.1.4.5 Nonsingular Linear Systems

A crucial task in applied modeling is solving linear systems such as $Ax=b$,
where $A$ is a matrix and $x$ and $b$ are conformable column vectors. The
system can be underdetermined, overdetermined or exactly determined (i.e.,
same number of equations as unknowns). In this section we consider the last
case, where the theory is straightforward. Let $A$ and $B$ be in
$\mathbbm{M}^{n\times n}$ and suppose that $AB=BA=I$. Then $B$ is called the
inverse of $A$, written as $A^{-1}$, while $A$ is said to be invertible or
nonsingular. The next theorem states that, for square matrices, the property
of having either a left or a right inverse is equivalent to nonsingularity.

######  Theorem 6.1.13.

Given $A$ in $\mathbbm{M}^{n\times n}$, the following statements are
equivalent:

  1. (i)

There exists an $L\in\mathbbm{M}^{n\times n}$ such that $LA=I$.

  2. (ii)

There exists an $R\in\mathbbm{M}^{n\times n}$ such that $AR=I$.

If one and hence both of these statements hold, then $A$ is nonsingular and
$L=R=A^{-1}$.

###### Proof.

Fix $A$ in $\mathbbm{M}^{n\times n}$ and suppose first that (i) holds. This
implies that $A$ has a left inverse. In view of Exercise 6.1.1.4, it must be
that $x\mapsto Ax$ is one-to-one on $\mathbbm{R}^{n}$. By Theorem 6.1.11, this
means that the same function is onto. Hence $x\mapsto Ax$ is a bijection, and
therefore invertible (Lemma 6.1.1). By Exercise 6.1.4.3, the inverse function
is linear and hence can be represented by a matrix. We denote it $A^{-1}$. For
the left inverse $L$ we have $L=A^{-1}$, since
$L=L(AA^{-1})=(LA)A^{-1}=A^{-1}$. Now suppose there exists an
$R\in\mathbbm{M}^{n\times n}$ such that $AR=I$. Then, $A$ is the left inverse
of $R$ and, by the previous argument, $R$ is invertible with $A=R^{-1}$. Pre-
multiplying both sides by $R$ gives $RA=I$, so $R$ is also a left inverse of
$A$. As we now know, this means that $A$ is nonsingular and $R=A^{-1}$. In
summary, if either (i) or (ii) holds, then $A$ is nonsingular, with left and
right inverses both equal to $A^{-1}$. ∎

Consider the linear system $Ax=b$, where $A\in\mathbbm{M}^{n\times n}$ and
$b\in\mathbbm{R}^{n}$. We seek a solution $x\in\mathbbm{R}^{n}$. The next
theorem provides conditions under which such an $x$ is always uniquely
identified.

######  Theorem 6.1.14.

The following statements are equivalent:

  1. (i)

For each $b\in\mathbbm{R}^{n}$, the equation $Ax=b$ has a unique solution.

  2. (ii)

The columns of $A$ are linearly independent.

  3. (iii)

The columns of $A$ form a basis of $\mathbbm{R}^{n}$.

  4. (iv)

$\operatorname{null}A=\\{0\\}$.

  5. (v)

$\operatorname{rank}A=n$.

  6. (vi)

$\det A$ is nonzero.

  7. (vii)

$A$ is nonsingular.

The symbol $\det A$ represents the determinant of $A$. For the definition,
see, for example, Jänich, (1994) or Cohen, (2021). We note only that, for
$n\times n$ matrices $A$ and $B$,

  * •

$\det(AB)=\det(A)\det(B)$,

  * •

$\det(\alpha A)=\alpha^{n}\det A$ for all $\alpha\in\mathbbm{R}$, and

  * •

$\det(A^{-1})=(\det A)^{-1}$ whenever $A$ is nonsingular.

Most of the equivalences in Theorem 6.1.14 can be established from the results
presented above. The key idea is that, under these equivalent conditions, the
columns of $A$ form a basis of $\mathbbm{R}^{n}$, and hence any
$b\in\mathbbm{R}^{n}$ can be expressed uniquely as a linear combination of
elements of these columns. In other words, there exists a unique
$x\in\mathbbm{R}^{n}$ with $Ax=b$. The remaining points are just equivalent
ways of saying that the columns of $A$ form a basis of $\mathbbm{R}^{n}$. Let
$A$ and $B$ be conformable in the sense that $AB$ is well defined. Show that
$\operatorname{rank}(AB)\leqslant\operatorname{rank}A$, with equality if and
only if $B$ is nonsingular. (Hint: Use Theorem 6.1.10.)

######  6.1.4.6 Orthogonality

We recall that vectors $u,v$ in $\mathbbm{R}^{n}$ are called orthogonal and we
write $u\perp v$ if $\left\langle{u,v}\right\rangle=0$. For a linear subspace
$L$ of $\mathbbm{R}^{n}$, we call $u\in\mathbbm{R}^{n}$ orthogonal to $L$ and
write $u\perp L$ whenever $u\perp v$ for all $v\in L$. The orthogonal
complement of linear subspace $L$ is defined as
$L^{\perp}:=\\{v\in\mathbbm{R}^{n}:v\perp L\\}$. Show that $L^{\perp}$ is a
linear subspace of $\mathbbm{R}^{n}$. Fix $u,v\in L^{\perp}$ and
$\alpha,\beta\in\mathbbm{R}$. If $z\in L$, then

$\left\langle{\alpha u+\beta
v,z}\right\rangle=\alpha\left\langle{u,z}\right\rangle+\beta\left\langle{v,z}\right\rangle=\alpha\times
0+\beta\times 0=0$

Hence $\alpha u+\beta v\in L^{\perp}$, as was to be shown. Prove: for any
linear subspace $L\subset\mathbbm{R}^{n}$, we have $L\cap L^{\perp}=\\{0\\}$.
A set of vectors $O\subset\mathbbm{R}^{n}$ is called an orthogonal set if any
two distinct elements of $O$ are orthogonal. For any orthogonal set $O$, the
Pythagorean law

$\left\|\sum_{u\in O}u\right\|^{2}=\sum_{u\in O}\|u\|^{2}$

always holds. Prove: Orthogonality implies linear independence in the sense
that

$O\subset\mathbbm{R}^{n}\text{ is orthogonal and $0\notin O$
}\;\implies\;\text{$O$ is linearly independent}.$

An orthogonal set $O\subset\mathbbm{R}^{n}$ is called an orthonormal set if
$\|u\|=1$ for all $u\in O$. If $L$ is a linear subspace of $\mathbbm{R}^{n}$,
$O$ is orthonormal in $L$ and $\operatorname{span}O=L$, then $O$ is called an
orthonormal basis of $L$. For example, the canonical basis
$\\{e_{1},\ldots,e_{n}\\}$ forms an orthonormal basis of $\mathbbm{R}^{n}$.
Explain why an orthonormal basis $O$ of a subspace $L$ is, in fact, a basis of
$L$, in the sense of the definition in §6.1.4.2. If $O$ is an orthonormal
basis of $L$, then, by definition, $O$ spans $L$. In addition, the elements of
$O$ are independent because they are orthogonal and nonzero. A matrix $M$ is
called an orthonormal matrix if $M\in\mathbbm{M}^{n\times n}$ for some
$n\in\mathbbm{N}$ and, in addition, the columns of $M$ form an orthonormal set
in $\mathbbm{R}^{n}$. These kinds of matrices will be important to us when we
analyze singular value decomposition. Notice that,

  * •

by definition, every orthonormal matrix is square, and

  * •

the $n$ columns of an orthonormal matrix $M$ in $\mathbbm{R}^{n}$ form a basis
of $\mathbbm{R}^{n}$, since they are nonzero and orthogonal.

The second point tells us that $M$ is nonsingular. The next lemma summarizes
important properties of orthonormal matrices.

######  Lemma 6.1.15.

Fix $M\in\mathbbm{M}^{n\times n}$ and let $I$ be the $n\times n$ identity. The
following statements are equivalent:

  1. (i)

$M$ is an orthonormal matrix.

  2. (ii)

$M^{\top}M=I$.

  3. (iii)

$MM^{\top}=I$.

  4. (iv)

$M^{\top}=M^{-1}$.

The equivalence of (ii) and (iii) is quite striking. It tells us that a square
matrix with orthonormal columns automatically has orthonormal rows.

###### Proof.

Clearly (i) and (ii) are equivalent, since they are two ways of writing the
same thing. Equivalence of (ii)–(iv) follows from Theorem 6.1.13 on page
6.1.13. ∎

#####  6.1.5 Convexity and Concavity

Convexity and concavity are structures of enormous significance in economics
and finance, in terms of both computation and theory. In this section we note
the key definitions and provide exercises that help build familiarity.

######  6.1.5.1 Convexity and Polyhedra

Convexity plays a central role in optimization and fixed point theory. As
usual, a subset $C$ of $\mathbbm{R}^{n}$ is called convex if

$u,v\in C\text{ and }\lambda\in[0,1]\;\implies\;\lambda u+(1-\lambda)v\in C.$

Show that

  1. (i)

the unit simplex in $\mathbbm{R}^{n}$ is a convex subset of $\mathbbm{R}^{n}$.

  2. (ii)

For all $a\in\mathbbm{R}^{n}$ and $\varepsilon>0$, the sphere
$B=\\{x\in\mathbbm{R}^{n}:\|x-a\|<\varepsilon\\}$ is convex.

  3. (iii)

The intersection of an arbitrary number of convex sets in $\mathbbm{R}^{n}$ is
again convex.

For part (i), let $S=\\{x\in\mathbbm{R}^{n}_{+}:\mathbbm{1}^{\top}x\leqslant
1\\}$ be the unit simplex, where $\mathbbm{1}$ is a column vector of ones. Fix
$u,v\in S$ and $\lambda\in[0,1]$. We have

$\lambda u+(1-\lambda)v\geqslant 0$

and

$\mathbbm{1}^{\top}(\lambda
u+(1-\lambda)v)=\lambda\mathbbm{1}^{\top}u+(1-\lambda)\mathbbm{1}^{\top}v\\\
\leqslant\lambda+(1-\lambda)=1$

Hence $S$ is a convex set. For part (ii), fix $u,v\in B$, $\lambda\in[0,1]$
and $a\in\mathbbm{R}^{n},\varepsilon>0$. We have

$\|\lambda u+(1-\lambda)v-a\|=\|\lambda(u-a)+(1-\lambda)(v-a)\|\\\
\leqslant\lambda\|u-a\|+(1-\lambda)\|v-a\|\\\
\leqslant\lambda\varepsilon+(1-\lambda)\varepsilon=\varepsilon$

Hence $B$ is convex. Regarding part (iii), let $(S_{i})$ be a convex set for
$i=1,2,\cdots,n$. Fix $u,v\in\cap^{n}_{i=1}S_{i}$ and $\lambda\in[0,1]$. We
have

$z=\lambda u+(1-\lambda)v\in S_{i}\quad\text{ for all }i$

This implies $z\in\cap^{n}_{i=1}S_{i}$ and hence $\cap^{n}_{i=1}S_{i}$ is
convex. In economic optimization problems, the convex sets within which we
seek extrema are usually polyhedra. A polyhedron in $\mathbbm{R}^{n}$ is a set
of the form

$P=\\{x\in\mathbbm{R}^{n}:Ax\leqslant b\\}\quad\text{ for some
$A\in\mathbbm{M}^{k\times n}$ and $b\in\mathbbm{R}^{k}$}.$ (6.13)

Equivalently, $P$ is a polyhedron in $\mathbbm{R}^{n}$ if there exist scalars
$b_{1},\ldots,b_{k}$ and $n$-dimensional vectors $a_{1},\ldots,a_{k}$ such
that $x\in P$ if and only if $a_{i}^{\top}x\leqslant b_{i}$ for
$i=1,\ldots,k$.

######  Example 6.1.17.

A budget set of the form $B=\\{x\in\mathbbm{R}^{n}_{+}:p^{\top}x\leqslant
m\\}$ where $m\geqslant 0$ and $p\in\mathbbm{R}^{n}_{+}$ is a polyhedron. Here
$p$ is a vector of prices and $x$ is a consumption bundle. Indeed, $B$ can be
expressed as the set of all $x\in\mathbbm{R}^{n}$ such that
$p^{\top}x\leqslant m$ and, for the nonnegativity constraints,
$-\delta_{i}^{\top}x\leqslant 0$ for $i=1,\ldots,n$, where $\delta_{i}$ is the
$i$-th canonical basis vector in $\mathbbm{R}^{n}$. This meets the definition
of a polyhedron.

Given $b\in\mathbbm{R}$ and nonzero $c\in\mathbbm{R}^{n}$,

  * •

$H_{0}:=\\{x\in\mathbbm{R}^{n}:x^{\top}c=b\\}$ is called a hyperplane in
$\mathbbm{R}^{n}$, while

  * •

$H_{1}:=\\{x\in\mathbbm{R}^{n}:x^{\top}c\leqslant b\\}$ is called a halfspace
in $\mathbbm{R}^{n}$.

Note our convention. In §6.1.4.4 we defined _linear_ hyperplanes, which
correspond to $H_{0}$ when $b=0$. Thus linear hyperplanes are a special kind
of hyperplane. You will be able to confirm that the hyperplane $H_{0}$ is a
linear subspace of $\mathbbm{R}^{n}$ if and only if $b=0$. Show that $H_{0}$
and $H_{1}$ are both convex in $\mathbbm{R}^{n}$. Fix $u,v\in H_{0}$,
$\lambda\in[0,1]$, $b\in\mathbbm{R}$ and nonzero $c\in\mathbbm{R}^{n}$. Then

$(\lambda u+(1-\lambda)v)^{\top}c=\lambda
u^{\top}c+(1-\lambda)v^{\top}c=\lambda b+(1-\lambda)b=b$

Thus $H_{0}$ is convex. The proof that $H_{1}$ is convex is similar. It is
immediate from the definition that $P\subset\mathbbm{R}^{n}$ is a polyhedron
if and only if $P$ is the intersection of $k$ halfspaces in $\mathbbm{R}^{n}$
for some $k\in\mathbbm{N}$. Figure 6.9 helps illustrate this idea.

Figure 6.9:  A polyhedron $P$ represented as intersecting halfspaces

An extreme point of a polyhedron $P$ is a point $p\in P$ that cannot be
realized as the convex combination of other points in $P$. In other words, we
cannot find two points $x,y\in P$ that are distinct from $p$ and satisfy
$\lambda x+(1-\lambda)y=p$ for some $\lambda\in[0,1]$. The extreme points of
$P$ in Figure 6.9 are represented as black dots. Show that every polyhedron in
$\mathbbm{R}^{n}$ is convex. A cone in $\mathbbm{R}^{n}$ is a set
$C\subset\mathbbm{R}^{n}$ such that $x\in C$ implies $\alpha x\in C$ for all
$\alpha>0$. Show that (i) the intersection of any two cones is again a cone
and (ii) a cone $C\subset\mathbbm{R}^{n}$ is convex (i.e., $C$ is a convex
cone) if and only if it is closed under addition (i.e, $x,y\in C$ implies
$x+y\in C$). Regarding part (i), let $C$ and $D$ be two cones. Fix $x\in C\cap
D$ and $\alpha>0$. Since $x\in C$ and $x\in D$, and since both are cones, we
have $\alpha x\in C\cap D$. Hence $C\cap D$ is a cone. Regarding part (ii),
suppose first that $C$ is a convex cone and fix $x,y\in C$. Since $C$ is
convex, it must be that $(1/2)(x+y)\in C$. Since $C$ is a cone we can scale by
$2$ without leaving $C$. Hence $x+y\in C$. Suppose next that $C$ is a cone and
closed under addition. Fix $\alpha\in(0,1)$ and $x,y\in C$. Since $C$ is a
cone, we have $\alpha x\in C$ and $(1-\alpha)y\in C$. Since $C$ is closed
under addition, it follows that $\alpha x+(1-\alpha)y\in C$. Hence $C$ is
convex. The positive cone of $\mathbbm{R}^{n}$ is the set

$\mathbbm{R}^{n}_{+}:=\\{x\in\mathbbm{R}^{n}:x\geqslant 0\\}.$

Show that, for the partially ordered set $(\mathbbm{R}^{n},\leqslant)$, the
positive cone is an increasing subset of $\mathbbm{R}^{n}$. Show in addition
that $\mathbbm{R}^{n}_{+}$ is a convex cone.

######  6.1.5.2 Convex and Concave Functions

A function $g$ from a convex subset $C$ of $\mathbbm{R}^{n}$ to
$\mathbbm{R}^{k}$ is called convex if

$g(\lambda u+(1-\lambda)v)\leqslant\lambda
g(u)+(1-\lambda)g(v)\quad\text{whenever }u,v\in C\text{ and
}0\leqslant\lambda\leqslant 1,$

and concave if $-g$ is convex. Concavity of $g$ is obviously equivalent to

$g(\lambda u+(1-\lambda)v)\geqslant\lambda
g(u)+(1-\lambda)g(v)\quad\text{whenever }u,v\in C\text{ and
}0\leqslant\lambda\leqslant 1.$

When $k=1$, the function $g$ is called, respectively, strictly convex or
strictly concave if, in addition, the inequalities become strict whenever
$u,v$ are distinct and $0<\lambda<1$. Given an example of a function $g$ from
$\mathbbm{R}^{n}$ to $\mathbbm{R}^{n}$ that is both convex and concave. Every
linear function is both convex and concave. These properties of functions are
closely related to convexity of sets. For example, the same function $g$ is
convex if and only if its epigraph

$\operatorname{epi}(g):=\\{(x,g(x))\in\mathbbm{R}^{n+1}:x\in C\\}$

is convex. If $C$ is a convex subset of $\mathbbm{R}^{n}$ and
$g\colon\mathbbm{R}^{n}\to\mathbbm{R}$ is convex, then Jensen’s inequality
states that, for any vectors $\\{x_{1},\ldots,x_{k}\\}\subset C$ and weights
$\\{\lambda_{1},\ldots,\lambda_{k}\\}\subset\mathbbm{R}$ with
$0\leqslant\lambda_{i}\leqslant 1$ and $\sum_{i}\lambda_{i}=1$, we have

$g\left(\sum_{i=1}^{k}x_{i}\lambda_{i}\right)\leqslant\sum_{i=1}^{k}g\left(x_{i}\right)\lambda_{i}.$

If $g$ is concave then the reverse inequality holds. Prove Jensen’s inequality
for the case where $g$ is convex when $k=3$. In the next exercise, if
$\\{y_{i}\\}$ is a finite collection of vectors in $\mathbbm{R}^{k}$, then
$\max_{i}y_{i}$ is the vector in $\mathbbm{R}^{k}$ obtained by taking the
maximum pointwise. The minimum $\min_{i}y_{i}$ is defined in a similar way.
Fix $m\in\mathbbm{N}$ and let $\\{g_{i}\\}_{i\in[m]}$ be a collection of
$\mathbbm{R}^{k}$-valued functions defined on a convex subset $C$ of
$\mathbbm{R}^{n}$. Show that,

  1. (i)

if $g_{i}$ is convex for every $i$ in $[m]$, then $g$ defined at each $x$ in
$C$ by $g(x):=\max_{i\in[m]}g_{i}(x)$ is also convex on $C$ and

  2. (ii)

if $g_{i}$ is concave for every $i$ in $[m]$, then $g$ defined at each $x$ in
$C$ by $g(x):=\min_{i\in[m]}g_{i}(x)$ is also concave on $C$.

It suffices to prove these results in the scalar case $n=k=1$, since the
vector results are just element-by-element extensions of the scalar case. We
focus on the setting where each $g_{i}$ is convex, as the concave case is
similar. In general, for scalars $\\{a_{i}\\}_{i=1}^{m}$ and
$\\{b_{i}\\}_{i=1}^{m}$, we always have

$\max_{i}\\{a_{i}+b_{i}\\}\leqslant\max_{i}\\{a_{i}\\}+\max_{i}\\{b_{i}\\}.$

Hence, in the scalar case, when all $g_{i}$s are convex, we have, for any
$\lambda\in[0,1]$ and $x,y\in C$,

$\displaystyle\max_{i}\\{g_{i}(\lambda
x+(1-\lambda)y)\\}\leqslant\max_{i}\\{\lambda
g_{i}(x)+(1-\lambda)g_{i}(y)\\}\leqslant\lambda\max_{i}g_{i}(x)+(1-\lambda)\max_{i}g_{i}(y)$

This proves the scalar case (and, by extension, the vector case). Let $f$ and
$g$ map $C$ to $\mathbbm{R}$, where $C\subset\mathbbm{R}^{n}$ is convex and so
are $f$ and $g$. Show that (i) $f+g$ is convex and (ii) $f+g$ is strictly
convex if, in addition, either $f$ or $g$ is strictly convex. Important
examples of concave and convex scalar-valued functions include certain kinds
of quadratic forms. For the following you should recall that a symmetric
$n\times n$ matrix $A$ is called

  * •

positive semidefinite if $x^{\top}Ax\geqslant 0$ for any $x$ in
$\mathbbm{R}^{n}$,

  * •

positive definite if $x^{\top}Ax>0$ for any nonzero $x$ in $\mathbbm{R}^{n}$,

  * •

negative semidefinite if $x^{\top}Ax\leqslant 0$ for any $x$ in
$\mathbbm{R}^{n}$, and

  * •

negative definite if $x^{\top}Ax<0$ for any nonzero $x$ in $\mathbbm{R}^{n}$.

It’s important to remember (but easy to forget) that symmetry is part of the
definition of these properties. You probably remember that

  * •

$A$ is positive definite (resp., semidefinite) if and only if all its
eigenvalues are strictly positive (resp., nonnegative) and

  * •

$A$ is positive definite (resp., semidefinite) $\implies$ its determinant is
strictly positive (resp., nonnegative).

The second statement follows from the first, since the determinant of a matrix
equals the product of its eigenvalues. The quadratic form $q(x)=x^{\top}Ax$ is

  * •

convex if and only if $A$ is positive semidefinite,

  * •

strictly convex if and only if $A$ is positive definite,

  * •

concave if and only if $A$ is negative semidefinite, and

  * •

strictly concave if and only if $A$ is negative definite.

See, for example, Simon, (1994). Let $X$ be $n\times k$. Prove the following:

  1. (i)

$X^{\top}X$ is positive semidefinite.

  2. (ii)

If, in addition, $X$ has full column rank, then $X^{\top}X$ is positive
definite.

#####  6.1.6 Optimization

In this section we review some key topics in optimization theory.

######  6.1.6.1 Definitions and Existence

A number $m$ contained in a subset $A$ of $\mathbbm{R}$ is called the maximum
of $A$ and we write $m=\max A$ if $a\leqslant m$ for every $a\in A$. It is
called the minimum of $A$, written as $m=\min A$, if $m\in A$ and $a\geqslant
m$ for every $a\in A$. Given an arbitrary set $D$ and a function $f\colon
D\to\mathbbm{R}$, define

$\max_{x\in D}f(x):=\max\\{f(x):x\in D\\}\quad\text{and}\quad\min_{x\in
D}f(x):=\min\\{f(x):x\in D\\}.$

A point $x^{*}\in D$ is called

  * •

a maximizer of $f$ on $D$ if $x^{*}\in D$ and $f(x^{*})\geqslant f(x)$ for all
$x\in D$, and

  * •

a minimizer of $f$ on $D$ if $x^{*}\in D$ and $f(x^{*})\leqslant f(x)$ for all
$x\in D$.

Equivalently, $x^{*}\in D$ is a maximizer of $f$ on $D$ if
$f(x^{*})=\max_{x\in D}f(x)$, and a minimizer if $f(x^{*})=\min_{x\in D}f(x)$.
We define

$\operatornamewithlimits{argmax}_{x\in D}f(x):=\\{x^{*}\in D:f(x^{*})\geqslant
f(x)\text{ for all $x\in D$}\\}.$

The set $\operatornamewithlimits{argmin}_{x\in D}f(x)$ is defined analogously.

######  Example 6.1.18.

If $f(x)=x^{2}$ and $D=[-1,1]$, then $\operatornamewithlimits{argmax}_{x\in
D}f(x)=\\{-1,1\\}$, while $\operatornamewithlimits{argmin}_{x\in
D}f(x)=\\{0\\}$. In the second case, where the solution set is a singleton,
that is, a set with exactly one element, we write
$\operatornamewithlimits{argmin}_{x\in D}f(x)=0$ as well.

Let $f\colon D\to A\subset\mathbbm{R}$ be any given function. Prove the
following:

  1. (i)

If $g\colon A\to\mathbbm{R}$ is a strictly increasing function, then $x^{*}$
is a maximizer of $f$ on $D$ if and only if $x^{*}$ is a maximizer of $g\circ
f$ on $A$.

  2. (ii)

If $g\colon A\to\mathbbm{R}$ is a strictly decreasing function, then $x^{*}$
is a maximizer of $f$ on $D$ if and only if $x^{*}$ is a minimizer of $g\circ
f$ on $A$.

Regarding part (i), let $f$ and $g$ be as stated. Since $g$ is strictly
increasing, we have

$f(x^{*})\geqslant f(x),\;\;\forall\,x\in D\quad\iff\quad g(f(x^{*}))\geqslant
g(f(x)),\;\;\forall\,x\in D.$

This proves the equivalence claimed in part (i). (Note why the strictly
increasing property of $g$ cannot be weakened here.) The proof of (ii) is
similar, with the second equality reversed. One important special case of part
(ii) is that $x^{*}\in D$ is a maximizer of $f$ on $D$ if and only if $x^{*}$
is a minimizer of $-f$ on $D$. Hence, any maximization problem can be
converted into a minimization problem and vice-versa.

######  6.1.6.2 Convexity and Extrema

§ 6.1.6.1 discussed existence of optimizers. In this section we consider
uniqueness. The key observation is that, for convex and concave functions,
local optimizers are global optimizers. If $C\subset\mathbbm{R}^{n}$ and $f$
is a real-valued function on $C$, then $u^{*}\in C$ is a local minimizer of
$f$ on $C$ if there exists an open set $G$ in $C$ such that $u^{*}\in G$ and
$f(u^{*})\leqslant f(u)$ whenever $u\in G$. A local maximizer is defined
analogously. The next exercise highlights one of the most important facts
concerning computation of solutions to optimization problems in real-world
applications. It is especially valuable in high-dimensional settings, where
optimization problems can be very challenging. Show that, if
$C\subset\mathbbm{R}^{n}$ is convex, $f$ is convex and $u^{*}$ is a local
minimizer of $f$ on $C$, then $u^{*}$ is a minimizer of $f$ on $C$. Let $f$
and $C$ be as described and let $u^{*}$ be a local minimizer. Suppose,
contrary to the claim in the exercise, that there exists a point $u$ in $C$
such that $f(u)<f(u^{*})$. Then, by convexity, for each $\lambda$ in $[0,1]$,
we have

$f(\lambda u+(1-\lambda)u^{*})\leqslant\lambda
f(u)+(1-\lambda)f(u^{*})<f(u^{*}).$

Taking $\lambda\to 0$, we can find a point $v:=\lambda u+(1-\lambda)u^{*}$
arbitrarily close to $u^{*}$ such that $f(v)<f(u^{*})$. This contradicts the
definition of a local minimizer. Similarly, if $f$ is concave on $C$, then any
local maximizer is a global maximizer.

######  6.1.6.3 Multivariate Quadratic Objectives

§ 1.4.2.3 treated a one-dimensional quadratic optimization problem. Next we
treat $n$-dimensional problems of the same type.

######  Lemma 6.1.16.

If $H\in\mathbbm{M}^{n\times n}$ is positive definite, then, for any
$b\in\mathbbm{R}$ and $a\in\mathbbm{R}^{n}$,

$u^{*}:=H^{-1}a\text{ is the unique minimizer of
}q(u):=u^{\top}Hu-2u^{\top}a+b\text{ in }\mathbbm{R}^{n}.$

Prove that any local minimizer of $q$ in Lemma 6.1.16 is also a global
minimizer. (Hint: Use Exercise 6.1.5.2.) Complete the proof of Lemma 6.1.16 by
showing that $u^{*}$ is a local minimizer. It suffices to show that the
derivative of $q$ at $u^{*}$ is zero. Use the following facts from matrix
calculus:

$a\in\mathbbm{R}^{n}\text{ and }H\in\mathbbm{M}^{n\times
n}\quad\implies\quad\frac{\mathop{}\\!\mathrm{d}}{\mathop{}\\!\mathrm{d}u}u^{\top}a=a\;\text{
and
}\;\frac{\mathop{}\\!\mathrm{d}}{\mathop{}\\!\mathrm{d}u}u^{\top}Hu=(H+H^{\top})u.$

#####  6.1.7 Lagrangian Duality

If you have studied undergraduate economics, you will have used Lagrangian
methods to solve constrained optimization problems. The objective of this
section is to supply insight on when and why the method works, as well as to
highlight the connection between an original constrained problem and a so-
called “dual problem.” This connection yields deep insights in economics,
finance, statistical learning, artificial intelligence and many other fields.

######  6.1.7.1 Theory

Let $E$ be a subset of $\mathbbm{R}^{n}$ and let $f$ map $E$ to $\mathbbm{R}$.
We aim to solve

$\min_{x\in E}f(x)\;\text{ subject to }\;g(x)=0\text{ and }h(x)\leqslant 0.$
(6.14)

Here $g$ maps $E$ to $\mathbbm{R}^{m}$ and $h$ maps $E$ to $\mathbbm{R}^{k}$.
For example, the zero symbol in the statement $g(x)=0$ is a vector of zeros,
and the meaning is that $g_{i}(x)=0$ in $\mathbbm{R}$ for $i$ in $1,\ldots,m$.
The interpretation of the second constraint is analogous. Any $x\in E$ that
satisfies the constraints in (6.14) is called feasible. Let $F(g,h)$ be the
set of all feasible $x\in E$. A feasible point that attains the minimum in
(6.14) is called optimal for—or a solution to—the optimization problem. Our
first claim is that the constrained optimization problem (6.14) is equivalent
to the _un_ constrained problem

$P=\min_{x\in E}\,\max_{\theta\in\Theta}L(x,\theta)$ (6.15)

where $\theta:=(\lambda,\mu)$ and

$L(x,\theta)=L(x,\lambda,\mu):=f(x)+\sum_{i=1}^{m}\lambda_{i}g_{i}(x)+\sum_{i=1}^{k}\mu_{i}h_{i}(x).$
(6.16)

Here $\theta\in\Theta$ combines the vectors of Lagrange multipliers
$\lambda\in\mathbbm{R}^{m}$ and $\mu\in\mathbbm{R}^{k}_{+}$, where
$\Theta:=\mathbbm{R}^{m}\times\mathbbm{R}^{k}_{+}$. By _equivalent to,_ we
mean that

  1. (i)

$\hat{f}(x):=\max_{\theta\in\Theta}L(x,\theta)$ satisfies $\hat{f}=f$ on
$F(g,h)$,

  2. (ii)

$\hat{f}=+\infty$ on the complement of $F(g,h)$ and

  3. (iii)

together $\hat{f}$ and $f$ satisfy

$P:=\min_{x\in E}\hat{f}(x)=\min_{x\in F(g,h)}\hat{f}(x)=\min_{x\in
F(g,h)}f(x).$ (6.17)

The first equality in (6.17) is by definition. The second two follow from (ii)
and (i) respectively. Hence we need only verify (i)–(ii). Show that (i)–(ii)
both hold. You can assume that extrema exist. Regarding the first claim,
suppose that $g(x)=0$ and $h(x)\leqslant 0$, so that $x\in F(g,h)$. In this
case,

$\hat{f}(x)=\max_{\theta\in\Theta}L(x,\theta)=f(x)+\max_{\lambda\in\mathbbm{R}^{m}}\sum_{i}\lambda_{i}g_{i}(x)+\max_{\mu\in\mathbbm{R}^{k}_{+}}\sum_{i}\mu_{i}h_{i}(x)=f(x).$
(6.18)

Hence $\hat{f}=f$ on $F(g,h)$ and claim (i) is verified. Regarding claim (ii),
suppose that $g_{i}(x)$ deviates from zero for some $i$. Then
$\max_{\lambda\in\mathbbm{R}^{m}}\sum_{i}\lambda_{i}g_{i}(x)$ equals
$+\infty$, so $\hat{f}(x)=+\infty$. In addition, if $h_{i}(x)>0$ for some $i$,
then $\max_{\mu\in\mathbbm{R}^{k}_{+}}\sum_{i}\mu_{i}h_{i}(x)=+\infty$, so,
once again $\hat{f}(x)=+\infty$. We have confirmed that $\hat{f}=+\infty$
whenever $x\notin F(g,h)$. The function $L$ in problem (6.16) is usually
called the Lagrangian. The $P$ in (6.15) stands for primal. So far we have
shown that the original constrained problem and the primal problem are the
same. The next step is to pair the primal problem with its dual problem, which
is obtained by reversing the order of min and max in the primal:

$D=\max_{\theta\in\Theta}\;\min_{x\in E}\;L(x,\theta).$ (6.19)

The dual problem has two attractive features. One is that, when minimizing
with respect to $x$, we do not need to concern ourselves with the constraints
on $x$ in the original formulation (6.14). The second is that, since
$L(x,\theta)$ is linear in $\theta$, and since we are minimizing a family of
these functions with respect to $x$, the minimizer is a concave function (see
page 6.1.5.2). Concavity assists maximization, which is the next step in
solving $D$. Show that $D\leqslant P$ always holds. Pick any $x^{\prime}\in E$
and $\theta\in\Theta$. We have
$L(x^{\prime},\theta)\geqslant\min_{x}L(x,\theta)$, so

$\max_{\theta}L(x^{\prime},\theta)\geqslant\max_{\theta}\min_{x}L(x,\theta).$
$\therefore\quad\min_{x}\max_{\theta}L(x,\theta)\geqslant\max_{\theta}\min_{x}L(x,\theta).$

The result $D\leqslant P$ in Exercise 6.1.7.1 is called weak duality. If
$P=D$, then strong duality is said to hold. Unlike weak duality, strong
duality requires conditions on the primitives. Evidently strong duality holds
if and only if it is valid to reverse the order of the min and max operators
in the definition of the primal (or the dual). Results of this kind are called
_min-max theorems_. Such theorems hold at “saddle points” of the function $L$.
The next section explains.

######  6.1.7.2 Saddle Points and Duality

We seek necessary and sufficient conditions for strong duality, which will
lead to a characterization of minimizers for the original constrained problem.
To do so, we again take $\theta:=(\lambda,\mu)$ and
$\Theta:=\mathbbm{R}^{m}\times\mathbbm{R}^{k}_{+}$, so that

$P=\min_{x\in E}\max_{\theta\in\Theta}L(x,\theta)\quad\text{and}\quad
D=\max_{\theta\in\Theta}\min_{x\in E}L(x,\theta).$ (6.20)

A pair $(x^{*},\theta^{*})$ in $E\times\Theta$ is called a saddle point of $L$
if

$L(x^{*},\theta)\leqslant L(x^{*},\theta^{*})\leqslant
L(x,\theta^{*})\quad\text{for all}\quad(x,\theta)\in E\times\Theta.$ (6.21)

A depiction of a saddle point of a given bivariate function $(x,\theta)\mapsto
L(x,\theta)\in\mathbbm{R}$ is given in Figure 6.10. The left hand side of the
top panel is a 3D visualization, and the right hand side is a contour plot of
the same function. The saddle point is at the center.

Figure 6.10:  A saddle point $(x^{*},\theta^{*})$ of the function $L$

When the extrema in (6.20) exist, we have the following result:

######  Theorem 6.1.17.

If $L$ has a saddle point $(x^{*},\theta^{*})$ in $E\times\Theta$, then strong
duality holds. Moreover, $P=D=L(x^{*},\theta^{*})$ and $x^{*}$ solves the
constrained optimization problem (6.14).

###### Proof.

Let $(x^{*},\theta^{*})$ be a saddle point $(x^{*},\theta^{*})$ of $L$ in
$E\times\Theta$. We have, for all $(x,\theta)\in E\times\Theta$,

$P\leqslant\max_{\theta}L(x^{*},\theta)\leqslant
L(x^{*},\theta^{*})\leqslant\min_{x}L(x,\theta^{*}),$

where the first inequality is by definition and the second two are by the
saddle point property. The last term is clearly dominated by $D$, so we
conclude that $P\leqslant L(x^{*},\theta^{*})\leqslant D$. But, by weak
duality, we also have $D\leqslant P$, so $P=L(x^{*},\theta^{*})=D$. Finally,
to confirm that $x^{*}$ solves the original constrained problem, suppose to
the contrary that there exists an $x_{0}\in E$ that satisfies the constraints
and yields $f(x_{0})<f(x^{*})$. Since the constraints are satisfied at both
$x_{0}$ and $x^{*}$, we can apply (6.18) on page 6.18 to obtain
$\max_{\theta\in\Theta}L(x_{0},\theta)=f(x_{0})$ and
$\max_{\theta\in\Theta}L(x^{*},\theta)=f(x^{*})$. Hence the second inequality
of the saddle point condition implies

$f(x^{*})=\max_{\theta\in\Theta}L(x^{*},\theta)\leqslant\max_{\theta\in\Theta}L(x_{0},\theta)=f(x_{0}).$

This contradicts the hypothesis that $f(x_{0})<f(x^{*})$. ∎

Theorem 6.1.17 tells us that to solve the constrained optimization problem and
establish strong duality, we need only obtain a saddle point of the
Lagrangian.

######  6.1.7.3 Karush, Kuhn and Tucker

For well behaved problems, saddle points can be identified via well known
first-order conditions, called the Karush–Kuhn–Tucker (KKT) conditions. To
state them, we return to the original problem (6.14) and write $\theta$
explicitly as $(\lambda,\mu)$, so that $(x^{*},\lambda^{*},\mu^{*})\in
E\times\mathbbm{R}^{m}\times\mathbbm{R}^{k}_{+}$ satisfies the saddle point
condition if

$L(x^{*},\lambda,\mu)\leqslant L(x^{*},\lambda^{*},\mu^{*})\leqslant
L(x,\lambda^{*},\mu^{*})\quad\text{for all}\quad x\in
E,\lambda\in\mathbbm{R}^{m}\text{ and }\mu\in\mathbbm{R}^{k}_{+}.$

The KKT conditions are met by $(x^{*},\lambda^{*},\mu^{*})\in
E\times\mathbbm{R}^{m}\times\mathbbm{R}^{k}_{+}$ if $x^{*}\in F(g,h)$,

$\nabla f(x^{*})+\sum_{i=1}^{m}\lambda^{*}_{i}\nabla
g_{i}(x^{*})+\sum_{i=1}^{k}\mu^{*}_{i}\nabla h_{i}(x^{*})=0\quad\text{and}$
(6.22) $\mu^{*}_{i}h_{i}(x^{*})=0\quad\text{for all }i\in[k].$ (6.23)

Here we are requiring that $f,g,h$ are all differentiable at $x^{*}$ and, for
a given function $q\colon E\to\mathbbm{R}$, we use $\nabla$ to represent the
vector of partial derivatives. Equation (6.22) requires that the derivative of
the Lagrangian with respect to $x$ is zero at $x^{*}$. The second condition is
called the complementary slackness condition. The KKT conditions are nothing
more than saddle point conditions. Condition (6.22) is the first order
condition for an interior minimizer of the Lagrangian with respect to $x$, at
the point $(x^{*},\theta^{*})$, which tries to identify the local minimum
visualized in the lower right panel of Figure 6.10. The complementary
slackness condition is also needed because if $\mu^{*}_{i}h_{i}(x^{*})=0$
fails at some $i$, then $\mu^{*}_{i}h_{i}(x^{*})<0$ must hold, in which case
we could strictly increase the Lagrangian by shifting $\mu^{*}_{i}$ to $0$.
This violates the saddle point property. If enough regularity conditions hold,
then the KKT conditions exactly identify extremal points. Here is one example,
which is proved in Chapter 8 of Matousek and Gärtner, (2007).

######  Theorem 6.1.18 (Karush–Kuhn–Tucker).

If $E$ is open, $f$ is continuously differentiable and convex, and both $g$
and $h$ are affine functions, then $x^{*}$ minimizes $f$ on $F(g,h)$ if and
only if there exists a pair
$(\lambda^{*},\mu^{*})\in\mathbbm{R}^{m}\times\mathbbm{R}^{k}_{+}$ such that
the KKT conditions hold.

####  6.2 Solutions

### Index

  * Absorbing §1.4.1.3
  * Accessible §1.4.1.3
  * Adjacency matrix §1.4.2.2
  * Aperiodic §1.4.1.4
  * Basis §6.1.4.2
  * Bellman equation §3.1.1.2
  * Bellman operator §3.1.2.3
  * Big O notation §6.1.3
  * Bijection 3rd item
  * Book value §5.2.3.1
  * Bounded §6.1.3.3
    * sequence §6.1.3.1
  * Canonical basis vectors Example 6.1.14
  * Cartesian product §6.1.1.1
  * Cauchy sequence §6.1.3.2
  * cdf §1.3.2
  * Chapman–Kolmogorov equation §4.1.1.4
  * characteristic polynomial §1.2.1.1
  * Closed set §6.1.3.3
  * codomain §6.1.1.3
  * Column space Example 6.1.13
  * Communication (graphs) §1.4.1.3
  * Compact §6.1.3.3
  * Competitive equilibrium §3.3.3.3
  * Complementary slackness §3.2.2.7, §6.1.7.3
  * Complex numbers §6.1.1.8
  * Composition §6.1.1.5
  * Concave function §6.1.5.2
  * Cone §6.1.5.1
  * Consensus §4.2.4.2
  * Contracting §5.1.1.1
  * Convergence §6.1.3.1, §6.1.3.2
  * Convergence of matrices §2.3.2.5
  * Convergence of vectors §2.3.1.2
  * Convex cone §6.1.5.1
  * Convex function §6.1.5.2
  * Convex set §6.1.5.1
  * Countable §6.1.1.5
  * Counter CDF (CCDF) §1.3.2
  * coupling §3.3.1.3
  * Cumulative distribution function §1.3.2
  * Cycle §1.4.1.4
  * De Groot learning §4.2.4
  * Decreasing 2nd item
  * Degree distribution §1.4.4.1
  * Determinant §6.1.4.5
  * Diagonalizable §1.2.1.2
  * Digraph §1.4.1.1
  * Directed graph §1.4.1.1
  * Directed path §1.4.1.3
  * Directed walk §1.4.1.3
  * Distributions §1.3.1.1
  * Domain §6.1.1.3
  * Domar weight §2.2.1.3
  * Dominant eigenvector §1.2.3.2
  * Dual §6.1.7.1
  * Dual problem §3.2.2.5
  * Edges 2nd item
  * Eigendecomposition §1.2.1.2
  * Eigenpair §1.2.1.1
  * Eigenspace §1.2.1.1
  * Eigenvalue §1.2.1.1
  * Eigenvector §1.2.1.1
  * Eigenvector centrality §1.4.3.4, §1.4.3.4
  * Epigraph §6.1.5.2
  * Equivalence §2.3.1.2, §2.3.2.5
  * Equivalence relation §6.1.1.2
  * Ergodic §4.2.1.2
  * Euler’s formula §6.1.1.8
  * Eventually contracting §5.1.1.3
  * Extreme point §3.2.2.8, §6.1.5.1
  * Fixed point §5.1, §6.1.1.6
  * Flow network §3.1.2
  * Frobenius inner product §2.3.2.2
  * Frobenius norm §2.3.2.2
  * Function §6.1.1.3
    * real-valued §6.1.1.5
  * Gelfand’s formula §2.3.3.1
  * Globally stable §4.2.2.1
  * Halfspace 2nd item
  * Harmonic §4.2.1.1
  * Heavy-tailed §1.3.2.1
  * Herfindahl index §2.2.2.3, §2.2.3.1
  * Hub centrality §1.4.3.2
  * Hyperplane 1st item
  * Imaginary §6.1.1.8
  * In-degree centrality §1.4.3.3
  * Incidence matrix §3.3.4.2
  * Increasing 1st item
  * Increasing function §6.1.2.3
  * Indicator §6.1.1.5
  * Initial condition §4.1.1.2
  * Inner product 1st item
    * Frobenius §3.3.1.3
  * Interior §6.1.3.3
  * Inverse §6.1.4.5
  * Invertible §6.1.4.5
  * Irreducible 1st item
  * Jensen’s inequality §6.1.5.2
  * Kantorovich duality §3.3.2
  * Karush–Kuhn–Tucker §6.1.7.3
  * Katz centrality §1.4.3.5, §1.4.3.5
  * Kernel §6.1.4.1
  * Kronecker product §3.3.1.4
  * Lagrange multiplier §6.1.7.1
  * Lagrangian §6.1.7.1
  * Law of large numbers §4.2.1.3
  * Law of total probability §1.3.1.1
  * Leontief inverse §2.1.2.2, §2.2.1.1
  * Light-tailed §1.3.2.1
  * Linear §6.1.4.3
  * Linear combination §6.1.4.1
  * Linear hyperplane §6.1.4.4
  * Linearly independent §6.1.4.1
  * Local maximizer §6.1.6.2
  * Local minimizer §6.1.6.2
  * Lognormal distribution Example 1.3.2
  * Marginal distribution §4.1.2
  * Markov chain §4.1.1.2
  * Markov model §4.1.1
  * Markov–Dobrushin coefficient §4.2.3.1
  * Martingale §4.2.1.1
  * Matrix norm §2.3.2.1
  * Maximizer 1st item
  * Maximum §6.1.6.1
  * Minimizer 2nd item
  * Minimum §6.1.6.1
  * Minimum cost-to-go §3.1.1.2
  * Minkowski’s inequaltiy §2.3.1.1
  * Modulus §6.1.1.8
  * Moment §1.3.2.1
  * Moment generating function §1.3.2.1
  * Monge map §3.3.1.1
  * Monotone
    * sequence §6.1.3.1
  * Nash equilibrium §1.4.2.3
  * Negative definite 4th item
  * Negative semidefinite 3rd item
  * Neumann series lemma §1.2.2.2
  * Nodes 1st item
  * Nonreal §6.1.1.8
  * Nonsingular §6.1.4.5
  * Norm §2.3.1.1
  * Normal distribution §1.3.2.1
  * Normal vector §6.1.4.4
  * NSL §1.2.2.2
  * Null space §6.1.4.1
  * One-to-one function 1st item
  * Onto function 2nd item
  * Open set §6.1.3.3
  * Operator norm §2.3.2.3
  * Optimal plan §3.3.1.3
  * Optimal policy §3.1.2.3
  * Order-preserving §6.1.2.3
  * Orthogonal §6.1.4.6
  * Orthogonal complement §6.1.4.6
  * Orthogonal set §6.1.4.6
  * Orthogonally diagonalizable §1.2.1.2
  * Orthonormal
    * matrix §6.1.4.6
    * set §6.1.4.6
  * Orthonormal basis §6.1.4.6
  * out-degree centrality §1.4.3.3
  * Output multiplier §2.1.3.4
  * $P$-Markov §4.1.1.2
  * Pareto distribution Example 1.3.3
  * Pareto tail §1.3.2.2
  * Partial order §6.1.2.1
  * Partially ordered set §6.1.2.1
  * Periodic digraph §1.4.1.4
  * Perron projection §1.2.3.2
  * Perron root §1.2.3.2
  * Pointwise convergence §2.3.1.2
  * Pointwise order Example 6.1.7, Example 6.1.8
  * Pointwise partial order §1.2.3.1
  * Polar form §6.1.1.8
  * Policy function §3.1.2.1
  * Positive cone §6.1.5.1
  * Positive definite 2nd item
  * Positive semidefinite 1st item
  * Power law §1.3.2.2
  * Power set §6.1.1.1
  * Preferential attachment §1.4.4.3
  * Primal §6.1.7.1
  * Primitive matrix 2nd item
  * Pythagorean law §6.1.4.6
  * Range §6.1.1.3
  * Rank §6.1.4.2
  * real numbers §6.1.1.1
  * Real part §6.1.1.8
  * Reflexivity §6.1.1.2
  * Relation §6.1.1.2
  * Saddle point §6.1.7.2
  * Scale-free network §1.4.4.1
  * Scale-free networks §1.4.4
  * Self-map §5.1, §6.1.1.6
  * Sequence §6.1.3
  * Series §6.1.3.1
  * Shortest path §3.1
  * Similar matrix §1.2.1.5
  * Simple eigenvalue §1.2.1.1
  * Slack variables §3.2.2.4
  * Span §6.1.4.1
  * Spectral gap §4.2.2.3
  * Spectral radius §1.2.2.1
  * Spectrum §1.2.1.1
  * Standard form §3.2.2.4, §3.3.1.4
  * State space §4.1.1
  * Stationary §4.1.3.1
  * Stationary distribution §1.3.1.3, §4.1.3.1
  * Stochastic matrix §1.3.1.3
  * Strictly decreasing 2nd item
  * Strictly increasing 1st item