Diagram of a Proof

E. L. Lady

The role of an if/then statement in a proof is very different depending on whether it occurs in the hypothesis or the conclusion.

If the statement “If P then Q” is what has to be proved, then P gets added the hypothesis of the theorem (by using the word “Suppose”), and the goal of the proof is to prove Q.

If the statement “If P then Q” is part of what’s given, this tells us that if we want to prove Q, it will be sufficient to prove P. Therefore instead of directing our efforts to proving Q, we can concentrate on proving P.

Problem. Let A is an m × n matrix and let v_{1}, …, v_{p} be vectors in ℝ^{n}. Prove that if the vectors Av_{1}, …, Av_{p} in ℝ^{m} are linearly independent, then the vectors v_{1}, …, v_{p} are linearly independent.

Given: To be proved:

Av_{1}, …, Av_{p} are linearly independent. v_{1}, …, v_{p} are linearly independent.

If a_{1}Av_{1} + ⋯ + a_{p}Av_{p} = 0 then a_{1} = ⋯ = a_{p} = 0.

If a_{1}v_{1} + ⋯ + a_{p}v_{p} = 0
then a_{1} = ⋯ = a_{p} = 0.

Now a_{1}v_{1} + ⋯ + a_{p}v_{p} = 0 gets added to the list of what’s given by using the word “suppose.” And to succeed in proving a_{1} = ⋯ = a_{p} = 0 it is good enough to prove that

a_{1}Av_{1} + ⋯ + a_{p}Av_{p} = 0, so that becomes the new goal.

Revised given: Desired end of proof:

Av_{1}, …, Av_{p} are linearly independent. Suppose a_{1}v_{1} + ⋯ + a_{p}v_{p} = 0.

Thus a_{1}Av_{1} + ⋯ + a_{p}Av_{p} = 0. Therefore a_{1} = ⋯ = a_{p} = 0 because Av_{1}, …, Av_{p} are linearly independent.

It is now obvious how to complete the proof.

proof: Suppose that Av_{1}, …, Av_{p} are linearly independent. And suppose that a_{1}v_{1} + ⋯ + a_{p}v_{p} = 0. Multiplying both sides by A and invoking the distributive law yields a_{1}Av_{1} + ⋯ + a_{p}Av_{p} = 0. Therefore a_{1} = ⋯ = a_{p} = 0 because Av_{1}, …, Av_{p} are linearly independent.

We have shown that if a_{1}v_{1} + ⋯ + a_{p}v_{p} = 0 then a_{1}, …, a_{p} must all be 0. This shows that v_{1}, …, v_{p} are linearly independent. ✓