6 ms·

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 ma

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.

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.