News for hackers. Stuff that matters.
Re:Matrix Multiplication by daniel-levin on Friday November 25, 2016 @09:23AM (#13036886)
This is a cool example of what Bret Victor calls an "Explorable Explanation" [0]. That said, I feel that it's more important to understand how and why matrix multiplication corresponds to a composition of linear transformations than learning the actual mechanics of doing the computation. You can get good at matrix multiplication without knowing what is going on. I view that as a less valuable activity than learning about linear transformations (vector-space structure preserving mappings) between finite dimensional vector spaces.

[0] http://worrydream.com/ExplorableExplanations/

Re:Matrix Multiplication by samuell on Friday November 25, 2016 @10:06AM (#13037191)
For understanding the mechanics of matrix multiplication, I found it useful to think in an analogy consisting of a grid of two layers of pipes; One -- the input-pipes -- coming in one direction, and the other -- the output pipes -- laid in an orthogonal direction. Then there would be "taps" in the cross-sections between the input and output pipes, representing the numbers (multiplication factors, really) in the matrix. I illustrated this in this little drawing: http://imgur.com/gallery/gBs64

The point then is that the taps (again, representing the matrix values) determine how much of each item in the input vector, that should be mixed into each item in the output vector.

This analogy has the limitation that the taps are allowed to enhance the flow, not just limit it, like physical taps would. That is, outputting more than 100% of the input :P Also, while this way of illustrating it may make some sense for matrix * vector multiplication, matrix * matrix would probably become a prohibitively cluttered image.

Re:Matrix Multiplication by snovv_crash on Friday November 25, 2016 @11:39AM (#13037886)
I really like that. And matrix * matrix would just have to be 3D, with a whole cube of taps. Sure, not easy to illustrate, but the concept extends well. It also makes it more obvious what the complexity of the operation is.
Re:Matrix Multiplication by im3w1l on Friday November 25, 2016 @04:36PM (#13040029)
Actually the complexity of matrix multiplication is not known. Current best is n^2.37
Re:Matrix Multiplication by dangom on Saturday November 26, 2016 @07:42AM (#13043224)
There is a proven lower bound [1], though.

[1] http://epubs.siam.org/doi/abs/10.1137/0218052

Re:Matrix Multiplication by justinpombrio on Friday November 25, 2016 @11:56AM (#13038017)
In a little more detail:

Look at the animation in the article, after the second matrix has been rotated and put on top of the first one. Then flip its top up so the two matrices are orthogonal. Finally, rotate the whole thing 90 degrees to the left (rotating along the axis that goes from the top of the page to the bottom of the page). Now you can see that the result will be a 2x3 matrix. And the values in each spot will be the sum of the products beneath it.

Re:Matrix Multiplication by sudoscript on Saturday November 26, 2016 @12:32AM (#13041884)
That's pretty cool. For me, everything changed when I started thinking in terms of column spaces and linear transformations. Matrices are not just a series of multiplications and additions. They describe so much more.
Re:Matrix Multiplication by ahane on Friday November 25, 2016 @10:28AM (#13037354)
3Blue1Brown is an amazing youtube channel that provides very entertaining and educating visual explanation for all sorts of maths.

He has a whole series on linear algebra, including matrix mulitplication:

https://www.youtube.com/playlist?list=PLZHQObOWTQDPD3MizzM2x...

Re:Matrix Multiplication by vanderZwan on Friday November 25, 2016 @11:44AM (#13037923)
... and after a succesfull Patreon campaign[0], he's going to do "Essence of Calculus" next. I'm seriously excited!

[0] https://www.patreon.com/3blue1brown

Re:Matrix Multiplication by daeken on Friday November 25, 2016 @04:57PM (#13040148)
I discovered this last night! I've been dealing with matrices frequently for the past 15 years and never really got them. Having watched his series now, I feel like I completely understand them, in a way that I never even fathomed before. I think I'm going to make a small series producing a raytracer from first principles, in a somewhat similar style; that visual design was just the perfect medium.
Re:Matrix Multiplication by bowlofstew on Friday November 25, 2016 @05:07PM (#13040204)
Thanks, I had not seen that channel before.
Re:Matrix Multiplication by nilkn on Friday November 25, 2016 @11:50AM (#13037960)
This is why I'm a big fan of Axler's Linear Algebra Done Right. The book's emphasis is on the concepts behind the calculations rather than the calculations.

I actually disagree with Axler on his avoidance of the determinant, though. I wish instead of avoiding it he'd spent more time developing it conceptually, as it's actually a fascinating construction. But to this day I have yet to find a gentler and better introduction to serious linear algebra than his book.

He recommends it as a second course, but I read it during my first course in the subject and considered it my "secret weapon". I truly believe that book is what allowed me to get a perfect score in the class -- I had a conceptual understanding that was just not possible to glean from the official course textbook.

Re:Matrix Multiplication by pash on Friday November 25, 2016 @01:13PM (#13038714)
Axler's book is very good. An alternative to consider is Paul Halmos's much older Finite-Dimensional Vector Spaces [0]. Both books take the same basic approach, and the proofs of the major theorems are substantially the same. (Halmos's book is well known and well liked and was probably Axler's starting point.)

Axler's book covers more ground (most notably, Halmos presents the polar decomposition but not the singular-value decompostion) and uses more modern terminology and notation. But Halmos's book has the merits of being half as long and a third as expensive, as well as having been written specifically to prepare the reader as directly as possible for Halmos's short introduction to Hilbert spaces [1].

I highly recommend one or the other of these books for readers who want to understand linear algebra as mathematicians do.

0. https://www.amazon.com/Finite-Dimensional-Vector-Spaces-Paul...

1. https://www.amazon.com/Introduction-Hilbert-Theory-Spectral-...

Re:Matrix Multiplication by anoncoward44 on Friday November 25, 2016 @08:28PM (#13041186)
For those who already know enough linear algebra to be bored with an entire book dedicated to Axler's approach to linear algebra, you can simply read the paper upon which the book is based:

http://www.axler.net/DwD.html

Re:Matrix Multiplication by ducttapecrown on Friday November 25, 2016 @02:24PM (#13039183)
Axler's book was free for me from my university's SpringerLink thingy.
Re:Matrix Multiplication by kaeluka on Saturday November 26, 2016 @06:33AM (#13043005)
Due to your post, I checked mine -- free pdf version available! Bingo! Thanks for the tip.
Re:Matrix Multiplication by Annatar on Saturday November 26, 2016 @07:26AM (#13043150)
This is why I'm a big fan of Axler's Linear Algebra Done Right. The book's emphasis is on the concepts behind the calculations rather than the calculations.

I could never learn mathematics that way, and goodness knows, school systems in both Europe and America have tried to teach it to me that way. What I understand of mathematics today has mostly been achieved through autodidaction.

Some of us cannot, repeat can not go from the abstract to the empirical; I'm one of those people, who have to go from the empirical to the abstract instead. I need to see the mechanics of it, because I learn by observing the pattern. If I cannot make out the pattern, I cannot comprehend the abstraction.

Take UNIX manual pages for example: the first thing I go to after reading the SYNOPSIS is the EXAMPLES section (and since most GNU/Linux manual pages have no EXAMPLES sections, it's a product which is useless to me, unlike UNIX). The more examples the EXAMPLES section entails, the faster I'm able to grasp the concept. Same with http://matrixmultiplication.xyz/, if I could have learned matrix multiplication that way, visually, instead of having to do it in my head, it would have been far easier. The other way around, it was a slow, painful torture, and to this present day, I cannot multiply the matrices in my head, or without these visualisations to remind me of the rules: they're too complicated for me to keep in my head.

The point I'm trying to make is that not everyone learns the same way, and our brains do not process the information in the same way, even if the final result, understanding of the concept, is identical. A lot of abstract concepts which are difficult to reliably repeat, or whose outcome is either non-deterministic or unclear, we do not even understand the same way, hence opinions often differ by a small or large margin. Don't assume that the learning technique which works for you would work for someone else. That's a major failure of most pedagogical approaches, with the exception of perhaps Montessori and Fröbel. Unlike Montessori and Fröbel, most pedagogical approaches force a uniform way of learning, except that a human brain does not learn in a uniform manner, differing from individual to individual instead. Teaching should be a highly individualized approach.

Re:Matrix Multiplication by Sharlin on Saturday November 26, 2016 @08:13AM (#13043336)
But surely these sort of meaningless examples with randomized numbers like at the site aren't that useful? I mean, a "real-world" example of matrix multiplication would be having a proper translation or rotation matrix and then visualizing how it maps a point to its image.
Re:Matrix Multiplication by nilkn on Saturday November 26, 2016 @05:11PM (#13046194)
That demonstrates multiplication of a matrix with a vector which is being rotated, but multiplication of two matrices corresponds to composition of the corresponding operators.

This is actually pretty instructive. For instance, rotations in three-dimensional space do not commute in general; hence neither does matrix multiplication.

Re:Matrix Multiplication by Sharlin on Sunday November 27, 2016 @08:10AM (#13048950)
Technically matrix-vector multiplication is just a special case of matrix-matrix-multiplication, but I take your point. Indeed it would be illuminating to see how exactly matrix multiplication composes two transformations.
Re:Matrix Multiplication by tnecniv on Friday November 25, 2016 @01:51PM (#13038970)
I can see why he discourages it. It prevents understanding why a matrix is singular. I often find students who use it as the main justification for singularity without further understanding singularity -- namely that it occurs when a linear map sends things to a lower dimensional space than it accepts.
Re:Matrix Multiplication by bandrami on Friday November 25, 2016 @09:36AM (#13036961)
Bingo. We did matrices in high school and even through a first linear algebra course in undergrad I got more or less competent at the mechanics of matrix multiplication without ever having any sense of why anyone would want to do this or why these rules, as opposed to some other set of rules that were equally formally valid, were of any interest. I could even tell you what the eigenvectors of a matrix were but had no sense of what that actually meant in terms of a linear transformation that matrix represented. Linear algebra is probably the area of math that is both universally important and completely skimped on by our education system.
Re:Matrix Multiplication by t3nary on Friday November 25, 2016 @09:43AM (#13037000)
I feel very similar. Do you have any recommendations for resources to learn about why matrix multiplication is defined that way?
Re:Matrix Multiplication by bandrami on Friday November 25, 2016 @10:15AM (#13037253)
"All the mathematics you missed but need to know for graduate school"[1] helped me a lot (and, in fact, I had and did).

Once I had finished that, Cullen's "Matrices and linear transformations"[2] was really helpful too. But I wouldn't do Cullen if you're still, as I was, floundering with the concepts of why you're doing this in the first place. It's great once you have those concepts down.

[1]: https://www.amazon.com/All-Mathematics-You-Missed-Graduate/d...

[2]: http://store.doverpublications.com/0486663280.html

Re:Matrix Multiplication by fsloth on Friday November 25, 2016 @10:26AM (#13037341)
Garrity's book looks exactly what I've been looking for for brushing up on basic math skills after a decade of fairly low-brow work after my MSc. Thanks for the reference!
Re:Matrix Multiplication by bandrami on Friday November 25, 2016 @10:46AM (#13037466)
Hope it helps! It definitely got me through the first year of grad school...
Re:Matrix Multiplication by cousin_it on Friday November 25, 2016 @10:16AM (#13037262)
Let's say you have a system with N possible states, evolving in discrete steps. At each step, the system has some probability of switching from any state to any other state. That gives you an NxN matrix of switching probabilities. For example, if the system always stays in the same state as it started, the switching probabilities are an identity matrix (1 on the diagonal and 0 everywhere else).

Now let's see what happens after two steps. If the system started out in state i, what's the probability that after two steps it will end up in state k? Well, it's the sum over all possible paths. In other words, the sum of probabilities of i->j->k for all possible j. In other words, the sum of p_{ij} times p_{jk} for j from 1 to N. But that's exactly the definition of multiplying a matrix by itself.

Now it should be easy to understand that whenever you have matrices that represent transformations of some object, composing transformations will correspond to multiplying matrices.

Re:Matrix Multiplication by darrickw on Friday November 25, 2016 @09:49AM (#13037046)
Check out this series of videos "The Essence of Linear Algebra"[1] for a really powerful visual and intuitive explanation. It starts with vectors and builds to matrix multiplication and further to several other topics.

[1]: https://www.youtube.com/playlist?list=PLZHQObOWTQDPD3MizzM2x...

Re:Matrix Multiplication by ww2 on Friday November 25, 2016 @10:46AM (#13037471)
If you compose two linear transformations into one step, and apply distributive property, you get the matrix multiplication rule.

http://math.stackexchange.com/questions/31725/intuition-behi...

Re:Matrix Multiplication by jperras on Friday November 25, 2016 @10:55AM (#13037546)
Axler's book, "Linear Algebra Done Right", is widely considered to be one of the best texts on linear algebra that focuses less on the mechanics and more on the structure of linear operators on vector spaces.

http://linear.axler.net/

Re:Matrix Multiplication by CalChris on Friday November 25, 2016 @12:08PM (#13038124)
Yes, and the abridged version (no proofs, examples, and exercises) is downloadable for free. He avoids determinants altogether (well, until the 10th chapter).

http://linear.axler.net/LinearAbridged.html

Re:Matrix Multiplication by 77pt77 on Friday November 25, 2016 @09:49AM (#13037047)
In particular understanding that conjugation by another matrix is just a coordinate/frame transformation is crucial.

Relying to much on explicit coordinates many times obfuscates what's going on.

Re:Matrix Multiplication by coherentpony on Friday November 25, 2016 @10:11AM (#13037217)
Is that true for non-square matrices?
Re:Matrix Multiplication by lkasjdklasdj on Friday November 25, 2016 @10:29AM (#13037364)
Conjugation only makes sense for square matrices. More generally, left and right multiplication correspond to coordinate transformations of the output and input space, respectively.
Re:Matrix Multiplication by coherentpony on Saturday November 26, 2016 @03:19PM (#13045639)
If A is n x n and P is n x p then P is not square but P^T A P is well-defined.
Re:Matrix Multiplication by zubspace on Friday November 25, 2016 @04:08PM (#13039841)
Is there something like this regarding homogeneous coordinates and the projective plane?

It's strange. Somehow I have now problems whatsoever regarding the use of 4-component vectors. As long as the z component stays one, I'm all set. But lately I'm trying to understand the construction of projection matrices and how to apply the knowledge of homogeneous coordinates, for example shadow mapping.

Parallel lines suddenly intersect? 3D space is just a projective plane? Now everything is all weird...

Re:Matrix Multiplication by thfuran on Sunday November 27, 2016 @07:40PM (#13052610)
Not sure if you already are aware, but you didn't use the term, so I figured it might help to point out that what you are talking about is projective geometry. I'm not sure of any good texts, though it sounds like you might want one more focused on graphics than projective geometry purely in the abstract.
Re:Matrix Multiplication by ooqr on Sunday November 27, 2016 @09:24AM (#13049284)
Homogenous coordinates have accrued really overcomplicated language around the very simple idea that something appears half as large twice as far away.
Re:Matrix Multiplication by c3534l on Friday November 25, 2016 @10:11PM (#13041491)
It at least cuts down on the amount of time you have to explain the mechanics of it. This is more intuitive to memorize than an algorithm composed of bullet-point instructions. For intuition, I highly recommend https://www.youtube.com/watch?v=kjBOesZCoqc - I think both the intuition and practicing the details should be learned.
Re:Matrix Multiplication by lisper on Friday November 25, 2016 @11:09PM (#13041667)
You'd probably like this then:

https://graphicallinearalgebra.net