Relationship to systems of linear equations

Linear maps: Matrices of Linear Maps

Relationship to systems of linear equations

Take another look at the system of linear equations \[ \begin{array}{cccccccc}
a_{11} x_1&+&a_{12}x_2&+&\ldots&+&a_{1n}x_n&=&b_1\\
\vdots &&\vdots&&\vdots &&\vdots&&\vdots\\
a_{m1} x_1&+&a_{m2}x_2&+&\ldots&+&a_{mn}x_n &=&b_m
\end{array}
\] with #(m\times n)#-coefficient matrix #A#. The system of equations can be written as a vector equation
\[
A\vec{x} = \vec{b}\phantom{xxx}
\]

The matrix #A# determines the linear map # L_A :\mathbb{R}^n\rightarrow\mathbb{R}^m#. In terms of this linear map the system can also be written as
\[
L_A( \vec{x})=\vec{b}
\]We recall that a system of linear equations is consistent if it has a solution.

Dimension of the solution space of a system of linear equationsLet #A# be an #(m\times n)#-matrix, and use #k# to denote the dimension of the column space, that is, the subspace of #\mathbb{R}^m# spanned by the columns of #A#. Moreover, let #\vec{b}# be a vector in #\mathbb{R}^m# and consider the system of linear equations #A\vec{x}=\vec{b}# of #m# linear equations with #n# unknowns, the coordinates of #\vec{x}#.

The system is consistent if and only if #\vec{b}# is part of the column space of #A#.
If the system is consistent, then the dimension of the solution space is equal to #n-k#.

1. According to the theorem of Inverse images of linear maps are affine subspaces, we find each solution to the equation # A \vec{x}=\vec{b}# as a sum of one particular solution and all vectors from the null space of #L_A#.

According to Theorem Image as a linear span the image space #\im{L_A}# of #L_ A # is the space #\linspan{ A \vec{e}_1,\ldots, A \vec{e}_n}#. This is the column space of the matrix #A#. The equation # A \vec{x} =\vec{b}# has at least one solution if and only if #\vec{b}\in\im{L_A}#, hence, if and only if #\vec{b}# is in the column space of the matrix.

2. As we saw in the proof of statement 1, the dimension of the solution space is equal to #\dim{\ker{A}}# if there is a solution. In this case, it follows from the Dimension theorem that the dimension is equal to \[{}\dim{\ker{A}} = n-\dim{\im{A}} = n-k\]

Later we will see that the dimension of the subspace of #\mathbb{R}^m# spanned by the columns is equal to the dimension of the subspace of #\mathbb{R}^n# spanned by the rows, that is, the rank of #A#.

The observant reader might already have concluded this from the Rank criteria for the existense of solutions of systems of linear equation. After all, there the fact stated (in terms of free parameters) that the dimension of the solution space is equal to #n-r#, where #r# is the rank. The rank stands for the dimension of the linear space spanned by the rows of #A#. We conclude that #n-k=n-r#, such that #r=k#. In words: the dimension of the space spanned by the rows of #A# is equal to the dimension of the space spanned by the columns of #A#.

The theorem can be described as follows: The dimension of the solution space is equal to the number of unknowns minus the number of `real' conditions.

A special consequence of the theorem says that #k=n# holds if and only if there is at most one solution to the system.

This solution method can be applied to arbitrary vector spaces of finite dimension.

From full inverse image of a linear map to matrix equationLet #L:V\to W# and #\vec{b}\in W#. The equation \[ L(\vec{v})=\vec{b}\] in the unknown vector #\vec{v}# in #V# has a solution #\vec{v}_0# if and only if #\vec{b}# lies in #\im{L}#. In that case, the solution space is the affine subspace \[\vec{v}_0+\ker{L}\]

If #V# has finite dimension #n# and #W# has finite dimension #m#, then this solution can be found, after the a choice of bases #\alpha# for #V# and #\beta # for #W#, by solving the system of linear equations with unknown #\vec{x}# in #\mathbb{R}^n# consisting of

\[{}_\beta L_\alpha \vec{x}=\beta(\vec{b})\]

The solution then consists of all vectors #\vec{v}=\alpha^{-1}(\vec{x})#, where #\vec{x}# is a solution of the system of linear equations.

The equation # L(\vec{v}) = \vec{b}# is equivalent to #\beta L\alpha^{-1}\alpha(\vec{v}) =\beta (\vec{b})#. If #\vec{v}=\alpha^{-1}(\vec{x})#, then this equation can be rewritten as #{}_\beta L_\alpha\vec{x}=\beta (\vec{b})#.

Consider the system of linear equations with augmented matrix \[A' = \left({\begin{array}{cccc|c} 6 & 6 & -2 & -2 & 54 \\ -7 & -9 & 4 & 2 & -74 \\ -7 & -10 & 5 & 2 & -80 \\ 3 & 2 & 0 & -1 & 21 \\ \end{array}}\right) \]

Express the solution set in the form #\vec{p} + \text{span}\left(\vec{v}_1,\ldots, {v}_t\right)# where #\vec{p}# is a particular solution to the system and #\vec{v}_1,\ldots, \vec{v}_t# are linearly independent.

#\vec{p} + \text{span}\left(\vec{v}_1,\ldots, {v}_t\right) = # # \matrix{ 3 \\ 5 \\ -1 \\ -2 } + \text{span}\left( \matrix{1 \\ -1 \\ -1 \\ 1 \\ } \right)#

We write
\[ A = \matrix{6 & 6 & -2 & -2 \\ -7 & -9 & 4 & 2 \\ -7 & -10 & 5 & 2 \\ 3 & 2 & 0 & -1 \\ }\phantom{xxx}\text{ and }\phantom{xxx} b = \matrix{54 \\ -74 \\ -80 \\ 21 \\ }\]
so #A' = \left(\begin{array}{c|c}A &\vec{b}\end{array}\right)#.

By row reduction, we can rewrite the augmented matrix to
\[ \matrix{1 & 0 & 0 & -1 & 5 \\ 0 & 1 & 0 & 1 & 3 \\ 0 & 0 & 1 & 1 & -3 \\ 0 & 0 & 0 & 0 & 0 \\ } \]
We can read off from this row reduced echelon form that the nullspace of #A# is # \text{span}\left( \matrix{1 \\ -1 \\ -1 \\ 1 \\ } \right)# and that \(\vec{p}= \matrix{ 3 \\ 5 \\ -1 \\ -2 } \) is a particular solution of #A\vec{x} = \vec{b}#. Thus, we arrive at the answer
\[\matrix{ 3 \\ 5 \\ -1 \\ -2 } + \text{span}\left( \matrix{1 \\ -1 \\ -1 \\ 1 \\ } \right)\]

The rank of #A# equals #{3}#. This is also the rank of #A'#, so solutions exist. In fact, since the kernel of #A# has dimension #t = 4 - 3 =1 #, the number of linearly independent vectors needed to span the direction space is #t#.

New example