12 ms·
Matrix Multiplication
- jmrm 5y agoI need this a bit more than 10 years ago, but thanks anyway :-)
- ogogmad 5y agoMy advice: - Learn how to multiply a matrix M by a column vector v. - Generalise that by noticing that M[u|v|...] = [Mu|Mv|...]. That's matrix multiplication.
- qsort 5y agoAfter all it's called linear algebra for a reason :)
- madars 5y agoYep! Wikipedia has a very useful visual https://en.wikipedia.org/wiki/Matrix_multiplication#/media/File:Matrix_multiplication_diagram_2.svg https://en.wikipedia.org/wiki/Matrix_multiplication#/media/F...
- hwers 5y agoThis is my favorite way to think about it as well. I think I learned it first in one of Steven Boyds astounding convex optimization lectures https://www.youtube.com/watch?v=McLq1hEq3UY https://www.youtube.com/watch?v=McLq1hEq3UY
- fault1 5y agoalso related: the left multiplication of a matrix M by a row vector: https://dzone.com/articles/visualizing-matrix https://dzone.com/articles/visualizing-matrix
- contravariant 5y agoIt looks so innocuous when you write it as (A B)_ij = A_ik B_kj.
- ogogmad 5y agoUsing the Einstein convention*. Otherwise that can be read wrong. * https://en.wikipedia.org/wiki/Einstein_notation https://en.wikipedia.org/wiki/Einstein_notation
- deleted 5y ago[deleted]
- deleted 5y ago[deleted]
- carlosgg 5y agoDiscussion from 5 years ago: https://news.ycombinator.com/item?id=13036386 https://news.ycombinator.com/item?id=13036386
- dang 5y agoThanks! Macroexpanded: Matrix Multiplication - https://news.ycombinator.com/item?id=24141472 https://news.ycombinator.com/item?id=24141472 - Aug 2020 (1 comment) Matrix Multiplication - https://news.ycombinator.com/item?id=13036386 https://news.ycombinator.com/item?id=13036386 - Nov 2016 (131 comments) Matrix Multiplication - https://news.ycombinator.com/item?id=13033725 https://news.ycombinator.com/item?id=13033725 - Nov 2016 (2 comments)
- gitgud 5y agoInteresting to compare this discussion vs the discussion 5 years ago. Although the consensus is the same (that it's not very intuitive) people seem to be much more blunt with their criticism now...
- d--b 5y agoVisually, the rotation part makes it much less intuitive than writing the result matrix next to the first operand and the second operand above the result matrix
- drhodes 5y agoDenis Auroux explains that way of seeing it, https://youtu.be/bHdzkFrgRcA?t=1404 https://youtu.be/bHdzkFrgRcA?t=1404
- neosat 5y agoso useful - thanks!
- deleted 5y ago[deleted]
- tinalumfoil 5y agoI agree. Matrix multiplication can pretty succinctly be defined in terms of the dot product between the row and column of the inputs at the corresponding spot in the output. When I first learned I already new a little about the properties of dot products so it made the “magical” properties of matrix multiplication more understandable. Maybe not the way a mathematician would define it — they might look at dot products as a special case of matrix multiplication thus teach the latter first — but it was at least intuitive.
- im3w1l 5y agoI think mathematicians will usually be aware of many ways of defining something. Because different definitions will suggest different approaches to a problem, and suggest different ways to generalize a concept. Yours is an important one.
- bee_rider 5y agoIt can be nice to help visualize, though, for example if you have a block matrix and you know some blocks have particular properties, it can be helpful to imagine the steps of an algorithm as various blocks sliding across each other.
- axpy906 5y agoI like the visual look of the sliding window.
- phkahler 5y agoI did until I realized it's computing more than one dot product at a time. Then it was suddenly not great. It falls somewhere between standard matrix multiplication and what might eventually be a good way to understand a systolic array multiplier.
- clircle 5y agoIs the connotation that this is the most intuitive way to think about or visualize matrix multiplication? If so, I reject.
- windsignaling 5y agoAgreed. Posts like this seem to get upvoted on HN just because "oooh, a pretty animation" and/or they struggled with college math "See? This is how they should've taught it! Pictures are better than lectures!"
- stolen_biscuit 5y agoYeah I found this confusing personally. For me, this image from learnopengl.com has been the most intuitive way: https://learnopengl.com/img/getting-started/matrix_multiplication.png https://learnopengl.com/img/getting-started/matrix_multiplic... from their page on transformations https://learnopengl.com/Getting-started/Transformations https://learnopengl.com/Getting-started/Transformations
- Twisol 5y agoI'd guess that the "sliding window" metaphor means you could model matrix multiplication as a convolution. Does this give any intuition for matrix multiplication via the Fast Fourier Transform? https://en.m.wikipedia.org/wiki/Convolution_theorem https://en.m.wikipedia.org/wiki/Convolution_theorem > the convolution theorem states that under suitable conditions the Fourier transform of a convolution of two functions (or signals) is the pointwise product of their Fourier transforms.
- amelius 5y agoThe fastest known matrix multiplication algorithm is the Coppersmith-Winograd algorithm with a complexity of O(n^2.3737). FFT is O(n log n). So probably not.
- Twisol 5y agoApologies; apparently I was thinking of integer multiplication using FFT: https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strasse... But my question (which wasn't about asymptotic complexity) stands: can we think about matrix multiplication as a convolution? If so, we can do pointwise multiplication sandwiched between Fourier transforms -- I don't expect it to be fast, I just expect it to be possible.
- Rayhem 5y ago> Fastest known matrix multiplication algorithm... ...for general matrices. Fourier transforms do indeed diagonalize circulant matrices[1], making their multiplications O(2 n log n + n) -> O(n log n). [1]: https://en.wikipedia.org/wiki/Circulant_matrix https://en.wikipedia.org/wiki/Circulant_matrix
- amelius 5y agoYes, no doubt that there are faster algorithms for specific matrices. That matrix you are bringing into the discussion is only n-dimensional, so not surprising that you can multiply it faster than a matrix that is n×n dimensional.
- jagrsw 5y agoI understand the rotation part and some uses, but what's the intuitive explanation for why it's done this way? Convention? IOW, what matrix multiplication tries to achieve by doing this manipulation which looks like rotation visually? Why not doing it w/o rotation instead (with the precondition that numbers of columns in two matrices should be equal, instead of column vs row)?
- ogogmad 5y agoA different convention would make matrix-matrix multiplication no longer express composition of linear maps. So the geometric -- or deeper meaning -- would be lost. The operation you're describing is nevertheless equal to A^T B. In other words, it can be expressed using a combination of matrix multiplication and matrix transpose. I don't see what it could be used for, though.
- xyzzyz 5y agoWhen mathematicians think about matrix multiplication (and matrices in general), they don't really think about "rotating" matrices like in the animation above, but rather about operators and their composition. The matrix multiplication is what it is, because that's how function composition works. Look: consider two functions, f(x, y) = (x + 2y, 3x + 4y), and g(x, y) = (-x + 3y, 4x - y). What's f(g(x, y))? Well, let's work it out, it's simple algebra: f(g(x, y)) = f(-x+3y, 4x-y) = ((-x+3y)+2(4x-y), 3(-x+3y) + 4(4x-y)) = (-x + 3y + 8x - 2y, -3x + 9y + 16x - 4y) = (7x + y, 13x + 5y). Whew, that was some hassle to keep track of everything. Now, here's what mathematicians typically do instead: they introduce matrices to make it much easier to keep track of the operations: Let e_0 = (1, 0), and e_1 = (0, 1). Then f(e_0) = f(1, 0) = (1, 3) = e_0 + 3 e_1, and f(e_1) = f(0, 1) = (2, 4) = 2 e_0 + 4 e_1. Thus, mathematicians would write that f in basis e_0, e_1 is represented by the matrix [1 2] [3 4] so that when you multiply it by the (coulmn) vector [x, y], you get [x] * [y] [1 2][x + 2y] [3 4][3x + 4y] Similarly, g(e_0) = (-1, 4) = -e_0 + 4e_1, g(e_1) = (3, -1) = 3e_0 - e_1, so it's represented by the matrix: [-1 3] [ 4 -1] Now, let's multiply matrix of f by matrix of g: [-1 3] * [ 4 -1] [1 2][-1*1+2*4 3*1-1*2] = [7 1] [3 4][-1*3+4*4 3*3-1*4] [13 5] and when we multiply the resulting matrix by column vector [x, y]: [x] * [y] [7 1][7x + y] [13 5][13x + 5] So, what did we get was in fact our original calculation of f(g(x, y)) = (7x + y, 13x + 5y). The conclusion here is that matrix multiplication is what the function composition forces it to be.
- Rickthedick 5y agohave you looked into https://en.wikipedia.org/wiki/Strassen_algorithm https://en.wikipedia.org/wiki/Strassen_algorithm strassen multiplication and karatsubas algorithm for multiplication? https://en.wikipedia.org/wiki/Karatsuba_algorithm https://en.wikipedia.org/wiki/Karatsuba_algorithm apparently its the one python uses. I just recently learned it and I find it very interesting.
- civilized 5y agoA good example of using technology to make the simple complicated.
- echelon 5y agoI was going to say, this is about the least intuitive I've seen matrix multiplication. Not only is the flip confusing, but they fill more than one result cell simultaneously. Slick animations, but it needs to be slower and simpler.
- paulpauper 5y agoit could be helpful to visual learners
- spiffytech 5y agoI find this very clear. I would have loved having this kind of visualization when I studied linear algebra in college (which was a struggle for me). In my experience, math is taught by people who are good understanding abstract concepts. It's hard for me to pick up abstract concepts, so a lot of traditional math education / exercises / tutorials work poorly for me.
- mrtksn 5y agoThe process itself is visualised here well but can someone explain why anyone would want to multiply matrixes? Yes, I know where it is used and I did my fair share back in college but it never really clicked for me in intuitive manner. Why simply don't go procedural and skip the matrix representation altogether? Using matrixes in physics calculations, for example, feels like disassociating the intuitiveness of the physics for the sake of the matrix calculation tools. When I look at a matrix of values I don't see anything.
- paulpauper 5y agoa major application is markov chains
- mrtksn 5y agoHow do you think about it in intuitive way?
- Jtsummers 5y agoIn a Markov chain, the matrix (or matrices) are similar to the matrix representation of a graph (without brackets): a b c d a 1 0 1 0 b 1 1 0 0 c 0 0 1 1 d 1 0 0 1 Written another way, the above graph has these directed edges: a -> a, a -> c b -> a, b -> b c -> c, c -> d d -> a, d -> d In a Markov chain, the possible state transitions (graph edges) are represented in the same way, but instead of a 1 or 0 (connects or doesn't connect) a probability is assigned to each possible transition. https://en.wikipedia.org/wiki/Examples_of_Markov_chains https://en.wikipedia.org/wiki/Examples_of_Markov_chains - Several examples with a mix of prose, graphical presentation, and the matrix representation.
- eurasiantiger 5y agoConnectedness between words.
- kzrdude 5y agoThe benefit is reusing the matrix theory - matrix knowledge(!) - in different contexts. In some cases making a matrix in physics is a quite sterile representation, like you suggest, like plugging in the numbers in an otherwise generally stated question. The matrix values depend on choices of coordinate system and everything, quite inelegant in that way. Why practically use matrixes on the computer? It's efficient to compute in blocks instead of one by one.
- max_ 5y agoThis is what you should show students before sitting them through a 1 hour class lecture.
- recursive 5y agoI passed a class on linear algebra, and I think most of it made sense to me at the time. I can't remember anything of it now, except "Abelian" was a funny sounding word that was used a lot. I clicked around on this thing. I didn't find it illuminating at all.
- max_ 5y agoI understand, people gain intuition through different things.
- coss 5y agoWow this is a much easier way to remember for me. Thank you!
- tomthe 5y agoNo problem in computer science is really optimised, until you can solve it with matrix multiplication ;)
- the__alchemist 5y agoI think the view of matrices as a transform of space is more intuitive, for a visual approach. Ie, I think a nice addition to this webapp would be demonstrating (At least for 2 and 3 dimensions) what the transforms look like; this algorithmic approach it's showing feels less useful.
- vecter 5y agoThis is incredibly confusing. I also don't like the dot-product explanation for individual entries of the resultant matrix. When I was in college, it was hammered into my head that matrix multiplication was a linear combination of column vectors. It took a while for that to sink in, but once it did, it made a lot more geometric sense than just taking a bunch of inner products of column and row vectors.
- commandlinefan 5y ago> a linear combination of column vectors Isn’t that pretty much the same as the dot-product explanation?
- vecter 5y agoTo clarify, I mean if the columns of a 3x3 matrix A are A1, A2, and A3, and the scalar elements of vector x are <x1, x2, x3> then Ax = x1*A1 + x2*A2 + x3*A3. Each column of A is scaled by an element of x and then added together. Is that what you had in mind by the dot-product explanation? To me, the dot product explanation is that in Ax = b, b1 = <row1 of A> dot x, b2 = <row2 of A> dot x, and b3 = <row3 of A> dot x. Of course these (and all other valid) interpretations of matrix multiplication are "the same", but this is less geometrically intuitive to me.
- nockupe_2 5y agoTotally yes. The mechanistic illustrations of matrix multiplication, including the OP, are easy enough but don't help me with motivation or intuition. I always start with Ax, which is just a linear combination of the columns, like the first figure here https://eli.thegreenplace.net/2015/visualizing-matrix-multiplication-as-a-linear-combination/ https://eli.thegreenplace.net/2015/visualizing-matrix-multip... For those who want to make their own cheat sheet: Matrix $\times$ vector is linear combination of the columns: \begin{align} Ax &= \begin{pmatrix} a_{1,1} & a_{1,2}\\ a_{2,1} & a_{2,2}\\ a_{3,1} & a_{3,2} \end{pmatrix} \begin{pmatrix} x_1\\x_2 \end{pmatrix}\\ &= x_1\begin{pmatrix} a_{1,1}\\ a_{2,1}\\ a_{3,1}\\ \end{pmatrix} + x_2\begin{pmatrix} a_{1,2}\\ a_{2,2}\\ a_{3,2}\\ \end{pmatrix} \end{align} Intuitively, this example maps a point in $\mathbb{R}^2$ to $\mathbb{R}^3$ Another way to see $Ax$: Columns of $A$ form a basis, and $x$ is a coordinate vector in that basis.
- laszlokorte 5y agoThe animation looks really neat but I did not find it very helpful from an pedagocical perspective which is why I built an alternative version inspired by OP. [1] /edit: I just noticed the OP is built by andrestaltz with Cycle.js. Cycle is a really nice reactive programming js framework that is very great to work with. [1]: https://static.laszlokorte.de/matrix-multiplication/ https://static.laszlokorte.de/matrix-multiplication/
- rustybolt 5y agoYes, I wanted to comment that it's just taking dot products of the rows of the left matrix and the columns of the right one. That's also more easy to understand since there's just one thing going on at a time, and you don't have to move, flip and overlay matrices. This is nice to animate but almost impossible to do in your head.
- eigenvalue 5y agoI agree, your version is much better and a lot less confusing.
- carbocation 5y agoThis is a nice visualization. Although visually obvious, it might be nice to also show the matrix dimension adjacent to or beneath the Matrix A and Matrix B labels.
- laszlokorte 5y agoThanks for the idea! I added that :)
- carbocation 5y agoThis is great! I think if you swap the order to show (row x column) you'll help people grasp the intuition behind the need for matching up Matrix A's column count with Matrix B's row count.
- dataangel 5y ago
- gerdesj 5y ago
- gurchik 5y agoMaybe OP just wanted to share something interesting and is unaffiliated with the site?
- teh_klev 5y agoThe domain name suggests it's someone called Laszlo Korte who owns the site and not jonbaer. Also what makes you think this is a "data gathering" exercise. Neither Privacy Badger nor uBlock Origin appear to have blocked any third party cookies. I think your comment is somewhat misguided.
- 725686 5y agoI you want some intuition, this Kalid Azad's explanation may help: https://betterexplained.com/articles/matrix-multiplication/ https://betterexplained.com/articles/matrix-multiplication/
- joeman1000 5y agoI like the website but don’t find the animation intuitive, sorry! I always position (for Ax = b) the A matrix with the x matrix to the top right of it. To the right of the A matrix, under the x matrix, I draw the resulting b matrix. I then draw a line through the (1,1) position of x downwards to b. It hits (1,1) of b, then I do the same horizontally from A(1,1). I take the dot product of the numbers which the two lines intersect, and repeat for all other positions. This is the only way I can remember matrix multiplication! It made my life so much easier and I am always on the lookout for intuitive visual tools for mathematics concepts. I don’t know if this is a really common tool, it was taught to me by my university professor Burkard Polster (the Mathologer on YouTube).
- flyers_research 5y agoWhenever I talk about matrix multiplication, I just say RC multiplication or row-column dot product. Linear Algebra is difficult because how literal it is and lack of emphasis on misinterpretations. A vector is different than most peoples understandings.
- deleted 5y ago[deleted]
- Tiddles-the2nd 5y agoVisually it looks very cool, but I agree it's not very helpful. At the very least each result and RC should be in a different colour.
- Dig1t 5y agoThis is absolutely, amazingly cool! Awesome job!
- theyoke 5y agoThis makes me think of a different but less intuitive way of matrix mul. Great jobs.
- framecowbird 5y agoThis is how I've always visualised matrix multiplication in my head, I find it quite intuitive.
- robertlagrant 5y agoThis visualisation really shows you how unintuitive matrix multiplication is.
- tbarbugli 5y agoI would never do it like this if I only had pen and paper but I admit the animation is pretty awesome :)
- Liambp 5y agoThis annoys me because it is the opposite of the way I do matrix multiplication myself. I work from left to right taking the rows of the left hand matrix, transposing them then scalar producting them with each column of the left hand matrix in turn. This animation starts with he columns of the left hand matrix and it feels like it is "working backwards" by going from right to left.
- floatingatoll 5y agoWell, now I understand matrix multiplication well enough to do it longhand in a pinch. Thanks for that!
- ljm 5y agoI was going through the ray tracer challenge book a while ago and this is the one thing I struggled with a little bit more than others. The underlying data structure made all the difference, but I still wasn't quite happy with how I approached it, with a bunch of nested loops and iterators.
- laputan_machine 5y agoAbsolutely beautifully animated! Nice
- wodenokoto 5y agoI think there are two parts to matrix multiplications: 1) How you do it by hand, which this page offers a very handy and easy to remember recipe for. 2) And why you do it in such a weird and not very multiplicative way. Matrix multiplication is so arbitrary when first introduced. Every time I see it work for some real life application I am surprised how mathematicians came up with it in the first place.