Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: theory: applied category theory

Topic: "Linearization"

John Baez (May 28 2020 at 05:34):

Matrices, Markov kernels and profunctors are all examples of "linearization". We have some sort of rig or 2-rig like real numbers, nonnegative real numbers or sets, and we define a morphism from $X$ to $Y$ to be a map from $X \times Y$, or $X^{\mathrm{op}} \times Y$ in the categorified case, to this rig or 2-rig.

John Baez (May 28 2020 at 05:35):

We can do most of the same tricks in each case.

John Baez (May 28 2020 at 05:36):

Relations are another example since a relation from a set $X$ to a set $Y$ the same as a function from $X \times Y$ to the boolean rig, $\{0,1\}$.

John Baez (May 28 2020 at 05:37):

Spans are another example since a span from a set $X$ to a set $Y$ is the same as function from $X \times Y$ to $\mathsf{Set}$.

John Baez (May 28 2020 at 05:41):

So, whenever you learn a trick that works for one of these things - matrices, Markov kernels, relations, spans, profunctors - you should immediately try to use this trick for all the rest. I often forget to do this, but when I remember it usually works.

James Fairbanks (May 28 2020 at 14:20):

Can I ask, why is this called linearization? I don't see a connection to total orders or linear maps.

Reid Barton (May 28 2020 at 14:24):

As in linear algebra and matrices, whether over a field, or just a rig like the nonnegative integers, or its categorification (FinSet or Set), or some more distant cousin. The unifying theme is that there is some kind of addition: $+$ or $\amalg$ or $\vee$

Reid Barton (May 28 2020 at 14:26):

Linearization is replacing a set $X$ by the free vector space on $X$, or by the free commutative monoid on $X$, or by the category of sets over $X$, ..., where you have this new "addition" operation.

James Fairbanks (May 28 2020 at 15:18):

Oh ok, in my understanding of a finite dimensional vector space, you have vectors which can be viewed as maps $v:n\to K$ where $K$ is a field and here we are relaxing the requirement that the dimensionality be a natural number and relaxing that $K$ be a field. Then you can construct matrices out of vectors to get $A: n\times m \to K$. That makes sense. You end up with functions $f:X\times Y \to K$ where $X,Y$ are objects and $K$ is a rig. These things should behave like matrices in a lot of ways. That explains why matrix multiplication is equivalent to relational algebra joins. And the axioms of the rig get transferred to these matrix like constructions so that the sum of matrices is the elementwise sum in the rig.

Daniel Geisler (May 28 2020 at 16:17):

@John Baez said:

So, whenever you learn a trick that works for one of these things - matrices, Markov kernels, relations, spans, profunctors - you should immediately try to use this trick for all the rest.

I'd love to hear more about this. Also I think of matrices and dynamical systems interchangeably. Am I getting something wrong? Thanks.

John Baez (May 28 2020 at 18:42):

James Fairbanks said:

Can I ask, why is this called linearization? I don't see a connection to total orders or linear maps.

It sounds like you got it by now, but:

In the cases I'm talking about, we have a rig or 2-rig $V$, and for any set or category $X$ we can form the free $V$-module on $X$ by taking $V^{X^{\mathrm{op}}}$. There's always a Yoneda-like embedding

$X \mapsto {X^{\mathrm{op}}}$

We can then describe any map of free $V$-modules

$F: V^{X^{\mathrm{op}}} \to V^{Y^{\mathrm{op}}}$

using a "matrix"

$T: Y \times X^{\mathrm{op}} \to V$

Furthermore we can compose these maps by matrix multiplication.

A popular example is $X = m$, $Y = n$, $V = \mathbb{R}$. Then

$V^{X^{\mathrm{op}}} = \mathbb{R}^m$

$V^{X^{\mathrm{op}}} = \mathbb{R}^n$

and I'm saying we can describe a linear map from $\mathbb{R}^m$ to $\mathbb{R}^n$ using an $n \times m$ matrix of real numbers,

$T: n \times m \to \mathbb{R}$

In this situation the Yoneda-like embedding

$n \to \mathbb{R}^n$

is just the inclusion of the n-element set into the vector space $\mathbb{R}^n$ as the standard basis!

The same story works for Markov kernels, relations, spans of sets, and profunctors. In every case are taking the category of sets (or 2-category of categories) and embedding it in a "linear" category (or 2-category) - that is, one where we can add maps, and we can compose maps by matrix multiplication. This lets us apply the ideas of linear algebra.

John Baez (May 28 2020 at 18:48):

I only got the point of presheaf categories and profunctors when I realized that they were a way to take category theory and linearize it.

Jade Master (May 28 2020 at 22:36):

Thanks John, this is really beautiful. Is the free $V$-module on a set $X$ really $V^{X}$ when $X$ is infinite? I'm not sure if you need to take only the functions with finite support.

John Baez (May 28 2020 at 22:51):

You're right, Jade: the free $V$-module on a set $X$ is only $V^X$ when $X$ is finite.

Category theory works a bit better: for example the free cocompletion of a category $X$ is $\mathsf{Set}^{X^{\mathrm{op}}}$ whenever $X$ is small.

When a set $X$ is not finite, to get the free $V$-module on it we need to take a subset of $V^X$ consisting of finite linear combinations of elements of $X$.

When a category $X$ is not small, to get its free cocompletion we need to take a subcategory of $\mathsf{Set}^{X^{\mathrm{op}}}$ consisting of small colimits of representables.

So "small" is the big boys' version of "finite".

John Baez (May 28 2020 at 22:52):

By the way what I just said about $\mathsf{Set}^{X^{\mathrm{op}}}$ should work for $V^{X^{\mathrm{op}}}$ more generally, but I'm too lazy to remember/write down the fine print. Steve Lack has a paper about cocompletions of large enriched categories.

John Baez (May 28 2020 at 22:53):

Also it's good to imagine that the "op" is hiding in $V^X$ even when $X$ is a set: it's just invisible then. This makes the analogy more perfect.

Jade Master (May 28 2020 at 23:18):

Of course a set is just a category with only identity arrows :smirk:

Gershom (May 29 2020 at 07:04):

Here is a dumb "pattern-matching" inspired question. There is a slogan that "homology is the linearization of homotopy". is there any way at all that fits with this picture, or are the two just different uses of the term "linearization"?

John Baez (May 29 2020 at 19:42):

It's pretty darn similar. When we take homotopy theory and "linearize" it to get homology theory, what we're doing is taking an infinity-groupoid and turning it into a strict stable infinity-groupoid, which is the same as chain complex of abelian groups.

Another way to think of the exact same thing that we're taking a simplicial set and freely turning it into a simplicial abelian group. (Simplicial sets are a model for infinity-groupoids, and the Dold-Kan theorem says simplicial abelian groups are the same as chain complexes of abelian groups.)

The second perspective is probably more helpful now. Taking a simplicial set and freely turning it into a simplical abelian group has, as a special case, forming the free abelian group on a set $S$. This is just $\mathbb{Z}^S$ when $S$ is finite. And this process $S \mapsto \mathbb{Z}^S$ is precisely an example of the "linearization" idea I was just talking about!

Alex Kreitzberg (Jun 27 2020 at 02:37):

Baez goes into a lot more detail about this stuff in his online course in chapter 4:

https://www.azimuthproject.org/azimuth/show/Applied+Category+Theory+Course#Chapter_4

My respect for matrices (as opposed to coordinate free presentations) deepened after the discussion.