apps.tex

\setsecnumdepth{subsection}

\begin{alttitles}

\chapter{Applications}
\label{ch:apps}

I was going to make this chapter the finale of the book, but found I just
couldn't wait. This is what I love about linear algebra: not the abstract
manipulation of meaningless numbers in grids, but the ways in which the whole
topic of matrices applies beautifully and usefully to real-world scenarios.

This chapter doesn't begin to cover \textit{all} the applications of linear
algebra! Those are vast, and probably innumerable. But here are three of my
favorites presented in capsule form so you can get a taste for why it's useful
to do all this stuff.

\pagebreak

\section{Leslie matrices}

\label{sec:leslie}
\index{zombie}
\index{butterfly}
\index{fern}

Our first example will deal with modeling population growth in communities of
organisms, whether butterflies, ferns, zombies (okay, maybe not zombies), or
people. In these cases, we have a system whose properties evolve over time, and
our interest is in predicting how those properties will change in the future.

\subsection{``Systems'' and ``states''}

\index{system}

The word ``\textbf{system}'' is kind of vague, but really all we mean by it is
some complex phenomenon whose rules of behavior are at least partly known.
Examples of systems are natural habitats, economies, schools, rocket engines,
and sports leagues. Each of these examples contains interacting parts that
influence each other in complicated ways, and has various things about them we
could measure through time.

\index{state (of a system)}

We'll often talk about the \textbf{state} of a system, which is a pretty vague
word too. You can think of a system's state as a collection of all the relevant
things that characterize its situation at a moment in time. If our system is an
economy, this would include things like the number of workers in different job
sectors, the average wage of those workers, and the total amount of inventory
in all warehouses and stores. If our system is a habitat, it would include the
number of each different type of animal currently living in it, possibly
together with its sex and age.

\index{chess}
\index{Monopoly}
\index{Get Out Of Jail Free card}

I think of a system's state as ``all the things you'd have to write down and
remember if you wanted to pause the system and restart it later.'' Think of a
game. If you're playing chess, and get interrupted, you and your opponent will
need to write down the current locations of all the pieces on the board, plus
whose turn it is. If you're playing Monopoly, there's a whole lot more to
remember: how much money every player has, who owns which properties, what
board space each token is on, who has a Get Out Of Jail Free card, and whether 
the current player has already rolled doubles (and if so, whether once or
twice).

\index{state vector}

Interestingly, we most often use a \textit{vector} to model the current state
of a system. Just imagine a vector in which the first element was the number of
Monopoly dollars that player 1 has, the second through fourth elements are
player 2's through 4's money, the fifth element is the space number of player
1's token, and so forth. Or, imagine an economy with five different industries,
whose state is represented by a ten-dimensional vector giving the current
number of workers and current demand for products in each industry.

\index{discrete-time system}

Systems are often studied as though time marched forwards in fixed intervals.
(Sometimes these are called ``discrete-time systems.'') Each ``time step''
marks the evolution from one system state to another, as a result of that
amount of time elapsing. In our Monopoly example, the time step would be one
player's turn: each time a player rolls and moves, the state of the system
changes slightly. For the economy, we might measure it in time steps of one
week, in which every industry gains or loses employees and/or inventory each
week.

\index{simulation}

Starting from an initial state and working out how future states will unfold is
called ``simulating'' the system, and a computer program that does this is
called a \textbf{simulation}.

\subsection{The Markov property}

One interesting type of system that arises -- and the one we'll study here --
is one in which \textit{the state at the next time step depends
\underline{only} on the state at the current time step}. This is accurate for,
say, the game of chess. When you're considering your move, all you need to know
is the \textit{current} state; \textit{i.e.}, where all the pieces currently
are. You don't need to know what happened in the past to get the game to the
current position. Questions like ``how did the black queen \textit{get} to
square e7, anyway?'' and ``which piece was the one that captured the missing
white knight?'' are irrelevant.

\index{Markov property}

A system whose next state depends only on its current state is said to have the
\textbf{Markov property}, a term we will revisit in Chapter~\ref{ch:eigenapps}.


\subsection{The bunny rabbit state vector}

\index{bunny rabbit}
\index{rabbit}
\index{lifespan}

Let's say we'd like to study a local population of bunny rabbits. For reasons
that will become clear later, we're only going to count \textit{female}
rabbits. We'll make our time step be one year, and say that in each year, there
are some number of baby girl rabbits (0 years old), some number of 1-year-old
girl rabbits, some number of 2-year-old girl rabbits, and some number of
3-year-old girl rabbits. To keep things manageable, we'll also say that the
maximum lifespan of a rabbit is 3 years, after which all rabbits go to heaven.

Thus our state vector will be a four-dimensional vector of four numbers:
namely, the total population of female rabbits of each of the four ages.
Perhaps at ``time 0'' (the current year, say) our state vector is:

\vspace{-.15in}
\begin{align*}
\overrightarrow{\textbf{pop}_0} =
\begin{bmatrix}
67 \\ 115 \\ 23 \\ 5 \\
\end{bmatrix}
\end{align*}
\vspace{-.15in}

This indicates that when we begin our study, there are 67 baby rabbits, 115
one-year-olds, 23 two-year-olds, and only 5 three-year-olds. We call this
vector $\overrightarrow{\textbf{pop}_0}$ because it contains the rabbit
populations at year number 0.

\subsection{The Leslie matrix for population prediction}

\index{Leslie matrix}

We're now going to define a matrix, traditionally named $L$, called a
\textbf{Leslie Matrix} after ecologist Patrick Leslie. Leslie matrices have the
following very strict form, so study it carefully:

\vspace{-.15in}
\begin{align*}
L =
\begin{bmatrix}
f_0 & f_1 & f_2 & f_3 \\
s_0 & 0 & 0 & 0 \\
0 & s_1 & 0 & 0 \\
0 & 0 & s_2 & 0 \\
\end{bmatrix}.
\end{align*}
\vspace{-.15in}

Leslie matrices can be any (square) size. Here I've chosen $4\times 4$ because
we're keeping track of four different age brackets of bunny rabbits.

\index{subdiagonal}

Notice that most of the entries are zero. The only ones that can be nonzero are
(1) the top row, and (2) the first ``subdiagonal'' -- meaning, the diagonal
going from row 1, column 0 down to row 4, column 3. (Or, in a general $n\times
n$ Leslie matrix, from row 1, column 0 down to row $n$, column $n-1$.)

\medskip
So what's the method to this madness? Here's what:


\begin{itemize}
\itemsep.1em

\index{fecundity}

\item ``f'' stands for \textbf{fecundity}. That's a fancy ecology word for
``fertility.'' The $f$ entries stand for -- get this -- the number of babies on
average that each female rabbit of a certain age will give birth to. So if
$f_2$ is .9, for instance, that means that every two-year-old mommy rabbit
will, on average, give birth to .9 baby rabbits. Obviously some two-year-old
females will have fewer babies than others, but $f_2=.9$ means that on average
each mom will produce .9 of them.

Now you can see why I said we only need to keep track of the female rabbit
population. Females -- the child-bearers -- are the limiting factor. As long as
there are a few males (or even one) running around the population to perform
the fertilization task, the number of males won't really matter to the
long-term survival of the species.

By the way, if any of the $f$ entries are 0, that simply means that female
rabbits of that age are infertile. (In many species, of course, only females
within a certain age range can bear children.)

\index{survival rate}

\item ``s'' stands for \textbf{survival}. These $s$ entries represent the
probabilities that a rabbit of each age will survive another year. For example,
if $s_0$ is .8, that means that every (female) baby rabbit has an 80\% chance
of surviving to become a one-year-old. If $s_2=.5$, then only half of the
two-year-olds will survive to become three-year-olds. Notice that there is no
$s_3$ in the matrix; that's because we assumed that 3 years is the maximum age
of a rabbit, and so none of the three-year-olds will survive anyway.

\end{itemize}

All the other entries in $L$ have to be zero, and I think you can see the
reason. If you're a one-year-old rabbit, there's only two possibilities for
you: you can either survive to become a two-year-old next year, or else you can
die. There's no possibility that you'll jump over age 2 and become a
three-year-old next year, nor is there a chance that you'll ``fail'' grade 1
and have to be a one-year-old again next year.

Notice also that the $s$ entries must be between 0 and 1 (they're survival
\textit{probabilities}, after all), although the $f$ entries need not be. (Some
species have very high birth rates, and a female of child-bearing age can
easily produce more than just one offspring per year on average.)

To be concrete, let's whip up a random Leslie matrix and look at it:

\vspace{-.15in}
\begin{align*}
L =
\begin{bmatrix}
.1 & .6 & .4 & .2 \\
.4 & 0 & 0 & 0 \\
0 & .8 & 0 & 0 \\
0 & 0 & .6 & 0 \\
\end{bmatrix}.
\end{align*}
\vspace{-.15in}

Upon inspection, we can see that in this population, the following things are
true:

\begin{compactitem}
\item Baby rabbits rarely -- but sometimes -- have offspring. On average, for
every ten baby rabbits in our population in a given year, they'll produce one
new baby rabbit the next year.
\item Rabbits reach peak fertility as one-year-olds ($\frac{6}{10}$ babies per
mother). This fertility then declines each year thereafter until death.
\item Baby rabbits have a hard time surviving: less than half of them (40\%)
survive their inaugural year.
\item Both one-year-old and two-year-old rabbits have better than even odds of
survival, though this survival rate does decline from year two to year three.
\end{compactitem}


\subsection{Projecting forwards: matrix multiplication}

Now let's look at our Leslie matrix in action. Earlier, we started out our
hypothetical female rabbit population with these values:

\vspace{-.15in}
\begin{align*}
\overrightarrow{\textbf{pop}_0} =
\begin{bmatrix}
67 \\ 115 \\ 23 \\ 5 \\
\end{bmatrix}
\end{align*}
\vspace{-.15in}

Now how many rabbits can we expect in each of these age groups next year?

That might seem like a complicated question, but the answer is actually staring
you in the face. It's just matrix multiplication:

\vspace{-.15in}
\begin{align*}
\overrightarrow{\textbf{pop}_1} =
L \cdot \overrightarrow{\textbf{pop}_0}.
\end{align*}
\vspace{-.15in}

Wow! Really? Why does that work?

\smallskip

Well, think about what matrix multiplication actually does. First, each of our
female rabbits, regardless of age, will contribute something to the expected
number of newborn rabbits next year. Our current babies will contribute on
average only .1 of a newborn each, while one-year-olds will produce .6 newborns
each, two-year-olds .4 newborns each, and three-year-olds .2 newborns each.
That's \textit{exactly} the dot product of the top row of $L$ (the fecundity
row) times the current population vector!

Then, for each of the other age groups, the number of rabbits next year will
simply be the number of rabbits \textit{one year younger} this year, multiplied
by the survival rate of that age group. For example, 67 babies this year will
result in about 26.8 one-year-olds next year, since only 40\% of them will
survive. This, too, turns out to be a dot product: the survival row for that
age times the number of rabbits of that age.

\pagebreak

Check it out:

\vspace{-.25in}
\begin{align*}
\small
\begin{bmatrix}
.1 & .6 & .4 & .2 \\
.4 & 0 & 0 & 0 \\
0 & .8 & 0 & 0 \\
0 & 0 & .6 & 0 \\
\end{bmatrix} \cdot
\begin{bmatrix}
67 \\ 115 \\ 23 \\ 5 \\
\end{bmatrix} =
\begin{bmatrix}
.1\cdot 67 + .6 \cdot 115 + .4 \cdot 23 + .2 \cdot 5 \\
.4\cdot 67 \\
.8\cdot 115 \\
.6\cdot 23 \\
\end{bmatrix} =
\begin{bmatrix}
85.9 \\ 26.8 \\ 92.0 \\ 13.8 \\
\end{bmatrix}.
\end{align*}
\vspace{-.15in}

\normalsize

Don't get too freaked out by the idea of ``85.9 baby rabbits.'' These are just
averages based on the various probabilities. In real life, there would of
course not be any partial rabbits out there.

\smallskip

Once you see the previous calculation, it won't surprise you that

\vspace{-.15in}
\begin{align*}
\overrightarrow{\textbf{pop}_2} =
L \cdot \overrightarrow{\textbf{pop}_1}, \\
\overrightarrow{\textbf{pop}_3} =
L \cdot \overrightarrow{\textbf{pop}_2}, \\
\overrightarrow{\textbf{pop}_4} =
L \cdot \overrightarrow{\textbf{pop}_3}, \\
\end{align*}
\vspace{-.75in}
\begin{center}
\textit{etc.}
\end{center}

\smallskip
These work out to:

\vspace{-.15in}
\begin{align*}
\overrightarrow{\textbf{pop}_2} =
\begin{bmatrix}
.1 & .6 & .4 & .2 \\
.4 & 0 & 0 & 0 \\
0 & .8 & 0 & 0 \\
0 & 0 & .6 & 0 \\
\end{bmatrix} \cdot
\begin{bmatrix}
85.9 \\ 26.8 \\ 92.0 \\ 13.8 \\
\end{bmatrix} &=
\begin{bmatrix}
64.23 \\ 34.36 \\ 21.44 \\ 55.2 \\
\end{bmatrix}, \\
\overrightarrow{\textbf{pop}_3} =
\begin{bmatrix}
.1 & .6 & .4 & .2 \\
.4 & 0 & 0 & 0 \\
0 & .8 & 0 & 0 \\
0 & 0 & .6 & 0 \\
\end{bmatrix} \cdot
\begin{bmatrix}
64.23 \\ 34.36 \\ 21.44 \\ 55.2 \\
\end{bmatrix} &=
\begin{bmatrix}
46.66 \\ 25.69 \\ 27.5 \\ 12.86 \\
\end{bmatrix}, \\
\overrightarrow{\textbf{pop}_4} =
\begin{bmatrix}
.1 & .6 & .4 & .2 \\
.4 & 0 & 0 & 0 \\
0 & .8 & 0 & 0 \\
0 & 0 & .6 & 0 \\
\end{bmatrix} \cdot
\begin{bmatrix}
46.66 \\ 25.69 \\ 27.5 \\ 12.86 \\
\end{bmatrix} &=
\begin{bmatrix}
33.65 \\ 18.67 \\ 20.55 \\ 16.49 \\
\end{bmatrix},
\end{align*}
\vspace{-.15in}

and so on out to eternity.

\smallskip

\index{commutative}

Also, since matrix multiplication is commutative, we can carry out the products
in any order. We can start at the beginning (year 0) and multiply $L$ by itself
the requisite number of times to compute any future year. So, computing the
fourth generation after the starting state can be written as:

\vspace{-.15in}
\begin{align*}
\overrightarrow{\textbf{pop}_4} = L \cdot L \cdot L \cdot L \cdot
\overrightarrow{\textbf{pop}_0}, \\
\end{align*}
\vspace{-.45in}

and the thirtieth generation as:

\vspace{-.15in}
\begin{align*}
\overrightarrow{\textbf{pop}_{30}} = L^{30} \cdot
\overrightarrow{\textbf{pop}_0},\\
\end{align*}
\vspace{-.45in}

(where $L^{30}$ means ``$L$ multiplied by itself 30 times,'' of course).

\bigskip

Sadly for the rabbits, this works out to:

\vspace{-.15in}
\begin{align*}
\overrightarrow{\textbf{pop}_{30}} = 
\begin{bmatrix}
0.0123 \\ 0.0066 \\ 0.0071 \\ 0.0057 \\
\end{bmatrix},\\
\end{align*}
\vspace{-.45in}

\index{Hazel}
\index{Fiver}
\index{Watership Down@\textit{Watership Down}}
\index{survival rate}

which means that in their present environment, this rabbit colony's days are
numbered. Maybe Hazel and Fiver will come up with a migration plan that
increases their survival rates...

\vfill

\pagebreak

\renewcommand{\thesubsection}{H\arabic{subsection}.}%... from subsections
\section{Hamming codes}

\index{Hamming code}
\index{error-correcting code}

Our next example is about \textbf{error-correcting codes}, extremely useful in
the transfer of electronic data. These ``codes,'' by the way, have nothing to
do with the \textit{secret} codes used in cryptography, which conceal and
reveal hidden messages. (Those are a different application, which also rely on
linear algebra, by the way!)

The particular error-correcting code we'll learn is called the \textbf{Hamming
code}, invented by mathematician Richard Hamming. I hope you find it as amazing
as I do.

\subsection{Doing ``arithmetic mod 2''}

\index{binary}

One thing we need to get out of the way first is a little bookkeeping matter.
With Hamming codes, we're going to be dealing exclusively with \textbf{binary}
data. As you'll remember from \textit{Cool Brisk Walk} chapter 7, binary
numbers are base 2, with only 0 and 1 as the digits.

\index{MP3 file}
\index{GIF file}
\index{JPG file}
\index{video file}

Although this may sound like a limitation, it's not: every single piece of
information that's transferred between computers or is stored on one
\textit{must} be represented in binary form anyway. This is true not only of
numeric data, but also text documents, MP3 audio files, GIF or JPG image files,
and even videos. Representing every kind of information as a long sequence of
0's and 1's is a solved problem, so it's no big deal for our error-correcting
scheme to assume that the messages it works with are in binary. It could hardly
be any other way.

\index{modulo operator (mod)}

Binary digits thus really aren't that weird. What's slightly more weird is
doing our arithmetic ``modulo 2,'' which the Hamming code will require. What
this means is that every time we perform an addition or a multiplication
operation, we're only going to keep \textit{the least-significant bit of the
answer.} Mathematically, this amounts to taking our result modulo 2 -- which
means ``divide the answer by 2 and take the remainder.'' You'll quickly see
that this means all we care about is whether our answer is even or odd; if it's
even, our result is 0, and if it's odd, our result is 1.

Here are the complete addition and multiplication tables for one-bit binary
numbers. There's only one surprise, and that's in the lower left:

\vspace{-.15in}
\begin{center}
\setlength{\tabcolsep}{40pt}
\begin{tabular}{cc}
$0+0 = 0$ & $0\cdot 0 = 0$ \\
$0+1 = 1$ & $0\cdot 1 = 0$ \\
$1+0 = 1$ & $1\cdot 0 = 0$ \\
$1+1 = \textbf{0}$ & $1\cdot 1 = 1$ \\
\end{tabular}
\end{center}
\vspace{-.15in}

Everything else is what you learned in elementary school. But remember that in
``arithmetic mod 2,'' one plus one equals \textit{zero}. In terms of
\textit{Cool Brisk Walk} chapter 7, we have $1_2 + 1_2 = 10_2$, but since we
only want to keep the least-significant bit of the answer, we throw away the
$1$ in $10_2$ which leaves us with $0_2$.

To test your understanding, compute this dot product mod 2:

\vspace{-.15in}
\begin{align*}
\begin{bmatrix}
1 & 1 & 0 & 1 & 0 & 1 & 1
\end{bmatrix} \cdot
\begin{bmatrix}
0 \\ 1 \\ 0 \\ 1 \\ 1 \\ 1 \\ 0 \\
\end{bmatrix}
\end{align*}
\vspace{-.15in}

The answer should turn out to be:

\vspace{-.15in}
\begin{align*}
1\cdot 0 + 
1\cdot 1 + 
0\cdot 0 + 
1\cdot 1 + 
0\cdot 1 + 
1\cdot 1 + 
1\cdot 0 &= \\
0 + 
1 + 
0 + 
1 + 
0 + 
1 + 
0 &= 1.
\end{align*}
\vspace{-.15in}

There are an odd number of 1--1 pairs when lining up those vectors element by
element, and therefore the dot product is 1.

\subsection{Noisy channels}

\index{noisy channel@``noisy channel''}
\index{corrupted data}

Okay, down to business. The setting for the Hamming Code is the sending of
information over a so-called \textbf{noisy channel}. A noisy channel is a
transmission path through which data can be sent, but because it is ``noisy,''
some of the information is likely to be \textbf{corrupted} along the way. A
corrupted bit is simply one that is transmitted incorrectly: the sender tried
to send a 0 but the receiver erroneously got a 1, or vice versa.

\begin{figure}[ht]
\centering
\includegraphics[width=1\textwidth]{noisyChannel.pdf}
\caption{A binary message sent through a noisy channel. Seven out of the eight
bits were transmitted and received correctly.}
\label{fig:noisyChannel}
\end{figure}

This setting is depicted in Figure~\ref{fig:noisyChannel}. The sender in the
picture tried to transmit an eight-bit digital message to the receiver, and was
successful in doing so...almost. That fifth bit is the problem: the sender sent
a 1, but the receiver got a 0. This is life on a noisy channel.

Why would this happen? Interference, distortion, literal ``noise'': these all
play a role in our big chaotic imperfect world. You've all experienced your
cell phone getting bad service or your radio getting bad reception. That's the
information getting slightly (or perhaps majorly) corrupted in transmission, to
the point where you get a garbled version of what the cell tower transmitted or
the radio station broadcast.

And of course the frustrating thing is not merely that some bits were
corrupted, but that the receiver doesn't \textit{know} whether any were
corrupted. She received a string of bits, most of which are probably correct,
but a few of which might not be. The bad ones are indistinguishable from the
good ones, so she doesn't have any way of knowing which ones to trust.

Or does she?

\subsection{The Hamming code scheme}

Enter the Hamming code. The sender and receiver will cooperate in an amazing
way such that -- within certain limits -- bits that are corrupted in-transit
can be \textit{detected} as such by the receiver, and then \textit{corrected}
without the receiver even needing to asking the sender to repeat himself.

\begin{figure}[ht]
\centering
\includegraphics[width=1\textwidth]{hammingCode.pdf}
\vspace{-.4in}
\caption{The Hamming code error-correction scheme.}
\label{fig:hammingCode}
\end{figure}
\smallskip

The overall scene is shown in Figure~\ref{fig:hammingCode}. Study it carefully.
Here are the key points:

\begin{enumerate}

\item Each of the gray boxes -- mysteriously labeled $G^\intercal$, $H$, and $R$ in the
figure -- is a \textit{linear transformation}.

\index{nibble}
\index{signal}
\item The sender begins by carving up his message into consecutive 4-bit pieces.
 As you may remember from \textit{Cool Brisk Walk}, these 4-bit chunks are
called \textbf{nibbles}. Each nibble is sent separately. For purposes of
understanding this system, we'll just consider ``the entire message'' to be a
single nibble. (Longer messages simply repeat the whole process once per
nibble.) This 4 bits of information that the sender is trying to communicate is
called the \textbf{signal}.

\item The sender begins by running those 4 signal bits through the
$G^\intercal$ linear transformation, which maps them to a
\textit{7}-dimensional vector. Those 7 bits are called a \textbf{code word}.
The code word is what's actually sent through the noisy channel, not the
original signal.

\index{error syndrome}

\item On the other end of the wire, the receiver gets 7 bits of information.
These \textit{may} be identical to the code word that was sent, but of course
they may instead contain one or more corrupted bits.

\item The receiver proceeds to do two things with these 7 bits. First, she runs
them through the $H$ linear transformation to produce a 3-bit string called the
\textbf{error syndrome}. This is the key to the whole scheme. \textit{If the
error syndrome is exactly \texttt{000}, that means that the 7 bits were
uncorrupted and can be trusted}. In this case, she proceeds to the next step.
If the error syndrome is anything \textit{other} than \texttt{000}, this means
that the 7 received bits are \textit{not a valid code word}. We know, then, that
they could not have come from running \textit{any} 4-bit signal through the
$G^\intercal$ message. But perhaps the most amazing thing of all is that in
this case -- when the error syndrome is not \texttt{000} -- it will incredibly
spell out a binary number telling her \textit{exactly which bit was corrupted!}

For instance, if the error syndrome is \texttt{110}, which is the binary number
six, then she knows bit number 6 (out of 7) was corrupted, and she needs to
flip it from a 0 to a 1 or from a 1 to a 0. If the error syndrome is
\texttt{001}, which is a binary one, then she knows to flip the \textit{first}
bit of the received message.

\item Finally, the receiver takes the 7 bits -- corrected if necessary, based
on the error syndrome -- and runs them through the $R$ linear transformation.
This produces the 4-bit nibble that the sender originally sent.

\end{enumerate}

The reason all this works is that Hamming carefully designed the $G^\intercal$,
$H$, and $R$ linear transformations so that everything works out as described.
I'm sure you'd like to look at those now. You already know something about
them, because of the number of bits they take as inputs and outputs:

\begin{compactitem}
\item $G^\intercal$ must be a $7\times 4$ matrix, since it maps a 4-bit vector to a
7-bit vector.
\item $H$ must be a $3\times 7$ matrix, since it transforms each 7-bit vector
into a 3-bit vector.
\item Finally, $R$ must be a $4\times 7$, since it maps 7 bits into 4 bits.
\end{compactitem}

Here they are in all their glory:\footnote{Incidentally, in Hamming's original
\index{transpose} design all of these matrices had seven columns, including
``$G$'', which was a $4\times 7$. However, since we always use the
transposed-version-of-$G$ when we multiply a vector by it, the accepted
convention has become to just call it ``$G^\intercal$'' and treat it as a
$7\times 4$ matrix, as I'm doing here.}

\vspace{-.15in}
\begin{align*}
G^\intercal &=
\begin{bmatrix}
1 & 0 & 1 & 1\\
1 & 1 & 0 & 1\\
0 & 0 & 0 & 1\\
1 & 1 & 1 & 0\\
0 & 0 & 1 & 0\\
0 & 1 & 0 & 0\\
1 & 0 & 0 & 0\\
\end{bmatrix} \\
\medskip
H &=
\begin{bmatrix}
0 & 0 & 0 & 1 & 1 & 1 & 1 \\
0 & 1 & 1 & 0 & 0 & 1 & 1 \\
1 & 0 & 1 & 0 & 1 & 0 & 1 \\
\end{bmatrix} \\
\medskip
R &=
\begin{bmatrix}
0 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 & 0 \\
\end{bmatrix}
\end{align*}
\vspace{-.15in}

You can stare at these for a while if you want, and try to figure out the
method in the madness. I confess, it seems like a lot of voodoo magic to me,
especially $G^\intercal$. The $H$ matrix actually has a very reliable pattern:
if you look at the columns, you'll recognize that from left to right they are
the binary numbers 1 through 7!

\subsection{Examples}

All right, let's work through this scheme for a couple of actual examples.

\subsubsection{Example 1: no corruption}

Our sender desires to transmit the 4-bit message \texttt{1110} to the receiver.
So \texttt{1110} is the signal. He multiplies $G^\intercal$ by it to get:

\vspace{-.15in}
\begin{align*}
\begin{bmatrix}
1 & 0 & 1 & 1\\
1 & 1 & 0 & 1\\
0 & 0 & 0 & 1\\
1 & 1 & 1 & 0\\
0 & 0 & 1 & 0\\
0 & 1 & 0 & 0\\
1 & 0 & 0 & 0\\
\end{bmatrix} \cdot
\begin{bmatrix}
1 \\ 1 \\ 1 \\ 0
\end{bmatrix} = 
\begin{bmatrix}
0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 1 \\ 1
\end{bmatrix}.
\end{align*}
\vspace{-.15in}

So he sends \texttt{0001111} into the noisy channel.

\textit{(Time passes.)}

\index{code word}

On the other side of the world, the receiver picks up a 7-bit message:
\texttt{0001111}. She first asks herself: ``is this message legit? Is it a
valid code word?'' To find out, she multiplies it by $H$:

\vspace{-.15in}
\begin{align*}
\begin{bmatrix}
0 & 0 & 0 & 1 & 1 & 1 & 1 \\
0 & 1 & 1 & 0 & 0 & 1 & 1 \\
1 & 0 & 1 & 0 & 1 & 0 & 1 \\
\end{bmatrix} \cdot
\begin{bmatrix}
0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 1 \\ 1
\end{bmatrix} =
\begin{bmatrix}
0 \\ 0 \\ 0 \\
\end{bmatrix}.
\end{align*}
\vspace{-.15in}

Good news: the error syndrome is all zeroes! This means that the 7 bits she
received are in fact what was sent. All that remains is to run them through the
$R$ transformation to uncover the original message:

\vspace{-.15in}
\begin{align*}
\begin{bmatrix}
0 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 & 0 \\
\end{bmatrix} \cdot
\begin{bmatrix}
0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 1 \\ 1
\end{bmatrix} =
\begin{bmatrix}
1 \\ 1 \\ 1 \\ 0 \\
\end{bmatrix}.
\end{align*}
\vspace{-.15in}

Ta da!

\subsubsection{Example 2: one-bit corruption}

Our sender desires to transmit \texttt{0011} to the receiver.
He transforms it using $G^\intercal$ by it to get:

\vspace{-.15in}
\begin{align*}
\begin{bmatrix}
1 & 0 & 1 & 1\\
1 & 1 & 0 & 1\\
0 & 0 & 0 & 1\\
1 & 1 & 1 & 0\\
0 & 0 & 1 & 0\\
0 & 1 & 0 & 0\\
1 & 0 & 0 & 0\\
\end{bmatrix} \cdot
\begin{bmatrix}
0 \\ 0 \\ 1 \\ 1
\end{bmatrix} = 
\begin{bmatrix}
0 \\ 1 \\ 1 \\ 1 \\ 1 \\ 0 \\ 0
\end{bmatrix}.
\end{align*}
\vspace{-.15in}

The sender thus puts the code word \texttt{0111100} into the noisy channel.

\textit{(Time passes...but something goes wrong! Little do the sender or
receiver know, but the fourth bit of this code word hits a glitch and is
flipped to a 0!)}

\index{code word}

On the other side of the world, the receiver picks up a 7-bit message:
\texttt{011\textbf{0}100}. She first asks herself: ``is this message legit? Is
it a valid code word?'' To find out, she multiplies it by $H$:

\vspace{-.15in}
\begin{align*}
\begin{bmatrix}
0 & 0 & 0 & 1 & 1 & 1 & 1 \\
0 & 1 & 1 & 0 & 0 & 1 & 1 \\
1 & 0 & 1 & 0 & 1 & 0 & 1 \\
\end{bmatrix} \cdot
\begin{bmatrix}
0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \\ 0
\end{bmatrix} =
\begin{bmatrix}
1 \\ 0 \\ 0 \\
\end{bmatrix}.
\end{align*}
\vspace{-.15in}

Egads! Our error syndrome raises a red flag. It's not all zeroes, so something
must have gone amiss.

But all is not lost, since Hamming magic tells us exactly \textit{what} went
amiss. The error syndrome \texttt{100} corresponds to the binary number 4.
Therefore, bit number 4 of the received message is what was corrupted. Our
friend must not have sent \texttt{011\textit{0}100}, but rather
\texttt{011\textit{1}100}!

The receiver thus confidently plugs this corrected vector into the $R$ matrix
to yield:

\vspace{-.15in}
\begin{align*}
\begin{bmatrix}
0 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 & 0 \\
\end{bmatrix} \cdot
\begin{bmatrix}
0 \\ 1 \\ 1 \\ 1 \\ 1 \\ 0 \\ 0
\end{bmatrix} =
\begin{bmatrix}
0 \\ 0 \\ 1 \\ 1 \\
\end{bmatrix},
\end{align*}
\vspace{-.15in}

which is exactly the signal our sender intended. Amazing!

\subsection{The one fly in the ointment}

Some things are too good to be true. That's not the case with the Hamming code:
it is good, and it is true. But it does have a limitation, which I alluded to
earlier and will now spell out.

\index{single-bit error}

The Hamming code can only deal with \textbf{single-bit errors}. As long as only
\textit{one} of the 7 bits transmitted as a code word is corrupted, the
receiver can intelligently detect the error and even figure out which bit to
correct. But if more than one bit is corrupted in a single batch-of-seven, all
bets are off.

The reason is this: Hamming designed the $G^\intercal$ matrix (and its
counterpart, $R$) so that \textit{any two code words are at least two bits
apart}. This calls for some explanation.

Remember from \textit{Cool Brisk Walk} that there are $2^{4}$, or 16, possible
4-bit patterns. This is our vocabulary when using the Hamming code: we can say
any of sixteen different ``things'' each time we send a message. Now the
$G^\intercal$ matrix transforms those 4 bits into 7 bits. How many possible
7-bit sequences are there? Answer: $2^7$, or \textit{128.}

Think about that for a minute. There are 128 different 7-bit strings, yet only
16 of them are valid code words. That means that if you picked a random 7-bit
string out of a hat, the probability is pretty small that you'd actually hit
upon a code word: $\frac{16}{128} = \frac{1}{8} = .125$, to be precise. This is
what gives the Hamming code its detective power: you have to get pretty
``lucky'' to fool it. Over $87\%$ of the time, your choice of 7-bits is
instantly exposed as a fraud by the $H$ matrix.

And if we consider only the 16 valid code words out of those 128, you'll see
that Hamming designed it so that you can't get to any one of them from any of
the others without changing at least \textit{two} bits. This means that two
separate, independent errors would have to occur in order for one valid code
word (representing a particular 4-bit signal) to be corrupted into another
valid code word (representing a \textit{different} 4-bit signal). As long as
only one bit gets flipped, you're guaranteed that the code word will be
corrupted into a \textit{non}-code word, and thus be exposed to the light.

There are actually whole families of error correcting codes with various
properties, some of which are more intricate and can detect and even correct
multi-bit errors. The Hamming code was just the first, and what a great insight
it gave us.

% TODO: mention that the code words are the kernel of H.

% TODO: make clear that when interpreting the error syndrome, you start
% counting the bits at 1.

\pagebreak

\renewcommand{\thesubsection}{G\arabic{subsection}.}%... from subsections
\section{Graph analysis}

\label{sec:graphs}
\index{graph}
\index{network-based data}

The last application I'll present in this chapter deals with
\textbf{graph-based} data. We covered graphs extensively in Chapter 5 of
\textit{Cool Brisk Walk}, but now we'll bring our matrix skills to bear on our
analysis, and with striking effect.

\index{vertex (graph)}
\index{edge (graph)}

Recall that a \textbf{graph}, in discrete math terms, is not an x-y plot,
which is what most people think of when they hear the term. Instead, it's a
special kind of data structure for organizing data. A graph consists of
\textbf{vertices} (singular: \textbf{vertex}) connected by \textbf{edges}.
Here's an example:

\begin{figure}[ht]
\centering
\includegraphics[width=0.8\textwidth]{directedGraph.pdf}
\caption{A directed graph.}
\label{fig:directedGraph}
\end{figure}

Each vertex represents some entity (say, a computer on a network, or a user on
social media) and the edges represent relationships between them (network
connections, for example, or ``followings''). As graphs go, this one is
minuscule; the Facebook graph, in which vertices are users and edges are
friendships, has well over a billion vertices. But this will serve our purposes
for illustration.


\subsection{Graph terms}

Here's a refresher on some important graph terms, most of which are repeats
from \textit{Cool Brisk Walk} Chapter 5:

\begin{description}

\index{order (of a graph)}
\index{size (of a graph)}

\item[order/size.] Colloquially, researchers sometimes refer to the number
of vertices in a graph as its \textbf{order}, and the number of its edges as
its \textbf{size}. (The ratio of these quantities becomes a subject of interest
as well.) Figure~\ref{fig:directedGraph} has order 5 and size 9.

\index{adjacent (vertices)}

\item[adjacent.] If two vertices have an edge directly connecting them, they
are called ``adjacent.'' In Figure~\ref{fig:directedGraph}, vertices A and D are
adjacent, but \textit{not} A and E. (Even though you can get from A to E, you
must do so indirectly, through D.)

\index{directed graph}
\index{undirected graph}
\index{Facebook}
\index{Twitter}

\item[directed/undirected.] In Figure~\ref{fig:directedGraph}, the edges have
arrowheads. This is called a \textbf{directed} graph, and means that there is a
meaningful directionality to the edges: the information that A points to C does
not imply that C also points to A.

Sometimes, though, we don't care about which ``way'' the edge goes, and so we
draw the graph with lines only, no arrowheads. This is true of
Figure~\ref{fig:undirectedGraph} on p.~\pageref{fig:undirectedGraph}, which is
thus an \textbf{undirected} graph.

Facebook is real-life example of an undirected graph (if I'm friends with you,
then you're friends with me, always) but Twitter is a directed graph (if I
follow you, that doesn't necessarily mean you also follow me).

\begin{figure}[ht]
\centering
\includegraphics[width=0.7\textwidth]{undirectedGraph.pdf}
\caption{An undirected graph.}
\label{fig:undirectedGraph}
\end{figure}

\index{path (through a graph)}

\item[path.] A \textbf{path} is a sequence of consecutive edges that takes you
from one vertex to the other. In Figure~\ref{fig:directedGraph}, there is a
path from A to E, which goes through C. By contrast, there is no path at all
from G to J in Figure~\ref{fig:undirectedGraph}.

\index{traversing (a graph)}

\item[traverse.] We use the verb ``\textbf{traverse}'' to mean ``follow an edge
from one vertex to another.'' This often comes up in the context of searching
for data in the graph, or finding a path through the graph with certain
features.

\index{weighted graph}

\item [weighted.] Sometimes, the edges in the graph are unlabeled. But we
frequently want to associate a \textit{number} with each edge, in order to
represent the length of a road between cities, say, or the relative importance
of a friendship. This number is called the \textbf{weight} of the edge, and a
graph with such weights is called a \textbf{weighted graph}.

\index{degree (of a graph vertex)}
\index{in-degree}
\index{out-degree}

\item [degree.] A vertex's ``\textbf{degree}'' is simply the number of other
vertices that are adjacent to it. In Figure~\ref{fig:undirectedGraph}, vertices J
and K have degree 1, and the others have degree 2. For a directed graph, we
distinguish between the number of incoming edges, called the
``\textbf{in-degree},'' and the number of outgoing edges, or
``\textbf{out-degree}.'' So vertex B in Figure~\ref{fig:directedGraph} has an
in-degree of 2 and an out-degree of 3, while D has an in-degree of 0 and an
out-degree of 2.

\index{connected (graph)}
\index{disconnected (graph)}
\index{reachable@``reachable'' vertex (graph)}
\index{directed graph}
\index{weakly connected (graph)}
\index{strongly connected (graph)}

\item[connected/disconnected.] A graph is \textbf{connected} (sometimes called
``\textbf{fully connected},'' which means the same thing) if every vertex is
``reachable'' from every other vertex by traversing its edges. Otherwise, it's
\textbf{disconnected}. Figure~\ref{fig:undirectedGraph} is clearly not
connected, since we can't get to J/K from the others. What about
Figure~\ref{fig:directedGraph}? Well, that depends on how we define the term
``connected.'' If we say a directed graph is \textbf{strongly connected}, that
means that every vertex can be reached from every other even if you only follow
the arrows' directions. If it's merely \textbf{weakly connected} if you can
reach every vertex when \textit{ignoring} the edge directions. So the A-B-C-D-E
graph is weakly connected, but not strongly connected.

\index{cycle}

\item[cycle.] In a graph, a \textbf{cycle} is a group of vertices that are
connected in a ring: you can start at one, traverse edges to the others, and
then return to where you started. A$\rightarrow$B$\rightarrow$A is a cycle in
our first graph, and F--H--I--G is a cycle in the second graph.

\index{DAG (directed, acyclic graph)}

\item[DAG.] Finally, if a graph is directed and contains \textit{no} cycles, we
called it a ``\textbf{DAG},'' or ``directed, acyclic graph.'' Certain kinds of
directed graphs must inherently be cycle-free to even make sense. For instance,
if each vertex represents an action item in a project plan, and a directed edge
indicates that one item must be completed before another can begin, there must
be no cycles or else the project could never be completed!

\index{prerequisite}
\index{CPSC 284}

An example DAG is given in Figure~\ref{fig:dag} (p.~\pageref{fig:dag}), which
shows part of the computer science curriculum at UMW. Each vertex is a required
course -- CPSC 284, in fact, is our Applied Discrete Mathematics course, which
you are currently reading the book for. The directed edges represent
prerequisites: you must complete CPSC 110 before beginning CPSC 284, for
instance. You should take a moment and verify that there are no cycles in this
graph, because if there are, it would spell doom for computer science majors.

\begin{figure}[ht]
\centering
\includegraphics[width=0.8\textwidth]{dag.pdf}
\caption{A DAG (directed, acyclic graph).}
\label{fig:dag}
\end{figure}

\end{description}

\subsection{The adjacency matrix}

Okay, so that's a bunch of stuff about graphs. Now let's talk about how to
\textit{represent} a graph in a computer program. Clearly, it would be a poor
choice to store an image file with a bunch of circles and lines. We need
something much simpler and more flexible, which will capture the essence of
what the graph \textit{is}, not how it is drawn.

\index{adjacency matrix}

One very common way to do this is with an \textbf{adjacency matrix}. A graph's
adjacency matrix is simply a square matrix where every row (and column)
corresponds to one vertex. A ``1'' in row $i$, column $j$ means ``yes, vertex
$i$ and vertex $j$ are adjacent.'' Otherwise, they're not.

We often use the letter $A$ to denote the adjacency matrix. Here's the
adjacency matrix for Figure~\ref{fig:directedGraph}
(p.~\pageref{fig:directedGraph}):

\label{firstAdjacencyMatrix}
\[
A_{7.3} = 
\begin{blockarray}{cccccc}
& {\footnotesize\textrm{A}} & {\footnotesize\textrm{B}} & {\footnotesize\textrm{C}} & {\footnotesize\textrm{D}} & {\footnotesize\textrm{E}} \\
\begin{block}{c[ccccc]}
{\footnotesize\textrm{A}} & 0 & 1 & 1 & 0 & 0 \\
{\footnotesize\textrm{B}} & 1 & 0 & 1 & 0 & 1 \\
{\footnotesize\textrm{C}} & 0 & 1 & 0 & 0 & 1 \\
{\footnotesize\textrm{D}} & 1 & 0 & 0 & 0 & 1 \\
{\footnotesize\textrm{E}} & 0 & 0 & 0 & 0 & 0 \\
\end{block}
\end{blockarray}
\]

Stick your finger in p.~\pageref{fig:directedGraph} and flip back and forth
between the graph and the matrix to ensure it's correct. The top row is $[\ 0\
1\ 1\ 0\ 0\ ]$, because vertex A has an outgoing edge to B and to C, but not to
D or to E. Also, vertex A has \textit{incoming} edges from B and D (but neither
from C nor E), which is why its left column is:

\vspace{-.15in}
\begin{center}
${\scriptsize \begin{bmatrix} 0
\\ 1 \\ 0 \\ 1 \\ 0 \end{bmatrix}}$.
\end{center}

Notice that the diagonal terms are zero, which means that none of the vertices
has ``an edge to itself,'' which is what we normally do.

When you've convinced yourself that you understand that adjacency matrix, test
your skills by verifying this one as well, for the undirected graph in 
Figure~\ref{fig:undirectedGraph} (p.~\pageref{fig:undirectedGraph}):

\[
A_{7.4} = 
\begin{blockarray}{ccccccc}
& {\footnotesize\textrm{F}} & {\footnotesize\textrm{G}} & {\footnotesize\textrm{H}} & {\footnotesize\textrm{I}} & {\footnotesize\textrm{J}} & {\footnotesize\textrm{K}} \\
\begin{block}{c[cccccc]}
{\footnotesize\textrm{F}} & 0 & 1 & 1 & 0 & 0 & 0 \\
{\footnotesize\textrm{G}} & 1 & 0 & 0 & 1 & 0 & 0 \\
{\footnotesize\textrm{H}} & 1 & 0 & 0 & 1 & 0 & 0 \\
{\footnotesize\textrm{I}} & 0 & 1 & 1 & 0 & 0 & 0 \\
{\footnotesize\textrm{J}} & 0 & 0 & 0 & 0 & 0 & 1 \\
{\footnotesize\textrm{K}} & 0 & 0 & 0 & 0 & 1 & 0 \\
\end{block}
\end{blockarray}
\]


\subsection{Adjacency matrix properties}

\index{stupid dog tricks}
\index{Letterman, David}

I almost named this section ``stupid adjacency matrix tricks'' (after David
Letterman's ``stupid dog tricks'' skit) but I decided to play it straight.
Here we're going to make some deep connections between the properties of any
graph (we'll call it $G$) and its adjacency matrix $A$. This is just the tip of
the iceberg, believe me; more is coming in Chapter 9 when we cover eigenvalues.

\subsubsection{Undirected $G$ $\Leftrightarrow$ symmetric $A$}

\index{diagonal, of a matrix}
\index{symmetric matrix}
\index{directed graph}
\index{undirected graph}

The first one you might already have noticed from your study of
p.~\pageref{firstAdjacencyMatrix}. And that is that if the graph is
\textit{un}directed, its adjacency matrix will be \textit{symmetric}. If you
didn't see this before, run your eyeballs over those two matrices again, and
notice how the F--G--H--I--J--K matrix is a mirror image of itself across the
main diagonal, whereas the A--B--C--D--E matrix is not.

This is, of course, a natural consequence of what ``undirected'' means. If a
graph has no arrowheads, then every time you can go from X to Y, you can also
go from Y to X. So if $A$'s entry at row X and column Y is a 1, then the entry
at row Y and column X must also be a 1. And that's what makes a matrix
symmetric.


\subsubsection{DAG $G$ $\Leftarrow$ upper-triangular $A$}

I haven't yet given you an adjacency matrix for the DAG in Figure~\ref{fig:dag}
(p.~\pageref{fig:dag}). Here you go:

\[
A_{\textrm{DAG}} = 
\begin{blockarray}{ccccccccc}
& {\footnotesize\textrm{110}}
& {\footnotesize\textrm{220}}
& {\footnotesize\textrm{240}}
& {\footnotesize\textrm{340}}
& {\footnotesize\textrm{284}}
& {\footnotesize\textrm{350}}
& {\footnotesize\textrm{326}}
& {\footnotesize\textrm{430}} \\
\begin{block}{c[cccccccc]}
{\footnotesize\textrm{110}} & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\
{\footnotesize\textrm{220}} & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
{\footnotesize\textrm{240}} & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\
{\footnotesize\textrm{340}} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
{\footnotesize\textrm{284}} & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\
{\footnotesize\textrm{350}} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
{\footnotesize\textrm{326}} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
{\footnotesize\textrm{430}} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
\end{block}
\end{blockarray}.
\]

\index{upper-triangular}
\index{prerequisite}

As always, take a minute to verify the entries. And then, recognize that this
matrix is \textit{upper-triangular}.

Why should that be? Think of it this way. The graph is a DAG, which means it
has no cycles, which in turn means that there must be \textit{some} order in
which a student could complete the courses in the curriculum and not violate
any prerequisites. One such ordering is:

\begin{center}
CPSC 110, 220, 240, 340, 284, 250, 326, 430.
\end{center}

(That's not the only such ordering; 110, 284, 220, 240, 350, 340, 430, 326
would work just as well.)

Now suppose I create the adjacency matrix with the rows (and columns) in that
order. The first column \textit{must} have all zeroes, because by definition
the first course you take in the sequence must have no prerequisites. The
second column must also have all zeroes...with the possible exception of the
first row, because the first course (and \textit{only} the first course) might
be required in order to take the second course. This goes on down the line:
each course we take may have as prerequisites any of the previous courses, but
none of the future courses. And so the matrix will have all zeroes below the
main diagonal, which is the definition of ``upper-triangular.'' Ka-ching.

The order of the rows (and columns) is of course the key. It's easy to make a
\textit{non}-upper-triangular adjacency matrix for a DAG, just by shuffling the
rows and columns in a different order. Here's one:

\[
A_{\textrm{DAG}_2} = 
\begin{blockarray}{ccccccccc}
& {\footnotesize\textrm{326}}
& {\footnotesize\textrm{350}}
& {\footnotesize\textrm{284}}
& {\footnotesize\textrm{340}}
& {\footnotesize\textrm{240}}
& {\footnotesize\textrm{430}}
& {\footnotesize\textrm{110}}
& {\footnotesize\textrm{220}}\\
\begin{block}{c[cccccccc]}
{\footnotesize\textrm{326}} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
{\footnotesize\textrm{350}} & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
{\footnotesize\textrm{284}} & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
{\footnotesize\textrm{340}} & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
{\footnotesize\textrm{240}} & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\
{\footnotesize\textrm{430}} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
{\footnotesize\textrm{110}} & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\
{\footnotesize\textrm{220}} & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
\end{block}
\end{blockarray}.
\]

Nothing upper-triangular about that one. So the implication only holds in one
direction: if your adjacency matrix is upper-triangular, this implies that the
graph will be a DAG, but not necessarily vice versa. There will, however,
always be \textit{some} way to get an upper-triangular $A$ from a DAG, if you
order the rows in the ``correct'' way.


\subsubsection{Disconnected $G$ $\Leftarrow$ block diagonal $A$}

\index{block diagonal matrix}

Lastly, here's kind of a mind-blowing one. Suppose we have a disconnected
graph, like the one in Figure~\ref{fig:undirectedGraph}
(p.~\pageref{fig:undirectedGraph}). This disconnectedness is apparent from the
adjacency matrix, because it is -- get this -- block diagonal!

\vspace{-.15in}
\begin{align*}
A_{7.4} = 
\mleft[
\begin{array}{cccc|cc}
0 & 1 & 1 & 0 & 0 & 0  \\
1 & 0 & 0 & 1 & 0 & 0  \\
1 & 0 & 0 & 1 & 0 & 0  \\
0 & 1 & 1 & 0 & 0 & 0  \\
\hline
0 & 0 & 0 & 0 & 0 & 1  \\
0 & 0 & 0 & 0 & 1 & 0  \\
\end{array}
\mright]
\end{align*}
\vspace{-.15in}

The ordering-of-the-adjacency-matrix-rows thing comes into play here, just as
it did with upper-triangular matrices and DAGs. We would clearly shuffle the
order around and get a non-block-diagonal matrix. But there will be some
ordering that gives us a block diagonal, and here's why: a disconnected graph
is separable into isolated subgraphs.\footnote{\index{partition} This is a
\textbf{partition}, if you remember your set theory from \textit{Cool Brisk
Walk}.} None of the subgraphs have any connections to any of the others. So, if
we order our adjacency matrix rows (and columns) such that we list all the
vertices in one subgraph, then the next, then the next, we \textit{must} have
zeroes everywhere except the blocks on the diagonal. Neat!


\subsection{Using the adjacency matrix}

The adjacency matrix view of a graph lets us calculate a number of insightful
properties. Some of these we won't get to until Chapter 9, but some we can look
at now.

\index{matrix-vector multiplication}

Here's a simple one. Suppose we multiply the adjacency matrix by a vector of
all 1's?

\[
\begin{blockarray}{cccccc}
& {\scriptsize\textrm{A}} & {\scriptsize\textrm{B}} & {\scriptsize\textrm{C}} & {\scriptsize\textrm{D}} & {\scriptsize\textrm{E}} \\
\begin{block}{c[ccccc]}
{\scriptsize\textrm{A}} & 0 & 1 & 1 & 0 & 0 \\
{\scriptsize\textrm{B}} & 1 & 0 & 1 & 0 & 1 \\
{\scriptsize\textrm{C}} & 0 & 1 & 0 & 0 & 1 \\
{\scriptsize\textrm{D}} & 1 & 0 & 0 & 0 & 1 \\
{\scriptsize\textrm{E}} & 0 & 0 & 0 & 0 & 0 \\
\end{block}
\end{blockarray} \cdot
\begin{bmatrix}
1 \\ 1 \\ 1 \\ 1 \\ 1 \\
\end{bmatrix} \ = \
\begin{blockarray}{cc}
\\
\begin{block}{[c]c}
2 & {\scriptsize\textrm{A}} \\
3 & {\scriptsize\textrm{B}} \\
2 & {\scriptsize\textrm{C}} \\
2 & {\scriptsize\textrm{D}} \\
0 & {\scriptsize\textrm{E}} \\
\end{block}
\end{blockarray}
\]

\index{out-degree}

That might seem like a mindless operation, until you realize what it produced.
The result is a vector of the \textit{out-degrees} of each vertex! Double
check it with p.~\pageref{fig:directedGraph} if you don't believe me. Vertex A
has two outgoing arrows, B has three, C and D each have two, and E has none.

A similar trick can be performed by \textit{left}-multiplying the adjacency
matrix by a \textit{row} of 1's:

\[
\begin{bmatrix}
1 & 1 & 1 & 1 & 1 \\
\end{bmatrix} \cdot
\begin{blockarray}{cccccc}
& {\scriptsize\textrm{A}} & {\scriptsize\textrm{B}} & {\scriptsize\textrm{C}} & {\scriptsize\textrm{D}} & {\scriptsize\textrm{E}} \\
\begin{block}{c[ccccc]}
{\scriptsize\textrm{A}} & 0 & 1 & 1 & 0 & 0 \\
{\scriptsize\textrm{B}} & 1 & 0 & 1 & 0 & 1 \\
{\scriptsize\textrm{C}} & 0 & 1 & 0 & 0 & 1 \\
{\scriptsize\textrm{D}} & 1 & 0 & 0 & 0 & 1 \\
{\scriptsize\textrm{E}} & 0 & 0 & 0 & 0 & 0 \\
\end{block}
\end{blockarray} \ =
\hspace*{-.1in}
\begin{blockarray}{cccccc}
& {\scriptsize\textrm{A}} & {\scriptsize\textrm{B}} & {\scriptsize\textrm{C}} & {\scriptsize\textrm{D}} & {\scriptsize\textrm{E}} \\
\begin{block}{c[ccccc]}
 & 2 & 2 & 2 & 0 & 3 \\
\end{block}
\end{blockarray}.
\]

\index{in-degree}

This gives us the in-degrees. Of course, for an undirected graph -- and a
symmetric matrix -- these two results will be the same.


\subsubsection{Path counting}

\index{path (through a graph)}

One thing that turns out to be very important about graphs is the number of
paths between various nodes. In fact, the whole Google search engine (and all
its imitators) are essentially based on this principle, which we will further
unpack in Chapter 9. If vertices are Web pages and edges are hyperlinks between
them, then the ``importance'' of a page is intimately related to \textit{how
many other pages have paths to it}.\footnote{I'm slightly oversimplifying
things, but only a bit. The main principle is bedrock, and this explanation
will hold us over until we get to the PageRank algorithm itself near the end of
the book.}

We could take a first, very rough cut at this just by looking at the in-degrees
we computed in the previous section. Which of our A--B--C--D--E pages is the
``most important?'' Well, I guess we'd say that E is. Its in-degree is 3, more
than any other vertex, which means that three of the other pages in our
mini-web link to it. No other page is so popular.

\index{1-path@``1-path''}

A more sophisticated analysis involves looking at paths, not just single edges.
If you think about it, the adjacency matrix itself gives us the number of
``paths of length 1'' between each pair of vertices. For short, we use the term
``1-path.'' Our p.~\pageref{fig:directedGraph} graph has one 1-path between B
and C, but no 1-paths between D and B, which is why the adjacency matrix has a
1 in one place but a 0 in another.

Now what if we wanted to count the number of 2-paths? Glancing back at
p.~\pageref{fig:directedGraph}, you can see that it's certainly possible to
count these, but it's kind of a pain in the neck. There's \textit{one} 2-path
between A and B (A$\rightarrow$C$\rightarrow$B), but \textit{two} 2-paths
between A and E (A$\rightarrow$B$\rightarrow$E and
A$\rightarrow$C$\rightarrow$E). Clearly this is error-prone, as well as
tedious, to count manually. And if I asked you to stare at that graph and tell
me how many \textit{50}-paths there were from A to C, you'd tell me to jump in
the lake.

Is there a way to automate such computations? Of course, or I wouldn't be
telling you all this. It's amazingly elegant, too. Would you believe that the
number of 2-paths \textit{from} every vertex \textit{to} every vertex is just:

\vspace{-.15in}
\begin{align*}
A \cdot A
\end{align*}
\vspace{-.25in}

\textit{?!!}

\smallskip
Holy smokes, that actually \textit{works}? Yes! Check it out:

\vspace{-.15in}
\label{adjacencySquared}
\begin{align*}
A^2 =
\begin{bmatrix}
0 & 1 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 & 1 \\
0 & 1 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 \\
\end{bmatrix} \cdot
\begin{bmatrix}
0 & 1 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 & 1 \\
0 & 1 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 \\
\end{bmatrix} =
\begin{bmatrix}
1 & 1 & 1 & 0 & 2 \\
1 & 2 & 1 & 0 & 1 \\
1 & 0 & 1 & 0 & 1 \\
0 & 1 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 \\
\end{bmatrix}.
\end{align*}
\vspace{-.15in}

Spot check that result. It says that there is one 2-path from A to C, and two
2-paths from A to E, both of which we already figured out. It also says that
there's \textit{no} 2-path from B to A, even though there was a 1-path from B
to A. Examining Figure~\ref{fig:directedGraph}, we see that's true as well. And
of course the fourth column and fifth row of $A\cdot A$ have all zeroes, just
as $A$ itself did, since there's no 2-path (or any length path) that starts at
E nor that terminates at D.

Even more amazingly, by repeatedly multiplying $A$ by itself like this, we can
repeat this result to get the number of paths of \textit{any} length: 3-paths,
4-paths, 5-paths...

\vspace{-.15in}
\begin{align*}
A^3 = 
\begin{bmatrix}
0 & 1 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 & 1 \\
0 & 1 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 \\
\end{bmatrix}^3 =
\begin{bmatrix}
 1 &  2 &  2 &  0 &  2 \\
 2 &  1 &  2 &  0 &  3 \\
 0 &  2 &  1 &  0 &  1 \\
 1 &  1 &  1 &  0 &  2 \\
 0 &  0 &  0 &  0 &  0 \\
\end{bmatrix},\\
\end{align*}
\begin{align*}
A^4 = 
\begin{bmatrix}
0 & 1 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 & 1 \\
0 & 1 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 \\
\end{bmatrix}^4 =
\begin{bmatrix}
 2 &  3 &  3 &  0 &  4 \\
 1 &  4 &  3 &  0 &  3 \\
 2 &  1 &  2 &  0 &  3 \\
 1 &  2 &  2 &  0 &  2 \\
 0 &  0 &  0 &  0 &  0 \\
\end{bmatrix},\\
\end{align*}
\begin{align*}
A^5 = 
\begin{bmatrix}
0 & 1 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 & 1 \\
0 & 1 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 \\
\end{bmatrix}^5 =
\begin{bmatrix}
 3 &  5 &  5 &  0 &  6 \\
 4 &  4 &  5 &  0 &  7 \\
 1 &  4 &  3 &  0 &  3 \\
 2 &  3 &  3 &  0 &  4 \\
 0 &  0 &  0 &  0 &  0 \\
\end{bmatrix} \cdots
\end{align*}
\vspace{-.15in}

Truly amazing. That last result, for instance, has a 3 in the upper-left. That
means that there must be exactly three 5-paths from A back to A. Can you spot
them in Figure~\ref{fig:directedGraph}?\footnote{The solutions are:
A$\rightarrow$C$\rightarrow$B$\rightarrow$A$\rightarrow$B$\rightarrow$A,
A$\rightarrow$B$\rightarrow$A$\rightarrow$C$\rightarrow$B$\rightarrow$A, and
A$\rightarrow$C$\rightarrow$B$\rightarrow$C$\rightarrow$B$\rightarrow$A.}
And how about the 6 in the upper-right? Can you find all six 5-paths from A to
E?\footnote{
I believe they are 
A$\rightarrow$B$\rightarrow$A$\rightarrow$B$\rightarrow$C$\rightarrow$E,
A$\rightarrow$B$\rightarrow$A$\rightarrow$C$\rightarrow$B$\rightarrow$E,
A$\rightarrow$B$\rightarrow$C$\rightarrow$B$\rightarrow$C$\rightarrow$E,
A$\rightarrow$C$\rightarrow$B$\rightarrow$A$\rightarrow$B$\rightarrow$E,
A$\rightarrow$C$\rightarrow$B$\rightarrow$A$\rightarrow$C$\rightarrow$E, and
A$\rightarrow$C$\rightarrow$B$\rightarrow$C$\rightarrow$B$\rightarrow$E. Whew!}

Oh, and the number of 50-paths? No sweat:

\vspace{-.20in}
\begin{align*}
\footnotesize
A^{50} = 
\begin{bmatrix}
 \num{7778742049} & \num{12586269025} &\num{12586269025} & 0 & \num{15557484098} \\
 \num{7778742048} & \num{12586269026} & \num{12586269025} & 0 & \num{15557484097} \\
 \num{4807526977} & \num{7778742048} & \num{7778742049} & 0 &  \num{9615053953} \\
 \num{4807526976} & \num{7778742049} & \num{7778742049} & 0 &  \num{9615053952} \\
          0      &               0 &                0 & 0 &                0 \\
\end{bmatrix}.
\end{align*}
\vspace{-.15in}

So apparently there are exactly $\num{12586269025}$ different paths of length
50 between vertices A and B, and just one more ($\num{12586269026}$, to be
exact) from B back to itself. Don't worry, I won't make you figure out all 12
billion in either case.

\smallskip

Okay, but why does any of this work? What possible connection could there be
between multiplying an adjacency matrix by itself repeatedly and counting the
number of paths in the graph?

Well, consider first the 2-path question. To find the number of 2-paths from
(say) A to E, we need the following two things to be true:

\begin{compactenum}
\item We need an edge from A to ``something else.''
\item We need an edge from that ``something else'' to E.
\end{compactenum}

% WARNING: refers to "top of page"
Now the way we got the number ``2'' in the upper-right corner of $A^2$ (top of
p.~\pageref{adjacencySquared}) was by taking the dot product of the top row
(vertex A's row) with the right column (E's column):

\[
\begin{blockarray}{ccccc}
{\scriptsize\textrm{A}} & {\scriptsize\textrm{B}} & {\scriptsize\textrm{C}} & {\scriptsize\textrm{D}} & {\scriptsize\textrm{E}} \\
\begin{block}{[ccccc]}
 0 & 1 & 1 & 0 & 0 \\
\end{block}
\end{blockarray} \cdot
\begin{blockarray}{cc}
\begin{block}{c[c]}
{\scriptsize\textrm{A}} & 0 \\
{\scriptsize\textrm{B}} & 1 \\
{\scriptsize\textrm{C}} & 1 \\
{\scriptsize\textrm{D}} & 1 \\
{\scriptsize\textrm{E}} & 0 \\
\end{block}
\end{blockarray} = 0\cdot 0 + 1\cdot 1 + 1\cdot 1 + 0\cdot 1 + 0\cdot 0 = 2.
\]

Look at that calculation and see the magic. To get from A to E, there are two
possible ``something elses'': B, and C. Each one can serve as a waystation on
your two-step journey from A to E. Accordingly, the two terms in our dot
product that multiplied to 1 were the B and C entries. Putting it all together:
since there's one way to get from A to B, and one way to get from B to E,
that's one possible 2-path; and since there's one way to get from A to C, and
one way to get from C to E, that's the other possible 2-path.

\smallskip

For larger numbers, it's just more of the same. Let's say we've figured out the
number of 9-paths from each vertex to each other one:

\vspace{-.15in}
\begin{align*}
A^9 = 
\begin{bmatrix}
0 & 1 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 & 1 \\
0 & 1 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 \\
\end{bmatrix}^9 =
\begin{bmatrix}
 21 & 34 & 34 &  0 & 42 \\
 22 & 33 & 34 &  0 & 43 \\
 12 & 22 & 21 &  0 & 25 \\
 13 & 21 & 21 &  0 & 26 \\
 0 &  0 &  0 &  0 &  0 \\
\end{bmatrix}.
\end{align*}
\vspace{-.15in}

Now we want to know how many 10-paths there are. All we need to do is multiply
by $A$ one more time:

\vspace{-.15in}
\begin{align*}
A^{10} = 
A^9 \cdot A = 
\begin{bmatrix}
 21 & 34 & 34 &  0 & 42 \\
 22 & 33 & 34 &  0 & 43 \\
 12 & 22 & 21 &  0 & 25 \\
 13 & 21 & 21 &  0 & 26 \\
 0 &  0 &  0 &  0 &  0 \\
\end{bmatrix} \cdot
\begin{bmatrix}
0 & 1 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 & 1 \\
0 & 1 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 \\
\end{bmatrix}.
\end{align*}
\vspace{-.15in}

Let's again consider the upper-right entry, with paths from A to E. To get the
number of 10-paths, we take the dot product of A's row with E's column:

\[
\begin{blockarray}{ccccc}
{\scriptsize\textrm{A}} & {\scriptsize\textrm{B}} & {\scriptsize\textrm{C}} & {\scriptsize\textrm{D}} & {\scriptsize\textrm{E}} \\
\begin{block}{[ccccc]}
 21 & 34 & 34 & 0 & 42 \\
\end{block}
\end{blockarray} \cdot
\begin{blockarray}{cc}
\begin{block}{c[c]}
{\scriptsize\textrm{A}} & 0 \\
{\scriptsize\textrm{B}} & 1 \\
{\scriptsize\textrm{C}} & 1 \\
{\scriptsize\textrm{D}} & 1 \\
{\scriptsize\textrm{E}} & 0 \\
\end{block}
\end{blockarray} = 21\cdot 0 + 34\cdot 1 + 34\cdot 1 + 0\cdot 1 + 42\cdot 0 =
68.
\]
\vspace{-.20in}

Here's the rationale. We can get from B directly to E. That means that any
9-path from A to B will give us a 10-path from A to E! And since there are 34
such paths, that's 34 possible A-to-E paths with B as their second-to-last
step. Similar reasoning for C as the penultimate vertex gives us our total. The
entire answer for 10-paths, if you're curious, works out to:

\vspace{-.25in}
\begin{align*}
A^{10} =
\begin{bmatrix}
34 & 55 & 55 &  0 & \textbf{68} \\
33 & 56 & 55 &  0 & 67 \\
22 & 33 & 34 &  0 & 43 \\
21 & 34 & 34 &  0 & 42 \\
 0 &  0 &  0 &  0 &  0 \\
\end{bmatrix}.
\end{align*}
\vspace{-.15in}

\bigskip

One final thing before I go. What if we wanted to know not how many paths of
\textit{exactly} length 7, but how many paths of \textit{length 7 or less}?
Easy. Any such path has 7 or fewer edges. So we can just add the number of
1-paths, the number of 2-paths, the number of 3-paths...all the way up to the
number of 7-paths. Simple matrix addition gives us that answer:

\vspace{-.25in}
\begin{align*}
A + A^2 + A^3 + A^4 + A^5 + A^6 + A^7 = 
\sum_{i=1}^7 A^i = 
\begin{bmatrix}
20 & 33 & 33 &  0 & 40 \\
21 & 32 & 33 &  0 & 41 \\
12 & 21 & 20 &  0 & 25 \\
13 & 20 & 20 &  0 & 25 \\
 0 &  0 &  0 &  0 &  0 \\
\end{bmatrix}.
\end{align*}
\vspace{-.15in}

So exactly 33 paths of 7 edges or fewer from B to C. This tells us that there's
quite a bit of information-travel potential between these two vertices, whether
they represent computers or people or something else. Applying such logic to a
social network can tell us a great deal about who the movers and shakers are in
an online community. Stay tuned for more.


% TODO: least-squares approximation (linear regression)
% (A'A)^-1 * A' is the "pseudo-inverse" of (non-square) A
% (A'A)^-1 * A' * gives the best fit parameters 

\end{alttitles}