Dimension
Almost every vector space we have encountered has been infinite in size (an exception is Example VSS). But some are bigger and richer than others. Dimension, once suitably defined, will be a measure of the size of a vector space, and a useful tool for studying its properties. You probably already have a rough notion of what a mathematical definition of dimension might be --- try to forget these imprecise ideas and go with the new ones given here.
Definition D (Dimension) Suppose that $V$ is a vector space and $\set{\vectorlist{v}{t}}$ is a basis of $V$. Then the dimension of $V$ is defined by $\dimension{V}=t$. If $V$ has no finite bases, we say $V$ has infinite dimension.
This is a very simple definition, which belies its power. Grab a basis, any basis, and count up the number of vectors it contains. That's the dimension. However, this simplicity causes a problem. Given a vector space, you and I could each construct different bases --- remember that a vector space might have many bases. And what if your basis and my basis had different sizes? Applying Definition D we would arrive at different numbers! With our current knowledge about vector spaces, we would have to say that dimension is not "well-defined." Fortunately, there is a theorem that will correct this problem.
In a strictly logical progression, the next two theorems would precede the definition of dimension. Many subsequent theorems will trace their lineage back to the following fundamental result.
Theorem SSLD (Spanning Sets and Linear Dependence) Suppose that $S=\set{\vectorlist{v}{t}}$ is a finite set of vectors which spans the vector space $V$. Then any set of $t+1$ or more vectors from $V$ is linearly dependent.
The proof just given has some monstrous expressions in it, mostly owing to the double subscripts present. Now is a great opportunity to show the value of a more compact notation. We will rewrite the key steps of the previous proof using summation notation, resulting in a more economical presentation, and even greater insight into the key aspects of the proof. So here is an alternate proof --- study it carefully.
\begin{proof} {\bf (Alternate Proof of Theorem SSLD)} We want to prove that any set of $t+1$ or more vectors from $V$ is linearly dependent. So we will begin with a totally arbitrary set of vectors from $V$, $R=\setparts{\vect{u}_j}{1\leq j\leq m}$, where $m>t$. We will now construct a nontrivial relation of linear dependence on $R$.
Each vector $\vect{u_j}$, $1\leq j\leq m$ can be written as a linear combination of $\vect{v}_i$, $1\leq i\leq t$ since $S$ is a spanning set of $V$. This means there are scalars $a_{ij}$, $1\leq i\leq t$, $1\leq j\leq m$, so that
\begin{align*} \vect{u}_j&=\sum_{i=1}^{t}a_{ij}\vect{v_i}&&1\leq j\leq m \end{align*}
Now we form, unmotivated, the homogeneous system of $t$ equations in the $m$ variables, $x_j$, $1\leq j\leq m$, where the coefficients are the just-discovered scalars $a_{ij}$,
\begin{align*} \sum_{j=1}^{m}a_{ij}x_j=0&&1\leq i\leq t \end{align*}
This is a homogeneous system with more variables than equations (our hypothesis is expressed as $m>t$), so by Theorem HMVEI there are infinitely many solutions. Choose one of these solutions that is not trivial and denote it by $x_j=c_j$, $1\leq j\leq m$. As a solution to the homogeneous system, we then have $\sum_{j=1}^{m}a_{ij}c_{j}=0$ for $1\leq i\leq t$. As a collection of nontrivial scalars, $c_j$, $1\leq j\leq m$, will provide the nontrivial relation of linear dependence we desire,
\begin{align*} \sum_{j=1}^{m}c_{j}\vect{u}_j &=\sum_{j=1}^{m}c_{j}\left(\sum_{i=1}^{t}a_{ij}\vect{v_i}\right) &&\text{ Definition TSVS}\\ &=\sum_{j=1}^{m}\sum_{i=1}^{t}c_{j}a_{ij}\vect{v}_i &&\text{ Property DVA}\\ &=\sum_{i=1}^{t}\sum_{j=1}^{m}c_{j}a_{ij}\vect{v}_i &&\text{ Property CMCN}\\ &=\sum_{i=1}^{t}\sum_{j=1}^{m}a_{ij}c_{j}\vect{v}_i &&\text{Commutativity in $\complex{}$}\\ &=\sum_{i=1}^{t}\left(\sum_{j=1}^{m}a_{ij}c_{j}\right)\vect{v}_i &&\text{ Property DSA}\\ &=\sum_{i=1}^{t}0\vect{v}_i &&\text{$c_j$ as solution}\\ &=\sum_{i=1}^{t}\zerovector &&\text{ Theorem ZSSM}\\ &=\zerovector &&\text{ Property Z} \end{align*}
That does it. $R$ has been undeniably shown to be a linearly dependent set. \end{proof} Notice how the swap of the two summations is so much easier in the third step above, as opposed to all the rearranging and regrouping that takes place in the previous proof. In about half the space. And there are no ellipses ($\ldots$).
Theorem SSLD can be viewed as a generalization of Theorem MVSLD. We know that $\complex{m}$ has a basis with $m$ vectors in it (Theorem SUVB), so it is a set of $m$ vectors that spans $\complex{m}$. By Theorem SSLD, any set of more than $m$ vectors from $\complex{m}$ will be linearly dependent. But this is exactly the conclusion we have in Theorem MVSLD. Maybe this is not a total shock, as the proofs of both theorems rely heavily on Theorem HMVEI. The beauty of Theorem SSLD is that it applies in any vector space. We illustrate the generality of this theorem, and hint at its power, in the next example.
Example LDP4: Linearly dependent set in $P_4$.
Theorem SSLD is indeed powerful, but our main purpose in proving it right now was to make sure that our definition of dimension (Definition D) is well-defined. Here's the theorem.
Theorem BIS (Bases have Identical Sizes) Suppose that $V$ is a vector space with a finite basis $B$ and a second basis $C$. Then $B$ and $C$ have the same size.
Theorem BIS tells us that if we find one finite basis in a vector space, then they all have the same size. This (finally) makes Definition D unambiguous.
We can now collect the dimension of some common, and not so common, vector spaces. \begin{theorem}{DCM}{Dimension of $\complex{m}$}{complex vector space!dimension} The dimension of $\complex{m}$ (Example VSCV) is $m$. \end{theorem} \begin{proof} Theorem SUVB provides a basis with $m$ vectors. \end{proof}
Theorem DP (Dimension of $P_n$) The dimension of $P_{n}$ (Example VSP) is $n+1$.
\begin{theorem}{DM}{Dimension of $M_{mn}$}{matrix vector space!dimension} The dimension of $M_{mn}$ (Example VSM) is $mn$. \end{theorem} \begin{proof} Example BM provides a basis with $mn$ vectors. \end{proof}
Example DSM22: Dimension of a subspace of $M_{22}$.
Example DSP4: Dimension of a subspace of $P_4$.
Example DC: Dimension of the crazy vector space.
It is possible for a vector space to have no finite bases, in which case we say it has infinite dimension. Many of the best examples of this are vector spaces of functions, which lead to constructions like Hilbert spaces. We will focus exclusively on finite-dimensional vector spaces. OK, one infinite-dimensional example, and then we will focus exclusively on finite-dimensional vector spaces.
Example VSPUD: Vector space of polynomials with unbounded degree.
For any matrix, we have seen that we can associate several subspaces --- the null space (Theorem NSMS), the column space (Theorem CSMS), row space (Theorem RSMS) and the left null space (Theorem LNSMS). As vector spaces, each of these has a dimension, and for the null space and column space, they are important enough to warrant names.
Definition NOM (Nullity Of a Matrix) Suppose that $A$ is an $m\times n$ matrix. Then the nullity of $A$ is the dimension of the null space of $A$, $\nullity{A}=\dimension{\nsp{A}}$.
Definition ROM (Rank Of a Matrix) Suppose that $A$ is an $m\times n$ matrix. Then the rank of $A$ is the dimension of the column space of $A$, $\rank{A}=\dimension{\csp{A}}$.
Example RNM: Rank and nullity of a matrix.
There were no accidents or coincidences in the previous example --- with the row-reduced version of a matrix in hand, the rank and nullity are easy to compute.
Theorem CRN (Computing Rank and Nullity) Suppose that $A$ is an $m\times n$ matrix and $B$ is a row-equivalent matrix in reduced row-echelon form with $r$ nonzero rows. Then $\rank{A}=r$ and $\nullity{A}=n-r$.
Every archetype (appendix A) that involves a matrix lists its rank and nullity. You may have noticed as you studied the archetypes that the larger the column space is the smaller the null space is. A simple corollary states this trade-off succinctly. (See technique LC.)
Theorem RPNC (Rank Plus Nullity is Columns) Suppose that $A$ is an $m\times n$ matrix. Then $\rank{A}+\nullity{A}=n$.
When we first introduced $r$ as our standard notation for the number of nonzero rows in a matrix in reduced row-echelon form you might have thought $r$ stood for "rows." Not really --- it stands for "rank"!
Let's take a look at the rank and nullity of a square matrix.
Example RNSM: Rank and nullity of a square matrix.
The value of either the nullity or the rank are enough to characterize a nonsingular matrix.
Theorem RNNM (Rank and Nullity of a Nonsingular Matrix) Suppose that $A$ is a square matrix of size $n$. The following are equivalent.
With a new equivalence for a nonsingular matrix, we can update our list of equivalences (Theorem NME5) which now becomes a list requiring double digits to number.
Theorem NME6 (Nonsingular Matrix Equivalences, Round 6) Suppose that $A$ is a square matrix of size $n$. The following are equivalent.