Chapter

Contents
 1. Solutions and Elementary Operations

 2. Gaussian Elimination

 3. Homogeneous Equations
1.1. Solutions and Elementary Operations
coefficients variables = unknowns
 a1x1+a2x2+…+anxn=b is called a linear equation (phương trình
tuyến tính)
 A solution (nghiệm) to the equation is a sequence s1,s2,…,sn
such that a1s1+a2s2+…+ansn=b
 s1,s2,…,sn is called a solution to a system of linear equations if
s1,s2,…,sn is a solution to every equation of the system
 A system may have:
0
no solution
unique solution
1
an infinite family of solutions 
 A system that has no solution is called inconsistent (không
tương thích/ không nhất quán)
 A system that has at least one solution is called consistent
(tương thích/ nhất quán)

Inconsistent Consistent
(không (tương thích)
tương thích)
No solutions Unique solution Infinitely many
( vô nghiệm) (nghiệm duy nhất) solutions
(vô số nghiệm)
 Example 1
 x  2 y  1 x  y  z  1
 
x  2 y  3 x  y  z  3
no solution (0,2,1), (2,0,1) (t,2-t,1)

Inconsistent Consistent
(infinitely many solutions)
(t,2-t,1) is called a general solution and
given in parametric form, t is parameter
( t is arbitrary)
 Elementary Operations
(phép biến đổi sơ cấp)
 Interchange two equations (type I)

 Multiply one equation by a nonzero number (type II)

 Add a multiple of one equation to a different equation

(type III)
 Algebraic Method

3x1  2 x2  x3  x4  1 3 2 1 1 1
 x3  2 x4  0  
2 x1 2 0 1 2 0 
3x1  x2  2 x3  5 x4  2  3 1 2 5 2 
augmented matrix

coefficient matrix
constant matrix
 3 2 1 1   1
 2 0 1 2  0 
   
 3 1 2 5   2 
 Example 2
 Consider the system

x  y  1

 x  2 y  2
1 1 1
augmented matrix
1 2 2
 Example 2
x  y  1 x  y  1 x  y  1 x  0 y  0
   
 x  2 y  2 0 x  3 y  3 0 x  y  1 0 x  y  1
1  1 1 ( III ) 1  1 1 1 1 1
( II ) ( III ) 1 0 0
  
1 2 2 0 3 3 0 1 1 0 1 1

Solution (0,-1)
Theorem. Suppose an elementary operation is performed on a
system of linear equations. Then the resulting system has the
same set of solutions as the original system, so the two system
are equivalent (tương đương)
In this case,their augmented matrices are called row-equivalent
 1.2. Gaussian Elimination
(phép khử Gauss)
 By using elementary row operations to carry the
augment matrix to “nice” matrix such as

1 0 0*
0 1 0*
0 0 1*

( and it is said to be in row- echelon form

(dạng bậc thang theo dòng))
 A row-echelon matrix has 3
properties
 All the zero rows are at the
bottom
0 1 * * * * *  The first nonzero entry
0 0 0 1 * * *  from the left in each
  nonzero row is a 1, called
0 0 0 0 1 * * the leading 1 for that row
0 0 0 0 0 0 1   Each leading 1 is to the
  right of all leading 1’s in
0 0 0 0 0 0 0  the rows above it
 Row-echelon matrix
The row-echelon matrix has the “staircase” form

0 1 * * * * *
0 0 0 1 * * *

0 0 0 0 1 * *
leading ones  
0 0 0 0 0 0 1
0 0 0 0 0 0 0

( for any choice in *-position )

 Which is a row-echelon
matrix?
1 * *
1 * * 0 2 *
 0 0 1  
 
0 0 1

1 * * * 0 1 * *  1 * * 
0 1 * * 0 0 0 1  0 0 0
     
0 1 * * 0 0 0 0  0 0 1 
 A reduced row-echelon matrix
(ma trận bậc thang theo dòng thu
gọn) has the properties
 It is a row-echelon matrix
 Each leading 1 is the only 1 0 * 0 
0 1 * 0
nonzero entry in its  
column 0 0 0 1 
 Which is a reduced row-
echelon matrix?
1 * 0 
1 * 0  0 1 0
0 0 1   
 
 0 0 1 

1 0 * 0  0 1 * 0  1 * 0 
0 1 * 0  0 0 0 1  0 0 0
     
0 0 0 1  0 0 0 0  0 0 1 
 How to carry a matrix to
(reduced) row-echelon form?
Elementary row operations
 Gaussian Algorithm
Theorem. Every matrix can be brought to (reduced) row-
echelon form by a series of elementary row operations
 Step 1. If all row are zeros, stop
 Step 2. Otherwise, find the first column from the left
containing a nonzero entry (call it a) and move the row
containing a to the top position
 Step 3. Multiply that row by 1/a to creat the leading 1
 Step 4. By subtracting multiples of that row from the
rows below it, make each entry below the leading 1
zero
 Step 5. Repeat step 1-4 on the matrix consisting of the
remaining rows
 Gaussian Algorithm
0 0 0 0
0 0 0 0
step 1:    stop
0 0 0 0
  leading one
0 0 0 0

2 2 1 0   1   1 
0 0 1 3 1 1  0 1 1  0

r r 0 0 1 3  2r 
2 2
2 1 0 
1 2 4 r  r  
     0 0 1 3 
1 1 4

 
1 2
 0 0 1 3
0 3 0 6 0 3 0 6 0 3 0 6 0 3 0 6
       
4 7 5 1 4 7 5 1  4 7 5 1 0 3 7 1

step 2 step 3 step 4 step 5

 Example
Carry the matrix
 2 6 2 2 
 2 3 11 4 
 
 3 11 3 0 
 to row-echelon matrix
 to reduced row-
echelon matrix
 2 6 2 2  1 r  1 3 1 1  23r rr r 1 3 1 1 
1 2

 2 3 11 4    2 3 11 4    0 3 9 6 
1
2 1 3

     
 3 11 3 0   3 11 3 0   0 2 6 3

1 1 3 1 1  2 r  r
r2 1 3 1 1   1 r 1 3 1 1 
  0 1 3 2   0 1 3 2 
3
3 2 3 7
 0 1 3 2      
0 2 6 3 0 0 0 7  0 0 0 1 

row-echelon matrix
1 3 1 1  2 r  r 3 2 1 3 1 0 
 r r
0 1 3 2  3 1
0 1 3 0 
   
0 0 0 1  0 0 0 1 
 1 0 10 0 
3 r  r
2

 0
1
 1 3 0 
 
0 0 0 1 
reduced row-echelon matrix
 Do yourself – carry these matrices to
reduced row-echelon matrices
 0 1 3 2 

B   2 1 0 1  
 2 1 3 
A   3 0 0 4 
 1 0 2 

1 2 0 1 
 2 1 3 0 
 0 2 1 3 D 
C   0 5 3 2 
 1 3 0 1   
1 3 3 2 
 Gauss-Jordan Elimination
(for solving a system of linear equantions)
 Step 1.Using elementary row
operations, augmented matrix  1 0 10 0  x  0 y  10 z  0
reduced row-echelon matrix  0 1 3 0   0 x  1 y  3 z  0
 0 0 0 1  0 x  0 y  0 z  1
 Step 2. If a row [0 0 0…0 1] occurs,
the system is inconsistent reduced row echelon matrix

 Step 3. Otherwise, assign the

1 0 10 0  1x  0 y  10 z  0
nonleading variables as   
 0 1 3 0   0 x  1 y  3 z  0
parameters, solve for the leading
 0 0 0 0  0 x  0 y  0 z  0
variables in terms of parameters

z=t (parameter) z is nonleading variable

Solve the following system of equations
x  2y  3
2x  3y  2z  5
3x  7 y  2 z  10
Solution.
Carry the augmented matrix to reduced row-echelon form
 1 2 0 3  2 r  r 1 2 0 3  1 2 0 3 
  3r  r 1 2
  r r  
 2 3 2 5   0 1 2 1   0 1 2 1
1 3 2 3

 3 7 2 10  0 1 2 19  0 0 0 20 

1
1 2 0 3 
r  
  0 1 2 1
3
20

0 0 0 1 
inconsistent
  1 2 1 3 1  1 2 1 3 1
   
 2 4 1 0 5 
  0 0 3 6 3  leading one
 1 2 2 3 4  0 0 3 6 3
1 2 1 3 1  1 2 0 1 2 
   
  0 0 1 2 1   0 0 1 2 1 
 0 0 0 0 0  0 0 0 0 0 
reduced row echelon matrix
x2,x4 are nonleading
variables, so we set x1 = 2 + 2t - s
x2=t and x4=s x2 = t
(parameters) and then x3 = 1 + 2s
compute x1, x3 x4 = s
Do yourself – solve the following systems
given by augmented matrices

1 1 0 3 0 1 2 3 5 0  1 2 1 1 0 
     
1) 0 0 1 2 0 2) 0 1 2 2 0  3)  3 4 2 5 0
0 0 0 0 0 0 0 0 0 0   2 3 3 1 0 

 3 1 1 1 
 
4)  2 0 5 2
 0 2 13 8 
 Example
Which condition on the numbers a,b,c is the system
3x  y  z  a

x  y  2z  b
5 x  3 y  4 z  c

consistent ?
3 1 1 a  1 1 2 b  3r  r 1 2 1 1 2 b 
  r r
1
2
 5 r  r
1 3
 
1 1 2 b   3 1 1 a    0 4 7 a  3b 
5 3 4 c  5 3 4 c  0 8 14 c  5b 
3 r  r  1
1 2 1 2 b 
5 r  r
1 3
 
  0 4 7 a  3b 
 0 0 0 c  2a  b 
Answer: c-2a+b=0
 The rank of a matrix
 The reduced row-echelon form of a matrix A is
uniquely determined by A, but the row-
echelon form of A is not unique
 The number r of leading 1’s is the same in
each of the different row-echelon matrices
 As r depends only on A and not on the row-
echelon forms, it is called the rank of the
matrix A, and written r=rankA
 The rank of a matrix
 If the a matrix A has the row-echelon matrix is

0 1 * * * * *
0 0 0 1 * * *

0 0 0 0 1 * *
 
0 0 0 0 0 0 1
0 0 0 0 0 0 0
then rankA=4
 Theorem 2
Suppose a system of m equations in n
variables has a solution. If the rank of the
augment matrix is r then the set of
solutions involves exactly n-r parameters
leading one

1 2 1 3 1  1 2 1 3 1  1 2 1 3 1 
     
 2 4 1 0 5   0 0 3 6 3  0 0 1 2 1 
1 2 2 3 4  0 0 3 6 3 0 0 0 0 0
rankA=2

4(number of variables)- 2(rankA) =2

(two parameters : x2=t, x4=s)
 1.3.Homogeneous Equations
(phương trình thuần nhất)
 The system is called homogeneous (thuần nhất) if
the constant matrix has all the entry are zeros

 Note that every homogeneous system has at least

one solution (0,0,…,0), called trivial solution
(nghiệm tầm thường)

 If a homogeneous system of linear equations has

nontrivial solution (nghiệm không tầm thường) then
it has infinite family of solutions (vô số nghiệm)
Hệ thuần nhất mà số ẩn
nhiều hơn số pt
Chắc chắn vô số nghiệm
 Theorem 1
If a homogeneous system of linear
equations has more variables than
equations, then it has nontrivial solution
(in fact, infinitely many)

Note that the converse of theorem 1 is not

true
 System of equations Summary

System of Inconsistent Cosistent

( no Unique solution Infinitely many
solutions) (exactly one solutions
solution)
linear equations yes yes yes
linear equations that yes no yes
has more
variables than
equations
homogeneous linear no yes yes
equations
homogeneous linear no no yes
equations that has
more variables
than equations
 Exercises
1. Find all a,b such that the matrix is an reduced row-
echelon matrix.
a b 0
0 b 1
 
0 0 0 
 a=b=1 0 0 1 
 a=0 and b=1  
 a=b=0
1 0 0 
 a=1 and b=0 0 0 1 
 None of the others  
 Exercises
2. Find all values of m such that the system has no
solution, (another word: inconsistent)
x  2 y  z  3

3x  y  z  m
  x  y  z  1

 Answer:
 Carry the augmented matrix to row-echelon form

 1 2 1 3  3d1  d2 1 2 1 3  1 2 1 3 
d1  d3 d 2 d3
     
 3  5 1 m    0 1 2 m  9    0 1 2 m  9 
 1 1 1 1  0 1 2 2  0 0 0 m  7 

 The system has no solution iff m≠7

 Exercises
3. Choose the correct statements.
 If the system has trivial solution, then it is a
homogeneuos system
 A homogeneous system of 7 equations and 5
variables always has many solutions
 A consistent system of 12 equations and 15
unknowns must have infinitely many solutions
 If a homogeneous system has an nontrivial solution,
then it has infinitely many solutions

 Homogeneous + more variables than equations  many solutions (vsn),

chắc chắn có nghiệm không tầm thường
 Homogeneous + exist nontrivial solution  infinitely many solutions (vsn)
 Exercises
4. Consider a system of 203 linear equations in 133 variables. Choose
the correct statements.

 If the system is homogeneous there is always at least one solution

 There may be infinitely many solutions.
 There may be exactly three solutions.
 If the system is homogeneous there are always infinitely many
solutions.
 There may be exactly one solution.
 There is always at least one solution.
 There may be no solution

 Homogeneous  consistent (luôn có ít nhất một nghiệm)

 Exercises
5. Find the rank of the matrix.
1 2 1
A   2 1 0 
1 7 3
 1
 2  1 2 1  1 2 1  1 2 3 
 3  2 1 0   0 5 2   0 1 2 / 5
  
 4  1 7 3 0 5 2  0 0 0 
 3x3

rankA = the number of leading ones in the row

echelon form of A
 Exercises
6. Find all values of m such that the matrix has the rank 2.
1 2 3 
A   2 3 4 
 Answer:  3 4 m 
 Carry the augmented matrix to row-echelon form

 1 2 3  1 2 3  1 2 3 
 2 3 4   0 1 2   0 1 2 
     
 3 4 m   0 2 m  9  0 0 m  5
 rankA=2 iff m=5 (rankA=3 iff m ≠5)

rankA=the number of leading ones in the row

echelon form of A
 Exercises
7. Given a homogeneous system of 23 unkowns (n=23)
and 35 equations. Suppose the augmentad matrix of
the system has the rank 17 (r=17). How many
parameters in the solution of the system?

x1 x2 x3 x4
 17
Number of parameters = number of 1 * * * 0 
 23 nonleading variables  
 12 = n - r (số ẩn – hạng ma trận)  0 0 1 * 0 
 6 r = rankA = number of leading ones 0 0 0 0 0 
 None of the others
leading variables: x1, x3

nonleading variables: x2, x4

 Exercises
8. Solve the homogeneous system
x  2 y  z  w  0

3x  y  3z  0
y  z  w  0

 Carry the augmented matrix to (reduced) row-echelon form

1 2 1 1 0  1 2 1 1 0  1 2 1 1 0 
     
 3 1 3 0 0 
  0 7  6 3 0 
  0 1  1 1 0 
0 1 1 1 0  0 1 1 1 0  0 7 6 3 0 
1 2 1 1 0 
 
  0 1 1 1 0  w is nonleading variable, so w=parameter=t
 0 0 1 4 0 
 Solution: w=t, z=4t, y=3t, x=3t
 Exercises
 x  2y  z  1

9. Find all values of m such that the system 2 x  5y  3z  5
3x  7y  m2 z  6

has infinitely many solution.

 m=1
 m=2 1 2 1 1  1 2 1 1  1 2 1 1
 m=0      
2 5 3 5  0 1 1 3   0 1 1 3
 m=  1 3 7 m2 6  0 1 m2  3 3 0 0 m2  4 0 
 m=3
 Exercises
3x  2y  mz  0

10. Find all values of m such that the system  x  y  2z  0
2 x  y  3mz  0

has nontrivial solution.
3 2 m 0  1 1 2 0  1 1 2 0 
     
 1 1 2 0   3 2 m 0   3 2 m 0 
 m≠1  2 1 3m 0   2 1 3m 0  2 1 3m 0 
 m = -1 1 1 2 0  1 1 2 0 
 m=1    
 0 5 m  6 0   0 1 3m  4 0 
 m=  1 0 1 3m  4 0  0 5 m  6 0 
 m ≠-1 1 1 2 0
 
 0 1 3m  4 0 
0 0 14m  14 0 
THANK YOU