Proof Strategies in Linear Algebra, linear algebra II lesson

Draw the two coordinate axes of the plane. Each axis is a subspace, yet $(1, 0)$ and $(0, 1)$ both lie in their union while their sum $(1, 1)$ lies on neither axis. Does that one picture show that a union of two subspaces is never a subspace, or only that it is not always one? The answer depends on exactly how the claim is worded. This lesson sets out the logic that decides what counts as evidence, from quantifiers and converses to direct proofs, counterexamples and induction.

Key terms

Universal claim

Definition A universal claim says that a statement $P(x)$ is true for every object $x$ in a specified set $S$ , written

\forall x \in S,\ P(x).

An existence claim says that $P(x)$ is true for at least one $x \in S$ , written $\exists x \in S,\ P(x)$ . A universal claim is proved by an argument that applies to an arbitrary member of $S$ . Checking examples proves it only when $S$ is finite and every member is checked. It is disproved by a counterexample, which is one particular $x \in S$ for which $P(x)$ is false. An existence claim is proved by producing one member of $S$ with the property, or by an argument showing that such a member must exist.

In plain words “Every” asks for a reason that covers all allowed cases at once, and a single failing case is enough to refute it. “Some” asks only for one good case.

Example Consider the universal claim that for all subspaces $U$ and $W$ of a real vector space $V$ , the union $U \cup W$ is a subspace. In $\mathbb{R}^2$ let $U$ be the horizontal axis and $W$ the vertical axis. Both are subspaces, so the hypothesis of the claim is met. The vectors $(1, 0) \in U$ and $(0, 1) \in W$ lie in the union, but their sum $(1, 1)$ has two nonzero coordinates and lies on neither axis. So the union is not closed under addition, and this one counterexample disproves the claim. It does not prove the opposite universal claim, that a union of two subspaces is never a subspace. That claim is false too, because if $U \subseteq W$ then $U \cup W = W$ is a subspace.

Hypothesis and conclusion

Definition An implication “if $P$ , then $Q$ ”, written $P \Rightarrow Q$ , has hypothesis $P$ and conclusion $Q$ . It is false exactly when $P$ is true and $Q$ is false. Most theorems are universal implications of the form “for every $x \in S$ , if $P(x)$ then $Q(x)$ ”, often with several hypotheses. A proof assumes the hypotheses and uses them, together with definitions and results already proved, to reach the conclusion. It may not assume the conclusion, or anything equivalent to it, along the way.

In plain words The hypotheses are what you may use, and the conclusion is what you have to show. Every step should rest on a hypothesis, a definition or an earlier result, and the conclusion should appear only at the end.

Example Let $T \colon V \to W$ be a linear map between vector spaces over $\mathbb{F}$ , where $\mathbb{F}$ is $\mathbb{R}$ or $\mathbb{C}$ . The claim is that if $u, v \in \ker T$ , then $u + v \in \ker T$ . The hypotheses are that $T$ is linear, $Tu = 0$ and $Tv = 0$ , and the conclusion is $T(u + v) = 0$ . Linearity and the two equations give

T(u + v) = Tu + Tv = 0 + 0 = 0.

The linearity hypothesis does real work here. The function $f(x) = x^2 - 1$ on $\mathbb{R}$ is not linear, and both $1$ and $-1$ are zeros of it, but $f(1 + (-1)) = f(0) = -1$ . So the zero set of a function that is not linear need not be closed under addition.

Converse

Definition The converse of the implication $P \Rightarrow Q$ is the implication $Q \Rightarrow P$ . It is a different statement, and knowing that one of the two is true says nothing about the other. When both hold we write $P \Leftrightarrow Q$ and say that $P$ holds if and only if $Q$ holds. A proof of such a statement must establish each direction. The converse should not be confused with the contrapositive, “if not $Q$ , then not $P$ ”, which is always equivalent to $P \Rightarrow Q$ .

In plain words Reversing the arrow makes a new claim, which needs its own proof or its own counterexample.

Example For a linear map $T \colon V \to W$ over $\mathbb{F}$ , consider the implication “if $T$ is injective, then $\ker T = \{0\}$ ”. If $v \in \ker T$ , then $Tv = 0 = T0$ , and injectivity gives $v = 0$ . The converse, “if $\ker T = \{0\}$ , then $T$ is injective”, needs a separate argument. Suppose $Tu = Tv$ . Linearity gives $T(u - v) = Tu - Tv = 0$ , so $u - v \in \ker T = \{0\}$ and $u = v$ . Both directions hold, so $T$ is injective if and only if $\ker T = \{0\}$ . By contrast, the implication “if $v \in \mathbb{R}^2$ is the zero vector, then its second coordinate is $0$ ” is true, while its converse fails for $v = (1, 0)$ .

Negation of a quantified statement

Definition The negation of a statement is true exactly when the statement is false. Negation switches each quantifier,

\begin{aligned} &\neg\,(\forall x \in S,\ P(x)) \\ &\qquad \iff \exists x \in S,\ \neg P(x), \\[0.6em] &\neg\,(\exists x \in S,\ P(x)) \\ &\qquad \iff \forall x \in S,\ \neg P(x), \end{aligned}

where $\neg$ means “not”. With several quantifiers, switch each one in turn from left to right and negate the statement that follows them. The negation of an implication $P \Rightarrow Q$ is ” $P$ and not $Q$ ”. So the negation of “for every $x \in S$ , if $P(x)$ then $Q(x)$ ” is “there is an $x \in S$ for which $P(x)$ is true and $Q(x)$ is false”, and a counterexample is exactly such an $x$ .

In plain words To deny that something always happens, find one case where it fails. To deny that something ever happens, show that it fails in every case. A case where the hypothesis fails says nothing against an implication.

Example A linear map $T \colon U \to V$ is surjective when for every $v \in V$ there exists $u \in U$ with $Tu = v$ . The negation says that there exists $v \in V$ such that $Tu \ne v$ for every $u \in U$ . For the map $T \colon \mathbb{R} \to \mathbb{R}^2$ given by $T(t) = (t, 0)$ , the target $v = (0, 1)$ is such a vector, because every output has second coordinate $0$ . One missed target is enough, and there is no need to show that every target is missed.

Direct proof

Definition A direct proof of “for every $x \in S$ , if $P(x)$ then $Q(x)$ ” lets $x$ be an arbitrary member of $S$ , assumes $P(x)$ , and reaches $Q(x)$ through a chain of steps, each justified by a hypothesis, a definition, an axiom or a result already proved. Arbitrary means that nothing is assumed about $x$ beyond membership in $S$ and the hypothesis $P(x)$ . The same goes for scalars, which range over all of $\mathbb{F}$ , including negative numbers and, when $\mathbb{F} = \mathbb{C}$ , numbers that are not real.

In plain words Name a general object, use only what you are told about it, and arrive at the claim. Because nothing special was chosen, the argument covers every case at once.

Example Let $U$ and $W$ be subspaces of a vector space $V$ over $\mathbb{F}$ . We prove that $U \cap W$ is a subspace, using the fact that a subset of $V$ is a subspace exactly when it contains $0$ and contains every combination $au + bv$ of its vectors $u, v$ with scalars $a, b \in \mathbb{F}$ . The zero vector lies in $U$ and in $W$ , so it lies in $U \cap W$ . Now let $u, v \in U \cap W$ and $a, b \in \mathbb{F}$ be arbitrary. Since $u$ and $v$ lie in the subspace $U$ , the combination $au + bv$ lies in $U$ . Since they also lie in $W$ , it lies in $W$ . Hence $au + bv \in U \cap W$ . No particular vectors or scalars were chosen, so the argument covers every pair of vectors and every pair of scalars.

Proof by induction

Definition Let $P(k)$ be a statement for each integer $k \ge k_0$ . Suppose the base case $P(k_0)$ is true, and the induction step holds, meaning that for every integer $k \ge k_0$ , if $P(k)$ is true then $P(k + 1)$ is true. Then $P(k)$ is true for every integer $k \ge k_0$ . In the induction step, $P(k)$ is called the induction hypothesis. It is assumed for one arbitrary $k$ , and the step must work for every such $k$ .

In plain words The base case starts a chain, and the step carries the truth from each integer to the next. Checking many values of $k$ is evidence, not proof, because it never supplies the step.

Example Let $N \in \mathbb{F}^{n \times n}$ with $N^2 = 0$ . We prove that $(I + N)^k = I + kN$ for every integer $k \ge 0$ . The base case $k = 0$ reads $I = I + 0N$ , which is true. For the step, assume $(I + N)^k = I + kN$ for some $k \ge 0$ . Then

\begin{aligned} (I + N)^{k+1} &= (I + N)^k (I + N) \\[0.4em] &= (I + kN)(I + N) \\[0.4em] &= I + N + kN + kN^2 \\[0.4em] &= I + (k + 1)N, \end{aligned}

where the last step uses $N^2 = 0$ . For the matrix $N$ with rows $(0, 1)$ and $(0, 0)$ the result says that every power of a shear adds up the shear amounts,

\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}^k = \begin{bmatrix} 1 & k \\ 0 & 1 \end{bmatrix}.

The hypothesis $N^2 = 0$ cannot be dropped. With $N = I$ and $k = 2$ the left side is $(2I)^2 = 4I$ , while the right side is $3I$ .

Check yourself

State the converse of “if a list of vectors in $\mathbb{R}^2$ contains the zero vector, then the list is linearly dependent”. Is the original statement true? Is the converse?

Show the answer

The converse is “if a list of vectors in $\mathbb{R}^2$ is linearly dependent, then it contains the zero vector”. The original is true. Give the zero vector the coefficient $1$ and every other vector the coefficient $0$ , and this nontrivial combination equals $0$ . The converse is false. The list $(1, 0), (2, 0)$ is dependent, because $2(1, 0) - (2, 0) = 0$ , but neither vector is zero.

Write the negation of the claim “for every $A \in \mathbb{R}^{2 \times 2}$ , if $A^2 = 0$ then $A = 0$ ”. Which of the two statements is true?

Show the answer

The negation is “there exists $A \in \mathbb{R}^{2 \times 2}$ with $A^2 = 0$ and $A \ne 0$ ”. A common mistake is to write “for every $A$ , if $A^2 = 0$ then $A \ne 0$ ”, which keeps the universal quantifier and the implication. The negation is the true statement. The matrix

A = \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix}

is not zero, and $A^2 = 0$ . So the original claim is false, and this matrix is a counterexample to it.

Let $T \colon V \to V$ be a linear map on a vector space over $\mathbb{F}$ , and let $U$ be a subspace with $Tu \in U$ for every $u \in U$ . Prove by induction that $T^k u \in U$ for every $u \in U$ and every integer $k \ge 0$ , where $T^0 = I$ . Then explain why checking $Tu \in U$ for one vector $u \in U$ does not in general establish the hypothesis on $T$ .

Show the answer

Let $P(k)$ be the statement that $T^k u \in U$ for every $u \in U$ . For the base case, $T^0 u = u$ lies in $U$ for every $u \in U$ . For the step, assume $P(k)$ for some $k \ge 0$ and let $u \in U$ be arbitrary. By the induction hypothesis $T^k u \in U$ , and applying the hypothesis on $T$ to the vector $T^k u$ gives

T^{k+1} u = T(T^k u) \in U.

That proves $P(k + 1)$ , so $P(k)$ holds for every $k \ge 0$ .

One vector is not enough in general, because $T$ may send another vector of $U$ outside $U$ . Take $T(x, y) = (x, x)$ on $\mathbb{R}^2$ and let $U$ be the horizontal axis. The zero vector passes the test, since $T0 = 0 \in U$ , but $T(1, 0) = (1, 1)$ is not in $U$ . Even a nonzero vector can pass while the hypothesis fails. On $\mathbb{R}^3$ let $U$ be the $xy$ -plane and $T(x, y, z) = (x, 0, y)$ . Then $T(1, 0, 0) = (1, 0, 0)$ lies in $U$ , but $T(0, 1, 0) = (0, 0, 1)$ does not. What linearity does allow is checking a list that spans $U$ . If $Tu_j \in U$ for every vector $u_j$ of such a list, then every combination $\sum_j c_j u_j$ is sent to $\sum_j c_j Tu_j \in U$ .

Proof Strategies in Linear Algebra

Video 1

Key terms

Universal claim

Hypothesis and conclusion

Converse

Negation of a quantified statement

Direct proof

Proof by induction

Check yourself

How this lesson connects

Used later in