Sheldon Axler's "Linear Algebra Done Right" has my highest recommendation if you want expertise in linear algebra.
As a followup, Paolo Aluffi's "Algebra: Chapter Zero" is the best synthesizing text for abstract algebra for a beginning graduate student. The thing that makes it so amazing is the writing style: it introduces and demystifies category theory, and then discusses groups, rings, modules, linear algebra, fields, r-modules, and advanced topics (toward the end) with the unifying theme of how they work and relate as categories. It is very much a book that focuses on the why over the what and how. And there are many many many juicy exercises.
I would recommend against Spivak's Calculus on manifolds. It's too dense and too focused on advanced topics (unless you're an ivy league undergrad, you don't learn cohomology). That being said I don't have an analysis reference that fits your request.
As a CS person I can continue with book recommendations related to computing-related topics in math (computational algebraic geometry comes to mind). Let me know if you're interested.
Thanks. Axler's LADR is indeed fantastic, I have already worked through 1/2 of it. I'm really happy to see my opinion seconded. It's really short and precise. Some people seem to prefer Halmos' Finite Dimensional Vector Spaces, but I found the presentation less didactic. Perhaps it's also more of an upper division text, and I'm not there yet.
I was looking for a real analysis companion, perhaps baby Rudin. I was also wondering whether it'd make sense to proceed directly to real analysis, or to step down a bit and read something like Spivak's Calculus.
I'd also like to hear about recommendations at undergrad level in the fields of logic and set theory, geometry, combinatorics, and probability theory. Those would complete my basic math curriculum.
I've tried reading Rudin a couple times, but it's a bit of a slog. There are easier analysis texts. Abbott's Understanding Analysis is good, though a bit basic. I'm currently reading Terence Tao's Analysis I, which is very good if you're in the right frame of mind for it. The first 150 pages are spent building the real numbers from scratch, starting with set theory and the Peano axioms. You successively construct the naturals, the integers, the rationals, and then the reals (as equivalence classes of Cauchy sequences of rationals). It's fun to see how the sausage is made, but I can also admit that when I was just starting out in math I might have found this book unbearably tedious.
I'd actually like to hear about alternatives to Rudin. My undergrad analysis class used it, but it's lack of diagrams was particularly bothersome. I'd spend an hour digesting a rat's nest of a paragraph only to discover that the underlying concept was simple enough that even a rough sketch ought to be able to get the gist of it across in seconds.
Lovasz - Combinatorial Problems and Exercises (AMS Chelsea)
The classic probability book is Feller (2 vol), but it's absurdly priced. There's also Sidney Resnick's Probability Path and Adventures in Stochastic Processes. Grinstead & Snell - Introduction to Probability Theory is free[2], and there's also Chung's A Course in Probability Theory (Academic Press/Elsevier).
Dover publishes at least three good books on counterexamples and pathological cases: Counterexamples in {Analysis, Probability, Topology}
I have essentially taught myself everything I know about analysis to suit my needs (and I'm probably worse off for it). I really wish there were a book like "Analysis from a computational perspective," which I suppose is just numerical analysis but I have yet to find any books that suit me in that topic either. That being said, something like Christianini's "Introduction to Support Vector Machines" has doubled as a synthesizing text on basic functional analysis for me. My recommendation, if you're comfortable with proofs that you would see in abstract algebra, is to jump right into baby Rudin or any other undergrad-level analysis text. I view them all pretty much the same.
Likewise I essentially learned all the probability theory and combinatorics I know from people and scraps, so I can't recommend a synthesizing text.
Undergraduate geometry can be a mess, so you should know what you're looking for. There are three kinds of undergraduate geometry classes: 1. Euclid's Elements (ugh), 2. The hyperbolic version of Euclid's Elements (meh), and 3. The "Erlangen Programme" style, which involves studying geometry via group theory and linear algebra. As you can probably tell, my recommendation is to study the last, because you already know group theory and with the other two you'll spend a lot of time wondering whether you can apply some basic obvious fact to prove some other basic obvious fact. The Erlangen style also allows you to describe projective and hyperbolic geometry via linear algebra (as well as the Euclid way), which is far more useful. See, for example, my post on projective geometry for elliptic curves [1]. I went through all three styles, but the last unfortunately had no textbook.
I'm not a huge fan of logic/set theory, but again the best treatment I can see for basic logic is to view it as algebra. In that vein, Halmos's "Logic as Algebra" was all I needed, and the prose is superb. This book does not contain any real set theory (say, about higher cardinals), but it's nice and short.
Axler's book is a bit troublesome in inventing new terminology unnecessarily. There are also a number of minor errors, and while the abstract structure is fleshed out, it's not often well "motivated". I like the focus on theoretical instead of a matrix-first approach, I just think it's not well done.
As a followup, Paolo Aluffi's "Algebra: Chapter Zero" is the best synthesizing text for abstract algebra for a beginning graduate student. The thing that makes it so amazing is the writing style: it introduces and demystifies category theory, and then discusses groups, rings, modules, linear algebra, fields, r-modules, and advanced topics (toward the end) with the unifying theme of how they work and relate as categories. It is very much a book that focuses on the why over the what and how. And there are many many many juicy exercises.
I would recommend against Spivak's Calculus on manifolds. It's too dense and too focused on advanced topics (unless you're an ivy league undergrad, you don't learn cohomology). That being said I don't have an analysis reference that fits your request.
As a CS person I can continue with book recommendations related to computing-related topics in math (computational algebraic geometry comes to mind). Let me know if you're interested.