Friday, July 23, 2021

Intersection semilattices of maximal cliques

Let $G$ be a graph, then the maximal cliques of the graph form a sperner family whose meet subsemilattice closure is the semilattice $M(G)$ of intersections of maximal cliques.

Example. let $A$ be a semigroup, ring, semigroup, or semiring then the maximal commuting clique intersections form a meet subsemilattice of $Sub(A)$.

The intersections of maximal cliques of $A$ are precisely the commutative subalgebras determined by the commuting graph. They produce a number of examples of commutative subalgebras in noncommutative algebra. Additionally, $M(G)$ provides an important order-theoretic account of graph properties.

Order theoretic properties of the intersection semilattice

The order types of the intersection semilattices $M(G)$ generated by maximal cliques have a complete order-theoretic classification.

Definition. let $a$,$b$ be elements of a poset then we say that $a \sim b$ provided that $\exists z: a \subseteq z \text{ and } b \subseteq z$.

Theorem. let $L$ be a meet semilattice, then it is a semilattice of intersections of the maximal cliques of a graph iff it satisfies the following two conditions:
  1. $L$ is generated by its maximal elements
  2. $L$ satisfies the upper bound sharing property: let $C$ be any clique in the upper bound sharing graph $\sim$ then $\exists z : \forall c \in C : c \subseteq z$.
Proof. Neccessity of condition (1): the maximal cliques of a graph always form a sperner family by maximality, so their intersections must always be generated by an antichain. In a meet semilattice, this antichain is the set of all maximal elements.

Neccessity of condition (2): let $C_1,C_2 \in M(G)$ such that $C_1 \sim C_2$, then $C_1$ and $C_2$ are contained in some common clique $D$, which means that $C_1$ and $C_2$ are adjacent. Let $F$ be a family of cliques of $M(G)$ that pairwise share upper bounds, then $F$ is pairwise adjacent, so that $\cup F$ forms a clique. There must be at least one maximal clique $\cup F \subseteq Z$ such that $\forall C \in F : C \subseteq Z$.

Constructive proof of sufficiency: let $L$ be a meet semilattice that satisfies these conditions. Then let $F$ be the maximal principal ideals of $L$. By condition (1) $F$ forms a sperner family. We can reconstruct the primal graph of the set system $F$ by $x \sim y$ if $\exists S \in F : \{x,y\} \subseteq S$, but this is precisely the upper bound sharing graph of $L$.

Let $C$ be any maximal clique of the upper bound sharing graph, then by condition (2) there is some clique $Z$ in $F$ that contains $C$ so that $C \subseteq Z$. It follows that any $\sim$ clique is a clique in $F$. Let $S \in F$ then $S$ is a $\sim$ clique, because $S$ is contains any pair of its own elements, and it is maximal because it is in a family $F$ that contains all its own cliques. Therefore, $F$ forms a maximal cliques family. $\square$

Suborder of adjacency principal filters:

Let $x \in G$. Then the intersection of all cliques of $M(G)$ containing $x$ is the adjacency principal filter $\uparrow x$ of $x$. This is the smallest member of $M(G)$ containing $x$. \[ \uparrow : G \to M(G) \] The image of $\uparrow$ is the subset of $M(G)$ consisting of all adjacency principal filters. The kernel of $\uparrow$ is the adjacency equality relation of $G$. The condensation of $G$ is the quotient of $G$ with respect to adjacency equality.

Theorem. the join irreducibles (excluding the minimal element as the empty join) of $M(G)$ are necessarily adjacency principal filters.

Proof. let $S \in M(G)$ be a clique in $M(G)$. Then suppose that $S$ is not an adjacency principal filter, then $S$ doesn't have any elements unique to itself, so it is the union of all its predecessors. As it is a union it is join reducible. Then suppose that a join irreducible element that is not an adjacency principal filter, then it is union irreducible which means it is join irreducible which is a contradiction. $\square$

We have the following bounds the suborder of the adjacency principal filters of $M(G)$: (1) the filters must contain all join irreducibles and (2) they can include up to the entire set $G$. The suborder of $M(G)$ consisting of adjacency principal filters is an important source of information, because it determines a graph up to adjacency equality.

Theorem. let $L$ be a semilattice with subset $S$ consisting of adjacency principal filters. Then all graphs having $S$ as a suborder of $M(G)$ equal to $L$ have the same condensation.

Proof. let $\uparrow : G \to L$ be the principal adjacency filter function for the semilattice $L$. Then we can recover $M(G)$ by recursion. \[ f(l) = \uparrow^{-1}(l) \cup \bigcup_{i \subset l} f(i)\] Then since the graph $G$ can be recovered by its maximal cliques, every graph $G$ can then be defined by its $\uparrow$ function. The adjacency equality of $G$ is the kernel of $\uparrow$, which has no effect up to condensation. Condensed graphs are therefore determined by the image of $\uparrow$ which is a suborder of $M(G)$. $\square$

Corollary. the condensation types of graphs are determined by the images of $\uparrow$, which are subobjects of the semilattice $L$.

There are generally multiple condensation types associated to a given order type $L$. This is demonstrated below.

Example 1. the cyclic graph $C_4$ it has a maximal cliques intersection semilattice of the following form, with the adjacency principal filters highlighted: the following larger graph has the same intersection order type but it has a different set of principal adjacency filters Example 2. the path graph $P_4$ has an intersection semilattice that looks like this the following larger graph has a semilattice with more adjacency principal filters In fact, every graph of with this semilattice order type has the condensation of either a path, gem, bull, or the above larger graph.

Theorem. let $G$ be a graph then $G$ is trivially perfect (e.g $P_4,C_4$-free) iff $M(G)$ is a lower tree

Proof. let $G$ be a trivially perfect graph, then removal of the center always disconnects the graph into connected components. The class of trivially perfect graphs is hereditary, so this can be applied recursively to get a lower tree decomposition of $G$. In the other direction, if the minimal element of $M(G)$ is a cut vertex, it can be removed to get connected components. In a lower tree this can be applied again recursively, to get a trivially perfect graph. $\square$

We can recover the clique graph of a graph, provided that we have the order type of $M(G)$ and its suborder of adjacency principal filters.

Proposition. let $G$ be a graph, with $M(G)$ its semilattice of intersections of maximal cliques, with $S$ its set of adjacency principal filters. Then if the minimal element of $M(G)$ is in $S$ the clique graph is a complete graph, otherwise it is equal to the independence graph of the maximal elements: two elements are independent provided they meet at the minimal element.

A graph is a clique graph provided that it has a Helly edge covering of its cliques. The Helly property of the independence graph of any semilattice $M(G)$ follows from the upper bound sharing property.

Graph theoretic properties:

The intersection semilattice has an order type and a suborder of adjacency principal filters, but it also contains additional data as a set system such as the clique number of the graph, which would not be recordered otherwise.

Proposition. the clique number of $G$ is equal to the rank of $M(G)$

A quick look at some of the set-theoretic properties of a selected assortment of classes of graphs is presented below:
$G$ $M(G)$
Empty graph Rank one family
Complete graph Unique family
Cluster graph Pairwise disjoint family
Cocluster graph Convex family
Triangle free graph Rank two family
Cotriangle free graph Cotriangle free maxima intersections
Trivially perfect graph: Lower tree ordered family
In a cluster graph, the maximal cliques correspond to connected components so that $M(G)$ is a pairwise disjoint family. In a cocluster graph, the cocluster is the graph join of empty graphs, which means that is convex from the maximal cliques of $G$ to the center.

Another case where we might want to compute $M(G)$ is when dealing with a $G$ composed from certain basic graph operations:
  • Graph coproducts: $M(C_1 + C_2) = M(C_1) \cup M(C_2) \cup \{\emptyset\}$.
  • Graph join: $M(\overline{\overline{C_1} + \overline{C_2}} ) = \{x \cup y: x \in C_1, y \in C_2\}$
  • Graph products: $M(G \times H) = \{ C_1 \times C_2 : C_1 \in M(G), C_2 \in M(H) \}$
The computation of $M(G)$ from the elementary graph operations, can aid in the computation of $M(G)$ for certain graphs $G$. Although emerging as a subsemilattice of $Sub(A)$ for certain algebraic structures, $M(G)$ also encodes a great deal about information about graphs in general.

References:
[1] Clique graphs

[2] Trivially perfect graphs

Tuesday, July 20, 2021

Relation and matrix algebras

Matrices are sort of like labeled directed graphs. They both have a combinatorial part, determined by their underlying directed graphs, and an algebraic part determined by matrix semirings. The relational aspects of the matrix algebra will be briefly discussed.

Definition. let $A$ be a semiring, with matrix semiring $Mat_n(A)$. Then the underlying relation of a matrix $R(M)$ is an adjacency matrix with one for all non-zero entries in $M$ and zero otherwise. \[ R : Mat_n(A) \to Mat_n(T_2) \] The underlying relation $R(M)$ of a matrix $M$ determines an inequality because relations form an ordered algebraic structure.

Theorem. let $M,N$ be matrices in the semiring $Mat_n(A)$ then \[ R(M\circ N) \subseteq R(M) \circ R(N) \] Proof. let $(i,j)$ be an entry in the matrix $M \circ N$ then if $(i,j) \in R(M \circ N)$ this implies that $(M \circ N)_{(i,j)} \not= 0$. The entries in a matrix can be written by a dot product $u \cdot v$ where $u$ is the $ith$ column of $N$ and $v$ is the $jth$ row of $M$. \[ u \cdot v = \sum_{i=1}^{n} u_i v_i\] Suppose that $u \cdot v \not= 0$, then this implies that there exists at least one index $i$ such that $u \cdot v \not= 0$ so that both entries at the index are not both zero. If that were not the case, then $u \cdot v$ would have to be zero. To see this notice that zero is an annihilator of every element in a semiring, so if there is a zero at each index of one of $u,v$ then $\forall i : u_i v_i = 0$.

By substitution, if $\forall n : u_n v_n = 0$ then $u \cdot v = \sum_{i=1}^n 0$, but this equals zero because the sum of any number of zeros is zero. It follows that there is at least one entry that both vectors are both not zero at. Then due to this entry $R(u) \circ R(v) = 1$ because all the dot product of $T_2$ vectors need to be one is a common non-zero entry at some index.

By the fact that $R(v_1) \circ R(v_2) = 1$ we have that $(R(M) \circ(N))_{(i,j)} = 1$, which implies that $(i,j) \in R(M) \circ R(N)$. Finally, by the fact that for all $(i,j)$ we have that $(i,j) \in R(M \circ N) \Rightarrow (i,j) \in R(M) \circ R(N)$ we know that $R(M \circ N) \subseteq R(M) \circ R(N)$. $\square$

In a semiring without additive inverses or zero divisors, like $\mathbb{N}$ then $R(M\circ N) = R(M) \circ R(N)$ and $R$ turns into a homomorphism. This relationship allow us to form subalgebras of matrix rings, from subalgebras of the relation algebra. In order to elaborate on this we must first establish the following lemma.

Lemma. let $Mat_n(T_2)$ be a matrix semiring then power sets of relations $R$ are multiplicative sets iff $R$ is transitive.

Proof. let $R$ be a relation, then in order for $\wp(R)$ to be composition closed, we must have that for all $E_1, E_2 \in R$ we have $\{E_1\} \circ \{E_2\} \in R$. This implies $R^2 \subseteq R$, so that $R$ is a transitive relation. Then if $R$ is a transitive relation and $A,B \subseteq R$ we have that $A \circ B$ consists of edges $E_1 \circ E_2$ such that $E_1 \in A$ and $E_2 \in B$, but all such edges are in $R$ since $R$ is transitive. Thus $\wp(R)$ is a multiplicative set. $\square$

We can use this to form suborders of matrix semirings. In particular, if $Mat_n(R)$ is a matrix semiring, then the subset of $Mat_n(R)$ consisting of matrices whose non-zero entries are all in a transitive relation $T$ forms a subalgebra. In short, this allows us to form subalgebras of matrices from ordering relations.

Theorem. let $R$ be a ring or a semiring, then the restriction $S$ of the matrix algebra $Mat_n(R)$ to those martices whose non-zero entries are all in a transitive relation $T$ forms a subalgebra.

Proof. this proof will split up into additive and multiplicative components.

(1) addition is defined componentwise, so any restriction of $Mat_n(R)$ to a set of non-zero entries is an additive submonoid. Negation is also defined componentwise, so in the case $R$ is a ring, then the restriction $S$ is also an additive subgroup.

(2) let $M,N$ have entries in $T$. Then because $T$ forms a composition closed class of the matrix semiring $Mat_n(T_2)$ by the previous lemma, we have that $R(M) \circ R(N) \subseteq T$, but by the inequality theorem this has $R(M\circ N) \subseteq R(M) \circ R(N) \subseteq T$. This means that the non-zero entries in $M \circ N$ are a subset of $T$, which implies that $M \circ N \in S$, so that $S$ is multiplicatively closed.

These restrictions don't necessarily need to have a multiplicative identity, which is worth pointing out. This often happens in ring theory, for example ideals don't need to have the multiplicative identity. This allows us to restrict the non-zero entries in a matrix to a transitive relation.

Example 1. diagonal matrices are determined by an antichain $i = j$

Example 2. upper triangular matrices are determined by a total order $i \leq j$

Example 3. lower triangular matrices are determined by a total order $j \leq i$

Example 4. upper triangular matrices with zero main diagonal are defined by a strict total order $i \lt j$ and lower triangular matrices with zero main diagonal are defined by the strict total order $j \lt i$.

Example 5. take any adjacency matrix of a transitive relation, and you can form rings of matrices with non-zero entries in it

References:
Triangular matrix

Saturday, July 17, 2021

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.

Commutative monoids as semimodules

The generalization of rings and modules to semirings and semimodules is justified by the fact we can use this new setting to make any commutative monoid into an $\mathbb{N}$ semimodule. Semimodules then can play a basic role in the theory of commutativity.

The basic construction:
Definition. let $R$ be a semiring and $M$ a commutative monoid, then $M$ is a (left) semimodule provided that it satisfies the following conditions:
  • Action $r(m+n) = rm + rn$.
  • Additivity $(r+s)m = rm + sm$.
  • Multiplicativity $(rs)m = r(sm)$.
  • Annihilation: $0m = r0 = 0$.
A unitary semimodule also has $1m = m$.

Theorem. let $M$ be a commutative monoid, then it is a $\mathbb{N}$ semimodule

Proof. (1) $(ab)^n = ababab...$ which by commutativity equals $a^n b^n$.
(2) $a^n a^m = \underbrace{a...}_{\text{n}}\underbrace{a...}_{\text{m}} = \underbrace{a...}_{\text{n+m}} = a^{n+m}$
(3) $(a^n)^m = \underbrace{(a^n)...}_{\text{m}} = a^{\underbrace{n...}_{\text{m}}} = a^{nm}$
(4) $a^0 = 1_M = (1_M)^n$. $\square$

This is a good first stepping stone towards a theory of commutative operations. The general idea is that commutative operations, as distinguished from non-commutative ones, are always define over some semiring: which provides coefficients, multiplicities, etc.

Guide to commutative operations:
The fact that commutative groups are $\mathbb{Z}$ modules means that different types of commutative operations are interpreted in different kinds of ways. This is described below.
  • Commutative semigroups: let $S$ be a commutative semigroup, then we can adjoin an identity to it to get $S^1$ which is a $\mathbb{N}$ semimodule.
  • Commutative monoids are $\mathbb{N}$ semimodules.
  • Commutative groups are $\mathbb{Z}$ modules.
Commutative cancellative monoids can be embedded in $\mathbb{Z}$ modules. In particular, the free commutative $\mathbb{N}$ semimodule $F(S)$ can be embedded in the free commutative $\mathbb{Z}$ module $F^{\circ}(S)$. The techniques of module theory and semimodule are very useful in the theory of commutative operations.

Data structures:
The implementation of commutative operations in a computer algebra system requires the use of a number of different data structures:
  • Multisets: $\mathbb{N}$ semimodules
  • Signed multisets: $\mathbb{Z}$ modules
  • Real valued sets: $\mathbb{R}$ modules
The use of modules and semimodules allows us to better describe the sort of data structures that are used in commutative monoids and commutative groups. Commutative monoids ($\mathbb{N}$ semimodules) deal with multisets, and commutative groups ($\mathbb{Z}$ modules) deal with computations over signed multisets.

Friday, July 16, 2021

Additive preorders of semirings

Semirings come from two major sources: classical ring theory and ordered algebraic structures. Every semiring $R$ is associated with an additive preorder: the natural increasing action preorder of the commutative additive monoid of $R$. This has $a \sqsubseteq b \Leftrightarrow \exists c : a+c = b$. This breaks up semirings into two basic classes: those whose additive preorders are symmetric and those whose preorder are antisymmetric.

Those semirings with symmetric preorder are precisely rings. To see this, notice that all J-total monoids are groups. on the other hand, it can be shown that semirings with antisymmetric preorder are ordered algebraic structures. This divides semirings along the lines that they most apppear in applications. Beyond these there are all the in between cases. The additively ordered semiring $\mathbb{N}$ is a special case, because although it is additively J-trivial it is also cancellative so that it can be embedded in a ring $\mathbb{Z}$. Most additively ordered semirings, such as the idempotent semirings emerging from quantales, cannot be embedded in rings under any circumstances. Numerical semigroups are also cancellative, commutative, and J-trivial, so they are another source of addition of semirings of this type.

Semirings with antisymmetric addition also emerge from classical ring theory. The ideals of a commutative ring form an idempotent semiring by the addition and multiplication of ideals. Radical ideals form a bounded distributive lattice $Spec(R)$ which means that they can also be represented as semirings under their lattice operations.

Theorem. let $R$ be a semiring with additive preorder $\sqsubseteq$. Then addition and multiplication are both monotone over this preorder.

Proof. (1) suppose $a \sqsubseteq b$ then $a+c = b$. Let $d$ be another element, then $(d+a)+c = (d+b)$ so $d+a \subseteq d+b$ by $c$.

(2) suppose $a \subseteq b$ then $a+c = b$. Let $d$ be another element, then $d(a+c) = da + dc = db$ so $da\subseteq db$ by $dc$. $\square$

By the preceding theorem, every semiring is a preordered algebraic structure. This is even true in the case of rings, it is just that the additive preorder on rings is the complete relation, and every map to a complete relation is monotone. Complete preorders are maximal in the hom class comparison ordering induced by underlying set functor.

In the more interesting case, when the semiring is not a ring, this turns any semiring into a preordered algebraic structure. Further, every semiring with antisymmetric preorder is an ordered algebraic structure. $\mathbb{N}$ is a good first example: both addition and multiplication are monotone over the additive ordering of the natural numbers. This is the subject of a corollary.

Corollary. let $R$ be a semiring with additive partial order $\sqsubseteq$. Then $R$ is an ordered semiring with respect to its additive ordering.

This covers the second basic case of semirings besides rings: those emerging from ordered algebraic structures. This idea neatly divides semirings into two basic classes: rings and ordered semirings. The other semirings have a mix of symmetry and antisymmetry of some kind.

Idempotent semirings are a very promising case, because they allow us to define all kinds of algebraic operations on sets: such as the arithmetic of ideals of semigroups and rings and the composition of morphism systems of a category. The use of idempotent semirings in category theory gets around the use of partial operations. There are also links between idempotent semirings, quantales, and hyperoperations that could be of use in number theory.

Wednesday, July 14, 2021

Commutativity necessary subrings

The commuting graphs of semigroups induce a number of different commutativity necessary subsemigroups: centralizers, maximal commuting cliques, commutative principal filters, the center, etc. As it it happens all of these concepts can be transferred to non-commutative rings, so that we can understand non-commutative algebra using graph-theoretic techniques.

Definition. let $R$ be a ring then the commuting graph $Com(R)$ of $R$ is the commuting graph of its multiplicative semigroup. \[ Com(R) = \{(x,y) : xy = yx \} \] The first step towards proving the existence of commutativity necessary subrings for a ring $R$ is to demonstrate that centralizers are subrings. The existence of the other types of commutativity necessary subrings immediately follows.

Theorem. let $R$ be a ring, $x$ an element of $R$, then the centralizer $S$ of $x$ is a subring. \[ S = \{ c : cx = xc \}\] Proof. (1) by basic semigroup theory, then centralizer is a multiplicative subsemigroup.

(2) by the nullary distributive law we have \[ \forall x*0 = 0 = 0*x \] It follows that $0$ is a central element which implies $0 \in S$.

(3) by the binary distributive law we have \[ x(a+b) = xa + xb = ax + bx = (a+b)x \] So the centralizer $S$ is additively closed.

(4) let $c \in R$ then $(-c)x$ is equal to $-(cx)$ by the distributive law and the definition of additive inverses. \[ cx + (-c)x = (c-c)x = 0*x = 0 \] In the other direction, $x(-c)$ is equal to $-(xc)$ for the same reasons. \[ xc + x(-c) = x(c-c) = x*0 = 0 \] Thus if $c$ is in the centralizer $S$ then so is $-c$ \[ (-c)*x = -(cx) = -(xc) = x*(-c)\] Thus $S$ is also negation closed, so that $S$ is a subring. $\square$

The first three conditions are equally applicable to semirings. Semirings axiomatically have both the binary and nullary distributive laws, which ensures that centralizers are additive submonoids. In the ring case, we see that centralizers also form additive subgroups.

All other commutativity necessary subrings can be formed by intersections of centralizers. The center is the intersection of all centralizers. Maximal commuting cliques are equal to the intersection of the centralizers of all their elements. Commutative principal filters are formed by the centralizer of the centralizer.

Centralizers:
Let $Mat_n(F)$ be the non-commutative ring of matrices over a field $F$. Then the centralizers of $Mat_n(F)$ can be computed by solving systems of linear polynomial equations. In general, the previous theorem shows that centralizers are always subrings.

Centers:
The center of any non-commutative ring is a commutative ring, over which the non-commutative ring is a ring extension. For example, the center of the quaternions $\mathbb{H}$ are the reals $\mathbb{R}$, so that $\mathbb{}$ is a four dimensional vector space over $\mathbb{R}$. In a non-commutative ring of matrices like $Mat_n(F)$ the center consists of the commutative ring of scalar matrices.

Commutative principal filters:
The commuting preorder of a ring is the adjacency preorder of its commuting graph. Then the multiplicative iteration preorder is a suborder of the commuting preorder. The principal filters of this preorder are all commutativity necessary subrings. The center is the minimal commutative principal filter.

Maximal commuting cliques:
Let $G$ be a finite graph, then every element of $G$ is contained in some maximal clique. In the infinite case we need Zorn's lemma, and the fact that the union of a chain of cliques is a clique. Then every element of an infinite graph is in a maximal clique as well. This implies that every element in a ring is contained in some commutative subring.

Theorem. monogenic rings are commutative

Proof. By Zorn's lemma every element is embedded in a maximal clique, which is a commutative subring. Then every element of a ring is embedded in a commutative subring. A monogenic subring is a minimal subring containing a given element, so it must be embedded in some greater then or equal commutative subring. The property of commutativity is hereditary, so monogenic rings are commutative. $\square$

This should work unless there is some issue with Zorn's lemma in the infinite case. This generalizes the well known fact that all monogenic semigroups are commutative, and it shows that rings can be built up from commutative building blocks.

Implications of Lagrange's theorem:
Let $R$ be a finite ring, then Lagrange's theorem implies that all the different commutativity necessary subrings have orders that divide the order of the ring $R$. In particular, the degrees of each element of the commuting graph are divisors of its order. This means that commuting graphs of rings are a lot like those for groups, but they aren't completely the same.

For example, the commuting graphs of rings don't necessarily have to have the same degree of commuting equality which is implied for in groups by Cauchy's theorem and the number of iteration equal elements $\phi(n)$ of prime cyclic groups of order $n$. Even so, Lagrange's theorem alone places a greater constraint on the set of possible multiplicative semigroups of rings.

In the case of finite division rings, we get that subalgebras must satisfy Lagrange's theorem in two different ways, corresponding to the two types of subgroups in a division ring: \[ (d)|(n) \] \[ (d-1)|(n-1) \] This places even greater constraints on the possible commuting graphs of division rings, but we can get around worrying about that altogether by Wedderburn's little theorem [1] which shows that all finite division rings are commutative. The double Lagrange's theorem still applies to finite fields.

See also:
Commutativity necessary subsemigroups

Subalgebra lattices of finite fields

References:
Weddernburn's theorem

Monday, July 12, 2021

Categorical approach to relation algebra

In the same way that composition of morphisms in a category is an extension of the composition in a preorder the composition of sets of morphisms is an extension of relation algebra. The relation algebra on a set is the quantale of morphism systems of the complete thin groupoid. As a result, morphisms are enriched ordered pairs and morphism systems are enriched relations.

The composition of morphism systems in a category is simply the set of all compositions of morphisms in each set, whenever they exist. If there are no compatible morphisms then the empty set is returned. Aside from the empty compositions, the quantale of morphism systems is similar to the quantales of sets of other algebraic structures.

Semiring of morphism systems:
Let $C$ be a category and $F,G$ families of morphisms in $C$. Then $F \circ G$ is the composition of all morphisms in $F$ and $G$ whenever they exist. This can be expressed in symbols as: \[ \bigcup_{m \in F, n \in G} \left\{ \begin{array}{ll} \emptyset & \text{Input}(m) \not= \text{Output}(n) \\ \{m \circ n\} & \text{otherwise} \end{array} \right. \] The resulting structure $(\wp(Arrows(C)),\circ)$ is a monoid with identity $I$ equal to the family of all identity morphisms of the category $C$. The composition function of a category has existence associativity, so that if $(ab)c$ exists then so does $a(bc)$ and then they both coincide. Therefore, the composition of morphism systems is also associative.

A corresponding semilattice structure $(\wp(Arrows(C)), \vee)$ can be defined by the union of morphism systems. This is a unital semilattice, by the fact that $\emptyset$ is an identity with respect to unions. In order to show that $\wp(Arrows(C))$ is a semiring, we only now need to show that these two monoids are related to one another.

Theorem. $(\wp(Arrows(C)),\vee,\circ)$ is a semiring

Proof. for the sake of notation it is convenient to replace the piecewise description of the composition of two morphisms by the composition of two singleton sets $\{m\} \circ \{n\}$. Then we can simply the rewrite the definition of composition, moving around the unions a little in order to get distributivity. \[ F \circ (G \cup H) \] \[ \bigcup_{m \in F, n \in G \cup H} \{m\} \circ \{n\} \] \[=\bigcup_{m \in F} ( \bigcup_{n \in G \cup H} \{m\} \circ \{n\} )\] \[=\bigcup_{m \in F}( ( \bigcup_{n \in G } \{m\} \circ \{n\}) \cup ( \bigcup_{n \in H} \{m\} \circ \{n\})) \] \[ = F\circ G \cup F \circ H \] It follows that $F\circ(G \cup H) = F\circ G \cup F \circ H$, the other distributive law $(F \cup G) \circ H = F \circ H \cup G \circ H$ follows by exactly the same reasoning. In order to confirm the structure is a semiring, we finally need to demonstrate that the additive identity $\emptyset$ is a multiplicative zero. In fact it is, because $\emptyset \circ A = A \circ \emptyset = \emptyset$. It follows that $\wp(Arrows(C))$ is a semiring $\square$

The relationship between the semiring of a category and its partial semigroup, is that the semiring is a multi-valued extension of the ordinary composition of morphisms. In particular, the composition function of a category $(C,\circ)$ can be recovered as a partial semigroup from the subset of the composition monoid of morphism systems consisting of all singleton morphism systems.

The composition of singleton morphisms in the case where no composition exists is the empty set. The partiality of the composition function of a category can be gotten around by adjoining a zero element. This is not necessary when the category $C$ is a monoid.

Semiring of relations:
Let $K_X$ be the complete thin groupoid on $X$. Then the morphisms of $K_X$ are ordered pairs $(a,b)$ and composition of ordered pairs $(a,b)$ and $(b,c)$ is $(a,c)$. Then since morphisms are ordered pairs, morphism systems are relations. Then the composition of relations is a special case of the composition of families of morphisms in a category: \[ R \circ S = \{ (a,c) : \exists (a,b) \in S, (b,c) \in R : (a,b) \circ (b,c) = (a,c) \}\] It follows that $(\wp(Arrows(K_X)),\circ)$ is equal to the composition of relations, and so relation algebra can be recovered by the composition of families of morphisms in a category. By the preceding theorem, $(\wp(Arrows(K_X)),\vee,\circ)$ is also a semiring as a special case of a family of morphism systems of a category.

The semiring congruence of a category:
The composition of morphism systems of a category is an extension of the composition of relations. The semiring of morphism systems of a category extends relation algebra on the semiring level.

Definition. let $F \in \wp(Arrows(C))$ be a morphism system of a category $C$. Then the underlying binary relation $T(F)$ is the subset of $\wp(Ob(C)^2)$ consisting of all ordered pairs of objects in the morphisms of $F$. \[ T : \wp(Arrrows(C)) \to \wp(Ob(C)^2) \] Theorem. let $C$ be a category then the underlying binary relation forms a congruence of the composition of morphism systems.

Proof. let $F,G$ be morphism systems with underlying binary relations $R,S$. Then if $m : A \to C \in F \circ G$ we have that there exists $f : B \to C$ in F and $g : A \to B$ in G such that $m = f \circ g$. Then $(B,C) \in R$ and $(A,B) \in S$ implies $(A,C) \in R \circ S$. In the other direction, suppose that $(A,C) \in R \circ S$ then there exists $f : B \to C$ and $g : A \to B$ such that $f \circ g : A \to C$, so that $(A,C)$ is in the underlying binary relation of $F \circ G$. $\square$

Theorem. let $C$ be a category then the underlying binary relation forms a congruence of the union of morphism systems.

Proof. let $F,G$ be morphism systems with underlying binary relations $R,S$. Then if $m : A \to B$ is in $F \cup G$ then either (1) $m \in F$ in which case $(A,B) \in R$ or (2) $m \in G$ in which case $(A,B) \in S$. Therefore, $(A,B) \in R \cup S$. In the other direction, every ordered pair in $R \cup S$ is an ordered pair of $F \cup G$, so the two coincide. $\square$

Corollary. the underlying binary relation forms a congruence of the semiring of morphism systems of a category.

The fact that the underlying binary relation is a semiring congruence, means that we can say that the composition fo morphism systems in a category is an extension of relation algebra. This is formalized by a semiring homomorphism.

Theorem. $T : \wp(Arrrows(C)) \to \wp(Ob(C)^2)$ is a semiring homomorphism from the semiring of homomorphisms of a category to the semiring of relations.

Proof. the function $T$ is defined by the image functor so it is a union homomorphism. $T(\emptyset = \emptyset)$ so $T$ also preserves additive identities. Finally, each morphism in $R \circ S$ is some composite $g \circ f : A \to C$ with $f : A \to B \in S$ and $g : B \to C \in R$ such that $(A,B) \in T(S)$ and $(B,C) \in T(R)$ so $(A,C) \in T(R) \circ T(S)$. Then in the other direction, $T(R) \circ T(S)$ is all ordered pairs $(A,C)$ such that there is a morphism $f: A \to B \in R$ and a morphism $g : B \to C \in S$ then $g \circ f \in R \circ S$ so $(A,C) \in T(R \circ S)$. Therefore, $T(R \circ S) = T(R) \circ T(S)$. $\square$

The equivalence classes of $T$ do not form intervals, so the underlying binary relation cannot form a lattice congruence. It suffices then to show that they form a semiring congruence, which we have done here.

Relation algebra:
The definition of the composition of morphism systems is based upon the union of the compositions of each individual pair of morphisms, so that composition can be union decomposed. Therefore, $\wp(Arrows(C))$ clearly forms a quantale for any category $C$ but this isn't enough to recover the full relation algebra structure. In order to do that we must recall that $K_X$ is a groupoid. \[ R^{-1} = \{ m^{-1} : m \in R \} \] The inverse of a morphism system of a groupoid is simply the set of inverses of each of its morphisms. With this groupoid-theoretic characterization we have a full characterisation of the relation algebra: $(S,\vee,\wedge, 0,1,\circ,I,-)$.
  • $\vee,\wedge$ are the union and intersection of relations. $0$ is the empty relation and $1$ is the complete relation.
  • $\circ$ is the composition of morphism systems
  • $I$ is the set consisting of all identity morphisms
  • $R^{-1}$ maps each morphism to its inverse
The residuals $R \triangleleft S$ and $R \triangleright S$ are $R \circ S^{-1}$ and $R^{-1} \circ S$, and so they are special cases of operations that can be defined for any morphism system of a groupoid. This turns the relation algebra of the complete thin groupoid into a residuated boolean algebra.

We can relate the relation algebra to general categories by the underlying binary relation congruence. In the special case of the morphism system of a groupoid, this also forms a unary congruence of the inverse operation.

Theorem. let $C$ be a groupoid with inverse operation $^{-1} : Ob(C) \to Ob(C)$. Then $T(R^{-1}) = T(R)^{-1}$. The underlying binary relation of the inverse of a morphism system, is the inverse of its underlying binary relation.

Proof. let $f : A \to B$ be a morphism in a groupoid it has ordered pair $(A,B)$ which has inverse $(B,A)$. Its inverse is $f^{-1} : B \to A$ which has ordered pair $(B,A)$ so the two coincide. This then applies to morphism systems on the level of images by these functions. $\square$

Although the morphism systems of categories always extend relations, the special properties of the relation algebra come from their embedding in a groupoid.

Properties of relations:
The properties of relations, expressed in relation algebra, are analogous to those which can be expressed in any category. The morphism system of a subsemigroupoid can be expressed by the condition: \[ R^2 \subseteq R \] The condition $R^2 \subseteq R$ in any quantale expresses composition closure. In a monoid, this defines subsemigroups of the monoid, but in the relation algebra this defines a transitive relation. Categories are basic extensions of transitivity, so transitive relations can be defined like this. The dual condition is: \[ R \subseteq R^2 \] This means that a given morphism system is self-factorizable. The idempotents of $\wp(Arrows(C))$ are clearly all morphism systems that satisfy both conditions. Relation composition forms an ordered semigroup, so that composition is bimonotone. In a number of cases it is also increasing.

When $R$ is reflexive so that $I \subseteq R$ then clearly $R$ is increasing. The same is true of morphism systems of a category with respect to the identity $I$. We have $I \subseteq R$ means that $R \circ S \subseteq R \circ I = R$ and $S \circ R \subseteq I \circ R = R$. The dual condition $I \cap R = \emptyset$ defines irreflexivity. Finally, coreflexive relations $R \subseteq I$ form a distributive lattice subsemiring.

Theorem. coreflexive relations $R \subseteq I$ form a distributive lattice subsemiring.

Proof. (1) union closure follows from the fact that $R \subseteq I$ is a principal down set, as does the membership of $\emptyset$. (2) two loop edges (a,a) are only composable when they are equal, so the composition of coreflexive relations is intersection which is again closed because $R \subseteq I$ forms a principal down set. This means multiplication is a semilattice, so that as a semiring the coreflexive relations form a distributive lattice. $\square$

Systems of identity morphisms still form a distributive lattice subsemiring in any category. The other properties of relations require the use of the inverse, which means that they are only applicable to a groupoid.
  • Symmetric : $R^{-1} = R$
  • Antisymmetric : $R^{-1} \cap R \subseteq I$
  • Functional : $R^{-1} \circ R \subseteq I$
  • Inverse functional: $R \circ R^{-1} \subseteq I$
Symmetry corresponds to inverse closure in a groupoid. Clearly, the combination of symmetry, transitivity, and reflexivity defines wide subgroupoids. In the case of of the complete thin groupoid $K_X$ we already know that this corresponds to the lattice $Part(A)$.

Corollary. the lattice $Part(A)$ is isomorphic to the family of morphism systems of the complete thin groupoid that satsify $I,R^{-1},R^2 \subseteq R$.

We see how a number of concepts like subsemigroupoids, wide subcategories, and wide subgroupoids can be defined by the algebra of morphism systems. In the case of wide thin groupoids, these create the familar classes of relations.

Subsemigroups of relations:
Every relation algebra is associated with the following composition subsemigroups: $PT_X$ consisting of all partial transformations, $PS_X$ the symmetric inverse semigroup of charts, $T_X$ the full transformation monoid, and the symmetric group $S_X$ of permutations. Each of these subsemigroups is a suborder of $Rel$. The full transformation monoid and the symmetric group form antichains, so we can ignore them for now. On the other hand, $PT_X$ and $PS_X$ both have non-trivial partial orders so we would like to relate the order on them to their semigroups.

Recall that coreflexive relations form a distributive lattice subsemigroup. Let $E$ be the composition subsemigroup of coreflexive relations of $Rel$. The composition of coreflexive relations is decreasing, so its action preorder is a suborder of the dual of the inclusion order of relations.

Input composition by a coreflexive relation is a domain restriction and output composition is codomain restriction. Thusly, the decreasing left actions by $E$ form domain restrictions of relations, which can be used to recover the inclusion ordering of $PT_X$ and $PS_X$. The natural ordering of an inverse semigroup in this context is the same as the inclusion ordering of relations.