6 Appendix

6.1Math 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 & 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.1Sets and Functions¶

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

6.1.1.1Sets¶

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

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

Let $\NN$ be the natural numbers, $\ZZ$ be the integers, $\QQ$ be the rational numbers and $\RR$ be the reals (i.e., the union of the rational and irrational numbers). For $x, y$ in $\RR$, we let

Absolute value is $|x| := x \vee (-x)$. For $n \in \NN$ we set $\natset{n} := \{1, \ldots, n\}$.

We make use of the following elementary facts: For all $a, b, c \in \RR$,

• $|a + b| \leq |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 | \leq |a - b|$.

• $|a \vee c - b \vee c | \leq |a - b|$.

The first item is called the triangle inequality. Also, if $a, b, c \in \RR_+$, then

6.1.1.2Equivalence 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$.

6.1.1.3Functions¶

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

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

• one-to-one if $f(a) = f(a')$ implies $a = a'$,

• onto if $\range(f) = B$, and

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

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 $\range(f) = (0,1)$. This function is not one-to-one, however. For example, $f(1/4)=f(3/4)=3/4$.

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.

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

Here is a nice logical exercise that turns out to be useful when we solve linear inverse problems.

6.1.1.5Real-Valued Functions¶

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

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 $\1\{P\}$ and takes value 1 (resp., 0) if $P$ is true (resp., false).

If $A \subset S$, where $S$ is any set, then $\1_A(x) := \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 $\NN$. 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, $\ZZ$ and $\QQ$ are countable, whereas $\RR$ and every nontrivial interval in $\RR$ 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

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

Figure 6.3 illustrates.

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.6Fixed 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$.

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.

6.1.1.7Vectors¶

An $n$-vector $x$ is a tuple of $n$ numbers $x = (x_1, \ldots, x_n)$ where $x_i \in \RR$ for each $i \in \natset{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 \RR$ and $x, y \in \RR^n$,

We let $\RR^n$ be the set of all $n$-vectors and $\matset{n}{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 \RR^n$ is defined as $\inner{ x, y} := \sum_{i=1}^n x_i y_i$.

• The Euclidean norm of $x \in \RR^n$ is $\|x \| := \sqrt{\inner{x, x}}$.

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

6.1.1.8Complex Numbers¶

We recall some elementary facts about $\CC$, the set of complex numbers.

Each element of $\CC$ can be understood as a point $(a, b) \in \RR^2$. In fact $\CC$ is just $\RR^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 $\real (a, b) = a$ and $\imag (a, b) = b$ and called the real and nonreal (or imaginary) part respectively. The symbol $i$ represents the point $(0, 1) \in \CC$. As is traditional, in the context of complex numbers, the complex number $(a, 0) \in \CC$ is often written more simply as $a$. With addition and scalar multiplication defined pointwise, this means that, as expected,

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

Note that, under this rule and our conventions, $i^2 = (0, 1)(0, 1) = (-1, 0) = -1$.

As in the real case, the exponential $\me^z$ is defined for $z \in \CC$ by $\sum_{k \geq 0} z^k/(k!)$. It can be shown that, under this extension, the exponential function continues to enjoy the additive property $\me^{z_1 + z_2} = \me^{z_1} \me^{z_2}$. As a result, $\me^{a + ib} = \me^a \me^{ib}$.

Rather than providing its coordinates, another way to represent a vector $z = (a, b) \in \RR^2$, and hence in $\CC$, is by providing a pair $(r, \phi)$ where $r > 0$ is understood as the length of the vector and $\phi \in [0, 2\pi)$ is the angle. This translates to Euclidean coordinates via

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

Figure 6.5 translates $\CC \ni (1, \sqrt{3}) = 1 + i \sqrt{3}$ into polar coordinates $2 \me^{i (\pi/3)}$.

The advantage of these representations is clear when we multiply, since the rule

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

6.1.2Order¶

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.1Partial 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$,

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

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

6.1.2.2Pointwise 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 $\RR^d$, we set

(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 Section 6.1.1.1 also hold for vectors in $\RR^d$. (For example, $|a + b| \leq |a| + |b|$ for any $a, b, c \in \RR^d$.)

6.1.2.3Monotonicity¶

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

If $P = Q = \RR$ and $\preceq$ and $\trianglelefteq$ are both equal to $\leq$, the standard order on $\RR$, 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.^[2]

In addition, if $S = g$ maps $A \subset \RR$ into $\RR$, 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.3Convergence¶

Let’s now recall the basics of convergence and continuity.

Given any set $S$, an $S$-valued sequence $(x_n) := (x_n)_{n \in \NN}$ is a function $n \mapsto x_n$ from $\NN$ to $S$. If $S=\RR$, we call $(x_n)$ a real-valued sequence. A subsequence of $(x_n)_{n \in \NN}$ is a sequence of the form $(x_{\sigma(n)})_{n \in \NN}$ where $\sigma$ is a strictly increasing function from $\NN$ 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| \leq M g_n$ for all $n \in \NN$.

6.1.3.1Metric Properties of the Real Line¶

The following definition is fundamental to what follows: a real-valued sequence $(x_n)$ converges to $x \in \RR$ and write $x_n \to x$ if

Let’s state some elementary limit laws that are used without comment throughout. (You can review the proofs in sources such as Bartle & Sherbert (2011)).

A sequence $(x_n)$ is called bounded if there is an $M \in \RR$ such that $|x_n| \leq M$ for all $n \in \NN$. It is called

• monotone increasing if $x_n \leq x_{n+1}$ for all $n \in \NN$, and

• monotone decreasing if $x_n \geq 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 $\RR$.

The intuitive meaning of the “if” part of Theorem 6.1.3 is that monotone bounded sequences always converge to some point in $\RR$ because $\RR$ contains no gaps. This statement is closely related to the “completeness” property of the real line, which is discussed in Bartle & Sherbert (2011) and many other texts on real analysis.

Next let’s consider series. Given a sequence $(x_n)$ in $\RR$, we set

More generally, given arbitrary countable $S$ and $g \in \RR^S$, we write $\sum_{x \in S} g(x) = M$ if there exists an enumeration $(x_n)_{n \in \NN}$ of $S$ such that $\sum_{n \geq 1} |g(x_n)|$ is finite and, in addition, $\sum_{n \geq 1} g(x_n) = M$.^[3]

6.1.3.2Metric Properties of Euclidean Space¶

Now we review the metric properties of $\RR^d$, for some $d \in \NN$, when distance between vectors $x, y \in \RR^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 $\RR^d$ is said to converge to $x \in \RR^d$ if

In this case we write $x_n \to x$. Figure 6.6 shows a sequence converging to the origin in $\RR^3$, with colder colors being later in the sequence.

Given any point $u \in \RR^d$ and $\epsilon > 0$, the $\epsilon$-ball around $u$ is the set

With this terminology, we can say that $(x_n)$ converges to $x \in \RR^d$ if the sequence $(x_n)$ is eventually in any $\epsilon$-ball around $x$.

A sequence $(x_n) \subset \RR^d$ is called Cauchy if, for all $\epsilon > 0$, there exists an $N \in \NN$ with $|x_n - x_m| < \epsilon$ whenever $n, m \geq N$.

It is a fundamental result of analysis, stemming from axiomatic properties of the reals, that the converse is also true:

6.1.3.3Topology¶

A point $u \in A \subset \RR^d$ is called interior to $A$ if there exists an $\epsilon > 0$ such that $B_\epsilon(u) \subset A$.

A subset $G$ of $\RR^d$ is called open in $\RR^d$ if every $u \in G$ is interior to $G$. A subset $F$ of $\RR^d$ is called closed if, given any sequence $(x_n)$ satisfying $x_n \in F$ for all $n \in \NN$ and $x_n \to x$ for some $x \in \RR^d$, the point $x$ is in $F$. In other words, $F$ contains the limit points of all convergent sequences that take values in $F$.

A subset $B$ of $\RR^d$ is called bounded if there exists a finite $M$ such that $\| b \| \leq M$ for all $b \in B$. A subset $K$ of $\RR^d$ is called compact in $\RR^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.4Continuity in Vector Space¶

If $A \subset \RR^d$, then $f \colon A \to \RR^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 $\RR^k$. If $f$ is continuous at all $x \in A$ then we call $f$ continuous on $A$.

More generally, every polynomial function is continuous on $\RR$. The elementary functions $\sin$, $\cos$, $\exp$ and $\log$ are all continuous on their domains.

The next lemma is helpful in locating fixed points.

6.1.4Linear Algebra¶

Next we review fundamental concepts and definitions from linear algebra.

6.1.4.1Subspaces and Independence¶

A subset $E$ of $\RR^n$ is called a linear subspace of $\RR^n$ if

In other words, $E$ is closed under the operations of addition and scalar multiplication; that is, (i) $\alpha \in \RR$ and $x \in E$ implies $\alpha x \in E$ and (ii) $x, y \in E$ implies $x+y \in E$.

A linear combination of vectors $v_1,\ldots, v_k$ in $\RR^n$ is a vector of the form

The set of all linear combinations of elements of $F \subset \RR^n$ is called the span of $F$ and written as $\Span F$.

Figure 6.7 shows the linear subspace spanned by the three vectors

The subspace $H$ in which these vectors lie is, in fact, the set of all $x \in \RR^3$ such that $\inner{x, c} = 0$, with $c=(-0.2, -0.1, 1)$. This plane is a two-dimensional object. While we make this terminology precise in Section 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.

A finite set of vectors $F := \{v_1, \ldots, v_k\} \subset \RR^n$ is called linearly independent if, for real scalars $\alpha_1, \ldots, \alpha_k$,

If $F$ is not linearly independent it is called linearly dependent.

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

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

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.

6.1.4.2Basis Vectors and Dimension¶

Let $V$ be a linear subspace of $\RR^n$. A set $B \subset V$ is called a basis for $V$ if $B$ is linearly independent and $\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 \RR^k$ such that

Indeed, if $u = \beta_1 v_1 + \cdots + \beta_k v_k$ is another representation, then, subtracting this equality from the last, we have

Because $S$ is assumed to be linearly independent, this yields $\alpha_i = \beta_i$ for all $i \in \natset{k}$.

Not surprisingly, given their name, the canonical basis vectors $E := \{\delta_1, \ldots, \delta_n\}$ serve as a basis for the whole space $\RR^n$. The representation (6.11), with coefficients $\alpha_i = \inner{x, \delta_i}$, is unique.

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 \RR^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 \matset{n}{k}$, $x \in \RR^k$ and $b \in \RR^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

See, for example, Chapter 2 of Aggarwal (2020) or Chapter 5 of Jänich (1994). In view of Exercise 6.1.26, for $A \in \matset{n}{k}$, we have $\rank A \leq k$. If $\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.

Part (ii) is related to Figure 6.7. The plane in that figure is 2-dimensional, as we confirm in Section 6.1.4.3 below. Any three vectors lying in the plane are linearly dependent.

6.1.4.3Linear 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 A u$ from $\RR^k$ to $\RR^n$ is called linear if

In this context, $A$ is sometimes called an operator rather than a function, but the meaning is the same.

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:

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 \neq 0$.

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

(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.4Linear Hyperplanes¶

In Exercise 6.1.21, you confirmed that, for a given nonzero $c \in \RR^n$, the subset of $\RR^n$ defined by $H := \setntn{x \in \RR^n}{\inner{c, x} = 0}$ is a linear subspace of $\RR^n$. Any set $H$ of this form is called a linear hyperplane in $\RR^n$. The vector $c$ is called the normal vector of the hyperplane.

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

6.1.4.5Nonsingular Linear Systems¶

A crucial task in applied modeling is solving linear systems such as $A x = 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 $\matset{n}{n}$ and suppose that $A B = B A = 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.

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

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(A B) = \det(A) \det(B)$,

• $\det(\alpha A) = \alpha^n \det A$ for all $\alpha \in \RR$, 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 $\RR^n$, and hence any $b \in \RR^n$ can be expressed uniquely as a linear combination of elements of these columns. In other words, there exists a unique $x \in \RR^n$ with $Ax=b$. The remaining points are just equivalent ways of saying that the columns of $A$ form a basis of $\RR^n$.

6.1.4.6Orthogonality¶

We recall that vectors $u,v$ in $\RR^n$ are called orthogonal and we write $u \perp v$ if $\inner{u, v} = 0$. For a linear subspace $L$ of $\RR^n$, we call $u \in \RR^n$ orthogonal to $L$ and write $u \perp L$ whenever $u \perp v$ for all $v \in L$.

A set of vectors $O \subset \RR^n$ is called an orthogonal set if any two distinct elements of $O$ are orthogonal. For any orthogonal set $O$, the Pythagorean law

always holds.

An orthogonal set $O \subset \RR^n$ is called an orthonormal set if $\| u \| = 1$ for all $u \in O$. If $L$ is a linear subspace of $\RR^n$, $O$ is orthonormal in $L$ and $\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 $\RR^n$.

A matrix $M$ is called an orthonormal matrix if $M \in \matset{n}{n}$ for some $n \in \NN$ and, in addition, the columns of $M$ form an orthonormal set in $\RR^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 $\RR^n$ form a basis of $\RR^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.

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

6.1.5Convexity 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.1Convexity and Polyhedra¶

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

In economic optimization problems, the convex sets within which we seek extrema are usually polyhedra. A polyhedron in $\RR^n$ is a set of the form

Equivalently, $P$ is a polyhedron in $\RR^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 \leq b_i$ for $i=1, \ldots, k$.