Adjacency matrices

A matrix is a way of describing pairwise relationships. A matrix looks like a grid of numbers, as in the following example:

┌           ┐
│ 0    1 42 │
│ 0.5 -3  1 │
└           ┘

The preceding matrix contains six entries, organized in two rows and three columns. A matrix can have any number of rows or columns, but they are always rectangular. A matrix with two rows and three columns is described as a 2 x 3 matrix. If the entire matrix is called A, then the element at row i and column j is called A_i,j. So, in the preceding example, A_2,1 = 0.5.

One way to represent a graph as a matrix is to place the weight of each edge in one element of the matrix (or a zero if there is no edge). So, an edge from v₃, to v₁ with a weight of 37 would be represented by A_3,1 = 37, meaning the third row has a 37 in the first column...