### Non-Numeric Matrices 2

In my last blog post, I showed how matrices and matrix multiplication in particular can
make sense for more than just numbers. In fact, I used a boolean matrix construct
to find the connected components of a graph. In this blog post I will extend that
idea to two more types of matrices:

- "Distance" matrices to find the shortest distances between any two nodes
- Path matrices to find the (shortest) list of actions that lead between any two states

```
data Distance = NA | Distance Int deriving(Eq)
instance Show Distance where
show NA = "X"
show (Distance x) = show x
```

In order to get matrix exponentiation to work for our new data type, we need to provide at least 3
definitions: `fromInteger, (+), and (*)`

. We only need IromInteger to be defined for
'0' and '1' so the underlying matrix framework can construct a valid identity matrix. Futher,
we are going to overwrite what it means to add and multiply to fit our new problem domain
(all pairs shortest path).
The elements of our Distance matrix are the distances between nodes in our graph (or 'X' if there is no edge between them).
If we square our distance matrix, we want the resulting matrix to contain elements with the *shortest*distance between any two nodes (in two steps). If we can go from node 'A' to node 'B' in \( x \) distance and we can go from node 'B' to node 'C' in \( y \) distance, then clearly we can get from 'A' to 'C' in \( x + y \) distance through 'B'. Further, if we have a bunch of possible distances from 'A' to 'C' through arbitrary intermediate nodes, the actual distance is the minimum of that list. Thus, we want to define`(*)`

to be addition, and `(+)`

to be minimum.
We also need some sensible notion for an identity matrix. What does it mean to be '0'? What does it mean
to be '1'? Well, in math \( 0*t = 0 \) and \( 0 + t = t \). The element that satisfies this for us is
'X'; if there is no path between 'A' and 'B', then no matter what the distance between 'B' and 'C' is,
there will never be a path between 'A' and 'C' through 'B'. Further, we will always favor the existence
of a path over the non-existence of one, so 'X' + t = t no matter what t is.
'1' has to obey a similar property: \( 1 * t = t \). What element obeys that law for us? Well, since (*) is
actually addition for us, '1' is actually '0'. Here is the Haskell Num instance for this data type.
```
instance Num Distance where
fromInteger 0 = NA
fromInteger 1 = Distance 0
NA + d = d
d + NA = d
Distance x + Distance y = Distance (min x y)
NA * _ = NA
_ * NA = NA
Distance x * Distance y = Distance (x + y)
abs = undefined
signum = undefined
negate = undefined
```

Now, we can easily create a distance matrix, iteratively multiply until convergence (or exponentiate it),
and get a matrix containing the shortest distance between any two vertices.
**Ryan>** let matrix = ...
**Ryan>** matrix
( 0 X X X 1 X 93 97 )
( X 0 7 X 79 14 X 27 )
( X X 0 X 36 X X 43 )
( X 91 39 0 98 X 95 35 )
( 71 13 4 98 0 32 X X )
( 30 X 19 X 66 0 X 99 )
( X 96 12 35 71 X 0 X )
( X X 69 X X X X 0 )

Now we can simply exponentiate this matrix, and haskell will automatically know to use our custom
defined `(+) and (*)`

operators for the matrix multiplication.
**Ryan>** matrix*matrix
( 0 14 5 99 1 33 93 97 )
( 44 0 7 177 43 14 X 27 )
( 107 49 0 134 36 68 X 43 )
( 169 91 39 0 75 105 95 35 )
( 62 13 4 98 0 27 164 40 )
( 30 79 19 164 31 0 123 62 )
( 142 84 12 35 48 103 0 55 )
( X X 69 X 105 X X 0 )
**Ryan>** matrix^8
( 0 14 5 99 1 28 93 41 )
( 44 0 7 141 43 14 137 27 )
( 93 49 0 134 36 63 186 43 )
( 132 88 39 0 75 102 95 35 )
( 57 13 4 98 0 27 150 40 )
( 30 44 19 129 31 0 123 62 )
( 105 61 12 35 48 75 0 55 )
( 162 118 69 203 105 132 255 0 )

So matrix \( ^8 \) yields the matrix containing the minimum distance between a any two vertices.
Matrix multiplication is an \( O(n^3) \) algorithm, and matrix exponentiation requires a logarithmic
number of matrix multiplication (also in terms of \( n \)), so the time complexity of this
algorithm is \( O(n^3 log (n) \), which is slightly worse than the \( O(n^3) \)
Floyd-Warshall algorithm.
### Path Matrices

The last type of matrix I will talk about are what I call 'Path' matrices. This is the most complex of the three variations I've found, but we can reuse many of the same ideas from Boolean matrices and Distance matrices. The motivation for Path matrices is to be able to calculate a (shortest) path (a list of actions or transitions) between any two vertices in a graph. For simplicity, I will denote an action by the state that you end up in. Thus, the action '3' is an action that goes to state '3' regardless of the starting state. This can be changed depending on the context of the problem but this is the most obvious choice for this example. The elements of the matrix will contain the sequence of actions required to go from from one vertex to another. If no such sequence exists, then that element will contain some special value, which I will call 'None'. This leads to the following Haskell data definition:```
type Action = Int
data Path = None | Path [Action] deriving (Show, Eq)
```

The elements of the matrix will be singleton lists (or 'None') where the elements of the list
indicates the sequence of actions required to go from one vertex to another. This might
seem confusing, so here is an example to clear things up:
```
( Path [] Path [2] Path [3] None None )
( None Path [] Path [3] Path [4] None )
( None Path [2] Path [] Path [4] Path [5] )
( Path [1] None Path [3] Path [] Path [5] )
( None None None Path [4] Path [] )
```

We want to define multiplication and addition in such a way that when exponentiated,
the resulting matrix yields the shortest list of actions required to move
between any two states.
If \( [a_1, a_2 .. a_n] \) is a list of actions that result in moving from 'A'
to 'B' and \( [b_1, b_2 .. b_m] \) is a list of actions that result in moving
from 'B' to 'C', then \( [a_1, a_2 .. a_n, b_1, b_2 .. b_m] \) is a list of
actions that would go from 'A' to 'C'. Thus, multiplication should
be defined as list concatenation. Further, given two potential paths from 'A' to 'C'
we will always favor the shorter one, so we can define addition of two lists to be the one shorter in length.
The last thing we need to specify is what our '0' and '1' elements are so we can build an identity matrix.
In this case, '0' = 'None' since None * x = None and None + x = x. Further, '1' = 'Path []' since
Path [] * x = x. This leads to the following Num instance in Haskell:
```
instance Num Path where
fromInteger 0 = None
fromInteger 1 = Path []
None + p = p
p + None = p
Path xs + Path ys = if length xs <= length ys then Path xs else Path ys
None * _ = None
_ * None = None
Path xs * Path ys = Path $ xs ++ ys
abs = undefined
signum = undefined
negate = undefined
```

Now we are ready to find the shortest list of actions between any two vertices.
**Ryan>** matrix
( Path [] Path [2] Path [3] None None )
( None Path [] Path [3] Path [4] None )
( None Path [2] Path [] Path [4] Path [5] )
( Path [1] None Path [3] Path [] Path [5] )
( None None None Path [4] Path [] )
**Ryan>** matrix^2
( Path [] Path [2] Path [3] Path [3,4] Path [3,5] )
( Path [4,1] Path [] Path [3] Path [4] Path [4,5] )
( Path [4,1] Path [2] Path [] Path [4] Path [5] )
( Path [1] Path [3,2] Path [3] Path [] Path [5] )
( Path [4,1] None Path [4,3] Path [4] Path [] )
**Ryan>** matrix^5
( Path [] Path [2] Path [3] Path [3,4] Path [3,5] )
( Path [4,1] Path [] Path [3] Path [4] Path [4,5] )
( Path [4,1] Path [2] Path [] Path [4] Path [5] )
( Path [1] Path [3,2] Path [3] Path [] Path [5] )
( Path [4,1] Path [4,3,2] Path [4,3] Path [4] Path [] )

Hopefully the matrices above make sense. 'matrix' is the original matrix. 'matrix \( ^2 \)' is the
matrix where the elements are lists of actions that can be completed in \( 2 \) or less steps.
'matrix \( ^5 \)' is the final matrix that is guaranteed to have every path filled in if it
exists. For example, to go from vertex \( 1 \) to vertex \( 5 \) (top right corner of matrix),
we will follow the path: \( 1 \rightarrow 3 \rightarrow 5 \). Similarly, to go from vertex \( 5 \)
to \( 1 \), we will take the path: \( 5 \rightarrow 4 \rightarrow 1 \).
## Comments

## Post a Comment