by Jade Master
In a previous blog post I showed that there is an embedding
$ \mathsf{Mat_R} \hookrightarrow \mathsf{RProf}$
from the category of matrices valued in a commutative quantale R and the category of R-enriched profunctors. This suggests that profunctors generalize matrices and indeed they do. We may then ask what techniques of linear algebra generalize to arbitrary profunctors? In this post we generalize the definition of eigenvalue and eigenvector to arbitrary profunctors. We will use ordinary $ \mathsf{Set}$-profunctors, i.e. functors
$ P:C \times D^{op} \to \mathsf{Set}.$
It will be hard to transfer intuition from linear algebra when C and D are too infinite so we consider only the case when C and D have a finite set of objects. These profunctors live in the following category.
Definition: Let $ \mathsf{FinProf}$ be the category where
$ P ; Q (c,e) = \int^{d \in D} P(c,d) \times Q(d,e)$
where ; denotes the forward order composition (as opposed to $ \circ$ which is used for reverse order composition).
I get my intuition about this coend formula from the case of R-enriched profunctors (which gives ordinary matrix multiplication). In either case, the composition sums the values over all intermediate indices. Every morphism $ f: d \to d'$ induces functions $ P(c,f) \times Q(d,e)$ and $ P(c,d') \times Q(f,e)$. The coend above is quotiented so that these functions agree.
We can always decategorify a profunctor $ P : C \times D^{op} \to \mathsf{Set}$ to a $ \mathbb{N}$ valued matrix
$ |P| : Ob C \times Ob D \to \mathbb{N}$
given by
$ |P|(c,d)= | P(c,d)|$
where the second absolute value indicates the magnitude of a set. Whatever categorification of eigenvalue and eigenvector that we choose, it better correspond to the usual thing when decategorified.
For an ordinary matrix $ M: X \to Y$, a number $ \lambda$ is an eigenvalue with eigenvector $ v$ if
$ M v = \lambda v$.
To generalize this to arbitrary profunctors first we need to generalize vectors, scalar multiplication, and equality.
categorifying vectors and their multiplication
An n-dimensional vector is a matrix $ v : n \to 1$ where $ n$ is your favorite n element set and $ 1$ is your favorite 1 element set. Similarly, a categorified vector will be a profunctor
$ \mathbf{v} : \mathbf{n} \to \mathbf{1}$
where $ \mathbf{n}$ is a category with n objects and $ \mathbf{1}$ is a category one object. I am leaving the definitions of $ \mathbf{n}$ and $ \mathbf{1}$ vague on purpose. They are allowed to have any set of morphisms you like; as long as $ \mathbf{n}$ has n objects and $ \mathbf{1}$ has one object, $ \mathbf{v}$ will decategorify to a nx1 vector. To multiply a categorified matrix with a categorified vector we use profunctor composition. For a category $ \mathbf{m}$ with m objects, a profunctor $ M : \mathbf{m} \to \mathbf{n}$ composes with $ \mathbf{v}$ to obtain a categorifed vector
$ M ; v : \mathbf{m} \to \mathbf{1}$
given by
$ (M ; v) (x,*) = \int^{y \in \mathbf{n}} M(x,y) \times v(y,*)$
where * is the unique object of $ \mathbf{1}$. This decategorifies to the right thing because
$ |(M ; v)(x,*) | = | \int^{y \in \mathbf{n}} M(x,y) \times v(y,*) |$
$ = \sum_{y \in Ob \mathbf{n}} | M(x,y) \times v(y,*)|$
$ =\sum_{y \in Ob \mathbf{n}} | M(x,y) |\times | v(y,*)|.$
In other words it is the matrix multiplication $ | M | | v|$ of their decategorifications.
categorifying scalar multiplication
A scalar is a 1x1 matrix so we define a categorified scalar to be a profunctor
$ \alpha : \mathbf{1} \times \mathbf{1}^{op} \to \mathsf{Set}.$
where $ \mathbf{1}$ is any category with one object. The product of $ \alpha$ with a profunctor $ M : \mathbf{m} \times \mathbf{n}^{op} \to \mathsf{Set}$ is the profunctor
$ \alpha M : \mathbf{m} \times \mathbf{n}^{op} \to \mathsf{Set}$
given by
$ \alpha M (x,y) = \alpha(*,*) \times M(x,y).$
This decategorifies to $ |\alpha | \cdot |M(x,y)|$ because
$ | \alpha(*,*) \times M(x,y) | = |\alpha(*,*)| \cdot |M(x,y)|$.
categorifying equality of matrices
A general maxim of categorification is that when you categorify equalities must be replaced with isomorphisms. We need to do this for the eigenvalue equation but what category should the isomorphisms live in? We will use the following.
Definition: Let $ \mathsf{Prof}(C,D)$ be the category where
$ \beta_{c,d} : P(c,d) \to Q(c,d).$
An isomorphism in this category is a natural isomorphism of the above type.
categorifying the eigenvalue equation
We are now ready to state the definition of categorified eigenvalues and categorified eigenvectors.
Definition: A profunctor $ \lambda : \mathbf{1} \times \mathbf{1}^{op} \to \mathsf{Set}$ is a categorified eigenvalue of a profunctor $ M : \mathbf{n} \times \mathbf{n}^{op} \to \mathsf{Set} $ with categorified eigenvector $ \mathbf{v}: \mathbf{n} \times \mathbf{1}^{op} \to \mathsf{Set}$ if they are equipped with an isomorphism
$ \beta : M ; \mathbf{v} \xrightarrow{\sim} \alpha ; v$
in the category $ \mathsf{Prof}(\mathbf{n}, \mathbf{1})$ of profunctors between $ \mathbf{n}$ and $ \mathbf{1}$.
So that's neat. There are tons of useful things you can do with eigenvalues. You could spend many hours getting lost in the rabbit holes on their wikipedia page. Can we categorify these facts to obtain interesting things about profunctors? Probably, but I will leave this for the next installment.