Two Ways to Prove an Implication
An implication has the form “if \(P\), then \(Q\).” In a linear algebra proof, \(P\) might say that a list is independent, while \(Q\) says that its length is at most the dimension of the space. There are two useful strategies when proving such claims indirectly. Contraposition replaces the implication with the equivalent statement “if not \(Q\), then not \(P\).” Contradiction assumes the hypotheses and also assumes that the desired conclusion is false, then derives an impossibility. These approaches can look similar, but they organize the assumptions differently.
The two strategies use different starting points. In a contrapositive proof, the original hypothesis \(P\) is not assumed: the goal is to show that failure of the conclusion forces failure of the hypothesis. In a contradiction proof, \(P\) remains in force, and we temporarily assume that \(Q\) fails. In either strategy, make the assumptions visible. A conclusion such as “this is impossible” is convincing only when the proof identifies which assumptions make it impossible.
We will use the Rank-Nullity Theorem for a linear map \(T:V\to W\) between finite-dimensional vector spaces over a field \(\mathbb{F}\): \(\dim V=\operatorname{rank}T+\operatorname{nullity}T\). Here \(\operatorname{rank}T=\dim(\operatorname{im}T)\) and \(\operatorname{nullity}T=\dim(\ker T)\). We also use that a subspace of a finite-dimensional space cannot have dimension greater than the space containing it.
Contraposition: Too Many Vectors Force Dependence
Consider the implication that an independent list in a finite-dimensional vector space cannot have more vectors than the dimension of that space. Rather than begin by assuming independence, it is often simpler to prove the contrapositive: a list longer than the dimension must be dependent.
Proof. We prove the contrapositive. Assume \(p>n\), and define \(S:\mathbb{F}^{p}\to V\) by \(S(c_1,\dots,c_p)^{\top}=\sum_{j=1}^{p}c_j\mathbf{v}_j\). Its image is a subspace of \(V\), so \(\operatorname{rank}S\le n\). By rank-nullity, \(\operatorname{nullity}S=p-\operatorname{rank}S\ge p-n>0\). Thus \(\ker S\) contains a nonzero coefficient vector \((c_1,\dots,c_p)^{\top}\), which means \(\sum_{j=1}^{p}c_j\mathbf{v}_j=\mathbf{0}\) with not all coefficients zero. The list is dependent. We have shown that \(p>n\) implies dependence, the contrapositive of the stated claim. \(\square\)
The key move is turning a list into a linear map: the coefficients are the input, and their linear combination of the list is the output. A nonzero vector in the kernel is exactly a nontrivial dependence relation. The inequality \(p>n\) matters because it makes the nullity strictly positive; without that strict inequality, this argument would not force a nonzero kernel vector.
Contraposition: Injectivity Restricts Dimensions
A linear map \(T:V\to W\) is injective if \(T(\mathbf{v})=T(\mathbf{w})\) implies \(\mathbf{v}=\mathbf{w}\). Equivalently, \(\ker T=\{\mathbf{0}\}\): if \(T(\mathbf{v})=T(\mathbf{w})\), linearity gives \(T(\mathbf{v}-\mathbf{w})=\mathbf{0}\); if the kernel contains only \(\mathbf{0}\), then \(\mathbf{v}-\mathbf{w}=\mathbf{0}\). Conversely, injectivity forces any vector in the kernel to equal \(\mathbf{0}\).
Proof. We prove the contrapositive. Assume \(\dim V>\dim W\). Since \(\operatorname{im}T\) is a subspace of \(W\), \(\operatorname{rank}T\le\dim W\). Rank-nullity then gives \(\operatorname{nullity}T=\dim V-\operatorname{rank}T\ge\dim V-\dim W>0\). Therefore \(\ker T\) contains a nonzero vector, so \(T\) is not injective. This proves that \(\dim V>\dim W\) implies \(T\) is not injective, which is the contrapositive of the theorem. \(\square\)
This proof depends on finite dimensionality: it uses dimensions and rank-nullity for both spaces. It also depends on strict inequality. If \(\dim V=\dim W\), the displayed lower bound only gives \(\operatorname{nullity}T\ge0\), which does not establish a nonzero kernel.
Worked Example: A Map from a Larger Space
Consider \(T:\mathbb{R}^{3}\to\mathbb{R}^{2}\) defined by \(T(x,y,z)=(x+z,y-z)\). Since \(3>2\), the theorem predicts that \(T\) cannot be injective. Find a nonzero kernel vector and check it.
To find the kernel, set both coordinates of the output equal to zero:
Taking \(z=1\) gives \(x=-1\) and \(y=1\). Thus \(\mathbf{v}=(-1,1,1)^{\top}\ne\mathbf{0}\). Substitution verifies the claim: \(T(-1,1,1)=(-1+1,1-1)=(0,0)\). So \(\mathbf{v}\in\ker T\), and \(T\) is not injective. The dimensions predicted a nonzero kernel; the computation identifies one particular vector in it.
Contradiction: Images of Independent Vectors
Contradiction is especially useful when the unwanted conclusion gives a relation that can be passed through a linear map. For example, if the images of independent vectors were dependent, their dependence relation would produce a kernel vector. Injectivity rules out that possibility.
Proof. Assume \(T\) is injective and the original list is independent. For contradiction, suppose the image list is dependent. Then there are scalars \(c_1,\dots,c_p\), not all zero, such that \(\sum_{j=1}^{p}c_jT(\mathbf{v}_j)=\mathbf{0}\). By linearity, this is \(T\!\left(\sum_{j=1}^{p}c_j\mathbf{v}_j\right)=\mathbf{0}\). Injectivity implies that the only vector mapped to \(\mathbf{0}\) is \(\mathbf{0}\), so \(\sum_{j=1}^{p}c_j\mathbf{v}_j=\mathbf{0}\). Independence of the original list forces every \(c_j=0\), contradicting the choice that they were not all zero. Therefore the image list is independent. \(\square\)
Notice the distinct jobs of the assumptions. Linearity lets the sum pass inside \(T\). Injectivity turns a zero image into a zero input. Independence then rules out a nontrivial zero combination. If any one of these steps is missing, the contradiction has not been established.
Worked Example: Checking Independence After a Map
Define \(T:\mathbb{R}^{2}\to\mathbb{R}^{3}\) by \(T(x,y)=(x+y,2x-y,x-2y)^{\top}\). Show that \(T\) is injective and that it carries the standard basis vectors to an independent list.
First solve \(T(x,y)=\mathbf{0}\). The first two coordinates give \(x+y=0\) and \(2x-y=0\). The first equation gives \(y=-x\); substituting into the second gives \(2x-(-x)=3x=0\), so \(x=0\) and \(y=0\). Thus the kernel contains only \(\mathbf{0}\), which verifies injectivity.
The standard basis vectors are \(\mathbf{e}_1=(1,0)^{\top}\) and \(\mathbf{e}_2=(0,1)^{\top}\). Applying \(T\) gives \(T(\mathbf{e}_1)=(1,2,1)^{\top}\) and \(T(\mathbf{e}_2)=(1,-1,-2)^{\top}\). To check their independence directly, suppose \(aT(\mathbf{e}_1)+bT(\mathbf{e}_2)=\mathbf{0}\). Coordinate by coordinate, this says \(a+b=0\), \(2a-b=0\), and \(a-2b=0\). The first equation gives \(b=-a\), and the second then gives \(3a=0\), so \(a=b=0\). Substitution into the third equation also gives \(0=0\). The only relation is trivial, confirming that the two image vectors are independent, as the theorem predicts.
Contradiction: A Spanning List of the Right Length
Another useful contradiction begins with a spanning list. If a list of exactly \(n\) vectors spans an \(n\)-dimensional space, it must also be independent. Otherwise, a nontrivial relation would create a nonzero kernel for the map that sends coefficients to combinations. But spanning makes that map onto the whole space, whose dimension is already \(n\).
Proof. Define \(S:\mathbb{F}^{n}\to V\) by sending a coefficient vector to the corresponding linear combination of the spanning list. Because the list spans \(V\), \(S\) is onto, so \(\operatorname{im}S=V\) and \(\operatorname{rank}S=n\). For contradiction, suppose the list is dependent. Then a nonzero coefficient vector maps to \(\mathbf{0}\), so \(\operatorname{nullity}S\ge1\). Rank-nullity would give \(n=\operatorname{rank}S+\operatorname{nullity}S\ge n+1\), which is impossible. The list is independent. If \(n=0\), the list is empty and has no nontrivial coefficient relation, so the conclusion also holds. \(\square\)
Worked Example: A Spanning List in R³
Let \(\mathbf{v}_1=(1,0,1)^{\top}\), \(\mathbf{v}_2=(0,1,1)^{\top}\), and \(\mathbf{v}_3=(1,1,0)^{\top}\). First verify that these vectors span \(\mathbb{R}^{3}\). Then verify that they are independent.
For any \((r,s,t)^{\top}\in\mathbb{R}^{3}\), choose \(x=(r-s+t)/2\), \(y=(-r+s+t)/2\), and \(z=(r+s-t)/2\). Then \(x+z=r\), \(y+z=s\), and \(x+y=t\). Therefore \((r,s,t)^{\top}=x\mathbf{v}_1+y\mathbf{v}_2+z\mathbf{v}_3\), so the list spans. For a check, \(x+z=(r-s+t+r+s-t)/2=r\); likewise \(y+z=s\) and \(x+y=t\).
Now suppose \(a\mathbf{v}_1+b\mathbf{v}_2+c\mathbf{v}_3=\mathbf{0}\). The coordinates give \(a+c=0\), \(b+c=0\), and \(a+b=0\). The first two equations yield \(a=-c\) and \(b=-c\); substituting into the third gives \(-2c=0\), hence \(c=0\) and then \(a=b=0\). The list is independent. In this calculation, assuming a relation and deriving that every coefficient is zero rules out the possibility of a nontrivial relation.
Common Pitfall: Confusing a Contrapositive with a Converse
For the claim “if \(T:V\to W\) is injective, then \(\dim V\le\dim W\),” the contrapositive is “if \(\dim V>\dim W\), then \(T\) is not injective.” It is not “if \(T\) is not injective, then \(\dim V>\dim W\).” That last statement reverses the implication and is not equivalent to the original claim.
For a concrete check, take \(T:\mathbb{R}^{2}\to\mathbb{R}^{2}\) given by \(T(x,y)=(x,0)\). The nonzero vector \((0,1)^{\top}\) lies in its kernel because \(T(0,1)=(0,0)\), so \(T\) is not injective. Yet \(\dim\mathbb{R}^{2}=\dim\mathbb{R}^{2}\), not \(\dim V>\dim W\). The original implication and its contrapositive remain valid; the mistaken converse fails.
Before finishing an indirect proof, name the assumption responsible for each decisive step. Does dependence supply nonzero coefficients? Does injectivity force a kernel vector to be zero? Does spanning make a map onto? Does rank-nullity produce a strict positive nullity? Stating these links precisely is what turns an informal “contradiction” into a valid proof.
Check Your Understanding
For each question, identify the hypotheses before choosing a proof strategy.
- Write the contrapositive of: if a list of \(p\) vectors in an \(n\)-dimensional space is independent, then \(p\le n\).
- In the dimension proof for injectivity, where is finite dimensionality used?
- Which assumption turns \(T\!\left(\sum_j c_j\mathbf{v}_j\right)=\mathbf{0}\) into \(\sum_j c_j\mathbf{v}_j=\mathbf{0}\)?
- Why does a nonzero kernel vector for the coefficient map give a dependence relation?
- For a spanning list of \(n\) vectors in an \(n\)-dimensional space, what contradiction results if the list is assumed dependent?
