Linear Algebra

Lecture 2:
Solving system of linear equation
Gaussian Elimination.

Instructor
Dr. Safaa Amin
 Linear System of Equations
• A system of m-linear equations in n
variables x1, x2, ..., xn has the general form

(1)
 Matrix Representation of a
Linear System of Equations
• With
AX = B

A is the coefficient matrix B is the column of RHS

X is the column of variables
 Example
• The matrix form

Can be represented as

 x • Represents the system

2 3 − 1   12
4 − 5 6   y  = 35
  z   
 
Use Gaussian Elimination
To solve a system of linear equations using Gaussian
elimination:

Step 1: Write the augmented matrix for the system.

Step 2: Use elementary row operations to write the

augmented matrix in row-echelon form.
(Begin by getting the entry in row 1 column
1 to be 1, with zeros under it.)

Step 3: Use back substitution to solve the resulting

system of equations.
1. Write an Augmented Matrix
2. Use Elementary Row Operations
3. Use Gaussian Elimination and
Gauss-Jordan Elimination
 Augmented Matrix
• The augmented matrix for AX = B is the
partitioned matrix [A|B]
• E.g.

• has its augmented matrix as

1. Write an Augmented Matrix
2. Use Elementary Row Operations
3. Use Gaussian Elimination and Gauss-
Jordan Elimination
 Elementary Row Operations
elementary row operations are :

• 1- Interchange any two rows in a matrix

• 2- Multiply any row of a matrix by a

nonzero scalar

• 3- Add to one row of a matrix a scalar

times another row of the same matrix
• Elementary row operation:

(1) Interchange two rows. rij : Ri  R j

r
(2) Multiply a row by a nonzero constant.i
(k )
: (k ) Ri → Ri
(3) Add a multiple of a row to another row.
rij( k ) : (k ) Ri + R j → R j
◼ Row equivalent:
Two matrices are said to be row equivalent if
one can be obtained from the other by a finite
sequence of elementary row operation.
• Ex 2: (Elementary row operation)

 0 1 3 4 − 1 2 0 3
− 1 2 0 3  0 1 3 4
 2 − 3 4 1  2 − 3 4 1
2 − 4 6 − 2
 1 − 2 3 − 1
1 3 − 3 0  1 3 − 3 0
 5 − 2 1 2 5 − 2 1 2

1 2 − 4 3  1 2 − 4 3
 0 3 − 2 − 1 0 3 − 2 − 1
0 − 3 13 − 8
2 1 5 − 2
Use Elementary Row Operations

Elementary Row Operations

1. Interchange two rows
3 2 −5 R1  R2
1 −2 10 
  interchange

rows 1 and row 2

2. Multiply a row by a nonzero constant
3 2 −5 3R1 → R1
1 −2 10 
  multiply row 1 by
3 and then
replace row 1 by
the result
Use Elementary Row Operations
Elementary Row Operations
3. Add a multiple of one row to another row

3 2 −5 2R1 + R2 → R2
1 −2 10 
  multiply row 1 by 2,
add it to row 2, and
then replace row 2
by the result
1. Write an Augmented Matrix
2. Use Elementary Row Operations
3. Row Echelon Form/Reduced Row
Echelon Form
 • Row-echelon form: (1, 2, 3)
◼ Reduced row-echelon form: (1, 2, 3, 4)

(1) All row consisting entirely of zeros occur at the bottom

of the matrix.
(2) For each row that does not consist entirely of zeros,
the first nonzero entry is 1 (called a leading 1) and all the
entries below it is zero.
(3) For two successive (nonzero) rows, the leading 1 in the
higher row is farther to the left than the leading 1 in the lower
row.
(4) Every column that has a leading 1 has zeros in every
position above and below its leading 1.
Row-echelon form:
1. Any rows consisting entirely of zeros are at the
bottom of the matrix.
2. For all other rows, the first nonzero entry is 1. This is
called the leading 1.
3. The leading 1 in each nonzero row is to the right of
the leading 1 in the row immediately above.
Examples:

1 −2 5 53  1 2 12 70 
0 1 4 −8 0 1 −3 −6 
   
0 0 1 12  0 0 0 0 
Reduced row-echelon form:
The matrix is in row-echelon form with the
added condition that each row with a leading
entry of 1 has zeros above the leading 1.
Examples:

1 0 0 12.6  1 0 0 −5
 0 1 0 −4  0 1 14 28 
   
 0 0 1 −3.8 0 0 0 0 
• Ex 4: (Row-echelon form or reduced row-echelon form)

 1 2 − 1 4 (row - echelon 0 1 0 5 (reduced row -

0 1 0 3 0 0 1 3
0 0 1 − 2 form) 0 0 0 0 echelon form)

 1 − 5 2 − 1 3 1 0 0 − 1
0 0 1 3 − 2 (row - echelon 0 1 0 2 (reduced row -
0 0 0 1 4 form) 0 0 1 3 echelon form)
0 0 0 0 1 0 0 0 0

 1 2 − 3 4 Not Row  1 2 − 1 2 Not Row

0 2 1 − 1 Echelon  0 0 0 0 Echelon
0 0 1 − 3 0 1 2 − 4
Form Form

18/39
 ◼ Gauss-Jordan elimination:
The procedure for reducing a matrix to a
reduced row-echelon form.
◼ Notes:
(1) Every matrix has an unique reduced row echelon form.

(2) A row-echelon form of a given matrix is not unique.

(Different sequences of row operations can produce
different row-echelon forms.)
(3) every reduced row-echelon form is a row echelon form but
the converse is not true.
• Ex: (Procedure of Gaussian elimination and Gauss-
Jordan elimination)

Produce leading 1
0 0 − 2 0 8 12 2 8 − 6 4 12 28
2 8 − 6 4 12 28 0 0 − 2 0
   8 12
2 4 − 5 6 − 5 4 2 4 − 5 6 − 5 4
The first nonzero column

leading 1 Produce leading 1

1 4 − 3 2 6 14 1 4 − 3 2 6 14
0 0 − 2 0 0 0 − 2 0 12
8 12 
8

 
2 4 − 5 6 − 5 4 0 0 5 0 − 17 − 24
Zeros elements below leading 1 The first nonzero Submatrix
column

20/39
 leading 1
( − 12 ) 1 4 − 3 2 6 14 1 4 − 3 2 6 14
r2 0 0 1 0 − 4 − 6 0 0 1 0 − 4 − 6
   
0 0 5 0 − 17 − 24 0 0 0 0 3 6
Zeros elements below leading 1 Submatrix
Produce leading 1

1 4 − 3 2 6 14
0 0 1 0 − 4 − 6
 
0 0 0 0 1 2
To complete Using Gauss-
Jordan

22
 Example1: Unique Solution
• Use Gaussian elimination to solve the
system
 Step 1
The augmented matrix
• The augmented matrix of the system is:

Step 2
Elementary row operations
We use elementary row operations to transform
the augmented matrix into row-reduced form
as follows,
This is a Row Echelon Form

Back
Substitution
 Example2: Unique Solution
• Use Gauss elimination method to solve
the linear system of equations
• Solving the last system by
back substitution, we get the
solution
• x = 1 and y = 1
 Example3: Infinite Solutions
• Use Gauss elimination method to solve
the linear system of equations
30
Writing the Resulting System
 Important Note
• Since the final system has the number of
variables (4) greater than the number of
equations (3),

• then one of the variable will be arbitrary,

• and the other variables will be found in

terms of it.
32
Solving The Resulting System
• The solution will be found in terms of x4 as
follows,

• Since x4 is arbitrary, then the system has infinite number

of solutions, depending on the value of x4
• for example if you choose

• Then,
Example 4 : No Solution
• Ex 5: Using elementary row
operations to solve a system
Associated
Linear System Augemented Matrix Elementary
Row Operation
x − 2 y + 3z = 9  1 −2 3 9
− 1 (1)
− x + 3y = −4  3 0 − r
412 : (1) R1 + R2 → R2

2 x − 5 y + 5 z = 17  2 − 5 5 17 
1 −2 3 r913( −2) : (−2) R1 + R3 → R3
0 1 3 5
 
2 −5 5 17 
1 −2 3 9
0 1 3 5r23(1) : (1) R2 + R3 → R3

0 −1 −1 − 1
1 − 2 3 91
0 ( ) 1  1 − 2 3 9

1 3 r3  : ( ) R3 → R3
5 2 0 1 3 5
2  
0 0 2 4 0 0 1 2
System of Linear Equation cases
Special Cases: After application of the Gauss-Jordan method, linear systems
having no solution or infinite number of solutions can be recognized.

No solution example: Infinite solutions

example:
1 2 3   1 0 −1 −2 
  0 1 0 3 
 0 0 −2   
0 0 0 0 
Unique solution
example:
 System of Linear Equation

consistent Has unique solution Has infinite

Inconsistent solutions
Which is the trivial
Has no Solution (Non-trivial
solution Solution)

Unique Infinite
Solution Solutions
Homogeneous systems of linear equations:

A system of linear equations is said to be homogeneous

if all the constant terms are zero.

a11 x1 + a12 x2 + a13 x3 +  + a1n xn = 0

a21 x1 + a22 x2 + a23 x3 +  + a2 n xn = 0
a31 x1 + a32 x2 + a33 x3 +  + a3n xn = 0

am1 x1 + am 2 x2 + am 3 x3 +  + amn xn = 0
Example: Solve the following homogeneous system

x1 − x2 + 3 x3 = 0
2 x1 + x2 + 3 x3 = 0
Sol: augmented matrix

 1 − 1 3 0 1 0 2 0
2 1 3 0 0 1 − 1 0
(reduced row -
leading variable ：x1 , x2 echelon form)

free variable ： x3
Let x3 = t
x1 = −2t , x2 = t , x3 = t , t  R
When t = 0, x1 = x2 = x3 = 0 (trivial solution)
• Trivial solution: x1 = x2 = x3 =  = xn = 0

◼ Nontrivial solution:
other solutions
◼ Notes:

(1) Every homogeneous system of linear equations is consistent.

(2) If the homogenous system has fewer equations than variables,
then it must have an infinite number of solutions.
(3) For a homogeneous system, exactly one of the following is true.
(a) The system has only the trivial solution.

(b) The system has infinitely many nontrivial

solutions in
42/39
addition to the trivial solution.
Examination Style Questions

43
GUC - Spring 2012 44