The Analogical Engine » Cale - A math and haskell blog

Cale

Inversions in permutations and words

Posted in Cale on January 9th, 2010 by Cale – Be the first to comment

An inversion in a permutation $\textstyle \sigma \in \mathfrak{S}_n$ is a pair $\textstyle (i,j)$ of indices such that
$\textstyle i < j$ but $\textstyle \sigma(i) > \sigma(j)$ . Let $\textstyle \mathrm{inv}(\sigma)$ denote the total number of inversions of $\textstyle \sigma$ . One can uniquely record a permutation $\textstyle \sigma \in \mathfrak{S}_n$ by recording, for each $\textstyle 1 \leq i \leq n$ the number of inversions $\textstyle (i,j)$ , which will be a number from $\textstyle 0$ to $\textstyle n-i$ . One can recover the $\textstyle i^\mathrm{th}$ entry of the permutation (and hence the whole permutation) from such a recording by the following algorithm. Let $\textstyle S$ be the set of the first $\textstyle i-1$ entries of the permutation. If the number of inversions of the form $\textstyle (i,j)$ is $\textstyle k$ , then there must be exactly $\textstyle k$ elements after the $\textstyle i^\mathrm{th}$ position which are smaller than it. Hence, the $\textstyle i^\mathrm{th}$ entry of the permutation is the $\textstyle (k+1)^\mathrm{th}$ smallest element of $\textstyle \{1,\dots,n\}\setminus S$ .

Hence,

$(\mathfrak{S}_n,\mathrm{inv}) \,\,\tilde\to\,\, \left(\prod_{i=1}^{n} \{0,\dots,n-i\},\omega\right)$
is a weight preserving bijection, where $\textstyle \omega$ is the usual additive weight.

By simply reversing the sequences (using the index substitution $\textstyle j=n-i$ ), we get a further bijection:

$(\mathfrak{S}_n,\mathrm{inv}) \,\,\tilde\to\,\, \left(\prod_{j=0}^{n-1} \{0,\dots,j\},\omega\right)$

So these two sets will have the same generating series. Using the product and sum lemma, we obtain:

$\begin{align*} \sum_{\sigma\in\mathfrak{S}_n} q^{\mathrm{inv}(\sigma)} &= \prod_{i=0}^{n-1} \sum_{k=0}^{i} q^{k} = \prod_{i=0}^{n-1} \frac{1 - q^{i+1}}{1-q}\\ &= \frac{\prod_{i=0}^{n-1} (1 - q^{i+1})}{(1-q)^n} = \frac{(q;q)_n}{(1-q)^n}\\ &= [n]_q ! \end{align*}$

We now extend the definition of inversions to words on the alphabet $\textstyle \{1,\dots,k\}$ . If $\textstyle w(i)$ is the symbol at the $\textstyle i^\mathrm{th}$ position of the word $\textstyle w$ , then an inversion in $\textstyle w$ is a pair $\textstyle (i,j)$ of positions such that $\textstyle i < j$ , but $\textstyle w(i) > w(j)$ .

We wish to know the generating series with respect to inversions for the set $\textstyle \mathfrak{W}^{(n)}_{n_1,\dots,n_k}$ of words of length $\textstyle n$ on $\textstyle \{1,\dots,k\}$ with $\textstyle n_i$ occurrences of $\textstyle i$ .

To get it, we will use an indirect decomposition, decomposing an element $\textstyle \sigma \in \mathfrak{S}_n$ as a word $\textstyle w \in \mathfrak{W}^{(n)}_{n_1,\dots,n_k}$ , together with permutations $\textstyle \sigma_1 \in \mathfrak{S}_{B_1}, \dots, \sigma_k \in \mathfrak{S}_{B_k}$ in a bijection which additively preserves inversions, where $\textstyle n = n_1 + n_2 + \cdots + n_k$ and $\textstyle B_i$ is a set with $\textstyle n_i$ elements.

That is, our weight-preserving bijection will look like:

$(\mathfrak{S}_n,\mathrm{inv}) \,\,\tilde\to\,\, (\mathfrak{W}^{(n)}_{n_1,\dots,n_k},\mathrm{inv})\times(\mathfrak{S}_{B_1},\mathrm{inv})\times \cdots \times (\mathfrak{S}_{B_k},\mathrm{inv})$

We split the domain of a permutation $\textstyle \sigma \in \mathfrak{S}_n$ into blocks with sizes $\textstyle n_1,\dots,n_k$ in the obvious way, with the $\textstyle i^\mathrm{th}$ block consisting of the elements $\textstyle B_i = \{m_i + 1,\dots,m_i + n_i\}$ where $\textstyle m_i = n_1 + \cdots + n_{i-1}$ . Note that $\textstyle \mathfrak{S}_{n_i}$ acts on $\textstyle B_i$ in a canonical way, with a permutation $\textstyle \rho \in \mathfrak{S}_{n_i}$ sending $\textstyle m_i + j$ to $\textstyle m_i + \rho(j)$ .

The word $\textstyle w$ is then defined by $\textstyle w(j) = i$ if $\textstyle \sigma(j) \in B_i$ .

We define the permutation $\textstyle \sigma_i$ for each $\textstyle i \in \{1,\dots,k\}$ as the subword of $\textstyle \sigma$ consisting of the elements of $\textstyle B_i$ . Note that if $\textstyle u$ and $\textstyle v$ are both elements of $\textstyle B_i$ , then $\textstyle (u,v)$ is an inversion of $\textstyle \sigma$ if and only if it is also is an inversion of $\textstyle \sigma_i$ .

It will help to illustrate this bijection with an example. Take $\textstyle n_1 = 3$ , $\textstyle n_2 = 3$ and $\textstyle n_3 = 2$ , so that $\textstyle B_1 = \{1,2,3\}$ , $\textstyle B_2 = \{4,5,6\}$ and $\textstyle B_3 = \{7,8\}$ .

Let $\textstyle \sigma \in \mathfrak{S}_8$ be the permutation (in word form):

$\sigma = \begin{pmatrix}6&2&5&3&1&4&8&7\end{pmatrix}$

Then we construct the word $\textstyle w \in \mathfrak{W}^{(8)}_{3,3,2}$ by taking $\textstyle w(i)$ to be the block in which $\textstyle \sigma(i)$ occurs:

$w = \begin{pmatrix}2&1&2&1&1&2&3&3\end{pmatrix}$

We then compute:

$\begin{align*} \sigma_1 &= \begin{pmatrix}2&3&1\end{pmatrix}\\ \sigma_2 &= \begin{pmatrix}6&5&4\end{pmatrix}\\ \sigma_3 &= \begin{pmatrix}8&7\end{pmatrix} \end{align*}$

To invert the above process, we simply replace the $\textstyle j^\mathrm{th}$ occurrence of $\textstyle k$ in the word $\textstyle w$ with $\textstyle \sigma_k(m_k + j)$ . Hence, this is a bijection.

To see that it is additively weight-preserving with respect to inversions, we do a bit of a case analysis. We classify the inversions $\textstyle (u,v)$ of $\textstyle \sigma$ according to whether $\textstyle \sigma(u)$ and $\textstyle \sigma(v)$ are in the same block $\textstyle B_i$ or in different blocks.

If they are in different blocks, say $\textstyle \sigma(u) \in B_i$ and $\textstyle \sigma(v) \in B_j$ , then since $\textstyle \sigma(u) > \sigma(v)$ , we must have $\textstyle i > j$ , and so $\textstyle w(u) = i > j = w(v)$ . Hence $\textstyle (u,v)$ is also an inversion of $\textstyle w$ . Conversely, every inversion of $\textstyle w$ will clearly be an inversion of $\textstyle \sigma$ of this type, since if $\textstyle u < v$ but $\textstyle i = w(u) > w(v) = j$ , we have that $\textstyle \sigma(u) \in B_i$ and $\textstyle \sigma(v) \in B_j$ , but since $\textstyle i > j$ , any element of $\textstyle B_i$ is greater than any element of $\textstyle B_j$ , and in particular $\textstyle \sigma(u) > \sigma(v)$ .

If they are in the same block $\textstyle B_i$ , then by a previous argument, $\textstyle (u,v)$ is an inversion of $\textstyle \sigma$ if and only if it is an inversion of $\textstyle \sigma_i$ .

Hence, we have that $\textstyle \mathrm{inv}(\sigma) = \mathrm{inv}(w) + \sum_{i=1}^k \mathrm{inv}(\sigma_i)$ .

By subtracting $\textstyle m_i$ from each of the elements of $\textstyle \sigma_i$ , we obtain a standard permutation $\textstyle \sigma^*_i \in \mathfrak{S}_{n_i}$ , and this is obviously inversion-preserving.

So, we have a weight-preserving bijection:

$\begin{align*} (\mathfrak{S}_n,\mathrm{inv}) &\,\,\tilde\to\,\, (\mathfrak{W}^{(n)}_{n_1,\dots,n_k},\mathrm{inv})\times(\mathfrak{S}_{B_1},\mathrm{inv})\times \cdots \times (\mathfrak{S}_{B_k},\mathrm{inv})\\ &\,\,\tilde\to\,\, (\mathfrak{W}^{(n)}_{n_1,\dots,n_k},\mathrm{inv})\times(\mathfrak{S}_{n_1},\mathrm{inv})\times \cdots \times (\mathfrak{S}_{n_k},\mathrm{inv}) \end{align*}$

Hence, we have a corresponding equation of generating series. Let $\textstyle W^{(n)}_{n_1,n_2,\cdots,n_k}(q)$ be the generating series for
$\textstyle (\mathfrak{W}^{(n)}_{n_1,\dots,n_k},\mathrm{inv})$ . Then:

$[n]_q! = W^{(n)}_{n_1,n_2,\cdots,n_k}(q) [n_1]_q! [n_2]_q! \cdots [n_k]_q!$
and hence,
$\begin{align*} W^{(n)}_{n_1,n_2,\cdots,n_k}(q) &= \frac{[n]_q!}{[n_1]_q! [n_2]_q! \cdots [n_k]_q!}\\ &={n\choose n_1,n_2,\dots,n_k}_q \end{align*}$

[pdf version]

Permutation indices

Posted in Cale on January 9th, 2010 by Cale – Be the first to comment

Here’s just a quick post of a plot I did a quite a while back:

invmaj

This animation shows for $\textstyle \mathfrak{S}_1$ through to $\textstyle \mathfrak{S}_9$ the number of permutations with a given number of inversions and major index. I love the way that discrete structure slowly falls away into something nearly continuous. I would have included more frames in the animation, but as there are $\textstyle n!$ permutations in $\textstyle \mathfrak{S}_n$ it gets expensive to compute these by brute force counting. I would need to come up with a more effective method.

An inversion of a permutation $\textstyle \sigma$ on $\textstyle [n]=\{1,\dots,n\}$ is a pair of elements $\textstyle (i,j)$ with $\textstyle 1 \leq i < j \leq n$ such that $\textstyle \sigma(j) < \sigma(i).$ That is, the permutation reverses their order. The inversion number, $\textstyle \mathrm{inv}(\sigma),$ is the number of such pairs that a given permutation has. For example, the permutation $\textstyle \sigma = [3,1,4,2]$ (regarded as a word, not a cycle) has inversions $\textstyle \{(3,1),(3,2),(4,2)\},$ and so $\textstyle \mathrm{inv}(\sigma) = 3.$

A descent in a permutation $\textstyle \sigma$ is a position $\textstyle i$ with $\textstyle 1 \leq i \leq n-1$ where a larger number occurs immediately before a smaller one. That is, $\textstyle \sigma(i) > \sigma(i+1).$ The major index, $\textstyle \mathrm{maj}(\sigma)$ is defined as the sum of the descents. For example, in the permutation $\textstyle \sigma = [3,1,4,2]$ we have descents at the first position (3 falls to 1), and at the third (4 falls to 2). So the major index of this permutation is $\textstyle 1 + 3 = 4.$

The plot shows at position $\textstyle (i,j)$ the number of permutations with exactly $\textstyle i$ inversions, and major index $\textstyle j$ as a normalised shade of grey, darker meaning larger. Indices increase left to right and top to bottom.

You can easily see from the symmetry of the plots that permutations are equidistributed with respect to these two indices, so that we can expect the polynomial where the coefficient of $\textstyle q^i t^j$ is the number of permutations with inversion number $\textstyle i$ and major index $\textstyle j$ will be a symmetric polynomial in $\textstyle q$ and $\textstyle t.$

Categorical Logic I

Posted in Cale on December 8th, 2009 by Cale – 2 Comments

Suppose we have almost any deduction system whatsoever. (I’m going to refine things and ask for more structure as we go along, but for now it will do.)

Our deduction system consists of a bunch of statements, and some rules for determining when some statements follow from others. It’s not much of a stretch to demand that given any statement $\textstyle X$ , we will be able to prove $\textstyle X$ from it, that is, that we have some trivial deduction $\textstyle X \vdash X$ . Also, in order to keep things interesting, if we have a deduction $\textstyle X \vdash Y$ , and a deduction $\textstyle Y \vdash Z$ , we ought to have some way to join them into a deduction $\textstyle X \vdash Z$ . This will be some sort of “concatenation of proofs”, but we’re not going to care how it’s implemented, just so long as it is associative, and the “identity deduction” above is an identity for it.

So, anyone who knows me well enough should know what’s coming now. We form a category whose objects are statements, and where the set of arrows $\textstyle X \to Y$ are exactly the deductions $\textstyle X \vdash Y$ . That is, the proofs of $\textstyle Y$ given $\textstyle X$ . The identity arrows are given by trivial deductions, and the composition is our concatenation of proofs.

Let’s rediscover basic logical operations in terms of category theoretic constructions.

Starting simple, what would an initial object $\textstyle 0$ correspond to? Well, the property of an initial object is that for any $\textstyle X$ we have a (unique) arrow $\textstyle 0 \to X.$ This seems to suggest that $\textstyle 0$ ought to be a statement which is trivially false, as anything can be deduced from it.

How about a terminal object $\textstyle 1$ ? There we have for any $\textstyle X$ , a unique arrow $\textstyle X \to 1.$ So this is behaving like something trivially true.

You might recall that in an arbitrary category with a terminal object, we often define an element of an object $\textstyle X$ to be an arrow $\textstyle 1 \to X.$ What would that be here? Well, it’s a proof of $\textstyle X$ starting from something which is trivially true, or just a proof of $\textstyle X.$ Dually, a coelement of $\textstyle X$ which is an arrow $\textstyle X \to 0$ will be a proof of falsity from $\textstyle X,$ or a refutation of $\textstyle X.$

How about the product of statements $\textstyle X$ and $\textstyle Y$ ? Well, $\textstyle X \times Y$ should be a statement which, according to the projection maps, implies both $\textstyle X$ and $\textstyle Y,$ and moreover, if any other statement $\textstyle Z$ implies both $\textstyle X$ and $\textstyle Y,$ then there must be a (unique) proof that $\textstyle Z$ implies $\textstyle X \times Y,$ making the following diagram commute:

$\xymatrix{ \quad& & Z\ar[ddll]_{f}\ar[ddrr]^{g}\ar[dd]^{(f,g)} & & \\ \quad\\ X & & X \times Y\ar[ll]^{\pi_X}\ar[rr]_{\pi_Y} & & Y }$

These are the usual properties attributed to logical AND, so the existence of (finite) products is, modulo perhaps some squabbling about uniqueness of proofs, equivalent to the notion that we have statements representing the conjunctions of other statements.

In a similar fashion, the coproduct $\textstyle X + Y$ has essentially all the properties we’d expect from logical disjunction (OR) of statements.

How about exponential objects? Recall that if $\textstyle X$ and $\textstyle Y$ are objects in some category $\textstyle \mathcal{C}$ , then an exponential object $\textstyle Y^X$ is an object of $\textstyle \mathcal{C}$ together with an arrow

$\mathrm{apply}: Y^X \times X \to Y$

so that whenever there is an arrow

$f: Z \times X \to Y$

we have that there is a unique arrow

$\hat{f}: Z \to Y^X$

such that the following diagram commutes:

$\xymatrix{ Z \times X \ar[dd]_{(\hat{f},\mathrm{id}_X)} \ar[ddrr]^{f} \\ \\ Y^X \times X \ar[rr]_{\mathrm{apply}} & & Y }$

In order to better follow this, we can try setting $\textstyle Z$ to be $\textstyle 1$ , in which case $\textstyle f$ becomes simply an arrow $\textstyle X \to Y,$ and $\textstyle \hat{f}$ becomes an arrow $\textstyle 1 \to Y^X,$ which we can think of as an element of the exponential.

That is, every proof of $\textstyle Y^X$ should correspond to a proof that $\textstyle X \to Y.$

So exponential objects correspond directly with implication.

What about logical negation? Well, we said earlier that an arrow $\textstyle X \to 0$ would act like a refutation of $\textstyle X,$ so a natural thing to do would be to define $\textstyle \neg X$ to be $\textstyle 0^X.$

Okay, so if our deduction system is in fact a Cartesian closed category with coproducts, it means we have encodings of the usual logical operations. What about the usual properties of logical operations with respect to each other?

Firstly, can we prove the distributive laws? In classical logic, we have that

$A \times (B + C) \iff (A \times B) + (A \times C)$ and that $A + (B \times C) \iff (A + B) \times (A + C)$

Secondly, do we get De Morgan’s laws for free, or do we need to add something more to this formulation?

I’ll leave those questions to be answered next time.

[pdf version]

A note about conjugation of permutations

Posted in Cale on November 28th, 2009 by Cale – Be the first to comment

I had a feeling that while the use of linear algebra in Robin’s notes about the action of conjugation in permutation groups is interesting, I thought it would be nice to see why the conjugacy classes are determined by cycle type by a purely combinatorial argument. After a chat about it, Robin encouraged me to write this note.

Let’s start by looking just at what happens when we conjugate a single cycle $\textstyle c = (c_1,c_2,\dots,c_k)$ by an arbitrary permutation $\textstyle \sigma$ , both in $\textstyle \mathfrak{S}_n$ , giving:

$c^\sigma = (c_1,c_2,\dots,c_k)^\sigma = \sigma^{-1} (c_1,c_2,\dots,c_k) \sigma$

First of all, which elements of $\textstyle [n] = \{1,2,\dots,n\}$ will be affected?

Diagrammatically, we have something which looks like this:

$\begin{tikzpicture}[cross line/.style={preaction={draw=white,-,line width=6pt}}] \node[font=\tiny] (d1) at (0,1.5) {$\bullet$}; \node (i) at (1,1) {$c_i$}; \node (j) at (1,-1) {$c_{i+1}$}; \node[font=\tiny] (d2) at (0,-1.5) {$\bullet$}; \draw[bend left=18,->,font=\scriptsize] (d1) to node[auto] {$c$} (i); \draw[bend left=23,->] (i) to node[auto] {$c$} (j); \draw[bend left=18,->,font=\scriptsize] (j) to node[auto] {$c$} (d2); \draw[bend left=60,->,dotted] (d2) to (d1); \node (si) at (-2.5,1) {$c_i^\sigma$}; \node (sj) at (-2.5,-1) {$c_{i+1}^\sigma$}; \node (si') at (3,1) {$c_i^\sigma$}; \node (sj') at (3,-1) {$c_{i+1}^\sigma$}; \draw[->] (si) to[cross line] node[near start,auto] {$\sigma^{-1}$} (i); \draw[->] (sj) to[cross line] node[near start,auto] {$\sigma^{-1}$} (j); \draw[->] (i) to node[auto] {$\sigma$} (si'); \draw[->] (j) to node[auto] {$\sigma$} (sj'); \end{tikzpicture}$

Here, the vertices are elements of $\textstyle [n]$ , and the arrows show where various permutations send them, according to which permutation they are labelled with.

There are two sets of elements to consider: those which are sent to some $\textstyle c_i$ by $\textstyle \sigma^{-1}$ , and so are equal to $\textstyle c_i^\sigma$ for some $\textstyle i,$ and those which are not.

If $\textstyle x$ is not sent to something affected by the cycle by $\textstyle \sigma^{-1}$ , so that

$(x^{\sigma^{-1}})^c = x^{\sigma^{-1}}$

then we have:

$x^{\sigma^{-1} c \sigma} = (x^{\sigma^{-1}})^{c \sigma} = (x^{\sigma^{-1}})^\sigma = x$

so that $\textstyle x$ is unaffected by the conjugated cycle.

On the other hand, if

$x = c_i^\sigma$

we have that:

$(c_i^\sigma)^{\sigma^{-1} c \sigma} = c_i^{c \sigma} = c_{i+1}^{\sigma}$

(You can follow this in the diagram above, by starting at the $\textstyle c_i^\sigma$ and taking the $\textstyle \sigma^{-1}, c, \mbox{ and } \sigma$ arrows successively.)

So the upshot of this is that:

$(c_1,\dots,c_k)^\sigma = (c_1^\sigma,\dots,c_k^\sigma)$

As each $\textstyle c_i^\sigma$ is sent by $\textstyle c^\sigma$ to $\textstyle c_{i+1}^\sigma$ , and everything else is left untouched.

To rearrange the diagram a little to reflect this new insight, we have something like this:

$\begin{tikzpicture}[cross line/.style={preaction={draw=white,-,line width=6pt}}] \node[font=\tiny] (d1) at (0,1.5) {$\bullet$}; \node (i) at (1,1) {$c_i$}; \node (j) at (1,-1) {$c_{i+1}$}; \node[font=\tiny] (d2) at (0,-1.5) {$\bullet$}; \draw[bend left=18,->,font=\scriptsize] (d1) to node[auto] {$c$} (i); \draw[bend left=23,->] (i) to node[auto] {$c$} (j); \draw[bend left=18,->,font=\scriptsize] (j) to node[auto] {$c$} (d2); \draw[bend left=60,->,dotted] (d2) to (d1); \node[font=\tiny] (sd1) at (4,1.5) {$\bullet$}; \node (si) at (5,1) {$c_i^\sigma$}; \node (sj) at (5,-1) {$c_{i+1}^\sigma$}; \node[font=\tiny] (sd2) at (4,-1.5) {$\bullet$}; \draw[bend left=18,->,font=\scriptsize] (sd1) to node[auto] {$c^\sigma$} (si); \draw[bend left=23,->] (si) to node[auto] {$c^\sigma$} (sj); \draw[bend left=18,->,font=\scriptsize] (sj) to node[auto] {$c^\sigma$} (sd2); \draw[bend left=60,->,dotted] (sd2) to (sd1); \draw[->] (si) to[cross line] node[auto,pos=0.6] {$\sigma^{-1}$} (i); \draw[->] (j) to[cross line] node[auto,pos=0.4] {$\sigma$} (sj); \end{tikzpicture}$

The trivial but important corollary here is that the image of a cycle under conjugation is always another cycle of the same length.

Another important result is that given two cycles of the same length, say $\textstyle c = (c_1,\dots,c_k)$ and $\textstyle d = (d_1,\dots,d_k)$ we can easily find a permutation $\textstyle \sigma,$ conjugation by which will send one to the other. Start with a function

$\begin{align*} \sigma^*: \{c_1,\dots,c_k\} &\to \{d_1,\dots,d_k\}\\ c_i &\mapsto d_i \end{align*}$

This will be well-defined, since each element of the first cycle occurs only once, and injective since any element will only occur once in the second cycle. So it will extend to a permutation in $\textstyle \mathfrak{S}_n$ (in a number of different ways in general). Any such permutation will do.

Since there are $\textstyle k$ different ways to line up the elements of the two cycles, and $\textstyle (n-k)!$ ways to rearrange the remainder of the elements, there will be $\textstyle k (n-k)!$ permutations that conjugate any single cycle of length $\textstyle k$ in $\textstyle \mathfrak{S}_n$ to any other cycle of length $\textstyle k.$

So individual cycles are conjugate if and only if they have the same length.

The next thing to note is that since every permutation can be written as a product of disjoint cycles, and conjugation is a group homomorphism, we have that conjugation preserves cycle type.

But not only does it preserve cycle type, as with individual cycles, given two permutations having the same cycle type, we can easily construct a permutation that sends one to the other, in much the same way as we did with the individual cycles. Just line up all the cycles of the same length in each permutation (there’ll be some choice in the matter, but any choice will do), and define a permutation sending each element of each cycle to the corresponding element of the corresponding cycle. Of course, unlike the case with just a single cycle, after choosing how to line things up this time, there will be no remaining choices to make (provided that we include cycles of length 1 in the process, if any).

For example, if we have:

$\begin{align*} a &= (1,2) (3,6,7) (5,9,12) (4,8,11,10)\\ b &= (5,8) (1,3,6) (2,10,4) (7,12,11,9) \end{align*}$

then we can simply read off the columns, choosing

$1^\sigma = 5, 2^\sigma = 8, 3^\sigma = 1, \dots$

to get

$\begin{align*} \sigma &= (1,5,2,8,12,4,7,6,3) (9,10) (11) \end{align*}$

and then $\textstyle a^\sigma = b.$

Rather than checking that we did this correctly by hand, we can confirm it using gap, as follows:

gap> a := (1,2)(3,6,7)(5,9,12)(4,8,11,10); (1,2)(3,6,7)(4,8,11,10)(5,9,12) gap> b := (5,8)(1,3,6)(2,10,4)(7,12,11,9); (1,3,6)(2,10,4)(5,8)(7,12,11,9) gap> sigma := (1,5,2,8,12,4,7,6,3)(9,10)(11); (1,5,2,8,12,4,7,6,3)(9,10) gap> a^sigma = b; true

And there you have it.

To summarise, conjugacy of permutations is entirely determined by their cycle type, and in general, there will be one permutation that conjugation by which sends one to the other for each way to align corresponding cycles of the same length.

So, if the cycle type is some partition:

$\lambda = (\lambda_1^{m_1},\dots,\lambda_k^{m_k})$

where the $\textstyle \lambda_i$ are distinct, and the $\textstyle m_i$ indicate the number of times that cycle length occurs (and so are not an exponent in the usual sense), then since we have $\textstyle m_i!$ ways to pair up cycles of length $\textstyle \lambda_i$ , and then for each of these cycles, we can choose from $\textstyle \lambda_i$ cyclic shifts to pair up members of that cycle, we have that the total number of permutations sending one member of this conjugacy class to another under conjugation are:

$z_\lambda = \prod_{i = 1}^k m_i!\,\lambda_i^{m_i}$

For example, my permutations above both had cycle type $\textstyle (2,3^2,4),$ and so the number of ways we could have constructed $\textstyle \sigma,$ by rearranging the cycles in $\textstyle b$ is:

$z_{(2,3^2,4)} = 2 \cdot 2!\,3^2 \cdot 4 = 144$

Because of this computation, we can tell how many elements are in each conjugacy class. If for every permutation that sends $\textstyle a$ to $\textstyle b$ , we have exactly $\textstyle z_\lambda$ of them which do the same thing, we have that starting from any permutation $\textstyle a,$ there are $\textstyle \frac{n!}{z_\lambda}$ distinct things we can get by conjugating with each of the $\textstyle n!$ permutations in $\textstyle \mathfrak{S}_n,$ which is then the size of the conjugacy class $\textstyle \mathfrak{S}_\lambda.$

[pdf version]

Natural transformations 5

Posted in Cale on November 18th, 2009 by Cale – Be the first to comment

Suppose that we have categories, functors, and natural transformations as suggested by the following diagram:

$ \xy (-32,0)*+{\mathcal{E}}="E"; (0,0)*+{\mathcal{D}}="D"; {\ar@/^3pc/^{U} "D";"E"}="U"; {\ar "D";"E"}="U'"; (-20,2)*{\scriptstyle{U'}}; {\ar@/_3pc/_{U''} "D";"E"}="U''"; (32,0)*+{\mathcal{C}}="C"; {\ar@/^3pc/^{V} "C";"D"}="V"; {\ar "C";"D"}="V'"; (12,2)*{\scriptstyle{V'}}; {\ar@/_3pc/_{V''} "C";"D"}="V''"; {\ar@{=>}_{\alpha} (-16,2)*{}; (-16,11)*{}}; {\ar@{=>}_{\beta} (-16,-11)*{}; (-16,-2)*{}}; {\ar@{=>}_{\gamma} (16,2)*{}; (16,11)*{}}; {\ar@{=>}_{\delta} (16,-11)*{}; (16,-2)*{}}; \endxy $

It’s not yet clear at this point, even though we have horizontal and vertical composition, that this diagram defines a well-defined composite, since there are at least two ways we could put this a diagram together. We could either take the vertical composites $\textstyle \alpha \circ \beta$ and $\textstyle \gamma \circ \delta$ , and then horizontally compose them, or we could take the horizontal composites $\textstyle \alpha \bullet \gamma$ and $\textstyle \beta \bullet \delta$ and then vertically compose them. However:

$\begin{align*} & (\alpha \circ \beta) \bullet (\gamma \circ \delta)\\ =\; & (\alpha \circ \beta) V'' \circ U (\gamma \circ \delta) & \mbox{def. of $\bullet$}\\ =\; & (\alpha V'' \circ \beta V'') \circ (U \gamma \circ U \delta) & \mbox{distrib.}\\ =\; & \alpha V'' \circ (\beta V'' \circ U \gamma) \circ U \delta & \mbox{assoc. of $\circ$}\\ =\; & \alpha V'' \circ (\beta \bullet \gamma) \circ U \delta & \mbox{def. of $\bullet$}\\ =\; & \alpha V'' \circ (U' \gamma \circ \beta V') \circ U \delta & \mbox{equiv. def. of $\bullet$}\\ =\; & (\alpha V'' \circ U' \gamma) \circ (\beta V' \circ U \delta) & \mbox{assoc. of $\circ$}\\ =\; & (\alpha \bullet \gamma) \circ (\beta \bullet \delta) & \mbox{def. of $\bullet$} \end{align*}$

So indeed, we have the law that:

$\boxed{(\alpha \circ \beta) \bullet (\gamma \circ \delta) = (\alpha \bullet \gamma) \circ (\beta \bullet \delta)}$

which is known as the interchange law.

The interchange law and the associativity of vertical and horizontal composition together give us the somewhat-awkward-to-formalise but intuitive result that if we have any diagram of natural transformations that we could compose, it doesn’t matter what order we choose to do it in. So the pasting diagrams that we’ve been using, being somewhat ambiguous about it, are really an appropriate notation to use.

It’s also possibly worth noting here that the functor distributivity laws we used to prove the interchange law and the associativity of horizontal composition are also special cases of the interchange law. For example:

$\begin{align*} & (\alpha \circ \beta) V\\ = \; & (\alpha \circ \beta) \bullet \mathrm{id}_V\\ = \; & (\alpha \circ \beta) \bullet (\mathrm{id}_V \circ \mathrm{id}_V)\\ = \; & (\alpha \bullet \mathrm{id}_V) \circ (\beta \bullet \mathrm{id}_V)\\ = \; & \alpha V \circ \beta V\\ \end{align*}$

There’s a valuable analogy to be had here with the multiplication and tensor product of linear maps.

If we have vector spaces $\textstyle V, V', W, W'$ , and linear maps $\textstyle A: V \to V'$ and $\textstyle B: W \to W'$ then we can define the tensor product of linear maps:

$\boxed{\begin{aligned} A \otimes B: V \otimes W & \to V' \otimes W'\\ (A \otimes B)(v \otimes w) & = (A v) \otimes (B w) \end{aligned}}$

With this definition, we have that:

$\begin{align*} & ((A \circ B) \otimes (C \circ D)) (v \otimes w) \\ = \; & ((A \circ B) v \otimes (C \circ D) w)\\ = \; & (A (B v) \otimes C (D w))\\ = \; & (A \otimes C) ((B v) \otimes (D w))\\ = \; & (A \otimes C) ((B \otimes D) (v \otimes w))\\ = \; & ((A \otimes C) \circ (B \otimes D)) (v \otimes w) \end{align*}$

so we have that:

$\boxed{(A \circ B) \otimes (C \circ D) = (A \otimes C) \circ (B \otimes D)}$

The situation for natural transformations, vertical, and horizontal composition looks so similar to the one for linear maps, composition, and tensor product that it seems there must be something going on here.

In fact there is, and in order to explain it, we’ll need the notion of a weak 2-category, which I’ll save for another time.

[pdf format]

Natural transformations 4

Posted in Cale on November 16th, 2009 by Cale – Be the first to comment

Okay, so we’ve seen at least a handful of examples of these natural transformation things. They are actually all over the place if you know where to look for them. As we move along through other categorical structures, we’ll see a fair number of them.

So, if natural transformations are supposed to be the arrows between functors, and we’re intending to do some category theory, we should be unsatisfied with just an unstructured set of them. We really ought to be able to compose them! Owing to their two-dimensional nature, there will actually be two ways.

Let’s start with the most obvious one, the one which turns the collection of functors between any two categories into a category itself.

Suppose we have categories, functors and natural transformations as depicted in this diagram:

$ \xy (-16,0)*+{\mathcal{D}}="D"; (16,0)*+{\mathcal{C}}="C"; {\ar@/^3pc/^{F} "C";"D"}="F"; {\ar "C";"D"}="G"; (-5,2)*{\scriptstyle{G}}; {\ar@/_3pc/_{H} "C";"D"}="H"; {\ar@{=>}_{\eta} (0,-11)*{}; (0,-2)*{}}; {\ar@{=>}_{\lambda} (0,2)*{}; (0,11)*{}}; \endxy $

So, these line up nicely, and for any object $\textstyle X \in \mathcal{C}$ we have components:

$\xymatrix{ HX \\ GX \ar[u]_{\lambda_X} \\ FX \ar[u]_{\eta_X}\\ }$

and if we have any arrow in $\textstyle \mathcal{C}$ :

$\xymatrix{ Y & X \ar[l]_{a} }$

then we have the following diagram in $\textstyle \mathcal{D}$ :

$\xymatrix{ HY & HX \ar[l]_{Ha}\\ GY \ar[u]_{\lambda_Y} & GX \ar[u]_{\lambda_X} \ar[l]_{Ga} \\ FY \ar[u]_{\eta_Y} & FX \ar[u]_{\eta_X} \ar[l]_{Fa}\\ }$

Since each naturality square commutes, the outer rectangle does as well:

$\begin{align*} & \lambda_Y \circ \eta_Y \circ Fa \\ = \, & \lambda_Y \circ Ga \circ \eta_X \\ = \, & Ha \circ \lambda_X \circ \eta_X \end{align*}$

which means that we have a new natural transformation, called the vertical composite of $\textstyle \lambda$ and $\textstyle \eta$ defined by:

$\boxed{(\lambda \circ \eta)_X = \lambda_X \circ \eta_X}$

(The above equation is in a box, because it is so very important to remember when working with these things!)

Moreover, we have identity and associativity fall out essentially immediately from the identity and associativity of arrows in $\textstyle \mathcal{D}.$ (If this isn’t clear, then check it!)

That is, for any natural transformation $\textstyle \alpha: U \to U',$

$\boxed{\begin{aligned} \mathrm{id}_{U'} \circ \alpha & = \alpha\\ \alpha \circ \mathrm{id}_{U} & = \alpha\\ \end{aligned}}$

where $\textstyle \mathrm{id}_U$ is the identity natural transformation:

$\boxed{(\mathrm{id}_U)_X = \mathrm{id}_{(UX)}}$

and if we have natural transformations like this:

$ \xy (-16,0)*+{\mathcal{D}}="D"; (16,0)*+{\mathcal{C}}="C"; {\ar@/^3.5pc/ "C";"D"}; {\ar@/^1.33pc/ "C";"D"}; {\ar@/_1.33pc/ "C";"D"}; {\ar@/_3.5pc/ "C";"D"}; {\ar@{=>}_{\alpha} (0,-13)*{}; (0,-7)*{}}; {\ar@{=>}_{\beta} (0,-4)*{}; (0,4)*{}}; {\ar@{=>}_{\gamma} (0,7)*{}; (0,13)*{}}; \endxy $

then,

$\boxed{(\alpha \circ \beta) \circ \gamma = \alpha \circ (\beta \circ \gamma)}$

Now let’s turn to the second type of composition. This time, we have categories and functors like so:

$ \xy (-32,0)*+{\mathcal{E}}="E"; (0,0)*+{\mathcal{D}}="D"; (32,0)*+{\mathcal{C}}="C"; {\ar@/^2pc/^{U} "D";"E"}="U"; {\ar@/^2pc/^{V} "C";"D"}="V"; {\ar@/_2pc/_{U'} "D";"E"}="U'"; {\ar@/_2pc/_{V'} "C";"D"}="V'"; {\ar@{=>}_{\alpha} (-16,-7)*{}; (-16,7)*{}}; {\ar@{=>}_{\beta} (16,-7)*{}; (16,7)*{}}; \endxy $

So, for any $\textstyle X \in \mathcal{C}$ we have the following components (examine this from right to left, as I’ve aligned the bits here with which category they lie in, in the diagram above):

$\xymatrix{ U'V'X & U'VX \ar[l]_{U'\beta_X} & & V'X & &\ar@{}[dr]|{}="X"& \\ UV'X \ar[u]_{\alpha_{V'X}} & UVX \ar[l]_{U\beta_X} \ar[u]_{\alpha_{VX}} & & VX \ar[u]_{\beta_X} & & & \\ \save "X" *{X} \restore }$

Because $\textstyle \alpha$ is natural, we have that the square in $\textstyle \mathcal{E}$ actually commutes:

$\alpha_{V'X} \circ U \beta_X = U' \beta_X \circ \alpha_{VX}$

So, we will define the horizontal composite of this $\textstyle \alpha$ and $\textstyle \beta$ as the common value:

$\boxed{(\alpha \bullet \beta)_X = \alpha_{V'X} \circ U \beta_X = U' \beta_X \circ \alpha_{VX} }$

This might seem complicated and hard to remember, but we can simplify it a bit if we define (for any appropriate $\textstyle \alpha$ and $\textstyle V$ ):

$\boxed{(\alpha V)_X = \alpha_{(VX)}}$
so that if
$\alpha: U \to U'$
then
$\alpha V: UV \to U'V$

And similarly,

$\boxed{(U \beta)_X = U (\beta_X)}$
so that if
$\beta: V \to V'$
then
$U\beta: UV \to UV'$

Then the definition above becomes

$\boxed{(\alpha \bullet \beta)_X = (\alpha V' \circ U \beta)_X = (U' \beta \circ \alpha V)_X}$

or more abstractly,

$\boxed{\alpha \bullet \beta = \alpha V' \circ U \beta = U' \beta \circ \alpha V}$

The notation is starting to better reflect the notion that we’re just doing $\textstyle \alpha$ on the $\textstyle U$ part, and $\textstyle \beta$ on the $\textstyle V$ part, and it doesn’t matter which one we do first, so long as we do them both.

The notation is also getting simpler. As we develop the properties of vertical and horizontal composition, this will all get conceptually much easier to keep track of.

One thing which is nice to notice is that these new notations we’ve defined for sticking a functor onto a natural transformation are the same as horizontal composition with the identity natural transformation on that functor:

$\begin{align*} (\alpha \bullet \mathrm{id}_V)_X & = U' (\mathrm{id}_V)_X \circ \alpha_{VX} & \mbox{def. of $\bullet$} \\ & = U' \mathrm{id}_{VX} \circ \alpha_{VX} & \mbox{component of identity}\\ & = \mathrm{id}_{U'VX} \circ \alpha_{VX} & \mbox{$U'$ is a functor}\\ & = \alpha_{VX} & \mbox{identity}\\ & = (\alpha V)_X & \mbox{notation} \end{align*}$

The proof that $\textstyle \mathrm{id}_U \bullet \beta = U\beta$ is similar, and a good exercise in checking that you’re comfortable with the definitions and notation.

We also have that $\textstyle \bullet$ is associative. I’m going to start working entirely at the level of functors and natural transformations here, since writing $\textstyle X$ in so many places is becoming tedious, and starts to make the presentation less clear. You’re invited to check anything which is not immediately apparent (in particular, the dubious steps that I’ve marked with (!?)).

We have functors and natural transformations as follows:

$\xy (-32,0)*+{\mathcal{F}}="F"; (0,0)*+{\mathcal{E}}="E"; (32,0)*+{\mathcal{D}}="D"; (64,0)*+{\mathcal{C}}="C"; {\ar@/^2pc/^{U} "E";"F"}="U"; {\ar@/_2pc/_{U'} "E";"F"}="U'"; {\ar@/^2pc/^{V} "D";"E"}="V"; {\ar@/_2pc/_{V'} "D";"E"}="V'"; {\ar@/^2pc/^{W} "C";"D"}="W"; {\ar@/_2pc/_{W'} "C";"D"}="W'"; {\ar@{=>}_{\alpha} (-16,-7)*{}; (-16,7)*{}}; {\ar@{=>}_{\beta} (16,-7)*{}; (16,7)*{}}; {\ar@{=>}_{\gamma} (48,-7)*{}; (48,7)*{}}; \endxy $

$\begin{align*} (\alpha \bullet \beta) \bullet \gamma & = (\alpha \bullet \beta) W' \circ U V \gamma & \mbox{def. of $\bullet$}\\ & = (\alpha V' \circ U \beta) W' \circ U V \gamma & \mbox{def. of $\bullet$} \\ & = (\alpha V'W' \circ (U \beta) W') \circ U V \gamma & \mbox{distrib. (!?)} \\ & = \alpha V'W' \circ ((U \beta) W' \circ U V \gamma) & \mbox{assoc. of $\circ$} \\ & = \alpha V'W' \circ (U (\beta W') \circ U V \gamma) & \mbox{assoc. (!?)} \\ & = \alpha V'W' \circ U (\beta W' \circ V \gamma) & \mbox{distrib. (!?)} \\ & = \alpha V'W' \circ U (\beta \bullet \gamma) & \mbox{def. of $\bullet$} \\ & = \alpha \bullet (\beta \bullet \gamma) & \mbox{def. of $\bullet$} \end{align*}$

That’s obviously important so let’s put it in a box:

$\boxed{(\alpha \bullet \beta) \bullet \gamma = \alpha \bullet (\beta \bullet \gamma)}$

It’s slowly becoming more apparent that perhaps it doesn’t matter at all about which order we choose to paste some complicated diagram of natural transformations together, and that everything is perfectly associative in every possible way that it could be.

We almost have it, there is but one remaining basic property we’ll need, and I’ll save it for the next post.

[pdf version]

Natural transformations 3.b

Posted in Cale on November 15th, 2009 by Cale – Be the first to comment

The other natural transformation from basic linear algebra which I’d like to say something about is actually between two functors

$\mathbf{Field} \to \mathbf{Group}$

Which might seem surprising, until I tell you what they are.

First of all, if $\textstyle F$ is any field, we can form the group of $\textstyle n\times n$ invertible matrices with entries in $\textstyle F$ , commonly known as the general linear group, or $\textstyle \mathrm{GL}_n F.$ Moreover, if $\textstyle \phi: F \to K$ is any field homomorphism, then we get an induced group homomorphism

$\mathrm{GL}_n(\phi): \mathrm{GL}_n F \to \mathrm{GL}_n K$

which simply applies the field homomorphism to each of the entries of the matrix. It’s not hard to check that this is actually a functor

$\mathrm{GL}_n: \mathbf{Field} \to \mathbf{Group}$

from the category of fields to the category of groups.

Secondly, if $\textstyle F$ is any field, we can take its group of units (invertible elements) under multiplication $\textstyle F^*$ , which, since it’s a field, is everything except for $\textstyle 0.$ So long as you’re familiar with the definitions of these things, it’s easy to see that any field homomorphism induces a group homomorphism directly, and that the functor laws are obeyed. So we have:

$*: \mathbf{Field} \to \mathbf{Group}$

In addition to these, we have for any field $\textstyle F$ , a group homomorphism

$\mathrm{det}_F: \mathrm{GL}_n F \to F^*$

the determinant! It’s a group homomorphism now because of the basic results from linear algebra that:

$\begin{align*} \mathrm{det}(\mathbf{1}) & = 1\\ \mathrm{det}(AB) & = \mathrm{det}(A) \mathrm{det}(B) \\ \mathrm{det}(A^{-1}) & = (\mathrm{det}(A))^{-1} \end{align*}$

Now, the naturality square,

$\xymatrix{ \mathrm{GL}_n F \ar[r]^{\mathrm{GL}_n \phi} \ar[d]_{\mathrm{det}_F} & \mathrm{GL}_n K \ar[d]^{\mathrm{det}_K} \\ F^* \ar[r]^{\phi^*} & K^* \\ }$

commutes because the determinant is a polynomial in the entries of the matrix, and field homomorphisms commute with any polynomial map.

So the determinant too numbers among natural transformations.

[pdf version]

Natural transformations 3.a

Posted in Cale on November 15th, 2009 by Cale – Be the first to comment

Let’s have a look at the details of just a couple more examples of natural transformations, this time from linear algebra.

One example is just so standard that I can’t help but give it. If we have some finite dimensional vector space $\textstyle V$ over the field $\textstyle F$ , then the dual space $\textstyle V^*$ is the space of all linear transformations $\textstyle V \to F$ , which in this special case are referred to as linear functionals. It’s not too hard to show that $\textstyle V^*$ has the same dimension as $\textstyle V$ , and therefore must be isomorphic to it. One way is simply to note that the dimension of the space of linear maps $\textstyle V \to W$ is equal to the product of the dimensions of $\textstyle V$ and $\textstyle W$ , and that the dimension of $\textstyle F$ over itself is of course $\textstyle 1$ .

However, there’s no obvious isomorphism to pick. If you fix a basis, there’s a sort of obvious one to choose from there, but each possible choice of basis for $\textstyle V$ leads to a different isomorphism.

However, consider the double dual: $\textstyle V^{**}$ which is the space of linear maps $\textstyle V^{*} \to F$ The situation suddenly seems much different. Of course, again we have that $\textstyle V$ is isomorphic to $\textstyle V^{**}$ , but this time there is a natural choice of isomorphism $\textstyle V \to V^{**}$ , in particular,

$\begin{align*} \eta_V: V & \to V^{**}\\ v & \mapsto (f \mapsto f(v)) \end{align*}$

That is, we send a vector $\textstyle v$ to the linear map which takes a linear functional $\textstyle f$ and sends it to $\textstyle f(v).$

So, there’s a sense here that this choice of isomorphism seems somehow “natural”, and it’s certainly quite special, but how do we formalise that?

Well, we’d like to be able to say that this double dual thing was a functor, and then we could apply our categorical definition of what natural means.

So let’s look at the dual first, and consider a linear map $\textstyle T: V \to W.$ Can we construct from it a linear map $\textstyle V^{*} \to W^{*}?$ Well, it seems not in any obvious way aside from choosing particular isomorphisms.

How about $\textstyle W^{*} \to V^{*}$ then? We could go for making $\textstyle *$ into a functor:

$*: \mathbf{Vec} \to \mathbf{Vec}^\mathrm{op}.$

Given a linear functional $\textstyle g: W\to F$ and a linear map $\textstyle T: V \to W,$ we can just compose them to get a linear functional $\textstyle g\circ T: V\to F.$

This process of converting linear maps $\textstyle V\to W$ into linear maps $\textstyle W^* \to V^*$ is usually called the transpose (as it corresponds to taking the transpose of matrix representations in a particular way), and we define

$T^t(g) = g\circ T.$

We also have that

$\begin{align*} (T\circ U)^t(g) & = g \circ (T \circ U) \\ & = (g \circ T) \circ U \\ & = T^t(g) \circ U \\ & = U^t(T^t(g)) \\ & = (U^t \circ T^t)(g) \end{align*}$
and of course this will send the identity transformation to the identity transformation. So this really is an honest functor.

So, this means that the map $\textstyle **$ which sends each vector space to its double dual and each linear map to the transpose of its transpose is now a plain functor

$**: \mathbf{Vec} \to \mathbf{Vec}.$

Our $\textstyle \eta_V$ from above is now primed to become the component of a natural transformation:

$\eta: \mathrm{id}_\mathbf{Vec} \to **$

All we have to check is that this diagram commutes:

$\xymatrix{ V \ar[r]^{T} \ar[d]_{\eta_V} & W \ar[d]^{\eta_W} \\ V^{**} \ar[r]^{T^{tt}} & W^{**} \\ }$

Easy enough, there’s lots of flipping things around and notation, but it’s all mechanical. For any $\textstyle v \in V$ and $\textstyle g \in W^*$ , we have:

$\begin{align*} (\eta_W\circ T)(v)(g) & = \eta_W (T v)(g) & \mbox{composite}\\ & = g(T v) & \mbox{def. of $\eta_W$}\\ (T^{tt} \circ \eta_V)(v)(g) & = T^{tt}(\eta_V(v))(g) & \mbox{composite}\\ & = (\eta_V(v)\circ T^t)(g) & \mbox{def. of transpose}\\ & = \eta_V(v)(T^t(g)) & \mbox{composite}\\ & = T^t(g)(v) & \mbox{def. of $\eta_V$}\\ & = (g\circ T)(v) & \mbox {def. of transpose}\\ & = g(T v) & \mbox{composite} \end{align*}$

So it works out, and this really is a natural transformation.

[pdf version]

Natural transformations 2

Posted in Cale on November 15th, 2009 by Cale – Be the first to comment

Now that we have the definition of a natural transformation fleshed out, let’s take a look at least a couple of examples before we go off talking about how we can glue them together in various ways.

I’ve been meaning to get some stuff into this blog about functional programming, so let’s borrow our first real example from Haskell. I think most of our readers probably know already, but for anyone who isn’t aware, Haskell is a nice functional programming language with lots of cool features, and I highly recommend checking it out if you’re a mathematician.

So, in Haskell, the various datatypes, together with the Haskell-definable functions between them form a category. Composition of functions f :: B -> C and g :: A -> B is given by the composition function defined in the Prelude:

(.) :: (b -> c) -> (a -> b) -> (a -> c)
(f . g) x = f (g x)

And of course, the identity maps are also in the Prelude:

id :: a -> a
id x = x

So we’ll refer to this category of Haskell types and functions as $\textstyle \mathbf{Hask}.$ In addition to being a category, we have a convenient way within Haskell to talk about functors $\textstyle \mathbf{Hask} \to \mathbf{Hask}.$

Our functor needs to have a part which is a function on types, and parametric types allow us to define some. For instance, for each type a, we have the type [a] of lists of values of type a, and we can define other datastructures which are parametrised on a type, such as binary trees with values of type a at each of the branches:

data Tree a where
   Leaf   :: Tree a
   Branch :: a -> Tree a -> Tree a -> Tree a

This defines Leaf as a value of type Tree a for any type a, and Branch as a function which takes a value of type a and two trees, each of type Tree a, and formally constructs a value of type Tree a.

I am using GADT syntax here, which is a syntax extension supported by GHC. You can turn it on with the flag -XGADTs, or by writing
{-# LANGUAGE GADTs #-}
at the top of your source file.

For example, we might represent the tree of integers:

$\begin{tikzpicture} \draw (0,0) -- (-1,-1) -- (-1.4,-2) -- (-1.6,-2.5); \draw (-1.4,-2) -- (-1.2,-2.5); \draw (-1,-1) -- (-0.6,-2) -- (-1,-3) -- (-1.2,-3.5); \draw (-1,-3) -- (-0.8,-3.5); \draw (-0.6,-2) -- (-0.4,-2.5); \draw (0,0) -- (1,-1) -- (0.6,-2) -- (0.4,-2.5); \draw (0.6,-2) -- (1,-3) -- (0.8,-3.5); \draw (1,-3) -- (1.2,-3.5); \draw (1,-1) -- (1.4,-2) -- (1.2,-2.5); \draw (1.4,-2) -- (1.6,-2.5); \filldraw[fill=brown!50] (-1.4,-2) circle (0.25) node {$1$}; \filldraw[fill=black!30!green] (-1.6,-2.5) circle (0.1); \filldraw[fill=black!30!green] (-1.2,-2.5) circle (0.1); \filldraw[fill=brown!50] (-1,-1) circle (0.25) node {$2$}; \filldraw[fill=brown!50] (-1,-3) circle (0.25) node {$3$}; \filldraw[fill=black!30!green] (-1.2,-3.5) circle (0.1); \filldraw[fill=black!30!green] (-0.8,-3.5) circle (0.1); \filldraw[fill=brown!50] (-0.6,-2) circle (0.25) node {$4$}; \filldraw[fill=black!30!green] (-0.4,-2.5) circle (0.1); \filldraw[fill=brown!50] (0,0) circle (0.25) node {$5$}; \filldraw[fill=brown!50] (0.6,-2) circle (0.25) node {$6$}; \filldraw[fill=black!30!green] (0.4,-2.5) circle (0.1); \filldraw[fill=brown!50] (1,-3) circle (0.25) node {$7$}; \filldraw[fill=black!30!green] (0.8,-3.5) circle (0.1); \filldraw[fill=black!30!green] (1.2,-3.5) circle (0.1); \filldraw[fill=brown!50] (1,-1) circle (0.25) node {$8$}; \filldraw[fill=brown!50] (1.4,-2) circle (0.25) node {$9$}; \filldraw[fill=black!30!green] (1.2,-2.5) circle (0.1); \filldraw[fill=black!30!green] (1.6,-2.5) circle (0.1); \end{tikzpicture}$

using the value:

t :: Tree Integer
t = Branch 5 (Branch 2 (Branch 1 Leaf
                                 Leaf)
                       (Branch 4 (Branch 3 Leaf
                                           Leaf)
                                 Leaf))
             (Branch 8 (Branch 6 Leaf
                                 (Branch 7 Leaf
                                           Leaf))
                       (Branch 9 Leaf
                                 Leaf))

Of course, being a function on types is not enough. If the type constructor [] for lists or Tree for trees is to be a functor, we need a way to send functions (a -> b) to functions [a] -> [b] or Tree a -> Tree b.

In order to provide a uniform interface to such mappings, the Haskell Prelude also defines the following class of type constructors:

class Functor f where
   fmap :: (a -> b) -> (f a -> f b)

Of course, these are really just endofunctors, but for purposes of programming, those are the ones we’re usually most concerned with.

To define [] and Tree as functors then, we write instances:

instance Functor [] where
   fmap f [] = []
   fmap f (x:xs) = f x : fmap f xs

For those unfamiliar with Haskell, the first equation says that applying fmap f to the empty list gives the empty list. The second says that applying it to a nonempty list whose first element is x and where the remainder of the list is called xs (think plural), is the list whose first element is f applied to x, and where the rest of the list is fmap f xs. The end result is that it just applies the function f to each of the values in the list, leaving the list structure otherwise unchanged.

Very similarly, we can define a functor instance for trees:

instance Functor Tree where
   fmap f Leaf = Leaf
   fmap f (Branch x left right) = Branch (f x) (fmap f left)
                                               (fmap f right)

This again just applies the function f to each of the values on the branches of the tree, leaving the structure alone.

Now, these are both functors with common domain and codomain, so perhaps we can describe a natural transformation between them?

A natural transformation $\textstyle \eta: Tree \to [\,]$ would give, for each type a, a function whose type would be Tree a -> [a]. So, we would expect that perhaps some polymorphic function will serve as a natural transformation.

However, this gets better: Since a polymorphic function of that type is disallowed by the type system to actually inspect values of type a as it does its work, it can only shuffle them around in some way which is independent of their values, and the only way it can get values of type a to fill the list is by plucking values from the tree it receives.

So, we would expect that if we applied a function to the values on the branches of the tree beforehand, and then the polymorphic function from trees to lists, the result would be the same as if we applied the polymorphic function first to get a list, and then applied the function to the values of the resulting list. The naturality square commutes!

To write the naturality equation using Haskell syntax, if

eta :: Tree a -> [a]

is our natural transformation, then

fmap f . eta = eta . fmap f

This equation cannot be used directly as part of a program, but will be a law that our code satisfies.

To rephrase all that, every polymorphic function of that type is a natural transformation, and Haskell’s type system will actually ensure that we don’t write code which violates this.

So, what’s a good example? How about something like an inorder traversal?

inorder :: Tree a -> [a]
inorder Leaf = []
inorder (Branch x l r) = inorder l ++ [x] ++ inorder r

Here, the operator (++) is concatenation of lists.

We can test this function in our Haskell interpreter:

ghci> inorder t
[1,2,3,4,5,6,7,8,9]

Aside: This is not the best algorithm to choose from a complexity standpoint because concatenation of lists takes time on the order of the length of the first list, making the overall traversal quadratic. We can actually get a much faster implementation by factoring this map through the type of functions:

[a] -> [a]

by using functions which add appropriate elements to the beginning of a list in lieu of actual lists. Concatenation of lists becomes composition of functions then, which is constant time. We can then apply our function to the empty list once it is constructed.
inorder :: Tree a -> [a]
inorder t = inorder' t []
  where
    inorder' :: Tree a -> ([a] -> [a])
    inorder' Leaf = id
    inorder' (Branch x l r) = inorder' l . (x:) . inorder' r
     -- NB. (x:) is the function which adds x
     --                   to the beginning of a list.

So to reiterate, from this very discrete programming standpoint, we have that one sort of natural transformations are these polymorphic functions which take one sort of data structure to another, leaving the elements of the structure untouched, and merely permuting, duplicating, or deleting them somehow in a way which is independent of their individual values.

One can imagine from this standpoint many sorts of natural transformations on sorts of combinatorial structures, expressed as functors $\textstyle \mathbf{Set} \to \mathbf{Set}$ (or variations thereof: the category of finite sets whose arrows are just the bijections is a good choice for those who are interested primarily in enumeration). I will leave the details of this approach to enumerative combinatorics for another time, but the keyword if you’re interested is “combinatorial species”.

[pdf version]

Natural transformations 1

Posted in Cale on November 15th, 2009 by Cale – Be the first to comment

I’d like to let a larger group of people in on my series of posts about adjunctions and monads, which itself is designed to let a larger group of people in on this stuff I’d like to say about vector spaces, functional programming, and other areas.

To that end, I’ll push the stuff I’m going to write about adjunctions onto the stack, and do a few posts right now about natural transformations. You should hopefully be able to follow from here if you already are comfortable with the basic definitions of what categories and functors are, but I will be throwing some other topics into the examples for enrichment.

So, to start things off, let’s have a look at what natural transformations are and have a look at a couple examples before we get into what things we can do with them.

Suppose that we have categories $\textstyle \mathcal{C}$ and $\textstyle \mathcal{D}$ and two parallel functors. Our natural transformation $\textstyle \eta: F \to G$ will go between the functors:

$ \xy (-16,0)*+{\mathcal{D}}="D"; (16,0)*+{\mathcal{C}}="C"; {\ar@/^1.5pc/^{F} "C";"D"}="F"; {\ar@/_1.5pc/_{G} "C";"D"}="G"; {\ar@{=>}_{\eta} (0,-5)*{}; (0,5)*{}}; \endxy $

(The reason our arrows in diagrams of natural transformations will go from right to left and and bottom to top is that it will make composition formulas easier to read off later.)

The natural transformation consists of, for each object $\textstyle X \in \mathcal{C}$ , an arrow $\textstyle \eta_X: FX \to GX$ in $\textstyle \mathcal{D}$ . Furthermore, for every arrow $\textstyle a: X \to Y$ in $\textstyle \mathcal{C},$ we have the following commutative square in $\textstyle \mathcal{D}$ :

$ \xymatrix{ FX \ar[r]^{Fa} \ar[d]_{\eta_X} & FY \ar[d]^{\eta_Y} \\ GX \ar[r]^{Ga} & GY \\ } $

That is, $\textstyle Ga \circ \eta_X = \eta_Y \circ Fa.$

A good interpretation of this naturality square in many settings is that if we’re thinking of each $\textstyle FX$ as some sort of structure built on $\textstyle X$ in some way, and $\textstyle Fa$ as acting as $\textstyle a$ does on the bits which came from $\textstyle X$ and leaving the additional structure alone, then the component of the natural transformation $\textstyle \eta_X$ acts on the other half: it rearranges the $\textstyle F$ structure into a $\textstyle G$ structure, leaving the bits which come from $\textstyle X$ alone.

There is an alternate definition from which we might be able to extract some more intuition that I would like to take a quick look at here:

We will define the categorical interval $\textstyle \mathbf{I}$ as the extremely simple category with two objects $\textstyle \{0,1\}$ , and a unique nonidentity arrow $\textstyle u: 0 \to 1$ between them. (This category is also sometimes known as $\textstyle \mathbf{2}.$ )

Suppose that $\textstyle F$ and $\textstyle G$ are functors as before. Then, a homotopy of functors $\textstyle F \to G$ is defined to be a functor $\textstyle H: \mathcal{C} \times \mathbf{I} \to \mathcal{D}$ such that:

$\begin{align*} H(X,0) & = FX \\ H(X,1) & = GX \\ H((a,\mathrm{id}_0): (X,0) \to (Y,0)) & = Fa \\ H((a,\mathrm{id}_1): (X,1) \to (Y,1)) & = Ga \\ \end{align*}$

If we have a functor like this, then for any $\textstyle a: X \to Y$ in $\textstyle \mathcal{C}$ , we have the following diagram of arrows in $\textstyle \mathcal{D}$ :

$\xymatrix{ H(X,0) \ar[dd]_{H(\mathrm{id}_X,u)} \ar[rr]^{H(a,\mathrm{id}_0)} \ar[ddrr]^{H(a,u)} & & H(Y,0) \ar[dd]^{H(\mathrm{id}_Y,u)} \\ \\ H(X,1) \ar[rr]^{H(a,\mathrm{id}_1)} & & H(Y,1)\\ }$

Because the composite of arrows in the product category is defined by $\textstyle (f_1,g_1) \circ (f_2,g_2) = (f_1 \circ f_2, g_1 \circ g_2),$ we have that each of those two triangles commutes, and so the square does as well.

But now if we can define for each $\textstyle X \in \mathcal{C}$ , the arrow $\textstyle \eta_X = H(\mathrm{id}_X,u)$ we can replace things in the above diagram according to the equations we have to get:

$\xymatrix{ FX \ar[dd]_{\eta_X} \ar[rr]^{Fa} \ar[ddrr]^{H(a,u)} & & FY \ar[dd]^{\eta_Y} \\ \\ GX \ar[rr]^{Ga} & & GY\\ }$

So these components $\textstyle \eta_X$ give rise to a natural transformation $\textstyle \eta: F \to G.$

Moreover, if we start with a natural transformation, $\textstyle \eta: F \to G$ , we can define a homotopy of functors using $\textstyle H(\mathrm{id}_X,u) = \eta_X$ , and construct the remainder of the definition of $\textstyle H$ according to the laws it must satisfy. So the two definitions are equivalent.

Those familiar with topology at this point are probably quite happy with this, but for everyone else who is in the dark, the analogy here is to the concept of a homotopy of continuous maps.

In topology, we might have topological spaces $\textstyle \mathcal{C}$ and $\textstyle \mathcal{D}$ (if you don’t know about topological spaces, you can think of subsets of $\textstyle \mathbb{R}^n$ perhaps), and a pair of continuous functions $\textstyle F,G: \mathcal{C} \to \mathcal{D}.$ The notion we’re trying to define is when it’s possible to continuously deform the function $\textstyle F$ into the function $\textstyle G$ . We define a homotopy of continuous maps as a continuous map $\textstyle H: \mathcal{C} \times \mathbf{I} \to \mathcal{D}$ , where this time, our $\textstyle \mathbf{I}$ is the interval of real numbers:

$\mathbf{I} = [0,1] = \{x \in \mathbb{R} : 0 \leq x \leq 1\}$

subject to the conditions that for each point $\textstyle X \in \mathcal{C}$ :

$\begin{align*} H(X,0) & = F(X) \\ H(X,1) & = G(X) \\ \end{align*}$

The way we typically think of this is to consider the second parameter $\textstyle t \in [0,1]$ to be like time. If we pick some point $\textstyle X \in \mathcal{C}$ , then the map $\textstyle H(X,-): [0,1] \to \mathcal{D}$ will trace out a continuous curve in $\textstyle \mathcal{D}$ which goes from $\textstyle F(X)$ at $\textstyle t = 0$ to $\textstyle G(X)$ at $\textstyle t = 1$ . This curve is analogous to our component $\textstyle \eta_X: FX \to GX$ .