Finding Solutions of Linear Systems
Gaussian Ellimination
Inverse of a Square Matrix
Linear Equations
a11 x1 + a12 x2 = b1
a21 x1 + a22 x2 = b2
Ax = b
a11 a12
A = Det A = a11a22 − a12 a21
a21 a22
Det A ≠ 0 ⇒ unique solution
Det A = 0 ⇒ no solution or ∞ solutions
x1 − 2 x2 = −1 1 − 2 x1 − 1
=
− x1 + 3x2 = 3 − 1 3 x2 3
x1 − 2 x2 = −1 1 −2 x1 −1
=
− x1 + 2 x2 =3 −1 2 x2 3
x1 − 2 x2 =−1 1 −2 x1 −1
=
− x1 + 2 x2 =
1 −1 2 x2 1
Solution of linear systems
• Lets consider 3 by 3 linear system
a11 x1 + a12 x2 + a13 x3 =
b1
a21 x1 + a22 x2 + a23 x3 =
b2
a x + a32 x2 + a33 x3 =
b3
31 1
Solution of linear systems
• Example: 3 by 3 linear system
1 −2 1 2 x −2 y=
+z 2 1 −2 1 x 2
0 1 −1 0 ⇔ y − z =0 ⇔ 0 1 −1 y = 0
0 0 2 4 2z = 4 0 0 2 z 4
z = 2;
y= z= 2;
x = 2 + 2 y − z = 2 + 4 − 2 = 4;
4
x = 2
2
Solution of linear systems
• Example: Find the solution of the linear system
4 x − 2 y + 5 z = 16 4 − 2 5 16
1 1
x + y = 0 0 0
x + 3 y − 2 z = −6 1 3 − 2 − 6
1 1 0 0 1 1 0 0
1 3 −2 −6 R2 → R2 − R1
R → R − 4R 0 2 −2 −6
3 3 1
4 −2 5 16 0 −6 5 16
1 1 0 0
R2 → R2 / 2 0 1 −1 −3
R3 → R3 + 6 R2
0 −6 5 16
1 1 0 0 − z =−2 y =−3 + z =−3 + 2 =−1
0 1 −1 = − 3 z 2 = x+ y 0
0 0 −1 −2 y − z =−3 x =− y =1
Solving Linear Systems
• Augmented matrix
a11 a12 a1n b1
a a22 a2 n b2 Ax = b
21
am1 am 2 amn bm
• Elementary row operations
1. Add to one row a multiple of another row
2. Interchange two rows
3. Multiply all elements of a row by a nonzero constant
• A nonzero row/column is a row/column which contains at least one
nonzero entry
• A leading entry of a row refers to the leftmost nonzero entry
• A leading entry of a column refers to the uppermost nonzero entry
Row Reduction and Echelon Form
• A rectangular matrix is in echelon form (EF) if it has the following
properties
1. All nonzero rows are above any rows of all zeros
2. Each leading entry of a row is in a column to the right of the leading
entry of the row above it
3. All entries in a column below a leading entry are zeros
• A matrix in echelon form with the following additional conditions is
called reduced echelon form (REF) if
• − nonzero number
1. The leading entry in each non zero row is 1 * − any number
2. Each leading 1 is the only nonzero entry in its column
2 − 4 − 6 1 1 0 0 − 7 • * * *
0 1 0 1 0 4 0 • * *
8 − 3
0 0 0 4 0 0 1 3 0 0 0 0
Row Reduction and Echelon Form
• * * * * * * * 1 * * 0 0 * 0 *
0 0 0 • * * * * 0 0 0 1 0 *
0 *
0 0 0 0 • * * * 0 0 0 0 1 * 0 *
0 0 0 0 0 0 • 0 0 0 0 0 0 0 1 0
• Echelon form Reduced echelon form REF or (RREF)
• A pivot position in a matrix A is a location in A that corresponds to
the leading 1 in the reduced echelon form
• The dots identify the pivots positions
• Pivots are leading elements in a row for a matrix in echelon form
Row Reduction
An Example: Reduce given matrix into REF form
• Step 1: Start from the leftmost nonzero column,
The pivot position is at the top
0 3 − 6 6 4 − 5
pivot column 3 − 7 8 − 5 8 9
3 − 9 12 − 9 6 15
• Step 2: Select a nonzero entry in the pivot column as a pivot. If
necessary interchange rows to move this entry into the pivot position
pivot
3 − 9 12 − 9 6 15
3 − 7 8 − 5 8 9 R1 ↔ R3
0 3 − 6 6 4 − 5
Row Reduction
An Example:
• Step 3: Use row operations to create zeroes in all positions below
the pivot
3 − 9 12 − 9 6 15 3 − 9 12 − 9 6 15
3 − 7 8 − 5 8 9 R2 → R2 − R1 0 2 − 4 4 2 − 6
0 3 − 6 6 4 − 5
0 3 − 6 6 4 − 5
• Step 4: Cover the row containing the pivot position and cover all rows
if any above it. Apply the Steps 1-3 to the remaining matrix.
• Repeat the process until there are no more nonzero rows to modify
3 − 9 12 − 9 6 15
• Pivot 0 2 − 4 4 2 − 6
0 3 − 6 6 4 − 5
Pivot column: c2
Row Reduction
An Example:
• Step 4: Use row operations to create zeroes in all positions below
the pivot
3 − 9 12 − 9 6 15 3 − 9 12 − 9 6 15
0 2 − 4 4 2 − 6 R → R / 2 0 1 − 2 2 1 − 3
2 2
0 3 − 6 6 4 − 5 0 3 − 6 6 4 − 5
3 − 9 12 − 9 6 15
0 1 − 2 2 1
− 3 R3 → R3 − 3R2
0 3 − 6 6 4 − 5
3 − 9 12 − 9 6 15
0 1 − 2 2 1
− 3 This is in echelon form
0 0 0 0 1 4
Reduced Echelon Form
• Step 5: Start with the rightmost pivot create zeros above each
pivot
3 − 9 12 − 9 6 15 R2 → R2 − R3 3 − 9 12 − 9 0 − 9
0 1 − 2 2 1 − 3 0 1 − 2 2 0 − 7
R1 → R1 − 6R3
0 0 0 0 1 4 0 0 0 0 1 4
3 − 9 12 − 9 0 − 9 3 0 − 6 9 0 − 72
0 1 − 2 2 0 − 7 R1 → R1 + 9R2 0 1 − 2 2 0 − 7
0 0 0 0 1 4 0 0 0 0 1 4
1 0 − 2 3 0 − 24
0 1 − 2 2 0 − 7 R1 → R1 / 3 This is reduced echelon form
• Steps 1-4 are called the
0 0 0 0 1 4 forward phase;
• Step 5 is called backward
phase
Row Reduction
• An Example: Find EF and RREF form of the matrix
0 −3 −6 4 9 1 4 5 − 9 − 7
−1 − 2 −1 3 1 R1 ↔ R4 −1 − 2 −1 3 1
− 2 − 3 0 3 − 1 − 2 − 3 0 3 − 1
1 4 5 − 9 − 7 0 −3 −6 4 9
• All elements below the pivot must be zero R2 → R2 + R1
R3 → R3 + 2R1
R3 → R3 − 5 2 R2
R → R +3 2R R3 ↔ R4
4 4 2
1 4 5 − 9 − 7 1 4 5 − 9 − 7 1 4 5 − 9 − 7
0 2 4 − 6 − 6 0 2 4 − 6 − 6
0 2 4 − 6 − 6
0 5 10 − 15 − 15 0 0 0 0 0 0 0 0 − 5 0
0 − 3 − 6 4 9 0 0 0 − 5 0 0 0 0 0 0
Row Reduction
• An Example 1 4 5 − 9 − 7 • * * * *
0 2 4 − 6 − 6 0 • * * *
0 0 0 − 5 0 0 0 0 • *
0 0 0 0 0 0 0 0 0 0
• A rectangular matrix is in echelon form if it has the following
properties
1. All nonzero rows are above any rows of all zeros
2. Each leading entry of a row is in a column to the right of the leading
entry of the row above it
3. All entries in a column below a leading entry are zeros
• A matrix in echelon form with the following additional conditions is
called reduced echelon form if
1. The leading entry in each non zero row is 1
2. Each leading 1 is the only nonzero entry in its column
Row Reduction
• An Example: Find EF and RREF form of the matrix
1 4 5 − 9 − 7 1 4 5 −9 −7
0 2 4 − 6 − 6 R3 → R3 / (−5) 0 2 4 −6 −6
0 0 0 − 5 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0
• All elements above pivots must be zero
1 4 5 0 −7 1 0 −3 0 5
R2 → R2 + 6 R3 0 2 4 0 −6 0 2 4 0 −6
R1 → R1 − 2 R2
R1 → R1 + 9 R3 0 0 0 1 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0
1 0 −3 0 5
0 1 2 0 −3
R2 → R2 / 2 0 0 0 1 0
0 0 0 0 0
Solution of linear systems
• Example: An augmented matrix reduced into echelon form (EF) .
Find all solutions of corresponding linear system
1 1 − 5 1
0 1 1 4
0 0 0 0
• Associate linear system has the form
x1 + x2 − 5 x3 = 1
x + x = 4
2 3
0 = 0
• Variables x1 and x2 : basic or leading variables; x3 is a free variable
• To write the solution express basic variables x1 and x2 in terms of
free variable x3.
x2 = 4 − x3 , x1 = 1 − x2 + 5 x3
x1 = 1 − x2 + 5 x3 = 1 − (4 − x3 ) + 5 x3 = −3 + 6 x3
Solution of linear systems
• Example: An augmented matrix reduced into reduced echelon form
(REF) . Find all solutions of corresponding linear system
1 0 − 5 1
0 1 1 4
0 0 0 0
• Associate linear system has the form
x1 − 5 x3 = 1
x + x = 4
2 3
0 = 0
• Variables x1 and x2 corresponding the pivot columns are called the
basic or leading variables; x3 is called a free variable
• To write the solution express basic variables x1 and x2 in terms of
free variable x3. x1 = 1 + 5 x3 , x2 = 4 − x3
x3 is free
Solution of linear systems
• Example: For which value of h the system is inconsistent ?
x + 5 y − 3 z = −4 1 5 − 3 − 4
−1 − 4 1 3
− x − 4 y + z = 3
− 2 − 7 y =h − 2 − 7 0 h
1 5 −3 −4
R2 → R2 + R1 0
1 − 2 − 1
R3 → R3 + 2 R1
0 3 − 6 h − 8
1 5 −3 −4
0
1 − 2 − 1 h ≠ 5
R3 → R3 − 3R2
0 0 0 h − 5
1 5 − 3 −4
0 1 − 2 0 = h−5 ≠ 0 Inconsistency, no solution
− 1
0 0 0 h − 5 ≠ 0
Solution of linear systems
• Example: Find all solutions of linear system for h=5
1 5 −3 −4
0 1 −2 −1 h = 5
R3 → R3 − 3R2
0 0 0 h − 5
1 5 −3 −4 z − is free var x + 5 y − 3z =−4
0 1 −2 −1 y − 2 z =−1 x =−4 − 5 y + 3 z
0 0 0 0 y =−1 + 2 z x =−4 − 5(−1 + 2 z ) + 3 z
x, y − are basic var x =−4 + 5 − 10 z + 3 z =1 − 7 z
x 1− 7z 1 − 7z 1 − 7
y = − 1 + 2 z = − 1 + 2 z = − 1 + z 2
z z 0 z 0 1
Solution of linear systems
• Example:
x 1− 7z 1 − 7z 1 − 7
y = − 1 + 2 z = − 1 + 2 z = − 1 + z 2
z z 0 z 0 1
z =t∈R
x 1 − 7 x 1 − 7
y = − 1 + t 2 , r = y a = − 1, v = 2
z 0 1 z 0 1
r = a + vt
Equation of a line though the point a along the direction v
For 3 x 3 systems
x1 −2 x2 +2 x3 =1
x1 −2 x2 + x3 =1
3 x1 −2 x2 + x3 =1
Put the equations in matrix form:
1 −2 2 x1 1 1 − 2 2
1 −2 1 x = 1 1 − 2 1
2
3 −2 1 x3 1 3 − 2 1
If we can find an inverse of this matrix, we can solve this system:
Finding the inverse of a 3 x 3 matrix
The inverse can be found by using a series of row operations:
1. Multiplying a row by a scalar
2. Adding or subtracting two rows.
3. Swapping any two rows
x1 −2 x2 +2 x3 =1
x1 −2 x2 + x3 =1
3 x1 −2 x2 + x3 =1
To find the inverse:
1 − 2 2
1 − 2 1
1. First write the matrix of the linear system:
3 − 2 1
1 − 2 2 1 0 0
2. “Augment” the Identity matrix: 1 − 2 1 0 1 0
3 − 2 1 0 0 1
3. Use row operations to transform the left half into the identity matrix I.
The right half will then be the inverse.
Example: Solve the system of equations x1 − 2 x2 + 2 x3 = 1
x1 − 2 x2 + x3 = 1
Augmented matrix: 3 x1 − 2 x2 + x3 = 1
1 −2 2 1 0 0 1 −2 2 1 0 0
1 −2 1 R2 → R2 − R1 R2 ↔ R3
0 1 0 ⇔ 0 0 −1 −1 1 0
R3 → R3 − 3R1
3 −2 1 0 0 1 0 4 −5 −3 0 1
1 −2 2 1 0 0 1 −2 2 1 0 0
0 4 −5 R2 → R2 + 5 R3
−3 0 1 R3 → (−1) × R3 0 4 −5
−3 0 1
R1 → R1 − 2 R3
0 0 −1 −1 1 0 0 0 1 1 −1 0
1 −2 0 −1 2 0 2 0 0 0 −1 1 R1 → R1 / 2
0 4 0 2 −5 1 R1 → 2 R1 − R2 0 4 0 2 −5 1 R2 → R2 / 4
0 0 1 1 −1 0 0 0 1 1 −1 0
1 0 0 0 −1/ 2 1/ 2 0 −1/ 2 1/ 2
0 1 0 1/ 2 −5 / 4 1/ 4 ⇒ A −=
1 1/ 2 −5 / 4 1/ 4
0 0 1 1 −1 0 1 −1 0
So the solution to
x1 − 2 x2 + 2 x3 = 1 1 −2 2
A 1 −2 1
= A −1A = I
x1 − 2 x2 + x3 = 1
3 −2 1
3 x1 − 2 x2 + x3 = 1
0 −1/ 2 1/ 2
A −1 1/ 2 −5 / 4 1/ 4
=
1 −1 0
is:
0 −1/ 2 1/ 2 1 0
x= 1/ 2 −5 / 4 1/ 4 1 =
A −1b = −1/ 2
1 −1 0 1 0
Example: Find the inverse of a matrix A by a series of row-operations:
1 1 0 1 0 0 1 1 0
2 2 1 0 1 0
A = 2 2 1
1 2 3 0 0 1 1 2 3
1 1 0 1 0 0
0 0 1 − 2 1 0
R2 → R2 – 2 R1
R3 → R3 – R1 0 1 3 − 1 0 1
1 1 0 1 0 0
R2 → R3 0 1 3 − 1 0 1
R3 → R2 0 0 1 − 2 1 0
1 1 0 1 0 0 −4 3 −1
0 1 0 5 − 3 1
R2 → R2 – 3 R3 A −1 5 −3 1
=
0 0 1 − 2 1 0 −2 1 0
R1 → R1 – R2 1 0 0 − 4 3 − 1
0 1 0 5 − 3 1
A −1A = I
0 0 1 − 2 1 0