Introduction to Proof via Linear Algebra Many universities offer a transition course from computational courses like Calculus to proof-oriented courses like Abstract Algebra. Such courses often go by a name like "Introduction to Proof" or "Transition to Higher Mathematics". They typically contain an introduction to first-order logic (conditionals, conjunctions, negations, quantifiers, etc.) as well as various methods of proof (contradiction, induction, etc.).

I'm hoping to find a text for a first course in linear algebra that fills the role of a "transition course" by deliberately incorporating first-order logic and proof techniques as part of the instruction.

The text should be accessible to students with two semesters of Calculus (roughly the basics of single-variable differentiation, integration, and infinite series). In particular, the overwhelming majority of students will have never written a formal proof and will have extremely limited exposure to logic and set theory.

Ideally, the author would discuss these topics just as they are needed in the treatment of linear algebra (as opposed to supposing the reader is familiar with them already). For example, the author might have a digression on proof by contradiction just prior to using it in some proof about linear independence.

Less ideal (but still acceptable) would be a text that at the very least makes use of all the relevant ideas from first-order logic and proof techniques that one expects from a transition course. Hopefully, the progression of such a text would be such that the instructor could use a supplemental text to discuss, say, proof by contradiction just as it is about to make its first appearance in the text.
Linear Algebra - As an Introduction to Abstract Mathematics (direct link to pdf here) seems like a good shout. I haven't looked through it thoroughly, but the following bold claim is made in the intro:


  In the setting of Linear Algebra, you will be introduced to abstraction. As the theory
  of Linear Algebra is developed, you will learn how to make and use definitions and how
  to write proofs. 


Indeed, at the end of each chapter are special "Proof-Writing Exercises".
My favourite book in linear algebra, as the first course, would be Schaum's Outline of Linear Algebra by Seymor Lipschutz.

Pros: Starts with an intense use of algorithms: vector, matrices, elimination, linear equations, etc. This comprehends the first three chapters. The rest of the book is the basic material for a first time course in linear algebra. It starts with axiomatic definition of vector spaces, then linear transformations, then connections between linear transformations and matrices, then inner products, diagonalization, Jordan's canonical form, etc. It has a plethora of examples.

Cons: It is highly devoted to algorithm, so mathematicians don't like that a much (This methods, though, are essential: imagine a mathematician incapable of solving a $3 \times 3$ ODE or being unable to diagonalize a small size matrix). Proofs are delayed to the end of each chapter, so the theorems are stated, then there are plenty of examples and then, at the end, the proofs.