Let us have a number of locations and a set of so-called directed connections between them.
Directed means that directions go one-way only. For instance:
Four locations: L1 — L4 that have the following connections:
From L1 to L2 and L4.
From L2 to L1 and L3 and L4.
From L3 to L2 and L4.
No connections away from L4.
We can represent this with a matrix with the rows representing the origins (From) of the
connections and the columns representing the destinations (To) of the connections. A value of 1
represents a connection; a 0 represents the absence of a connection.
L1
L2
L3
L4
L1
0
1
0
1
L2
1
0
1
1
L3
0
1
0
1
L4
0
0
0
0
We can now ask how many routes (aka paths) exist from one location to another. For instance,
if we want to travel from L1 to L4, there are quite a few ways to do it. For example:
1-step path: from L1 to L4.
2-step path: from L1 to L2, and then from L2 to L4.
3-step path: from L1 to L2, then from L2 to L3, and then from L3 to L4.
Obviously, there are more ways to travel from L1 to L4 is you allow for revisiting a location along the way;
for example: L1 —> L2 —> L3 —> L2 —> L4
Although with a small set of locations such as in the example, these paths are not that difficult
to find, they become a lot harder (more work) to find when the set of locations and connections grows.
Lucky for us, matrix arithmetic makes this much(!) easier:
!! To find all n-step paths, simply raise the connection matrix to the power of n!!
1, 2
For example, if we call the above connection matrix M, M2 is the matrix
containing the counts of all the 2-step connections between all locations:
M2
=
L1
L2
L3
L4
L1
1
0
1
1
L2
0
2
0
2
L3
1
0
1
1
L4
0
0
0
0
Similarly, to find all 3-step path counts between locations:
M3
=
L1
L2
L3
L4
L1
0
2
0
2
L2
2
0
2
2
L3
0
2
0
2
L4
0
0
0
0
Just some spot checking: two 3-step routes from L1 to L4?
L1 —> L2 —> L3 —> L4
L1 —> L2 —> L1 —> L4
To play with this, follow these steps:
Specify the number of locations.
Hit Make connection matrix!
Fill in the connection matrix: use '1' to indicate a connection and '0' to indicate the absence of a connection.
Specify how many steps paths must have.
Hit Compute path count!
Number of locations (0 <= Number of locations <= 10):
Connection matrix:
Path count matrix:
Steps in path?
1 Here we do not go into how to multiply matrices with each other. 2 Matrix × matrix multiplication is (generally) not commutative; i.e., A × B ≠ B × A.