11 ms·

A Programmer’s Intuition for Matrix Multiplication

299 points by sebg 6y ago

activatedgeek 6y ago
I'd prefer stating that matrices actually don't mean anything in isolation. They are simply representations of linear maps. What happens to the elements of a matrix before the elements are formed is irrelevant to the matrix itself. ..And to be clear, I am not a purist.
- WJW 6y ago
  Purist test: aren't vectors just Nx1 matrices? Joking aside, matrices are linear maps in the context of multiplication. They can absolutely have meanings assigned outside the usual "when multiplied by a vector" type of calculations. For example the "adjacency matrix" representation of a graph is very often never multiplied by a vector even in academic algorithm descriptions. YMMV if you call it a (lookup) table in that context but the term "matrix" seems fairly well established there.
  - bonoboTP 6y ago
    You can do many linear algebra operations on the adjacency matrix. It's a proper matrix, in the full sense, not just a table of numbers.
  - andi999 6y ago
    And covectors 1xN matrices?
  - deleted 6y ago
    [deleted]
  - michelpp 6y ago
    > They can absolutely have meanings assigned outside the usual "when multiplied by a vector" type of calculations. For example the "adjacency matrix" representation of a graph is very often never multiplied by a vector even in academic algorithm descriptions. Not disputing your basic point, but I'm not sure "very often never" is entirely accurate. In the GraphBLAS API vector/matrix and matrix/vector multiplication is key for almost all algorithms that depend on breadth first search, this is because matrix/vector multiplication is a single step in a BFS which is the core operation of the GraphBLAS. The vector is typically used to hold the current frontier (and mask). See the "Shortest Path Lengths" example here: https://github.com/michelp/pygraphblas/blob/master/pygraphblas/demo/Introduction-to-GraphBLAS-with-Python.ipynb https://github.com/michelp/pygraphblas/blob/master/pygraphbl... (disclosure, I am the pygraphblas author). > Purist test: aren't vectors just Nx1 matrices? I like it. :) As an interesting point, the GraphBLAS defines both Matrix and Vector types, but internally in the SuiteSparse implementation, they are all just unified into one type and yes, vectors are Nx1 or 1xN.
    - WJW 6y ago
      Wow thanks for that example. I don't think I've seen that trick before; now I want do do more with graphs again.
      - thechao 6y ago
        I implemented flood fill for Adobe as an adapter on top of BFS (from the BGL), which was, itself, an adapter on top of BLAS (written in FORTRAN). It was somewhat faster than the handcoded assembly BFS they were using at the time. The compile times were killer, though.
  - blackbear_ 6y ago
    > the "adjacency matrix" representation of a graph is very often never multiplied by a vector even in academic algorithm descriptions. Not true. There is a whole field (graph signal processing) that studies graphs in terms of their description in matrix form (adjacency, connectivity and more). For example, you can find connected components by looking at the eigenvectors of a certain matrix.
  - Joker_vD 6y ago
    Yes, they pretty much are unless you're in the business of linear codes—then they're actually 1xN matrices. A pretty annoying convention for someone coming in from the general algebra: takes a time to stop mentally transposing everything.
  - pmiller2 6y ago
    > For example the "adjacency matrix" representation of a graph is very often never multiplied by a vector even in academic algorithm descriptions. Unless you're doing spectral graph theory, which looks at properties of the eigenvalues and eigenvectors of the graph's adjacency matrix. Even then, you don't usually multiply the adjacency matrix by a vector explicitly.
    - WJW 6y ago
      Today I learned! I'm fairly familiar with "regular" spectral analysis techniques, ie FFTs and DCTs, with some CWT waveletty goodness thrown in here and there but I never heard about spectral graph analysis. That's what you get for staying in EE land too long I guess.
      - qppo 6y ago
        Fourier & Friends are excellent analytical tools for the nature of patterns, regardless of where they occur! In EE-land we think too much about real and complex numbers, where Fourier analysis is more concrete. But spectral graph theory makes a lot of sense when you think of Fourier analysis as a way of decomposing patterns into their constituent parts, it just looks a bit funny when those patterns aren't numbers.
        pmiller2 6y ago
        Indeed. By using tools of linear algebra on the adjacency matrices of a graph, you can tell a lot about the structure of the graph. For instance, if A is the adjacency matrix of a graph G, with n vertices (we say 'vertices' in the math department almost exclusively -- rarely do we say 'nodes'), and k edges, denoting the trace of A by Tr(A), we can find the number of triangles in A by computing Tr(A^3)/6. We can also tell if G is connected by computing A^n. [0] OTOH, the spectrum doesn't tell you nearly everything you'd want to know about a graph. There are many examples of non-isomorphic graphs that are nonetheless cospectral. For instance, one of my professors from grad school wrote a landmark paper in spectral graph theory in 1973, showing that almost all trees are cospectral. [1] --- [0]: Of course, you'd probably never actually do this, because it's horribly inefficient, but here's how it goes. First, you prove easily by induction that A^c_{i,j} is the number of paths of length c starting at vertex i and ending at vertex j. With that in mind, we see that if there is a row of all nonzero numbers in any matrix A^c for c <= n, then G is connected. With a little more work, you can even extract all the connected components of G, by looking at submatrices of A^c. [1]: Unsurprisingly, the paper is titled "Almost all trees are cospectral". See: https://www.semanticscholar.org/paper/Almost-all-trees-are-cospectral-Schwenk/dc8911f3ebd968a107cdd04379245263994c0e86#paper-header https://www.semanticscholar.org/paper/Almost-all-trees-are-c...
  - scubbo 6y ago
    > aren't vectors just Nx1 matrices? It's been a while since I formally studied maths, but - can you describe a situation in which this is _not_ true? (modulo transposition)
    - dan-robertson 6y ago
      Well if you think of matrices as linear maps then saying a vector is just an Nx1 matrix is like saying that a vector is just a linear map from a vector space of dimension 1 to a vector space of dimension N. It isn’t really a very useful thing to say
      - tomjakubowski 6y ago
        Sure it's useful, if not earth-shattering - another way of saying it is that a vector maps scalars to vectors on the same line.
    - crdrost 6y ago
      So, I would say that there is a canonical isomorphism between them but that they are not quite the same. So, to take a step back, I'd say that a covector is a linear function from a vector input to a scalar output (those terms themselves being somewhat fungible, the space of "vectors" needs to probably form a module over the "scalars" which must themselves be a ring—the issue is that I would as a physicist include scalar fields but you can have two nonzero fields multiply to give a zero field, so they do not obey the field axioms). Then I would say that an [m n]-tensor is technically a multilinear function from m covectors and n vectors to a scalar. This means that a [0 1]-tensor is really exactly a covector, but a [1 0]-tensor is not really exactly a vector. One can manifestly be constructed from any vector v (take any covector c and produce the scalar c(v)) and we generally have some criteria that I forget which ensures that this is not just an injection but also a bijection implying some inverse, so that these [1 0] "co-covectors" are indeed isomorphic to the vectors. And then of course this becomes much easier in a metric space where we identify a canonical bijection between vectors and covectors called the "metric", this gives a much more direct way by which co-covectors are isomorphic to vectors. Hopefully that all makes sense. The situations in which this is not true are non-metric spaces where linear maps from (linear maps from vectors to scalars) to scalars are just a subset of the "apply to this vector" instances, but other linear maps are maybe also included. Then there is a more dramatic statement which I think requires the space to be Hausdorff-paracompact or something, which is the idea that of course we have the outer product which naturally combines an [a b]-tensor and a [c d] tensor into an [a+c, b+d]-tensor ("take these vectors and covectors, give them to the first tensor, take those vectors and covectors, give them to the second tensor, then take the two scalar outputs and multiply them together), and we claim that actually an [m n]-tensor can always be realized as a finite sum of outer products of m [1 0]-tensors with n [0 1]-tensors, which allows you to do arbitrary index contractions in a geometric way.
  - dnautics 6y ago
    > Purist test The short answer is. Yes, but if your PL treats it that way you will wind up in trouble [0]. The long answer is: https://www.youtube.com/watch?v=C2RO34b_oPM https://www.youtube.com/watch?v=C2RO34b_oPM (but seriously take the time to watch this, it's fantastic). [0] Separately C- and often C-derived languages/frameworks like numpy also treat them as 1xN matrices, but that's a nearly tabs-vs-spaces level religious war, with actual consequences. I think a lot of people got confused when translating andrew ng's early octave-based ML coursera course (Nx1) to python (1xN), and also in the back and forth between math ML papers which use Nx1 and python.
    - tomjakubowski 6y ago
      Besides needing to change the order of multiplication (y = xM vs y = Mx) and use the right transposition of the matrix, do any other actual consequences come from the choice of "row vector" vs "column vector"?
      - dnautics 6y ago
        Mathematically speaking, no. They are isomorphic duals. But ergonomics are important to prevent errors. I personally think Matrix-in-front is nice because it evokes the idea that the matrix is a function acting on the vector. In the real world, When you start doing matrix-vector, if you aren't careful with row-major vs column-major storage you can introduce performance regressions. Let's say the architecture can do 256 bit memory move into 4xf64 mmx registers, you have to think carefully about what is going where before proceeding. Some architectures might be able to do an arbitrary stride so that those f64s can be nonadjacent in a simultaneous move. I suspect not handling this correctly is part of what holds back really good fp8, fp16 performance, and I suspect for example the TPUs struggle with this. Of course optimizing for matrix-vector can be different for optimizing for matrix-matrix, since the column vs row memory access preference for the front matrix is exactly the opposite of the back matrix.
    - jpeloquin 6y ago
      > numpy also treat them [vectors] as 1xN matrices I may be misunderstanding something, but in numpy at least a vector, a 1×N array ("row vector"), and a N×1 array ("column vector") behave differently. vec = numpy.array([1,2,3]) assert vec.shape == (3,) assert vec.ndim == 1 row = np.array([[1,2,3]]) assert row.shape == (1,3) assert row.ndim == 2 col = np.array([[1], [2], [3]]) assert col.shape == (3,1) assert col.ndim == 2 And a vector, unlike a 1×N or N×1 array, can be multiplied to either side of any matrix with compatible cardinality: assert all(vec @ numpy.eye(3) == numpy.array([1, 2, 3])) assert all(numpy.eye(3) @ vec == numpy.array([1, 2, 3])) Matlab / Octave, in contrast, forces the user to pick a 1×N or N×1 matrix to represent a vector. Its arrays are always ≥ 2D. So you're probably still right that people get confused translating this to Python. Just wanted to clarify the numpy side of things. The JuliaCon talk you linked does a great job of explaining what different fields mean by "vector"; thanks for linking it.
  - ducttapecrown 6y ago
    Vectors are Nx1 matrices only once you choose an ordered basis!
  - activatedgeek 6y ago
    I think if in any context one uses the usual matrix algebra, it is the same linear map, just in a more abstract setting. If you tell me storing a lookup table is matrix, I think that is sort of out of context. But then again, I could be labelled a purist here, and I'm trying really hard to not fall into the trap.
  - tobmlt 6y ago
    Along with what others have mentioned, another application of adjacency matrix multiplication is in doing discrete calculus on meshes. Pushing one forms to two forms via exterior differentiation, for example. The chief operation is a matrix multiplication with said adjacency matrix.
  - alentist 6y ago
    The nth power of an adjacency matrix yields the number of length-n walks from any vertex to any other vertex.
- d_tr 6y ago
  Agreed. I think that the distinction between the objects and their possible representations should be made clear from the beginning, simply because it will make things easier to understand. IMO, just a couple of chapters from an introductory pure mathematics book is actually the most "to the point" place to start even for people who are not huge fans of math. Just the precise definition of a vector space over a field, a linear operator, a vector basis, the derivation of matrix elements, the usual related examples and some "gymnastics" on paper can make stuff "click" and be a great start for any intended application.
adamnemecek 6y ago
Matrix multiplication is like convolution.
- activatedgeek 6y ago
  To be sure there isn't a perspective here that I may be unaware of, is this a reference to circulant matrices, which bear the Toeplitz sparsity structure?
  - jacobolus 6y ago
    You might find something interesting in https://cr.yp.to/lineartime/multapps-20080515.pdf https://cr.yp.to/lineartime/multapps-20080515.pdf
- salty_biscuits 6y ago
  Maybe convolution on a discrete basis can be represented as a matrix multiplication with a circulant matrix?
zests 6y ago
Matrices are a fun way to stretch the mind. They are easy to grasp yet very dissimilar to numbers. Sometimes they can be used to represent numbers and we can use our matrix intuition to answer questions about regular numbers. You can define functions on matrices just like you define them on numbers. Multiplication is a function. The determinant is a function. You can even take derivatives of these functions. The derivative of the determinant function is written in terms of the trace of the matrix. Yet another matrix function. Who would have guessed that the derivative and trace are related in this way? There's really a lot of depth here. https://en.wikipedia.org/wiki/Jacobi%27s_formula https://en.wikipedia.org/wiki/Jacobi%27s_formula
- _Microft 6y ago
  Don't forget the matrix exponential which might certainly blow the mind of a lot of people here. Matrices as exponent - who would have thought that possible! https://en.wikipedia.org/wiki/Matrix_exponential https://en.wikipedia.org/wiki/Matrix_exponential
  - zests 6y ago
    det(e^A) = e^(tr(A)) Pure magic.
hchasestevens 6y ago
I've always found the bipartite graph conceptualization of matrix multiplication the most intuitive, and especially so if you're familiar with neural networks: https://www.math3ma.com/blog/matrices-probability-graphs https://www.math3ma.com/blog/matrices-probability-graphs
- crdrost 6y ago
  That is genuinely a really fun way to look at it, thank you for linking this! Especially this fits nicely with Markov matrices where you have N input nodes and N output nodes and the sum of all of the probabilities coming out of one of the nodes needs to equal 1. What I might find a little more difficult to teach to people through this lens is the phenomenon of eigenvectors, but I suppose that's to be expected—nothing will work well for all purposes.
  - layoutIfNeeded 6y ago
    >What I might find a little more difficult to teach to people through this lens is the phenomenon of eigenvectors Why? Eigenvectors are simply inputs to the network where the output keeps its shape, that is, at most it gets rescaled, as if you had applied a uniform gain to the components, but otherwise it will be the same as the input.
    - tonyarkles 6y ago
      Oh. Oh my. I have studied linear algebra theory some. I have used it a ton. I have used eigenvectors to solve problems. I have never grokked them. This description changed that. Thank you!
    - crdrost 6y ago
      So for example let me ask for your knee-jerk opinions based on this idea: - does a matrix have the same left-eigenvectors as its right-eigenvectors? - what is the relationship between the left-eigenvalues and right-eigenvalues? - is there always an eigenvector? when is there a complete set? how do you generalize your notion of eigenvectors so that matrices always have a complete set of them? I am not sure any of these are intuitive here.
shoo 6y ago
In some applications, e.g. modelling something defined by PDE, you might need to solve a very large linear system of equations Ax=b, where the vector b has 100,000,000 elements, and A is a 100,000,000 by 100,000,000 element matrix. So for a naive dense matrix representation of A using 1 byte per entry you'd need around 9 petabytes of storage. In practise, for many interesting systems of equations that encode "local" properties, A will be a sparse matrix where the overwhelming majority of matrix entries are zero. There are various sparse matrix formats designed to avoid storing zeroes: the simplest is COO where you store triples of the form (i, j, A_ij) for all nonzero entries A_ij of A. More efficient formats are CSR or CSC ( compressed sparse row & column respectively) that use even less memory by avoiding storing repeated indices where there are runs of nonzero elements. To solve one of these huge linear systems Ax = b , we hardly ever want [1] to go to the expense of computing and storing an explicit matrix representation of the inverse A^{-1} . Instead, we merely need to have some function f that is able to map an input vector b to some output vector f(b)=x that happens to satisfy Ax=b . If the matrix A has sufficiently nice properties [2] we can use an efficient iterative method such as the conjugate gradient method to map the input vector b to an output vector x by solving Ax=b. To evaluate the conjugate gradient method, we don't need to necessarily have an explicit dense or sparse representation of the matrix A, we merely need a function that encodes how A acts on a vector by matrix multiplication. E.g. some function g that maps an input vector x to the output vector g(x) = Ax. So if we've got some appropriately defined conjugate gradient method algorithm cg(g, b), we can define the function f(b) := cg(g, b) Calling f(b) will return x that satisfies g(x) = b, i.e. f is the inverse of g. So now we're expressing linear algebra without having any explicit matrices anywhere: but our functions g and f are of course both linear operators that encode the action of matrix multiplication by A and A^{-1} respectively. [1] Why not? It's a lot more effort to compute A^{-1} which could be used to evaluate A^{-1}b for any given b, but often we only want to know A^{-1}b for a specific b. Also, if the matrix A encodes some local property of a physical system , then A^{-1} will encode a global property -- so it will need to be a dense matrix. [2] Sufficiently nice properties: if it's symmetric positive definite, which arises naturally in a bunch of situations. See eg https://en.m.wikipedia.org/wiki/Conjugate_gradient_method https://en.m.wikipedia.org/wiki/Conjugate_gradient_method
- unnouinceput 6y ago
notsuoh 6y ago
This comes up occasionally. I don't find it to be particularly helpful, even though I do think betterexplained has been a strong source of gaining intuition into various subjects. Recognizing though that method of understanding something is pretty personal, I will say that what really helped me refresh was the 3Blue1Brown Essence of Linear Algebra series on Youtube. If you're trying to better grasp the subject, do yourself a favor and check out those videos. https://www.3blue1brown.com/essence-of-linear-algebra-page/ https://www.3blue1brown.com/essence-of-linear-algebra-page/
- Yajirobe 6y ago
  Everyone's seen/knows them already
  - adenadel 6y ago
    Well, even if "everyone" knows it, at some point you have to come across it for the first time. https://xkcd.com/1053/ https://xkcd.com/1053/
    - commandlinefan 6y ago
      Everyone's seen that XKCD already.
      - coldtea 6y ago
        https://xkcd.com/1053/ https://xkcd.com/1053/
        bryanrasmussen 6y ago
        I'm thinking now we go here https://xkcd.com/1270/ https://xkcd.com/1270/
  - notsuoh 6y ago
    Perhaps not the people who have not seen the OP’s link?
justjonathan 6y ago
I wholehearted endorse 3B1B, The linear algebra series is excellent, the rest of his work is too!
OneGuy123 6y ago
If we're talking about 3D rendering then a matrix multiplication with a vector are just projections: A 3x3 matrix that transforms a vector is nothing else than that vector being projected onto the 3 axis which are inside the 3x3 matrix. This is very easy to see visually. A matrix times matrix multiplication (eg 3x3 times 3x3) is just projecting the axis of one matrix onto the other: expressing the coordinate system in terms of a different coordinate system. The 4x3 (or 4x4) matrix is needed for translation and 3d projection for a 3d triangle onto a 2d plane (screen pixels). For translation: it's just a hack since if you write it out it's a nice and a fast hack to simulate "movement". Then for projection you just hack the numbers in the matrix in such a way that you shrink things further apart from the origin. TLDR: for 3d graphics matrices are used because you can hack them to represent any kind of a transformation. The reason they are used is because graphics cards are fast at performing dot products. Plus matrix multiplication doesn't require trigonometry or division so it doesn't require the slower transcendental GPU instructions (sin, cos,...). For other uses their interpretations is different. I always hated the dull mathematic definition of "a matrix represents a linear map" because what the matrix actually represents is completely context dependent.
- d_tr 6y ago
  > I always hated the dull mathematic definition of "a matrix represents a linear map" because what the matrix actually represents is completely context dependent. The projection and translation matrices you mentioned represent restricted sets of linear maps in some vector space, but the meaning of the restriction is also captured in other mathematical structures. See affine spaces and projective spaces.
- Koshkin 6y ago
  Sure - remember those noisy dot matrix printers?..
- markisus 6y ago
  The projection viewpoint for a rotation matrix using dot products is totally valid, but I think the column viewpoint is more intuitive. A 3x3 matrix can be viewed as something that acts on the standard unit basis vectors. The action on the standard unit basis vectors can be read out by looking at the columns. (A matrix times the ith standard basis vector is just the ith column.) Since the transform is linear, all the other points in space are carried along with the action as well. This is the "linear map" viewpoint of a rotation matrix. I show an example here https://biro.ai/we-learned-the-wrong-way-to-matrix-multiply/ https://biro.ai/we-learned-the-wrong-way-to-matrix-multiply/ where this viewpoint lets you instantly see what a rotation matrix does by looking at the columns.
Exuma 6y ago
OMG Thank you! I'm going through tons of linear algebra for a ML algorithm I need to understand and matrix multiplication is ... weird to say the least.
- dr_zoidberg 6y ago
  I strongly recommend 3blue1brown's intro to linear algebra[0] for quick intuitions, followed by Gilbert Strangs MIT Open Course[1][2] for (much) deeper detail. Strang is a genius, but Sanderson's graphics and intuitions can be helpful early on. [0] https://www.youtube.com/watch?v=fNk_zzaMoSs&list=PLZHQObOWTQDPD3MizzM2xVFitgF8hE_ab https://www.youtube.com/watch?v=fNk_zzaMoSs&list=PLZHQObOWTQ... [1] https://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-spring-2010/ https://ocw.mit.edu/courses/mathematics/18-06-linear-algebra... [2] https://www.youtube.com/playlist?list=PL49CF3715CB9EF31D https://www.youtube.com/playlist?list=PL49CF3715CB9EF31D
  - Exuma 6y ago
    thanks!! I skimmed Strangs video just now and it looks super good, what a great suggestion!
deleted 6y ago
[deleted]
Tycho 6y ago
What is some good intuition around matrix inverses?
- 10000truths 6y ago
  An inverse function?
- joppy 6y ago
  The matrix inverse “undoes whatever the matrix did” is pretty much the most straightforward interpretation, if you’re thinking of a matrix as performing some kind of rotation/shear/scaling of space. There are some other interpretations, for example if you think of a linear system Ax=b as a kind of “checking machine” (does x satisfy Ax=b? Yes/no, try again), then the inverse of A can produce solutions, since x=(A inverse)b.
da39a3ee 6y ago
> However, sometimes the matrix being operated on is not a linear operation, but a set of vectors or data points. In Jeremy Kun's book [1] he argues that in fact data matrices _can_ be viewed as linear transformations. See e.g. section 10.9 on the SVD > That is, we’re saying the input is R3 and the basis vectors are people:... > By representing the ratings this way, we’re imposing the hypothesis that the _process_ of rating movies is linear in nature. ... [1] https://pimbook.org/ https://pimbook.org/
rademacher 6y ago
I was expecting this to be more about writing fast matrix multiplies. Surprisingly, it ends up being a lot more than just a triple loop and there's a reason that everyone uses existing libraries like OpenBLAS and MKL [1]. [1] https://www.cs.utexas.edu/users/flame/laff/pfhp/ https://www.cs.utexas.edu/users/flame/laff/pfhp/
Waterluvian 6y ago
Does anyone mind suggesting a solid intro to matrices in the context of what they are and how the affine transformations work? I know of these concepts but I think it's time to learn.
julian_adams 6y ago
Can you write up a physical intuition for the usage of matrix?
- Koshkin 6y ago
  A rotation in space by an angle can be written as a matrix.
siraben 6y ago
When I took a course in linear algebra, we learned about linear transformations and vector spaces in the abstract first. Then when we got to matrices it was viewed as a way to represent linear transformations. Also it led to a natural derivation for matrix multiplication.
- siraben 6y ago
  If anyone is curious I've uploaded the half-page derivation found in Chapter 3 of Linear Algebra Done Right here[0]. [0] https://imgur.com/a/BTKMWU2 https://imgur.com/a/BTKMWU2
crb002 6y ago
Matrix vector multiply takes an n string and maps it to a k string via a matrix automata. Matrix matrix multiply maps p strings instead of one. We should be parsing on a GPU. https://en.wikipedia.org/wiki/CYK_algorithm https://en.wikipedia.org/wiki/CYK_algorithm

299 points by sebg 6y ago

I'd prefer stating that matrices actually don't mean anything in isolation. They are simply representations of linear maps. What happens to the elements of a matrix before the elements are formed is irrelevant to the matrix itself. ..And to be clear, I am not a purist.

WJW 6y ago
Purist test: aren't vectors just Nx1 matrices? Joking aside, matrices are linear maps in the context of multiplication. They can absolutely have meanings assigned outside the usual "when multiplied by a vector" type of calculations. For example the "adjacency matrix" representation of a graph is very often never multiplied by a vector even in academic algorithm descriptions. YMMV if you call it a (lookup) table in that context but the term "matrix" seems fairly well established there.
- bonoboTP 6y ago
  You can do many linear algebra operations on the adjacency matrix. It's a proper matrix, in the full sense, not just a table of numbers.
- andi999 6y ago
  And covectors 1xN matrices?
- deleted 6y ago
  [deleted]
- michelpp 6y ago
  > They can absolutely have meanings assigned outside the usual "when multiplied by a vector" type of calculations. For example the "adjacency matrix" representation of a graph is very often never multiplied by a vector even in academic algorithm descriptions. Not disputing your basic point, but I'm not sure "very often never" is entirely accurate. In the GraphBLAS API vector/matrix and matrix/vector multiplication is key for almost all algorithms that depend on breadth first search, this is because matrix/vector multiplication is a single step in a BFS which is the core operation of the GraphBLAS. The vector is typically used to hold the current frontier (and mask). See the "Shortest Path Lengths" example here: https://github.com/michelp/pygraphblas/blob/master/pygraphblas/demo/Introduction-to-GraphBLAS-with-Python.ipynb https://github.com/michelp/pygraphblas/blob/master/pygraphbl... (disclosure, I am the pygraphblas author). > Purist test: aren't vectors just Nx1 matrices? I like it. :) As an interesting point, the GraphBLAS defines both Matrix and Vector types, but internally in the SuiteSparse implementation, they are all just unified into one type and yes, vectors are Nx1 or 1xN.
  - WJW 6y ago
    Wow thanks for that example. I don't think I've seen that trick before; now I want do do more with graphs again.
    - thechao 6y ago
      I implemented flood fill for Adobe as an adapter on top of BFS (from the BGL), which was, itself, an adapter on top of BLAS (written in FORTRAN). It was somewhat faster than the handcoded assembly BFS they were using at the time. The compile times were killer, though.
- blackbear_ 6y ago
  > the "adjacency matrix" representation of a graph is very often never multiplied by a vector even in academic algorithm descriptions. Not true. There is a whole field (graph signal processing) that studies graphs in terms of their description in matrix form (adjacency, connectivity and more). For example, you can find connected components by looking at the eigenvectors of a certain matrix.
- Joker_vD 6y ago
  Yes, they pretty much are unless you're in the business of linear codes—then they're actually 1xN matrices. A pretty annoying convention for someone coming in from the general algebra: takes a time to stop mentally transposing everything.
- pmiller2 6y ago
  > For example the "adjacency matrix" representation of a graph is very often never multiplied by a vector even in academic algorithm descriptions. Unless you're doing spectral graph theory, which looks at properties of the eigenvalues and eigenvectors of the graph's adjacency matrix. Even then, you don't usually multiply the adjacency matrix by a vector explicitly.
  - WJW 6y ago
    Today I learned! I'm fairly familiar with "regular" spectral analysis techniques, ie FFTs and DCTs, with some CWT waveletty goodness thrown in here and there but I never heard about spectral graph analysis. That's what you get for staying in EE land too long I guess.
    - qppo 6y ago
      Fourier & Friends are excellent analytical tools for the nature of patterns, regardless of where they occur! In EE-land we think too much about real and complex numbers, where Fourier analysis is more concrete. But spectral graph theory makes a lot of sense when you think of Fourier analysis as a way of decomposing patterns into their constituent parts, it just looks a bit funny when those patterns aren't numbers.
      - pmiller2 6y ago
        Indeed. By using tools of linear algebra on the adjacency matrices of a graph, you can tell a lot about the structure of the graph. For instance, if A is the adjacency matrix of a graph G, with n vertices (we say 'vertices' in the math department almost exclusively -- rarely do we say 'nodes'), and k edges, denoting the trace of A by Tr(A), we can find the number of triangles in A by computing Tr(A^3)/6. We can also tell if G is connected by computing A^n. [0] OTOH, the spectrum doesn't tell you nearly everything you'd want to know about a graph. There are many examples of non-isomorphic graphs that are nonetheless cospectral. For instance, one of my professors from grad school wrote a landmark paper in spectral graph theory in 1973, showing that almost all trees are cospectral. [1] --- [0]: Of course, you'd probably never actually do this, because it's horribly inefficient, but here's how it goes. First, you prove easily by induction that A^c_{i,j} is the number of paths of length c starting at vertex i and ending at vertex j. With that in mind, we see that if there is a row of all nonzero numbers in any matrix A^c for c <= n, then G is connected. With a little more work, you can even extract all the connected components of G, by looking at submatrices of A^c. [1]: Unsurprisingly, the paper is titled "Almost all trees are cospectral". See: https://www.semanticscholar.org/paper/Almost-all-trees-are-cospectral-Schwenk/dc8911f3ebd968a107cdd04379245263994c0e86#paper-header https://www.semanticscholar.org/paper/Almost-all-trees-are-c...
- scubbo 6y ago
  > aren't vectors just Nx1 matrices? It's been a while since I formally studied maths, but - can you describe a situation in which this is _not_ true? (modulo transposition)
  - dan-robertson 6y ago
    Well if you think of matrices as linear maps then saying a vector is just an Nx1 matrix is like saying that a vector is just a linear map from a vector space of dimension 1 to a vector space of dimension N. It isn’t really a very useful thing to say
    - tomjakubowski 6y ago
      Sure it's useful, if not earth-shattering - another way of saying it is that a vector maps scalars to vectors on the same line.
  - crdrost 6y ago
    So, I would say that there is a canonical isomorphism between them but that they are not quite the same. So, to take a step back, I'd say that a covector is a linear function from a vector input to a scalar output (those terms themselves being somewhat fungible, the space of "vectors" needs to probably form a module over the "scalars" which must themselves be a ring—the issue is that I would as a physicist include scalar fields but you can have two nonzero fields multiply to give a zero field, so they do not obey the field axioms). Then I would say that an [m n]-tensor is technically a multilinear function from m covectors and n vectors to a scalar. This means that a [0 1]-tensor is really exactly a covector, but a [1 0]-tensor is not really exactly a vector. One can manifestly be constructed from any vector v (take any covector c and produce the scalar c(v)) and we generally have some criteria that I forget which ensures that this is not just an injection but also a bijection implying some inverse, so that these [1 0] "co-covectors" are indeed isomorphic to the vectors. And then of course this becomes much easier in a metric space where we identify a canonical bijection between vectors and covectors called the "metric", this gives a much more direct way by which co-covectors are isomorphic to vectors. Hopefully that all makes sense. The situations in which this is not true are non-metric spaces where linear maps from (linear maps from vectors to scalars) to scalars are just a subset of the "apply to this vector" instances, but other linear maps are maybe also included. Then there is a more dramatic statement which I think requires the space to be Hausdorff-paracompact or something, which is the idea that of course we have the outer product which naturally combines an [a b]-tensor and a [c d] tensor into an [a+c, b+d]-tensor ("take these vectors and covectors, give them to the first tensor, take those vectors and covectors, give them to the second tensor, then take the two scalar outputs and multiply them together), and we claim that actually an [m n]-tensor can always be realized as a finite sum of outer products of m [1 0]-tensors with n [0 1]-tensors, which allows you to do arbitrary index contractions in a geometric way.
- dnautics 6y ago
  > Purist test The short answer is. Yes, but if your PL treats it that way you will wind up in trouble [0]. The long answer is: https://www.youtube.com/watch?v=C2RO34b_oPM https://www.youtube.com/watch?v=C2RO34b_oPM (but seriously take the time to watch this, it's fantastic). [0] Separately C- and often C-derived languages/frameworks like numpy also treat them as 1xN matrices, but that's a nearly tabs-vs-spaces level religious war, with actual consequences. I think a lot of people got confused when translating andrew ng's early octave-based ML coursera course (Nx1) to python (1xN), and also in the back and forth between math ML papers which use Nx1 and python.
  - tomjakubowski 6y ago
    Besides needing to change the order of multiplication (y = xM vs y = Mx) and use the right transposition of the matrix, do any other actual consequences come from the choice of "row vector" vs "column vector"?
    - dnautics 6y ago
      Mathematically speaking, no. They are isomorphic duals. But ergonomics are important to prevent errors. I personally think Matrix-in-front is nice because it evokes the idea that the matrix is a function acting on the vector. In the real world, When you start doing matrix-vector, if you aren't careful with row-major vs column-major storage you can introduce performance regressions. Let's say the architecture can do 256 bit memory move into 4xf64 mmx registers, you have to think carefully about what is going where before proceeding. Some architectures might be able to do an arbitrary stride so that those f64s can be nonadjacent in a simultaneous move. I suspect not handling this correctly is part of what holds back really good fp8, fp16 performance, and I suspect for example the TPUs struggle with this. Of course optimizing for matrix-vector can be different for optimizing for matrix-matrix, since the column vs row memory access preference for the front matrix is exactly the opposite of the back matrix.
  - jpeloquin 6y ago
    > numpy also treat them [vectors] as 1xN matrices I may be misunderstanding something, but in numpy at least a vector, a 1×N array ("row vector"), and a N×1 array ("column vector") behave differently. vec = numpy.array([1,2,3]) assert vec.shape == (3,) assert vec.ndim == 1 row = np.array([[1,2,3]]) assert row.shape == (1,3) assert row.ndim == 2 col = np.array([[1], [2], [3]]) assert col.shape == (3,1) assert col.ndim == 2 And a vector, unlike a 1×N or N×1 array, can be multiplied to either side of any matrix with compatible cardinality: assert all(vec @ numpy.eye(3) == numpy.array([1, 2, 3])) assert all(numpy.eye(3) @ vec == numpy.array([1, 2, 3])) Matlab / Octave, in contrast, forces the user to pick a 1×N or N×1 matrix to represent a vector. Its arrays are always ≥ 2D. So you're probably still right that people get confused translating this to Python. Just wanted to clarify the numpy side of things. The JuliaCon talk you linked does a great job of explaining what different fields mean by "vector"; thanks for linking it.
- ducttapecrown 6y ago
  Vectors are Nx1 matrices only once you choose an ordered basis!
- activatedgeek 6y ago
  I think if in any context one uses the usual matrix algebra, it is the same linear map, just in a more abstract setting. If you tell me storing a lookup table is matrix, I think that is sort of out of context. But then again, I could be labelled a purist here, and I'm trying really hard to not fall into the trap.
- tobmlt 6y ago
  Along with what others have mentioned, another application of adjacency matrix multiplication is in doing discrete calculus on meshes. Pushing one forms to two forms via exterior differentiation, for example. The chief operation is a matrix multiplication with said adjacency matrix.
- alentist 6y ago
  The nth power of an adjacency matrix yields the number of length-n walks from any vertex to any other vertex.
d_tr 6y ago
Agreed. I think that the distinction between the objects and their possible representations should be made clear from the beginning, simply because it will make things easier to understand. IMO, just a couple of chapters from an introductory pure mathematics book is actually the most "to the point" place to start even for people who are not huge fans of math. Just the precise definition of a vector space over a field, a linear operator, a vector basis, the derivation of matrix elements, the usual related examples and some "gymnastics" on paper can make stuff "click" and be a great start for any intended application.

adamnemecek 6y ago

Matrix multiplication is like convolution.

activatedgeek 6y ago
To be sure there isn't a perspective here that I may be unaware of, is this a reference to circulant matrices, which bear the Toeplitz sparsity structure?
- jacobolus 6y ago
  You might find something interesting in https://cr.yp.to/lineartime/multapps-20080515.pdf https://cr.yp.to/lineartime/multapps-20080515.pdf
salty_biscuits 6y ago
Maybe convolution on a discrete basis can be represented as a matrix multiplication with a circulant matrix?

zests 6y ago

Matrices are a fun way to stretch the mind. They are easy to grasp yet very dissimilar to numbers. Sometimes they can be used to represent numbers and we can use our matrix intuition to answer questions about regular numbers. You can define functions on matrices just like you define them on numbers. Multiplication is a function. The determinant is a function. You can even take derivatives of these functions. The derivative of the determinant function is written in terms of the trace of the matrix. Yet another matrix function. Who would have guessed that the derivative and trace are related in this way? There's really a lot of depth here. https://en.wikipedia.org/wiki/Jacobi%27s_formula https://en.wikipedia.org/wiki/Jacobi%27s_formula

_Microft 6y ago
Don't forget the matrix exponential which might certainly blow the mind of a lot of people here. Matrices as exponent - who would have thought that possible! https://en.wikipedia.org/wiki/Matrix_exponential https://en.wikipedia.org/wiki/Matrix_exponential
- zests 6y ago
  det(e^A) = e^(tr(A)) Pure magic.

hchasestevens 6y ago

I've always found the bipartite graph conceptualization of matrix multiplication the most intuitive, and especially so if you're familiar with neural networks: https://www.math3ma.com/blog/matrices-probability-graphs https://www.math3ma.com/blog/matrices-probability-graphs

crdrost 6y ago
That is genuinely a really fun way to look at it, thank you for linking this! Especially this fits nicely with Markov matrices where you have N input nodes and N output nodes and the sum of all of the probabilities coming out of one of the nodes needs to equal 1. What I might find a little more difficult to teach to people through this lens is the phenomenon of eigenvectors, but I suppose that's to be expected—nothing will work well for all purposes.
- layoutIfNeeded 6y ago
  >What I might find a little more difficult to teach to people through this lens is the phenomenon of eigenvectors Why? Eigenvectors are simply inputs to the network where the output keeps its shape, that is, at most it gets rescaled, as if you had applied a uniform gain to the components, but otherwise it will be the same as the input.
  - tonyarkles 6y ago
    Oh. Oh my. I have studied linear algebra theory some. I have used it a ton. I have used eigenvectors to solve problems. I have never grokked them. This description changed that. Thank you!
  - crdrost 6y ago
    So for example let me ask for your knee-jerk opinions based on this idea: - does a matrix have the same left-eigenvectors as its right-eigenvectors? - what is the relationship between the left-eigenvalues and right-eigenvalues? - is there always an eigenvector? when is there a complete set? how do you generalize your notion of eigenvectors so that matrices always have a complete set of them? I am not sure any of these are intuitive here.

shoo 6y ago

In some applications, e.g. modelling something defined by PDE, you might need to solve a very large linear system of equations Ax=b, where the vector b has 100,000,000 elements, and A is a 100,000,000 by 100,000,000 element matrix. So for a naive dense matrix representation of A using 1 byte per entry you'd need around 9 petabytes of storage. In practise, for many interesting systems of equations that encode "local" properties, A will be a sparse matrix where the overwhelming majority of matrix entries are zero. There are various sparse matrix formats designed to avoid storing zeroes: the simplest is COO where you store triples of the form (i, j, A_ij) for all nonzero entries A_ij of A. More efficient formats are CSR or CSC ( compressed sparse row & column respectively) that use even less memory by avoiding storing repeated indices where there are runs of nonzero elements. To solve one of these huge linear systems Ax = b , we hardly ever want [1] to go to the expense of computing and storing an explicit matrix representation of the inverse A^{-1} . Instead, we merely need to have some function f that is able to map an input vector b to some output vector f(b)=x that happens to satisfy Ax=b . If the matrix A has sufficiently nice properties [2] we can use an efficient iterative method such as the conjugate gradient method to map the input vector b to an output vector x by solving Ax=b. To evaluate the conjugate gradient method, we don't need to necessarily have an explicit dense or sparse representation of the matrix A, we merely need a function that encodes how A acts on a vector by matrix multiplication. E.g. some function g that maps an input vector x to the output vector g(x) = Ax. So if we've got some appropriately defined conjugate gradient method algorithm cg(g, b), we can define the function f(b) := cg(g, b) Calling f(b) will return x that satisfies g(x) = b, i.e. f is the inverse of g. So now we're expressing linear algebra without having any explicit matrices anywhere: but our functions g and f are of course both linear operators that encode the action of matrix multiplication by A and A^{-1} respectively. [1] Why not? It's a lot more effort to compute A^{-1} which could be used to evaluate A^{-1}b for any given b, but often we only want to know A^{-1}b for a specific b. Also, if the matrix A encodes some local property of a physical system , then A^{-1} will encode a global property -- so it will need to be a dense matrix. [2] Sufficiently nice properties: if it's symmetric positive definite, which arises naturally in a bunch of situations. See eg https://en.m.wikipedia.org/wiki/Conjugate_gradient_method https://en.m.wikipedia.org/wiki/Conjugate_gradient_method

unnouinceput 6y ago

notsuoh 6y ago

This comes up occasionally. I don't find it to be particularly helpful, even though I do think betterexplained has been a strong source of gaining intuition into various subjects. Recognizing though that method of understanding something is pretty personal, I will say that what really helped me refresh was the 3Blue1Brown Essence of Linear Algebra series on Youtube. If you're trying to better grasp the subject, do yourself a favor and check out those videos. https://www.3blue1brown.com/essence-of-linear-algebra-page/ https://www.3blue1brown.com/essence-of-linear-algebra-page/

Yajirobe 6y ago
Everyone's seen/knows them already
- adenadel 6y ago
  Well, even if "everyone" knows it, at some point you have to come across it for the first time. https://xkcd.com/1053/ https://xkcd.com/1053/
  - commandlinefan 6y ago
    Everyone's seen that XKCD already.
    - coldtea 6y ago
      https://xkcd.com/1053/ https://xkcd.com/1053/
      - bryanrasmussen 6y ago
        I'm thinking now we go here https://xkcd.com/1270/ https://xkcd.com/1270/
- notsuoh 6y ago
  Perhaps not the people who have not seen the OP’s link?

justjonathan 6y ago

I wholehearted endorse 3B1B, The linear algebra series is excellent, the rest of his work is too!

OneGuy123 6y ago

If we're talking about 3D rendering then a matrix multiplication with a vector are just projections: A 3x3 matrix that transforms a vector is nothing else than that vector being projected onto the 3 axis which are inside the 3x3 matrix. This is very easy to see visually. A matrix times matrix multiplication (eg 3x3 times 3x3) is just projecting the axis of one matrix onto the other: expressing the coordinate system in terms of a different coordinate system. The 4x3 (or 4x4) matrix is needed for translation and 3d projection for a 3d triangle onto a 2d plane (screen pixels). For translation: it's just a hack since if you write it out it's a nice and a fast hack to simulate "movement". Then for projection you just hack the numbers in the matrix in such a way that you shrink things further apart from the origin. TLDR: for 3d graphics matrices are used because you can hack them to represent any kind of a transformation. The reason they are used is because graphics cards are fast at performing dot products. Plus matrix multiplication doesn't require trigonometry or division so it doesn't require the slower transcendental GPU instructions (sin, cos,...). For other uses their interpretations is different. I always hated the dull mathematic definition of "a matrix represents a linear map" because what the matrix actually represents is completely context dependent.

d_tr 6y ago
> I always hated the dull mathematic definition of "a matrix represents a linear map" because what the matrix actually represents is completely context dependent. The projection and translation matrices you mentioned represent restricted sets of linear maps in some vector space, but the meaning of the restriction is also captured in other mathematical structures. See affine spaces and projective spaces.
Koshkin 6y ago
Sure - remember those noisy dot matrix printers?..
markisus 6y ago
The projection viewpoint for a rotation matrix using dot products is totally valid, but I think the column viewpoint is more intuitive. A 3x3 matrix can be viewed as something that acts on the standard unit basis vectors. The action on the standard unit basis vectors can be read out by looking at the columns. (A matrix times the ith standard basis vector is just the ith column.) Since the transform is linear, all the other points in space are carried along with the action as well. This is the "linear map" viewpoint of a rotation matrix. I show an example here https://biro.ai/we-learned-the-wrong-way-to-matrix-multiply/ https://biro.ai/we-learned-the-wrong-way-to-matrix-multiply/ where this viewpoint lets you instantly see what a rotation matrix does by looking at the columns.

Exuma 6y ago

OMG Thank you! I'm going through tons of linear algebra for a ML algorithm I need to understand and matrix multiplication is ... weird to say the least.

dr_zoidberg 6y ago
I strongly recommend 3blue1brown's intro to linear algebra[0] for quick intuitions, followed by Gilbert Strangs MIT Open Course[1][2] for (much) deeper detail. Strang is a genius, but Sanderson's graphics and intuitions can be helpful early on. [0] https://www.youtube.com/watch?v=fNk_zzaMoSs&list=PLZHQObOWTQDPD3MizzM2xVFitgF8hE_ab https://www.youtube.com/watch?v=fNk_zzaMoSs&list=PLZHQObOWTQ... [1] https://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-spring-2010/ https://ocw.mit.edu/courses/mathematics/18-06-linear-algebra... [2] https://www.youtube.com/playlist?list=PL49CF3715CB9EF31D https://www.youtube.com/playlist?list=PL49CF3715CB9EF31D
- Exuma 6y ago
  thanks!! I skimmed Strangs video just now and it looks super good, what a great suggestion!

deleted 6y ago

[deleted]

Tycho 6y ago

What is some good intuition around matrix inverses?

10000truths 6y ago
An inverse function?
joppy 6y ago
The matrix inverse “undoes whatever the matrix did” is pretty much the most straightforward interpretation, if you’re thinking of a matrix as performing some kind of rotation/shear/scaling of space. There are some other interpretations, for example if you think of a linear system Ax=b as a kind of “checking machine” (does x satisfy Ax=b? Yes/no, try again), then the inverse of A can produce solutions, since x=(A inverse)b.

da39a3ee 6y ago

> However, sometimes the matrix being operated on is not a linear operation, but a set of vectors or data points. In Jeremy Kun's book [1] he argues that in fact data matrices _can_ be viewed as linear transformations. See e.g. section 10.9 on the SVD > That is, we’re saying the input is R3 and the basis vectors are people:... > By representing the ratings this way, we’re imposing the hypothesis that the _process_ of rating movies is linear in nature. ... [1] https://pimbook.org/ https://pimbook.org/

rademacher 6y ago

I was expecting this to be more about writing fast matrix multiplies. Surprisingly, it ends up being a lot more than just a triple loop and there's a reason that everyone uses existing libraries like OpenBLAS and MKL [1]. [1] https://www.cs.utexas.edu/users/flame/laff/pfhp/ https://www.cs.utexas.edu/users/flame/laff/pfhp/

Waterluvian 6y ago

Does anyone mind suggesting a solid intro to matrices in the context of what they are and how the affine transformations work? I know of these concepts but I think it's time to learn.

julian_adams 6y ago

Can you write up a physical intuition for the usage of matrix?

Koshkin 6y ago
A rotation in space by an angle can be written as a matrix.

siraben 6y ago

When I took a course in linear algebra, we learned about linear transformations and vector spaces in the abstract first. Then when we got to matrices it was viewed as a way to represent linear transformations. Also it led to a natural derivation for matrix multiplication.

siraben 6y ago
If anyone is curious I've uploaded the half-page derivation found in Chapter 3 of Linear Algebra Done Right here[0]. [0] https://imgur.com/a/BTKMWU2 https://imgur.com/a/BTKMWU2

crb002 6y ago

Matrix vector multiply takes an n string and maps it to a k string via a matrix automata. Matrix matrix multiply maps p strings instead of one. We should be parsing on a GPU. https://en.wikipedia.org/wiki/CYK_algorithm https://en.wikipedia.org/wiki/CYK_algorithm