2.108 min read

Logic and Proof Techniques

Linear algebra proofs use precise logical reasoning. A statement is a claim that is either true or false. The converse of "If P then Q" is "If Q then P" — which may or may not be true.

The contrapositive of "If P then Q" is "If not Q then not P" — always logically equivalent to the original. Proving the contrapositive is a common technique when direct proof is hard.

Many key results in linear algebra are if and only if (iff) statements: both the statement and its converse are true. For example, "vectors are linearly dependent if and only if one is a linear combination of the others."

Formal View

Definition 2.10 — Logical Equivalences

For a statement "If

P

then

Q

" (written

P \Rightarrow Q

): \begin{itemize} \item Converse:

Q \Rightarrow P

(not necessarily true) \item Contrapositive:

\neg Q \Rightarrow \neg P

(always equivalent to

P \Rightarrow Q

) \item Biconditional:

P \Leftrightarrow Q

means

P \Rightarrow Q

and

Q \Rightarrow P

\end{itemize}

Why This Matters

Logical precision prevents errors when reasoning about abstract mathematical structures.

Algorithm correctness proofs use if-and-only-if characterizations
Invertible matrix theorem: 10 properties are mutually equivalent — each is iff the others
Solvability of Ax = b: solvable iff b is in the column span of A

Learning Resources

Mathematical proof techniques

Khan Academy

Introduction to logical reasoning and proof structure.

9 min

Quiz

Question 1

What is the contrapositive of "If $A$ is invertible, then $\det(A) \neq 0$ "?

Common Mistakes

Confusing the converse with the contrapositive — the converse is NOT guaranteed true, the contrapositive is.
Thinking "iff" can be proved by proving only one direction — you must prove both P→Q and Q→P.