### 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.

- 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.

- 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).

## 2. Matrix Properties

*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.

*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**

*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*).

*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.

*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

*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.

*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.

*M*has the following reduction

**1 0**

**0 1**

*N*has the following reduction

**1**

*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.

*L*which are used to increment

*N*can each time be reductions of a different matrix in the family.

## 4. Computer-Generated Results

*anti-trivial*case). In this image, shaded cells represent the entry 1 in the matrix, while unshaded ones represent the entry 0.

- 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

**Theorem.**

*The infinite poset of matrix properties given by diagonal matrices is as described 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.*- 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.