Non-Numeric Matrices

Matrices are a fundamental part of linear algebra, and we typically think of a matrix as a 2 dimensional array of numbers. In this post, I will show that matrices can be used in other ways too, and I will show that these new types of matrices can be used to solve real problems.

Adjacency Matrix

If you are already familiar with Adjacency matrices, I recommend you skip ahead to the next section; otherwise, read on! Matrices are especially important in graph theory, as they can be used to model the structure of a graph. A graph is a set of vertices and edges, and the edges indicate how the vertices are connected. Graphs can be used to model a number of real world things: the internet, social networks, road systems, etc. One common representation of a graph is an adjacency matrix: For a matrix \( A = [a_{ij}] \), \( a_{ij} = 1 \) if node i is connected to node j and \( a_{ij} = 0 \) otherwise (Note I implicitly implied there is some ordering on the nodes). One interesting property of adjacency matrices is that you can count the number of paths between any \( 2 \) nodes in \( k \) steps using matrix exponentiation. For example, if \( A \) is my adjacency matrix, then \( A^2 \) is a matrix where \( A^2 = [a^2_{ij}] \) and \( a^2_{ij} \) counts the number of paths between \( i \) and \( j \) in exactly \( 2 \) steps. \( A^k \) has the same interpretation with \( k \) steps. This works because \( a_{ij} \) counts the number of ways to go from \( i \) to \( j \) in \( 1 \) step, and \( a_{jk} \) counts the number of ways to go from \( j \) to \( k \) in \( 1 \) step, so it seems reasonable that the number of ways to go from \( i \) to \( k \) in \( 2 \) steps is the sum of \( a_{ij} a_{jk} \) for all \( j \).

Boolean Matrices

Adjacency matrices can be used to find the connected components of a graph (not efficiently, though). For example, if we raise \( A \) to an 'arbitrarily high' power, then the non-zero entries of \( A \) indicate that the corresponding nodes are connected. Note that raising \( A \) to the power \( n \) is sufficient for a matrix of size \( n \). We can more directly answer the connected components question by introducing a new type of matrix, which I will call a Boolean matrix. Intuitively, we can think of a Boolean matrix \( A = [a_{ij}] \) as having \( a_{ij} = True \) if \( i \) is connected to \( j \) and \( a_{ij} = False \) otherwise. If we redefine addition and multiplication in terms of boolean operations, then we can leverage the same matrix exponentiation idea for Boolean matrices. Thus, we can answer questions such as: "Is \( j \) reachable from \( i \) in \( p \) steps?". If we define addition for booleans to be "Or" and multiplication for booleans to be "And", then we get the desired properties. We can intuitively justify this choice because if \( i \) is connected to \( j \) in \( 1 \) step, and \( j \) is connected to \( k \) in \( 1 \) step, then surely \( i \) is connected to \( k \) in \( 2 \) steps. Since both \( a_{ij} \) and \( a_{jk} \) must be true for \( a^2_{ik} \) to be true, we want multiplication to be "And": $$ a_{ij} a_{jk} = a_{ij} \wedge a_{jk} $$ However, in order for there to be a path between \( i \) and \( k \) in \( 2 \) steps, any \( j \) may be used as an intermediate vertex. Thus, we want addition to be "Or": $$ a_{ij} a_{jk} + a_{ij'} a_{j'k} = (a_{ij} \wedge a_{jk}) \vee (a_{ij'} \wedge a_{j'k}) $$ Thus, for two Boolean matrices \( A \) and \( B \), $$ C = A B $$ $$ c_{ij} = \sum_{1 \leq j \leq n} a_{ij} b_{jk} = \vee_{1 \leq j \leq n} a_{ij} \wedge a_{jk} $$

Haskell Implementation

I will leverage the Data.Matrix module from Hackage to demonstrate Boolean matrices.
 $ cabal install matrix
Let's open up an interactive ghci session and start inspecting some of the functions that this library provides
$ ghci
Ryan> import Data.Matrix
Ryan> :type matrix
matrix :: Int -> Int -> ((Int, Int) -> a) -> Matrix a

Ryan> matrix 4 4 (\(a,b) -> a*b)
(  1  2  3  4 )
(  2  4  6  8 )
(  3  6  9 12 )
(  4  8 12 16 )

Ryan> :type fromList
fromList :: Int -> Int -> [a] -> Matrix a

Ryan> fromList 4 4 [1..16]
(  1  2  3  4 )
(  5  6  7  8 )
(  9 10 11 12 )
( 13 14 15 16 )

Ryan> :info Matrix
...
instance Eq a => Eq (Matrix a) -- Defined in ‘Data.Matrix’
instance Functor Matrix -- Defined in ‘Data.Matrix’
instance Num a => Num (Matrix a) -- Defined in ‘Data.Matrix’
instance Show a => Show (Matrix a) -- Defined in ‘Data.Matrix’
instance Foldable Matrix -- Defined in ‘Data.Matrix’ 
So we have some ways to construct matrices using matrix and fromList. The instance declarations that Data.Matrix provides are fairly expected, possibly with the exception of Num, since we don't usually think of a matrix as being a number. However, what does it exactly mean to be an instance of Num in haskell?
Ryan> :info Num
class Num a where
(+) :: a -> a -> a
(*) :: a -> a -> a
(-) :: a -> a -> a
negate :: a -> a
abs :: a -> a
signum :: a -> a
fromInteger :: Integer -> a 
All it means is we have to define the above operations. Since all the above functions make sense for Matrices, it makes sense for it to be in the Num typeclass (given that it's elements are also in the Num typeclass, that is).
Ryan> let a = fromList 2 2 [1..4]
Ryan> a
( 1 2 )
( 3 4 )

Ryan> a*a
(  7 10 )
( 15 22 )

Ryan> a^4
( 199 290 )
( 435 634 )
Now that we have an idea of what the module provides, we can return to the idea of Boolean matrices. In order to get Data.Matrix to support multiplication (and exponentiation) of Boolean matrices, we must make Bool an instance of the Num typeclass:
import Data.Matrix
import System.Random

instance Num Bool where
fromInteger 0 = False
fromInteger 1 = True
abs = undefined
signum = undefined
negate = not
(+) = (||)
(*) = (&&) 

convert :: Matrix Bool -> Matrix Int
convert = fmap (\b -> if b then 1 else 0)   

-- creates a random undirected adjacency matrix (with a sparsity factor of 0.2)
randMatrix :: Int -> Matrix Bool
randMatrix n = a + transpose a 
where a = fromList n n . map (< 0.2) $ randoms (mkStdGen 0)           
Note that I intentionally left some functions undefined (for example, abs, signum, and fromInteger when the input is not 0 or 1). While I theoretically could have implemented those functions, I will leave them undefined for simplicity. All I really care about is (+) and (*) anyway (and possibly negate if strassen's matrix multiplication algorithm is used). the choice of fromInteger 0 = False and fromInteger 1 = True is not arbitrary either (and it's not because that's how it's represented in c). It needs to be defined that way so that the identity matrix has the properties that we expect (for example, \( A I = A \) and \( I A = I \)). Also, I wrote a conversion function so we can go between Boolean Matrices to adjacency matrices. Also, it should be noted that my randMatrix function is not truly random as it is a pure function, but will appear random enough for this example. Now we are ready to create a Boolean Matrix.
Ryan> let a = randMatrix 8
Ryan> convert a 
( 0 0 1 0 0 1 0 0 )
( 0 0 1 0 0 0 0 0 )
( 1 1 0 1 0 0 0 0 )
( 0 0 1 0 0 0 0 0 )
( 0 0 0 0 1 0 0 0 )
( 1 0 0 0 0 0 0 0 )
( 0 0 0 0 0 0 1 1 )
( 0 0 0 0 0 0 1 1 )

Ryan> convert $ a^8
( 1 1 1 1 0 1 0 0 )
( 1 1 1 1 0 1 0 0 )
( 1 1 1 1 0 1 0 0 )
( 1 1 1 1 0 1 0 0 )
( 0 0 0 0 1 0 0 0 )
( 1 1 1 1 0 1 0 0 )
( 0 0 0 0 0 0 1 1 )
( 0 0 0 0 0 0 1 1 )

Concluding Remarks

Here are some key take-aways from this blog post:
  • Thinking about graphs in terms of matrices can be useful
  • Matrices make sense for more than real numbers
  • Haskell is cool and incredibly powerful
There's a lot more to talk about on this topic, and in my next blog post, I will use the same ideas on two new types of matrices. These new constructs will allow me to answer two common questions in graph theory:
  • What is the shortest distance between every pair of vertices in a graph?
  • The shortest list of actions to get between any two vertices in a graph?

Comments

Popular posts from this blog

Optimal Strategy for Farkle Dice

Markov Chains and Expected Value

Automatically Finding Recurrence Relations from Integer Sequences