Matrix Categories over a Semiring

Fixing a semiring of “entries” turns matrices into a category, and different entry semirings recover different combinatorial worlds such as relations, weighted graphs, and labelled graphs. This note sets up and its categorified version , where the only ingredients that matter are direct sums and a commutative-monoid enrichment.

Matrices over a semiring

Fix a (possibly noncommutative) semiring and a set of finite sets. The category has the elements of as objects and, as a morphism , an matrix of entries in ; composition is the matrix product built from ‘s addition and multiplication. A semiring suffices because no additive inverses are needed.

Combinatorial instances

Example. Relations, weighted and labelled graphs

With and (the Boolean semiring) a matrix is an adjacency relation, so presents bipartite graphs and, on a single object, . Over or a tropical semiring entries become multiplicities or weights. Over the free semiring on a label set an entry is a formal sum of words, so morphisms are edge-label-decorated graphs and the matrix product compounds labels along paths, using concatenation within a term and union across parallel paths.

Categorifying the entries

Construction with entries drawn from a category

Replace by a category with a zero object and finite biproducts. In each matrix entry is a morphism of ; the matrix product uses the biproduct for the sum and composition for the product. The construction needs only direct sums plus a commutative-monoid enrichment, a canonical addition of parallel morphisms. Biproducts supply exactly this. Ordinary is the one-object case, with hom-monoid .