10 ms·

Graphical Linear Algebra

287 points by guerrilla 6y ago

siraben 6y ago
When I took a course on linear algebra, the professor would introduce the notion of vector spaces and linear transformations first before talking about matrices, and actually one can derive the matrix multiplication algorithm from the specification of how it must correspond with composition of linear transformations. I thought that the algebraic notation is very concise and appropriate for linear algebra. While new notation like this is interesting, I do wonder how useful it is from a pedagogical standpoint for linear algebra. Category theory OTOH is one of the areas of mathematics with diagrams rule over equations because a single diagram can encode so many equations. For excellent introductions to linear algebra I recommend Linear Algebra Done Right[0], which Springer offered for free for a while (it doesn't seem to be anymore though, contact me if you want the PDF). [0] http://linear.axler.net/ http://linear.axler.net/
enriquto 6y ago
It would be nice to have a single-page complete summary of this notation. The whole text is way too verbose and boring (at least the first two chapters).
- guerrilla 6y ago
  There's a paper linked to here which he says contains all the "spoilers": http://arxiv.org/abs/1403.7048 http://arxiv.org/abs/1403.7048 > If you are impatient and want to get to the conclusion quickly, here’s the link to our paper where the basic theory is explained (Spoiler warning!). We will also discuss several applications of graphical linear algebra that have been developed in recent years.
CharlesMerriam2 6y ago
Meh. Sorry. Start with [Essence of Linear Algebra](https://www.youtube.com/playlist?list=PLZHQObOWTQDPD3MizzM2xVFitgF8hE_ab https://www.youtube.com/playlist?list=PLZHQObOWTQDPD3MizzM2x...) by [3 Blue 1 Brown](https://www.youtube.com/channel/UCYO_jab_esuFRV4b17AJtAw https://www.youtube.com/channel/UCYO_jab_esuFRV4b17AJtAw) for an intuitive overview of all the major concepts. While working through a full Linear Algebra course, it is important to develop your own software to do things. That is, some sort of command tool to enter matrices and run operations on them. As you go through a course, you will keep adding operations. You should work on some of the most common tricks, like using 4 by 4 matrices for computer graphics and understanding what a PCA does.
- s1t5 6y ago
  As much as I like 3blue1brown, watching those videos is not a good way to learn. It's maybe a good way to get some intuition about a topic and much closer to the "infotainment" category. A good textbook + solving problems + maybe writing code works much better for actual learning.
- eru 6y ago
  > While working through a full Linear Algebra course, it is important to develop your own software to do things. That is, some sort of command tool to enter matrices and run operations on them. As you go through a course, you will keep adding operations. That's definitely possible, but not everyone approaches linear algebra from such a number oriented perspective. In fact, my linear algebra prof in Uni tried to avoid coordinates (ie numbers) as much as possible. Eg talking about abstract linear transformations instead of emphasising that you can represent them you can represent them as a rectangle of numbers.
spekcular 6y ago
The short version appears to be that the author has managed to replace standard linear algebra notation with an alternative (but mathematically equivalent) graphical notation, which is harder to do computations and write programs in. This submission is the latest in a trend of what I would classify as "math-lite" category theory and Haskell articles that reach the HN front page, which purport to explain something interesting but end up just rehashing standard mathematics in opaque ways. I really wish this would stop. Fortunately (unfortunately?) I've been down this road a few times and know to avoid getting sucked in, but I can easily see a bright, curious person wasting a lot of time before realizing that the content is merely linguistic, not mathematical. Is (for example) category theory a useful organizational tool in certain abstract branches of mathematics? Sure (those branches being, basically, algebraic topology and algebraic geometry). Is it a grand unified theory of math? No, it's just some useful vocabulary. Most mathematicians go their entire lives without writing a paper mentioning categories. Getting excited about category theory is like getting excited about matrix notation – useful, sure, but not where the meat is. I also find any claims that category theory is relevant to the average working programmer to be dubious at best. (And yes, I realize the graphical notation presented in this article is not category theory. I am making a broader point about certain kinds of articles I see, which also applies here.)
- siraben 6y ago
  This graphical notation for linear algebra isn't like the usual diagram notation category theory at all. > Is category theory a useful organizational tool in certain abstract branches of mathematics? Yes. Abstracting math in a very general way lets you explore patterns and a result in category theory (e.g. Yoneda lemma) generalizes immediately to other instances of categories. > I also find any claims that category theory is relevant to the average working programmer to be dubious at best. I would say there is value in knowing some category theory, especially if the programmer is working in a strongly-typed functional language. Knowing what a functor is, what a catamorphism is and so on, can be useful ways to write more declarative code and teach about abstractions in the same way OOP uses Design Patterns to teach programmers about reusuable code.
  - 6y ago
deltron3030 6y ago
Reminds me of petri nets.
- jshholland 6y ago
  Not entirely a coincidence - see this paper (coauthored by the guy behind the blog in the OP): https://dl.acm.org/doi/10.1145/3290338 https://dl.acm.org/doi/10.1145/3290338
  - deltron3030 6y ago
    And coauthored by you obviously :) Thanks a bunch, very interesting. I've stumbled upon petri nets as a state machine alternative when looking for graphical modeling tools for functional programming (I'm a designer learning Elixir). Here's a talk: https://www.youtube.com/watch?v=aWnGPaputGE https://www.youtube.com/watch?v=aWnGPaputGE
edflsafoiewq 6y ago
The usual notation for a linear transformation X' = aX + bY Y' = cX + dY minimizes irrelevant information. But the diagram for one seems to bring it to the fore: a diagram is basically a system of fully parenthesized, unsimplified expressions eg X' = (3X + (2(X+4Y) - 6X)) + Y ... In fact, it contains even more information than that, since it also tells you if, in (X+Y)+(X+Y), you are supposed to compute (X+Y) once and reuse the value or compute it twice.
- tel 6y ago
  Depends on what you mean by relevant information. GLA exposes the many compositional natures of linear transformations. The fact that there is a compact matrix representation is a wonderful treat.
  - edflsafoiewq 6y ago
    Can you be more concrete?
    - tel 6y ago
      A lot of category theory is just about composition, how different structures compose and how compositions of those structures continue to be composable. So in this case, GLA builds the theory of linear transformations from trivial/simple pieces and their various ways of being composed. It also discusses the mechanisms for proof and reduction (you noted how GLA is clear about whether a sub-computation is reused or not, it'll also be clear about how those two choices are equivalent). So it's really not studying "just" linear transformation (which are, in finite cases, summarized by a matrix of numbers/field elements) but also the theory of their construction, manipulation, simplification. It gives you a rich language for talking about how two linear combinations might be related to one another, something that's more challenging to access from a matrix.
      - edflsafoiewq 6y ago
        Well, that wasn't very concrete. How about this: can you give an example of a linear-algebraic fact that is more easily shown by reasoning about these diagrams than by just using the numbers-moving-along-wires interpretation to immediately turn it into regular equations? For example, the only thing I can think of is maybe (AB)^T = B^T A^T.
jovial_cavalier 6y ago
This is not nearly interesting enough to justify the Stephenson-esque asides on "English snobbishness" and bits on if Fibonacci had to apply for a grant for Arabic numerals.
Tainnor 6y ago
Regardless of the usefulness of category theory or not, the author seems to imply that "traditional linear algebra" is about matrices. This is not true. This may be true from an engineering perspective, or maybe if you've studied in the US, but over here, linear algebra starts with fields, vector spaces, homomorphisms. We establish pretty early on that matrices and linear transformations are in essence the same thing (up to choice of basis), and then we go on to prefer coordinate-free proofs. But, of course, we do discuss the computational aspect (i.e. the Gauss algorithm) because this is exactly what makes linear algebra so useful: many questions can be answered extremely efficiently. Whether you want to frame things in the language of category theory or not, is up to anyone, but the "standard mathematical treatment" is quite beautiful and intriguing already (if I want to feel inspired, I open up my copy of Halmos's "Finite Dimensional Vector Spaces", not necessarily the best introduction for someone who is new, but very beautifully written for someone who has already seen linear algebra).
- buddhiajuke 6y ago
  You’re not wrong. OTOH the other day I heard someone in the Netflix doc about Alberto Nisman’s murder that described a terrorist network as a “matrix”. I grumped as card-carrying pedants are duty-bound to, but then realized that if there’s a 1:1 correspondence between graphs and (adjacency, incidence) matrices, then there’s very little loss of meaning in referring to graphs as “matrices”. Maybe in some communication contexts it’s even clearer.
  - uglycoyote 6y ago
    That's funny, I would have just chalked it up to "they are using a different sense of the word matrix", knowing that most dictionaries contain multiple definitions of the same word. But nice work making this mental leap, I have never thought about it! But it's true, you can envision it as a NxN matrix of N terrorists, where the number in cell i,j represent's the strength of the relationship (it's a weighted graph!), and that might actually be useful for something. I don't doubt that "matrix" might actually exist in numeric form in some CIA or military computer somewhere.
mlwhiz 6y ago
Linear algebra is often taught so poorly. So I am happy someone took the time to create such relevant content. Thanks.
ouroboros1 6y ago
This looks interesting! I get the impression there would not be much friction to implement some of these mechanisms in Haskell.
- solomonb 6y ago
  I think it would be a challenge without dependent types.
CodeArtisan 6y ago
There is also http://immersivemath.com/ila/index.html http://immersivemath.com/ila/index.html
adamnemecek 6y ago
I would also invite people to check out Chu spaces (http://chu.stanford.edu/ http://chu.stanford.edu/). They are essentially matrices with closure under norm (meaning you always have an inverse). This puts them on the same side as probability, linear logic, C*-algebra, and constructive mathematics.
ianhorn 6y ago
Diagrammatic notations seem to pop up all over the place, but in my mind they all share a difficulty that interesting complex graphs tend to not be planar (can't be drawn without criss-crossing lines). That makes it hard to organize in a skimmable/glanceable way. I'd love to see what a future with ubiquitous 3D volumetric displays or VR or whatever could do for diagrammatic notations. You might suddenly be able to organize larger diagrams and I wouldn't be surprised if diagrammatic notations became more useful and started popping up more in that hypothetical future.
gosukiwi 6y ago
As a software developer, I remember basically nothing about Linear Algebra from my time at University :( Besides graphics, what are some applications for linear algebra in software?
- categorybooks 6y ago
  I believe you'll find some applications here: https://codingthematrix.com/ https://codingthematrix.com/
  - gosukiwi 6y ago
    Wow, that's exactly what I was asking for :) Thanks!
da39a3ee 6y ago
I would like to read this but I really need a version without the verbiage and humour. I'm really not convinced it's necessary to try to make these things so "accessible".
- guerrilla 6y ago
  Then read the paper that it's based on which is linked to by the blog and my other comments.
  - da39a3ee 6y ago
    Thanks, I didn't mean to offend. Which is the best starting point? Based on the blog post I was hoping to get some introduction by way of familiar concepts such as linear algebra and homomorphism, before confronting applications to theoretical computer science. Anyway, is the best starting point "Diagrammatic Algebra: From Linear to Concurrent Systems" or "The Calculus of Signal Flow Diagrams I: Linear relations on streams" or something else?
rurban 6y ago
I loved the Makelele story in the intro. I hardly remember him, and didn't recognize that Real was so much worse without him. Linalg really is the most underappreciated technique.

287 points by guerrilla 6y ago

When I took a course on linear algebra, the professor would introduce the notion of vector spaces and linear transformations first before talking about matrices, and actually one can derive the matrix multiplication algorithm from the specification of how it must correspond with composition of linear transformations. I thought that the algebraic notation is very concise and appropriate for linear algebra. While new notation like this is interesting, I do wonder how useful it is from a pedagogical standpoint for linear algebra. Category theory OTOH is one of the areas of mathematics with diagrams rule over equations because a single diagram can encode so many equations. For excellent introductions to linear algebra I recommend Linear Algebra Done Right[0], which Springer offered for free for a while (it doesn't seem to be anymore though, contact me if you want the PDF). [0] http://linear.axler.net/ http://linear.axler.net/

enriquto 6y ago

It would be nice to have a single-page complete summary of this notation. The whole text is way too verbose and boring (at least the first two chapters).

guerrilla 6y ago
There's a paper linked to here which he says contains all the "spoilers": http://arxiv.org/abs/1403.7048 http://arxiv.org/abs/1403.7048 > If you are impatient and want to get to the conclusion quickly, here’s the link to our paper where the basic theory is explained (Spoiler warning!). We will also discuss several applications of graphical linear algebra that have been developed in recent years.

CharlesMerriam2 6y ago

Meh. Sorry. Start with [Essence of Linear Algebra](https://www.youtube.com/playlist?list=PLZHQObOWTQDPD3MizzM2xVFitgF8hE_ab https://www.youtube.com/playlist?list=PLZHQObOWTQDPD3MizzM2x...) by [3 Blue 1 Brown](https://www.youtube.com/channel/UCYO_jab_esuFRV4b17AJtAw https://www.youtube.com/channel/UCYO_jab_esuFRV4b17AJtAw) for an intuitive overview of all the major concepts. While working through a full Linear Algebra course, it is important to develop your own software to do things. That is, some sort of command tool to enter matrices and run operations on them. As you go through a course, you will keep adding operations. You should work on some of the most common tricks, like using 4 by 4 matrices for computer graphics and understanding what a PCA does.

s1t5 6y ago
As much as I like 3blue1brown, watching those videos is not a good way to learn. It's maybe a good way to get some intuition about a topic and much closer to the "infotainment" category. A good textbook + solving problems + maybe writing code works much better for actual learning.
eru 6y ago
> While working through a full Linear Algebra course, it is important to develop your own software to do things. That is, some sort of command tool to enter matrices and run operations on them. As you go through a course, you will keep adding operations. That's definitely possible, but not everyone approaches linear algebra from such a number oriented perspective. In fact, my linear algebra prof in Uni tried to avoid coordinates (ie numbers) as much as possible. Eg talking about abstract linear transformations instead of emphasising that you can represent them you can represent them as a rectangle of numbers.

spekcular 6y ago

The short version appears to be that the author has managed to replace standard linear algebra notation with an alternative (but mathematically equivalent) graphical notation, which is harder to do computations and write programs in. This submission is the latest in a trend of what I would classify as "math-lite" category theory and Haskell articles that reach the HN front page, which purport to explain something interesting but end up just rehashing standard mathematics in opaque ways. I really wish this would stop. Fortunately (unfortunately?) I've been down this road a few times and know to avoid getting sucked in, but I can easily see a bright, curious person wasting a lot of time before realizing that the content is merely linguistic, not mathematical. Is (for example) category theory a useful organizational tool in certain abstract branches of mathematics? Sure (those branches being, basically, algebraic topology and algebraic geometry). Is it a grand unified theory of math? No, it's just some useful vocabulary. Most mathematicians go their entire lives without writing a paper mentioning categories. Getting excited about category theory is like getting excited about matrix notation – useful, sure, but not where the meat is. I also find any claims that category theory is relevant to the average working programmer to be dubious at best. (And yes, I realize the graphical notation presented in this article is not category theory. I am making a broader point about certain kinds of articles I see, which also applies here.)

siraben 6y ago
This graphical notation for linear algebra isn't like the usual diagram notation category theory at all. > Is category theory a useful organizational tool in certain abstract branches of mathematics? Yes. Abstracting math in a very general way lets you explore patterns and a result in category theory (e.g. Yoneda lemma) generalizes immediately to other instances of categories. > I also find any claims that category theory is relevant to the average working programmer to be dubious at best. I would say there is value in knowing some category theory, especially if the programmer is working in a strongly-typed functional language. Knowing what a functor is, what a catamorphism is and so on, can be useful ways to write more declarative code and teach about abstractions in the same way OOP uses Design Patterns to teach programmers about reusuable code.
- 6y ago

deltron3030 6y ago

Reminds me of petri nets.

jshholland 6y ago
Not entirely a coincidence - see this paper (coauthored by the guy behind the blog in the OP): https://dl.acm.org/doi/10.1145/3290338 https://dl.acm.org/doi/10.1145/3290338
- deltron3030 6y ago
  And coauthored by you obviously :) Thanks a bunch, very interesting. I've stumbled upon petri nets as a state machine alternative when looking for graphical modeling tools for functional programming (I'm a designer learning Elixir). Here's a talk: https://www.youtube.com/watch?v=aWnGPaputGE https://www.youtube.com/watch?v=aWnGPaputGE

edflsafoiewq 6y ago

The usual notation for a linear transformation X' = aX + bY Y' = cX + dY minimizes irrelevant information. But the diagram for one seems to bring it to the fore: a diagram is basically a system of fully parenthesized, unsimplified expressions eg X' = (3X + (2(X+4Y) - 6X)) + Y ... In fact, it contains even more information than that, since it also tells you if, in (X+Y)+(X+Y), you are supposed to compute (X+Y) once and reuse the value or compute it twice.

tel 6y ago
Depends on what you mean by relevant information. GLA exposes the many compositional natures of linear transformations. The fact that there is a compact matrix representation is a wonderful treat.
- edflsafoiewq 6y ago
  Can you be more concrete?
  - tel 6y ago
    A lot of category theory is just about composition, how different structures compose and how compositions of those structures continue to be composable. So in this case, GLA builds the theory of linear transformations from trivial/simple pieces and their various ways of being composed. It also discusses the mechanisms for proof and reduction (you noted how GLA is clear about whether a sub-computation is reused or not, it'll also be clear about how those two choices are equivalent). So it's really not studying "just" linear transformation (which are, in finite cases, summarized by a matrix of numbers/field elements) but also the theory of their construction, manipulation, simplification. It gives you a rich language for talking about how two linear combinations might be related to one another, something that's more challenging to access from a matrix.
    - edflsafoiewq 6y ago
      Well, that wasn't very concrete. How about this: can you give an example of a linear-algebraic fact that is more easily shown by reasoning about these diagrams than by just using the numbers-moving-along-wires interpretation to immediately turn it into regular equations? For example, the only thing I can think of is maybe (AB)^T = B^T A^T.

jovial_cavalier 6y ago

This is not nearly interesting enough to justify the Stephenson-esque asides on "English snobbishness" and bits on if Fibonacci had to apply for a grant for Arabic numerals.

Tainnor 6y ago

Regardless of the usefulness of category theory or not, the author seems to imply that "traditional linear algebra" is about matrices. This is not true. This may be true from an engineering perspective, or maybe if you've studied in the US, but over here, linear algebra starts with fields, vector spaces, homomorphisms. We establish pretty early on that matrices and linear transformations are in essence the same thing (up to choice of basis), and then we go on to prefer coordinate-free proofs. But, of course, we do discuss the computational aspect (i.e. the Gauss algorithm) because this is exactly what makes linear algebra so useful: many questions can be answered extremely efficiently. Whether you want to frame things in the language of category theory or not, is up to anyone, but the "standard mathematical treatment" is quite beautiful and intriguing already (if I want to feel inspired, I open up my copy of Halmos's "Finite Dimensional Vector Spaces", not necessarily the best introduction for someone who is new, but very beautifully written for someone who has already seen linear algebra).

buddhiajuke 6y ago
You’re not wrong. OTOH the other day I heard someone in the Netflix doc about Alberto Nisman’s murder that described a terrorist network as a “matrix”. I grumped as card-carrying pedants are duty-bound to, but then realized that if there’s a 1:1 correspondence between graphs and (adjacency, incidence) matrices, then there’s very little loss of meaning in referring to graphs as “matrices”. Maybe in some communication contexts it’s even clearer.
- uglycoyote 6y ago
  That's funny, I would have just chalked it up to "they are using a different sense of the word matrix", knowing that most dictionaries contain multiple definitions of the same word. But nice work making this mental leap, I have never thought about it! But it's true, you can envision it as a NxN matrix of N terrorists, where the number in cell i,j represent's the strength of the relationship (it's a weighted graph!), and that might actually be useful for something. I don't doubt that "matrix" might actually exist in numeric form in some CIA or military computer somewhere.

mlwhiz 6y ago

Linear algebra is often taught so poorly. So I am happy someone took the time to create such relevant content. Thanks.

ouroboros1 6y ago

This looks interesting! I get the impression there would not be much friction to implement some of these mechanisms in Haskell.

solomonb 6y ago
I think it would be a challenge without dependent types.

CodeArtisan 6y ago

There is also http://immersivemath.com/ila/index.html http://immersivemath.com/ila/index.html

adamnemecek 6y ago

I would also invite people to check out Chu spaces (http://chu.stanford.edu/ http://chu.stanford.edu/). They are essentially matrices with closure under norm (meaning you always have an inverse). This puts them on the same side as probability, linear logic, C*-algebra, and constructive mathematics.

ianhorn 6y ago

Diagrammatic notations seem to pop up all over the place, but in my mind they all share a difficulty that interesting complex graphs tend to not be planar (can't be drawn without criss-crossing lines). That makes it hard to organize in a skimmable/glanceable way. I'd love to see what a future with ubiquitous 3D volumetric displays or VR or whatever could do for diagrammatic notations. You might suddenly be able to organize larger diagrams and I wouldn't be surprised if diagrammatic notations became more useful and started popping up more in that hypothetical future.

gosukiwi 6y ago

As a software developer, I remember basically nothing about Linear Algebra from my time at University :( Besides graphics, what are some applications for linear algebra in software?

categorybooks 6y ago
I believe you'll find some applications here: https://codingthematrix.com/ https://codingthematrix.com/
- gosukiwi 6y ago
  Wow, that's exactly what I was asking for :) Thanks!

da39a3ee 6y ago

I would like to read this but I really need a version without the verbiage and humour. I'm really not convinced it's necessary to try to make these things so "accessible".

guerrilla 6y ago
Then read the paper that it's based on which is linked to by the blog and my other comments.
- da39a3ee 6y ago
  Thanks, I didn't mean to offend. Which is the best starting point? Based on the blog post I was hoping to get some introduction by way of familiar concepts such as linear algebra and homomorphism, before confronting applications to theoretical computer science. Anyway, is the best starting point "Diagrammatic Algebra: From Linear to Concurrent Systems" or "The Calculus of Signal Flow Diagrams I: Linear relations on streams" or something else?

rurban 6y ago

I loved the Makelele story in the intro. I hardly remember him, and didn't recognize that Real was so much worse without him. Linalg really is the most underappreciated technique.