Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A Programmer’s Intuition for Matrix Multiplication

betterexplained.com

Post reply on HN
Print view View original

11–20 of 95 posts

Re: A Programmer’s Intuition for Matrix Multiplication

#11

Post by WJW »

pmiller2 wrote: post #10
WJW wrote: post #3

Earlier quoted context omitted.

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 th…

> 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.

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.

Re: A Programmer’s Intuition for Matrix Multiplication

#13

Post by qppo »

WJW wrote: post #11
pmiller2 wrote: post #10

Earlier quoted context omitted.

> 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.

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.

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.

Re: A Programmer’s Intuition for Matrix Multiplication

#14

Post by scubbo »

WJW wrote: post #3
activatedgeek wrote: post #2

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.

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 th…

> 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)

Re: A Programmer’s Intuition for Matrix Multiplication

#15

Post by WJW »

michelpp wrote: post #7
WJW wrote: post #3

Earlier quoted context omitted.

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 th…

> 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…

Wow thanks for that example. I don't think I've seen that trick before; now I want do do more with graphs again.

Re: A Programmer’s Intuition for Matrix Multiplication

#16

Post by dan-robertson »

scubbo wrote: post #14
WJW wrote: post #3

Earlier quoted context omitted.

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 th…

> 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)

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

Re: A Programmer’s Intuition for Matrix Multiplication

#17

Post by zests »

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

Re: A Programmer’s Intuition for Matrix Multiplication

#18

Post by crdrost »

scubbo wrote: post #14
WJW wrote: post #3

Earlier quoted context omitted.

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 th…

> 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)

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.

Re: A Programmer’s Intuition for Matrix Multiplication

#19

Post by _Microft »

zests wrote: post #17

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 deri…

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

Post reply on HN