Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

August 19, 2013

The Nucleus of a Profunctor: Some Categorified Linear Algebra

Posted by Simon Willerton

Most of us learnt as undergraduates that from an n×mn\times m-matrix MM you get two linear maps M: m nM\colon \mathbb{R}^{m}\to \mathbb{R}^{n} and M T: n mM^{\text{T}} \colon \mathbb{R}^{n}\to \mathbb{R}^{m}, and that these are adjoint with respect to the standard inner products on m\mathbb{R}^{m} and n\mathbb{R}^{n}: M Tp,q m=p,Mq 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 𝒱=Set\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 :𝒜 op𝒱\mathcal{M}\colon \mathcal{A}^{\mathrm{op}}\otimes \mathcal{B}\to \mathcal{V}. This gives rise to two 𝒱\mathcal{V}-functors *:(𝒱 ) op𝒱 𝒜 op\mathcal{M}_{\ast }\colon (\mathcal{V}^{\mathcal{B}})^{\mathrm{op}}\to \mathcal{V}^{\mathcal{A}^{\mathrm{op}}} and *:𝒱 𝒜 op(𝒱 ) op\mathcal{M}^{\ast }\colon \mathcal{V}^{\mathcal{A}^{\mathrm{op}}}\to (\mathcal{V}^{\mathcal{B}})^{\mathrm{op}} which are adjoint (𝒱 ) op( *p,q)𝒱 𝒜 op(p, *q). (\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 TM: m mM^{\text{T}}M\colon \mathbb{R}^{m}\to \mathbb{R}^{m} or equivalently the fixed point set of MM T: n nM 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, Hom:𝒜 op𝒜𝒱\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 AA and BB rather than two integers nn and mm. If we pick an ordering on AA and BB then we can identify them with {1,,n}\{ 1,\dots ,n\} and {1,,m}\{ 1,\dots , m\} .

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

The vector spaces A\mathbb{R}^{A} and B\mathbb{R}^{B} have canonical inner products on them, namely, for p,p Ap,p'\in \mathbb{R}^{A} we have p,p A aAp(a)p(a). \langle p,p'\rangle _{\mathbb{R}^{A}}\coloneqq \sum _{a\in A}p(a) p'(a). Starting with an A×BA\times B-matrix M:A×BM\colon A\times B\to \mathbb{R} we can get a pair of adjoint maps M *: B AM_{\ast }\colon \mathbb{R}^{B}\to \mathbb{R}^{A} and M *: A BM^{\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:A×BM\colon A\times B\to \mathbb{R}, we take the adjoint (such an over worked word!) to get a function B AB\to \mathbb{R}^{A} given by b(aM(a,b))b\mapsto (a\mapsto M(a,b)). We then use the fact that B\mathbb{R}^{B} is the free vector space on BB so there is a unique linear extension of that function to M *: B AM_{\ast }\colon \mathbb{R}^{B}\to \mathbb{R}^{A}. This is the linear map that you think it is: (M *q)(a) bBM(a,b)q(b). (M_{\ast }q)(a)\coloneqq \sum _{b\in B}M(a,b) q(b). As undergraduates we would write this as (Mq) a=M abq b(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 MM and take the adjoint function A BA\to \mathbb{R}^{B} given by a(bM(a,b))a\mapsto (b\mapsto M(a,b)). Then we extend this by linearity to get a linear function M *: A BM_{\ast }\colon \mathbb{R}^{A}\to \mathbb{R}^{B} which is given by (M *p)(b) aAM(a,b)p(a). (M_{\ast }p)(b)\coloneqq \sum _{a\in A}M(a,b) p(a). In undergraduate notation we might write (M Tp) b=M abp a(M^{T}p)_{b}=M_{a b}p_{a}.

Now these two functions we have constructed are adjoint in that M *p,q B=p,M *q A, \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 aA,bBM(a,b)p(a)q(b). \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 𝒱=Set\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 𝒱=[0,]\mathcal{V}=[0,\infty ] interesting, although a good, motivating example will also come from taking 𝒱={true,false}\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 A\mathbb{R}^{A}.

The category of presheaves 𝒜^\hat{\mathcal{A}} is the functor 𝒱\mathcal{V}-category 𝒱 𝒜 op\mathcal{V}^{\mathcal{A}^{\mathrm{op}}}, so an object of 𝒜^\hat{\mathcal{A}} is a functor 𝒜 op𝒱\mathcal{A}^{\mathrm{op}}\to \mathcal{V}. Associated to a pair of presheaves p,pA^p,p'\in \hat{A} is not a number, but rather the hom-𝒱\mathcal{V}-object: 𝒜^(p,p)= a𝒜[p(a),p(a)]. \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 A\mathbb{R}^{A}: we had p,p A aAp(a)p(a)\langle p, p'\rangle _{\mathbb{R}^{A}} \coloneqq \sum _{a\in A} p(a)p'(a).

Analogous to A\mathbb{R}^{A} being the free vector space on AA, we have that the category of presheaves 𝒜^\hat{\mathcal{A}} is the free cocomplete category on 𝒜\mathcal{A}, which means that if F:𝒜𝒞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 FF.

Similarly, the category of opcopresheaves 𝒜ˇ\check{\mathcal{A}} is the 𝒱\mathcal{V}-category (𝒱 𝒜) op(\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 :𝒜 op𝒱\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 *M_{\ast }, we take the adjoint of the profunctor :𝒜 op𝒱\mathcal{M}\colon \mathcal{A}^{\mathrm{op}}\otimes \mathcal{B}\to \mathcal{V} to get a functor 𝒱 𝒜 op=𝒜^\mathcal{B}\to \mathcal{V}^{\mathcal{A}^{\mathrm{op}}}=\hat{\mathcal{A}} given by b(a(a,b))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 ( *q)(a)= b[q(b),(a,b)]. (\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 *q)(a) bBM(a,b)q(b)(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 :𝒜 op𝒱\mathcal{M}\colon \mathcal{A}^{\mathrm{op}}\otimes \mathcal{B}\to \mathcal{V} to get a functor 𝒜 op𝒱 \mathcal{A}^{\mathrm{op}}\to \mathcal{V}^{\mathcal{B}} which is the same as a functor 𝒜(𝒱 ) op=ˇ\mathcal{A}\to (\mathcal{V}^{\mathcal{B}})^{\mathrm{op}}=\check{\mathcal{B}} given by a(b(a,b))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 ( *p)(b)= a[p(a),(a,b)]. (\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 *q)(a) bBM(a,b)q(b)(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: ˇ( *p,q)𝒜^(p, *q). \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 a,b[p(a)q(b),(a,b)]\int _{a,b}[p(a)\otimes q(b),\mathcal{M}(a,b)]. Again the comparison with the linear algebra case is telling: M *p,q B=p,M *q A= a,bM(a,b)p(a)q(b)\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:𝒞𝒟F\colon \mathcal{C}\to \mathcal{D} and G:𝒟𝒞G\colon \mathcal{D}\to \mathcal{C} form an adjunction FGF\dashv G. Then the following are equivalent categories (I’ll just state the objects, for simplicity). Fix(GF) {c𝒞 the unit cGF(c) is an iso} Fix(FG) {d𝒟the counitFG(d)dis an iso} Z(F,G) {(c𝒞,d𝒟,α:cG(d),β:F(c)d)|αandβare adjoint} \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()N(\mathcal{M}) of a profunctor :𝒜 op𝒱\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 Fix(M *M *)\text{Fix}(M^{\ast }M_{\ast }) – or Fix(M TM)\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, Hom:𝒜 op𝒜𝒱\text{Hom}\colon \mathcal{A}^{\mathrm{op}}\otimes \mathcal{A}\to \mathcal{V}, the nucleus N(Hom)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.

Posted at August 19, 2013 9:57 AM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2648

33 Comments & 1 Trackback

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

Interesting — I’m looking forward to hearing more.

In the linear algebra world, the analogue of the nucleus is Fix(M *M +)Fix(M^* M_+) (or Fix(M TM)Fix(M^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?

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 MM, let me write M *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 its eigenvalues and eigenvectors. This is done as follows.

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

So, we’ve succeeded in turning an arbitrary matrix MM into a self-adjoint matrix, M *M\sqrt{M^\ast M}, in a canonical way. It bears a close relationship to MM, at least if MM is a square matrix: for then M=NM *MM = N\sqrt{M^* M} for some isometry NN (i.e. orthogonal or unitary matrix NN).

(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 values of MM are the eigenvalues of M *M\sqrt{M^* M}. They are always nonnegative, since M *M\sqrt{M^\ast M} is positive semidefinite.

Now, what are the fixed points of M *MM^\ast M? I claim they are the same as the fixed points of M *M\sqrt{M^\ast M}. Indeed,

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

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

Hence the fixed points of M *MM^\ast M are the eigenvectors of M *M\sqrt{M^\ast M} with eigenvalue 1. I don’t know whether there’s a standard name for the eigenvectors of M *M\sqrt{M^\ast M}. Since the eigenvalues of M *M\sqrt{M^\ast M} are called the singular values of MM, I want to say that the eigenvectors of M *M\sqrt{M^\ast M} are called the singular vectors of MM. Anyway, in that language, the fixed points of M *MM^\ast M are the singular vectors of MM with singular value 11.

Posted by: Tom Leinster on August 19, 2013 11:20 AM | Permalink | Reply to this

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

Incidentally, Axler uses a really excellent analogy to explain this stuff about singular values and, more generally, the theory of operators on an inner product space. It’s very much in the spirit of categorification.

Let VV be a complex inner product space.

  • Operators on VV are like complex numbers.

  • Isometries on VV are like complex numbers of unit modulus. (E.g. the eigenvalues of an isometry VVV \to V are complex numbers of unit modulus.)

  • Self-adjoint operators on VV are like real numbers. (E.g. the eigenvalues of a self-adjoint operator are real numbers.)

  • Positive semidefinite on VV are like nonnegative real numbers. (E.g. the eigenvalues of a positive semidefinite operator are nonnegative. When I say “positive semidefinite”, I include “self-adjoint” in the definition.)

  • The positive semidefinite operator T *T\sqrt{T^* T} associated to an operator TT is like the modulus |z||z| of a complex number zz.

  • The polar decomposition theorem (that any operator is the composite of an isometry with a positive semidefinite operator) is like the theorem that any complex number is the product of a complex number of unit modulus with a positive real.

Can you make anything of that in the categorical world?

Posted by: Tom Leinster on August 19, 2013 11:33 AM | Permalink | Reply to this

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

I guess you forgot an important simile.

  • Taking the adjoint is like complex conjugation.

Anyway, let’s make a start at looking at categorified versions.

  • Operators on V are linear endofunctions on a vector space, so should be like continuous (or cocontinuous) functors on a complete (or cocomplete) category 𝒞\mathcal{C}.

  • An isometry is a linear map ψ:VV\psi\colon V\to V satisfying v,w=ψ(v),ψ(w)\langle v, w\rangle=\langle \psi(v), \psi(w)\rangle so should be like a continuous (or cocontinuous) endofunctor Ψ:𝒞𝒞\Psi\colon \mathcal{C}\to \mathcal{C} which is fully faithful, ie. satisfies 𝒞(c,d)=𝒞(Ψ(c),Ψ(d))\mathcal{C}( c, d)=\mathcal{C} (\Psi(c), \Psi(d)). [Edited to correct a silly mistake.]

  • Self-adjoint operators are those that satisfy ψ(v),w=v,ψ(w)\langle \psi(v), w\rangle=\langle v, \psi(w)\rangle so should be like, erm, self-adjoint functors.

  • Positive operators are those that satisfy ψ(v),v0\langle \psi(v), v\rangle \ge 0 and I don’t know what those should be like.

Hmm. I can’t seem to much further in this naive fashion.

Posted by: Simon Willerton on August 19, 2013 2:26 PM | Permalink | Reply to this

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

I guess you forgot an important simile.

  • Taking the adjoint is like complex conjugation.

Oops. Yes, that one’s crucial! It makes it clear that:

  • Isometries are like complex numbers of unit modulus, since the equation T *T=1T^* T = 1 is like the equation z¯z=1\overline{z} z = 1.

  • Self-adjoint operators are like real numbers, since the equation T *=TT^* = T is like the equation z¯=z\overline{z} = z.

Thanks.

A typo/braino in your own comment: in the second bullet point of the four-bullet list, when you say “An operator”, you mean “An isometry VVV \to V”.

I guess the main difficulty is to handle positivity. Here we could use the following fact: an operator is positive (i.e. positive semidefinite and self-adjoint) if and only if it is of the form S *SS^* S for some operator SS. This is analogous to the fact that a complex number is (real and) nonnegative if and only if it is of the form w¯w\overline{w} w for some complex number ww.

That strategy enables us to categorify without ever talking about inequalities between objects of the enriching category 𝒱\mathcal{V}. But I haven’t begun to think this through.

Posted by: Tom Leinster on August 19, 2013 3:06 PM | Permalink | Reply to this

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

I corrected the braino, thanks.

A functor is expressible as the composite of a left and right adjoint F *FF^\ast F or FF *F F^\ast if and only if it can be given the structure of a monad or a comonad. That seems to lead to the question: How do you take the square-root of a monad?

Posted by: Simon Willerton on August 20, 2013 10:48 AM | Permalink | Reply to this

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

Hmmm… the Kleisli and the Eilenberg-Moore categories give extremal adjoint factorizations of a monad, so you might want to think of them as upper and lower bounds for a square root, in some order… but in saying “square root” you probably want an endofunctor?

Maybe we could try the old babylonian trick, because it works nicely for matrices, too: start with 11 and the positive MM, and replace them with their harmonic and arithmetic means, respectively; and repeat until some limit arises. This raises the not-more-perspicuous, but less-irrational question: what are arithmetic and harmonic means of two monads?

Posted by: Jesse McKeown on August 20, 2013 11:29 PM | Permalink | Reply to this

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

Tom wrote:

I guess the main difficulty is to handle positivity.

Perhaps when we really understand this we’ll be able to meet Terry Tao’s challenge and categorify the Cauchy–Schwarz inequality.

Posted by: John Baez on August 21, 2013 9:04 AM | Permalink | Reply to this

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

Thinking about this stuff further made me realize I had some linear algebra to get out of my system, as you’ll probably have seen.

One thing that I hope that post makes clear is that “square root” is actually a slightly misleading phrase in this context. The important theorem here is that every positive operator TT has a unique positive square root T\sqrt{T}. Now, by definition, positive includes “self-adjoint”, so it doesn’t matter whether we interpret the square root condition as

T=TT T = \sqrt{T} \sqrt{T}

or

T=T *T. T = \sqrt{T}^\ast \sqrt{T}.

But morally, it’s the latter that’s important. Squares of operators aren’t even guaranteed to be positive.

Anyway, I’m quite confused about how the categorification goes. Given small VV-categories AA and BB, a module M:A opBVM: A^{op} \otimes B \to V can be regarded as any of the following:

  • a continuous functor AˇBˇ\check{A} \to \check{B}

  • a cocontinuous functor B^A^\hat{B} \to \hat{A}

  • a continuous functor BˇA^\check{B} \to \hat{A}

  • a cocontinuous functor A^Bˇ\hat{A} \to \check{B}

  • an adjunction A^Bˇ\hat{A} \stackrel{\longrightarrow}{\stackrel{\bot}{\leftarrow}} \check{B}.

Given MM, the adjunction in the last bullet point induces a monad on A^\hat{A}. But that monad is obtained by composing a cocontinuous functor with a continuous functor, so it’s not guaranteed to be anything in particular. Is that really what we’re supposed to be doing?

Also, I don’t know which monads on A^\hat{A} arise in this way. Not all of them, I would imagine. One way of describing this monad arising from MM — let’s call it T MT^M — is that it’s the codensity monad of the functor BA^B \to \hat{A} that “is” MM. Now, every monad on a category is a codensity monad of some functor into that category, so it looks at first as if every monad on A^\hat{A} arises in this way. But that’s forgetting the condition that BB had to be small. I don’t know what constraints this imposes on the induced monad.

On another point, I think if we were going to push the analogy between matrices and modules, we might want to start considering something like \dagger-categories. For abstract vector spaces AA and BB, the dual of a map M:ABM: A \to B is a map M *:B *A *M^\ast: B^\ast \to A^\ast, which is something of a different type. It’s only when you give AA and BB inner product structures (or work explicitly with matrices) that we get canonical isomorphisms A *AA^\ast \cong A and B *BB^\ast \cong B, enabling us to regard M *M^\ast as a map BAB \to A. So, it’s only with that extra structure that “M *MM^\ast M” makes sense.

Similarly, for VV-categories AA and BB, the “dual” of a module M:ABM: A ↛ B can only be interpreted as the corresponding module M *:B opA opM^\ast: B^{op} ↛ A^{op}. It’s only if we have equivalences A opAA^{op} \cong A and B opBB^{op} \cong B that we can regard M *M^\ast as a module BAB ↛ A. Again, it’s only with that extra structure that “M *MM^\ast M” makes sense.

Posted by: Tom Leinster on August 22, 2013 2:01 PM | Permalink | Reply to this

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

Interesting; I look forward to the rest of it.

we take the adjoint (such an over worked word!)

For that reason, I prefer to use the word adjunct for pairs of morphisms that correspond under an adjunction isomorphism.

Posted by: Mike Shulman on August 20, 2013 4:53 AM | Permalink | Reply to this

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

I was brought up on “transpose” and continue to use it. The nLab’s suggested alternatives, “conjugate” and “mate”, also seem good. “Adjunct” is a bit too similar-sounding to “adjoint” for my taste, although I suppose that could instead be counted as a point in its favour.

Posted by: Tom Leinster on August 20, 2013 10:52 AM | Permalink | Reply to this

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

Simon wrote:

Rather naughtily, I won’t motivate the construction in this post…

Reminds me of something funny I heard. Ordinary people try to motivate other people; mathematicians try to motivate mathematics.

Anyway, I’m motivated to read more!

Posted by: John Baez on August 21, 2013 8:00 AM | Permalink | Reply to this

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

Simon wrote:

As undergraduates we would write this as (Mq) a=M abq b(M q)_{a}=M_{a b}q_{b}, if we were using the Einstein summation convention.

Or something like this:

(Mq) a=M b aq b(M q)^{a}=M^a_b q^b

if you want to really follow Einstein and only sum over pairs of indices where one is upstairs (contravariant) and one is downstairs (covariant).

Back when I was stuck at particular rather low level of pseudo-sophistication, I looked down on the Einstein summation because it was basis-dependent. Later I learned about Penrose’s abstract index notation, which redeems the Einstein summation convention from this taint. Later still, I learned it’s just a low-budget way to typeset string diagrams: the superscripts are names for strings coming into a box from above, while the subscripts are names for strings coming out from below.

I’m sure you know this too, being currently at a roughly equal level of pseudo-sophistication as me. But I thought I’d mention it, because you didn’t quite bother to draw the cute conclusion: categorified versions of Penrose’s abstract index notation and the Einstein summation convention are pretty convenient for dealing with coends.

For example, instead of writing something big like this:

( *q)(a)= b[q(b),(a,b)] (\mathcal{M}_{\ast }q)(a) = \int _{b} [q(b),\mathcal{M}(a,b)]

you can just write

(M *q) a=M b aq b (M_\ast q)^a = M^a_b q^b

Superscripts indicate arguments of contravariant functors. Subscripts indicate covariant arguments. A coend is a thing where we ‘sum over’ an index that appears once as a superscript and once as a subscript.

At least for physicists and mathematicians who have suffered through physics, this notation would make things like profunctors and coends look a lot more familiar and less scary. As you note, it’s just categorified linear algebra.

Posted by: John Baez on August 21, 2013 8:47 AM | Permalink | Reply to this

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

John, thanks for highlighting a subtlety that I should have made explicit. Whilst one is perhaps used to using profunctors in coends, what I am using here in a[q(b),(a,b)] \int_a [q(b),\mathcal{M}(a,b)] is in fact an end. In the Sheffield Category Theory Seminar we have a mnemonic “the end of the walking stick is at the bottom” to remind us that b\int_b means ‘end’ and b\int^b means ‘coend’.

[I suspect that the Catsters should do some videos on ends and coends…]

I believe people round these parts are more familiar with the idea that a profunctor :A opB𝒱\mathcal{M}\colon A^{op}\otimes B\to \mathcal{V} gives rise to a cocontinuous functor ^:B^A^\hat{\mathcal{M}}\colon\hat{B}\to \hat{A} between presheaf categories – so an object of B^\hat{B} is a functor r:B op𝒱r\colon B^\op\to \mathcal{V} – and this is given by the coend formula
(^r)(a)= bM(a,b)r(b).(\hat{\mathcal{M}}r)(a)=\int^b M(a,b)\otimes r(b). So if we covariant things as subscripts and contravariant things as superscripts we would write this as (^r) a=M b ar b.(\hat{\mathcal{M}}r)^a= M^a_b r^b.

One gets the slogan that profunctors A opB𝒱A^{op}\otimes B\to \mathcal{V} are the same thing as cocontinuous functors B^A^\hat{B}\to \hat{A}.

In the same vein there is a continuous functor between opcopresheaf categories ˇ:AˇBˇ\check{\mathcal{M}}\colon \check{A}\to \check{B}, given by (ˇs)(b)= aM(a,b)r(a),(\check{\mathcal{M}}s)(b)=\int^a M(a,b)\otimes r(a), which we can write as (ˇs) b=M b as a.(\check{\mathcal{M}}s)_b= M^a_b s_a.

The slogan here is that profunctors A opB𝒱A^{op}\otimes B\to \mathcal{V} are the same thing as continuous functors AˇBˇ\check{A}\to \check{B}.

Now the constructions I was talking about switches variances, so we have *:BˇA^\mathcal{M}_\ast\colon \check{B}\to \hat{A}, given by an end formula ( *q)(a)= b[q(b),M(a,b)],(\mathcal{M}_\ast q)(a)=\int_b [q(b),M(a,b)], which would come out under Einstein summation convention as something like ( *q) a=[q b,M b a].(\mathcal{M}_\ast q)^a= [q_b, M^a_b]. I don’t know a good way to distinguish ends and coends here, nor a good way how to represent this in string diagrams.

The slogan in this case is that profunctors A opB𝒱A^{op}\otimes B\to \mathcal{V} are the same thing as adjunctions between Bˇ\check{B} and A^\hat{A}.

Posted by: Simon Willerton on August 21, 2013 2:09 PM | Permalink | Reply to this

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

Simon wrote:

In the Sheffield Category Theory Seminar we have a mnemonic “the end of the walking stick is at the bottom” to remind us that b\int_b means ‘end’ and b\int^b means ‘coend’.

Whoops, I never learned that convention! Not knowing which end is up, I screwed up.

If coends are like generalizations of sums, shouldn’t ends be more like generalizations of products? I don’t have any intuition for ends, so I could be completely wrong. But if I’m right, maybe they deserve a more multiplicative notation than \int? Don’t worry, I’m not trying to get people to change the usual notation… but I think there’s some notation for infinite products that completes the analogy:

::::? \sum : \prod :: \int : ?

I don’t know a good way to distinguish ends and coends here, nor a good way how to represent this in string diagrams.

Hmm.

Posted by: John Baez on August 21, 2013 5:46 PM | Permalink | Reply to this

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

sometimes expT(t)dt exp \int T(t) \d t ; some of our HoTT people sometimes write \forall for dependent products.

Posted by: Jesse McKeown on August 22, 2013 11:40 PM | Permalink | Reply to this

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

When I was an undergraduate learning about the Einstein summation convention, I would encounter expressions such as T lm ijkS ij nm, T^{ijk}_{lm} S^{nm}_{ij}, where, as John said, repeated indices were to be summed over. My applied maths supervisor, Peter Eggleton, had a well worn pun for identifying when such an expression didn’t fit the conventions.

If it has three “i”s it’s a monster.

Posted by: Simon Willerton on August 21, 2013 3:09 PM | Permalink | Reply to this

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

I’ve also wondered about how to represent ends with abtract indices. The closest I’ve come is thinking of them as some sort of “division”, but I never worked out whether that could make sense formally.

Posted by: Mike Shulman on August 21, 2013 7:45 PM | Permalink | Reply to this
Read the post Galois Correspondences and Enriched Adjunctions
Weblog: The n-Category Café
Excerpt: Translate from category theory to order theory
Tracked: February 5, 2014 11:12 PM

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

I’m going to start an nLab page on this. Where it says

Let’s fix a suitable category 𝒱\mathcal{V} to enrich over, this should be closed symmetric and sufficiently complete and cocomplete.

How should I understand that ‘sufficiently’?

Posted by: David Corfield on August 5, 2014 9:27 AM | Permalink | Reply to this

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

David, I guess I was hedging somewhat. You should understand that “sufficiently complete and cocomplete” to mean

“containing enough limits and colimits to make everything that follows work, this might or might not be strictly weaker than being complete and cocomplete, but I haven’t really thought about it because all of the examples I’m currently bothered about are both complete and cocomplete.”

Posted by: Simon Willerton on August 5, 2014 10:13 AM | Permalink | Reply to this

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

Thanks. By the way, did you settle on a new name for ‘nucleus’? I think somewhere you said you weren’t too happy with it.

At the moment nLab doesn’t seem to want to create pages, but someone’s on the case, and I should have something up today. Hopefully, we can put together a wide range of examples.

Posted by: David Corfield on August 5, 2014 12:02 PM | Permalink | Reply to this

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

I have a radical suggestion, which is that ‘the category of copresheaves on 𝒜\mathcal{A}’ should be our name for (𝒱 𝒜) op(\mathcal{V}^{\mathcal{A}})^\mathrm{op}, not 𝒱 𝒜\mathcal{V}^{\mathcal{A}}.

Then the co-Yoneda embedding embeds 𝒜\mathcal{A} into its category of copresheaves, just as the Yoneda embedding embeds 𝒜\mathcal{A} into its category of presheaves.

Also the category of copresheaves on 𝒜\mathcal{A} becomes the free completion of 𝒜\mathcal{A}, just as the category of presheaves is the free cocompletion of 𝒜\mathcal{A}.

Furthermore, with this terminology, Isbell duality gives an adjunction between presheaves and copresheaves.

(As soon as a category theorist learns something, they want to reform terminology to make what they learned easier to remember.)

Posted by: John Baez on May 30, 2020 1:27 AM | Permalink | Reply to this

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

Speaking of toposes and duals, did you see Joyal and Anel’s topo-logie?

Posted by: David Corfield on May 30, 2020 2:58 PM | Permalink | Reply to this

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

I have an even more radical suggestion, which is that the term “presheaf” has had its day and should be retired.

To call something a “presheaf” suggests that it could potentially be a sheaf. That’s fine when we’re in a context where “sheaf” makes sense; I don’t mind the term so much when the domain category is a poset of open subsets, or more generally a site. But for an arbitrary category AA — with no more data given — “sheaf on AA” is meaningless, whereas “presheaf on AA” is meaningful.

A second point: as I understand it, Lawvere and Schanuel’s bid to replace “semiring” by “rig” stemmed from the feeling that “semiring” suggests inadequacy. A semiring sounds like something that isn’t as good as a ring. (Like a seminorm isn’t as good as a norm.) Or at least, that ring is the main concept and semirings are secondary. But semirings are canonical, natural structures in their own right; they’re not just something obtained from a more important definition by axiom-slicing. One of the most basic mathematical structures of all, the natural numbers, is a semiring that isn’t a ring. Hence the suggestion to replace “semiring” by a term without negative connotations.

(From this perspective, one should really say “a ring is a rig with negatives” rather than “a rig is a ring without negatives”.)

Similarly, presheaves on a category shouldn’t be viewed as an inadequate or problematic relative of sheaves, even if “sheaf” does happen to have a well-defined meaning for the domain category concerned.

“Copresheaf” is even worse. The derivation of the word is super-convoluted:

  • a sheaf is a contravariant Set-valued functor with certain good properties;

  • a presheaf is like a contravariant Set-valued functor with certain good properties, but without necessarily having those good properties;

  • a copresheaf is the dual of something like a contravariant Set-valued functor with certain good properties, but without necessarily having those good properties.

It’s far too complex a word for a concept as simple as “covariant functor into Set”. In particular, “presheaf” includes the condition of contravariance, and “co” is added to get back to covariance, thus needlessly building a double dual into the word itself. When I first started seeing “copresheaf”, only quite recently I think, I found it hard to take seriously. Now it seems to be taking root.

The trouble is, I don’t have better suggestions. In Martin Hyland’s Part III course that I took long ago, he used “diagram” to mean “copresheaf”. That’s certainly a nicer word, but I’ve never seen anyone else use it in this way. Moreover, I have no good ideas to replace “presheaf”; and given how entrenched that already is, it would have to be a really good idea in order to take its place.

Any suggestions?

Posted by: Tom Leinster on May 30, 2020 5:38 PM | Permalink | Reply to this

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

I don’t have better suggestions

Well, maybe I do. I’d rather just say “covariant functor” and “contravariant functor”.

It’s true that by not saying what the codomain is, I’m being slightly vague. But (1) the context usualy makes it clear, just as in most parts of maths one can say “function on XX” and the intended codomain is clear (usually \mathbb{R} or \mathbb{C}); (2) the term “presheaf” doesn’t specify the codomain either, in that for many (most?) mathematicians, presheaves are presheaves of rings, modules, etc., rather than presheaves of sets.

Anything to avoid “copresheaf”…

Posted by: Tom Leinster on May 30, 2020 6:04 PM | Permalink | Reply to this

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

You just snuck in before I posted my reply below. I did nearly make the comment that the term ‘function’ is often used unambiguously for a function to the ‘obvious’ codomain.

Posted by: Simon Willerton on May 30, 2020 6:17 PM | Permalink | Reply to this

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

I actually like the word “module”. (I know some people don’t, but I’m not backing down just yet.) The only issue is whether a contravariant module is called ‘left’ or ‘right’. I think I usually say ‘right’, but it may depend on the day of the week. So a covariant functor to SetSet would be a ‘left module’.

Yeah, I really can’t stand ‘copresheaf’. So ugly.

Posted by: Todd Trimble on May 30, 2020 9:28 PM | Permalink | Reply to this

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

“(Bi)module” is definitely my preferred word for a functor A op×BSetA^{op} \times B \to Set. However, for some reason I tend not to use it outside the two-sided situation. I can’t really justify that.

It’s always seemed clear to me that a left module is a covariant functor into SetSet and a right module is a contravariant functor. What reason would there be to say the opposite?

(I guess I should justify the convention I state. Let X:ASetX: A \to Set, let aAa \in A, and let xX(a)x \in X(a). Consider maps f:ab,g:bc. f: a \to b, \,\, g: b \to c. If we write (Xf)(x)(X f)(x) as fxf x, etc., then (gf)x=g(fx). (g \circ f)x = g(f x). That’s nice: the order of the variables doesn’t change, and we can unambiguously write both sides as gfxg f x. This notation corresponds to calling our covariant functor XX a left AA-module. So we should do that. But were we to write (Xf)(x)(X f)(x) as xfx f, we’d get x(gf)=(xf)g, x (g \circ f) = (x f)g, which is nasty. That nasty notation would correspond to calling our covariant functor a right module. So we shouldn’t do that.)

Posted by: Tom Leinster on May 30, 2020 10:29 PM | Permalink | Reply to this

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

I think of presheaves and copresheaves as categorifications of scalar-valued functions, in some loose sense which I can’t make precise at this point.

For a set or a space you consider the set of functions to the real-numbers (or integers), say, and for a category you consider the functors to sets. That’s my intuition anyway. It took me many years to go from the name ‘presheaf’ to this intuition! Coming in to category theory, I did find the name ‘presheaf’ somewhat intimidating.

I could concretely suggest the names ‘scalar functor’ and ‘coscalar functor’; however, I’m not sure I’m convinced by them. (And which is which?)

Posted by: Simon Willerton on May 30, 2020 6:09 PM | Permalink | Reply to this

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

For a set or a space you consider the set of functions to the real-numbers (or integers), say, and for a category you consider the functors to sets. That’s my intuition anyway.

Yes, mine too. That’s the same intuition I was appealing to in reason (1) here.

It took me many years to go from the name ‘presheaf’ to this intuition! Coming in to category theory, I did find the name ‘presheaf’ somewhat intimidating.

It’s as if we’d first coined a nice short one-word term for “continuous function”, then prefixed a “pre” to mean a thing that’s like a continuous function except that it isn’t necessarily continuous. In other words, a function.

I could concretely suggest the names ‘scalar functor’ and ‘coscalar functor’; however, I’m not sure I’m convinced by them. (And which is which?)

Thanks. That’s not too far off the standard “set-valued functor” and “contravariant set-valued functor”.

Posted by: Tom Leinster on May 30, 2020 6:19 PM | Permalink | Reply to this

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

I think of presheaves and copresheaves as categorifications of scalar-valued functions, in some loose sense which I can’t make precise at this point.

For a set or a space you consider the set of functions to the real-numbers (or integers), say, and for a category you consider the functors to sets. That’s my intuition anyway.

Interesting! My intuition comes from the fact that presheaf categories are free co-completions. I.e. I more or less always think of a presheaf on CC as a ‘colimit’ of some diagram in CC.

Posted by: Richard Williamson on May 30, 2020 11:45 PM | Permalink | Reply to this

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

Interesting! My intuition comes from the fact that presheaf categories are free co-completions. I.e. I more or less always think of a presheaf on CC as a ‘colimit’ of some diagram in CC.

Indeed. One thing that I’ve learnt from the likes of Tom and John is that colimits are like sums. So the analogue of what you are saying would be the thing you get by freely adding formal sums.

Consider a finite set XX. It sits inside its set of (scalar-valued) functions as the set of delta functions. Then the set of functions on XX is

  • the free abelian monoid on the set if the scalars are the natural numbers \mathbb{N},
  • the free abelian group (or \mathbb{Z}-module) on the set if the scalars are the integers \mathbb{Z},
  • and the free kk-vector space on the set if the scalars are a field kk.

(I added the word ‘finite’ before the word ‘set’ above because I’m too lazy on a Sunday morning to think how I should phrase it for the infinite case.)

So the set of functions can be viewed as what you get when you freely add all formal sums of some kind. You can think of a function on a set XX as a formal sum of elements of XX.

A natural question to pose here is “You mentioned vector spaces, there you don’t just have sums, you also have scalar multiplication. How does that work for categories?” Well the analogue of scalar multiplication in the language of colimits is copowering.

Posted by: Simon Willerton on May 31, 2020 9:18 AM | Permalink | Reply to this

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

Nice!

Posted by: Richard Williamson on June 3, 2020 11:30 PM | Permalink | Reply to this

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

Incidentally, I agree with the spirit of John’s suggestion that (V A) op(V^A)^{op} deserves a simple name. Putting aside the question of words for the moment, I like to use the notation

Aˇ=(V A) op. \check{A} = (V^A)^{op}.

It’s a companion to the standard notation

A^=V A op. \hat{A} = V^{A^{op}}.

So Isbell conjugacy defines an adjunction between Aˇ\check{A} and A^\hat{A}.

This notational system is also intended to evoke the notation used for Pontryagin duality and the Fourier transform (although I wouldn’t want to claim a super-exact analogy).

Posted by: Tom Leinster on May 31, 2020 10:27 PM | Permalink | Reply to this

Post a New Comment