Exercise
Another kind of linear transformation is a projection. For example, let \(T \colon \mathbb{R}^3 \to \mathbb{R}^3\) be the map that projects any vector in \(\mathbb{R}^3\) onto the \(x_1x_2\)-plane (the plane \(x_3 = 0\)). (See the lecture recording for a picture of what \(T\) does.) What is the matrix of \(T\)?
Today we'll finish up our initial discussion of linear transformations by talking about when a linear transformation is onto (or surjective). Then we'll begin to discuss matrix algebra: thinking about matrices as objects that we can add and multiply in their own right.
Definition (onto/surjective)
A linear transformation \(T \colon \mathbb{R}^m \to \mathbb{R}^n\) is said to be onto (or surjective) if, for all \(\mathbf{y} \in \mathbb{R}^n\), there is at least one \(\mathbf{x} \in \mathbb{R}^m\) such that \(T(\mathbf{x}) = \mathbf{y}.\)
In other words, for an onto function, all possible outputs are actually mapped to by the function: the range of the function is the entire codomain.
Example
The linear transformation \(T\left(\begin{bmatrix} a \\ b \end{bmatrix}\right) = \begin{bmatrix} a+b \\ b \end{bmatrix}\) (from above) is onto. To see this, we take some arbitrary vector \(\begin{bmatrix} x \\ y \end{bmatrix}\) and want to check that \(T\left(\begin{bmatrix} a \\ b \end{bmatrix}\right) = \begin{bmatrix} x \\ y \end{bmatrix} \) has at least one solution. This is \(a+b = x\) and \(b = y,\) so we can quickly see that \(\begin{bmatrix} a \\ b \end{bmatrix} = \begin{bmatrix} x-y \\ y \end{bmatrix}.\) Therefore, \(T\) is onto because every output comes from at least one input (in this case, exactly one input).
Example
The linear transformation \(T \colon \mathbb{R}^2 \to \mathbb{R}^3\) given by \(T\left(\begin{bmatrix} a \\ b \end{bmatrix}\right) = \begin{bmatrix} a \\ 2a \\ b \end{bmatrix}\) is not onto. A quick way to see why is to observe that for every vector in the range of \(T\), the first component is half of the second component. Therefore, a vector such as \(\begin{bmatrix} 1 \\ 3 \\ 0 \end{bmatrix}\) cannot be in the range of \(T,\) so the range of \(T\) is not all of \(\mathbb{R}^3.\)
Let's consider a linear transformation \(T \colon \mathbb{R}^m \to \mathbb{R}^n\). The codomain of \(T\) is \(\mathbb{R}^n\), and we want to know when this is also the range of \(T\). The range consists of all possible outputs, so let's examine what a typical output looks like. If \(A\) is the \(n \times m\) matrix corresponding to \(T\), then we have \[ T(\mathbf{x}) = A\mathbf{x} = x_1 \mathbf{v}_1 + x_2 \mathbf{v}_2 + \dotsm + x_m \mathbf{v}_m, \] where \(\mathbf{x} = (x_1, x_2, \dots, x_m)\) and \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m \in \mathbb{R}^n\) are the columns of \(A\). This means that the range of \(T\) is the set of all possible vectors in \(\mathbb{R}^n\) that can be written as \(x_1 \mathbf{v}_1 + x_2 \mathbf{v}_2 + \dotsm + x_m \mathbf{v}_m\) for some \(x_1, x_2, \dots, x_m.\) That looks familiar too: it's just the span of \(\mathbf{v}_1, \dots, \mathbf{v}_m\)!
Theorem (onto/surjective)
If \(T \colon \mathbb{R}^m \to \mathbb{R}^n\) is a linear transformation with matrix \(A\), then the range of \(T\) is the span of the columns of \(A\).
In particular, \(T\) is onto if and only if the columns of \(A\) span \(\mathbb{R}^n\).
As a consequence, if \(m < n\), then a linear transformation \(T \colon \mathbb{R}^m \to \mathbb{R}^n\) can never be onto. (Intuitively: if \(m < n\), then \(\mathbb{R}^m\) is "smaller" than \(\mathbb{R}^n\), so there's no linear transformation that maps \(\mathbb{R}^m\) onto \(\mathbb{R}^n\) in a way that hits all the points in \(\mathbb{R}^n\).)
Now that we know that matrices are "the same as" linear transformations, we can add to our unifying theorem about square matrices:
The Unifying Theorem, version 2
Let \(A\) be an \(n \times n\) matrix with columns \(\mathbf{v}_1, \dots, \mathbf{v}_n\). Let \(T \colon \mathbb{R}^n \to \mathbb{R}^n\) be the linear transformation defined by \(T(\mathbf{x}) = A\mathbf{x}.\) Then, the following are equivalent:
(i) \(\mathbf{v}_1, \dots, \mathbf{v}_n\) span \(\mathbb{R}^n\).
(ii) \(\mathbf{v}_1, \dots, \mathbf{v}_n\) are linearly independent.
(iii) For all \(\mathbf{b} \in \mathbb{R}^n\), the linear system \(A\mathbf{x} = \mathbf{b}\) has exactly one solution.
(iv) \(T\) is one-to-one.
(v) \(T\) is onto.
Let's switch to looking at matrices, which we now know represent linear transformations. Like vectors, we can do certain arithmetical / algebraic operations on matrices, but unlike vectors, we have a way to multiply two matrices and get another matrix. We'll see how matrix multiplication relates to composition of linear transformations.
We begin with addition and scalar multiplication of matrices, which are defined the same way as for vectors. (In fact, we often think of vectors as just \(n \times 1\) or \(1 \times n\) matrices.)
Definition (addition, scalar multiplication of matrices)
Let \(A\) and \(B\) be two \(n \times m\) matrices. We define \(A + B\) to be the \(n \times m\) matrix whose \((i, j)\) entry is \(A_{i,j} + B_{i,j}.\)
For a scalar \(c \in \mathbb{R},\) we define \(cA\) to be the \(n \times m\) matrix whose \((i,j)\) entry is \(c \cdot A_{i,j}\).
(Remember that \(A_{i,j}\) means the entry of \(A\) in the \(i\)th row and \(j\)th column.) In other words, we do matrix addition and matrix scalar multiplication entry by entry. However, we can only add two matrices if they have the same size (or dimension - numbers of rows and columns). So, \[\begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix} + \begin{bmatrix} -1 & 3 & 1 \\ 4 & 2 & -1 \end{bmatrix} = \begin{bmatrix} 0 & 5 & 4 \\ 8 & 7 & 5 \end{bmatrix},\] but \[\begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix} + \begin{bmatrix} -1 & 3 \\ 4 & 0 \end{bmatrix} \] does not make sense and is not defined.
Definition (zero matrix)
The \(n \times m\) zero matrix, denoted \(0_{n,m}\) or just \(0\), is the matrix of all zeros.
The zero matrix is the additive identity for matrices, meaning that \(A + 0 = 0 + A = A\) for all \(n \times m\) matrices \(A\).
Note that we now have three different kinds of things we call "zero": there's the number 0, there are zero vectors of any length, and now we have zero matrices of any size. When you see a "0" in linear algebra (either in these notes, on your homework/exams, or out in the wild), please pay attention to the context to determine what kind of object it is.
Like vectors, matrix addition is commutative and associative, and distributes over scalar multiplication; in other words, you can work with sums and scalar multiples of matrices exactly like you would with real numbers. However, this is very much NOT the case for matrix multiplication.
You might expect matrix multiplication to work in the same way as addition: simply multiply corresponding entries of the two input matrices. But this is NOT how multiplication is defined. Instead, we define matrix multiplication so that it corresponds to a natural "multiplication" operation for linear transformations, namely function composition.
Definition (composition of linear transformations)
If \(T \colon \mathbb{R}^m \to \mathbb{R}^n\) and \(S \colon \mathbb{R}^n \to \mathbb{R}^p\) are linear transformations, we define the composition \(S \circ T\) to be the linear transformation \(\mathbb{R}^m \to \mathbb{R}^p\) defined as follows: for \(\mathbf{x} \in \mathbb{R}^m\), we have \[ (S \circ T)(\mathbf{x}) = S\left( T(\mathbf{x}) \right).\]
In other words, \(S \circ T\) is the function that first applies \(T\), then applies \(S.\) Notice that the order of application is right-to-left! (This choice means that we can say \( (S \circ T)(\mathbf{x}) = S\left( T(\mathbf{x}) \right)\), where \(S\) and \(T\) go in the same order on both sides. But it is annoying, I'm sorry.) Notice also that, for \(S \circ T\) to be defined, the codomain of \(T\) must be the same as the domain of \(S.\) Finally, even if both are defined, \(S \circ T\) and \(T \circ S\) are generally not the same transformation. (They may not even have the same domain and codomain.)
In this definition, there is something I implicitly assumed, namely that \(S \circ T\) is actually a linear transformation. Luckily, this is always true:
Fact (composition of linear transformations)
The composition of two linear transformations is also a linear transformation.
To prove this statement, we can just use the definition of linear transformation. For example, to see that \(S \circ T\) respects addition, we take some \(\mathbf{v}, \mathbf{w} \in \mathbb{R}^m\) and compute: \[\begin{aligned} (S \circ T)(\mathbf{v} + \mathbf{w}) &= S\left( T(\mathbf{v} + \mathbf{w}) \right) \\ &= S\left( T(\mathbf{v}) + T(\mathbf{w}) \right) \\ &= S(T(\mathbf{v})) + S(T(\mathbf{w})) \\ &= (S \circ T)(\mathbf{v}) + (S \circ T)(\mathbf{w}). \end{aligned} \] To get from the first line to the second line, we used the fact that \(T\) respects addition; to get from the second line to the third line, we used the fact that \(S\) respects addition. (The other two equalities are just using the definition of \(S \circ T.\)) You can similarly prove that \(S \circ T\) respects scalar multiplication.
Now that we know that \(S \circ T\) is a linear transformation, we will define matrix multiplication so that it corresponds to composition of linear transformation. In other words:
Goal
If \(A\) is the matrix of the linear transformation \(S\) and \(B\) is the matrix of the linear transformation \(T\), then \(AB\) should be the matrix of \(S \circ T\).
Let's see an example, and then we'll actually write down formulas for matrix multiplication.
Exercise
Suppose that \(S \colon \mathbb{R}^3 \to \mathbb{R}^2\) has matrix \(A = \begin{bmatrix} 1&2&3\\4&5&0 \end{bmatrix}\), and \(T \colon \mathbb{R}^2 \to \mathbb{R}^3\) has matrix \(B = \begin{bmatrix} -1 & 0 \\ 0 & -2 \\ 0 & 1 \end{bmatrix} \). Because the codomain of \(T\) is the same as the domain of \(S\) (namely, they are both \(\mathbb{R^3}\)), we can compose \(S\) with \(T\) to get a linear transformation \(S \circ T \colon \mathbb{R}^2 \to \mathbb{R}^2.\) To find the matrix of \(S \circ T,\) we only need to know what it does to the standard basis vectors in \(\mathbb{R}^2,\) as we learned last time.
So, let's compute \((S \circ T)(\mathbf{e}_1)\) and \((S \circ T)(\mathbf{e}_2)\). As a shortcut, remember that the columns of the matrix of \(T\) (that is, the columns of \(B\)) are \(T(\mathbf{e}_1)\) and \(T(\mathbf{e}_2)\). Therefore, \[ (S \circ T)(\mathbf{e}_1) = S(T(\mathbf{e}_1)) = S\left( \begin{bmatrix} -1 \\ 0 \\ 0 \end{bmatrix} \right) = A \begin{bmatrix} -1 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 1&2&3\\4&5&0 \end{bmatrix} \begin{bmatrix} -1 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} -1 \\ -4 \end{bmatrix}. \] Similarly, \[ (S \circ T)(\mathbf{e}_2) = S(T(\mathbf{e}_2)) = S\left( \begin{bmatrix} 0 \\ -2 \\ 1 \end{bmatrix} \right) = A \begin{bmatrix} 0 \\ -2 \\ 1 \end{bmatrix} = \begin{bmatrix} 1&2&3\\4&5&0 \end{bmatrix} \begin{bmatrix} 0 \\ -2 \\ 1 \end{bmatrix} = \begin{bmatrix} -1 \\ -10 \end{bmatrix}. \] Therefore, the matrix of \(S \circ T,\) which is the product \(AB\), is \[AB = \begin{bmatrix} -1 & -1 \\ -4 & -10 \end{bmatrix}.\]
Notice that \(AB\) is \(2 \times 2\), which is good because it is supposed to correspond to \(S \circ T \colon \mathbb{R}^2 \to \mathbb{R}^2\) (just like how \(A\) is \(2 \times 3\) and corresponds to \(S \colon \mathbb{R}^3 \to \mathbb{R}^2\)).
Looking at this example suggests how matrix multiplication should work in general. In the example, notice that the first column of \(AB\) is \(A\) times the first column of \(B\) (which we figured out by remembering that the first column of \(B\) is \(T(\mathbf{e}_1)\)). Similarly, the second column of \(AB\) is \(A\) times the second column of \(B\). This leads to one description of matrix multiplication:
Definition (matrix multiplication, column-by-column)
If \(A\) is a \(p \times n\) matrix and \(B\) is an \(n \times m\) matrix, then \(AB\) is the \(p \times m\) matrix defined by \[ AB = \begin{bmatrix} | & | & & | \\ A\mathbf{b}_1 & A\mathbf{b}_2 & \dotsm & A\mathbf{b}_m \\ | & | & & | \end{bmatrix}, \] where \(\mathbf{b}_1, \mathbf{b}_2, \dots, \mathbf{b}_m\) are the columns of \(B\).
However, this is not how most people actually do matrix multiplication. Instead, it can be done entry-by-entry, using the following equivalent definition:
Definition (matrix multiplication, entry-by-entry)
If \(A\) is a \(p \times n\) matrix and \(B\) is an \(n \times m\) matrix, then \(AB\) is the \(p \times m\) matrix where the \((i,j)\) entry is the dot product of the \(i\)th row of \(A\) with the \(j\)th column of \(B\).
Note: As you may remember, the dot product of two vectors in \(\mathbb{R}^n\) is the sum of the products of corresponding entries: \[(x_1, x_2, \dots, x_n) \cdot (y_1, y_2, \dots, y_n) = x_1y_1 + x_2y_2 + \dotsm + x_ny_n.\]
Let's make sure this works for our example above, in which we computed \[AB = \begin{bmatrix} 1&2&3\\4&5&0 \end{bmatrix} \begin{bmatrix} -1 & 0 \\ 0 & -2 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} -1 & -1 \\ -4 & -10 \end{bmatrix}.\] According to this definition, \(AB\) should equal \[ \begin{bmatrix} (1,2,3) \cdot (-1,0,0) &\quad (1,2,3) \cdot (0,-2,1) \\ (4,5,0) \cdot (-1,0,0) &\quad (4,5,0) \cdot (0, -2, 1) \end{bmatrix} = \begin{bmatrix} -1 & -1 \\ -4 & -10 \end{bmatrix},\] which is correct.
Matrix multiplication is very different than the multiplication of real numbers; several properties of regular multiplication do not carry over to multiplication of matrices. Let's look at some examples. Because these are such common misconceptions, there is a ton of bold text in the following.
However, matrix multiplication still has some nice properties:
To avoid such headaches with matrix multiplication, we can only think about square \(n \times n\) matrices for some \(n\), since then we never have to worry whether anything is defined. (Multiplication is still not commutative, though!) This is where we'll spend a lot of time in the future.