Chapter 2
Linear Algebra
Linear algebra is about linear systems of equations and their solutions. As a
simple example, consider the following system of two linear equations with
two unknowns:
2
x
1

x
2
=
1
x
1
+
x
2
=
5
.
There is a unique solution, given by
x
1
= 2 and
x
2
= 3.
One way to see
this is by drawing a graph, as shown in Figure 2.1. One line in the figure
represents the set of pairs (
x
1
, x
2
) for which 2
x
1

x
2
= 1, while the other
represents the set of pairs for which
x
1
+
x
2
= 5. The two lines intersect only
at (2
,
3), so this is the only point that satisfies both equations.
The above example illustrates one possible outcome with two equations
and two unknowns.
Two other possibilities are to have no solutions or an
infinite number of solutions, as illustrated in Figure 2.2. The lines in Figure
2.2(a) are given by the equations
x
1
+
x
2
=
2
x
1
+
x
2
=
5
.
Since they are parallel, they never intersect. The system of equations there
fore does not have a solution. In Figure 2.2(b), a single line is given by both
of the following equations
2
x
1

x
2
=
1

4
x
1
+ 2
x
2
=

2
.
Every point on this line solves the system of equations. Hence, there are an
infinite number of solutions.
15
16
(2, 3)
(0.5, 0)
(0, 1)
(5, 0)
(0, 5)
x
1
x
2
Figure 2.1: A system of two linear equations with two unknowns, with a unique
solution.
There is no way to draw two straight lines on a plane so that they only
intersect twice. In fact, there are only three possibilities for two lines on a
plane: they never intersect, intersect once, or intersect an infinite number of
times. Hence, a system of two equations with two unknowns can have either
no solution, a unique solution, or an infinite number of solutions.
Linear algebra is about such systems of linear equations, but with many
more equations and unknowns.
Many practical problems benefit from in
sights o
ff
ered by linear algebra. Later in this chapter, as an example of how
linear algebra arises in real problems, we explore the analysis of contingent
claims. Our primary motivation for studying linear algebra, however, is to
develop a foundation for linear programming, which is the main topic of this
book. Our coverage of linear algebra in this chapter is neither selfcontained
nor comprehensive. A couple of results are stated without any form of proof.
The concepts presented are chosen based on their relevance to the rest of the
book.
c
Benjamin Van Roy and Kahn Mason
17
(5, 0)
(0, 5)
x
1
x
2
(2, 0)
(0, 2)
(0.5, 0)
(0, 1)
x
1
x
2
(a)
(b)
Figure 2.2: (a) A case with no solution.
(b) A case with an infinite number of
solutions.
2.1
Matrices
We assume that the reader is familiar with matrices and their arithmetic
operations.
This section provides a brief review and also serves to define
notation that we will be using in the rest of the book. We will denote the set
of matrices of real numbers with
M
rows and
N
columns by
M
×
N
. Given a
matrix
A
∈
M
×
N
, we will use the notation
A
ij
to refer to the entry in the
i
th row and
j
th column, so that
A
=
A
11
A
12
· · ·
A
1
N
A
21
A
22
· · ·
A
2
N
.
.
.
.
.
.
· · ·
.
.
.
A
M
1
A
M
2
· · ·
A
MN
.
2.1.1
Vectors