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:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2648

20 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

Post a New Comment