Feeds:
Posts

## String diagrams, duality, and trace

Previously we introduced string diagrams and saw that they were a convenient way to talk about tensor products, partial compositions of multilinear maps, and symmetries. But string diagrams really prove their use when augmented to talk about duality, which will be described topologically by bending input and output wires. In particular, we will be able to see topologically the sense in which the following four pieces of information are equivalent:

• A linear map $U \to V$,
• A linear map $U \otimes V^{\ast} \to 1$,
• A linear map $V^{\ast} \to U^{\ast}$,
• A linear map $1 \to U^{\ast} \otimes V^{\ast}$.

Using string diagrams we will also give a diagrammatic definition of the trace $\text{tr}(f)$ of an endomorphism $f : V \to V$ of a finite-dimensional vector space, as well as a diagrammatic proof of some of its basic properties.

Below all vector spaces are finite-dimensional and the composition convention from the previous post is still in effect.

Bending wires

Associated to every finite-dimensional vector space $V$ is a pair of special morphisms. The evaluation or pairing map

$\displaystyle \text{ev}_V : V \otimes V^{\ast} \ni v \otimes f \mapsto v \circ f \in 1$

is the natural pairing between $V$ and its dual space (thinking of $v \in V$ as a map $1 \to V$ and thinking of $f \in V^{\ast}$ as a map $V \to 1$). The coevaulation or copairing map

$\displaystyle \text{coev}_V : 1 \ni 1 \mapsto \sum_{i=1}^n e_i^{\ast} \otimes e_i \in V^{\ast} \otimes V$

is less obviously natural ($e_i$ above is a basis of $V$); thinking of $V^{\ast} \otimes V$ as identified with $\text{End}(V)$, it picks out the identity $\text{id}_V$. Evaluation and coevaluation are represented by the following special wires, bent down:

We obtain the evaluation and coevaluation maps for $V^{\ast}$ by symmetry, namely

$\displaystyle \text{ev}_{V^{\ast}} = \gamma_{V^{\ast}, V} \circ \text{ev}_V : V^{\ast} \otimes V \to 1$

and

$\displaystyle \text{coev}_{V^{\ast}} = \text{coev}_V \circ \gamma_{V^{\ast}, V} : 1 \to V \otimes V^{\ast}$

which we will represent by the following special wires, bent up:

Previously we drew directional arrows along the wires in our string diagrams even though these did not appear to provide any extra information. These directional arrows were for compatibility with evaluation and coevaluation, and we now allow them to point left where previously they had only pointed right, which has the following interpretation: an input wire labeled $V$ pointing to the left is equivalent to an input wire labeled $V^{\ast}$ pointing to the right, and similarly an output wire labeled $V$ pointing to the right is equivalent to an output wire labeled $V^{\ast}$ pointing to the left. For example, the following diagram describes a map $f : U \otimes V^{\ast} \to W^{\ast}$:

Just as we have axioms ensuring that the symmetry behaves like crossing wires ought to, we have axioms ensuring that evaluation and coevaluation behave like bending wires ought to, namely the zigzag identities, which allow us to “pull wires straight”:

In non-string diagram notation, this means that

$\displaystyle (\text{coev}_V \otimes \text{id}_{V^{\ast}}) \circ (\text{id}_{V^{\ast}} \otimes \text{ev}_V) = \text{id}_{V^{\ast}}$

and that

$\displaystyle (\text{id}_V \otimes \text{coev}_V) \circ (\text{ev}_V \otimes \text{id}_V) = \text{id}_V$

both of which can be verified explicitly. We will verify the second zigzag identity as follows: letting $e_1, ... e_n$ denote a basis of $V$. If $e_i$ is a basis vector, then the first zigzag transforms $e_i$ as follows:

$\displaystyle e_i \mapsto e_i \otimes (\sum e_j^{\ast} \otimes e_j) \mapsto e_i$.

The first zigzag identity can be verified similarly.

There are two other zigzag identities involving the other evaluation and coevaluation maps which follow from the above zigzag identities applied to $V^{\ast}$. However, they also follow from the zigzag identities applied to $V$ as follows. By naturality of symmetry (applied to $V^{\ast} \otimes V$ and $V^{\ast}$), we have (omitting labels on wires for convenience)

and similarly

and composing these two diagrams and applying Reidemeister III, Reidemeister II, and the definition of the other evaluation and coevaluation maps, we obtain the following sequence of equalities:

which establishes a third zigzag identity. A mirror version of this argument establishes a fourth zigzag identity.

The above argument is a good example of the benefits of string diagram notation, since writing it out in non-string diagram notation is unpleasant and unenlightening, even after omitting subscripts:

$\displaystyle (\text{coev} \otimes \text{id}) \circ (\text{id} \otimes \text{ev})$

is equal to

$\displaystyle (\text{id} \otimes \text{coev}) \circ (\gamma \otimes \text{id}) \circ (\text{id} \otimes \gamma) \circ (\gamma \otimes \text{id}) \circ (\text{id} \otimes \gamma) \circ (\text{ev} \otimes \text{id})$

by the naturality of $\gamma$, which is equal to

$\displaystyle (\text{id} \otimes \text{coev}) \circ (\text{id} \otimes \gamma) \circ (\gamma \otimes \text{id}) \circ (\text{id} \otimes \gamma) \circ (\text{id} \otimes \gamma) \circ (\text{ev} \otimes \text{id})$

by Reidemeister III, which is equal to

$\displaystyle (\text{id} \otimes \text{coev}) \circ (\text{id} \otimes \gamma) \circ (\gamma \otimes \text{id}) \circ (\text{ev} \otimes \text{id})$

by the interchange law and Reidemeister II, which is equal to

$\displaystyle (\text{id} \otimes \text{coev}) \circ (\text{ev} \otimes \text{id})$

by the interchange law and definition, where $\text{coev}$ in this last line refers to $\text{coev}_{V^{\ast}}$. When we use non-string diagram notation we are unnaturally attempting to compress a 2-dimensional argument into 1-dimensional notation.

Duals of maps

Given a linear map $f : U \to V$, we can now bend its input and output wires to obtain the three other equivalent descriptions of $f$ given at the beginning of the post. We can pass back and forth between these perspectives in various ways using evaluation and coevaluation, and any move from one perspective to another can be inverted using evaluation or coevaluation again by the zigzag identities:

In particular, we can define the dual $f^{\ast} : V^{\ast} \to U^{\ast}$ using evaluation and coevaluation, or alternately we can notate it using the diagram describing $f$ but rotated $180^{\circ}$:

In non-string diagram notation, this means

$\displaystyle f^{\ast} = (\text{coev}_U \otimes \text{id}_{V^{\ast}}) \circ (\text{id}_{U^{\ast}} \otimes f \otimes \text{id}_{V^{\ast}}) \circ (\text{id}_{U^{\ast}} \otimes \text{ev}_V)$

and it can be verified explicitly that this reproduces the usual definition of dual as follows: if $e_1, ... e_n$ is a basis of $U$ and $d_1, ... d_m$ is a basis of $V$, then let $e_i^{\ast}, d_j^{\ast}$ denote the corresponding dual bases of $U^{\ast}, V^{\ast}$, and write

$\displaystyle f e_i = \sum_j f_{ij} d_j$.

Then the above diagram transforms $f_j^{\ast} \in V^{\ast}$ as follows:

$d_j^{\ast} \mapsto (\sum_i e_i^{\ast} \otimes e_i) \otimes d_j^{\ast} \mapsto (\sum_i e_i^{\ast} \otimes (\sum_k f_{ik} d_k)) \otimes d_j^{\ast} \mapsto \sum_i f_{ij} e_i^{\ast}$

which is precisely $f^{\ast} d_j^{\ast}$ as desired.

If our goal in constructing the dual was finding a natural way of switching the input and the output, we could also have done so as follows:

This gives us the same dual map. To see this, and to get a feel for duality in general, we will prove a few lemmas showing that we can slide boxes along bent wires. Below we again omit labels on wires for convenience.

Lemma (sliding down on the right):

Proof. By definition and the zigzag identities,

and the conclusion follows. $\Box$

The same argument gives the following.

Lemma (sliding down on the left):

The next lemma requires a slightly longer argument.

Lemma (sliding up on the left):

Proof. By definition, naturality of symmetry, and sliding down on the left,

By a second application of naturality of symmetry and by definition,

and the conclusion follows. $\Box$

Essentially the same argument gives the following.

Lemma (sliding up on the right):

We are now ready to prove the following.

Proposition:

Proof. By sliding up on the left and the zigzag identities,

and the conclusion follows. $\Box$

Trace

Now that we have established some basic properties of the dual, we can define the trace $\text{tr}(f)$ of a linear map $f : V \to V$ to be the following diagram (again omitting labels on wires for convenience):

In other words, the trace is given by “feeding $f$ back to itself.” Note that it has no input or output wires and is therefore a morphism $1 \to 1$, hence a scalar. In non-string diagram notation, this means that

$\displaystyle \text{tr}(f) = \text{coev}_{V^{\ast}} \circ (f \otimes \text{id}_{V^{\ast}}) \otimes \text{ev}_V$.

If $e_1, ... e_n$ is a basis for $V$ and $f e_i = \sum_j f_{ij} e_j$, then we compute that the above diagram transforms $1 \in 1$ as follows:

$\displaystyle 1 \mapsto \sum_i e_i \otimes e_i^{\ast} \mapsto \sum_i (\sum_j f_{ij} e_j) \otimes e_i^{\ast} \mapsto \sum_i f_{ii}$.

This reproduces the usual coordinate-dependent definition of the trace. Note, however, that the diagrammatic definition is automatically independent of a choice of basis, since both $\text{ev}_V$ and $\text{coev}_V$ are defined independent of a choice of basis.

We now give some diagrammatic proofs (in particular, coordinate-free) of two basic properties of the trace.

Theorem: $\text{tr}(f \circ g) = \text{tr}(g \circ f)$.

Proof. By sliding down on the right and sliding up on the left, we have

and the conclusion follows. Note that $f$ and $g$ need not both be endomorphisms of a vector space as long as $f \circ g$ is. $\Box$

The same proof shows quite vividly that the trace of a composite of morphisms is invariant under cyclic permutation.

Theorem: $\text{tr}(f) = \text{tr}(f^{\ast})$.

Proof. By either sliding up on the right or sliding down on the left, $\text{tr}(f^{\ast})$ is

so we are also trying to show that the other possible way of feeding $f$ back to itself also reproduces the trace. By definition, by naturality of the symmetry, and by definition again,

and the conclusion follows. $\Box$