Matrix algebras of distributive lattices

Let $L$ be a bounded distributive lattice, then $L$ is also a semiring. The idempotent semiring of matrices $Mat_n(L)$ has a natural presentation as an ordered algebraic structure, by its own additive partial order. Given a representation of $L$ by a family of sets then $Mat_n(L)$ consists of set valued matrices. Set valued matrices can then be defined by products of relation algebras.

Matrix semiring of $T_2$
The composition of two relations $R \circ S$ on a set $X$ is a relation whose entries $(a,b) \in R \circ S$ are defined by: \[ \exists x : (a,x) \in S, (x,b) \in R \] Which can be expressed as a distributive lattice polynomial: \[ \bigvee_{x \in X} (a,x) \in S \wedge (x,b) \in R \] This distributive lattice polynomial corresponds to the inner product of $T_2$ valued vectors, and thus it consists of terms of the product of $T_2$ valued matrices. Thus, \[ Rel \cong Mat(T_2) \] In order to produce a proper correspondence, it is necessary to consider the different types of composition ordering and matrix representations. The most common representation of relations by matrices, uses the row-first approach. In that case, the relation algebra might correspond to the opposite semiring.

Set-valued matrices:
In order to construct a more general theory of matrices over distributive lattices, it is necessary to first construct a set-theoretic representation of $L$. \[ f : L \to \wp(X) \] This invites us to consider the theory of set-valued matrices. In these cases, the distributive lattice describing the combination of set vectors $U,V$ with indices in $I$ is: \[ U \cdot V = \bigcup_{i \in I} U_i \cap V_i \] In that case, the membership of $x$ in the above set is a distributive lattice polynomial in $T_2$ \[ x \in U\cdot V = \bigvee_{i \in I} x \in U_i \wedge x \in V_i \] This suggests that the composition of set-valued matrices in $Mat_n(L)$ is a product of compositions of relation compositions in $Mat_n(T_2)$. This leads to the theory of relation decompositions.

Example. let $S = {a,b,c}$ \[ \begin{bmatrix} \{a\} & \{a,b\} & \{b\} \\ \{a,c\} & \{a\} & \{a,b\} \\ \{c\} & \{a,c\} & \{a\} \end{bmatrix} \] We can split this up into three adjacency matrices $M_a,M_b,M_c$. \[ M_a = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 1 \end{bmatrix} , M_b = \begin{bmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{bmatrix}, M_c = \begin{bmatrix} 0 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 0 \end{bmatrix} \] This turns $M$ into an indexed family of relations. Then composition of matrices in $Mat(L)$ then simply becomes the composition of a product of relations.

The matrix algebra:
Let $L$ be a distributive lattice, with set theoretic representation $f : L \to \wp(S)$. Then we can naturally turn any $L$ matrix into a $S$ indexed family of relations, whose composition is the componentwise composition of relations. If $L$ is a finite boolean algebra, then this is equivalent to a product of relation algebras.

In the case that $L$ is not a boolean algebra, such as the ordered triple $T_3$ which has set theoretic representation $\emptyset, \{a\},\{a,b\}$ then we get an indexed family of relations $\{R_a,R_b\}$ except with the condition that $R_b \subseteq R_a$, so that matrices over $T_3$ are a totally ordered family of relations. The specialization order of the set theoretic representation corresponds to the inclusion ordering of the relation decomposition of the matrix representation.

The matrix semiring construction provides order-theoretic foundations for the relation algebra. The relation algebra $Rel$ can be construed as the matrix semiring over the ordered pair $T_2$, the simplest non-trivial case of a matrix semiring over a distributive lattice.

Category theory typically deals with the composition of morphisms one at a time, this problem is dealt with by the use of idempotent semirings. This provides a matrix theoretic representation for the simplest of these semirings, the semiring of families of morphisms of a complete thin groupoid.