ming algorithms have become thousands of times faster and stateoftheart
computers have become thousands of times faster – together this makes a
factor of millions.
A linear program that would have required one year to
solve when the first linear programming algorithms were deployed now takes
under half a minute!
In Chapter 6, we discuss some of this history and
present some of the main algorithmic ideas in linear programming.
14
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 offered 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.