Writing Short Proofs

So far we have mostly computed. From here on, many statements are about all matrices or all vectors of some kind, and we need a way to be sure of them. That way is a proof: a chain of small steps, each justified by a definition, the hypothesis, or a fact proved earlier. You met the logic of "if $P$, then $Q$" in geometry; here it meets linear independence and its friends.

Why it works

Why can't examples prove a general claim? A statement like "for all $n \times n$ matrices $A$ and $B$, $(AB)^{T} = B^{T}A^{T}$" covers infinitely many cases, and checking ten of them leaves infinitely many unchecked. A proof instead works with an arbitrary object: it names one that satisfies the hypothesis and uses only what every such object must satisfy. The other direction is easier: a single counterexample is enough to show a "for all" claim is false.

The shape of a direct proof

Write down what you are given, for arbitrary objects: "Let $\mathbf{u}$ and $\mathbf{v}$ be vectors with $A\mathbf{u} = \mathbf{0}$ and $A\mathbf{v} = \mathbf{0}$."
Write down what you must show, in terms of definitions: "We must show $A(\mathbf{u} + \mathbf{v}) = \mathbf{0}$."
Connect the two with small steps, each with a reason.

Worked example: A direct proof

Prove: if $\mathbf{u}$ and $\mathbf{v}$ are solutions of $A\mathbf{x} = \mathbf{0}$, then so is $\mathbf{u} + \mathbf{v}$.

Let $\mathbf{u}$ and $\mathbf{v}$ be any vectors with $A\mathbf{u} = \mathbf{0}$ and $A\mathbf{v} = \mathbf{0}$.
$A(\mathbf{u} + \mathbf{v}) = A\mathbf{u} + A\mathbf{v}$, because matrix-vector multiplication distributes over addition.
$= \mathbf{0} + \mathbf{0}$, by the hypothesis.
$= \mathbf{0}$. So $\mathbf{u} + \mathbf{v}$ is a solution. $\blacksquare$

Answer: Proved for every pair of solutions, not just one example.

Worked example: Disproving with a counterexample

True or false: if $AB = 0$ (the zero matrix), then $A = 0$ or $B = 0$.

Try simple matrices with many zeros. Let $A = \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix}$ and $B = \begin{bmatrix} 0 & 0 \\ 0 & 1 \end{bmatrix}$.
$AB = \begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix}$, yet neither $A$ nor $B$ is the zero matrix.
One counterexample is enough: the statement is false. (For numbers, $ab = 0$ forces $a = 0$ or $b = 0$; matrices are different.)

Answer: False.

Worked example: Proof by contrapositive

Prove: if $\{\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3\}$ is linearly independent, then $\{\mathbf{v}_1, \mathbf{v}_2\}$ is linearly independent.

The contrapositive of "if $P$, then $Q$" is "if not $Q$, then not $P$", and it is true exactly when the original is. Here: if $\{\mathbf{v}_1, \mathbf{v}_2\}$ is dependent, then $\{\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3\}$ is dependent.
Suppose $\{\mathbf{v}_1, \mathbf{v}_2\}$ is dependent: $c_1\mathbf{v}_1 + c_2\mathbf{v}_2 = \mathbf{0}$ with $c_1, c_2$ not both $0$.
Then $c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + 0\mathbf{v}_3 = \mathbf{0}$, and the weights are still not all $0$.
That is a dependence relation for the three vectors, so they are dependent. $\blacksquare$

Answer: Every subset of an independent set is independent.

Common mistake

Checking one example (or five) and calling it a proof. Examples are excellent for guessing what is true and for finding counterexamples, but they cannot show a "for all" statement. Quick test of your argument: does any step use a specific number from your example? If so, it is not yet a proof.

A related trap is proving the converse by accident. "If $A$ is invertible, then $A\mathbf{x} = \mathbf{0}$ has only the trivial solution" is a different statement from "if $A\mathbf{x} = \mathbf{0}$ has only the trivial solution, then $A$ is invertible" (the second needs $A$ to be square). Keep track of which way the arrow points.

Which kind of argument fits which claim.
To show…	Do this
"For all …, P"	Take an arbitrary object and prove P for it
"For all …, P" is false	Give one counterexample
"If P, then Q"	Assume P and derive Q, or assume not Q and derive not P
"P if and only if Q"	Prove both directions

Key idea

A proof handles an arbitrary case using definitions and earlier results, one justified step at a time. Examples suggest, a counterexample refutes, and only a proof establishes a statement about all cases.

Writing Short Proofs

The shape of a direct proof

Practice

Builds on

Leads to

Sources and further reading