Subsection Subspaces and span
Assume that we find two vectors that solve
\(A\vec{x} = 0\text{.}\) What other vectors also solve this equation? In our discussion of linear combinations, we saw that if
\(\vec{x}_1\) and
\(\vec{x}_2\) solve
\(A\vec{x} = 0\text{,}\) then so does
\(A(\alpha_1\vec{x}_1 + \alpha_2\vec{x}_2)\) for any constants
\(\alpha_1\) and
\(\alpha_2\text{.}\) Thus, all linear combinations will also solve the equation. This leads to the definition of the span of a set of vectors.
Definition 3.6.1.
The set of all linear combinations of a set of vectors is called their span.
\begin{equation*}
\operatorname{span} \bigl\{ \vec{x}_1, \vec{x}_2 , \ldots , \vec{x}_n \bigr\}
=
\bigl\{
\text{Set of all linear combinations of
$\vec{x}_1, \vec{x}_2 , \ldots , \vec{x}_n$}
\bigr\} .
\end{equation*}
Thus, if two vectors solve a homogeneous equation, so does everything in the span of those two vectors. The span of a collection of vectors is an example of a subspace, which is a common object in linear algebra. We say that a set \(S\) of vectors in \({\mathbb R}^n\) is a subspace if whenever \(\vec{x}\) and \(\vec{y}\) are members of \(S\) and \(\alpha\) is a scalar, then
\begin{equation*}
\vec{x} + \vec{y}, \qquad \text{and} \qquad \alpha \vec{x}
\end{equation*}
are also members of \(S\text{.}\) That is, we can add and multiply by scalars and we still land in \(S\text{.}\) So every linear combination of vectors of \(S\) is still in \(S\text{.}\) That is really what a subspace is. It is a subset where we can take linear combinations and still end up being in the subset.
Example 3.6.2.
If we let
\(S = {\mathbb R}^n\text{,}\) then this
\(S\) is a subspace of
\({\mathbb R}^n\text{.}\) Adding any two vectors in
\({\mathbb R}^n\) gets a vector in
\({\mathbb R}^n\text{,}\) and so does multiplying by scalars.
The set
\(S' = \{ \vec{0} \}\text{,}\) that is, the set of the zero vector by itself, is also a subspace of
\({\mathbb R}^n\text{.}\) There is only one vector in this subspace, so we only need to check for that one vector, and everything checks out:
\(\vec{0}+\vec{0} = \vec{0}\) and
\(\alpha \vec{0} = \vec{0}\text{.}\)
The set
\(S''\) of all the vectors of the form
\((a,a)\) for any real number
\(a\text{,}\) such as
\((1,1)\text{,}\) \((3,3)\text{,}\) or
\((-0.5,-0.5)\) is a subspace of
\({\mathbb R}^2\text{.}\) Adding two such vectors, say
\((1,1)+(3,3) = (4,4)\) again gets a vector of the same form, and so does multiplying by a scalar, say
\(8(1,1) = (8,8)\text{.}\)
We can apply these ideas to the vectors that live inside a matrix. The span of the rows of a matrix \(A\) is called the row space. The row space of \(A\) and the row space of the row echelon form of \(A\) are the same, because reducing the matrix \(A\) to its row echelon form involves taking linear combinations, which will preserve the span. In the example,
\begin{align*}
\text{row space of }
\begin{bmatrix}
1 & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9
\end{bmatrix}
\amp =
\operatorname{span}
\left\{
\begin{bmatrix}
1 & 2 & 3
\end{bmatrix}
,
\begin{bmatrix}
4 & 5 & 6
\end{bmatrix}
,
\begin{bmatrix}
7 & 8 & 9
\end{bmatrix}
\right\}\\
\amp =
\operatorname{span}
\left\{
\begin{bmatrix}
1 & 2 & 3
\end{bmatrix}
,
\begin{bmatrix}
0 & 1 & 2
\end{bmatrix}
\right\}\text{.}
\end{align*}
Similarly to row space, the span of columns is called the column space.
\begin{equation*}
\text{column space of }
\begin{bmatrix}
1 & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9
\end{bmatrix}
=
\operatorname{span}
\left\{
\begin{bmatrix}
1 \\ 4 \\ 7
\end{bmatrix}
,
\begin{bmatrix}
2 \\ 5 \\ 8
\end{bmatrix}
,
\begin{bmatrix}
3 \\ 6 \\ 9
\end{bmatrix}
\right\} .
\end{equation*}
In particular, to find a set of linearly independent columns we need to look at where the pivots were. If you recall above, when solving
\(A \vec{x}
= \vec{0}\) the key was finding the pivots, any non-pivot columns corresponded to free variables. That means we can solve for the non-pivot columns in terms of the pivot columns. Let’s see an example.
Example 3.6.3.
Find the linearly independent columns of the matrix
\begin{equation*}
\begin{bmatrix}
1 & 2 & 3 & 4 \\
2 & 4 & 5 & 6 \\
3 & 6 & 7 & 8
\end{bmatrix} .
\end{equation*}
Solution.
We find a pivot and reduce the rows below:
\begin{equation*}
\begin{bmatrix}
\mybxsm{1} & 2 & 3 & 4 \\
2 & 4 & 5 & 6 \\
3 & 6 & 7 & 8
\end{bmatrix}
\to
\begin{bmatrix}
\mybxsm{1} & 2 & 3 & 4 \\
0 & 0 & -1 & -2 \\
3 & 6 & 7 & 8
\end{bmatrix}
\to
\begin{bmatrix}
\mybxsm{1} & 2 & 3 & 4 \\
0 & 0 & -1 & -2 \\
0 & 0 & -2 & -4
\end{bmatrix} .
\end{equation*}
We find the next pivot, make it one, and rinse and repeat:
\begin{equation*}
\begin{bmatrix}
\mybxsm{1} & 2 & 3 & 4 \\
0 & 0 & \mybxsm{-1} & -2 \\
0 & 0 & -2 & -4
\end{bmatrix}
\to
\begin{bmatrix}
\mybxsm{1} & 2 & 3 & 4 \\
0 & 0 & \mybxsm{1} & 2 \\
0 & 0 & -2 & -4
\end{bmatrix}
\to
\begin{bmatrix}
\mybxsm{1} & 2 & 3 & 4 \\
0 & 0 & \mybxsm{1} & 2 \\
0 & 0 & 0 & 0
\end{bmatrix} .
\end{equation*}
The final matrix is the row echelon form of the matrix. Consider the pivots that we marked. The pivot columns are the first and the third column. All other columns correspond to free variables when solving \(A \vec{x} = \vec{0}\text{,}\) so all other columns can be solved in terms of the first and the third column. In other words
\begin{equation*}
\text{column space of }
\begin{bmatrix}
1 & 2 & 3 & 4 \\
2 & 4 & 5 & 6 \\
3 & 6 & 7 & 8
\end{bmatrix}
=
\operatorname{span}
\left\{
\begin{bmatrix}
1 \\
2 \\
3
\end{bmatrix}
,
\begin{bmatrix}
2 \\
4 \\
6
\end{bmatrix}
,
\begin{bmatrix}
3 \\
5 \\
7
\end{bmatrix}
,
\begin{bmatrix}
4 \\
6 \\
8
\end{bmatrix}
\right\}
=
\operatorname{span}
\left\{
\begin{bmatrix}
1 \\
2 \\
3
\end{bmatrix}
,
\begin{bmatrix}
3 \\
5 \\
7
\end{bmatrix}
\right\} .
\end{equation*}
We could perhaps use another pair of columns to get the same span, but the first and the third are guaranteed to work because they are pivot columns.
In the previous example, this means that only the first and third columns are “important” in the sense of generating the full column space as a span. We would like to have a way to talk about what these first and third columns do.
Definition 3.6.4. Spanning set.
Let
\(S\) be a subspace of a vector space. The set
\(\{\vec{v}_1, \vec{v}_2, ..., \vec{v}_k\}\) is a
spanning set for the subspace
\(S\) if each of these vectors are in
\(S\) and the span of
\(\{\vec{v}_1, \vec{v}_2, ..., \vec{v}_k\}\) is equal to
\(S\text{.}\)
In the context of the previous example, for the matrix
\begin{equation*}
A = \begin{bmatrix}
1 & 2 & 3 & 4 \\
2 & 4 & 5 & 6 \\
3 & 6 & 7 & 8
\end{bmatrix}
\end{equation*}
we know that
\begin{equation*}
\text{column space of }
\begin{bmatrix}
1 & 2 & 3 & 4 \\
2 & 4 & 5 & 6 \\
3 & 6 & 7 & 8
\end{bmatrix}
=
\operatorname{span}
\left\{
\begin{bmatrix}
1 \\
2 \\
3
\end{bmatrix}
,
\begin{bmatrix}
2 \\
4 \\
6
\end{bmatrix}
,
\begin{bmatrix}
3 \\
5 \\
7
\end{bmatrix}
,
\begin{bmatrix}
4 \\
6 \\
8
\end{bmatrix}
\right\}
=
\operatorname{span}
\left\{
\begin{bmatrix}
1 \\
2 \\
3
\end{bmatrix}
,
\begin{bmatrix}
3 \\
5 \\
7
\end{bmatrix}
\right\} .
\end{equation*}
This means that both
\begin{equation*}
\left\{
\begin{bmatrix}
1 \\
2 \\
3
\end{bmatrix}
,
\begin{bmatrix}
2 \\
4 \\
6
\end{bmatrix}
,
\begin{bmatrix}
3 \\
5 \\
7
\end{bmatrix}
,
\begin{bmatrix}
4 \\
6 \\
8
\end{bmatrix}
\right\}
\quad \text{ and } \quad
\left\{
\begin{bmatrix}
1 \\
2 \\
3
\end{bmatrix}
,
\begin{bmatrix}
3 \\
5 \\
7
\end{bmatrix}
\right\}
\end{equation*}
are spanning sets for this column space.
The idea also works in reverse. Suppose we have a bunch of column vectors and we just need to find a linearly independent set. For example, suppose we started with the vectors
\begin{equation*}
\vec{v}_1 =
\begin{bmatrix}
1 \\
2 \\
3
\end{bmatrix}
,
\quad
\vec{v}_2 =
\begin{bmatrix}
2 \\
4 \\
6
\end{bmatrix}
,
\quad
\vec{v}_3 =
\begin{bmatrix}
3 \\
5 \\
7
\end{bmatrix}
,
\quad
\vec{v}_4 =
\begin{bmatrix}
4 \\
6 \\
8
\end{bmatrix} .
\end{equation*}
These vectors are not linearly independent as we saw above. In particular, the span \(\vec{v}_1\) and \(\vec{v}_3\) is the same as the span of all four of the vectors. So \(\vec{v}_2\) and \(\vec{v}_4\) can both be written as linear combinations of \(\vec{v}_1\) and \(\vec{v}_3\text{.}\) A common thing that comes up in practice is that one gets a set of vectors whose span is the set of solutions of some problem. But perhaps we get way too many vectors, we want to simplify. For example above, all vectors in the span of \(\vec{v}_1, \vec{v}_2, \vec{v}_3, \vec{v}_4\) can be written \(\alpha_1 \vec{v}_1 + \alpha_2 \vec{v}_2 + \alpha_3 \vec{v}_3 + \alpha_4
\vec{v}_4\) for some numbers \(\alpha_1,\alpha_2,\alpha_3,\alpha_4\text{.}\) But it is also true that every such vector can be written as \(a \vec{v}_1 + b \vec{v}_3\) for two numbers \(a\) and \(b\text{.}\) And one has to admit, that looks much simpler. Moreover, these numbers \(a\) and \(b\) are unique. More on that later in this section.
To find this linearly independent set we simply take our vectors and form the matrix \([ \vec{v}_1 ~ \vec{v}_2 ~ \vec{v}_3 ~ \vec{v}_4 ]\text{,}\) that is, the matrix
\begin{equation*}
\begin{bmatrix}
1 & 2 & 3 & 4 \\
2 & 4 & 5 & 6 \\
3 & 6 & 7 & 8
\end{bmatrix} .
\end{equation*}
We crank up the row-reduction machine, feed this matrix into it, and find the pivot columns and pick those. In this case, \(\vec{v}_1\) and \(\vec{v}_3\text{.}\)
Subsection Basis and dimension
At this point, we have talked about subspaces, and two other properties of sets of vectors: linear independence and being a spanning set for a subspace. In some sense, these two properties are in opposition to each other. If I add more vectors to a set, I am more likely to become a spanning set (because I have more options for adding to get other vectors), but less likely to be independent (because there are more possibilities for a linear combination to be zero). Similarly, the reverse is true; removing vectors means the set is more likely to be linearly independent, but less likely to span a given subspace. The question then becomes if there is a sweet spot where both things are true, and that leads to the definition of a basis.
Definition 3.6.5. Basis and Dimension.
If \(S\) is a subspace and we can find \(k\) linearly independent vectors in \(S\)
\begin{equation*}
\vec{v}_1, \vec{v}_2, \ldots, \vec{v}_k ,
\end{equation*}
such that every other vector in \(S\) is a linear combination of \(\vec{v}_1,
\vec{v}_2,\ldots, \vec{v}_k\text{,}\) then the set \(\{ \vec{v}_1, \vec{v}_2, \ldots, \vec{v}_k \}\) is called a basis of \(S\text{.}\) In other words, \(S\) is the span of \(\{ \vec{v}_1, \vec{v}_2, \ldots, \vec{v}_k \}\text{.}\) We say that \(S\) has dimension \(k\text{,}\) and we write
\begin{equation*}
\dim S = k\text{.}
\end{equation*}
The next theorem illustrates the main properties and classification of a basis of a vector space.
Theorem 3.6.6.
If \(S \subset {\mathbb R}^n\) is a subspace and \(S\) is not the trivial subspace \(\{ \vec{0} \}\text{,}\) then there exists a unique positive integer \(k\) (the dimension) and a (not unique) basis \(\{ \vec{v}_1, \vec{v}_2, \ldots, \vec{v}_k \}\text{,}\) such that every \(\vec{w}\) in \(S\) can be uniquely represented by
\begin{equation*}
\vec{w} =
\alpha_1 \vec{v}_1 +
\alpha_2 \vec{v}_2 +
\cdots
+
\alpha_k \vec{v}_k ,
\end{equation*}
for some scalars \(\alpha_1\text{,}\) \(\alpha_2\text{,}\) …, \(\alpha_k\text{.}\)
We should reiterate that while
\(k\) is unique (a subspace cannot have two different dimensions), the set of basis vectors is not at all unique. There are lots of different bases for any given subspace. Finding just the right basis for a subspace is a large part of what one does in linear algebra. In fact, that is what we spend a lot of time on in linear differential equations, although at first glance it may not seem like that is what we are doing.
Example 3.6.7.
The standard basis
\begin{equation*}
\vec{e}_1, \vec{e}_2, \ldots, \vec{e}_n ,
\end{equation*}
is a basis of \({\mathbb R}^n\) (hence the name). So as expected
\begin{equation*}
\dim {\mathbb R}^n = n .
\end{equation*}
On the other hand the subspace
\(\{ \vec{0} \}\) is of dimension
\(0\text{.}\)
The subspace
\(S''\) from a previous example, that is, the set of vectors
\((a,a)\) is of dimension 1. One possible basis is simply
\(\{ (1,1) \}\text{,}\) the single vector
\((1,1)\text{:}\) every vector in
\(S''\) can be represented by
\(a (1,1) =
(a,a)\text{.}\) Similarly another possible basis would be
\(\{ (-1,-1) \}\text{.}\) Then the vector
\((a,a)\) would be represented as
\((-a) (-1,-1)\text{.}\) In this case, the subspace
\(S''\) has many different bases, two of which are
\(\{(1,1)\}\) and
\(\{(-1,-1)\}\text{,}\) and the vector
\((a,a)\) has a different representation (different constant) for the different bases.
Row and column spaces of a matrix are also examples of subspaces, as they are given as the span of vectors. We can use what we know about row spaces and column spaces from the previous section to find a basis.
Example 3.6.8.
Earlier, we considered the matrix
\begin{equation*}
A =
\begin{bmatrix}
1 & 2 & 3 & 4 \\
2 & 4 & 5 & 6 \\
3 & 6 & 7 & 8
\end{bmatrix} .
\end{equation*}
Using row reduction to find the pivot columns, we found
\begin{equation*}
\text{column space of $A$} \left(
\begin{bmatrix}
1 & 2 & 3 & 4 \\
2 & 4 & 5 & 6 \\
3 & 6 & 7 & 8
\end{bmatrix}
\right)
=
\operatorname{span}
\left\{
\begin{bmatrix}
1 \\
2 \\
3
\end{bmatrix}
,
\begin{bmatrix}
3 \\
5 \\
7
\end{bmatrix}
\right\} .
\end{equation*}
What we did was we found the basis of the column space. The basis has two elements, and so the column space of \(A\) is two dimensional.
We would have followed the same procedure if we wanted to find the basis of the subspace \(X\) spanned by
\begin{equation*}
\begin{bmatrix}
1 \\
2 \\
3
\end{bmatrix}
,
\begin{bmatrix}
2 \\
4 \\
6
\end{bmatrix}
,
\begin{bmatrix}
3 \\
5 \\
7
\end{bmatrix}
,
\begin{bmatrix}
4 \\
6 \\
8
\end{bmatrix}
.
\end{equation*}
We would have simply formed the matrix \(A\) with these vectors as columns and repeated the computation above. The subspace \(X\) is then the column space of \(A\text{.}\)
Example 3.6.9.
Consider the matrix
\begin{equation*}
L =
\begin{bmatrix}
{1} & 2 & 0 & 0 & 3 \\
0 & 0 & {1} & 0 & 4 \\
0 & 0 & 0 & {1} & 5
\end{bmatrix}
\end{equation*}
Conveniently, the matrix is in reduced row echelon form. The column space is the span of the pivot columns, because the pivot columns always form a basis for the column space of a matrix. It is the 3-dimensional space
\begin{equation*}
\text{column space of $L$} =
\operatorname{span} \left\{
\begin{bmatrix}
1 \\
0 \\
0
\end{bmatrix}
,
\begin{bmatrix}
0 \\
1 \\
0
\end{bmatrix}
,
\begin{bmatrix}
0 \\
0 \\
1
\end{bmatrix}
\right\}
= {\mathbb{R}}^3 .
\end{equation*}
The row space is the 3-dimensional space
\begin{equation*}
\text{row space of $L$} =
\operatorname{span} \left\{
\begin{bmatrix}
1 & 2 & 0 & 0 & 3
\end{bmatrix}
,
\begin{bmatrix}
0 & 0 & 1 & 0 & 4
\end{bmatrix}
,
\begin{bmatrix}
0 & 0 & 0 & 1 & 5
\end{bmatrix}
\right\} .
\end{equation*}
As these vectors have 5 components, we think of the row space of \(L\) as a subspace of \({\mathbb{R}}^5\text{.}\)
Subsection Rank
In that last example, we noticed that the dimension of the row space and the column space were the same. It turns out that this is not a coincidence. In order to describe this in more detail, we need to define one more term.
Definition 3.6.10. Rank.
Given a matrix
\(A\text{,}\) the maximal number of linearly independent rows is called the
rank of
\(A\text{,}\) and we write “
\(\operatorname{rank} A\)”for the rank.
For example,
\begin{equation*}
\operatorname{rank}
\begin{bmatrix}
1 & 1 & 1 \\
2 & 2 & 2 \\
-1 & -1 & -1
\end{bmatrix}
=
1 .
\end{equation*}
The second and third row are multiples of the first one. We cannot choose more than one row and still have a linearly independent set. But what is
\begin{equation*}
\operatorname{rank}
\begin{bmatrix}
1 & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9
\end{bmatrix} \quad = \quad ?
\end{equation*}
That seems to be a tougher question to answer. The first two rows are linearly independent, so the rank is at least two. If we would set up the equations for the \(\alpha_1\text{,}\) \(\alpha_2\text{,}\) and \(\alpha_3\text{,}\) we would find a system with infinitely many solutions. One solution is
\begin{equation*}
\begin{bmatrix}
1 & 2 & 3
\end{bmatrix} -2
\begin{bmatrix}
4 & 5 & 6
\end{bmatrix} +
\begin{bmatrix}
7 & 8 & 9
\end{bmatrix} =
\begin{bmatrix}
0 & 0 & 0
\end{bmatrix} .
\end{equation*}
So the set of all three rows is linearly dependent, the rank cannot be 3. Therefore the rank is 2.
But how can we do this in a more systematic way? We find the row echelon form!
\begin{equation*}
\text{Row echelon form of}
\quad
\begin{bmatrix}
1 & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9
\end{bmatrix}
\quad
\text{is}
\quad
\begin{bmatrix}
1 & 2 & 3 \\
0 & 1 & 2 \\
0 & 0 & 0
\end{bmatrix} .
\end{equation*}
The elementary row operations do not change the set of linear combinations of the rows (that was one of the main reasons for defining them as they were). In other words, the span of the rows of the \(A\) is the same as the span of the rows of the row echelon form of \(A\text{.}\) In particular, the number of linearly independent rows is the same. And in the row echelon form, all nonzero rows are linearly independent. This is not hard to see. Consider the two nonzero rows in the example above. Suppose we tried to solve for the \(\alpha_1\) and \(\alpha_2\) in
\begin{equation*}
\alpha_1
\begin{bmatrix}
1 & 2 & 3
\end{bmatrix}
+
\alpha_2
\begin{bmatrix}
0 & 1 & 2
\end{bmatrix} =
\begin{bmatrix}
0 & 0 & 0
\end{bmatrix} .
\end{equation*}
Since the first column of the row echelon matrix has zeros except in the first row means that \(\alpha_1 = 0\text{.}\) For the same reason, \(\alpha_2\) is zero. We only have two nonzero rows, and they are linearly independent, so the rank of the matrix is 2. This also tells us that if we were trying to solve the system of equations
\begin{align*}
x_1 + 2x_2 + 3x_3 \amp= a \\
4x_1 + 5x_2 + 6x_3 \amp= b \\
7x_1 + 8x_2 + 9x_3 \amp= c
\end{align*}
we would get that one row of the reduced augmented matrix has all zeros on the left side, and so this system either has a free variable or is inconsistent, because only two equations here are relevant.
Referring back to the examples from earlier in this section, we could carry out the same calculations to say that
\begin{equation*}
\text{rank } \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix} = 2
\end{equation*}
and
\begin{equation*}
\text{rank } \begin{bmatrix} 1 & 2 & 0 & 0 & 3 \\ 0 & 0 & 1 & 0 & 4 \\0 & 0 & 0 & 1 & 5 \end{bmatrix} = 3.
\end{equation*}
We know how to find the set of linearly independent rows, but sometimes it may also be useful to find the linearly independent columns as well. It is a tremendously useful fact that the number of linearly independent columns is always the same as the number of linearly independent rows:
Theorem 3.6.11.
\(\operatorname{rank} A = \operatorname{rank} A^T\)
Or, in the context of the row and column spaces that we have already discussed:
Theorem 3.6.12.
Rank The dimension of the column space and the dimension of the row space of a matrix
\(A\) are both equal to the rank of
\(A\text{.}\)
This relates to the statement at the start of this section; since the number of vectors that we needed to take to get a basis of linearly independent columns was always the same as the number of pivots, and the number of pivots is the rank, we get that above theorem.
Subsection Kernel
The set of solutions of a linear equation \(L\vec{x} = \vec{0}\text{,}\) the kernel of \(L\text{,}\) is a subspace: If \(\vec{x}\) and \(\vec{y}\) are solutions, then
\begin{equation*}
L(\vec{x}+\vec{y}) =
L\vec{x}+L\vec{y} =
\vec{0}+\vec{0} = \vec{0} ,
\qquad \text{and} \qquad
L(\alpha \vec{x}) =
\alpha L \vec{x} =
\alpha \vec{0} = \vec{0}.
\end{equation*}
So \(\vec{x}+\vec{y}\) and \(\alpha \vec{x}\) are solutions. The dimension of the kernel is called the nullity of the matrix.
The same sort of idea governs the solutions of linear differential equations. We try to describe the kernel of a linear differential operator, and as it is a subspace, we look for a basis of this kernel. Much of this book is dedicated to finding such bases.
The kernel of a matrix is the same as the kernel of its reduced row echelon form. For a matrix in reduced row echelon form, the kernel is rather easy to find. If a vector
\(\vec{x}\) is applied to a matrix
\(L\text{,}\) then each entry in
\(\vec{x}\) corresponds to a column of
\(L\text{,}\) the column that the entry multiplies. To find the kernel, pick a non-pivot column make a vector that has a
\(-1\) in the entry corresponding to this non-pivot column and zeros at all the other entries corresponding to the other non-pivot columns. Then for all the entries corresponding to pivot columns make it precisely the value in the corresponding row of the non-pivot column to make the vector be a solution to
\(L \vec{x} = \vec{0}\text{.}\) This procedure is best understood by example.
Example 3.6.13.
Consider
\begin{equation*}
L =
\begin{bmatrix}
\mybxsm{1} & 2 & 0 & 0 & 3 \\
0 & 0 & \mybxsm{1} & 0 & 4 \\
0 & 0 & 0 & \mybxsm{1} & 5
\end{bmatrix} .
\end{equation*}
This matrix is in reduced row echelon form, the pivots are marked. There are two non-pivot columns, so the kernel has dimension 2, that is, it is the span of 2 vectors. Let us find the first vector. We look at the first non-pivot column, the \(2^{\text{nd}}\) column, and we put a \(-1\) in the \(2^{\text{nd}}\) entry of our vector. We put a \(0\) in the \(5^{\text{th}}\) entry as the \(5^{\text{th}}\) column is also a non-pivot column:
\begin{equation*}
\begin{bmatrix}
? \\ -1 \\ ? \\ ? \\ 0
\end{bmatrix} .
\end{equation*}
Let us fill the rest. When this vector hits the first row, we get a \(-2\) and \(1\) times whatever the first question mark is. So make the first question mark \(2\text{.}\) For the second and third rows, it is sufficient to make it the question marks zero. We are really filling in the non-pivot column into the remaining entries. Let us check while marking which numbers went where:
\begin{equation*}
\begin{bmatrix}
1 & \mybxsm{2} & 0 & 0 & 3 \\
0 & \mybxsm{0} & 1 & 0 & 4 \\
0 & \mybxsm{0} & 0 & 1 & 5
\end{bmatrix}
\begin{bmatrix}
\mybxsm{2} \\ -1 \\ \mybxsm{0} \\ \mybxsm{0} \\ 0
\end{bmatrix}
=
\begin{bmatrix}
0 \\ 0 \\ 0
\end{bmatrix}
.
\end{equation*}
Yay! How about the second vector. We start with
\begin{equation*}
\begin{bmatrix}
? \\ 0 \\ ? \\ ? \\ -1 .
\end{bmatrix}
\end{equation*}
We set the first question mark to 3, the second to 4, and the third to 5. Let us check, marking things as previously,
\begin{equation*}
\begin{bmatrix}
1 & 2 & 0 & 0 & \mybxsm{3} \\
0 & 0 & 1 & 0 & \mybxsm{4} \\
0 & 0 & 0 & 1 & \mybxsm{5}
\end{bmatrix}
\begin{bmatrix}
\mybxsm{3} \\ 0 \\ \mybxsm{4} \\ \mybxsm{5} \\ -1
\end{bmatrix}
=
\begin{bmatrix}
0 \\ 0 \\ 0
\end{bmatrix}\text{.}
\end{equation*}
There are two non-pivot columns, so we only need two vectors. We have found the basis of the kernel. So,
\begin{equation*}
\text{kernel of $L$} =
\operatorname{span} \left\{
\begin{bmatrix}
2 \\ -1 \\ 0 \\ 0 \\ 0
\end{bmatrix}
,
\begin{bmatrix}
3 \\ 0 \\ 4 \\ 5 \\ -1
\end{bmatrix}
\right\}
\end{equation*}
What we did in finding a basis of the kernel is we expressed all solutions of
\(L \vec{x} = \vec{0}\) as a linear combination of some given vectors.
The procedure to find the basis of the kernel of a matrix
\(L\text{:}\)
-
Find the reduced row echelon form of
\(L\text{.}\)
-
Write down the basis of the kernel as above, one vector for each non-pivot column.
The rank of a matrix is the dimension of the column space, and that is the span of the pivot columns, while the kernel is the span of vectors in the non-pivot columns. So the two numbers must add to the number of columns.
Theorem 3.6.14. Rank-Nullity Theorem.
If a matrix \(A\) has \(n\) columns, rank \(r\text{,}\) and nullity \(k\) (dimension of the kernel), then
\begin{equation*}
n = r+k .
\end{equation*}
The theorem is immensely useful in applications. It allows one to compute the rank
\(r\) if one knows the nullity
\(k\) and vice versa, without doing any extra work.
Let us consider an example application, a simple version of the so-called Fredholm alternative. A similar result is true for differential equations. Consider
\begin{equation*}
A \vec{x} = \vec{b} ,
\end{equation*}
where \(A\) is a square \(n \times n\) matrix. There are then two mutually exclusive possibilities:
-
A nonzero solution
\(\vec{x}\) to
\(A \vec{x} = \vec{0}\) exists.
-
The equation
\(A \vec{x} = \vec{b}\) has a unique solution
\(\vec{x}\) for every
\(\vec{b}\text{.}\)
How does the Rank–Nullity theorem come into the picture? Well, if
\(A\) has a nonzero solution
\(\vec{x}\) to
\(A \vec{x} = \vec{0}\text{,}\) then the nullity
\(k\) is positive. But then the rank
\(r = n-k\) must be less than
\(n\text{.}\) In particular it means that the column space of
\(A\) is of dimension less than
\(n\text{,}\) so it is a subspace that does not include everything in
\({\mathbb{R}}^n\text{.}\) So
\({\mathbb{R}}^n\) has to contain some vector
\(\vec{b}\) not in the column space of
\(A\text{.}\) In fact, most vectors in
\({\mathbb{R}}^n\) are not in the column space of
\(A\text{.}\)
The idea of a kernel also comes up when defining and discussing eigenvectors. In order to find this vector, we are looking for a vector \(\vec{v}\) so that
\begin{equation*}
(A - \lambda I)\vec{v} = \vec{0}.
\end{equation*}
This means that we are looking for a vector \(\vec{v}\) that is in the kernel of the matrix \((A - \lambda I)\text{.}\) Since the kernel is also a subspace, this means that the set of all eigenvectors of a matrix \(A\) with a certain eigenvalue is a subspace, so it has a dimension. This dimension is number of linearly independent eigenvectors with that eigenvalue, so it is the geometric multiplicity of this eigenvalue. This also motivates why this is sometimes called the eigenspace for a given eigenvalue. Finding a basis of this subspace (which is also finding the kernel of the matrix \(A - \lambda I\) ) is the exact same as the process of finding the eigenvectors of the matrix \(A\text{.}\)
Subsection Computing the inverse
If the matrix
\(A\) is square and there exists a unique solution
\(\vec{x}\) to
\(A \vec{x} = \vec{b}\) for any
\(\vec{b}\) (there are no free variables), then
\(A\) is invertible.
In particular, if
\(A \vec{x} = \vec{b}\) then
\(\vec{x} = A^{-1} \vec{b}\text{.}\) Now we just need to compute what
\(A^{-1}\) is. We can surely do elimination every time we want to find
\(A^{-1} \vec{b}\text{,}\) but that would be ridiculous. The mapping
\(A^{-1}\) is linear and hence given by a matrix, and we have seen that to figure out the matrix we just need to find where does
\(A^{-1}\) take the standard basis vectors
\(\vec{e}_1\text{,}\) \(\vec{e}_2\text{,}\) …,
\(\vec{e}_n\text{.}\)
That is, to find the first column of
\(A^{-1}\) we solve
\(A \vec{x} = \vec{e}_1\text{,}\) because then
\(A^{-1} \vec{e}_1 = \vec{x}\text{.}\) To find the second column of
\(A^{-1}\) we solve
\(A \vec{x} = \vec{e}_2\text{.}\) And so on. It is really just
\(n\) eliminations that we need to do. But it gets even easier. If you think about it, the elimination is the same for everything on the left side of the augmented matrix. Doing
\(n\) eliminations separately we would redo most of the computations. Best is to do all at once.
Therefore, to find the inverse of
\(A\text{,}\) we write an
\(n
\times 2n\) augmented matrix
\([ \,A ~|~ I\, ]\text{,}\) where
\(I\) is the identity matrix, whose columns are precisely the standard basis vectors. We then perform row reduction until we arrive at the reduced row echelon form. If
\(A\) is invertible, then pivots can be found in every column of
\(A\text{,}\) and so the reduced row echelon form of
\([ \,A ~|~ I\, ]\) looks like
\([ \,I ~|~ A^{-1}\, ]\text{.}\) We then just read off the inverse
\(A^{-1}\text{.}\) If you do not find a pivot in every one of the first
\(n\) columns of the augmented matrix, then
\(A\) is not invertible.
This is best seen by example.
Example 3.6.15. .
Find the inverse of the matrix
\begin{equation*}
\begin{bmatrix}
1 & 2 & 3 \\
2 & 0 & 1 \\
3 & 1 & 0
\end{bmatrix} .
\end{equation*}
Solution.
We write the augmented matrix and we start reducing:
\begin{align*}
\amp \left[
\begin{array}{ccc|ccc}
\mybxsm{1} & 2 & 3 & 1 & 0 & 0\\
2 & 0 & 1 & 0 & 1 & 0 \\
3 & 1 & 0 & 0 & 0 & 1
\end{array}
\right]
\to
\left[
\begin{array}{ccc|ccc}
\mybxsm{1} & 2 & 3 & 1 & 0 & 0\\
0 & -4 & -5 & -2 & 1 & 0 \\
0 & -5 & -9 & -3 & 0 & 1
\end{array}
\right]
\to
\left[
\begin{array}{ccc|ccc}
\mybxsm{1} & 2 & 3 & 1 & 0 & 0\\
0 & \mybxsm{1} & \nicefrac{5}{4} & \nicefrac{1}{2} & \nicefrac{1}{4} & 0 \\
0 & -5 & -9 & -3 & 0 & 1
\end{array}
\right]
\to \\
\to
\amp
\left[
\begin{array}{ccc|ccc}
\mybxsm{1} & 2 & 3 & 1 & 0 & 0\\
0 & \mybxsm{1} & \nicefrac{5}{4} & \nicefrac{1}{2} & \nicefrac{1}{4} & 0 \\
0 & 0 & \nicefrac{-11}{4} & \nicefrac{-1}{2} & \nicefrac{-5}{4} & 1
\end{array}
\right]
\to
\left[
\begin{array}{ccc|ccc}
\mybxsm{1} & 2 & 3 & 1 & 0 & 0\\
0 & \mybxsm{1} & \nicefrac{5}{4} & \nicefrac{1}{2} & \nicefrac{1}{4} & 0 \\
0 & 0 & \mybxsm{1} & \nicefrac{2}{11} & \nicefrac{5}{11} & \nicefrac{-4}{11}
\end{array}
\right]
\to\\
\to
\amp
\left[
\begin{array}{ccc|ccc}
\mybxsm{1} & 2 & 0 & \nicefrac{5}{11} & \nicefrac{-5}{11} & \nicefrac{12}{11} \\
0 & \mybxsm{1} & 0 & \nicefrac{3}{11} & \nicefrac{-9}{11} & \nicefrac{5}{11} \\
0 & 0 & \mybxsm{1} & \nicefrac{2}{11} & \nicefrac{5}{11} & \nicefrac{-4}{11}
\end{array}
\right]
\to
\left[
\begin{array}{ccc|ccc}
\mybxsm{1} & 0 & 0 & \nicefrac{-1}{11} & \nicefrac{3}{11} & \nicefrac{2}{11} \\
0 & \mybxsm{1} & 0 & \nicefrac{3}{11} & \nicefrac{-9}{11} & \nicefrac{5}{11} \\
0 & 0 & \mybxsm{1} & \nicefrac{2}{11} & \nicefrac{5}{11} & \nicefrac{-4}{11}
\end{array}
\right] \text{.}
\end{align*}
So
\begin{equation*}
{\begin{bmatrix}
1 & 2 & 3 \\
2 & 0 & 1 \\
3 & 1 & 0
\end{bmatrix}}^{-1}
=
\begin{bmatrix}
\nicefrac{-1}{11} & \nicefrac{3}{11} & \nicefrac{2}{11} \\
\nicefrac{3}{11} & \nicefrac{-9}{11} & \nicefrac{5}{11} \\
\nicefrac{2}{11} & \nicefrac{5}{11} & \nicefrac{-4}{11}
\end{bmatrix} .
\end{equation*}
Not too terrible, no? Perhaps harder than inverting a
\(2 \times 2\) matrix for which we had a formula, but not too bad. Really in practice this is done efficiently by a computer.
Subsection Trace and Determinant of Matrices
The next thing to add into our toolbox of matrices is the idea of the trace of a matrix, and how it and the determinant relate to the eigenvalues of said matrix.
Definition 3.6.16. Trace.
Let
\(A\) be an
\(n \times n\) square matrix. The
trace of
\(A\) is the sum of all diagonal entries of
\(A\text{.}\)
For example, if we have the matrix
\begin{equation*}
\begin{bmatrix}
1 & 4 & -2 \\
3 & 2 & 5 \\
0 & 1 & 3
\end{bmatrix}
\end{equation*}
the trace is \(1 + 2 + 3 = 6\text{.}\)
The trace is important in our context because it also tells us something about the eigenvalues of a matrix. To work this out, let’s consider the generic \(2\times 2\) matrix and how we would find the eigenvalues. If we have a \(2 \times 2\) matrix of the form
\begin{equation*}
A = \begin{bmatrix} a & b \\ c & d
\end{bmatrix}
\end{equation*}
we can write out the expression \(\det(A - \lambda I)\) in order to find the eigenvalues. In this case, we would get
\begin{equation*}
\det(A - \lambda I) = \det\left( \begin{bmatrix} a - \lambda & b \\ c & d - \lambda \end{bmatrix} \right) = (a-\lambda)(d-\lambda) - bc = \lambda^2 - (a+d)\lambda + (ad - bc).
\end{equation*}
However, the coefficients in this polynomial look familiar. \((ad-bc)\) is just the determinant of the matrix \(A\text{,}\) and \(a+d\) is the trace. Therefore, for any \(2 \times 2\) matrix, we could write the characteristic polynomial as
\begin{equation}
\det(A - \lambda I) = \lambda^2 - T\lambda + D\tag{3.6.1}
\end{equation}
where \(T\) is the trace of the matrix and \(D\) is the determinant. On the other hand, assume that \(r_1\) and \(r_2\) are the two eigenvalues of this matrix (whether they be real, complex, or repeated). In that case, we know that this polynomial has \(r_1\) and \(r_2\) as roots. Therefore, it is equal to
\begin{equation}
\det(A - \lambda I) = (\lambda - r_1)(\lambda - r_2) = \lambda^2 - (r_1 + r_2)\lambda + r_1r_2.\tag{3.6.2}
\end{equation}
Matching up the coefficient of
\(\lambda\) and the constant term in
(3.6.1) and
(3.6.2) gives the relation that
\begin{equation*}
T = r_1 + r_2 \qquad D = r_1r_2,
\end{equation*}
that is, the trace of the matrix is the sum of the eigenvalues, and the determinant of the matrix is the product of the eigenvalues. We only showed this fact for \(2 \times 2\) matrices, but it does hold for matrices of all sizes, giving us the following theorem.
Theorem 3.6.17.
Let \(A\) be an \(n \times n\) square matrix with eigenvalues \(\lambda_1,\ \lambda_2,\ ..., \lambda_n\text{,}\) written with multiplicity if needed. Then
-
The trace of
\(A\) is
\(\lambda_1 + \lambda_2 + \cdots + \lambda_n\text{.}\)
-
The determinant of
\(A\) is
\((\lambda_1)(\lambda_2)\cdots(\lambda_n)\text{.}\)
From the above statement, we note that if any of the eigenvalues is zero, the product of all eigenvalues will be zero, and so the matrix will have zero determinant. This gives an extra follow-up fact, and addition to .
Theorem 3.6.18.
A matrix
\(A\) is invertible if and only if all of it’s eigenvalues are non-zero.
Example 3.6.19.
Use the facts above to analyze the eigenvalues of the matrix
\begin{equation*}
A = \begin{bmatrix} 1 & 2 \\ 5 & 4 \end{bmatrix}.
\end{equation*}
Solution.
From the matrix
\(A\text{,}\) we can compute that the trace of
\(A\) is
\(1+4=5\text{,}\) and the determinant is
\((1)(4) - (2)(5) = -6\text{.}\) Based on the theorem above, we know that the two eigenvalues of this matrix must add to
\(5\) and multiply to
\(-6\text{.}\) While you could probably guess the numbers here, the important take-aways from this example are what we can learn.
The main fact to point out is that this is enough information, in the \(2 \times 2\) case, to tell us that the eigenvalues have to be real and distinct. Since their product is a negative number, we can eliminate the other two options. If we have two complex roots, they must be of the form \(x + iy\) and \(x-iy\text{,}\) and so the product is
\begin{equation*}
(x+iy)(x-iy) = x^2 + ixy - ixy - i^2y^2 = x^2 + y^2
\end{equation*}
which is always positive, no matter what
\(x\) and
\(y\) are. Similarly, if we have a repeated eigvalue, the product will be that number squared, which is also positive. Therefore, if the determinant of a
\(2 \times 2\) matrix is negative, the eigenvalues must be real and distinct, with one being positive and one negative (otherwise the product can not be negative). These facts will be important when we start to analyze the solutions to systems of differential equations in
Chapter 4.
Example 3.6.20.
What can be said about the eigenvalues of the matrix
\begin{equation*}
A = \begin{bmatrix}
0 & -1 & 0 \\
2 & 2 & 0 \\
-7 &-3 & -1
\end{bmatrix}?
\end{equation*}
Solution.
We can find the same information as the previous example. The trace of
\(A\) is
\(1\text{,}\) and the determinant, by cofactor expansion along column 3, is
\((-1)(0 + 2) = -2\text{.}\) Therefore, the sum of the
three eigenvalues is
\(1\text{,}\) and the product of them is
\(-2\text{.}\) We don’t actually have enough information here to determine what the eigenvalues are. The issue is that with three eigenvalues, there are many different ways to get to a product being negative. There could be three negative eigenvalues, two positive and one negative, or one negative real with two complex eigenvalues. However, the one thing we do know for sure is that there must be one negative real eigenvalue. For this particular example, we can compute that the eigenvalues are
\(-1\text{,}\) \(1+i\text{,}\) and
\(1-i\text{,}\) so we did end up in the complex case.
Checkpoint 3.6.21.
Imagine that we have a
\(3 \times 3\) matrix with a positive determinant (it doesn’t matter what the trace is). Think about all the scenarios and verify that at least one eigenvalue must be real and positive for this to happen.
