Introduction to string diagrams

November 5, 2012 by Qiaochu Yuan

Today I would like to introduce a diagrammatic notation for dealing with tensor products and multilinear maps. The basic idea for this notation appears to be due to Penrose. It has the advantage of both being widely applicable and easier and more intuitive to work with; roughly speaking, computations are performed by topological manipulations on diagrams, revealing the natural notation to use here is 2-dimensional (living in a plane) rather than 1-dimensional (living on a line).

For the sake of accessibility we will restrict our attention to vector spaces. There are category-theoretic things happening in this post but we will not point them out explicitly. We assume familiarity with the notion of tensor product of vector spaces but not much else.

Below the composition of a map $f : a \to b$ with a map $g : b \to c$ will be denoted $f \circ g : a \to c$ (rather than the more typical $g \circ f$ ). This will make it easier to translate between diagrams and non-diagrams. All diagrams were drawn in Paper.

String diagrams

String diagrams for finite-dimensional vector spaces work as follows. To start with, a linear map $f : U \to V$ is represented by a box labeled $f$ with one input string labeled $U$ and one output string labeled $V$ . Composition of linear maps $f : U \to V$ and $g : V \to W$ is given by pairing input and output wires with matching labels.

The tensor product of two linear maps $f : U_1 \to V_1, g : U_2 \to V_2$ is a map $f \otimes g : U_1 \otimes U_2 \to V_1 \otimes V_2$ represented graphically by stacking boxes vertically. Note that $f \otimes g$ has two input wires and two output wires.

The $1$ -dimensional vector space $1$ is not represented by a wire at all, to reflect the fact that it is an identity for tensor product in the sense that there is a natural isomorphism $V \otimes 1 \cong V$ . Thus a vector in a vector space is a morphism $v : 1 \to V$ , which is just a box with no input wire and one output wire, and a linear functional or covector is a morphism $f : V \to 1$ , which is just a box with no output wire and one input wire.

The identity map $\text{id}_V : V \to V$ is represented by a wire with no attached box, to reflect the fact that it is an identity for composition, and the identity map $\text{id}_1 : 1 \to 1$ is not represented by anything at all.

In general, an arbitrary linear map

$\displaystyle f : U_1 \otimes ... \otimes U_n \to V_1 \otimes ... \otimes V_m$

(obtained for example by taking the tensor product of various other maps) is represented by a box labeled $f$ with $n$ input wires labeled $U_1, ... U_n$ and $m$ output wires labeled $V_1, ... V_m$ .

Such maps admit a generalized notion of composition given by pairing only some input and output wires rather than all of them (defined formally by composition after tensoring with a suitable collection of identity morphisms). For example, if $m : A \otimes A \to A$ is a bilinear map on a vector space $A$ , the following is the statement that $m$ is associative:

In 1-dimensional notation, this reads

$\displaystyle (m \otimes \text{id}_A) \circ m = (\text{id}_A \otimes m) \circ m$ .

Implicit in our use of string diagram notation is the interchange law, which asserts that the following diagram is a well-defined map $U_1 \otimes U_2 \to W_1 \otimes W_2$ (in the sense that the two ways of evaluating it using tensor products and compositions produce the same result):

In 1-dimensional notation, this reads

$\displaystyle (f_1 \otimes f_2) \circ (g_1 \otimes g_2) = (f_1 \circ g_1) \otimes (f_2 \circ g_2)$ .

The interchange law should be thought of as a $2$ -dimensional version of associativity. It allows us to “drop generalized parentheses” in the sense that we do not have to specify what order we tensor and compose a family of maps as above.

Symmetry

The tensor product is commutative in a suitable sense, so we should be able to freely change the order of input and output wires. We can do this formally as follows. For any pair $U, V$ of vector spaces there is a distinguished symmetry map

$\displaystyle \gamma_{U, V} : U \otimes V \ni u \otimes v \mapsto v \otimes u \in V \otimes U$

which is represented by unlabeled crossing wires. The symmetry maps obey various axioms which ensure that they behave like crossing wires ought to. The most important axiom is naturality, which asserts that we can slide boxes along symmetries:

In 1-dimensional notation, this reads

$\displaystyle (f \otimes g) \circ \gamma_{U_2, V_2} = \gamma_{U_1, V_1} \circ (g \otimes f)$ .

Note that if we only want to slide one box along a symmetry we can let the other one be an identity.

Strictly speaking, naturality also applies to morphisms drawn with more than one input or output wire, so can look more complicated than the above.

Another axiom obeyed by the symmetry asserts that applying the symmetry twice gives the identity. Topologically it is described by pulling two wires apart. Looking ahead to future posts, we will call this axiom Reidemeister II:

In 1-dimensional notation, this reads $\gamma_{U, V} \circ \gamma_{V, U} = \text{id}_{U \otimes V}$ .

The third axiom we will discuss is sometimes called the braid relation, but following the pattern of the above naming scheme we will call it Reidemeister III. Topologically it is described by pulling the middle wire across a crossing:

In 1-dimensional notation, this reads that

$\displaystyle (\text{id}_U \otimes \gamma_{V, W}) \circ (\gamma_{U, W} \otimes \text{id}_V) \circ (\text{id}_W \otimes \gamma_{U, V})$

is equal to

$\displaystyle (\gamma_{U, V} \otimes \text{id}_W) \circ (\text{id}_V \otimes \gamma_{U, W}) \circ (\gamma_{V, W} \circ \text{id}_U)$ .

In particular, specialized to the case of an $n$ -fold tensor product $V^{\otimes n}$ , Reidemeister II and III are precisely the relations in a well-known presentation of the symmetric group $S_n$ , so that $S_n$ naturally acts on $V^{\otimes n}$ .

The symmetry maps allow string diagrams greater expressive power. For example, if $m : A \otimes A \to A$ is a bilinear map, the following is the statement that $m$ is commutative:

Posted in math.CT | Tagged diagrammatic algebra, MaBloWriMo, monoidal categories | 15 Comments

15 Responses

on January 18, 2017 at 3:02 pm | Reply Armin Reichert

String diagrams have been formally defined first by Günter Hotz in 1965 in his habilitation thesis.

See http://mathoverflow.net/questions/168888/who-invented-diagrammatic-algebra

The thesis (in German) can be download here:

https://www.magentacloud.de/lnk/LiPMlYfh (part 1)

https://www.magentacloud.de/lnk/YivslUWJ (part 2)
on September 1, 2014 at 7:12 am | Reply Hopf algebroids and (quantum) groupoids (Part 1) | Simplicity

[…] diagrams isn’t clear, you can learn about string diagrams in several places on the web, like here or […]
on November 8, 2012 at 2:23 am | Reply home_pw@msn.com

in the symmetry section, consider the first formula. Should the last symbol be V as given, or U? (i.e. typo)?
- on November 8, 2012 at 6:15 pm | Reply Qiaochu Yuan
  
  Yes, it should be $U$ . Fixed.
on November 6, 2012 at 11:16 pm | Reply String diagrams, duality, and trace « Annoying Precision

[…] « Introduction to string diagrams […]
on November 6, 2012 at 7:01 am | Reply Todd Trimble

No mention of Joyal and Street???
- on November 6, 2012 at 1:07 pm | Reply Qiaochu Yuan
  
  I’m not familiar with the history of string diagrams and I didn’t want to say something incorrect about Joyal and Street’s contributions. I also didn’t want to talk too much about category theory until later.
  - on November 6, 2012 at 3:31 pm | Reply Zhen Lin
    
    To the best of my knowledge, the calculus of string diagrams as applied to braided monoidal categories was first formalised by Joyal and Street in their 1991 paper, in which the soundness of the calculus is also proven. But if you are only using string diagrams for, say, the category of finite-dimensional vector spaces, then it is probably not unfair to only mention Penrose.
    
    Penrose’s diagrammatic notation has some other clever features: for example, the metric tensor is written as an upside down U, highlighting its naturality of its use in lowering indices. Even determinants can be expressed reasonably efficiently… that’s all in _Road to Reality_.
  - on November 6, 2012 at 5:26 pm | Reply Todd Trimble
    
    @Zhen: (as an aside, I’m sure you know that Geometry of Tensor Calculus I covers a number of doctrines besides braided monoidal categories). I have to admit that I’ve looked only cursorily at Penrose’s work. Does he prove theorems that place his notation on a rigorous footing? It was my impression that this is precisely a value of Joyal and Street’s work. (Of course, Feynman diagrams were another precursor of string diagrams. It could even be said that Peirce’s existential graphs were yet another precursor.)
  - on November 7, 2012 at 12:58 pm | Reply Zhen Lin
    
    @Todd: If Penrose proved anything, it probably isn’t be in _Road to Reality_. But I’m not sure there’s anything that even needs proving in the context of finite-dimensional vector spaces: all the objects in question can be regarded as arrays of numbers, and the diagram is just a way of keeping track of all the indices and contractions. Of course, maybe there’s some subtlety I’m missing…
  - on November 7, 2012 at 6:15 pm | Reply Todd Trimble
    
    Zhen, I’m not sure I really want to argue about it here, but it seems to me a major point of string diagrams would be the recognition that the meaning of a string diagram, whether in a general monoidal category or just in vector spaces, is invariant under certain types of deformation of string diagrams (e.g., the yanking moves for adjunctions) — that seems to be the whole point which makes their manipulation so effective. And it seems to me that that point is definitely in need of proof, even when restricted to just the vector space case.
    
    But I’m happy to shut up and let Qiaochu keep talking!
on November 6, 2012 at 4:02 am | Reply Rod Carvalho

In the first diagram, shouldn’t it be $g \circ f$ instead of $f \circ g$ ?
- on November 6, 2012 at 6:12 am | Reply Rod Carvalho
  
  Nevermind. You answer this question in:
  
  Below the composition of a map $f : a \to b$ with a map $g : b \to c$ will be denoted $f \circ g : a \to c$ (rather than the more typical $g \circ f$ ). This will make it easier to translate between diagrams and non-diagrams.
on November 6, 2012 at 12:41 am | Reply Zhen Lin

String diagrams are a wonderful tool, and not just for calculations in monoidal categories – minus the braiding part, they work in bicategories too. It’s incredibly helpful when trying to work out proofs involving lots of functors and natural transformations. The triangle identities involving adjunctions take a particularly nice form when presented as string diagrams, which makes working with them a lot easier.
- on November 6, 2012 at 1:06 pm | Reply Qiaochu Yuan
  
  Yes, I might talk about this in a subsequent post (but no jinxes).

Comments RSS

	ZW on The double commutant theo…
	auto on More about the Schrödinger equ…
	Jaromir Kuben on Meditation on the Sylow theore…
	Qiaochu Yuan on Meditation on the Sylow theore…
	Qiaochu Yuan on Some remarks on the infinitude…

Annoying Precision

"A good stock of examples, as large as possible, is indispensable for a thorough understanding of any concept, and when I want to learn something new, I make it my first job to build one." – Paul Halmos