Hacker News Reader

Comment by capn_duck | Hacker News Reader

Yes I think this spreadsheet view is so detrimental and confusing for newcomers. I'm not even sure the analogy makes sense. The key part of linear algebra imo is the concept of linear transformations.

T(a+b)=T(a)+T(b)

Matrices just happen to be one way of expressing those transformations.

View on HN

And for extra magic, since every vector space has a basis, every linear transform between vector spaces with a finite basis can be represented by a finite matrix (https://en.m.wikipedia.org/wiki/Transformation_matrix). While this might feel obvious if you haven’t explored structure-preserving transforms between other types of algebraic objects (e.g. groups, rings), it is in fact very special. Learning this made me a lot more interested in linear algebra. It unifies the algebraic viewpoint that emphasizes things like the superposition property (T(x+y) = T(x) + T(y) and T(ax) = aT(x)) with the computational viewpoint that emphasizes calculations using matrices.

Since all linear transforms between vector spaces with a finite basis are finite matrices, the computational tools make it tractable to calculate properties of vector spaces that aren’t even decidable for e.g. groups. For a simple, but remarkable example: All finite vector spaces of the same dimension are isomorphic, but in general, it’s undecidable to compute if two finitely-presented groups are isomorphic.

> it’s undecidable to compute if two finitely-presented groups are isomorphic.

But (iirc) it is semidecidable, like the halting problem, and isomorphism is decidable for finitely presented abelian groups.

A semi-decidable problem is still pretty bad news from a computational perspective, but I agree that it's not the best example of what I was trying to illustrate. I was aiming for something dramatic and (somewhat) approachable, but ended up emphasizing properties of vector spaces as free abelian groups, rather than as vector spaces per se (which undermines my emphasis of the specialness of vector spaces in comparison to other algebraic structures). That said, to the best of my knowledge, the algorithms for computing whether two finitely-generated* abelian groups are isomorphic take advantage of the close relationship between finitely-generated abelian groups and vector spaces to compute the Smith normal form of matrices associated with the groups and then compare the normal forms. This takes roughly O(nmsublinear factors) for n x m matrices[0]. So to revise my example, vector spaces with a finite basis (and any finitely-generated free abelian group) can be compared for isomorphism in constant time and finitely-generated non-free abelian groups take time roughly quadratic in the number of generators, so there is a huge win there still.

Do you have a favorite example that highlights the unique computational properties of vector spaces?

*I don't know how this changes in the finitely-presented case, but I assume the extra constraint can be used to improve the performance of the algorithms. It's a lot easier to find asymptotic analysis of the finitely-generated case though and I don't see a way around dealing with the fact that it's still not free.

[0] - I'm basing this on Chapter 8 of https://cs.uwaterloo.ca/~astorjoh/diss2up.pdf, but this is a deep field in which I am not an expert, so if you are, I'd love to hear more.

Reply on news.ycombinator.com