## The `kaMatrix` functor

#### Synopsis

```signature kaMATRIX functor kaMatrix (KA) : kaMATRIX ```

This functor generates the Kleenean algebra of matrices over a Kleenean algebra.

#### Functor result interface

```structure Ring : KA type t val dimension : t -> int * int val tabulate : int * int -> (int * int -> Ring.t) -> t val sub : t * (int * int) -> Ring.t val map : (Ring.t -> Ring.t) -> t -> t val zero : int * int -> t val unit : int * int -> t val sum : t * t -> t val prod : t * t -> t val star : t -> t ```

#### Description

```type t ```
the type of all matrices with entries from Ring.t.

`dimension A `
returns the dimension of matrix A.

`tabulate (i, j) f `
returns a matrix whose field (i,j) contains the value f(i,j).

`sub (A, (i, j)) `
returns the value in field (i,j) of matrix A.

`map f t `
returns the matrix obtained from A by applying f to its entries.

`zero (i, j) `
returns the matrix of dimension (i,j) whose fields contain Ring.zero.

`unit (i, j) `
returns the matrix of dimension (i,j) whose fields (k,k) contain Ring.unit, and all other fiels contain Ring.zero.

`sum (A, B) `
returns the sum of A and B, by using pointwise addition Ring.sum.

`prod (A, B) `
returns the product of matrices A and B.

`star t `
returns the Kleenean closure of matrix A, defined by recursion on the dimension (for square matrices only).

KA, Path

#### Discussion

Example:

The matrix algebra can be used for an efficient `all_pairs_shortest_paths'-algorithm: To compute the minimal weight of paths between nodes i and j in a graph, the weights of arcs are coded as a matrix P over the Kleenean algebra Path. The minimal weights of paths between i and j are then the entries of P* in field (i,j).

```structure PathMat = kaMatrix(Path);

let
val z = Path.zero
val P = (PathMat.tabulate) (5,5)
(fn (0,0) => 0 | (0,1) => 3 | (0,2) => 8 | (0,3) => z | (0,4) => ~4
| (1,0) => z | (1,1) => 0 | (1,2) => z | (1,3) => 1 | (1,4) => 7
| (2,0) => z | (2,1) => 4 | (2,2) => 0 | (2,3) => z | (2,4) => z
| (3,0) => 2 | (3,1) => z | (3,2) => ~5| (3,3) => 0 | (3,4) => z
| (4,0) => z | (4,1) => z | (4,2) => z | (4,3) => 6 | (4,4) => 0
| _ => raise Size)
in
PathMat.star P
end
```
This matrix P* is sometimes computed iteratively by
```
fun fast_path M =
let
val (n,k) = PathMat.dimension M
fun f (m,M) = if n-1 <= m then M
else f(2*m, PathMat.prod(M,M))
in
f (1,M)
end;
```