Page 385 - 35Linear Algebra

G.6 Matrices 385

G.6 Matrices

Adjacency Matrix Example
Lets think about a graph as a mini-facebook. In this tiny facebook there are
only four people, Alice, Bob, Carl, and David.
Suppose we have the following relationships

• Alice and Bob are friends.
• Alice and Carl are friends.
• Carl and Bob are friends.
• David and Bob are friends.

Now draw a picture where each person is a dot, and then draw a line between
the dots of people who are friends. This is an example of a graph if you think
of the people as nodes, and the friendships as edges.
Now lets make a 4 × 4 matrix, which is an adjacency matrix for the graph.
Make a column and a row for each of the four people. It will look a lot like a
table. When two people are friends put a 1 the the row of one and the column
of the other. For example Alice and Carl are friends so we can label the table
below.
A B C D
A 1
B
C 1
D

We can continue to label the entries for each friendship. Here lets assume
that people are friends with themselves, so the diagonal will be all ones.

385