### The Nucleus of a Profunctor: Some Categorified Linear Algebra

#### Posted by Simon Willerton

Most of us learnt as undergraduates that from an $n\times m$-matrix $M$ you get two linear maps $M\colon \mathbb{R}^{m}\to \mathbb{R}^{n}$ and $M^{\text{T}} \colon \mathbb{R}^{n}\to \mathbb{R}^{m}$, and that these are adjoint with respect to the standard inner products on $\mathbb{R}^{m}$ and $\mathbb{R}^{n}$: $\langle M^{\text{T}} p,q\rangle _{\mathbb{R}^{m}} = \langle p, M q\rangle _{\mathbb{R}^{n}}.$ I want to explain how I think of (at least part of) an enriched category construction, the nucleus of a profunctor, as being analogous. I learnt about the nucleus idea in a recent paper by Dusko Pavlovic.

Quantitiative Concept Analysis, in Formal Concept Analysis, Lecture Notes in Computer Science, Volume 7278 (2012) 260–277; also arxiv:1204.5802

The construction does seem to have been described before for categories enriched over quantales in the following paper, but I don’t know if it’s known in the category theoretic community at large.

Javier Gutiérrez García, Iraide Mardones-Pérez, María Angeles de Prada Vicente, and Dexue Zhang, Fuzzy Galois connections categorically, Mathematical Logic Quarterly 56, No. 2, 131–147 (2010).

Let’s fix a suitable category $\mathcal{V}$ to enrich over. Pick $\mathcal{V}=\text{Set}$ if you are more comfortable with ordinary categories, so that a $\mathcal{V}$-category is just an ordinary small category.

The analogue of a matrix in the world of $\mathcal{V}$-categories is a profunctor $\mathcal{M}\colon \mathcal{A}^{\mathrm{op}}\otimes \mathcal{B}\to \mathcal{V}$. This gives rise to two $\mathcal{V}$-functors $\mathcal{M}_{\ast }\colon (\mathcal{V}^{\mathcal{B}})^{\mathrm{op}}\to \mathcal{V}^{\mathcal{A}^{\mathrm{op}}}$ and $\mathcal{M}^{\ast }\colon \mathcal{V}^{\mathcal{A}^{\mathrm{op}}}\to (\mathcal{V}^{\mathcal{B}})^{\mathrm{op}}$ which are adjoint $(\mathcal{V}^{\mathcal{B}})^{\mathrm{op}}(\mathcal{M}^{\ast }p,q)\cong \mathcal{V}^{\mathcal{A}^{\mathrm{op}}}(p,\mathcal{M}_{\ast }q).$ What we will actually be interested in the nucleus, which is the centre, or invariant part, of this adjunction. In the linear algebra world, the analogue of this is the fixed point set of $M^{\text{T}}M\colon \mathbb{R}^{m}\to \mathbb{R}^{m}$ or equivalently the fixed point set of $M M^{\text{T}}\colon \mathbb{R}^{n}\to \mathbb{R}^{n}$. Rather naughtily, I won’t motivate the construction in this post, but in the next post, hopefully, I will discuss Formal (and Fuzzy) Concept Analysis and describe what this has to do with it.

The observant amongst you might have observed that this is a generalization of the Isbell completion of a category which I have mentioned here before. In that case you work with the identity profunctor, $\text{Hom}\colon \mathcal{A}^{\mathrm{op}}\otimes \mathcal{A}\to \mathcal{V}$.

### Some undergraduate linear algebra (done a bit oddly)

I will change the notation slightly from the introduction and work with two finite sets $A$ and $B$ rather than two integers $n$ and $m$. If we pick an ordering on $A$ and $B$ then we can identify them with $\{ 1,\dots ,n\}$ and $\{ 1,\dots , m\}$.

Associated to $A$ and $B$ are the free-vector spaces on $A$ and $B$, namely $\mathbb{R}^{A}$ and $\mathbb{R}^{B}$. We can think of $\mathbb{R}^{A}$ in at least two way: on the one hand as the set of formal linear combinations of elements of $A$; and on the other hand as the $\mathbb{R}$-valued functions on $A$. We will think of it here as the $\mathbb{R}$-valued functions, and so if $p\in \mathbb{R}^{A}$ is a vector and $a\in A$ then we will write $p(a)$ for the $a$ component of the vector. As undergraduates, we would more likely write $p_{a}$ for this.

The vector spaces $\mathbb{R}^{A}$ and $\mathbb{R}^{B}$ have canonical inner products on them, namely, for $p,p'\in \mathbb{R}^{A}$ we have $\langle p,p'\rangle _{\mathbb{R}^{A}}\coloneqq \sum _{a\in A}p(a) p'(a).$ Starting with an $A\times B$-matrix $M\colon A\times B\to \mathbb{R}$ we can get a pair of adjoint maps $M_{\ast }\colon \mathbb{R}^{B}\to \mathbb{R}^{A}$ and $M^{\ast }\colon \mathbb{R}^{A}\to \mathbb{R}^{B}$. In each case, we form the map in two steps.

For the first map, starting with the matrix $M\colon A\times B\to \mathbb{R}$, we take the adjoint (such an over worked word!) to get a function $B\to \mathbb{R}^{A}$ given by $b\mapsto (a\mapsto M(a,b))$. We then use the fact that $\mathbb{R}^{B}$ is the free vector space on $B$ so there is a unique linear extension of that function to $M_{\ast }\colon \mathbb{R}^{B}\to \mathbb{R}^{A}$. This is the linear map that you think it is: $(M_{\ast }q)(a)\coloneqq \sum _{b\in B}M(a,b) q(b).$ As undergraduates we would write this as $(M q)_{a}=M_{a b}q_{b}$, if we were using the Einstein summation convention.

Similarly, for the second map we perform two steps. Firstly we start with $M$ and take the adjoint function $A\to \mathbb{R}^{B}$ given by $a\mapsto (b\mapsto M(a,b))$. Then we extend this by linearity to get a linear function $M_{\ast }\colon \mathbb{R}^{A}\to \mathbb{R}^{B}$ which is given by $(M_{\ast }p)(b)\coloneqq \sum _{a\in A}M(a,b) p(a).$ In undergraduate notation we might write $(M^{T}p)_{b}=M_{a b}p_{a}$.

Now these two functions we have constructed are adjoint in that $\langle M^{\ast }p,q\rangle _{\mathbb{R}^{B}} = \langle p, M_{\ast }q\rangle _{\mathbb{R}^{A}},$ this is easy to see as both left and right hand side are equal to $\sum _{a\in A,b\in B}M(a,b)p(a) q(b).$ I’ve gone through that in some gory detail, so that the ideas of the categorification I’m about to do will look analgous.

### Some categorified linear algebra

Let’s fix a suitable category $\mathcal{V}$ to enrich over, this should be closed symmetric and sufficiently complete and cocomplete. As I said above, think of $\mathcal{V}=\text{Set}$ if you are more comfortable with ordinary categories, so that a $\mathcal{V}$-category is just an ordinary small category.

I like thinking about metric-like things so I would find $\mathcal{V}=[0,\infty ]$ interesting, although a good, motivating example will also come from taking $\mathcal{V}=\{ \text{true},\text{false}\}$ so that $\mathcal{V}$-categories are preorders. We won’t see this example until next time though. Suppose that $\mathcal{A}$ and $\mathcal{B}$ are $\mathcal{V}$-categories. Associated to $\mathcal{A}$ (and similarly to $\mathcal{B}$) are the $\mathcal{V}$-categories of presheaves $\hat{\mathcal{A}}$ and opcopresheaves $\check{\mathcal{A}}$. Both of these should be thought of as being like scalar-valued functions on $\mathcal{A}$, that is to say, analogues of $\mathbb{R}^{A}$.

The category of **presheaves** $\hat{\mathcal{A}}$ is the functor $\mathcal{V}$-category $\mathcal{V}^{\mathcal{A}^{\mathrm{op}}}$, so an object of $\hat{\mathcal{A}}$ is a functor $\mathcal{A}^{\mathrm{op}}\to \mathcal{V}$. Associated to a pair of presheaves $p,p'\in \hat{A}$ is not a number, but rather the hom-$\mathcal{V}$-object:
$\hat{\mathcal{A}}(p,p')=\int _{a\in \mathcal{A}}[p(a),p'(a)].$
Here the square brackets mean the internal hom in $\mathcal{V}$. You should compare this formula to the definition of the inner product on $\mathbb{R}^{A}$: we had $\langle p, p'\rangle _{\mathbb{R}^{A}} \coloneqq \sum _{a\in A} p(a)p'(a)$.

Analogous to $\mathbb{R}^{A}$ being the free vector space on $A$, we have that the category of presheaves $\hat{\mathcal{A}}$ is the free cocomplete category on $\mathcal{A}$, which means that if $F\colon \mathcal{A}\to \mathcal{C}$ is a functor to a cocomplete category $\mathcal{C}$ then there is a unique (up to isomorphism) cocontinuous functor $\hat{\mathcal{A}}\to \mathcal{C}$ extending $F$.

Similarly, the category of **opcopresheaves** $\check{\mathcal{A}}$ is the $\mathcal{V}$-category $(\mathcal{V}^{\mathcal{A}})^{\mathrm{op}}$.

Now suppose that $\mathcal{M}$ is a profunctor from $\mathcal{A}$ to $\mathcal{B}$, this means, using Pavlovic’s convention, that it is a functor $\mathcal{M}\colon \mathcal{A}^{\mathrm{op}}\otimes \mathcal{B}\to \mathcal{V}$. This is clearly the analogue of a matrix. As we did with ordinary linear algebra, we will produce a pair of adjoint functors $\mathcal{M}^{\ast }\colon \hat{\mathcal{A}}\to \check{\mathcal{B}}$ and $\mathcal{M}_{\ast }\colon \check{\mathcal{B}}\to \hat{\mathcal{A}}$.

To produce these functors we proceed as we did above. For $M_{\ast }$, we take the adjoint of the profunctor $\mathcal{M}\colon \mathcal{A}^{\mathrm{op}}\otimes \mathcal{B}\to \mathcal{V}$ to get a functor $\mathcal{B}\to \mathcal{V}^{\mathcal{A}^{\mathrm{op}}}=\hat{\mathcal{A}}$ given by $b\mapsto (a \mapsto \mathcal{M}(a,b))$. As the presheaf category $\hat{\mathcal{A}}$ is complete, we can take the unique continuous extension to the free completion of $\mathcal{B}$, to get the continuous functor $\mathcal{M}_{\ast }\colon \check{\mathcal{B}}\to \hat{\mathcal{A}}$. You can show that this has the following form $(\mathcal{M}_{\ast }q)(a) = \int _{b} [q(b),\mathcal{M}(a,b)].$ Again this needs comparing with the comparable formula in linear algebra: $(M_{\ast }q)(a)\coloneqq \sum _{b\in B} M(a,b)q(b)$.

Similarly for $\mathcal{M}^{\ast }$, we take the adjoint of the profunctor $\mathcal{M}\colon \mathcal{A}^{\mathrm{op}}\otimes \mathcal{B}\to \mathcal{V}$ to get a functor $\mathcal{A}^{\mathrm{op}}\to \mathcal{V}^{\mathcal{B}}$ which is the same as a functor $\mathcal{A}\to (\mathcal{V}^{\mathcal{B}})^{\mathrm{op}}=\check{\mathcal{B}}$ given by $a\mapsto (b \mapsto \mathcal{M}(a,b))$. As the presheaf category $\check{\mathcal{B}}$ is cocomplete, we can take the unique cocontinuous extension to the presheaves category on $\mathcal{A}$, to get the cocontinuous functor $\mathcal{M}^{\ast }\colon \hat{\mathcal{A}}\to \check{\mathcal{B}}$. You can show that this has the following form $(\mathcal{M}^{\ast }p)(b) = \int _{a} [p(a),\mathcal{M}(a,b)].$ Again this needs comparing with the comparable formula in linear algebra: $(M_{\ast }q)(a)\coloneqq \sum _{b\in B} M(a,b)q(b)$.

Now we have a cocontinuous functor $\mathcal{M}^{\ast }\colon \hat{\mathcal{A}}\to \check{\mathcal{B}}$ and a continuous functor $\mathcal{M}_{\ast }\colon \check{\mathcal{B}}\to \hat{\mathcal{A}}$. You will not be surprised to learn that the former is left adjoint to the latter: $\check{\mathcal{B}}(\mathcal{M}^{\ast }p,q)\cong \hat{\mathcal{A}}(p,\mathcal{M}_{\ast }q).$ It is not difficult to show that both sides are isomorphic to $\int _{a,b}[p(a)\otimes q(b),\mathcal{M}(a,b)]$. Again the comparison with the linear algebra case is telling: $\langle M^{\ast }p,q\rangle _{\mathbb{R}^{B}} = \langle p, M_{\ast }q\rangle _{\mathbb{R}^{A}}=\sum _{a,b}M(a,b)p(a) q(b)$.

### The nucleus of a profunctor

The nucleus of the profunctor is going to be the centre, or invariant part, of the above adjunction, so I will explain what the centre is in general. I don’t know if this is standard terminology as I learnt of it in discussion with Tom Leinster and haven’t seen it in the literature.

Suppose $F\colon \mathcal{C}\to \mathcal{D}$ and $G\colon \mathcal{D}\to \mathcal{C}$ form an adjunction $F\dashv G$. Then the following are equivalent categories (I’ll just state the objects, for simplicity). $\begin{aligned} \text{Fix}(GF)&\coloneqq \{ c\in \mathcal{C}\mid \text{ the unit }\, c\to GF(c)\, \text{ is an iso}\} \\ \text{Fix}(FG)&\coloneqq \{ d\in \mathcal{D}\mid \text{the counit}\, FG(d)\to d\, \text{is an iso}\} \\ Z(F,G)&\coloneqq \left \{ \left (c\in \mathcal{C},d\in \mathcal{D},\alpha \colon c\xrightarrow{\sim } G(d),\beta \colon F(c)\xrightarrow{\sim }d\right )\,\big |\, \alpha\, \text{and}\,\beta\,\text{are adjoint}\right \} \end{aligned}$ We can think of any one of these as being the centre of the adjunction.

The nucleus $N(\mathcal{M})$ of a profunctor $\mathcal{M}\colon \mathcal{A}^{\mathrm{op}}\otimes \mathcal{B}\to \mathcal{V}$ is then defined to be the centre of the adjunction $\mathcal{M}^{\ast }\dashv \mathcal{M}_{\ast }$.

In the linear algebra world, the analogue of the nucleus is $\text{Fix}(M^{\ast }M_{\ast })$ – or $\text{Fix}(M^{\text{T}}M)$ in more standard notation – the fixed point set of the composite of a linear map with its adjoint. It looks like it could be a standard object of study. Can anyone point me to where this is an interesting object?

In perhaps the simplest case, when we consider the identity, or hom, profunctor, $\text{Hom}\colon \mathcal{A}^{\mathrm{op}}\otimes \mathcal{A}\to \mathcal{V}$, the nucleus $N(\text{Hom})$ is the Isbell completion of the $\mathcal{V}$-category $\mathcal{A}$ which I have mentioned here at the Café.

I believe that the nucleus idea does crop up in various parts of mathematics, but I’m not really sure of how pervasive it is. Next time I will endeavour to explain what it has to do with formal (and fuzzy) concept analysis.

## Re: The Nucleus of a Profunctor: Some Categorified Linear Algebra

Interesting — I’m looking forward to hearing more.

What this makes me think of is the singular values of a matrix. Let me assume we’re working over either $\mathbb{R}$ or $\mathbb{C}$, and given a matrix $M$, let me write $M^\ast$ for either the transpose or the conjugate transpose, respectively.

The theory of eigenvalues and eigenvectors is at its most satisfying for matrices that are self-adjoint (that is, symmetric or Hermitian): e.g. then we have an orthogonal basis of eigenvectors. So, given a matrix that isn’t self-adjoint, we might seek to turn it into a matrix that is, then consider

itseigenvalues and eigenvectors. This is done as follows.Let $M$ be any matrix. Then $M^\ast M$ is positive semidefinite, and a general result tells us that it therefore has a unique positive semidefinite square root, $\sqrt{M^\ast M}$. This new matrix is self-adjoint.

So, we’ve succeeded in turning an arbitrary matrix $M$ into a self-adjoint matrix, $\sqrt{M^\ast M}$, in a canonical way. It bears a close relationship to $M$, at least if $M$ is a

squarematrix: for then $M = N\sqrt{M^* M}$ for some isometry $N$ (i.e. orthogonal or unitary matrix $N$).(One place to find this stuff is Chapter 7 of Axler’s

Linear Algebra Done Right. The last result I mentioned is the polar decomposition theorem, 7.41.)The

singular valuesof $M$ are the eigenvalues of $\sqrt{M^* M}$. They are always nonnegative, since $\sqrt{M^\ast M}$ is positive semidefinite.Now, what are the fixed points of $M^\ast M$? I claim they are the same as the fixed points of $\sqrt{M^\ast M}$. Indeed,

$M^\ast M v = v \iff (\sqrt{M^\ast M} + 1)(\sqrt{M^\ast M} - 1) v = 0.$

But $\sqrt{M^\ast M} + 1$ is injective (since $-1$ is not an eigenvalue of $\sqrt{M^\ast M}$), so this is equivalent to $(\sqrt{M^\ast M} - 1)v = 0$, as claimed.

Hence the fixed points of $M^\ast M$ are the eigenvectors of $\sqrt{M^\ast M}$ with eigenvalue 1. I don’t know whether there’s a standard name for the eigenvectors of $\sqrt{M^\ast M}$. Since the eigen

valuesof $\sqrt{M^\ast M}$ are called the singular values of $M$, I want to say that the eigenvectorsof $\sqrt{M^\ast M}$ are called the singular vectors of $M$. Anyway, in that language, the fixed points of $M^\ast M$ are the singular vectors of $M$ with singular value $1$.