The poset of matrix properties

Below are the notes for the talk above, given at the Algebra, Geometry, Topology & Applications seminar.

1. Bird's-Eye View of Exactness Properties 

One of the active areas of research in Categorical Algebra is the study of various properties of categories expressed using limits and colimits. Such properties are usually referred to as exactness properties. This terminology comes from the fact that, historically, the first such properties emerged in the study of exact sequences in the sense of Homological Algebra. The matrix properties in the title of this post are particular types of exactness properties, which can be encoded using integer matrices. Before explaining what they are, let us first recall the notions of limit and colimit.

Given a diagram of objects and arrows (objects are certain mathematical structures and arrows are morphisms between them), a limit (of the diagram) is a way to encode the information about the diagram in a single object; it is a terminal (commutative) cone over the diagram. The notion of a colimit is defined by "reversing arrows" in the definition of a limit.

Examples of limits and colimits abound in mathematics:

• Various complex topological spaces are colimits of diagrams of simpler spaces.
• Higher dimensional vector spaces are limits of lower dimensional spaces.
• Cartesian products of mathematical structures (e.g., sets, groups, topological spaces with the Tykhonov topology) are instances of limits.
• Every set is a colimit of singleton sets. A singleton set itself is a limit of the empty diagram.
• Starting with a unit interval, combining limits and colimits we can build spaces such as the sphere, the torus and the Klein bottle (among many others).
• The monoid of words decomposes as a colimit of multiple copies of the additive monoid of natural numbers. 
• Taking the quotient of a mathematical structure (e.g., of a set by an equivalence relation, or of a group by a normal subgroup), is an example of a colimit.
• Intersection of subsets of a set and inverse image of a subset along a function are examples of limits.
• Profinite structures (e.g., profinite groups) are special types of limits of finite structures.
• Addition and multiplication of natural numbers are examples of colimits and limits.
• etc.

Each of these examples require a suitable category, in which it is specified what objects are, what morphisms are between objects (arrows), and how we compose them (which we need for expressing commutativity). The following two points are worth noting:

• For a given diagram, its limit (as well as colimit), when the latter exists, is unique, but only up to isomorphism.
• Every limit is a colimit in the dual category (a category obtained from a given one by reversing the direction of arrows).

From a concrete perspective, which looks at mathematical structures through the lenses of their elements, limits and colimits are tools for constructing local objects in a given universe of mathematical structures. From a more abstract perspective, limits and colimits are tools for analyzing global properties of universes of structures. Here is a striking analogy: in real life, addition and multiplication of natural numbers are means for accumulating quantity; in number theory, they are means for studying the natural number system. This is not a mere analogy, as addition and multiplication of natural numbers are instances of colimits and limits in the category where objects are natural numbers and a morphism from, e.g., 2 to 5, is a function from the set {0,1} to the set {0,1,2,3,4}.

Picking up on the previous analogy, as much as the study of the natural number system employs analysis of properties of multiplication and addition, the study of a category employs analysis of properties of limits and colimits. It turns out that properties which involve limits or colimits only, are much easier to study, than properties which involve both limits and colimits. This is in fact true in number theory as well, where purely from the additive point of view, the natural number system is nothing other than the monoid of words of a singleton alphabet, i.e., it is a free monoid over a singleton, and from the multiplicative point of view, it is a free commutative monoid over a countable set (namely, the set of prime numbers via the prime number decomposition). However, unlike in number theory, we are not studying here a single category, but all of them, which brings in properties that are not necessarily true in every category. Determining implications between those properties can be a nontrivial task, even if the properties are expressed in terms of limits or colimits alone.

2. Matrix Properties

In an n-dimensional cube, mark some vertices with a blue marker, and mark one of them with red. Then, consider a property of a mathematical structure X which states that for every representation of the cube in the n-th power of X, and for every substructure S of the n-th power of X, if the blue vertices fall in S, then so must the red vertices.   

This becomes a property of a category, if we ask the property to hold for every object X in the category (to formulate the categorical property, one would use "generalized elements" in the place of "elements"). Such property can be represented using a matrix of 0's and 1's, where each column of the matrix is a column-vector of coordinates of blue vertices, provided we choose the red vertex to be the point with all coordinates equal to 0. Hence the name matrix property. For the rotating figure above, the matrix will be:

    Points: C D F B H I P

   Axis AI: 0 0 0 0 0 1 1

   Axis AB: 0 0 0 1 1 0 1

   Axis AD: 0 1 1 0 1 0 1

   Axis AC: 1 0 1 0 1 0 1

Now, representing the cube in the n-th power of X amounts to choosing elements of X that will be called 0 and 1. In this case n = 4 and the property states that for arbitrary choice of 0 and 1 in X, if all columns of the matrix above belong to some substructure of X, then so does the column of zeros. We give here two examples of categories having this specific matrix property:

• The category of groups. If X is a group, then we can express A as e.g. A = C - F + D.
• The category of lattices. If X is a lattice, then we can express A as e.g. A = (C /\ D) \/ (D /\ B) \/ (B /\ C).

The same property turns out to hold in the dual category of the category of sets, as well as in the dual of the category of topological spaces, and many other categories.

In the figure above, if we delete the points B, H, I, P, we will obtain a matrix property that defines Mal'tsev categories, among which are many categories of group-like structures as well as the dual of any topos. On the other hand, if we delete the points F, H, I, P, then we will obtain a matrix property that defines majority categories. Majority categories play a similar role for lattice-like structures as Mal'tsev categories do for group-like structures. Many theorems for groups and other similar structures can be proved in Mal'tsev categories. Similarly, many theorems for lattice-like structures can be proved in majority categories. The dual of the category of topological spaces happens to be a majority category, but not a Mal'tsev one.

The matrix property defining Mal'tsev categories implies the property given by the matrix above, simply because one matrix can be obtain from the other by deleting some columns. This is intuitively clear: if fewer blue vertices guarantee the red, then a surplus of blue vertices will still do the same. The majority property implies the property above for the same reason. However, in general, implications of matrix properties are not given by merely addition of columns. These implications are context sensitive (for which class of categories do we want the implication to hold?) and in the context of algebraic categories, where matrix properties become a special type of linear Mal'tsev conditions, we do not know yet an algorithm for deciding them. Very recently, we found an algorithm for deciding implications of matrix properties in the context of categories having finite limits. This context is the context for definitions of Mal'tsev category, majority category, as well as many others that have been studied in Categorical Algebra since 1990's, and hence it is a natural habitat of matrix properties. The algorithm settles a problem that has been open since a general notion of a matrix property was first proposed in my MSc Thesis in 2004.

3. The Algorithm

The algorithm for deciding implications of matrix properties has a geometric description. To explain it, we first need to define a notion of a reduction of a matrix. We will say that a matrix L is a reduction of a matrix M when L can be obtained from M by a succession of the following transformations:

• Expansion: when a new dimension is added to the cube (in any position), but the colored vertices do not change their position.

• Collapse: when one of the dimensions of the cube is collapsed and the colored vertices are projected along the collapsing dimension.

• Tilt: when given two dimensions in the cube, such that all colored vertices are on the same end of the first dimension, colored vertices on one side of the second dimension slide along the edges of the first dimension.

• Inside-out turn: when all colored vertices change their position on the edge of a given dimension. 

If the structure of blue vertices of a reduction L of M can be embedded in N, then we can add to N a blue vertex at the relative position of the red vertex in L. The algorithm says that M will imply N provided after a series of increments of blue vertices in N using reductions of M, the red vertex of N will get colored blue. 

The only time this algorithm will fail to detect matrix implication is when M has the following reduction

   1 0 

   0 1

and N has the following reduction

        1

In these two cases, the matrices M and N do imply each other and moreover, they imply all other (nonempty) matrix properties. Categories having these properties are preorders -- this is the trivial case.

A similar algorithm works if we want to establish that a conjunction of a family of matrix properties implies another matrix property, except that then the reductions L which are used to increment N can each time be reductions of a different matrix in the family.

4. Computer-Generated Results

The algorithm allowed us to use computer programming for computing various fragments of the poset of matrix properties of categories having finite limits. The image below displays the poset of non-trivial 3-dimensional matrix properties (excluding the matrix property that holds for all categories -- the anti-trivial case). In this image, shaded cells represent the entry 1 in the matrix, while unshaded ones represent the entry 0.

All of the implications above can actually follow from deletion of columns except the very bottom one. We leave it as an exercise to establish the bottom implication using the algorithm described above. The poset of (non-trivial and non-anti-trivial) 4-dimensional matrix properties is much larger. There are altogether 442 non-equivalent 4-dimensional matrix properties, with the following distribution, where the numbers on the horizontal axis count blue vertices on the 4-dimensional cube:

It is difficult to display all 442 of the 4-dimensional matrix properties on one picture, so will limit the number of columns (blue vertices) to 6:

The highlighted matrices represented exactness properties already encountered in literature (in most cases, in the case of algebraic categories). Read from bottom to top, left to right, they are:

• Mal'tsev + majority ("arithmetical"),
• Mal'tsev + 4-near-unanimity,
• majority,
• 4-minority,
• refinement of Mal'tsev with directly decomposable congruences,
• minority,
• Mal'tsev,
• 3-edge,
• 4-ary near unanimity,
• 4-edge,
• refinement of directly decomposable congruence classes,
• refinement of the egg-box property,
• refinement of normal local projections.

5. Some Theorems and Concluding Remarks

The algorithm is useful not only for using the computer to generate fragments of the infinite poset of exactness properties, but also for proving theorems about exactness properties that help one understand the structure of this poset. Some of these theorems were inspired by the computer-generated pictures. Here we briefly review some of the theorems that we managed to establish thus far.

Theorem. The infinite poset of matrix properties given by diagonal matrices is as described in the figure below. 

Diagonal matrices are those where the only non-zero entries lie on the main diagonal, but the red vertex need not have all coordinates equal to 0. In the figure below, m represents the dimension of the diagonal matrix and k represents the number of non-zero coordinates of the red vertex.

Theorem. The conjunction of Mal'tsev and majority properties (i.e., the "arithmetical" case) implies any other non-trivial matrix property.

Theorem. Each matrix property is either implied by the majority matrix or implies the Mal'tsev property (but not both).

Theorem. Among matrix properties that are not anti-trivial, there are no maximal matrix properties.

We conclude with a few important remarks:

• In this post, we limited our attention to binary matrix properties, i.e., when the entries in the matrix are either 0 or 1. The theorems above are valid only in the binary case. The geometric interpretation of matrix properties using n-dimensional cubes is also only valid in the binary case.
• The algorithm for deciding implications of matrix properties was established in [HJJ]. The pictures of some fragments of the poset of matrix properties are also from [HJJ].
• The theorems above are from [HJJvdW].
• Matrix properties were first introduced in [J] (see [HJJ] for additional references).
• Majority categories were first introduced in [H], by an application of the "matrix method" for translating universal-algebraic properties into exactness properties described in [J].
• The notion of a Mal'tsev category, defined in the context of categories having finite limits, first appeared in [CPP].
• This post is an extension of another post, which gives a shorter and a complementary account of the results discussed here.
• The geometric interpretation of the algorithm presented in this post is an original contribution of the post. A paper will be written up on it, hopefully some time soon.
• Moving diagrams were designed on Geogebra, recorded using Wondershare UniConverter, and turned into gif files using ezgif.
• Python implementation of the algorithm can be found here. The software is called "mclex".
• The fourth author of [HJJvdW] was a first-year student at Stellenbosch University, when he joined the research project.

References

[CPP] A. Carboni, M.C. Pedicchio, and N. Pirovano, Internal graphs and internal groupoids in Mal’cev categories, Canadian Math. Soc. Conference proceedings 13, 1992, 97-109.

[H] M. Hoefnagel, Majority categories, Theory and Applications of Categories 34, 249-268, 2019.

[HJJ] M. Hoefnagel, P.-A. Jacqmin, and Z. Janelidze, The matrix taxonomy of finitely complete categories, submitted for publication, 2021.

[HJJvdW] M. Hoefnagel, P.-A. Jacqmin, Z. Janelidze, and E. van der Walt, On binary matrix properties, submitted for publication, 2021.

[J] Z. Janelidze, Matrices of terms and relations in categories, MSc Thesis, Tbilisi State University, 2004.