String diagram

String diagrams are a formal graphical language for representing morphisms in monoidal categories, or more generally 2-cells in 2-categories.

When interpreted in the monoidal category of vector spaces and linear maps with the tensor product, string diagrams are called tensor networks or Penrose graphical notation.

History

Günter Hotz gave the first mathematical definition of string diagrams in order to formalise electronic circuits,^[1] but the article remained confidential because of the absence of an English translation. The invention of string diagrams is usually credited to Roger Penrose^[2] with Feynman diagrams also described as a precursor.^[3] They were later characterised as the arrows of free monoidal categories in a seminal article by André Joyal and Ross Street.^[4] While the diagrams in these first articles were hand-drawn, the advent of typesetting software such as LaTeX and PGF/TikZ made the publication of string diagrams more wide-spread.^[5]

The existential graphs of Charles Sanders Peirce are arguably the oldest form of string diagrams, they are interpreted in the monoidal category of finite sets and relations with the Cartesian product.^[6] The lines of identity of Peirce's existential graphs can be axiomatised as a Frobenius algebra, the cuts are unary operators on homsets that axiomatise logical negation. This makes string diagrams a sound and complete two-dimensional deduction system for first-order logic,^[7] invented independently from the one-dimensional syntax of Gottlob Frege's Begriffsschrift.

Definition

The idea is to represent structures of dimension d by structures of dimension 2-d, using Poincaré duality. Thus,

an object is represented by a portion of plane,
a 1-cell $f:A\to B$ is represented by a vertical segment—called a string—separating the plane in two (the right part corresponding to A and the left one to B),
a 2-cell $\alpha :f\Rightarrow g:A\to B$ is represented by an intersection of strings (the strings corresponding to f above the link, the strings corresponding to g below the link).

The parallel composition of 2-cells corresponds to the horizontal juxtaposition of diagrams and the sequential composition to the vertical juxtaposition of diagrams.

Duality between commutative diagrams (on the left hand side) and string diagrams (on the right hand side)

Example

Consider an adjunction $(F,G,\eta ,\varepsilon )$ between two categories ${\mathcal {C}}$ and ${\mathcal {D}}$ where $F:{\mathcal {C}}\leftarrow {\mathcal {D}}$ is left adjoint of $G:{\mathcal {C}}\rightarrow {\mathcal {D}}$ and the natural transformations $\eta :I\rightarrow GF$ and $\varepsilon :FG\rightarrow I$ are respectively the unit and the counit. The string diagrams corresponding to these natural transformations are:

String diagram of the unit

String diagram of the counit

String diagram of the identity

The string corresponding to the identity functor is drawn as a dotted line and can be omitted. The definition of an adjunction requires the following equalities:

{\begin{aligned}(\varepsilon F)\circ F(\eta )&=1_{F}\\G(\varepsilon )\circ (\eta G)&=1_{G}\end{aligned}}

The first one is depicted as

Diagrammatic representation of the equality

(\varepsilon F)\circ F(\eta )=1_{F}

Other diagrammatic languages

Morphisms in monoidal categories can also be drawn as string diagrams ^[8] since a strict monoidal category can be seen as a 2-category with only one object (there will therefore be only one type of planar region) and Mac Lane's strictification theorem states that any monoidal category is monoidally equivalent to a strict one. The graphical language of string diagrams for monoidal categories may be extended to represent expressions in categories with other structure, such as braided monoidal categories, dagger categories,^[9] etc. and is related to geometric presentations for braided monoidal categories^[10] and ribbon categories.^[11] In quantum computing, there are several diagrammatic languages based on string diagrams for reasoning about linear maps between qubits, the most well-known of which is the ZX-calculus.

External links

TheCatsters (2007). String diagrams 1 (streamed video). Youtube. Archived from the original on 2021-12-19.
String diagrams at the nLab

References

^ Hotz, Günter (1965). "Eine Algebraisierung des Syntheseproblems von Schaltkreisen I." Elektronische Informationsverarbeitung und Kybernetik. 1 (3): 185–205.
^ Penrose, Roger (1971). "Applications of negative dimensional tensors". Combinatorial mathematics and its applications. 1: 221–244.
^ Baez, J.; Stay, M. (2011), Coecke, Bob (ed.), "Physics, Topology, Logic and Computation: A Rosetta Stone", New Structures for Physics, Berlin, Heidelberg: Springer, pp. 95–172, doi:10.1007/978-3-642-12821-9_2, ISBN 978-3-642-12821-9, retrieved 2022-11-08
^ Joyal, André; Street, Ross (1991). "The geometry of tensor calculus, I". Advances in mathematics. 88 (1): 55–112.
^ Selinger, Peter (2010), "A survey of graphical languages for monoidal categories", New structures for physics, Springer, pp. 289–355, retrieved 2022-11-08
^ Brady, Geraldine; Trimble, Todd H (2000). "A categorical interpretation of CS Peirce's propositional logic Alpha". Journal of Pure and Applied Algebra. 149 (3): 213–239.
^ Haydon, Nathan; Sobociński, Pawe\l (2020). "Compositional diagrammatic first-order logic". International Conference on Theory and Application of Diagrams. Springer: 402–418.
^ Joyal, André; Street, Ross (1991). "The geometry of tensor calculus, I" (PDF). Advances in Mathematics. 88 (1): 55–112. doi:10.1016/0001-8708(91)90003-P. ISSN 0001-8708.
^ Selinger, P. (2010). "A Survey of Graphical Languages for Monoidal Categories" (PDF). In Bob Coecke (ed.). New Structures for Physics. Lecture Notes in Physics. Vol. 813. Springer Berlin Heidelberg. pp. 289–355. arXiv:0908.3347. Bibcode:2009arXiv0908.3347S. doi:10.1007/978-3-642-12821-9_4. ISBN 978-3-642-12820-2.
^ Joyal, A.; Street, R. (1993). "Braided Tensor Categories". Advances in Mathematics. 102 (1): 20–78. doi:10.1006/aima.1993.1055. ISSN 0001-8708.
^ Shum, Mei Chee (1994-04-11). "Tortile tensor categories". Journal of Pure and Applied Algebra. 93 (1): 57–110. doi:10.1016/0022-4049(92)00039-T. ISSN 0022-4049.

External links

Media related to String diagram at Wikimedia Commons

This category theory-related article is a stub. You can help Wikipedia by expanding it.

[1] Hotz, Günter (1965). "Eine Algebraisierung des Syntheseproblems von Schaltkreisen I." Elektronische Informationsverarbeitung und Kybernetik. 1 (3): 185–205.

[2] Penrose, Roger (1971). "Applications of negative dimensional tensors". Combinatorial mathematics and its applications. 1: 221–244.

[3] Baez, J.; Stay, M. (2011), Coecke, Bob (ed.), "Physics, Topology, Logic and Computation: A Rosetta Stone", New Structures for Physics, Berlin, Heidelberg: Springer, pp. 95–172, doi:10.1007/978-3-642-12821-9_2, ISBN 978-3-642-12821-9, retrieved 2022-11-08

[4] Joyal, André; Street, Ross (1991). "The geometry of tensor calculus, I". Advances in mathematics. 88 (1): 55–112.

[5] Selinger, Peter (2010), "A survey of graphical languages for monoidal categories", New structures for physics, Springer, pp. 289–355, retrieved 2022-11-08

[6] Brady, Geraldine; Trimble, Todd H (2000). "A categorical interpretation of CS Peirce's propositional logic Alpha". Journal of Pure and Applied Algebra. 149 (3): 213–239.

[7] Haydon, Nathan; Sobociński, Pawe\l (2020). "Compositional diagrammatic first-order logic". International Conference on Theory and Application of Diagrams. Springer: 402–418.

[8] Joyal, André; Street, Ross (1991). "The geometry of tensor calculus, I" (PDF). Advances in Mathematics. 88 (1): 55–112. doi:10.1016/0001-8708(91)90003-P. ISSN 0001-8708.

[9] Selinger, P. (2010). "A Survey of Graphical Languages for Monoidal Categories" (PDF). In Bob Coecke (ed.). New Structures for Physics. Lecture Notes in Physics. Vol. 813. Springer Berlin Heidelberg. pp. 289–355. arXiv:0908.3347. Bibcode:2009arXiv0908.3347S. doi:10.1007/978-3-642-12821-9_4. ISBN 978-3-642-12820-2.

[10] Joyal, A.; Street, R. (1993). "Braided Tensor Categories". Advances in Mathematics. 102 (1): 20–78. doi:10.1006/aima.1993.1055. ISSN 0001-8708.

[11] Shum, Mei Chee (1994-04-11). "Tortile tensor categories". Journal of Pure and Applied Algebra. 93 (1): 57–110. doi:10.1016/0022-4049(92)00039-T. ISSN 0022-4049.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]