The n-Category Café

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.