Rudin's equivalent in Linear Algebra I am looking for a linear algebra book which is as abstract as possible. But not an abstract algebra book. Something that is what Rudin's is for (beginning) analysis, that is, terse, rigorous and with beautiful exercises. 
For example: Intro to LA, by Curtis, and LA by Hoffman-Kunze. Opinions?
(I know there are already very similar questions around, but I felt they are not quite the same.)
 A: I am not sure what you are really looking for ("as abstract as possible" would suggest a Bourbakist approach, but this is not likely to involve many "beautiful exercises", though in part this depends on what you consider beautiful and what you consider and exercise). But since nobody else did yet, I'd like to mention Roger Godement's Cours d'Algèbre (1963), which would meet some of your criteria (and has been translated in English, too). It is not restricted to linear algebra, but those willing to admit some basic stuff about logic, set theory, groups, rings, and complex numbers can start reading at section 10 (modules and vector spaces), after which it is pretty much all stuff relevant to Linear Algebra until the final section 36 (Hermitian forms).
In the Bourbakist tradition vector spaces are of course introduced as a special case of modules over a ring. However the pursuit of generality is done only where it is painless, in the sense that it assumes the level of generality natural for the theorems being considered. This means for instance that in section 19 (the notion of dimension) the base ring is assumed to be a skew field (a.k.a. division ring; just "corps" in French where this term does not imply commutativity) whereas in the previous section (finiteness theorems) it was only assumed to be Noetherian or principal, depending on the exact results stated. In the lead-up to determinants (sections 21-24) the ring or field will be assumed commutative, and sections 34-36 where eigenvalue problems are discussed assume a true (commutative) field. One of the really nice things that I found in this approach is that not needlessly assuming commutativity forces some notational habits that I have found are useful even when working over rings that are commutative (for instance writing scalars at the opposite side of vectors than linear maps).
For the record, the book contains about 165 pages of exercises at the end, and though I cannot vouch for the beauty of all of them, there must be some nice ones to found there.
A: Axler's "Linear algebra done right" fits your criteria.  It's terse, it's rigorous, and it has beautiful exercises.
I would warn, however, that its focus is ultimately on the coordinate-free underpinnings and does little to prepare you for the computational aspects.
Katznelson and Katznelson's "A Terse Introduction to Linear Algebra" is a more "down to earth" alternative.
A: Edit: The order I presented the books is not a ranking simply the chronological order I went through them and this happened to be the order I wrote them in the review. I would recommend H&K.
I'll try to answer two questions in my reviews below: first, the quality of exposition and shortcomings, second the exercises. (full disclosure: This is my first time reviewing a maths book so apologies for any mediocrity and I also did not purchase them or borrow them from the library - I'll leave you to make your deductions).
1 LADR by Axler (recently brought out a 3rd edition but I haven't read this).
i) The pedagogical approach and concept of this book sounds good but in practice it was handled terribly. First, he treats polynomials as functions, rather than formally, and though this can be altered if you know what you're doing, it is hardly appropriate for a beginner. Secondly, he delays matrices far too long - I think after chapter 3, when linear maps were done, the concept of a matrix and determinant could have been beautifully integrated and streamlined into the exposition - needless to say this opportunity was wasted. Everything falls apart, material wise, after chapter 6, though I still got some benefit out of it.
ii) The problems are exceptionally easy. I mean this in reference to knowing the material of the book - as long as you can remember the material in the chapters, you will have no trouble doing them - I didn't spend more than a few seconds on each exercise before seeing what to do (except when coming up with counterexamples).
2 Hoffman & Kunze: 
i) Matrices are introduces straight away and it covers more material than Axler. I like the practicality of the book, though its terseness is not for everyone. Addresses many shortfalls of Axler.
ii) Good problem set, some challenging problems, many good 'routine' questions to drill concepts.
3 Halmos: Linear Algebra Problem Book (with reference to FDVS)
i) You actually answer questions to make your own exposition, though Halmos is as perfect as usual. Needs a secondary text for a first time student (FDVS would be good) and the material follows his classic examples format.
ii) Excellent, perfect set of questions. He goes over many examples, you are asked to prove many theorems and search for the kind of things beginning students trip up over. For instance, in the first chapter - an introduction to groups and fields- you are 'hand held' through showing how things like associativity etc. are non-trivial, which group axioms are independent, why it is important for multiplication and addition to interact 'sensibly', and then you can move all of this theory into the second chapter on vector spaces, again beautifully motivated with examples and uses the preceding material. This format goes on, and the questions are both illuminating and yet also I would say completely approachable for a student. There are even hints with solutions the following section, so you can peak at a hint, then the solution if really stuck. However, the questions are mainly easy, though about ten in the whole book did stump me.
Companion to LAPB: FDVS by Halmos.
A: I think Halmos's book "Finite Dimensional Vector Spaces" fits this description. 
A: The standard is Linear Algebra by Serge Lang.
A: Another book that fits your requirements is Lax's "Linear Algebra and its Applications"...and it has answers in the back of the book (quite rare for graduate-level texts).
It focuses on Linear Algebra as the study of linear transformations as opposed to matrix operations.
A: For beginners, most colleges use: David Lay's Linear Algebra & Applications. This book really teaches students how to do proof on matrices. 
