Monads and Multilinear Extensions

We have seen some general conditions under which we can lift the powerset monad to categories of algebras, or equivalently distribute other monads over it. In this post we look at the concrete construction we have been using for the powerset, and generalise the key ideas to a broader class of monads.

The Powerset Case

For a binary operation

\bullet : X \times X \rightarrow X

the extension to powersets

\hat{\bullet} : \mathcal{P}(X) \times \mathcal{P}(X) \rightarrow \mathcal{P}(X)

has some interesting properties.

Firstly, it commutes with units, in the following sense:

\{ u \} \hat{\bullet} \{ v \} = \{ u \bullet v \}

We can interpret this as saying $\hat{\bullet}$ extends the behaviour of $\bullet$ from individual elements to arbitrary sets.

Secondly, it commutes with unions in the following sense:

\bigcup \{ U \hat{\bullet} V \mid U \in \mathbf{U}, V \in \mathbf{V} \} = \bigcup \mathbf{U} \hat{\bullet} \bigcup \mathbf{V}

We can interpret this as requiring $\hat{\bullet}$ be a homomorphism with respect to unions in both its arguments. We say $\hat{\bullet}$ is bilinear in this case, borrowing terminology from linear algebra for argument-wise preservation of vector space structure.

The construction we are using yields a bilinear extension of any binary operation. Such extensions are unique, as we shall soon see as a corollary of a more general result. You may wish to consider how to prove this directly.

The General Case

The properties of the concrete construction we have been using that were identified above are crucial to its good behaviour. We now generalise those properties to more general monads.

Abstract Definitions

We can generalise the notion of extension to any monad $\mathbb{T} : \mathcal{C} \rightarrow \mathcal{C}$ on a monoidal category

(\mathcal{C}, \otimes, I)

For morphism

f : A \otimes B \rightarrow C

we say that morphism

f’ : \mathbb{T}(A) \otimes \mathbb{T}(B) \rightarrow \mathbb{T}(C)

is an extension of $f$ if

f’ \cdot \eta \otimes \eta = \eta \cdot f

To generalise bilinearity, we need to assume $\mathbb{T}$ is a commutative monad. For Eilenberg-Moore algebras

(A,\alpha), (B, \beta), (C,\gamma)

we say

g : A \otimes B \rightarrow C

is bilinear if

h \cdot \alpha \otimes \beta = \gamma \cdot \mathbb{T}(h) \cdot \mathsf{dst}

where $\mathsf{dst}$ is the double strength natural transformation given by our assumption that $\mathbb{T}$ is commutative.

Finally, we say that a morphism

h : \mathbb{T}(X) \otimes \mathbb{T}(Y) \rightarrow \mathbb{T}(Z)

is a bilinear extension of $f$ if it is an extension that is bilinear with respect to the free algebras

(\mathbb{T}(X), \mu_X), (\mathbb{T}(Y), \mu_Y), (\mathbb{T}(Z), \mu_Z)

Existence of Bilinear Extensions

With the terminology of the previous section, we can construct a bilinear extension of $f$ as

\mathbb{T}(f) \cdot \mathsf{dst} : \mathbb{T}(X) \otimes \mathbb{T}(Y) \rightarrow \mathbb{T}(Z)

To confirm this is an extension:

\mathbb{T}(f) \cdot \mathsf{dst} \cdot \eta \otimes \eta = \mathbb{T}(f) \cdot \eta = \eta \cdot f

For bilinearity

\mathbb{T}(f) \cdot \mathsf{dst} \cdot \mu \otimes \mu = \mathbb{T}(f) \cdot \mu \cdot \mathbb{T}(\mathsf{dst}) \cdot \mathsf{dst} = \mu \cdot \mathbb{T}(f) \cdot \mathbb{T}(\mathsf{dst}) \cdot \mathsf{dst}

Uniqueness of Bilinear Extensions

Assume $h$ and $k$ are bilinear, and they satisfy

h \cdot \eta \otimes \eta = k \cdot \eta \otimes \eta

This implies

\mu \cdot \mathbb{T}(h) \cdot \mathbb{T}(\eta \otimes \eta) \cdot \mathsf{dst} = \mu \cdot \mathbb{T}(k) \cdot \mathbb{T}(\eta \otimes \eta) \cdot \mathsf{dst}

Applying naturality, this is equivalent to

\mu \cdot \mathbb{T}(h) \cdot \mathsf{dst} \cdot \mathbb{T}(\eta) \otimes \mathbb{T}(\eta) = \mu \cdot \mathbb{T}(k) \cdot \mathbb{T}(\eta) \otimes \mathbb{T}(\eta)

Using the bilinearity property

h \cdot \mu \otimes \mu \cdot \mathbb{T}(\eta) \otimes \mathbb{T}(\eta) = k \cdot \mu \otimes \mu \cdot \mathbb{T}(\eta) \otimes \mathbb{T}(\eta)

Finally, using bifunctoriality and the right unit monad axiom:

h = k

As a pair of bilinear extensions of the same morphism satisfy our initial assumption, bilinear extensions are unique.

Summary

In this post we have abstracted some properties of the powerset monad to any commutative monad. Although these definitions isolate some interesting algebraic structure, they are perhaps slightly ill-motivated at this stage.

As is common in category theory, we have established an existence property that allows us to construct a gadget with desirable properties, and a uniqueness property that gives us a proof principle with which to reason about such gadgets. This perspective will be important when we look at the preservation of linear equations.

To keep things simple, we have concentrated on bilinearity. It is fairly straightforward to generalise further to multilinearity, which we leave to the enthusiastic reader.

More background on the machinery in this section can be found in:

Kock “Bilinearity and Cartesian Closed Monads”
Manes “A Class of Fuzzy Theories”
Jacobs “Semantics of weakening and contraction”

Monads and Multilinear Extensions

The Powerset Case