Linear Algebra and Matrices - A Primer in Econometric Theory

The previous chapter was relatively abstract but it sets us up nicely to study the kinds of practical problems from linear algebra that we encounter in statistics and econometrics. This chapter treats many of the core problems in linear algebra, frequently relating them back to our analysis of vectors and linear maps in chapter 2.

3.1Matrices and Linear Equations¶

Matrices provide a convenient way to organize data and algebraic operations. Let’s start with definitions.

3.1.1Basic Definitions¶

A $N \times K$ matrix is a rectangular array $\boldA$ of real numbers with $N$ rows and $K$ columns, written in the following way:

\boldA = \left( \begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1K} \\ a_{21} & a_{22} & \cdots & a_{2K} \\ \vdots & \vdots & & \vdots \\ a_{N1} & a_{N2} & \cdots & a_{NK} \end{array} \right)

The symbol $a_{nk}$ stands for the element in the $n$ th row of the $k$ th column. Often these elements represent coefficients in a system of linear equations, such as

\begin{array}{c} a_{11} x_1 + a_{12} x_2 + \cdots + a_{1K} x_K = b_1 \\ \vdots \\ a_{N1} x_1 + a_{N2} x_2 + \cdots + a_{NK} x_K = b_N \end{array}

(3.1)

For obvious reasons, $\boldA$ is also called a vector if either $N = 1$ or $K = 1$ . In the former case, $\boldA$ is called a row vector, while in the latter case it is called a column vector. When convenient, we will use the notation $\row_n \boldA$ to refer to the $n$ th row of $\boldA$ , and $\col_k \boldA$ to refer to its $k$ th column.

We extend the notation $\boldzero$ and $\boldone$ from vectors to matrices, in the sense that these symbols will also represent matrices with all elements equal to zero and one respectively. Dimensions will be stated explicitly or clear from context.

If $\boldA$ is $N \times K$ and $N = K$ , then $\boldA$ is called square. For an $N \times N$ matrix $\boldA$ , the $N$ elements of the form $a_{nn}$ for $n=1,\ldots,N$ are called the principal diagonal:

\left( \begin{array}{cccc} \red{a_{11}} & a_{12} & \cdots & a_{1N} \\ a_{21} & \red{a_{22}} & \cdots & a_{2N} \\ \vdots & \vdots & & \vdots \\ a_{N1} & a_{N2} & \cdots & \red{a_{NN}} \\ \end{array} \right)

The unique $N \times N$ matrix with ones on the principle diagonal and zeros elsewhere is called the identity matrix, and denoted by $\boldI$ :

\boldI := \left( \begin{array}{cccc} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & & \vdots \\ 0 & 0 & \cdots & 1 \\ \end{array} \right)

Note that $\col_n \boldI = \bolde_n$ , the $n$ th canonical basis vector in $\RR^N$ .

Just as was the case for vectors, a number of algebraic operations are defined for matrices. The first two, scalar multiplication and addition, are immediate generalizations of the vector case: For $\gamma \in \RR$ , we let

\gamma \left( \begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1K} \\ a_{21} & a_{22} & \cdots & a_{2K} \\ \vdots & \vdots & & \vdots \\ a_{N1} & a_{N2} & \cdots & a_{NK} \\ \end{array} \right) := \left( \begin{array}{cccc} \gamma a_{11} & \gamma a_{12} & \cdots & \gamma a_{1K} \\ \gamma a_{21} & \gamma a_{22} & \cdots & \gamma a_{2K} \\ \vdots & \vdots & & \vdots \\ \gamma a_{N1} & \gamma a_{N2} & \cdots & \gamma a_{NK} \\ \end{array} \right)

while

\left( \begin{array}{ccc} a_{11} & \cdots & a_{1K} \\ a_{21} & \cdots & a_{2K} \\ \vdots & \vdots & \vdots \\ a_{N1} & \cdots & a_{NK} \\ \end{array} \right) + \left( \begin{array}{ccc} b_{11} & \cdots & b_{1K} \\ b_{21} & \cdots & b_{2K} \\ \vdots & \vdots & \vdots \\ b_{N1} & \cdots & b_{NK} \\ \end{array} \right) := \left( \begin{array}{ccc} a_{11} + b_{11} & \cdots & a_{1K} + b_{1K} \\ a_{21} + b_{21} & \cdots & a_{2K} + b_{2K} \\ \vdots & \vdots & \vdots \\ a_{N1} + b_{N1} & \cdots & a_{NK} + b_{NK} \\ \end{array} \right)

Addition is only defined for matrices that have identical shape.

The matrix product $\boldC = \boldA \boldB$ of matrices $\boldA$ and $\boldB$ is formed by taking as its $i,j$ th element the inner product of the $i$ th row of $\boldA$ and the $j$ th column of $\boldB$ . That is,

c_{ij} = \inner{\row_i \boldA,\, \col_j \boldB} = \sum_{k=1}^K a_{ik} b_{kj}

Here’s the picture for $i=j=1$ :

\left( \begin{array}{ccc} \red{a_{11}} & \red{\cdots} & \red{a_{1K}} \\ a_{21} & \cdots & a_{2K} \\ \vdots & \vdots & \vdots \\ a_{N1} & \cdots & a_{NK} \\ \end{array} \right) \left( \begin{array}{ccc} \red{b_{11}} & \cdots & b_{1J} \\ \red{b_{21}} & \cdots & b_{2J} \\ \red{\vdots} & \vdots & \vdots \\ \red{b_{K1}} & \cdots & b_{KJ} \\ \end{array} \right) = \left( \begin{array}{ccc} \red{c_{11}} & \cdots & c_{1J} \\ c_{21} & \cdots & c_{2J} \\ \vdots & \vdots & \vdots \\ c_{N1} & \cdots & c_{NJ} \\ \end{array} \right)

Since inner products are only defined for vectors of equal length, we need the length of the rows of $\boldA$ to be equal to the length of the columns of $\boldB$ . In other words, if $\boldA$ is $N \times K$ and $\boldB$ is $J \times M$ , then we require $K = J$ . The resulting matrix $\boldA \boldB$ is $N \times M$ . Here’s the rule to remember:

\boldA \text{ is } N \times K \text{ and } \boldB \text{ is } K \times M \; \implies \; \boldA \boldB \text{ is } N \times M

Matrix multiplication is not commutative: $\boldA \boldB$ and $\boldB \boldA$ are not in general equal. In most other ways it behaves like ordinary multiplication:

Here and below we use the word conformable to indicate dimensions are such that the operation in question makes sense. For example, two matrices are conformable for addition if they have the same number of rows and columns.

The $k$ th power of a square matrix $\boldA$ is defined as

\boldA^k := \underbrace{\boldA \cdots \boldA}_{k \text{ terms}}

If $\boldB$ is such that $\boldB^2 = \boldA$ , then $\boldB$ is called the square root of $\boldA$ and written $\sqrt{\boldA}$ .

Before going further, let’s state the fundamental connection between matrix multiplication and the more elementary notion of linear combinations of vectors, as introduced in Section 2.1.2: Given $N \times K$ matrix $\boldA$ and $K \times 1$ column vector $\boldx$ , the product $\boldA \boldx$ is an $N \times 1$ column vector formed as a linear combination of the columns of $\boldA$ , with scalars $x_1, \ldots, x_K$ . In symbols,

\begin{aligned} \boldA \boldx & = \left( \begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1K} \\ a_{21} & a_{22} & \cdots & a_{2K} \\ \vdots & \vdots & & \vdots \\ a_{N1} & a_{N2} & \cdots & a_{NK} \end{array} \right) \left( \begin{array}{c} x_1 \\ x_2 \\ \vdots \\ x_K \end{array} \right) \\ & = x_1 \left( \begin{array}{c} a_{11} \\ a_{21} \\ \vdots \\ a_{N1} \end{array} \right) + x_2 \left( \begin{array}{c} a_{12} \\ a_{22} \\ \vdots \\ a_{N2} \end{array} \right) + \cdots + x_K \left( \begin{array}{c} a_{1K} \\ a_{2K} \\ \vdots \\ a_{NK} \end{array} \right) \\ & = \sum_{k=1}^K x_k \col_k \boldA \end{aligned}

3.1.2Matrices as Maps¶

One of the most useful ways to think about matrices is as maps from one vector space to another. In particular, an $N \times K$ matrix $\boldA$ can be thought of as a map sending a vector $\boldx \in \RR^K$ into a new vector $\boldy = \boldA \boldx$ in $\RR^N$ . As the next theorem shows, these maps are always linear. In fact, they are the only linear functions. In other words, the set of linear functions from $\RR^K$ to $\RR^N$ and the set of $N \times K$ matrices are in one-to-one correspondence:

Proof

((i) $\implies$ (ii)) Let $T \colon \RR^K \to \RR^N$ be linear. We aim to construct a matrix $\boldA$ such that $T\boldx = \boldA \boldx$ for all $\boldx \in \RR^K$ . As usual, let $\bolde_k$ be the $k$ th canonical basis vector in $\RR^K$ . Define an $N \times K$ matrix $\boldA$ by $\col_k \boldA = T\bolde_k$ . Pick any $\boldx \in \RR^K$ . We can also write $\boldx = \sum_{k=1}^K x_k \bolde_k$ , where $x_k$ is the $k$ th element of $\boldx$ . By linearity, we have

T\boldx = \sum_{k=1}^K x_k T \bolde_k = \sum_{k=1}^K x_k \col_k \boldA

This is just $\boldA \boldx$ , as shown in Section 3.1.1.

((ii) $\implies$ (i)) Fix $N \times K$ matrix $\boldA$ and consider the function $T \colon \RR^K \to \RR^N$ defined by $T \boldx = \boldA \boldx$ . Pick any $\boldx$ , $\boldy$ in $\RR^K$ , and any scalars $\alpha$ and $\beta$ . The rules of matrix arithmetic (see fact 3.1.1) tell us that

T(\alpha \boldx + \beta \boldy) := \boldA (\alpha \boldx + \beta \boldy) = \boldA \alpha \boldx + \boldA \beta \boldy = \alpha \boldA \boldx + \beta \boldA \boldy =: \alpha T\boldx + \beta T\boldy

Hence $T$ is linear. ◻

When we consider the problem of solving a system of linear equations such as $\boldA \boldx = \boldb$ , the first issue we need to concern ourselves with is existence. Can we find an $\boldx$ that satisfies this equation, for any given $\boldb$ ? A bit of thought will convince you that this is the same question as: Is the corresponding linear map $T\boldx = \boldA \boldx$ an onto function? (See Section 15.2 for the definition.) Equivalently, is $\range T$ equal to all of $\RR^N$ ?

The range of $T$ is all vectors of the form $T\boldx = \boldA \boldx$ where $\boldx$ varies over $\RR^K$ . We just saw in Section 3.1.1 that, for any $\boldx \in \RR^K$ , we have $\boldA \boldx = \sum_{k=1}^K x_k \col_k \boldA$ . It follows that $\range T$ is equal to the column space of $\boldA$ , which is by definition the span of the columns of $\boldA$ . We represent it by the symbol

\colspace \boldA := \Span \{ \col_1 \boldA, \ldots, \col_K \boldA \}

(3.2)

To summarize the preceding discussion, we have

\colspace \boldA = \range T = \setntn{\boldA \boldx}{ \boldx \in \RR^K}

How large is the column space of a given matrix? To answer that question, we have to say what "large" means. In the context of linear algebra, size of subspaces is usually measured by dimension. The dimension of $\colspace \boldA$ is known as the rank of $\boldA$ . That is,

\rank \boldA := \dim \colspace \boldA

$\boldA$ is said to have full column rank if $\rank \boldA$ is equal to $K$ , the number of its columns. The reason we say “full” rank here is that, by definition, $\colspace \boldA$ is the span of $K$ vectors. Hence, by part (i) of theorem 2.1.6, we must have $\dim \colspace \boldA \leq K$ . In other words, the rank of $\boldA$ is less than or equal to $K$ . $\boldA$ is said to have full column rank when this maximum is achieved.

When is this maximum achieved? By part (ii) of theorem 2.1.6, this will be the case precisely when the columns of $\boldA$ are linearly independent. Let’s state this as a fact:

The last equivalence follows from theorem 2.1.1.

3.1.3Square Matrices and Invertibility¶

Perhaps the most common problem in linear algebra is solving systems of linear equations. A generic representation is $\boldA \boldx = \boldb$ , where $\boldx$ contains the unknowns and $\boldA$ and $\boldb$ are given. There are a variety of scenarios depending on the properties of $\boldA$ . For now let’s consider the case where $\boldA$ is $N \times N$ , and seek conditions on $\boldA$ under which, for every $\boldb \in \RR^N$ , there exists exactly one $\boldx \in \RR^N$ such that $\boldA \boldx = \boldb$ .

The best way to understand this problem is as follows. Let $T$ be the linear map $T \boldx = \boldA \boldx$ . The question we are asking here is: When does each point $\boldb \in \RR^N$ have one and only one preimage under $T$ ? In other words, when is $T$ a bijection?

To answer this question, we can refer back to the discussion in Section 2.1.7. We saw there that linear bijections are called nonsingular functions, and we discussed a number of equivalences for this property. The next fact replicates these equivalences in the language of matrices.

These results can all be verified using theorem 2.1.7 by checking the corresponding implications for $T \boldx = \boldA \boldx$ . For example, it’s easy to see that if $\bolde_n$ is the $n$ th canonical basis vector of $\RR^N$ , then

T\bolde_n = \boldA \bolde_n = \col_n \boldA

and hence the condition of linear independence of $\{T\bolde_1, \ldots, T\bolde_N\}$ in theorem 2.1.7 translates to linear independence of the columns of $\boldA$ .

Following common usage, if any of the equivalent conditions in fact 3.1.3 are true we will call not just the map $T$ but also the underlying matrix $\boldA$ nonsingular. If any one—and hence all—of these conditions fail, then $\boldA$ is called singular.

Any bijection has an inverse (see Section 15.2). In fact any nonsingular map $T$ has a nonsingular inverse $T^{-1}$ (see fact 2.1.9). In the present setting, where $T$ is generated by a matrix $\boldA$ , the inverse $T^{-1}$ is also associated with a matrix, called the inverse of $\boldA$ . The next theorem gives details:

For this reason, nonsingular matrices are also referred to as invertible. The proof of theorem 3.1.2 is a solved exercise (ex. 3.5.5).

As stated in the next fact, to show that $\boldA$ is invertible and $\boldB$ is the inverse of $\boldA$ , it suffices to show that $\boldB$ is either a left inverse, in the sense that $\boldB \boldA = \boldI$ , or a right inverse, in the sense that $\boldA \boldB = \boldI$ . A proof is given in Section 3.1.4.

The next fact collects more useful results about inverse matrices.

The relation $(\boldA \boldB)^{-1} = \boldB^{-1} \boldA^{-1}$ is just a special case of the analogous rule for inversion of bijections (see fact 15.2.1). But you can also prove the equality directly by confirming that $\boldB^{-1} \boldA^{-1}$ is a right inverse (or left inverse) of $\boldA \boldB$ .

3.1.4Determinants¶

To each square matrix $\boldA$ , we can associate a unique number $\det \boldA$ called the determinant of $\boldA$ . To define it, let $S(N)$ be the set of all bijections from $\{1, \ldots, N\}$ to itself. For $\pi \in S(N)$ we define the signature of $\pi$ as

\sgn(\pi) := \prod_{m < n} \frac{\pi(m) - \pi(n)}{m - n}

The determinant of $N \times N$ matrix $\boldA$ is then given as

\det \boldA := \sum_{\pi \in S(N)} \sgn(\pi) \prod_{n=1}^N a_{\pi(n) n}

We won’t concern ourselves with the details of this definition. For now it’s enough to know the following facts:

In the $2 \times 2$ case one can show that the determinant satisfies

\det \left( \begin{array}{cc} a & b \\ c & d \\ \end{array} \right) = ad - bc

(3.4)

As an example of how these results can be useful, let’s go back and prove fact 3.1.4. Fix square matrix $\boldA$ and suppose that a right inverse $\boldB$ exists, in the sense that $\boldA \boldB = \boldI$ . This equality implies that both $\boldA$ and $\boldB$ are nonsingular, since applying $\det$ to both sides of $\boldA \boldB = \boldI$ and using the rules in fact 3.1.6 gives $\det(\boldA) \det(\boldB) = 1$ . It follows that both $\det \boldA$ and $\det \boldB$ are nonzero. Hence both matrices are nonsingular.

To show that $\boldB$ is the inverse of $\boldA$ , we just need to check that, in addition to $\boldA \boldB = \boldI$ , we have $\boldB \boldA = \boldI$ . To obtain the latter equality from the former, premultiply the former by $\boldB$ to get $\boldB \boldA \boldB = \boldB$ and then postmultiply by $\boldB^{-1}$ to get $\boldB \boldA = \boldI$ . The proof for the left inverse case is similar.

3.2Properties of Matrices¶

Let’s look at some special kinds of matrices and their role in linear algebra.

3.2.1Diagonal and Triangular Matrices¶

A square matrix is called

lower triangular if each element strictly above the principal diagonal is zero,
upper triangular if every element strictly below the principal diagonal is zero, and
triangular if it is either upper or lower triangular.

For example, if we define

\boldL := \left( \begin{array}{ccc} 1 & 0 & 0 \\ 2 & 5 & 0 \\ 3 & 6 & 1 \end{array} \right) \quad \text{and} \quad \boldU := \left( \begin{array}{ccc} 1 & 2 & 3 \\ 0 & 5 & 6 \\ 0 & 0 & 1 \end{array} \right)

then $\boldL$ and $\boldU$ are lower and upper triangular respectively. The great advantage of triangular matrices is that the associated linear equations are simple to solve using either forward or backward substitution. For example, with the system

\left( \begin{array}{ccc} 1 & 0 & 0 \\ 2 & 5 & 0 \\ 3 & 6 & 1 \end{array} \right) \left( \begin{array}{ccc} x_1 \\ x_2 \\ x_3 \end{array} \right) = \left( \begin{array}{c} x_1 \\ 2x_1 + 5x_2 \\ 3x_1 + 6x_2 + x_3 \end{array} \right) = \left( \begin{array}{c} b_1 \\ b_2 \\ b_3 \\ \end{array} \right)

the top equation involves only $x_1$ , so we can solve for its value directly. Plugging this value into the second equation, we can solve for $x_2$ and so on.

An even better situation arises when our matrix is both upper and lower triangular. These are the diagonal matrices. In other words, a square matrix $\boldA$ is diagonal if all entries off the principal diagonal are zero. For example, the identity matrix is diagonal.

The following notation is often used to define diagonal matrices:

\diag(d_1, \ldots, d_N) := \left( \begin{array}{cccc} d_1 & 0 & \cdots & 0 \\ 0 & d_2 & \cdots & 0 \\ \vdots & \vdots & & \vdots \\ 0 & 0 & \cdots & d_N \\ \end{array} \right)

With diagonal matrices it is trivial to compute powers, roots, inverses and products:

Property 3.2.2

Let $\boldC = \diag(c_1, \ldots, c_N)$ and $\boldD = \diag(d_1, \ldots, d_N)$ . The following statements are true:

$\boldC + \boldD = \diag(c_1 + d_1, \ldots, c_N + d_N)$ .
$\boldC \boldD = \diag(c_1 d_1, \ldots, c_N d_N)$ .
$\boldD^k = \diag(d^k_1, \ldots, d^k_N)$ for any $k \in \NN$ .
If $d_n \geq 0$ for all $n$ , then $\sqrt{\boldD}$ exists and equals $\diag(\sqrt{d_1}, \ldots, \sqrt{d_N})$ .
If $d_n \neq 0$ for all $n$ , then $\boldD$ is nonsingular and $\boldD^{-1} = \diag(d_1^{-1}, \ldots, d_N^{-1})$ .

You can check parts (i) and (ii) directly. The other claims follow from (i) and (ii).

3.2.2Trace, Transpose, and Symmetry¶

The trace of an $N \times N$ matrix $\boldA$ is the sum of the elements on its principal diagonal:

\trace \boldA = \sum_{n=1}^N a_{nn}

The transpose of $N \times K$ matrix $\boldA$ is a $K \times N$ matrix $\boldA^\T$ such that $\col_n(\boldA^\T) = \row_n \boldA$ . For example,

\boldA := \left( \begin{array}{cc} 10 & 40 \\ 20 & 50 \\ 30 & 60 \end{array} \right) \quad \implies \quad \boldA^\T = \left( \begin{array}{ccc} 10 & 20 & 30 \\ 40 & 50 & 60 \end{array} \right)

(3.5)

and

\boldB := \left( \begin{array}{ccc} 1 & 3 & 5 \\ 2 & 4 & 6 \\ \end{array} \right) \quad \implies \quad \boldB^\T = \left( \begin{array}{cc} 1 & 2 \\ 3 & 4 \\ 5 & 6 \end{array} \right)

A square matrix $\boldA$ is called symmetric if $\boldA^\T = \boldA$ , or, equivalently, $a_{nk} = a_{kn}$ for every $k$ and $n$ . Note that $\boldA^\T \boldA$ and $\boldA \boldA^\T$ are always well-defined and symmetric.

Note that if $\bolda$ and $\boldb$ are $N \times 1$ vectors, then the matrix product $\bolda^\T \boldb = \boldb^\T \bolda$ is equal to $\sum_{n=1}^N a_n b_n$ , which is the same as the inner product $\inner{\bolda, \boldb}$ . In what follows we’ll often work with column vectors and use matrix product rather than inner product notation.

3.2.3Eigenvalues and Eigenvectors¶

Let $\boldA$ be $N \times N$ . As in Section 3.1.2, think of $\boldA$ as a linear map, so that $\boldA \boldx$ is the image of $\boldx$ under $\boldA$ . In general, $\boldA$ will map $\boldx$ to some arbitrary new location but sometimes $\boldx$ will only be scaled. That is,

\boldA \boldx = \lambda \boldx

(3.6)

for some scalar $\lambda$ . If $\boldx$ and $\lambda$ satisfy (3.6) and $\boldx$ is nonzero, then $\boldx$ is called an eigenvector of $\boldA$ , $\lambda$ is called an eigenvalue, and $(\boldx, \lambda)$ is called an eigenpair.

Example 3.2.1

\boldA := \begin{pmatrix} 1 & -1 \\ 3 & 5 \end{pmatrix}, \quad \boldx := \begin{pmatrix} 1 \\ -1 \end{pmatrix} \quad \text{and} \quad \lambda := 2

then $(\boldx, \lambda)$ is an eigenpair of $\boldA$ , since $\boldx \neq \boldzero$ and

\boldA \boldx = \begin{pmatrix} 1 & -1 \\ 3 & 5 \end{pmatrix} \begin{pmatrix} 1 \\ -1 \end{pmatrix} = \begin{pmatrix} 2 \\ -2 \end{pmatrix} = 2 \begin{pmatrix} 1 \\ -1 \end{pmatrix} = \lambda \boldx

Consider now the matrix

\boldR := \left( \begin{array}{cc} 0 & -1 \\ 1 & 0 \\ \end{array} \right)

that rotates any point counterclockwise by $90^{\circ}$ , as shown in figure 3.1. This rotation causes the scaling in (3.6) to fail for any $\lambda \in \RR$ and nonzero $\boldx \in \RR^2$ . If, however, we admit the possibility that $\lambda$ and the elements of $\boldx$ can be complex, then (3.6) can hold. For example, direct calculation confirms that $\lambda = i$ and $\boldx = (1, -i)^\T$ is an eigenpair for $\boldR$ . It turns out that contemplation of complex eigenpairs is useful. Here eigenpairs are taken to be complex-valued unless explicitly stated to be real.

\boldR rotates points by 90^{\circ} — Figure 3.1: $\boldR$ rotates points by $90^{\circ}$

Here $\boldI$ is the $N \times N$ identity. Exercise 3.5.17 asks you to confirm this important fact. For the $2 \times 2$ matrix in (3.4), the rule for the $2 \times 2$ determinant in (3.4), fact 3.2.6 and a little bit of algebra imply that its eigenvalues are given by the two roots of the polynomial expression

\lambda^2 - (a + d) \lambda + (ad - bc) = 0

More generally, given any $N \times N$ matrix $\boldA$ , it can be shown via the fundamental theorem of algebra that there exist complex numbers $\lambda_1, \ldots, \lambda_N$ , not necessarily distinct, such that

\det(\boldA - \lambda \boldI) = \prod_{n=1}^N (\lambda_n - \lambda)

(3.7)

It is clear that each $\lambda_n$ satisfies $\det(\boldA - \lambda_n \boldI) = 0$ and hence is an eigenvalue of $\boldA$ . In particular, $\lambda_1, \ldots, \lambda_N$ is the set of eigenvalues of $\boldA$ , although it’s worth repeating that these numbers are not necessarily distinct.

It is immediate from (i) that $\boldA$ is nonsingular $\iff$ all its eigenvalues are nonzero.

3.2.4Quadratic Forms¶

In statistics and econometrics we often encounter quadratic expressions. In general, given symmetric $N \times N$ matrix $\boldA$ , the quadratic function or quadratic form on $\RR^N$ associated with $\boldA$ is the map $Q$ defined by

Q(\boldx) := \boldx^\T \boldA \boldx = \sum_{j=1}^N \sum_{i=1}^N a_{ij} x_i x_j

To give a simple illustration, let $N = 2$ and let $\boldA$ be the identity matrix $\boldI$ . In this case,

Q(\boldx) = \| \boldx \|^2 = x_1^2 + x_2^2

A 3D graph of this function is shown in figure 3.2.

Quadratic function Q(\boldx) = x_1^2 + x_2^2 — Figure 3.2:Quadratic function $Q(\boldx) = x_1^2 + x_2^2$

One thing you’ll notice about this function is that its graph lies everywhere above zero, or $Q(\boldx) \geq 0$ . In fact we know that $\| \boldx \|^2$ is nonnegative and will be zero only when $\boldx = \boldzero$ . Hence the graph touches zero only at the point $\boldx = \boldzero$ . Many other choices of $\boldA$ yield a quadratic form with this property. Such $\boldA$ are said to be positive definite. More generally, an $N \times N$ symmetric matrix $\boldA$ is called

nonnegative definite if $\boldx^\T \boldA \boldx \geq 0$ for all $\boldx \in \RR^N$ ,
positive definite if $\boldx^\T \boldA \boldx > 0$ for all $\boldx \in \RR^N$ with $\boldx \neq \boldzero$ ,
nonpositive definite if $\boldx^\T \boldA \boldx \leq 0$ for all $\boldx \in \RR^N$ , and
negative definite if $\boldx^\T \boldA \boldx < 0$ for all $\boldx \in \RR^N$ with $\boldx \neq \boldzero$ .

If $\boldA$ fits none of these categories, then $\boldA$ is called indefinite. Figure 3.3 shows the graph of a negative definite quadratic function. Now the function is hill-shaped, and $\boldzero$ is the unique global maximum. Figure 3.4 shows an indefinite form.

Quadratic function Q(\boldx) = x_1^2/2 + 8 x_1 x_2 + x_2^2/2 — Figure 3.4:Quadratic function $Q(\boldx) = x_1^2/2 + 8 x_1 x_2 + x_2^2/2$

The easiest case for detecting definiteness is when the matrix $\boldA$ is diagonal, since

\boldA = \diag(d_1, \ldots, d_N) \quad \text{implies} \quad Q(\boldx) = d_1 x_1^2 + \cdots + d_N x_N^2

From the right-hand expression we see that a diagonal matrix is positive definite if and only if all diagonal elements are positive. Analogous statements are true for nonnegative, nonpositive and negative definite matrices. The next fact generalizes this idea and is proved in Section 3.3.4.

It follows from fact 3.2.8 that

Finally, here’s a necessary (but not sufficient) condition for each kind of definiteness.

3.3Projection and Decomposition¶

This section collects some essential results on projection and decomposition of matrices. The projection material takes our abstract projection theory from Section 2.2 and translates it into the more concrete language of matrices.

3.3.1Projection Matrices¶

As stated in theorem 2.2.2, given any subspace $S$ , the corresponding projection $\boldP = \proj S$ is a linear map from $\RR^N$ to $\RR^N$ . In view of theorem 3.1.1, it follows that there exists an $N \times N$ matrix $\hat \boldP$ such that $\boldP \boldx = \hat \boldP \boldx$ for all $\boldx \in \RR^N$ . In fact we’ve anticipated this in the notation $\boldP$ , and from now on $\boldP$ will also represent the corresponding matrix. But what does this matrix look like?

This result generalizes fact 2.2.6, which pertains to projection onto the span of an orthonormal basis. The expression in (3.8) is more complex, but at the same time it applies to any basis, orthonormal or otherwise. We further explore the connection between the two results in Section 3.3.3. For the proof of theorem 3.3.1 see exercise 3.5.30 and its solution.

The construction of $\boldP$ in (3.8) implicitly assumes that $\boldB^\T \boldB$ is nonsingular. This is justified because $\boldB$ has full column rank (see ex. 3.5.28). As usual, we let $\boldM = \boldI - \boldP$ denote the residual projection.

Example 3.3.1

Recall example 2.2.1, where we found that the projection of $\boldy \in \RR^N$ onto $\Span\{\boldone\}$ is $\bar y \boldone$ . We can get this from (3.8) as well. Since $\boldone$ is a basis for $\Span\{\boldone\}$ , we have

\boldP = \proj \; \Span\{\boldone\} \; \implies \; \boldP = \boldone (\boldone^\T\boldone)^{-1} \boldone^\T = \frac{1}{N} \boldone \boldone^\T

(3.9)

This leads us back to $\boldP \boldy = \bar y \boldone$ , as expected. The corresponding residual projection is

\boldM_c = \boldI - \frac{1}{N} \boldone \boldone^\T

(3.10)

The reason for the subscripted $c$ was discussed in example 2.2.3.

For example, it’s easy to see that $\boldM_c$ in (3.10) maps $\boldone$ to $\boldzero$ . Exercise 3.5.31 asks you to prove fact 3.3.1.

A square matrix $\boldA$ is called idempotent if $\boldA \boldA = \boldA$ .

Idempotence of $\boldP$ and $\boldM$ can be checked by direct calculation. A better understanding is obtained by reflecting on the fact that projecting onto a subspace twice is the same as projecting once. After one projection the vector is already in the subspace. See fact 2.2.8.

For orthogonal projections, we can say more:

To see why $\rank \boldP = \dim S$ , recall that the rank of a linear map is the dimension of its range. When $\boldP = \proj S$ , the range of $\boldP$ is exactly $S$ .

To show that $\trace \boldP = \dim S$ also holds, we can appeal to fact 3.3.3. There’s also a nice direct proof. See exercise 3.5.27 and its solution. Once we know that $\trace\boldP = \dim S$ , it’s clear that $\trace\boldM = N - \dim S$ because

\trace\boldM = \trace(\boldI - \boldP) = \trace \boldI - \trace\boldP = N - \dim S

3.3.2Overdetermined Systems of Equations¶

In Section 3.1.3 we talked about solving equations of the form $\boldA \boldx = \boldb$ when $\boldA$ is square. In statistics and econometrics, we often work the case where $\boldA$ is $N \times K$ and $K \leq N$ . When the inequality is strict, the system of equations is said to be overdetermined.

Consider the problem of whether or not there exists a vector $\boldx$ satisfying $\boldA \boldx = \boldb$ in this setting. Intuitively, when the number of equations is larger than the number of unknowns ( $N > K$ ) we may not be able to find an $\boldx$ that satisfies all $N$ equations. There are several equivalent ways to formalize this intuition. The linear map $T \colon \RR^K \to \RR^N$ corresponding to $\boldA$ is $T\boldx = \boldA \boldx$ (see Section 3.1.2). We know the following statements to be equivalent:

there exists an $\boldx \in \RR^K$ with $\boldA \boldx = \boldb$ .
$\boldb \in \colspace \boldA$ .
$\boldb \in \range T$ .

We also know from theorem 2.1.8 that when $K < N$ , the function $T$ cannot be onto, and hence it’s possible that $\boldb$ lies outside the range of $T$ .

In fact we can say more than this. When $K < N$ , the scenario $\boldb \in \colspace \boldA$ is in some sense very rare. The reason is that the dimension of $\colspace \boldA$ , which is precisely the rank of $\boldA$ , is less than or equal to $K$ (see Section 3.1.2) and hence strictly less than $N$ . There is a sense in which $K$ -dimensional subspaces of $\RR^N$ are negligible, and hence the “chance” of $\boldb$ happening to lie in this subspace is tiny.^[1]

As a result the standard approach is to admit that an exact solution may not exist, and to focus instead on finding a $\boldx \in \RR^K$ such that $\boldA \boldx$ is as close to $\boldb$ as possible. It’s natural that "close to" is defined in terms of ordinary Euclidean norm, which leads us to the minimization problem

\min_{\boldx \in \RR^K} \| \boldb - \boldA \boldx \|

(3.11)

This is called a least squares problem because solving (3.11) is the same as minimizing $\| \boldb - \boldA \boldx \|^2$ with respect to $\boldx$ , and the squared norm is, by definition, a sum of squares. Assuming as before that $\boldA$ is $N \times K$ with $K \leq N$ and $\boldb$ is $N \times 1$ , we can use the orthogonal projection theorem to solve (3.11) as follows:

Proof

Let $\boldA$ and $\boldb$ be as in the statement of the theorem. Let $\hboldx$ be as in (3.12) and let $S := \colspace \boldA$ . By the full column rank assumption, the columns of $\boldA$ form a basis for $S$ . Hence, applying theorem 3.3.1, the orthogonal projection of $\boldb$ onto $S$ is

\boldP\boldb := \boldA (\boldA^\T \boldA)^{-1} \boldA^\T \boldb = \boldA \hboldx

(3.13)

Moreover, since the orthogonal projection theorem gives a unique minimizer in terms of the closest point in $S$ to $\boldb$ , we must have

\| \boldb - \boldA\hboldx \| < \| \boldb - \boldy\| \quad \text{for all } \boldy \in S, \; \boldy \neq \boldA \hboldx

(3.14)

Pick any $\boldx \in \RR^K$ such that $\boldx \neq \hboldx$ . By the definition of $S$ we have $\boldA \boldx \in S$ . In addition, since $\boldx \neq \hboldx$ , and since $\boldA$ has full column rank, it must be that $\boldA \boldx \neq \boldA \hboldx$ (ex. 3.5.4). Hence

\| \boldb - \boldA\hboldx \| < \| \boldb - \boldA \boldx\| \quad \text{for all } \boldx \in \RR^K, \; \boldx \neq \hboldx

In other words, $\hboldx$ is the unique solution to (3.11). ◻

In the expression for $\hboldx$ in (3.12), the matrix $(\boldA^\T \boldA)^{-1} \boldA^\T$ is called the pseudoinverse of $\boldA$ . If $K = N$ —that is, if $\boldA$ is in fact square—then, under our full rank assumption, the pseudoinverse reduces to the inverse $\boldA^{-1}$ , and the least squares solution $\hboldx$ in (3.12) reduces to the expression given in (3.3).

What happens if we drop the assumption that the columns of $\boldA$ are linearly independent? The set $\colspace \boldA$ is still a linear subspace, and the orthogonal projection theorem still gives us a closest point $\boldP \boldb$ to $\boldb$ in $\colspace \boldA$ . Since $\boldP \boldb \in \colspace \boldA$ , there still exists a vector $\hboldx$ such that $\boldP \boldb = \boldA \hboldx$ . The problem is that now there exists an infinity of such vectors. Exercise 3.5.34 asks you to prove this.

3.3.3QR Decomposition¶

The QR decomposition of a given matrix $\boldA$ is a product of the form $\boldQ \boldR$ , where the first matrix has orthonormal columns and the second is upper triangular. This factorization has many applications, including least squares problems and the computation of eigenvalues. The decomposition is based on Gram–Schmidt orthogonalization.

Proof

Let $\boldA$ be as stated, and let $\bolda_k := \col_k \boldA$ . Theorem 2.2.3 gives us existence of an orthonormal set $\{\boldu_1, \ldots, \boldu_K\}$ such that the span of $\{\boldu_1, \ldots, \boldu_k\}$ equals that of $\{\bolda_1, \ldots, \bolda_k\}$ for $k = 1, \ldots, K$ . In particular, $\bolda_k$ is in the span of $\{\boldu_1, \ldots, \boldu_k\}$ , and hence, appealing to fact 2.2.3, we can write

\begin{aligned} \bolda_1 & = (\bolda_1^\T \boldu_1) \boldu_1 \\ \bolda_2 & = (\bolda_2^\T \boldu_1) \boldu_1 + (\bolda_2^\T \boldu_2) \boldu_2 \\ \bolda_3 & = (\bolda_3^\T \boldu_1) \boldu_1 + (\bolda_3^\T \boldu_2) \boldu_2 + (\bolda_3^\T \boldu_3) \boldu_3 \end{aligned}

and so on. Sticking to the $3 \times 3$ case to simplify expressions, we can stack these equations horizontally to get

\left( \begin{array}{ccc} | & | & | \\ \bolda_1 & \bolda_2 & \bolda_3 \\ | & | & | \end{array} \right) = \left( \begin{array}{ccc} | & | & | \\ \boldu_1 & \boldu_2 & \boldu_3 \\ | & | & | \end{array} \right) \left( \begin{array}{ccc} (\bolda_1^\T \boldu_1) & (\bolda_2^\T \boldu_1) & (\bolda_3^\T \boldu_1) \\ 0 & (\bolda_2^\T \boldu_2) & (\bolda_3^\T \boldu_2) \\ 0 & 0 & (\bolda_3^\T \boldu_3) \end{array} \right)

or $\boldA = \boldQ \boldR$ . This is our QR decomposition.

It remains to show that $\boldR$ is invertible. This will be so if each term $\bolda_k^\T \boldu_k$ is nonzero, since the determinant is the product of these elements (see fact 3.2.7). Suppose, to the contrary, that $\bolda_k^\T \boldu_k = 0$ for some $k$ . Then $\bolda_k$ lies in the span of $\{\boldu_1, \ldots, \boldu_{k-1}\}$ , which, by construction, agrees with the span of $\{\bolda_1, \ldots, \bolda_{k-1}\}$ . This contradicts linear independence of the columns of $\boldA$ . ◻

Given the decomposition $\boldA = \boldQ \boldR$ , the least squares solution $\hboldx$ defined in (3.12) can also be written as $\hboldx = \boldR^{-1} \boldQ^\T \boldb$ (ex. 3.5.32). Premultiplying by $\boldR$ converts this expression to $\boldR \hboldx = \boldQ^\T \boldb$ , which is easy to solve because $\boldR$ is triangular (see Section 3.2.1).

3.3.4Diagonalization and Spectral Theory¶

One important concept in dynamic systems and related fields is topological conjugacy. If $f \colon A \to A$ and $g \colon B \to B$ , then $g$ is said to be topologically conjugate to $f$ whenever there exists a continuous bijection $\tau \colon B \to A$ such that $f = \tau \circ g \circ \tau^{-1}$ . The idea is that the action of $f$ can be replicated by transporting a point into the domain of $g$ , applying $g$ , and then transporting it back. This can be beneficial if $g$ is somehow simpler than $f$ .

In the case of linear maps—that is, matrices—it is natural to study conjugacy in a setting where the bijection is also required to be linear. In linear algebra this is called similarity. In particular, a square matrix $\boldA$ is said to be similar to another matrix $\boldB$ if there exists an invertible matrix $\boldP$ such that $\boldA = \boldP \boldB \boldP^{-1}$ . Figure 3.5 shows the conjugate relationship of the two matrices when thought of as maps.

\boldA is similar to \boldB — Figure 3.5: $\boldA$ is similar to $\boldB$

The next fact is a fun exercise.

As discussed above, similarity of $\boldA$ to a given matrix $\boldB$ is most useful when $\boldB$ is somehow simpler than $\boldA$ , or more amenable to a given operation. The simplest kind of matrices we work with are diagonal matrices, so similarity to a diagonal matrix is particularly desirable. If $\boldA$ is similar to a diagonal matrix, then $\boldA$ is called diagonalizable.

If $\boldA = \boldP \boldLambda \boldP^{-1}$ where $\boldLambda$ is diagonal, it follows immediately that the elements on the principal diagonal of $\boldLambda$ are the eigenvalues of $\boldA$ , and that the columns of $\boldP$ are eigenvectors. To see this, observe that $\boldA = \boldP \boldLambda \boldP^{-1}$ implies $\boldA \boldP = \boldP \boldLambda$ . Equating the $n$ th column on each side gives $\boldA \boldp_n = \lambda_n \boldp_n$ , where $\boldp_n := \col_n \boldP$ . Finally, $\boldp_n$ is not the zero vector because otherwise $\boldP$ would not be invertible. Let’s summarize:

But when is $\boldA$ diagonalizable? The only thing we need to make the expression $\boldA = \boldP \boldLambda \boldP^{-1}$ work is for $\boldP$ to be invertible. This explains the next fact.

If $\boldA$ does have $N$ linearly independent eigenvectors, then we are in good shape—diagonalization is possible. But can we do any better? The matrix $\boldLambda$ cannot really be simplified, but in some cases $\boldP$ can be. In particular, things are even nicer if $\boldP$ has orthonormal columns—that is, its columns form an orthonormal set, and hence an orthonormal basis of $\RR^N$ . These kinds of matrices are called orthogonal matrices. Here are some nice properties of such matrices.

The first result tells us is that if $\boldA = \boldQ \boldLambda \boldQ^{-1}$ and $\boldQ$ has orthonormal columns, then $\boldA = \boldQ \boldLambda \boldQ^\T$ . It’s easy to see from this expression that $\boldA$ must be symmetric, so if we hope to diagonalize with this extra orthonormal property, then we shouldn’t look beyond symmetric matrices. The following fundamental theorem tells us that this form of diagonalization is possible precisely when $\boldA$ is symmetric.

This is one version of the spectral decomposition theorem. See, for example, §10.3 of Jänich (1994). $\boldQ \boldLambda \boldQ^\T$ is called the symmetric eigenvalue decomposition of $\boldA$ . It’s not hard to see that its action on a given $N \times 1$ vector $\boldx$ can be written as

\boldA\boldx = \sum_{n=1}^N \lambda_n (\boldu_n^\T \boldx) \boldu_n

where $\lambda_n$ is the $n$ th eigenvalue of $\boldA$ and $\boldu_n = \col_n \boldQ$ . Compare with $\boldx = \sum_{n=1}^N (\boldu_n^\T \boldx) \boldu_n$ , which is true by fact 2.2.3.

One nice application of the spectral theorem is a proof of fact 3.2.8, which states among other things that symmetric matrix $\boldA$ is positive definite if and only if its eigenvalues are all positive. Exercise 3.5.23 and its solution step you through the arguments.

Here $\boldQ \boldLambda \boldQ^\T$ is the spectral decomposition of $\boldA$ . To check that $\boldQ \sqrt{\boldLambda} \boldQ^\T$ is a square root just multiply. $\sqrt{\boldLambda}$ exists because $\boldA$ is nonnegative definite, and hence its eigenvalues are nonnegative (see fact 3.2.8 and fact 3.2.2).

By combining our results on spectral decomposition with the QR decomposition discussed in Section 3.3.3, we can prove the following well-known fact:

This decomposition is called the Cholesky decomposition. The proof is obtained by writing

\boldA = \boldQ \boldLambda \boldQ^\T = \boldQ \sqrt{\boldLambda} \sqrt{ \boldLambda} \boldQ^\T = (\sqrt{ \boldLambda} \boldQ^\T)^\T \sqrt{ \boldLambda} \boldQ^\T

and applying the QR decomposition to $\sqrt{ \boldLambda} \boldQ^\T$ . This allows us to write $\sqrt{ \boldLambda} \boldQ^\T = \tilde \boldQ \boldR$ , where $\boldR$ is nonsingular and upper triangular, and $\tilde \boldQ$ has orthonormal columns. Because the columns of $\tilde \boldQ$ are orthonormal,

\boldA = (\tilde \boldQ \boldR)^\T \tilde \boldQ \boldR = \boldR^\T \tilde \boldQ^\T \tilde \boldQ \boldR = \boldR^\T \boldR

Our decomposition has the properties stated in fact 3.3.10.

3.3.5Norms and Continuity¶

Given vector sequence $\{\boldx_n\}$ in $\RR^K$ and any point $\boldx \in \RR^K$ , we say that $\{\boldx_n\}$ converges to $\boldx$ and write $\boldx_n \to \boldx$ if, for any $\epsilon > 0$ , there exists an $N \in \NN$ such that $\|\boldx_n - \boldx\| < \epsilon$ whenever $n \geq N$ . Another way to say this is that the real-valued sequence $z_n := \|\boldx_n - \boldx\|$ converges to zero in $\RR$ as $n \to \infty$ .

For econometrics it is helpful if we extend the notion of convergence to matrices. We can do this in a parallel fashion by defining norms over matrices. The matrix norm of $N \times K$ matrix $\boldA$ is defined as

\| \boldA \| := \max \left\{ \| \boldA \boldx \| \,: \, \boldx \in \RR^K, \; \| \boldx \| = 1 \right\}

(3.15)

In this expression there are two different norms in play: The left-hand side is a matrix norm, while on the right we have the ordinary vector norm.

Given a sequence of $N \times K$ matrices $\boldA_n$ and an $N \times K$ matrix $\boldA$ , we say that $\boldA_n$ converges to $\boldA$ if the matrix norm deviation $\|\boldA_n - \boldA\|$ converges to zero in $\RR$ .

While the value in (3.15) is not particularly easy to solve for in general, the definition is entirely standard, and one can show that the matrix norm behaves like the vector norm in many ways. For example,

Compare these results with those of fact 2.1.2.

This bound is handy. For example, it tells us that if every element of $\boldA$ is close to zero then $\| \boldA \|$ must also be close to zero.

3.3.5.1Neumann Series¶

Let’s look at an important result in analysis that uses matrix norms. Starting in chapter 7, we will investigate dynamic systems such as $\boldx_{t+1} = \boldA \boldx_t + \boldb$ , where $\boldx_t$ represents the values of some variables of interest and $\boldA$ and $\boldb$ form the parameters in the law of motion for $\boldx_t$ . One question we might ask in this setting is whether or not there exists a "stationary" vector $\boldx \in \RR^N$ , in the sense that $\boldx_t = \boldx$ implies $\boldx_{t+1} = \boldx$ . In other words, we seek an $\boldx \in \RR^N$ that solves the system of equations

\boldx = \boldA \boldx + \boldb \qquad (\boldA \text{ is } N \times N \text{ and } \boldb \text{ is } N \times 1)

(3.16)

We can get some insight by reflecting on the scalar case $x = a x + b$ . If $|a| < 1$ , then this equation has the unique solution

\bar x = \frac{b}{1-a} = b \sum_{k=0}^{\infty} a^k

The second equality follows from elementary results on geometric series.

It turns out that a similar result is true in $\RR^N$ if we replace the condition $|a| < 1$ with an analogous result for matrices based around the matrix norm. We begin with the Neumann series lemma, which states the following:

Here $\boldI$ is the identity. The equality in (3.17) means that the matrix sum $\sum_{i=0}^t \boldA^i$ converges to the left-hand side in matrix norm as $t \to \infty$ . The sum is called the Neumann series associated with $\boldA$ . The condition in the theorem ensures that it converges. When the condition holds, (3.16) has the unique solution

\bar \boldx = (\boldI - \boldA)^{-1} \boldb = \sum_{i=0}^{\infty} \boldA^i \boldb

How to test the condition in theorem 3.3.5? The most commonly used sufficient condition involves the spectral radius of $\boldA$ , which is defined as

\rho(\boldA) := \max \setntn{ |\lambda| } { \lambda \text{ is an eigenvalue of } \boldA}

(3.18)

In this definition, $|\lambda|$ is the modulus of the possibly complex number $\lambda$ .^[3]

To understand why $\rho(\boldA) < 1$ is sufficient for the result in the Neumann series lemma, consider theorem 3.3.5 in this light: The claim is that $\sum_{i=0}^{\infty} \boldA^i$ is the inverse of $\boldI - \boldA$ , so $\sum_{i=0}^t \boldA^i (\boldI - \boldA)$ should be close to $\boldI$ for large $t$ . Evidently

\sum_{i=0}^t \boldA^i (\boldI - \boldA) = \sum_{i=0}^t \boldA^i - \sum_{i=0}^t \boldA^{i+1} = \boldI - \boldA^{t+1}

Hence, for the result to go through, we require $\boldA^t \to \boldzero$ as $t \to \infty$ . The case where $\boldA$ is diagonalizable gives the clearest insight here, so let’s suppose, as in Section 3.3.4, that $\boldA = \boldP \boldLambda \boldP^{-1}$ where $\boldLambda$ is a diagonal matrix containing the eigenvalues $\lambda_1, \ldots, \lambda_N$ of $\boldA$ on its principal diagonal. As discussed in fact 3.3.5, we then have

\boldA^t = \boldP \left( \begin{matrix} \lambda_1^t & 0 & \cdots & 0 \\ 0 & \lambda_2^t & \cdots & 0 \\ \vdots & \vdots & & \vdots \\ 0 & 0 & \cdots & \lambda_N^t \\ \end{matrix} \right) \boldP^{-1}

If $\rho(\boldA) < 1$ , then $|\lambda_n| < 1$ for all $n$ , and hence $\lambda_n^t \to 0$ as $t \to \infty$ . It follows that $\boldA^t \to \boldzero$ as required.

3.4Further Reading¶

Good treatments of matrix and linear algebra include Jänich (1994) and Axler (2015).

3.5Exercises¶

3.5.1Solutions to Selected Exercises¶

Solution to Exercise 3.5.5

Let $\boldA$ be a nonsingular matrix and let $T$ be the linear map associated with $\boldA$ via $T\boldx = \boldA \boldx$ . Since $A$ is nonsingular, $T$ is also, by definition, nonsingular and hence, by fact 2.1.9, has a nonsingular inverse $T^{-1}$ . Being nonsingular, $T^{-1}$ is necessarily linear, and hence, by theorem 3.1.1, there exists a matrix $\boldB$ such that $T^{-1} \boldx = \boldB \boldx$ for all $\boldx$ . By the definition of the inverse, we have $\boldA \boldB \boldx = T ( T^{-1} (\boldx )) = \boldx = \boldI \boldx$ . Since this holds for any $\boldx$ , we have $\boldA \boldB = \boldI$ (see ex. 3.5.13). A similar argument shows that $\boldB \boldA = \boldI$ .

Regarding the second claim, $\boldA^{-1} \boldb$ is a solution to $\boldA \boldx = \boldb$ , since $\boldA \boldA^{-1} \boldb = \boldI \boldb = \boldb$ . Uniqueness follows from fact 3.1.3 (and, in particular, the fact that nonsingularity of $\boldA$ includes the implication that the map $\boldx \mapsto \boldA \boldx$ is one-to-one).

Solution to Exercise 3.5.15

First, $\boldX$ is symmetric because

\boldX^\T = (\boldI - 2 \boldu \boldu^\T)^\T = \boldI - 2 (\boldu \boldu^\T)^\T = \boldI - 2 (\boldu^\T)^\T \boldu^\T = \boldI - 2 \boldu \boldu^\T = \boldX

Second, $\boldX \boldX = \boldI$ because

\begin{aligned} \boldX \boldX = (\boldI - 2 \boldu \boldu^\T) (\boldI^\T - 2 \boldu \boldu^\T) & = \boldI \boldI - 2 \boldI 2 \boldu \boldu^\T + (2 \boldu \boldu^\T)(2 \boldu \boldu^\T) \\ & = \boldI - 4 \boldu \boldu^\T + 4 \boldu \boldu^\T\boldu \boldu^\T = \boldI - 4 \boldu \boldu^\T + 4 \boldu \boldu^\T = \boldI \end{aligned}

The second last equality is due to the assumption that $\boldu^\T \boldu = \| \boldu \|^2 = 1$ .

Solution to Exercise 3.5.21

The claim is true because

\begin{aligned} &\left(\boldA+\boldU\boldW \right) \left[ \boldA^{-1} - \boldA^{-1}\boldU \left(\boldI+\boldW\boldA^{-1}\boldU \right)^{-1} \boldW\boldA^{-1} \right] \\ & \quad = \boldI + \boldU\boldW \boldA^{-1} - (\boldU+\boldU \boldW \boldA^{-1}\boldU)(\boldI + \boldW\boldA^{-1}\boldU)^{-1}\boldW\boldA^{-1} \\ & \quad = \boldI + \boldU\boldW \boldA^{-1} - \boldU(\boldI+ \boldW\boldA^{-1}\boldU)(\boldI + \boldW\boldA^{-1}\boldU)^{-1}\boldW\boldA^{-1} \\ & \quad = \boldI + \boldU\boldW \boldA^{-1} - \boldU\boldW \boldA^{-1} = \boldI \end{aligned}

Solution to Exercise 3.5.23

Suppose that $\boldA$ is symmetric with eigenvalues $\lambda_1, \ldots, \lambda_N$ . By theorem 3.3.4 we can decompose it as $\boldA = \boldQ \boldLambda \boldQ^\T$ , where $\boldLambda$ is the diagonal matrix formed from eigenvalues and $\boldQ$ is an orthogonal matrix. Fixing $\boldx \in \RR^N$ and letting $\boldy := \boldQ^\T \boldx$ , we have

\boldx^\T \boldA \boldx = (\boldQ^\T \boldx)^\T \boldLambda (\boldQ^\T \boldx) = \boldy^\T \boldLambda \boldy = \lambda_1 y_1^2 + \cdots + \lambda_N y_N^2

(3.19)

Suppose that all eigenvalues are positive. Take $\boldx$ to be nonzero. The vector $\boldy$ must be nonzero (why?), and it follows from (3.19) that $\boldx^\T \boldA \boldx > 0$ . Hence $\boldA$ is positive definite as claimed.

Conversely, suppose that $\boldA$ is positive definite. Fix $n \leq N$ and set $\boldx = \boldQ \bolde_n$ . Evidently $\boldx$ is nonzero (why?). Hence $\boldx^\T \boldA \boldx > 0$ . Since $\boldQ^\T$ is the inverse of $\boldQ$ , it follows that

\lambda_n = \bolde_n^\T \boldLambda \bolde_n = (\boldQ^\T \boldx)^\T \boldLambda \boldQ^\T \boldx = \boldx^\T \boldQ \boldLambda \boldQ^\T \boldx = \boldx^\T \boldA \boldx > 0

Since $n$ was arbitrary, all eigenvalues are positive.

Solution to Exercise 3.5.27

Let $S$ and $\boldP$ be as in the statement of the exercise and let $K := \dim S$ . We aim to show that $\trace \boldP = K$ . Let $\boldB$ be a matrix such that its columns form a basis for $S$ . By the definition of dimension, $\boldB$ has $K$ columns. Applying (3.8), we have

\trace \boldP =\trace(\boldB (\boldB^\T\boldB)^{-1} \boldB^\T )

Recalling fact 3.2.3, we rearrange to get

\trace[\boldB (\boldB^\T\boldB)^{-1} \boldB^\T] = \trace[(\boldB^\T\boldB)^{-1} \boldB^\T\boldB ] = \trace \boldI

where $\boldI$ is the $K \times K$ identity. The claim follows.

Solution to Exercise 3.5.28

Let $\boldA = \boldB^\T \boldB$ . It suffices to show that $\boldA$ is positive definite, since this implies that its determinant is strictly positive, and any matrix with nonzero determinant is nonsingular. To see that $\boldA$ is positive definite, pick any $\boldb \neq \boldzero$ . We must show that $\boldb^\T \boldA \boldb > 0$ . To see this, observe that

\boldb^\T \boldA \boldb = \boldb^\T \boldB^\T \boldB \boldb = (\boldB \boldb)^\T \boldB \boldb = \| \boldB \boldb \|^2

By the properties of norms, the last term is zero only when $\boldB \boldb = \boldzero$ . But this is not true because $\boldb \neq \boldzero$ and $\boldB$ is full column rank (see theorem 2.1.1).

Solution to Exercise 3.5.30

Let $S$ and $\boldP$ be as stated in theorem 3.3.1 and let $\boldB$ be a matrix such that the columns of $\boldB$ form a basis of $S$ . Fix $\boldy \in \RR^N$ . The claim is that $\hboldy := \boldB (\boldB^\T\boldB)^{-1} \boldB^\T \boldy$ is the orthogonal projection of $\boldy$ onto $S$ . To verify this, we need to show that

$\hboldy \in S$ and
$\boldy - \hboldy \perp S$ .

Part (i) is true because $\hboldy$ can be written as $\hboldy = \boldB \boldx$ where $\boldx := (\boldB^\T\boldB)^{-1} \boldB^\T \boldy$ . The vector $\boldB \boldx$ is a linear combination of the columns of $\boldB$ . Since these columns form a basis of $S$ , they must lie in $S$ . Hence $\hboldy \in S$ as claimed.

Regarding (ii), from the assumption that $\boldB$ gives a basis for $S$ , all points in $S$ have the form $\boldB \boldx$ for some $\boldx \in \RR^K$ . Thus (ii) translates to the claim that

\boldy - \boldB (\boldB^\T \boldB)^{-1} \boldB^\T \boldy \perp \boldB \boldx \quad \text{for all } \boldx \in \RR^K

This is true because if $\boldx \in \RR^K$ , then

(\boldB \boldx)^\T [\boldy - \boldB (\boldB^\T \boldB)^{-1} \boldB^\T \boldy] = \boldx^\T [\boldB^\T \boldy - \boldB^\T \boldB (\boldB^\T \boldB)^{-1} \boldB^\T \boldy] = \boldx^\T [\boldB^\T \boldy - \boldB^\T \boldy] = 0

Solution to Exercise 3.5.32

Let $\boldA$ , $\boldQ$ , $\boldR$ and $\boldb \in \RR^N$ be as in the statement of the exercise. The claim is that $\hboldx$ defined in (3.12) is equal to $\tilde \boldx := \boldR^{-1} \boldQ^\T \boldb$ . To show this, in view of linear independence of the columns of $\boldA$ , it suffices to show that $\boldA \tilde \boldx = \boldA \hboldx$ , or

\boldA (\boldA^\T \boldA)^{-1} \boldA^\T \boldb = \boldQ \boldR \boldR^{-1} \boldQ^\T \boldb

After simplifying, we see it suffices to show that $\boldA (\boldA^\T \boldA)^{-1} \boldA^\T = \boldQ \boldQ^\T$ . Since $\boldA$ and $\boldQ$ have the same column space, this follows from theorem 3.3.1.

Footnotes¶

Formally, $K$ dimensional subspaces have measure zero in $\RR^N$ whenever $K < N$ . Hence every probability measure that is absolutely continuous with respect to Lebesgue measure puts zero mass on such a set. Less formally, consider the case where $N = 3$ and $K=2$ . Then $\colspace \boldA$ forms at most a 2-dimensional plane in $\RR^3$ . Intuitively, this set has no volume in $\RR^3$ because planes have no “thickness.” Similarly, while we might visualize $\boldb$ as a dot in $\RR^3$ , as a point it is in fact infinitesimally small. Hence the chance of a randomly chosen $\boldb$ lying in $\colspace \boldA$ is zero.
↩
If we permit the eigenvectors to be complex, then the requirement is that they form a basis of $\CC^N$ , the set of complex $N$ -vectors. In this case there is a sense in which almost all matrices are diagonalizable.
↩
The modulus of $a + ib \in \CC$ is $(a^2 + b^2)^{1/2}$ . If the imaginary part is zero, this reduces to the usual notion of absolute value.
↩
This is the so-called "underdetermined" case, where the number of equations is less than the number of unknowns. Intuitively, we do not have enough restrictions to pin down values uniquely.
↩
Hint: In view of fact 3.2.9, it suffices to show that $\boldB^\T \boldB$ is positive definite.
↩
Hint: Look at fact 3.3.9 and the argument that follows it.
↩

References¶

Jänich, K. (1994). Linear Algebra. New York: Springer.
Axler, S. (2015). Linear Algebra Done Right. New York: Springer.

3 Linear Algebra and Matrices

3.1Matrices and Linear Equations¶

3.1.1Basic Definitions¶

3.1.2Matrices as Maps¶

3.1.3Square Matrices and Invertibility¶

3.1.4Determinants¶

3.2Properties of Matrices¶

3.2.1Diagonal and Triangular Matrices¶

3.2.2Trace, Transpose, and Symmetry¶

3.2.3Eigenvalues and Eigenvectors¶

3.2.4Quadratic Forms¶

3.3Projection and Decomposition¶

3.3.1Projection Matrices¶

3.3.2Overdetermined Systems of Equations¶

3.3.3QR Decomposition¶

3.3.4Diagonalization and Spectral Theory¶

3.3.5Norms and Continuity¶

3.3.5.1Neumann Series¶

3.4Further Reading¶

3.5Exercises¶

3.5.1Solutions to Selected Exercises¶