Solving linear systems of equations is
a central problem of Linear Algebra that we discuss in an
introductory way in this chapter. Such systems arise in numerous
applications from engineering to the natural and social sciences.
Major sources of linear systems of equations are the discretization
of differential equations and the linearization of nonlinear
equations. In this chapter we analyze the solution sets of linear
systems of equations and we characterize the number of solutions
using the echelon form from Chap. 5. We also develop an algorithm for
the computation of the solutions.
Definition
6.1
A linear system (of equations) over a
field K with n equations in m unknowns 
has the form
or
where the coefficient
matrix ![$$A=[a_{ij}]\in K^{n,m}$$](A320947_1_En_6_Chapter_IEq2.gif)
and the right hand side ![$$b=[b_i]\in K^{n,1}$$](A320947_1_En_6_Chapter_IEq3.gif)
are given. If 
, then the
linear system is called homogeneous, otherwise non-homogeneous. Every 
with 
is called a solution of the
linear system. All these 
form the solution set of the linear system,
which we denote by 
.
has the form
and the right hand side are given. If , then the
linear system is called homogeneous, otherwise non-homogeneous. Every with
is called a solution of the
linear system. All these form the solution set of the linear system,
which we denote by .The next result characterizes the
solution set 
of the linear system 
using the
solution set 
of the associated homogeneous
linear system 
.
of the linear system using the
solution set of the associated homogeneous
linear system .Lemma
6.2
Let 
and 
with 
be given. If 
, then
and with be given. If , then
Proof
If 
, and thus
,
then
Hence 
, which
shows that 
.
, and thus
,
then
, which
shows that .Let now 
and let
. Then
i.e., 
. Hence
,
which shows that 
.
and let
. Then
. Hence
,
which shows that .
We will have a closer look at the set
: Clearly, 
. If 
, then for all
we have 
,
and hence 
.
Furthermore, for 
we
have
and hence 
.
Thus, 
is a nonempty subset of
that
is closed under scalar multiplication and addition.
: Clearly, . If , then for all
we have ,
and hence .
Furthermore, for we
have
.
Thus, is a nonempty subset of
that
is closed under scalar multiplication and addition.Lemma
6.3
If 
, 
and 
, then 
.
Moreover, if S is
invertible, then 
.
, and , then .
Moreover, if S is
invertible, then .Proof
If 
, then also
, and thus 
, which shows
that 
.
If S is invertible and
, then
. Multiplying from the left with
yields
. Since 
, we have
.
, then also
, and thus , which shows
that .
If S is invertible and
, then
. Multiplying from the left with
yields
. Since , we have
.
Consider the linear system of
equations 
. By
Theorem 5.2 we can find a matrix
such that SA is in echelon
form. Let ![$$\widetilde{b}=[\widetilde{b}_i]:=Sb$$](A320947_1_En_6_Chapter_IEq55.gif)
, then
by Lemma 6.3, and the linear system 
takes the form
Suppose that 
, and let 
be the pivot columns. Using a
right-multiplication with a permutation matrix we can move the
r pivot columns of
SA to the first
r columns. This is achieved
by
![$$\begin{aligned} P^T := [e_{j_1},\dots ,e_{j_r},e_1,\dots , e_{j_1-1},e_{j_1+1},\dots ,e_{j_2-1},e_{j_2+1},\dots , e_{j_r-1},e_{j_r+1},\dots ,e_m]\in K^{m,m}, \end{aligned}$$](A320947_1_En_6_Chapter_Equ10.gif)
which yields
![$$\begin{aligned} \widetilde{A}:={SAP}^T= {\left[ \begin{array}{cc} I_r &{} \widetilde{A}_{12}\\ 0_{n-r,r} &{} 0_{n-r,m-r} \end{array}\right] ,} \end{aligned}$$](A320947_1_En_6_Chapter_Equ11.gif)
where 
. If 
, then we
have ![$$\widetilde{A}_{12}=[\;]$$](A320947_1_En_6_Chapter_IEq62.gif)
. This permutation leads to a
simplification of the following presentation, but it is usually
omitted in practical computations.
. By
Theorem 5.2 we can find a matrix
such that SA is in echelon
form. Let , then
by Lemma 6.3, and the linear system takes the form
, and let be the pivot columns. Using a
right-multiplication with a permutation matrix we can move the
r pivot columns of
SA to the first
r columns. This is achieved
by
. If , then we
have . This permutation leads to a
simplification of the following presentation, but it is usually
omitted in practical computations.Since 
, we can write 
as 
, or 
, which has the form
![$$\begin{aligned} \underbrace{\left[ \begin{array}{ccc|ccc} &{} &{} &{} &{} &{} \\ &{} I_r &{} &{} &{} \widetilde{A}_{12} &{}\\ &{} &{} &{} &{} &{}\\ \hline &{} &{} &{} &{} &{} \\ &{} 0_{n-r,r} &{} &{} &{} 0_{n-r,m-r} &{} \\ &{} &{} &{} &{} &{}\end{array}\right] }_{=\widetilde{A}:=SAP^T} \underbrace{\begin{bmatrix} y_1 \\ \vdots \\ y_r\\ y_{r+1}\\ \vdots \\ y_m \end{bmatrix}}_{=y:=Px} = \underbrace{\begin{bmatrix} \widetilde{b}_1 \\ \vdots \\ \widetilde{b}_r\\ \widetilde{b}_{r+1}\\ \vdots \\ \widetilde{b}_n \end{bmatrix}}_{=\widetilde{b}:=Sb}\!. \end{aligned}$$](A320947_1_En_6_Chapter_Equ1.gif)
The left-multiplication of x with P just means a different ordering of
the unknowns 
. Thus, the solutions of 
can be
easily recovered from the solutions of 
, and vice versa: We have
if and only if 
.
, we can write as , or , which has the form
(6.1)
. Thus, the solutions of can be
easily recovered from the solutions of , and vice versa: We have
if and only if .The solutions of (6.1) can now be determined
using the extended coefficient
matrix
![$$[\widetilde{A},\widetilde{b}]\in K^{n,m+1},$$](A320947_1_En_6_Chapter_Equ12.gif)
which is obtained by attaching 
as an extra column to 
.
Note that ![$$\mathrm{rank}(\widetilde{A})\le \mathrm{rank}([\widetilde{A},\widetilde{b}])$$](A320947_1_En_6_Chapter_IEq74.gif)
,
with equality if and only if 
.
as an extra column to .
Note that ,
with equality if and only if .If ![$$\mathrm{rank}(\widetilde{A})<\mathrm{rank}([\widetilde{A},\widetilde{b}])$$](A320947_1_En_6_Chapter_IEq76.gif)
,
then at least one of 
is
nonzero. Then (6.1) cannot have a solution, since all entries
of 
in the rows 
are zero.
,
then at least one of is
nonzero. Then (6.1) cannot have a solution, since all entries
of
in the rows
are zero.If, on the other hand, ![$$\mathrm{rank}(\widetilde{A})=\mathrm{rank}([\widetilde{A},\widetilde{b}])$$](A320947_1_En_6_Chapter_IEq80.gif)
,
then 
and
(6.1) can be
written as
This representation implies, in particular, that
From Lemma 6.2 we know that 
.
In order to determine 
we set 
in
(6.2), which
yields
![$$\begin{aligned} {\mathscr {L}}(\widetilde{A},0) = \big \{\; [\widehat{y}_1,\dots ,\widehat{y}_m]^T \; | \;&\widehat{y}_{r+1},\dots ,\widehat{y}_m\;\text{ arbitrary } \text{ and } \\&[\widehat{y}_1,\dots ,\widehat{y}_r]^T=0 -\widetilde{A}_{12}[\widehat{y}_{r+1},\dots ,\widehat{y}_{m}]^T\;\big \}.\nonumber \end{aligned}$$](A320947_1_En_6_Chapter_Equ3.gif)
If 
, then
![$$\widetilde{A}_{12}=[\;]$$](A320947_1_En_6_Chapter_IEq86.gif)
, 
and thus
,
i.e., the solution of 
is uniquely
determined.
,
then and
(6.1) can be
written as
(6.2)
.
In order to determine we set in
(6.2), which
yields
(6.3)
, then
, and thus
,
i.e., the solution of is uniquely
determined.Example
6.4
For the extended coefficient matrix
![$$\begin{aligned}{}[\widetilde{A},\widetilde{b}] \;=\; \left[ \begin{array}{ccc|c} 1 &{} 0 &{} 3 &{} \widetilde{b}_1 \\ 0 &{} 1 &{} 4 &{} \widetilde{b}_2 \\ 0 &{} 0 &{} 0 &{} \widetilde{b}_3 \end{array}\right] \in \mathbb Q^{3,4} \end{aligned}$$](A320947_1_En_6_Chapter_Equ13.gif)
we have ![$$\mathrm{rank}(\widetilde{A})=\mathrm{rank}([\widetilde{A},\widetilde{b}])$$](A320947_1_En_6_Chapter_IEq90.gif)
if and only if 
. If 
, then 
.
if and only if . If , then .If 
, then 
can be written as
![$$\begin{aligned} \begin{bmatrix}y_1\\ y_2\end{bmatrix}= \begin{bmatrix}\widetilde{b}_1\\ \widetilde{b}_2\end{bmatrix}- \begin{bmatrix}3\\ 4\end{bmatrix}\,[y_3]. \end{aligned}$$](A320947_1_En_6_Chapter_Equ14.gif)
Hence, ![$$\widetilde{b}^{(3)}=[\widetilde{b}_1,\widetilde{b}_2,0]^T\in {\mathscr {L}}(\widetilde{A},\widetilde{b})$$](A320947_1_En_6_Chapter_IEq96.gif)
and
![$$\begin{aligned} {\mathscr {L}}(\widetilde{A},0) = \big \{\; [\widehat{y}_1,\widehat{y}_2,\widehat{y}_3]^T \;|\; \widehat{y}_{3}\;\text{ arbitrary } \text{ and } \; [\widehat{y}_1,\widehat{y}_2]^T= -[3,4]^T [\widehat{y}_{3}]\;\big \}. \end{aligned}$$](A320947_1_En_6_Chapter_Equ15.gif)
, then can be written as
and
Summarizing our considerations we have
the following algorithm for solving a linear system of
equations.
Algorithm
6.5
Let 
and 
be given.
and be given.
![$$\mathrm{rank}(SA)<\mathrm{rank}([SA,\widetilde{b}])$$](A320947_1_En_6_Chapter_IEq101.gif)
![$$r=\mathrm{rank}(A)=\mathrm{rank}([SA,\widetilde{b}])$$](A320947_1_En_6_Chapter_IEq103.gif)
Since 
and ![$$\mathrm{rank}([A,b])=\mathrm{rank}([SA,\widetilde{b}])=\mathrm{rank}([\widetilde{A},\widetilde{b}])$$](A320947_1_En_6_Chapter_IEq110.gif)
,
the discussion above also yields the following result about the
different cases of the solvability of a linear system of
equations.
and ,
the discussion above also yields the following result about the
different cases of the solvability of a linear system of
equations.Corollary
6.6
For 
and 
the following assertions hold:
and the following assertions hold:
- (1)
If
![$$\mathrm{rank}(A)<\mathrm{rank}([A,b])$$](A320947_1_En_6_Chapter_IEq113.gif)
, then
. - (2)
If
![$$\mathrm{rank}(A)=\mathrm{rank}([A,b])=m$$](A320947_1_En_6_Chapter_IEq115.gif)
, then
(i.e., there exists a unique
solution). - (3)
If
![$$\mathrm{rank}(A)=\mathrm{rank}([A,b])<m$$](A320947_1_En_6_Chapter_IEq117.gif)
, then
there exist many solutions. If the field K has infinitely many elements (e.g.,
when 
, 
or 
), then there exist infinitely many
pairwise distinct solutions.
Example
6.7
Let 
and consider the linear system of
equations 
with
We form [A, b] and apply the Gaussian elimination
algorithm in order to transform A into echelon form:
![$$\begin{aligned}{}[A,b]&\leadsto&\left[ \begin{array}{rrrr|r} 1 &{} 2 &{} 2 &{} 1 &{} 1\\ 0 &{} 1 &{} 0 &{} 3 &{} 0\\ 0 &{} -2 &{} 1 &{} -1 &{} 1\\ 0 &{} -1 &{} 1 &{} 2 &{} 1\\ 0 &{} -1 &{} 1 &{} 2 &{} 1 \end{array}\right] \;\leadsto \; \left[ \begin{array}{rrrr|r} 1 &{} 2 &{} 2 &{} 1 &{} 1\\ 0 &{} 1 &{} 0 &{} 3 &{} 0\\ 0 &{} 0 &{} 1 &{} 5 &{} 1\\ 0 &{} 0 &{} 1 &{} 5 &{} 1\\ 0 &{} 0 &{} 1 &{} 5 &{} 1 \end{array}\right] \\&\leadsto&\left[ \begin{array}{rrrr|r} 1 &{} 2 &{} 2 &{} 1 &{} 1\\ 0 &{} 1 &{} 0 &{} 3 &{} 0 \\ 0 &{} 0 &{} 1 &{} 5 &{} 1 \\ 0 &{} 0 &{} 0 &{} 0 &{} 0 \\ 0 &{} 0 &{} 0 &{} 0 &{} 0 \end{array}\right] \;\leadsto \; \left[ \begin{array}{rrrr|r} 1 &{} 0 &{} 2 &{} -5 &{} 1 \\ 0 &{} 1 &{} 0 &{} 3 &{} 0\\ 0 &{} 0 &{} 1 &{} 5 &{} 1\\ 0 &{} 0 &{} 0 &{} 0 &{} 0\\ 0 &{} 0 &{} 0 &{} 0 &{} 0 \end{array}\right] \\&\leadsto&\left[ \begin{array}{rrrr|r} 1 &{} 0 &{} 0 &{} -15 &{} -1\\ 0 &{} 1 &{} 0 &{} 3 &{} 0 \\ 0 &{} 0 &{} 1 &{} 5 &{} 1\\ 0 &{} 0 &{} 0 &{} 0 &{} 0\\ 0 &{} 0 &{} 0 &{} 0 &{} 0 \end{array}\right] \;=\; [SA|\widetilde{b}]. \end{aligned}$$](A320947_1_En_6_Chapter_Equ17.gif)
Here ![$$\mathrm{rank}(SA) = \mathrm{rank}([SA,\widetilde{b}])=3$$](A320947_1_En_6_Chapter_IEq123.gif)
,
and hence there exist solutions. The pivot columns are 
for
, so
that 
and
. Now 
can be written as
![$$\begin{aligned} \begin{bmatrix} x_1 \\ x_2 \\ x_3\end{bmatrix}= \left[ \begin{array}{r} -1 \\ 0 \\ 1\end{array}\right] - \left[ \begin{array}{r} -15 \\ 3 \\ 5\end{array}\right] \,[x_4]. \end{aligned}$$](A320947_1_En_6_Chapter_Equ18.gif)
Consequently, ![$$\widetilde{b}^{(4)}=[-1,0,1,0]^T\in {\mathscr {L}}(A,b)$$](A320947_1_En_6_Chapter_IEq129.gif)
and 
,
where
![$$\begin{aligned} {\mathscr {L}}(A,0) = \big \{\; [\widehat{x}_1,\ldots ,\widehat{x}_4]^T \;|\; \widehat{x}_{4}\;\text{ arbitrary } \text{ and } \; [\widehat{x}_1,\widehat{x}_2,\widehat{x}_3]^T= -[-15,3,5]^T [\widehat{x}_{4}]\;\big \}. \end{aligned}$$](A320947_1_En_6_Chapter_Equ19.gif)
and consider the linear system of
equations with
,
and hence there exist solutions. The pivot columns are for
, so
that and
. Now can be written as
and ,
where
Exercises
- 6.1
Find a field K and matrices
,
and 
with 
. - 6.2
Determine
for the following A and b:
![$$\begin{aligned}&A = \left[ \begin{array}{rrr} 1 &{} 1 &{} 1 \\ 1 &{} 2 &{} -1 \\ 1 &{} -1 &{} 6 \end{array}\right] \in \mathbb R^{3,3}, \quad b = \left[ \begin{array}{r} 1 \\ -2 \\ 3 \end{array}\right] \in \mathbb R^{3,1},\\&A = \left[ \begin{array}{@{}r@{\quad }r@{\quad }r@{\quad }r@{}} 1 &{} 1 &{} 1 &{} 0 \\ 1 &{} 2 &{} -1 &{} -1 \\ 1 &{} -1 &{} 6 &{} 2 \end{array}\right] \in \mathbb R^{3,4}, \quad b = \left[ \begin{array}{r} 1 \\ -2 \\ 3 \end{array}\right] \in \mathbb R^{3,1},\\&A = \left[ \begin{array}{@{}r@{\quad }r@{\quad }r@{}} 1 &{} 1 &{} 1 \\ 1 &{} 2 &{} -1 \\ 1 &{} -1 &{} 6 \\ 1 &{} 1 &{} 1 \end{array}\right] \in \mathbb R^{4,3}, \quad b = \left[ \begin{array}{r} 1 \\ -2 \\ 3 \\ 1 \end{array}\right] \in \mathbb R^{4,1},\\&A = \left[ \begin{array}{@{}r@{\quad }r@{\quad }r@{}} 1 &{} 1 &{} 1 \\ 1 &{} 2 &{} -1 \\ 1 &{} -1 &{} 6 \\ 1 &{} 1 &{} 1 \end{array}\right] \in \mathbb R^{4,3}, \quad b = \left[ \begin{array}{r} 1 \\ -2 \\ 3 \\ 0 \end{array}\right] \in \mathbb R^{4,1}. \end{aligned}$$](A320947_1_En_6_Chapter_Equ20.gif)
- 6.3
Let
,
Determine
and 
in dependence of
. - 6.4
Let
and 
. For 
denote by 
the
ith column of B. Show that the linear system of
equations 
has
at least one solution 
if and only if
Find conditions under which this solution is unique.![$$\begin{aligned} \mathrm{rank}(A) = \mathrm{rank}([A,b_1])=\mathrm{rank}([A,b_2]) = \cdots = \mathrm{rank}([A,b_s]). \end{aligned}$$](A320947_1_En_6_Chapter_Equ22.gif)
- 6.5
Letbe given with
for all i. Determine a recursive formula for
the entries of the solution of the linear system 
.