You are right: Linear Algebra is not just the "best" place to start. It's THE place to start.
Among all the books cited in Wikipedia - Linear Algebra, I would recommend:
- Strang, Gilbert, Linear Algebra and Its Applications (4th ed.)
Strang's book has at least two reasons for being recommended. First, it's extremely easy and short. Second, it's the book they use at MIT for the extremely good video Linear Algebra course you'll find in the link of Unreasonable Sin.
For a view towards applications (though maybe not necessarily your applications) and still elementary:
- B. Noble & J.W. Daniel: Applied Linear Algebra, Prentice-Hall, 1977
Linear algebra has two sides: one more "theoretical", the other one more "applied". Strang's book is just elementary, but perhaps "theoretical". Noble-Daniel is definitively "applied". The distinction from the two points of view relies in the emphasis they put on "abstract" vector spaces vs specific ones such as $\mathbb{R}^n$ or $\mathbb{C}^n$, or on matrices vs linear maps.
Maybe because of my penchant towards "pure" maths, I must admit that sometimes I find matrices somewhat annoying. They are funny, specific, whereas linear maps can look more "abstract" and "ethereal". But, for instance: I can't stand the proof that the matrix product is associative, whereas the corresponding associativity for the composition of (linear or non linear) maps is true..., well, just because it can't help to be true the first moment you write it down.
Anyway, at a more advanced level in the "theoretical" side you can use:
Greub, Werner H., Linear Algebra, Graduate Texts in Mathematics (4th ed.), Springer
Halmos, Paul R., Finite-Dimensional Vector Spaces, Undergraduate Texts in Mathematics, Springer
Shilov, Georgi E., Linear algebra, Dover Publications
In the "applied" (?) side, a book that I love and you'll appreciate if you want to study, for instance, the exponential of a matrix is Gantmacher.
And, at any time, you'll need to do a lot of exercises. Lipschutz's is second to none in this:
- Lipschutz, Seymour, 3,000 Solved Problems in Linear Algebra, McGraw-Hill
Enjoy! :-)