Dr.
Ahlem Nemer 1
Course : Algebra 3
Year : 2023/2024
Department of Computer Science
———————————————————————————–
Chapter 2 :
Linear systems
1 General and basic definitions
Definition 1.1 Suppose that v1 , v2 , · · · , vn is a set of vectors. In order to have that v1 , v2 , · · · , vn are linearly
dependent, it is necessary that at least one of β1 , β2 , · · · , βn is not equal to 0 in the case where
n
X
βi vi = 0. (1)
i=1
Example 1.1 The set of vectors v1 = (1, −5), v2 = (−2, 10) is linearly dependent because, for β1 = 2 and
β2 = 1, we get
β1 v1 + β2 v2 = (0, 0).
Definition 1.2 Suppose that v1 , v2 , · · · , vn is a set of vectors and that
n
X
βi vi = 0 =⇒ βi = 0, f or all i = 1, · · · , n.
i=1
Then, we can say that the set v1 , v2 , · · · , vn is linearly independent.
Example 1.2 Take that v1 , v2 , v3 , v4 is the set of vectors where v1 = (0, 2, 3, 1), v2 = (1, 0, 5, 6), v3 = (3, 4, 0, 5) and v4 =
(1, 2, 3, 0). Then, for β1 , β2 , β3 , β4 ∈ R, we have
β1 v1 + β2 v2 + β3 v3 + β4 v4 = (0, 0, 0, 0).
Dr. Ahlem Nemer 2
This leads to
β2 + 3β3 + β4 = 0
2β1 + 4β3 + 2β4 = 0
3β1 + 5β2 + 3β4 = 0
β1 + 6β2 + 5β3 = 0
Here, we get β1 = β2 = β3 = β4 = 0. Then, we say that v1 , v2 , v3 , v4 are linearly independent.
Definition 1.3 Let A be an m × n matrix and suppose that
1. If there exist zero rows, they must represent the last rows of A.
2. In all non-zero rows, we have that the number one is the first non-zero entry. It is also possible to find
another non-zero number as the first non-zero entry.
3. From top to bottom of A , it is necessary to find more of zero numbers which are given before the first non-zero
entry.
Then, A is called an echelon matrix.
Definition 1.4 Suppose that A is a square matrix of order n and is also nonsingular. Let r be the rank of the
matrix A. Then, we have r = n
Definition 1.5 Suppose that A is an m × n matrix and that Cj f or j = 1, · · · , n, and Ri f or i = 1, · · · , m, are,
respectively, columns and rows of the matrix A. Let r be the maximal number of linearly independent vectors,
i.e, columns or rows. Then, we can say that the rank of A is equal to r.
Example 1.3 Let A be a square matrix
5 3 0 5
0 8 5 1
A=
4
,
7 3 2
7 2 1 3
Then, the rank of A is equal to 4.
Definition 1.6 Let A be an echelon matrix, and let r denote the number of non-zero rows of A. Then, we can
say that the rank of A is equal to r.
Dr. Ahlem Nemer 3
2 Non-homogeneous and homogeneous systems
Definition 2.1 A system of equations that is written in the form
a11 x1 + a12 x2 + · · · + a1n xn = b1 ,
a21 x1 + a22 x2 + · · · + a2n xn = b2 ,
..
.
am1 x1 + am2 x2 + · · · + amn xn = bm ,
or is given by
AX = B, (2)
represents a linear system of m equations in n unknowns. There exists only one unknown vector, denoted by X,
of the components x1 , x2 , · · · , xn . To be more precise, the given system (2) is defined by
a11 a12 · · · a1n x1 b1
a21 a22 · · · a2n x2 b2
.. = .. .
..
. . .
am1 am2 ··· amn xn bm
Definition 2.2 Let AX = B be a linear system. Then, we say
1. AX = B is called a homogeneous system in the case where all the components of the vector B are zeros.
2. AX = B is called a non-homogeneous system in the case where B has at least one component that is not
equal to zero.
Definition 2.3 Let AX = B be a linear system of m equations in n unknowns of the form
a11 a12 · · · a1n x1 b1
a21 a22 · · · a2n x2 b2
.. = .. ,
..
. . .
am1 am2 ··· amn xn bm
where A is a so-called coefficient matrix, and where X and B are column vectors. Then, the matrix which is
defined by
a11 a12 · · · a1n b1
a21 a22 · · · a2n b2
.. ,
.. .. ..
. . . .
am1 am2 · · · amn bm
is a so-called augmented matrix.
Dr. Ahlem Nemer 4
Theorem 2.1 Let AX = B be a homogeneous system. Then, there exist non-trivial solutions of this system if
and only if the rank of the matrix A which is denoted by r satisfies r ≺ n.
Theorem 2.2 Suppose that A is an n-square matrix defined as
A = [v1 , v2 , · · · , vn ],
where v1 , v2 , · · · , vn are vectors. Then, we say that v1 , v2 , · · · , vn are linearly independent if and only if the
matrix A represents a nonsingular matrix.
Theorem 2.3 Let AX = B be a non-homogeneous system. Then, there exist solutions of this system if and
only if the rank of the augmented matrix is equal to the rank of A, denoted by r. To be more precise, we can say
that
1. there exists a unique solution when r = n.
2. There exist infinite solutions when r ≺ n.
Remark 2.1 Let AX = B be a linear system, where A is an m × n matrix, and where X and B are vectors
defined, respectively, by
x1 b1
x2 b2
.. and .
..
. .
xn bm
Then, we have the three following cases:
1. When we take that m ≺ n, the system AX = B is under-determined.
2. When we take that m = n, the system AX = B is determined.
3. When we take that m n, the system AX = B is over-determined.
Remark 2.2 .
1. X = (0, 0, · · · , 0)T is the trivial solution of a homogeneous system.
2. There exist non-trivial solutions of a homogeneous system when m ≺ n.
Dr. Ahlem Nemer 5
3 Method of Gauss elimination
The linear system of m equations in n unknowns
a11 x1 + a12 x2 + · · · + a1n xn = b1 ,
a21 x1 + a22 x2 + · · · + a2n xn = b2 ,
..
.
am1 x1 + am2 x2 + · · · + amn xn = bm ,
can be solved by applying the method of Gauss elimination. For this, we first need to construct the augmented
matrix
a11 a12 · · · a1n b1
a21 a22 · · · a2n b2
.. .
.. .. ..
. . . .
am1 am2 ··· amn bm
Moreover, we check the element a11 which must satisfy a11 6= 0. We proceed to multiply 1 − th row by −ai1 /a11
for i = 1, · · · , m and to add the results of this operation to the other rows. The application of this procedure
(r − 1) times leads to get a new matrix.
Remark 3.1 When we use the method of Gauss elimination, it is necessary to change the position of the
equations in the case where a11 = 0.
Example 3.1 Find the solution of this system
x1 + 3x2 + x4 = 1,
2x1 + 5x2 + 2x4 = 3,
3x1 + x3 + 3x4 = 1,
x1 + 3x2 + 4x3 + 8x4 = 2.
The augmented matrix is defined by
1 3 0 1 1
2 5 0 2 3
.
3 0 1 3 1
1 3 4 8 2
The application of the Gauss elimination method leads to get
1 3 0 1 1
0 −1 0 0 1
,
0 −9 1 0 −2
0 0 4 7 1
Dr. Ahlem Nemer 6
1 3 0 1 1
0
−1 0 0 1 ,
0 0 1 0 −11
0 0 4 7 1
1 3 0 1 1
0
−1 0 0 1 .
0 0 1 0 −11
0 0 0 7 45
Here, we have
x1 + 3x2 + x4 = 1,
−x2 = 1,
x3 = −11,
7x4 = 45.
Then, the solution of the given system is x1 = −17/7, x2 = −1, x3 = −11, x4 = 45/7. This means X =
(−17/7, −1, −11, 45/7)T .
Dr. Ahlem Nemer 7
4 Solvability of systems by employing matrix inverses and by deter-
minants
Let AX = B be a linear system of m equations in n unknowns. If we suppose that m = n. Then, as we show in
Chapter 1, it is possible to employ Cramer’s rule to solve this system. This method can also be called the method
of determinants. On the other hand, it is possible to apply the method of matrix inversion. More precisely,
under the condition that A is nonsingular, we can say that there exists a unique solution which is defined by
X = A−1 B. (3)
Theorem 4.1 Let A denote an n-square matrix and let B be a vector with B ∈ Rn . Then, we can say that all
these statements are equivalent.
1. A is a nonsingular matrix.
2. When B = 0, there exists the trivial solution for the homogeneous system AX = B.
3. The non-homogeneous system AX = B has solutions.
4. There exists a unique solution of the non-homogeneous system AX = B.
5. The determinant of the matrix A is not equal to zero.
References
[1] S. R. Koneru, Engineering Mathematics, Universities Press, 2002
[2] Xin-She Yang, Introduction to computational mathematics ( 2nd Edition), World Scientific Publishing
Company, 2014
[3] I. N. Bronshtein and K. A. Semendyayev and G. Musiol and H. Mühlig, Handbook of Mathematics,
Springer, 2015
[4] E. Rukmangadachari, Mathematical methods, Pearson Education India, 2009
[5] V. Sundarapandian, Numerical linear algebra, PHI Learning Private Limited, 2008
[6] Magar E. Magar, Data analysis in biochemistry and biophysics, Academic Press, 1972