Linear Systems of Algebraic Equations
This page presents some topics from Linear Algebra needed for construction of solutions to systems of linear algebraic equations and some applications. We use matrices and vectors as essential elements in obtaining and expressing the solutions.
Null Space or Kernel
If
A is an
\( m\times n \) matrix, then the solution space of the homogeneous system of algebraic equations
\( {\bf A}\,{\bf x} = {\bf 0} ,\) which is a subspace of
\( \mathbb{R}^n , \) is called the
null space or
kernel of matrix
A.
It is usually denoted by ker(
A). The null space of the adjoint matrix
\( {\bf A}^{\ast} = \overline{\bf A}^{\mathrm T} \) is
a subspace of
\( \mathbb{R}^m \) and is called the
cokernel of
A and denoted by coker(
A).
Theorem: Elementary row operations do not change the kernel and the row space of a matrix.
Theorem: Let \( L:\,V\, \mapsto \, U \) be a linear transformation.
The kernel of L is the subspace of V and the range of L is a subspace of U.
Theorem: If \( L:\,V\, \mapsto \, U \) is a linear transformation and V is
finite dimension, then
\[
\dim \left( \ker (L) \right) + \dim \left( \mbox{range}(L) \right) = \dim (V) .
\]
If
L is defined by an
m-by-
n matrix
A, which has the column space and row space to be of dimension
r, then the dimension of its kernel is
\( n-r \) and the dimension of its cokernel (which is left null space of
A or kernel of
\( {\bf A}^{\mathrm T} \) ) is
\( m-r .\)
Theorem: For a \( m\times n \) matrix, the kernel is the
orthogonal complement of the row space in \( \mathbb{R}^n = \mbox{Range} \left( {\bf A}^{\mathrm T} \right)
\oplus \mbox{kernel} \left( {\bf A} \right) . \)
Theorem: For a \( m\times n \) matrix, the cokernel (the
left null space) is the orthogonal complement of the column space in \( \mathbb{R}^m =
\mbox{Range} \left( {\bf A} \right) \oplus \mbox{kernel} \left( {\bf A}^{\mathrm T} \right) . \) ■
A Basis for the Kernel: If \( L:\,\mathbb{R}^n\, \mapsto \, \mathbb{R}^m \)
is a linear transformation given by \( L({\bf x}) = {\bf A}\,{\bf x} , \) for some
\( m \times n \) matrix A. To find a basis for ker(L), perform the following steps:
Step 1: Find B, the reduced row echelon form of A.
Step 2: Solve for one particular solution for each independent variable in the homogeneous system \( {\bf B}\,{\bf x} = {\bf 0} .\)
The ith such solution, \( {\bf v}_i , \) is found by setting the ith independent
variable equal to 1, and setting all other independent variables equal to 0.
The set \( \{ {\bf v}_1, \ {\bf v}_2 , \ \ldots , \ {\bf v}_k \} \) found in Step 2 is a basis for ker(L).
You may want to replace \( {\bf v}_i \) with \( c\,{\bf v}_i , \)
where \( c\ne 0 , \) to eliminate fractions. ■
Sage will compute a null space for us. Which is rather remarkable, as it is an infinite
set! Again, this is a powerful command, and there is lots of
associated theory, so we
will not understand everything about it right away, and it also has a radically different
name in Sage. But we will find it useful immediately. Lets reprise an example.
The relevant command to build the null space of a matrix is
.right_kernel(), where
again, we will rely exclusively on the “right” version. Also, to match our work in the
text, and make the results more recognizable, we will consistently use the keyword
option basis=’pivot’,
which we will be able to explain once we have more theory. Note too, that this is a place where it is critical that
matrices are defined to use the rationals as their number system (QQ).
sage:I = matrix(QQ, [[ 1, 4, 0, -1, 0, 7, -9],
... [ 2, 8, -1, 3, 9, -13, 7],
... [ 0, 0, 2, -3, -4, 12, -8],
... [-1, -4, 2, 4, 8, -31, 37]])
sage: nsp = I.right_kernel(basis=’pivot’)
Vector space of degree 7 and dimension 4 over Rational Field
User basis matrix:
[-4 1 0 0 0 0 0]
[-2 0 -1 -2 1 0 0]
[-1 0 3 6 0 1 0]
[ 3 0 -5 -6 0 0 1]
As we said,
nsp
contains a lot of unfamiliar information. Ignore most of it for
now. But as a set, we can test membership in nsp:
sage: x = vector(QQ, [3, 0, -5, -6, 0, 0, 1])
sage: x in nsp
True
sage: y = vector(QQ, [-4, 1, -3, -2, 1, 1, 1])
sage: y in nsp
True
sage: z = vector(QQ, [1, 0, 0, 0, 0, 0, 2])
sage: z in nsp
False
We did a bad thing above, as Sage likes to use I
for the imaginary number
i (which is also denoted by
j) and we just clobbered that. We won’t do it again. See below how to fix this.
nsp is an infinite set. Since we know the null space is defined as solution to a system of
equations, and the work above shows it has at least two elements, we are not surprised
to discover that the set is infinite
sage: nsp.is_finite()
False
Note that in Sage, the kernel of a matrix
A is the “left kernel”, i.e. the space of vectors
z
such that
\( {\bf z}\,{\bf A} = {\bf 0} . \) This space is called cokernel of matrix A.
sage: A = Matrix([[1,2,3],[3,2,1],[1,1,1]])
sage: kernel(A)
Free module of degree 3 and rank 1 over Integer Ring
Echelon basis matrix:
[ 1 1 -4]
Example. Let \( L\,:\, \mathbb{R}^5 \mapsto \mathbb{R}^4 \) be given by
\( L[{\bf x}] = {\bf A}\,{\bf x} , \) where
\[
{\bf A} = \begin{bmatrix} 8&4&16&32&0 \\ 4&2&10&22&-4 \\ -2&-1&-5&-11&7 \\ 6&3&15&33&-7 \end{bmatrix} .
\]
To find the kernel of of the linear operator
L, we use Gauss-Jordan elimination
\[
{\bf A} \, \sim \, {\bf R} = \begin{bmatrix} 1& \frac{1}{2} & 0& -2&0 \\ 0&0&1&3&0 \\ 0&0&0&0&1 \\ 0&0&0&0&0 \end{bmatrix} .
\]
Since the pivots are in columns 1, 3, and 5, the corresponding variables
\( x_1 , \ x_3 , \ x_4 \) are leading avriables, and
\( x_2 , \ x_4 \) are free variables. Therefore, the system of algebraic equations
\( {\bf A}\,{\bf x} = {\bf 0} \) can be written as
\[
\begin{cases}
x_1 &= - \frac{1}{2}\, x_2 + 2\,x_4 , \\
x_3 &= - x_4 , \\
x_5 &= 0 . \end{cases}
\]
We construct two particular solutions, first by setting \( x_2 =1 \quad\mbox{and} \quad x_4 =0 \)
to obtain \( {\bf u}_1 = \left[ -1, 2, 0,0,0 \right]^{\mathrm T} , \) and then setting \( x_2 =0 \quad\mbox{and} \quad x_4 =1 ,\)
yielding \( {\bf u}_2 = \left[ 2, 0, -3, 1, 0 \right]^{\mathrm T} . \)
The set \( \left\{ {\bf u}_1 , {\bf u}_2 \right\} \) forms a basis for ker(L), and thus
\( \mbox{dim}(\mbox{ker}(L) = \mbox{dim}(\mbox{ker}({\bf A}) = 2, \) which equals the number of independent variables. The entire
subspace ker(L) consists of all linear combinations of the basis vectors.
Example. Consider 2-by-4 matrix of rank 2
\[
{\bf A} = \begin{bmatrix} 1&2&3&4 \\ 0&1&2&3 \end{bmatrix} .
\]
The vectors
\( {\bf u}_1 = \left[ 1,\ 2, \ 3, \ 4 \right] \) and
\( {\bf u}_2 = \left[ 0, \ 1,\ 2, \ 3 \right] \)
form the basis for the row space. To find the kernel of matrix
A, we need to solve the system of equations
\[
\begin{cases} x_1 + 2 x_2 + 3 x_3 + 4x_4 &=0, \\
x_2 + 2x_3 + 3x_4 &=0. \end{cases}
\]
Since
\( x_1 = x_3 + 2x_4 \) and
\( x_2 = -2x_3 -3 x_4 , \) we find the basis
of the null space (= kernel) of
A to be spanned on two vectors:
\[
{\bf u}_3 = \left[ 1, \ -2, \ 1, \ 0 \right]^{\mathrm T} , \qquad {\bf u}_4 = \left[ 2, \ -3, \ 0, \ 1 \right]^{\mathrm T} .
\]
These four vectors are a basis in
\( \mathbb{R}^4 . \) Any vector
\( {\bf x} = \left[ a, \ b, \ c,\ d \right]^{\mathrm T} \)
can be split into
\( {\bf x}_r \) in the row space and
\( {\bf x}_n \) in the kernel:
\begin{align*}
\begin{bmatrix} a \\ b \\ c \\ d \end{bmatrix} &= \frac{7\,a +4\,b +c -2\,d}{10} \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \end{bmatrix} +
\frac{-2\,a -b +d}{2} \begin{bmatrix} 0 \\ 1 \\ 2 \\ 3 \end{bmatrix}
\\
& \quad +
\frac{-a -2\,b + 7\, c -4\, d}{10} \begin{bmatrix} 1 \\ -2 \\ 1 \\ 0 \end{bmatrix} +
\frac{2\, a - b -4\,c +3\,d}{10} \begin{bmatrix} 2 \\ -3 \\ 0 \\ 1 \end{bmatrix} .
\end{align*}
This allows us to build projection matrices for the row space
\[
{\bf R} = \left[ {\bf u}_1 , \ {\bf u}_2 \right] \frac{1}{10} \begin{bmatrix} 7&4&1&-2 \\ -10&-5&0&5 \end{bmatrix} =
\frac{1}{10} \begin{bmatrix} 7&4&1&-2 \\ 4&3&2&1 \\ 1&2&3&4 \\ -2&1&4&7 \end{bmatrix}
\]
and for the null space (kernel)
\[
{\bf K} = \left[ {\bf u}_3 , \ {\bf u}_4 \right] \frac{1}{10} \begin{bmatrix} -1&-2&7&-4 \\ 2&-1&-4&3 \end{bmatrix} =
\frac{1}{10} \begin{bmatrix} 3&-4&-1&2 \\ -4&7&-2&-1 \\ -1&-2&7&-4 \\ 2&-1&-4&3 \end{bmatrix} .
\]
The eigenvalues of both matrices
R and
K are 1,1,0,0, so they are projection because
\( {\bf R}^2 = {\bf R} \)
and
\( {\bf K}^2 = {\bf K} . \) Moreover, these projection matrices are orthogonal
(
RTR =
R RT =
I and
KTK =
K KT =
I)
because they are symmetric. These matrices are not defective; for instance,
the eigenvectors corresponding to double eigenvalue
\( \lambda_1 = 1 \) of matrix
K are
\( {\bf u}_1 = \left[ 2, \ -3, \ 0, \ 1 \right]^{\mathrm T} \) and
\( {\bf u}_2 = \left[ 1, \ -2, \ 1, \ 0 \right]^{\mathrm T} , \) while eigenvectors corresponding
to double eigenvalue
\( \lambda_2 = 0 \) are
\( {\bf u}_3 = \left[ 3, \ 2, \ 1, \ 0 \right]^{\mathrm T} \)
and
\( {\bf u}_4 = \left[ 2, \ 1, \ 0, \ -1 \right]^{\mathrm T} .\) Therefore, these two projection matrices
R and
K share the same minimal polynomial
\( \psi (\lambda ) = \lambda (\lambda -1) . \)
Multiplying A with its transpose, we get two symmetric square matrices
\[
{\bf A} \,{\bf A}^{\mathrm T} = \begin{bmatrix} 30 & 20 \\ 20 & 14 \end{bmatrix} \quad\mbox{with eigenvalues} \quad 22 \pm 4\sqrt{29} ,
\]
and
\[
{\bf A}^{\mathrm T} {\bf A} = \begin{bmatrix} 1&2&3&4 \\ 2&5&8&11 \\ 3&8&13&18 \\ 4&11&18&25 \end{bmatrix} \quad\mbox{with eigenvalues} \quad 22 \pm 4\sqrt{29} , \ 0, \ 0 .
\]
Matrices
A and
\( {\bf A}^{\mathrm T} {\bf A} \) have the same null space (= kernel).
Applications
