MIT 18.701 — Lecture 6

Linear Transformations, Bases and Matrices, The Dimension Theorem

§ Vector Space Definitions (cont.)

Previously, we defined span and linear independence using vectors. Let's generalize these definitions to subspaces.

Definition (Span). Consider subspaces $W_1, \dots, W_k \subseteq V$ of a vector space $V$ . Then their span is:

\mathrm{span}(W_1, \dots, W_k) := W_1 + \dots + W_k := \{w_1 + \dots + w_k : w_i \in W_i\}.

Equivalently, the span of $\{W_1, \dots, W_k\}$ is the smallest subspace of $V$ containing $\bigcup_{i = 1}^k W_i$ .

Definition (Linear Independence). We say subspaces $W_1, \dots, W_k \subseteq V$ of a vector space $V$ are linearly independent if, for any choice of vectors $w_i$ in each subspace $W_i$ , we have:

w_1 + \dots + w_k = 0 ~ \text{ if and only if } ~ w_1 = \dots = w_k = 0.

Remark. Our previous notions of span and linear independence in terms of vectors are the same as those for subspaces: they're the special cases when each $W_i$ is a one-dimensional subspace $W_i := \{\lambda v_i: \lambda \in F\}$ .

Definition (Direct Sum). If subspaces $W_1, \dots, W_k \subseteq V$ of a vector space $V$ are both spanning and linearly independent, then we say $V$ is isomorphic to the direct sum ( $\oplus$ ) of these subspaces:

V = W_1 \oplus \dots \oplus W_k \cong W_1 \times \dots \times W_k.

To be precise, here is how we formally define the isomorphism $\cong$ in the definition above.

Definition (Transformations). Given vector spaces $V$ and $W$ and a map $T: V \to W$ , we say:

$T$ is a linear transformation if $T(v_1 + v_2) = T(v_1) + T(v_2)$ and $T(\lambda v_1) = \lambda T(v_1)$ always.
$T$ is a linear operator if it is a linear transformation with its domain $V$ equal to its codomain $W$ .
$T$ is an isomorphism if it is a bijective linear transformation.

Example. Each matrix $M \in F^{m \times n}$ gives a natural linear transformation $M: F^n \to F^m$ .

Example. Consider the vector space $V := \{\text{infinitely differentiable } f: \mathbb{R} \to \mathbb{R} \}$ . Then the map $T: V \to V$ defined by $T: f \mapsto f'$ is a linear operator.

§ Choosing a Basis

The following always (obviously!) holds.

Theorem. (Finite-Dimensional Vector Spaces) Suppose a finite-dimensional vector space $V$ over a field $F$ has dimension $n$ and some basis $\{v_1, \dots, v_n\} \subseteq V$ . Then $V$ is isomorphic to $F^n$ , with isomorphism:

\varphi: F^n \to V ~ \text{ defined by } ~ \varphi\left(\left[\begin{smallmatrix} \lambda_1 \\ \vdots \\ \lambda_n \end{smallmatrix}\right]\right) = \lambda_1v_1 + \dots + \lambda_n v_n

So all vector spaces of the same dimension over $F$ are isomorphic.

This yields two philosophical perspectives about vector spaces:

Physicists' Approach: We can reduce any abstract $n$ -dimensional vector space $V$ to the simpler vector space $F^n$ , as long as we just pick a basis. So the different ways we can pick a good basis should be our focus of study.

Example. The space $\mathbb{R}^3$ can be described using $(r, \theta, \varphi)$ or $(x, y, z)$ or …

Mathematicians' Approach: The same vector space $V$ looks very different under different choices of basis. So our focus of study should be the qualities of vector spaces that are well-defined independent of choice of basis.

Example. It turns out that the determinant and trace of a matrix do not depend on the choice of basis.

§ Linear Transformation $\implies$ Matrix (Only if You Choose a Basis!)

Recall the following remark from the previous lecture:

Remark. It does not make sense to describe linear maps between arbitrary vector spaces $M: V \to W$ using a matrix. Matrices only make sense if the vector spaces $V$ and $W$ are both of the form $F^m$ and $F^n$ .

To fix this, let's take the physicists' approach: if we choose a basis for vector spaces $V$ and $W$ , then we can reduce $V$ and $W$ to the isomorphic vector spaces $F^n$ and $F^m$ , at which point matrix representations make sense.

Theorem. (Matrix Representation of Linear Maps) Consider vector spaces $V$ and $W$ over a field $F$ . Select a basis $\{v_1, \dots, v_n\} \subseteq V$ for $V$ and a basis $\{w_1, \dots, w_m\} \subseteq W$ for $W$ . Then any linear transformation $T: V \to W$ is determined entirely by just the images of $T(v_1), \dots, T(v_n)$ . To be explicit,

Express each $T(v_i) \in W$ as a linear combination of the basis $\{w_j\} \subseteq W$ with coefficients $(M_T)_{ji}$ ; that is,
$\text{Define } (M_T)_{ji} \text{ to be the coefficients required to make } T(v_i) = \sum_{j = 1}^m (M_T)_{ji} w_j \text{ true.}$
Given these entries $\{(M_T)_{ji}\}$ alone, we can compute the image of any vector $v = \sum_{i = 1}^n \lambda_i v_i \in V$ under $T$ to be:
$T\left(\sum_{i = 1}^n \lambda_i v_i \right) = \sum_{j = 1}^m \left(\sum_{i = 1}^n (M_T)_{ji} \lambda_i\right)w_j.$
(The right-hand side of the above is just a messy-looking way to write matrix-vector multiplication.)

Unfortunately, abstract vector spaces $V$ and $W$ aren't usually born with an inherent choice of basis. How do the entries of our matrix $\{(M_T)_{ji}\} \in F^{m \times n}$ change when we change our choices of basis?

Theorem. (Change of Basis) Suppose a linear transformation $T: V \to W$ has corresponding matrix representation $M_T$ when we choose bases $\{v_1, \dots, v_n\} \subseteq V$ and $\{w_1, \dots, w_m\} \subseteq W$ .

Suppose we instead adopt new bases $\{Av_1, \dots, Av_n\} \subseteq V$ and $\{Bw_1, \dots, Bw_m\} \subseteq W$ , where $A$ and $B$ are bijective linear operators $A: V \to V$ and $B: W \to W$ that encode our change of basis.

Then the matrix $M_T'$ determined by these new choices of bases looks like $M_T' = M_{B}^{-1}M_T M_A$ .

Proof: By definition, the entries of our new matrix $M_T'$ must satisfy the property:

T(Av_i) = \sum_{j = 1}^m (M_T')_{ji} (Bw_j) \text{ for all } i.

Note that we can perform left-multiplication by $B^{-1}$ on both sides of this equation to achieve:

(B^{-1}TA)v_i = \sum_{j = 1}^m (M_T')_{ji}w_j.

Forget about what $M_T'$ meant to us to begin with: looking only at the equation above, we can read off that the coefficients $(M_T')_{ji}$ encode the image of each $v_i$ under the map $B^{-1}TA$ as a linear combination of $w_j$ .

Thus, $M_T' = M_{B^{-1}TA}$ , so $M_T' = M_B^{-1} M_TM_A$ , as promised. $\blacksquare$

Something interesting happens when we consider change of basis for linear maps $T: V \to V$ .

Suppose $V$ is an $n$ -dimensional vector space over $F$ .
If we pick basis $\{v_1, \dots, v_n\} \subseteq V$ for $V$ , then we can express $T$ using a matrix $M_T \in F^{n \times n}$ .
Now, pick a different choice of basis $\{Av_1, \dots, Av_n\}$ , where $A$ is a bijective linear operator $A: V \to V$ .
Then $T: V \to V$ under this new basis looks like $M_T' = M_A^{-1}M_TM_A$ .

The key observation is that $M_T' = M_A^{-1}M_TM_A$ just looks like the result of conjugating $M_T$ by $M_A$ . Thus,

Theorem. (Matrix Conjugation) Changing the basis used in deriving the matrix form $M_T$ of a linear map $T: V \to V$ is the same as conjugating the matrix $M_T$ by another matrix $M_A$ in the group $GL_n(F)$ .

Remark. Recall that a subgroup is normal if it remains invariant under conjugation. Equivalently, a subgroup $H$ of $GL_n(F)$ is normal if changing the basis of a matrix in $H$ yields another matrix in $H$ .

§ Rank, Nullity, and the Dimension Theorem

Definition (Rank and Nullity). Given a linear transformation $T: V \to W$ (for finite-dimensional vector spaces $V$ and $W$ ), the kernel and image of $T$ are $\ker T := \{ v \in V: Tv = 0\} \subseteq V$ and $\im T := \{Tv : v \in V\} \subseteq W$ .

Then the rank and nullity of $T$ are $\mathrm{rank} \ T := \dim(\im T)$ and $\mathrm{nullity} \ T := \dim(\ker T)$ .

Somewhat intuitively, the rank and nullity of a linear map together satisfy the following nice property:

Theorem. (Dimension Theorem) For a linear transformation $T: V \to W$ between finite-dimensional vector spaces $V$ and $W$ , we have $\dim \im T + \dim \ker T = \dim V$ .

Remark. The Dimension Theorem is just the “logarithm” version of the fact that for any group homomorphism $f: G \to H$ , we have $| \ker f | \cdot | \im f | = |G|$ : just take $G$ and $H$ to be vector spaces over $F = \mathbb{Z} / p \mathbb{Z}$ .

In fact, the Dimension Theorem is stronger than $| \ker f | \cdot | \im f | = |G|$ , since dimension is a stronger notion than cardinality: $\mathbb{R}^2$ and $\mathbb{R}^3$ have the same cardinality, but as vector spaces over $\mathbb{R}$ , they have different dimensions!

We'll finish class by proving the Dimension Theorem.

Proof: Choose bases $\{v_1, \dots, v_n\} \subseteq V$ and $\{w_1, \dots, w_m \} \subseteq W$ so we may represent $T: V \to W$ with a matrix $M_T$ . We begin by investigating a very special case: suppose $T = T_0$ for which the matrix $M_{T_0}$ looks like the following:

M_{T_0} = \begin{bmatrix} 1 & \cdots & 0 & 0 & \cdots & 0 \\ \vdots & \ddots & \vdots & \vdots & \vdots & \vdots \\ 0 & \cdots & 1 & 0 & \cdots & 0 \\ 0 & \cdots & 0 & 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & \cdots & 0 & 0 & \cdots & 0 \end{bmatrix} \text{ with a } k\text{-dimensional } I_k \text{ in the top-left corner.}

In other words, $T$ sends each of $(v_1, \dots, v_k)$ to $(w_1, \dots, w_k)$ , respectively, and $T$ sends each of $(v_{k + 1}, \dots, v_n)$ to zero. Then the image of $T$ is $\mathrm{span}(w_1, \dots, w_k)$ , and the kernel of $T$ is $\mathrm{span}(v_{k + 1}, \dots, v_n)$ . Thus, the rank of $T$ is $k$ and the nullity of $T$ is $n - k$ , so the Dimension Theorem holds because $k + (n - k) = n$ .

Now the key idea is the following: consider, more generally, a linear transformation $T: V \to W$ whose matrix representation $M_T$ is not as nice as $M_{T_0}$ . We claim that, under a suitable change of basis, the matrix $M_T$ can become $M_T' = M_{T_0}$ , in which case we'd be done!

Why must there exist a change of basis that transforms $M_T$ into $M_T' = M_{T_0}$ ? Because performing change of basis on a matrix looks like performing row and column operations on $M_T$ . So we can procedurally perform row and column operations (changes of basis) to eventually reform $M_T$ into the form $M_{T_0}$ . $\blacksquare$

The moral of the story? Picking the right basis can yield very nice results.

Remark. The above argument also implies that the rank of a matrix $M_T$ is the same as that of its transpose $M_T^{\top}$ .

§ Vector Space Definitions (cont.)

§ Choosing a Basis

§ Linear Transformation ⟹ \implies⟹ Matrix (Only if You Choose a Basis!)

§ Rank, Nullity, and the Dimension Theorem

§ Linear Transformation $\implies$ Matrix (Only if You Choose a Basis!)