Appendix B. Proof Techniques

Mathematics depends on proof. A proof is a logical argument that establishes the truth of a statement from definitions, assumptions, and previously proved results.

Linear algebra contains computational procedures, but it is also a theoretical subject. Many important statements must be proved rather than merely observed from examples. A computation may suggest a pattern, but a proof explains why the pattern always holds.

This appendix presents the proof methods used throughout the book.

B.1 Statements and Definitions

A mathematical statement is a sentence that is either true or false.

For example,

2+3=5

is a true statement, while

2+3=6

is false.

Definitions introduce precise meanings for mathematical terms. A definition does not require proof. Instead, it establishes terminology.

For example:

A square matrix $A$ is invertible if there exists a matrix $B$ such that
$> AB = BA = I. >$

Once this definition is accepted, one may prove theorems about invertible matrices.

A theorem is a statement proved from definitions and previously known results.

A lemma is a theorem mainly used to prove another theorem.

A corollary is a result that follows quickly from a theorem.

B.2 Structure of a Proof

A proof should proceed in a clear sequence of steps.

A typical proof contains:

Part	Purpose
Assumptions	State what is given
Goal	State what must be shown
Argument	Use definitions and known facts
Conclusion	State that the goal has been proved

For example:

Let $u,v,w$ be vectors in a vector space $V$ . Prove that
$> u+(v+w) = (u+v)+w. >$

Proof:

Vector addition in a vector space satisfies the associative law by definition. Therefore,

u+(v+w) = (u+v)+w.

Hence the statement holds.

This proof is short because associativity is already part of the definition of a vector space.

B.3 Direct Proof

A direct proof begins with assumptions and proceeds logically to the desired conclusion.

Example

Prove that the sum of two odd integers is even.

Proof:

Let $a$ and $b$ be odd integers. Then there exist integers $m$ and $n$ such that

a = 2m+1, \qquad b = 2n+1.

Therefore,

a+b = (2m+1)+(2n+1) = 2(m+n+1).

Since $m+n+1$ is an integer, $a+b$ is even.

Thus the sum of two odd integers is even.

The proof succeeds because it begins with the definition of odd integers and manipulates the resulting expressions.

B.4 Proof by Contrapositive

An implication

P \implies Q

is logically equivalent to its contrapositive

\neg Q \implies \neg P.

Sometimes the contrapositive is easier to prove than the original statement.

Example

Prove:

If a real number $x$ satisfies $x^2 \neq 0$ , then $x \neq 0$ .

Instead of proving this directly, prove the contrapositive.

Contrapositive:

If $x=0$ , then $x^2=0$ .

Proof:

If $x=0$ , then

x^2 = 0^2 = 0.

Therefore the contrapositive holds, so the original statement holds.

In linear algebra, contraposition often appears in proofs about injectivity, independence, and invertibility.

B.5 Proof by Contradiction

Proof by contradiction assumes the statement is false and derives an impossibility.

The contradiction shows that the assumption of falsity cannot hold.

Example

Prove:

There is no rational number whose square equals $2$ .

Proof:

Assume, for contradiction, that

\sqrt{2} = \frac{p}{q}

for integers $p$ and $q$ with no common factor.

Squaring gives

2 = \frac{p^2}{q^2},

p^2 = 2q^2.

Thus $p^2$ is even, which implies $p$ is even. Write

p = 2k.

Then

4k^2 = 2q^2,

q^2 = 2k^2.

Thus $q^2$ is even, so $q$ is even.

Hence both $p$ and $q$ are even, contradicting the assumption that they have no common factor.

Therefore $\sqrt{2}$ is irrational.

Contradiction proofs are common in dimension arguments and existence theorems.

B.6 Proof by Cases

A proof by cases divides a problem into separate possibilities and proves the statement in each case.

Example

Prove that for every integer $n$ ,

n(n+1)

is even.

Proof:

Every integer is either even or odd.

Case 1: $n$ is even.

Then

n = 2k

for some integer $k$ . Therefore,

n(n+1) = 2k(n+1),

which is even.

Case 2: $n$ is odd.

Then

n = 2k+1

for some integer $k$ . Therefore,

n+1 = 2k+2 = 2(k+1),

which is even. Hence,

n(n+1)

is even.

Since both cases give the same conclusion, the statement holds for all integers $n$ .

B.7 Existence Proofs

An existence proof shows that at least one object satisfies a given property.

There are two common forms.

Type	Method
Constructive	Explicitly build the object
Nonconstructive	Prove existence indirectly

Constructive Example

Prove that there exists a real number whose square is $9$ .

Proof:

The number $3$ satisfies

3^2 = 9.

Therefore such a number exists.

Nonconstructive Example

Suppose a theorem proves that every polynomial of odd degree has a real root. Such a proof may establish existence without giving an explicit formula for the root.

Linear algebra often uses constructive existence proofs. For example, Gaussian elimination explicitly constructs solutions to systems of equations.

B.8 Uniqueness Proofs

A uniqueness proof shows that only one object satisfies a property.

The usual method is:

Assume two objects satisfy the property.
Show they must be equal.

Example

Prove that the zero vector in a vector space is unique.

Proof:

Suppose $0$ and $0'$ are both zero vectors.

Since $0$ is a zero vector,

0 + 0' = 0'.

Since $0'$ is a zero vector,

0 + 0' = 0.

Therefore,

0 = 0'.

Hence the zero vector is unique.

Uniqueness arguments appear frequently in decompositions, coordinate systems, and bases.

B.9 Proof by Induction

Mathematical induction proves statements indexed by the natural numbers.

To prove a statement $P(n)$ for all integers $n \geq 1$ , one proves:

Base case: $P(1)$ .
Inductive step: $P(k) \implies P(k+1)$ .

Example

Prove:

1+2+\cdots+n = \frac{n(n+1)}{2}.

Base case:

For $n=1$ ,

1 = \frac{1(2)}{2}.

Thus the statement holds for $n=1$ .

Inductive step:

Assume

1+2+\cdots+k = \frac{k(k+1)}{2}.

Then

1+2+\cdots+k+(k+1) = \frac{k(k+1)}{2} + (k+1).

Factor:

= \frac{k(k+1)+2(k+1)}{2} = \frac{(k+1)(k+2)}{2}.

Thus the formula holds for $k+1$ .

Therefore, by induction, the formula holds for all $n \geq 1$ .

Induction is important in linear algebra for proofs involving matrix powers, recursive algorithms, and determinant formulas.

B.10 Counterexamples

A universal statement

\forall x,\ P(x)

is disproved by finding a single counterexample.

Example

Consider the statement:

Every square matrix is invertible.

This is false.

Counterexample:

A = \begin{bmatrix} 1 & 2 \\ 2 & 4 \end{bmatrix}.

The second row is a multiple of the first row, so

\det(A)=0.

Therefore $A$ is not invertible.

One counterexample is enough to disprove a universal claim.

B.11 Necessary and Sufficient Conditions

Suppose $P$ and $Q$ are statements.

P \implies Q,

then $Q$ is necessary for $P$ , and $P$ is sufficient for $Q$ .

For example:

If a matrix is invertible, then its determinant is nonzero.

Thus:

Statement	Role
Invertible	Sufficient
Nonzero determinant	Necessary

If both implications hold,

P \iff Q,

then each condition is both necessary and sufficient for the other.

Many major theorems in linear algebra consist of equivalent conditions.

For example, for an $n \times n$ matrix $A$ , the following are equivalent:

Condition
$A$ is invertible
$\det(A)\neq0$
The columns of $A$ are linearly independent
The equation $Ax=b$ has a unique solution for every $b$

Such equivalence theorems are central to the subject.

B.12 Forward and Backward Reasoning

In problem solving, one may reason forward from assumptions or backward from the desired conclusion.

Forward reasoning

Start from what is known and derive consequences.

Backward reasoning

Ask what conditions would guarantee the desired conclusion.

Example

Suppose we want to prove

A^2 = I

for a matrix $A$ .

Backward reasoning suggests checking whether multiplying $A$ by itself simplifies naturally. One may then inspect the structure of $A$ or compute directly.

In practice, good proofs often combine both directions.

B.13 Equality Proofs

To prove two sets are equal, prove mutual inclusion:

A=B

means:

A \subseteq B \quad \text{and} \quad B \subseteq A.

Example

Prove:

A \cap (B \cup C) = (A \cap B)\cup(A \cap C).

Proof:

First show

A \cap (B \cup C) \subseteq (A \cap B)\cup(A \cap C).

Let

x \in A \cap (B \cup C).

Then

x \in A

and

x \in B \cup C.

Thus $x\in B$ or $x\in C$ .

If $x\in B$ , then

x \in A\cap B.

If $x\in C$ , then

x \in A\cap C.

Hence

x \in (A\cap B)\cup(A\cap C).

Now prove the reverse inclusion similarly.

Therefore the sets are equal.

Set equality arguments appear frequently in subspace proofs.

B.14 Proofs in Linear Algebra

Linear algebra proofs usually involve:

Object	Typical method
Vector spaces	Verify axioms
Subspaces	Check closure properties
Linear independence	Analyze linear combinations
Spanning sets	Construct representations
Linear maps	Verify linearity
Bases	Combine spanning and independence
Matrix identities	Use algebraic manipulation
Eigenvalues	Analyze characteristic equations

Example: Subspace Proof

Prove that the set

$$
W = \left{
\begin{bmatrix}
x \
y \
0
\end{bmatrix}: x,y \in \mathbb{R} \right} $$

is a subspace of $\mathbb{R}^3$ .

Proof:

The zero vector belongs to $W$ :

\begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix} \in W.

Let

u= \begin{bmatrix} x_1 \\ y_1 \\ 0 \end{bmatrix}, \qquad v= \begin{bmatrix} x_2 \\ y_2 \\ 0 \end{bmatrix} \in W.

Then

u+v = \begin{bmatrix} x_1+x_2 \\ y_1+y_2 \\ 0 \end{bmatrix} \in W.

Now let $c \in \mathbb{R}$ . Then

cu = \begin{bmatrix} cx_1 \\ cy_1 \\ 0 \end{bmatrix} \in W.

Therefore $W$ is closed under addition and scalar multiplication. Hence $W$ is a subspace.

B.15 Common Errors in Proofs

Several mistakes occur frequently.

Assuming what must be proved

A proof cannot begin by assuming the conclusion.

Checking only examples

Examples may illustrate a statement, but they do not prove universal truth.

Using undefined notation

Every symbol should have a clear meaning.

Ignoring quantifiers

Statements involving “for all” and “there exists” require careful interpretation.

Confusing implication and equivalence

Proving

P \implies Q

does not prove

Q \implies P.

B.16 Reading Proofs

Reading proofs is a skill that develops gradually.

A good strategy is:

Identify the assumptions.
Identify the conclusion.
Locate the main idea.
Check each logical step.
Determine which definitions are used.

In linear algebra, many proofs become easier once the relevant definitions are written explicitly.

For example, when proving linear independence, begin with the definition:

c_1v_1 + \cdots + c_nv_n = 0.

When proving injectivity of a linear map, begin with

T(u)=T(v).

The definition often determines the entire structure of the proof.

B.17 Writing Proofs

Good proofs are precise, organized, and economical.

Useful guidelines include:

Guideline	Purpose
State assumptions clearly	Establish context
Use complete sentences	Improve readability
Introduce notation carefully	Prevent ambiguity
Explain key transitions	Clarify logic
Avoid unnecessary detail	Maintain focus
End with the conclusion	Signal completion

A proof is both a logical argument and a mathematical explanation. It should convince the reader that the statement is true and explain why it is true.

B.18 Summary

Proof techniques are tools for establishing mathematical truth.

Method	Main idea
Direct proof	Deduce conclusion from assumptions
Contrapositive	Prove equivalent reverse implication
Contradiction	Derive impossibility
Cases	Separate possibilities
Induction	Extend from one integer to the next
Existence proof	Show an object exists
Uniqueness proof	Show only one object exists
Counterexample	Disprove universal statement

Linear algebra uses these methods constantly. Computational skill alone is not enough. The subject also requires logical structure, precise definitions, and rigorous argument.