# Applications of Matrices and Linear Algebra

## 1 Curves and Surfaces Through Given Points

In this section and the ones that follow, we describe a number of
applications of

matrices and linear algebra. Most of these examples come from the text [1].
Other

examples are also available on the web site.

### 1.1 Two Points on a Line

We are given two points in the plane, say (x_{1}, y_{1}) and (x_{2}, y_{2}), and we want
to find

the equation of the line determined by these two points. Let the equation of the
line

be

c_{1}x + c_{2}y + c_{3} = 0,

where c_{1}, c_{2}, and c_{3} are to be determined. We write

x_{1}c_{1} + y_{1}c_{2} + 1c_{3} = 0,

x_{2}c_{1} + y_{2}c_{2} + 1c_{3} = 0,

and

xc_{1} + yc_{2} + 1c_{3} = 0.

Since there is to be a non-trivial solution, the matrix

must have determinant equal to zero. Therefore

x(y_{1} − y_{2}) − y(x_{1} − x_{2}) + (x_{1}y_{2} − x_{2}y_{1}) = 0,

and we can choose

c_{1} = (y_{1} − y_{2}),

c_{2} = (x_{2} − x_{1}),

and

c_{3} = (x_{1}y_{2} − x_{2}y_{1}).

### 1.2 A Circle Through Three Given Points

We are given the three non-collinear points (x_{1}, y_{1}), (x_{2}, y_{2}), and (x_{3}, y_{3})
and want to

find the circle containing these points. Any circle in the plane can be
described by

an equation of the form

Rewriting this as

we see that the points (x, y) on the circle must satisfy the equation

for some choice of the unknowns c_{1}, c_{2}, c_{3}, and c_{4}. We write

and

Once again, since there is to be a non-trivial solution, the determinant of the matrix

must be zero, and writing this out will give us an equation of the circle in
the variables

x and y.

### 1.3 Additional Examples

The same approach can be used to determine a conic through five points, a
plane

through three points, and a sphere through four points.

## 2 Allocation Problems

We have n different jobs to assign to n different people. For i = 1, ..., n
and j = 1, ..., n

the quantity C_{ij} is the cost of having person i do job j. The n by n matrix C
with

these entries is the cost matrix. An assignment is a selection of n entries of C
so that

no two are in the same column or the same row; that is, everybody gets one job.
Our

goal is to find an assignment that minimizes the total cost

We know that there are n! ways to make assignments, so one solution would be

to determine the cost of each of these assignments and selection the cheapest.
But

for large n this is impractical. We want an algorithm that will solve the
problem

with less calculation. The algorithm we present here, discovered by two
Hungarian

mathematicians in the 1930’s, is called The Hungarian Method.

To illustrate, suppose there are three people and three jobs, and the cost
matrix

is

The algorithm is as follows:

**• Step 1:** Subtract the minimum of each row from all the entries of
that row.

This is equivalent to saying that each person charges a certain amount just for

participating, even before any assignments are made, and we must pay these

costs in any case. Subtracting these necessary costs, which do not depend on

the ultimate assignments, cannot change the optimal solutions.

The new matrix is then

**• Step 2:** Subtract each column minimum from the entries of its column.
This

is equivalent to saying that each job has a minimum cost that we must pay,

regardless of who performs it. As before, subtracting these necessary costs does

not change the optimal solutions.

The matrix becomes

**• Step 3:** Draw a line through the smallest number of rows and columns
that

results in all zeros being covered by a line; here I have put in boldface the
entries

covered by a line. The matrix becomes

We have used a total of two lines, one row and one column.

What we want is a set of n zeros with the property that each row contains one of

them, and each column contains one of them; we shall call such a set an optimal

set of zeros. Such a set of zeros will provide the desired cheapest assignments.

The next two steps help us decide whether or not such a set of zeros currently

exists.

**• Step 4:** If the number of lines just drawn is n we have finished. In
our example,

we are not finished. Proving that needing n lines to cover all the zeros means

that there is an optimal set of zeros is difficult. It is easy to show that if
there

exists an optimal set of zeros, then n or more lines are necessary to cover all
the

zeros; just notice that any line can contain at most one member of an optimal

set of zeros.

**• Step 5:** If, as in our example, the number of lines drawn is fewer than n,

determine the smallest entry not yet covered by a line (not boldface, here). It

is 10 in our example. Then subtract this number from all the uncovered entries

and add it to all the entries covered by both a vertical and horizontal line.
This

step is equivalent to, first, subtracting the smallest entry from every row not

completely covered by a line, and, second, adding this smallest entry to every

column covered by a line. Since adding or subtracting a fixed amount from any

row or column does not change the optimal solutions, we can return then to

Step 3.

Our matrix becomes

Now return to Step 3.

In our example, when we return to Step 3 we find that we need three lines now

and so we are finished. The optimal allocation is to assign the second person to

the first job, the third person to the second job, and the first person to the
third

job. Generally, finding an optimal set of zeros for larger cost matrices, even
when we

know such a set must exist, is not a simple matter; there are computer
algorithms to

perform this task, however.

**Exercise 2.1** Apply this algorithm to the cost matrix

## 3 Graph Theory

A directed graph is a set of symbols {P_{1}, P_{2}, ..., P_{n}} called the vertices
and a set of

ordered pairs (P_{i}, P_{j}) for P_{i} ≠ P_{j} , called the edges of the directed graph.
Write

P_{i} -> P_{j} if and only if (P_{i}, P_{j}) is an edge. We represent this directed graph
using

the matrix M with M_{ij} = 1 if P_{i} -> P_{j} and M_{ij} = 0 otherwise. See the download

“Motivating Matrix Operations” for a discussion of influence graphs and
dominance-

directed
graphs.

A subset of vertices is called a clique if and only if it has at least three
members,

P_{i} -> P_{j} and P_{j} -> P_{i} for each pair of vertices in the subset, and we cannot add a

vertex to the subset without violating the second condition. Define a matrix S
so

that S_{ij} = 1 if and only if P_{i} -> P_{j} and P_{j} -> P_{i}; otherwise S_{ij} = 0. Then the
vertex

P_{i} is a member of a clique if and only if (S^3)^{ii} ≠ 0.

## 4 Game Theory

The use of a pay-off matrix in game theory provides a good application of
linear

algebra; see the pdf on the web site.

## 5 Markov Chains

Let {1, 2, ..., k} be states. For i = 1, ..., k and j = 1, ..., k let P_{ij} ≥ 0
be the probability

of going from state j to state i in one step. The matrix P with entries P_{ij} is
called

the transition matrix. We begin with a column vector
, where

is
the probability that we start in state i. For n = 1, 2, ... the vector x^{n} is the
vector

whose entry
is the probability of being in state i after n steps, given the initial

probability vector x^0. We then have

We are often interested in the limiting behavior of the x^{n}.

For example, let

and let x^0 = [1 0]^T . Then for n even we have x^{n} = [1 0]^T and
for n odd we have

x^{n} = [0 1]^T .

We say that P is regular if, for some n, the matrix P^{n} has only positive
entries.

A basic theorem in Markov Chains is the following:

Theorem 5.1 If P is regular, then there is a probability vector q = (q_{1}, ...,
q_{k}), with

all entries positive, such that, as
for each j. Let Q be the matrix

with Q_{ij} = q_{i}, for each i and j.

So the limiting probability of going from j to i is independent of j. For any

probability (column) vector x we have Qx = q. Also Qq = q, so q is an
eigenvector

of Q associated with eigenvalue λ = 1.

## 6 Hill Codes

Simple substitution codes are easily broken by frequency analysis. Here we
consider

a code involving matrices.

Number the letters of the alphabet from A = 1 to Y = 25 and Z = 0. To encode

the sentence “I am hiding” , we first group the letters in pairs, as “ia mh id
in gg”.

Then replace each letter by its number, to get

9 1, 13 8, 9 4, 9 14, 7 7,

and view each of these pairs of numbers as a two-by one vector. Select an
encoding

matrix A; in this case we use a two-by-two matrix

Now multiply each of the two-by-one vectors by A; in our example we get [11
3]^T ,

which is KC, [29 24] = [3 24]^T , which is CX, and so on. This is a Hill-2
cipher. To

decode, we need A to be invertible modulo 26, which means that its determinant,

modulo 26 must have an inverse, modulo 26, which will happen if and only if this

determinant modulo 26 is not divisible by 2 or 13.

**Exercise 6.1** Find a decoding procedure for this Hill code by
calculating a modulo-26

inverse for the matrix A.