Skip to main content
Logo image

A First Course in Linear Algebra

Robert A. Beezer

Section PD Properties of Dimension

Once the dimension of a vector space is known, then the determination of whether or not a set of vectors is linearly independent, or if it spans the vector space, can often be much easier. In this section we will state a workhorse theorem and then apply it to the column space and row space of a matrix. It will also help us describe a super-basis for Cm.
🔗

Subsection GT Goldilocks’ Theorem

We begin with a useful theorem that we will need later, and in the proof of the main theorem in this subsection. This theorem says that we can extend linearly independent sets, one vector at a time, by adding vectors from outside the span of the linearly independent set, all the while preserving the linear independence of the set.
🔗

Proof.

Suppose S={v1,v2,v3,…,vm} and begin with a relation of linear dependence on S′,
a1v1+a2v2+a3v3+⋯+amvm+am+1w=0.
There are two cases to consider. First suppose that am+1=0. Then the relation of linear dependence on S′ becomes
a1v1+a2v2+a3v3+⋯+amvm=0
and by the linear independence of the set S, we conclude that a1=a2=a3=⋯=am=0. So all of the scalars in the relation of linear dependence on S′ are zero.
In the second case, suppose that am+1≠0. Then the relation of linear dependence on S′ becomes
am+1w=−a1v1−a2v2−a3v3−⋯−amvmw=−a1am+1v1−a2am+1v2−a3am+1v3−⋯−amam+1vm.
This equation expresses w as a linear combination of the vectors in S, contrary to the assumption that w∉⟨S⟩, so this case leads to a contradiction.
The first case yielded only a trivial relation of linear dependence on S′ and the second case led to a contradiction. So S′ is a linearly independent set since any relation of linear dependence is trivial.
In the story Goldilocks and the Three Bears, the young girl Goldilocks visits the empty house of the three bears while out walking in the woods. One bowl of porridge is too hot, the other too cold, the third is just right. One chair is too hard, one too soft, the third is just right. So it is with sets of vectors — some are too big (linearly dependent), some are too small (they do not span), and some are just right (bases). Here is Goldilocks’ Theorem.
🔗

Proof.

Let B be a basis of V. Since dim⁡(V)=t, Definition B and Theorem BIS imply that B is a linearly independent set of t vectors that spans V.
  1. Suppose to the contrary that S is linearly independent. Then B is a smaller set of vectors that spans V. This contradicts Theorem SSLD.
  2. Suppose to the contrary that S does span V. Then B is a larger set of vectors that is linearly independent. This contradicts Theorem SSLD.
  3. Suppose to the contrary that S does not span V. Then we can choose a vector w such that w∈V and w∉⟨S⟩. By Theorem ELIS, the set S′=S∪{w} is again linearly independent. Then S′ is a set of m+1=t+1 vectors that are linearly independent, while B is a set of t vectors that span V. This contradicts Theorem SSLD.
  4. Suppose to the contrary that S is linearly dependent. Then by Theorem DLDS (which can be upgraded, with no changes in the proof, to the setting of a general vector space), there is a vector in S, say vk that is equal to a linear combination of the other vectors in S. Let S′=S∖{vk}, the set of “other” vectors in S. Then it is easy to show that V=⟨S⟩=⟨S′⟩. So S′ is a set of m−1=t−1 vectors that spans V, while B is a set of t linearly independent vectors in V. This contradicts Theorem SSLD.
There is a tension in the construction of a basis. Make a set too big and you will end up with relations of linear dependence among the vectors. Make a set too small and you will not have enough raw material to span the entire vector space. Make a set just the right size (the dimension) and you only need to have linear independence or spanning, and you get the other property for free. These roughly-stated ideas are made precise by Theorem G.
🔗
The structure and proof of this theorem also deserve comment. The hypotheses seem innocuous. We presume we know the dimension of the vector space in hand, then we mostly just look at the size of the set S. From this we get big conclusions about spanning and linear independence. Each of the four proofs relies on ultimately contradicting Theorem SSLD, so in a way we could think of this entire theorem as a corollary of Theorem SSLD. (See Proof Technique LC.) The proofs of the third and fourth parts parallel each other in style: introduce w using Theorem ELIS or toss vk using Theorem DLDS. Then obtain a contradiction to Theorem SSLD.
🔗
Theorem G is useful in both concrete examples and as a tool in other proofs. We will use it often to bypass verifying linear independence or spanning.
🔗

Example BPR. Bases for Pn, reprised.

In Example BP we claimed that
B={1,x,x2,x3,…,xn}C={1,1+x,1+x+x2,1+x+x2+x3,…,1+x+x2+x3+⋯+xn}
were both bases for Pn (Example VSP). Suppose we had first verified that B was a basis, so we would then know that dim⁡(Pn)=n+1. The size of C is n+1, the right size to be a basis. We could then verify that C is linearly independent. We would not have to make any special efforts to prove that C spans Pn, since Theorem G would allow us to conclude this property of C directly. Then we would be able to say that C is a basis of Pn also.

Example BDM22. Basis by dimension in M22.

In Example DSM22 we showed that
B={[−2110],[−2001]}
is a basis for the subspace Z of M22 (Example VSM) given by
Z={[abcd]|2a+b+3c+4d=0,−a+3b−5c−d=0}.
This tells us that dim⁡(Z)=2. In this example we will find another basis. We can construct two new matrices in Z by forming linear combinations of the matrices in B.
2[−2110]+(−3)[−2001]=[222−3]3[−2110]+1[−2001]=[−8331]
Then the set
C={[222−3],[−8331]}
has the right size to be a basis of Z. Let us see if it is a linearly independent set. The relation of linear dependence
a1[222−3]+a2[−8331]=O[2a1−8a22a1+3a22a1+3a2−3a1+a2]=[0000]
leads to the homogeneous system of equations whose coefficient matrix
[2−82323−31]
row-reduces to
[10010000].
So with a1=a2=0 as the only solution, the set is linearly independent. Now we can apply Theorem G to see that C also spans Z and therefore is a second basis for Z.

Example SVP4. Sets of vectors in P4.

In Example BSP4 we showed that
B={x−2,x2−4x+4,x3−6x2+12x−8,x4−8x3+24x2−32x+16}
is a basis for W={p(x)|p∈P4, p(2)=0}. So dim⁡(W)=4.
The set
{3x2−5x−2,2x2−7x+6,x3−2x2+x−2}
is a subset of W (check this) and it happens to be linearly independent (check this, too). However, by Theorem G it cannot span W.
The set
{3x2−5x−2,2x2−7x+6,x3−2x2+x−2,−x4+2x3+5x2−10x,x4−16}
is another subset of W (check this) and Theorem G tells us that it must be linearly dependent.
The set
{x−2,x2−2x,x3−2x2,x4−2x3}
is a third subset of W (check this) and is linearly independent (check this). Since it has the right size to be a basis, and is linearly independent, Theorem G tells us that it also spans W, and therefore is a basis of W.
A simple consequence of Theorem G is the observation that a proper subspace has strictly smaller dimension than its parent vector space. Hopefully this may seem intuitively obvious, but it still requires proof, and we will cite this result later.
🔗

Proof.

Suppose that dim⁡(U)=m and dim⁡(V)=t. Then U has a basis B of size m. If m>t, then by Theorem G, B is linearly dependent, which is a contradiction. If m=t, then by Theorem G, B spans V. Then U=⟨B⟩=V, also a contradiction. All that remains is that m<t, which is the desired conclusion.
The final theorem of this subsection is an extremely powerful tool for establishing the equality of two sets that are subspaces. Notice that the hypotheses include the equality of two integers (dimensions) while the conclusion is the equality of two sets (subspaces). It is the extra “structure” of a vector space and its dimension that makes possible this huge leap from an integer equality to a set equality.
🔗

Proof.

The hypothesis that U⊆V allows for two cases. Either U⊊V or U=V.
If U⊊V, then the hypotheses of Theorem PSSD are met and we have a contradiction to the hypothesis that dim⁡(U)=dim⁡(V).
Since the first case is impossible, the second case must always occur, which is our desired conclusion.
🔗

Subsection RT Ranks and Transposes

We now prove one of the most surprising theorems about matrices. Notice the paucity of hypotheses compared to the precision of the conclusion.
🔗

Proof.

Suppose we row-reduce A to the matrix B in reduced row-echelon form, and B has r nonzero rows. The quantity r tells us three things about B: the number of leading 1’s, the number of nonzero rows and the number of pivot columns. For this proof we will be interested in the latter two.
Theorem BRS and Theorem BCS each has a conclusion that provides a basis, for the row space and the column space, respectively. In each case, these bases contain r vectors. This observation makes the following go.
r(A)=dim⁡(C(A))Definition ROM=rTheorem BCS=dim⁡(R(A))Theorem BRS=dim⁡(C(At))Theorem CSRST=r(At)Definition ROM
Jacob Linenthal helped with this proof.
This says that the row space and the column space of a matrix have the same dimension, which should be very surprising. It does not say that column space and the row space are identical. Indeed, if the matrix is not square, then the sizes (number of slots) of the vectors in each space are different, so the sets are not even comparable.
🔗
It is not hard to construct by yourself examples of matrices that illustrate Theorem RMRT, since it applies equally well to any matrix. Grab a matrix, row-reduce it, count the nonzero rows or the number of pivot columns. That is the rank. Transpose the matrix, row-reduce that, count the nonzero rows or the pivot columns. That is the rank of the transpose. The theorem says the two will be equal. Every time. Here is an example anyway.
🔗

Example RRTI. Rank, rank of transpose, Archetype I.

Archetype I has a 4×7 coefficient matrix which row-reduces to
[140021−300101−3500012−660000000]
so the rank is 3. Row-reducing the transpose yields
[100−3170101270011370000000000000000]
demonstrating that the rank of the transpose is also 3.
🔗

Subsection DFS Dimension of Four Subspaces

That the rank of a matrix equals the rank of its transpose is a fundamental and surprising result. However, applying Theorem FS we can easily determine the dimension of all four fundamental subspaces associated with a matrix.
🔗

Proof.

If A row-reduces to a matrix in reduced row-echelon form with r nonzero rows, then the matrix C of extended echelon form (Definition EEF) will be an r×n matrix in reduced row-echelon form with no zero rows and r pivot columns (Theorem PEEF). Similarly, the matrix L of extended echelon form (Definition EEF) will be an m−r×m matrix in reduced row-echelon form with no zero rows and m−r pivot columns (Theorem PEEF).
dim⁡(N(A))=dim⁡(N(C))Theorem FS=n−rTheorem BNS dim⁡(C(A))=dim⁡(N(L))Theorem FS=m−(m−r)Theorem BNS=r dim⁡(R(A))=dim⁡(R(C))Theorem FS=rTheorem BRS dim⁡(L(A))=dim⁡(R(L))Theorem FS=m−rTheorem BRS
There are many different ways to state and prove this result, and indeed, the equality of the dimensions of the column space and row space is just a slight expansion of Theorem RMRT. However, we have restricted our techniques to applying Theorem FS and then determining dimensions with bases provided by Theorem BNS and Theorem BRS. This provides an appealing symmetry to the results and the proof.
🔗
In Section S we saw two general constructions (Theorem SIIS, Theorem SSIS) that combined two subspaces to create new subspaces. The four subspaces involved have dimensions related to each other, a result that will can be very useful.
🔗

Proof.

Let A={x1,x2,x3,…,xk} be a basis of the subspace U∩V. Because U and V are each individually subspaces of U+V, we can extend A via repeated applications of Theorem ELIS to form bases for U and V. To wit, let {u1,u2,u3,…,ur}⊆U be a set of vectors such that C={x1,x2,x3,…,xk,u1,u2,u3,…,ur} is a basis for U. Similarly, let {v1,v2,v3,…,vs}⊆V be a set of vectors such that D={x1,x2,x3,…,xk,v1,v2,v3,…,vs} is a basis for V. Note that we have implicitly determined (by Definition D) that dim⁡(U∩V)=k, dim⁡(U)=k+r, and dim⁡(V)=k+s.
With this setup, we claim that
B={x1,x2,x3,…,xk,u1,u2,u3,…,ur,v1,v2,v3,…,vs}
is a basis for the subspace U+V. We establish spanning first. Suppose that x∈U+V, so x=u+v where u∈U and v∈V. Since u∈U we can express u as a linear combination of the vectors in C, and since v∈V we can express v as a linear combination of the vectors in D. So
x=u+v=(a1x1+a2x2+a3x3+⋯+akxk+c1u1+c2u2+c3u3+⋯+crur)+(b1x1+b2x2+b3x3+⋯+bkxk+d1v1+d2v2+d3v3+⋯+dsvs)=(a1+b1)x1+(a2+b2)x2+(a3+b3)x3+⋯+(ak+bk)xk+c1u1+c2u2+c3u3+⋯+crur+d1v1+d2v2+d3v3+⋯+dsvs
and we see that x is a linear combination of the vectors of B, so B spans U+V by Definition SSVS.
To establish linear independence, we begin with a relation of linear independence (Definition RLD) on B,
a1x1+a2x2+a3x3+⋯+akxk+c1u1+c2u2+c3u3+⋯+crur+d1v1+d2v2+d3v3+⋯+dsvs=0.
We rearrange this equation, and give a name to the common vector that is the expression on either side of the equality.
w=a1x1+a2x2+a3x3+⋯+akxk+c1u1+c2u2+c3u3+⋯+crur=−d1v1+d2v2+d3v3+⋯+dsvs.
From the first expression we see that w is a linear combination of the basis C and so w∈U. The second expression shows that w is a linear combination of the basis D and so w∈V. Thus, w∈U∩V and we can express w as a linear combination of the vectors of A. We use this observation, and another expression for w from just above, to form an equality that we then rearrange,
w=e1x1+e2x2+e3x3+⋯+ekxk=−d1v1+d2v2+d3v3+⋯+dsvs0=e1x1+e2x2+e3x3+⋯+ekxk+d1v1+d2v2+d3v3+⋯+dsvs
Aha! Finally, we have a relation of linear dependence on a linearly independent set (D) and so by Definition LI we conclude that
e1=e2=e3=⋯=ek=d1=d2=d3=⋯=ds=0
and in particular, w=0.
Now, if we return to the equation where we first introduced w, it becomes
0=w=a1x1+a2x2+a3x3+⋯+akxk+c1u1+c2u2+c3u3+⋯+crur.
Now, this is a relation of linear dependence on a linearly independent set (C) and so by Definition LI we conclude that
a1=a2=e3=⋯=ak=c1=c2=c3=⋯=cr=0
and we have determined that all of the scalars in our original relation of linear dependence on B are zero, and so by Definition LI, we see that B is linearly independent.
Having established that B is a basis, we can say that dim⁡(U+V)=k+r+s. So we have our result,
dim⁡(U+V)=k+r+s=(k+r)+(k+s)−k=dim⁡(U)+dim⁡(V)−dim⁡(U∩V).
An alternate version of the conclusion of Theorem SID is
🔗
dim⁡(U+V)+dim⁡(U∩V)=dim⁡(U)+dim⁡(V)
which has an appealing symmetry. Exercise PD.T60 is highly related to this theorem.
🔗
🔗

Sage DMS. Dimensions of Matrix Subspaces.

The theorems in this section about the dimensions of various subspaces associated with matrices can be tested easily in Sage. For a large arbitrary matrix, we first verify Theorem RMRT, followed by the four conclusions of Theorem DFS.
🔗

Reading Questions PD Reading Questions

3. Calculate dimensions of the 4 subspaces.

Row-reduce the matrix A to reduced row-echelon form. Without any further computations, compute the dimensions of the four subspaces, (a) N(A), (b) C(A), (c) R(A) and (d) L(A).
🔗
A=[1−12851114−102−3−8−620184]
🔗
🔗
🔗

Exercises PD Exercises

C40.

Determine if the set T={x2−x+5,4x3−x2+5x,3x+2} spans the vector space of polynomials with degree 4 or less, P4. (Compare the solution to this exercise with Solution C40.1.)
🔗
Solution.
The vector space P4 has dimension 5 by Theorem DP. Since T contains only 3 vectors, and 3<5, Theorem G tells us that T does not span P4.
🔗

T05.

Trivially, if U and V are two subspaces of W with U=V, then dim⁡(U)=dim⁡(V). Combine this fact, Theorem PSSD, and Theorem EDYES all into one grand combined theorem. You might look to Theorem PIP for stylistic inspiration. (Notice this problem does not ask you to prove anything. It just asks you to roll up three theorems into one compact, logically equivalent statement.)
🔗
🔗

T10.

Prove the following theorem, which could be viewed as a reformulation of parts (3) and (4) of Theorem G, or more appropriately as a corollary of Theorem G (Proof Technique LC).
🔗
Suppose V is a vector space and S is a subset of V such that the number of vectors in S equals the dimension of V. Then S is linearly independent if and only if S spans V.
🔗
🔗

T15.

Suppose that A is an m×n matrix and let min(m,n) denote the minimum of m and n. Prove that r(A)≤min(m,n). (If m and n are two numbers, then min(m,n) stands for the number that is the smaller of the two. For example min(4,6)=4.)
🔗
🔗

T20.

Suppose that A is an m×n matrix and b∈Cm. Prove that the linear system LS(A,b) is consistent if and only if r(A)=r([A|b]).
🔗
Solution.
Proof.
(⇒) 
Suppose first that LS(A,b) is consistent. Then by Theorem CSCS, b∈C(A). This means that C(A)=C([A|b]) and so it follows that r(A)=r([A|b]).
(⇐) 
Adding a column to a matrix will only increase the size of its column space, so in all cases, C(A)⊆C([A|b]). However, if we assume that r(A)=r([A|b]), then by Theorem EDYES we conclude that C(A)=C([A|b]). Then b∈C([A|b])=C(A) so by Theorem CSCS, LS(A,b) is consistent.
🔗

T25.

Suppose that V is a vector space with finite dimension. Let W be any subspace of V. Prove that W has finite dimension.
🔗
🔗

T33.

Part of Exercise B.T50 is the half of the proof where we assume the matrix A is nonsingular and prove that a set is a basis. In Solution T50.1 we proved directly that the set was both linearly independent and a spanning set. Shorten this part of the proof by applying Theorem G. Be careful, there is one subtlety.
🔗
Solution.
By Theorem DCM we know that Cn has dimension n. So by Theorem G we need only establish that the set C is linearly independent or a spanning set. However, the hypotheses also require that C be of size n. We assumed that B={x1,x2,x3,…,xn} had size n, but there is no guarantee that C={Ax1,Ax2,Ax3,…,Axn} will have size n. There could be some “collapsing” or “collisions.”
Suppose we establish that C is linearly independent. Then C must have n distinct elements or else we could fashion a nontrivial relation of linear dependence involving duplicate elements.
If we instead choose to prove that C is a spanning set, then we could establish the uniqueness of the elements of C quite easily. Suppose that Axi=Axj. Then
A(xi−xj)=Axi−Axj=0.
Since A is nonsingular, we conclude that xi−xj=0, or xi=xj, contrary to our description of B.
🔗

T60.

Suppose that W is a vector space with dimension 5, and U and V are subspaces of W, each of dimension 3. Prove that U∩V contains a nonzero vector. State a more general result.
🔗
Solution 1.
Let {u1,u2,u3} and {v1,v2,v3} be bases for U and V (respectively). Then, the set {u1,u2,u3,v1,v2,v3} is linearly dependent, since Theorem G says we cannot have 6 linearly independent vectors in a vector space of dimension 5. So we can assert that there is a nontrivial relation of linear dependence,
a1u1+a2u2+a3u3+b1v1+b2v2+b3v3=0
where a1,a2,a3 and b1,b2,b3 are not all zero.
We can rearrange this equation as
a1u1+a2u2+a3u3=−b1v1−b2v2−b3v3
This is an equality of two vectors, so we can give this common vector a name, say w,
w=a1u1+a2u2+a3u3=−b1v1−b2v2−b3v3
This is the desired nonzero vector, as we will now show.
First, since w=a1u1+a2u2+a3u3, we can see that w∈U. Similarly, w=−b1v1−b2v2−b3v3, so w∈V. This establishes that w∈U∩V (Definition SI).
Is w≠0? Suppose not, in other words, suppose w=0. Then
0=w=a1u1+a2u2+a3u3
Because {u1,u2,u3} is a basis for U, it is a linearly independent set and the relation of linear dependence above means we must conclude that a1=a2=a3=0. By a similar process, we would conclude that b1=b2=b3=0. But this is a contradiction since a1,a2,a3,b1,b2,b3 were chosen so that some were nonzero. So w≠0.
How does this generalize? All we really needed was the original relation of linear dependence that resulted because we had “too many” vectors in W. A more general statement would be: Suppose that W is a vector space with dimension n, U is a subspace of dimension p and V is a subspace of dimension q. If p+q>n, then U∩V contains a nonzero vector.
Solution 2.
The previous solution to this exercise is reminiscent of techniques from the proof of Theorem SID. If we assume the theorem, then a solution becomes much more direct. The key observation is that the subspace U+V is a subspace of W and so cannot have dimension greater than 5, since a larger basis would violate Theorem G. So we have
dim⁡(U∩V)=dim⁡(U)+dim⁡(V)−dim⁡(U+V)Theorem SID=3+3−dim⁡(U+V)Hypothesis≥6−5=1Theorem G
So U∩V is a nontrivial subspace and so contains a nonzero vector.
🔗
🔗
You have attempted 1 of 4 activities on this page.
🔗
PrevTopNext