# defining a bicategory of real-valued matrices

Let $\mathbf{Rel}$ be the bicategory of sets, relations, and inclusions between relations. The following fact is well-known:

• Any ordinary function $f : X \to Y$ between sets induces a pair of relations $B(1,f) : X \to Y$ and $B(f,1) : Y \to X$ in $\mathbf{Rel}$, defined explicitly by \begin{align*} B(1,f) &= (x,y) \mapsto y = f(x)\\ B(f,1) &= (y,x) \mapsto f(x) = y \end{align*} forming an adjunction $B(1,f) \dashv B(f,1)$. In particular, the unit and the counit of this adjunction correspond to the following logical implications: $$\eta : x' = x \longrightarrow \exists y. y = f(x) \wedge f(x') = y$$ $$\epsilon : \exists x. f(x) = y \wedge y' = f(x) \longrightarrow y' = y$$

One way of generalizing this example is by replacing sets with categories and relations by profunctors, considering the bicategory $\mathbf{Prof}$ as a proarrow equipment over $\mathbf{Cat}$.

I'm interested in a different sort of potential generalization. At least in the case of finite sets, a relation $X \to Y$ can be seen as an $X\times Y$ matrix with boolean-valued entries. Suppose we generalize to finite matrices valued in an arbitrary field $k$. Such matrices clearly form a 1-category (call it $\mathbf{FinMat}_k$), with composition defined by matrix multiplication. Moreover, every finite function $f : X \to Y$ induces a pair of matrices $B(1,f) : X \to Y$ and $B(f,1) : Y \to X$, corresponding to the indicator function \begin{align*} B(1,f) &= (x,y) \mapsto [y = f(x)]\\ B(f,1) &= (y,x) \mapsto [f(x) = y] \end{align*} where $[a = b]$ is 1 if $a = b$ and 0 otherwise.

Question: Is there a natural bicategorical structure on $\mathbf{FinMat}_k$ (at least for certain values of $k$), such that for every finite function $f : X \to Y$, we have an adjunction $B(1,f) \dashv B(f,1)$ in $\mathbf{FinMat}_k$? (Perhaps it is necessary to adjust the definition of $B(1,f)$ or $B(f,1)$?)

As a non-example which was my first attempt, in the case of $k = \mathbb{R}$, we could define 2-cells between real-valued matrices $\alpha : f \Rightarrow g : X \to Y$ as a family of inequalities $$\alpha_{x,y} : f(x,y) \le g(x,y)$$ However, this would not verify the adjunction. In particular, although we do have an $\eta$ inequality \begin{align*} [x' = x] &\le [f(x') = f(x)] \\ &= \sum_y [y = f(x)] \cdot [f(x') = y] \end{align*} for every $x$ and $x'$, the $\epsilon$ inequality $$\sum_x [f(x) = y] \cdot [y' = f(x)] \le [y' = y]$$ does not necessarily hold (in general, only if $f$ is injective).

• you can consider vector spaces with a fixed finite base, the tensor product as arrows and linear morphisms as cells, this is a classical module's bicategory type. – Buschi Sergio Mar 31 '14 at 10:40
• $\mathbf{FinMat}$ is a monoidal category, and so can be re-interpreted as a 2-category in the way you describe, but that just shifts my question one dimension up. Under that interpretation, each finite function $f : X \to Y$ determines a pair of linear transformations $k^{|X|} \to k^{|Y|}$ and $k^{|Y|} \to k^{|X|}$, and the question is whether/in what sense these can be seen as "adjoint"? – Noam Zeilberger Mar 31 '14 at 11:13
• The $\mathbf{Poset}$-enrichment of $\mathbf{Rel}$ is coming from the fact that $\{ 0, 1 \}$ is itself partially ordered. Perhaps you might have better luck with a (tropical) semiring instead of a field? – Zhen Lin Mar 31 '14 at 13:10
• One thing you can do is generalize relations by giving a function on the middle set (the one that maps to the ends) and then this corresponds to a morphim from functions on one set to functions on the other, so basically to this matrix. This can be generalized by replacing function with distribution, vector bundle, sheaf etc. – Adam Gal Oct 13 '14 at 19:55

It's not strictly speaking true that working with a field $k$ generalizes the case of relations: composition of relations doesn't agree with composition of $\mathbb{F}_2$-valued matrices. Relations are instead matrices valued in the Boolean semiring $B = \{ 0, 1 \}$, where addition is logical OR instead of logical XOR. The Boolean semiring is fundamentally a poset, with addition coming from taking categorical coproducts and multiplication coming from taking categorical products, so it's natural to try to replace $B$ with a distributive lattice $L$ rather than a field.
I claim that this works; the crucial fact is that addition is idempotent so there's no issue with the failure of $f$ to be injective.
More generally, for a suitably nice monoidal category $V$ we can construct a bicategory out of $V$-enriched profunctors / bimodules. Composition of profunctors is defined in terms of enriched coends. In particular we can take $V$ to be a suitably nice monoidal poset, which should give generalizations of the above construction as well as Zhen Lin's suggestion of using a tropical semiring in the comments.
• For "suitably nice" it probably suffices to take $V$ to be cocomplete and closed. In the poset case this corresponds to taking $V$ to be a quantale (ncatlab.org/nlab/show/quantale). – Qiaochu Yuan Apr 1 '14 at 4:53
• Thank you, this is helpful. I am still interested in the original example (in particular, real-valued matrices with ordinary matrix multiplication) and whether it can be given something like the structure of a proarrow equipment, but it's helpful to have spelled out how this example differs from $\mathbf{Rel}$. – Noam Zeilberger Apr 1 '14 at 6:25