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.
- 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
- 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).
3. The Algorithm
- 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.
4. Computer-Generated Results
- Mal'tsev + majority ("arithmetical"),
- Mal'tsev + 4-near-unanimity,
- refinement of Mal'tsev with directly decomposable congruences,
- 4-ary near unanimity,
- refinement of directly decomposable congruence classes,
- refinement of the egg-box property,
- refinement of normal local projections.
5. Some Theorems and Concluding 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.