Matrices as Tensor Network Diagrams | Hacker News Reader

Matrices as Tensor Network Diagrams

math3ma.com

225 points_Microft33 comments

If I remember correctly, Einstein struggled with Tensors and enlisted his friend Mercel Grossmann to help him develop the Tensor Calculus he needed for the General Theory of Relativity. Einstein was no mathematical slouch, obviously, but it’s nice to know that even the most brilliant sometimes need some help from their friends.

Indeed, the "einstein summation convention" is a slightly more primitive version of this graphical tensor notation.

Slight nit-pick, but matrix multiplication is not exclusively a contraction, but rather a contraction on the tensor product of the two matrices. See the next paragraph for why this is concerning.

I find this notation great for simple applications, but potentially unwieldy for dim > 2. For instance, how would I represent the tensor (or outer) product of two matrices? the inputs would be two circles with two lines attached to each, the result would need to be a single circle with four lines attached. The natural attempt would be something like:

  a    - o -
      /    /
     |    /
     \   |
  ab  ---o---
         |   \
        /    |
       /    /
  b    - o -

But I suspect the above diagram isn't correct because there are no "open" indices at the end of this. Rather, this diagram seems to represent the contraction of a 4D tensor with 2, 2D tensors.

It seems we we would need a way of connecting circles without implying a contraction of a particular index.

Anyone know how to annotate the outer product of two matrices in this diagrammatic convention?

A tensor product of two matrices is just this, with 4 loose ends:

    ---A---
    ---B---

A_ab B_cd = (A⊗B)_acbd. If a,c=1...N then you can think of (ac) as being an index with N^2 possible values, which is what the double line now means... if you like, you may compact it a bit:

    ===(A⊗B)===

But how am I supposed to know that AB is one mathematical object here instead of the 2 separate objects A, B? My point is that there should be a graphical way other than "put them arbitrarily close" to link them together

I prefer your second notation, with the tensor product happening in parenthesis, but it kind of defeats the point of the graphical nature of the notation if we need to explictly write the tensor product I think..

Speaking as someone who uses this tensor notation quite a lot: putting multiple objects into the same diagram is what a tensor product is, and a great thing about the notation is that it reveals that a tensor product of two matrices is not an essential object in itself.

If you wish, you can draw a circle around A and B to "factor out" that part of the diagram as a sub tensor product. Here might be a way to show that matrix multiplication is both "tensor product then contract" and "function composition": https://imgur.com/tcCycYj.png (though I didn't give this gray-circle notation much thought).

Think about this: how is it in a product abcd of plain old numbers am I supposed to see the mathematical object ad without putting them arbitrarily close together? (Well, in standard notation, you do put them close together and write (ad)bc or something.)

The equations satisfied by tensor products are exactly those of drawing things next to each other. Look up Bob Coeckes Kindergarten Quantum Mechanics which was linked elsewhere here.

What you need is two parallel walls where lines can start and end. The rest is all fine.

The computer graphics pioneer Jim Blinn has a nice lecture on tensor diagrams: https://www.youtube.com/watch?v=40TdlWURkS8

https://www.microsoft.com/en-us/research/wp-content/uploads/...

To those interested in machine learning, this idea naturally leads to “deep tensor networks” that are neural networks that can operate on and with high order tensors. I wrote a (non-rigorous) blog post about this: http://outlace.com/TensorNets1.html

excellent post, thank you.

How would one write a cross-product with that?

Using two vectors and the epsilon tensor (Levi-Chivita-symbol), I guess?

Edit: So like this: two circles with one connection each as input, i.e. vectors (a and b), and a tensor with three connections, leaving one, meaning the result will be a vector again.

  a  o
      \
       o -    (-o c)
      /
  b  o

Multiplying with another vector c gives the parallelepipedial product (a x b) c, a scalar (also = det(a,b,c)).

Cool :)

Yeah, and this works for any "algebra" (ie. vector space with a way of multiplying vectors.) The three legged thing is what they call the "structure constants" for the algebra.

Would it make sense/work to do something like this ?

  (a x b )(c x d) =>     ???

  o       o             o   o
   \     /               \ /    
    o - o         =>      o
   /     \               / \
  o       o             o   o

Would the circle in the middle of the cross be a tensor of order 4 then?

Edit: It's been a while since I did that but wouldn't that be the following in sum notation?

  eps_ijk a_j b_k eps_ilm c_l d_m = (new tensor)_jklm a_j b_k c_l d_m

Yes it really is just like lego, you can make all kinds of bizarro shapes.

“Chivita“ is written Civita. Chivita would be pronounced “Kivita”. :-)

Yeah, cross product is the determinant with "one strand bent back."

If you take a 3-regular planar graph and put the determinant/Levi-Civita tensor on each vertex, you get plus-or-minus the number of edge-3-colorings of that graph. The four-color theorem is merely to show this tensor contraction is always non-zero :-) (Nobody's managed to prove it this way, yet.)

Here are some notes showing how to contract two Levi-Civita symbols together graphically: https://imgur.com/HmaLSaB.png

This is in Penrose's 1971 paper ("Applications of negative-dimensional tensors"). He went on to notice that you can do a "puff-up-and-contract" construction to completely get rid of all the Levi-Civita tensors: https://imgur.com/eK9ZCkc.png

From here, he recognized that this sort of tensor network on 3-dimensional space was equivalent to an abstract tensor network on "(-2)-dimensional space", where there is an identity that let him remove all the places the strings cross https://imgur.com/65z0zov.png (This element placed at each edge in (-2)-dimensional space is known as the "second Jones-Wenzl projector for the Temperley-Lieb algebra.")

From a more recent point of view, what he did was find a graphical way to go from an SO(3) tensor network to an SL(2) tensor network (which should be possible since both Lie groups are isomorphic).

Negative-dimensional tensors... now that's wild. Thanks for the sketches, I'll have a look!

> From a more recent point of view, what he did was find a graphical way to go from an SO(3) tensor network to an SL(2) tensor network (which should be possible since both Lie groups are isomorphic).

Locally isomorphic, but not isomorphic: SL(2) is the simply connected double cover Spin(3) of SO(3). As you probably know, the non-simply-connectedness of SO(3) is what's witnessed by Dirac's belt trick (https://en.wikipedia.org/wiki/Plate_trick).

Thanks, that's right. (I had the Lie algebras in mind with that statement. The Lie brackets are placed at the vertices in the construction.)

The other time, during a discussion about Feynman diagrams (https://news.ycombinator.com/item?id=19909542) I mentioned some resources related to tensor diagrams (https://medium.com/@pmigdal/in-the-topic-of-diagrams-i-did-w...). Happy this topic gets more mainstream, and this blog post by Tai-Danae Bradley is pure gold!

Practical things: who want to co-write a library (JS I guess) for drawing such tensor diagrams? I think it has a lot of potential for representing formulae, form Markov Chains, through Quantum Computing to Deep Learning!

What bothers me about this is, all indices are not the same. You could draw a line connecting a 5-dimensional index to a 3-dimensional one. There should be some way of separating incompatible indices. Granted this is less of an issue for physics where virtually every index goes from 0 to 3 inclusive - although some go from 1 to 3. Conventionally, this is dealt with by using Greek letters for 4-vectors and regular letters for 3-vectors.

You put labels on lines. For example the diagram here works like that:

https://en.wikipedia.org/wiki/6-j_symbol

> Granted this is less of an issue for physics where virtually every index goes from 0 to 3 inclusive

These days physicists who do tensor-network analysis and simulations of many-body quantum systems (e.g., MPS in 1D) probably use the diagrams more than relativists, and in those cases the indices can come with arbitrary dimensions.

Normal matrix notation has the same problem. I can write AB even if A is 5x5 and B is 3x3.

I am sad to bring sad tidings but... This is very beautiful, it just puts the burden of the proof on a more abstract setting, which may be more difficult to grasp.

(This is just a comment on the "graphical proofs", they are beautiful but they cannot be "proofs" unless you provide the background).

It's turtles all the way down:

https://graphicallinearalgebra.net/2015/06/09/matrices-diagr...

These are not "graphical proofs" in the sense of pictures that suggest patterns in mathatical relations. This is (or can be) a formal graphical language for (a branch of) mathematics. Like any formal language it's not self evident how or why it works and needs to be rigourously defined.

In many different areas of scientific investigation, purely diagrammatic expressions have begun to be used as mathematical substitutes for the traditional symbolic expressions. These new languages reflect clear operational concepts such as ‘systems’ and ‘processes’, and ‘wires’ are used to represent information flow. Composition is built-in, as the act of connecting wires together. These diagrams are more intuitive, and easier to manipulate, than conventional symbolic models of reasoning.

Examples of areas in which these techniques are being used include logic, for the study of propositions and deductions [43]; physics, for the study of space and spacetime [8, 32]; linguistics, to model the interaction of words within a sentence [21]; knowledge, to represent information and belief revision [22]; and computation, for the study of data and computer programs [1, 10]. These diagrams have been provided with a rigorous underpinning using category theory, a powerful branch of mathematics which relates these diagrammatic theories to algebraic structures. More deeply, this approach can also be applied to the study of diagrammatic theories themselves [12, 33]. As such, it is its own ‘metatheory’. One major goal of the project will be to understand to what extent this can serve as a foundation for mathematics itself, as a replacement for set theory. To work towards this, one goal will be to understand how various mathematical structures can be defined from this perspective, a rich line of enquiry for which some answers are already known, but much more is left to still be discovered. An interesting feature of categorical approaches to foundations is that standard limitative theorems, such as the incompleteness theorem of Godel, are no longer set in stone [7, 39]; instead, they become malleable, and can be directly ¨ controlled by changing the categorical universe in which one works.

Switching to the field of artificial intelligence and automation — perhaps, so it seems, a world away from the abstraction of higher mathematics — the diagrammatic categories themselves have been implemented as the actual language and deduction mechanism of automated reasoning software packages. These tools make it possible to automatically explore the theories formulated in the diagrammatic language. For the case of the abstract mathematical expressions, the package quantomatic, currently in development at the Computing Laboratory at the University of Oxford, performs this function. For the particular case of diagrammatic models of language and meaning, parsers and tools for corpus exploration are currently under development.

The study of each of these ‘diagrammatic theories’, each modelling a separate part of cognitive, physical, or mathematical reality, are currently separate. Our grand vision is to develop a fully integrated framework, in which all of the above can be comprehended and dealt with together. This would be a foundation for mathematics, not in isolation but in direct relation to the cognitive and physical worlds; not only as an exercise in abstract thought, but directly implemented computationally, with tools available for automatic calculation and deduction. The unique perspective given by categorical foundations on Godel-style theorems will allow their relevance to cognition to be rigorously studied. The strong mathematical similarities between the diagrammatic techniques used in these different fields, which have only recently begun to be appreciated, provides a good impetus for this research programme.

Source: An integrated diagrammatic universe for knowledge, language and artificial reasoning. Abramsky & Coecke, Oxford.

http://www.cs.ox.ac.uk/people/bob.coecke/JTFCats.pdf

In what sense do they mean "begun", as in, that this is a new concept? Some of their citations go back to the 60's and 70's. Engineers have been using block diagrams for.. how long? Venn diagrams were invented in 1880 according to Wikipedia. It doesn't strike me that the use of visual languages in mathematics is particularly new.

I think that they mean in this source this /particular/ way of diagrammatic reasoning, as pioneered by Coecke, who literally wrote the book on it (http://www.cambridge.org/gb/pqp), although very similar diagrammatic reasoning has been used for some time in Category Theory through string diagrams (https://en.wikipedia.org/wiki/String_diagram).

I think the approach is different. String diagrams is a small DSL while the above is intended to be more foundational and be used to bootstrap and translate between various specific diagrammatic theories (including String diagrams).

> The study of each of these ‘diagrammatic theories’, each modelling a separate part of cognitive, physical, or mathematical reality, are currently separate. Our grand vision is to develop a fully integrated framework, in which all of the above can be comprehended and dealt with together.

> More deeply, this approach can also be applied to the study of diagrammatic theories themselves [12, 33]. As such, it is its own ‘metatheory’. One major goal of the project will be to understand to what extent this can serve as a foundation for mathematics itself, as a replacement for set theory.

Also, as an ironic side note in relation with the article, some of the diagrammatic theories that have been elaborated by this group include diagrams that contain (and not just represent) matrices. I don't know why I'm commenting in this thread, I don't understand anything in these papers, I just know it describes what I see, i.e. the great universal diagram. Don't you see it ?

here are some pages that might be relevant

https://ncatlab.org/nlab/show/tensor+network https://ncatlab.org/nlab/show/string+diagram

Reply on news.ycombinator.com