Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
MAST10007 Linear Algebra
These notes have been made in accordance with the provisions of Part VB of the copyright act for teaching purposes of the
University. These notes are for the use of students of the University of Melbourne enrolled in MAST10007 Linear Algebra.
1
Topic 1: Linear equations [AR 1.1 and 1.2]
1.1. Systems of linear equations. Row operations.
1.2. Reduction of systems to row-echelon form.
1.3. Reduction of systems to reduced row-echelon form.
1.4. Consistent and inconsistent systems.
2
1.1 Systems of linear equations. Row operations
Linear equations
Definition (Linear equation and linear system)
A linear equation in n variables, x1, x2, . . . , xn, is an equation of the form
a1x1 + a2x2 + · · ·+ anxn = b,
where a1, . . . , an and b are constants.
A finite collection of linear equations in the variables x1, x2, . . . , xn is
called a system of linear equations or a linear system.
Example
x1 + 5x2 + 6x3 = 100
x2 − x3 = −1
−x1 + x3 = 11
3
Definition (Homogeneous linear system)
A system of linear equations is called homogeneous if all the constants
on the right hand side are zero.
Example
x1 + 5x2 + 6x3 = 0
x2 − x3 = 0
−x1 + x3 = 0
Definition (Solution of a system of linear equations)
A solution to a system of linear equations in the variables x1, . . . , xn is a
set of values of these variables which satisfy every equation in the
system.
4
Example 1. Data fitting using a polynomial
Find the coefficients c , α, β, γ such that the cubic polynomial
y = c + αx + βx2 + γx3 passes through the points specified below.
x y
−0.1 0.90483
0 1
0.1 1.10517
0.2 1.2214
Solution:
Substituting the points (x , y) into the cubic polynomial gives:
0.90483 = c − 0.1α + 0.01β − 0.001γ
1 = c
1.10517 = c + 0.1α + 0.01β + 0.001γ
1.2214 = c + 0.2α + 0.04β + 0.008γ
5
So c = 1.
We can rewrite the system as 3 equations in 3 unknowns.
−0.1α+ 0.01β − 0.001γ = −0.09517
0.1α + 0.01β + 0.001γ = 0.10517
0.2α + 0.04β + 0.008γ = 0.2214
Note:
To solve these equations by hand is tedious, so we can use a computer
package such as MATLAB.
6
Example 2. (Revision)
Solve the following linear system.
2x − y = 3
x + y = 0
Solution:
Graphically
Solution is the intersection of the lines: (x , y) = (1,−1).
Note:
◮ Need accurate sketch.
◮ Not practical for three or more variables.
7
Elimination
2x − y = 3 (1)
x + y = 0 ⇒ y = −x (2)
Substituting (2) in (1) gives
2x + x = 3 ⇒ 3x = 3 ⇒ x = 1
Substituting into (2) gives y = −1.
Note:
Elimination of variables will always give a solution, but we need to do
this systematically and not in an adhoc manner, for three or more
variables.
8
Definition (Coefficient matrix and augmented matrix)
The coefficient matrix for a linear system is the matrix formed from the
coefficients in the equations.
The augmented matrix for a linear system is the matrix formed from the
coefficients in the equations and the constant terms. These are
separated by a vertical line.
Example 3.
Write down an augmented matrix for the following linear system:
2x − y = 3
x + y = 0
Solution: [
2 −1 3
1 1 0
]
9
Row Operations
To find the solutions of a linear system, we perform row operations to
simplify the augmented matrix. An essential condition is that whichever
row operations we perform, we can recover the solutions to the original
system from the new matrix.
Definition (Elementary row operations)
The elementary row operations are:
1. Interchanging two rows.
2. Multiplying a row by a non-zero constant.
3. Adding a multiple of one row to another row.
Note:
The matrices produced after each row operation are not equal but are
equivalent, meaning that the solution is the same for the system
represented by each augmented matrix. We use the symbol ∼ to denote
equivalence of matrices.
10
Example 4.
Solve the following system using elementary row operations:
2x − y = 3
x + y = 0
Solution:[
2 −1 3
1 1 0
]
R2 ↔ R1 ∼
[
1 1 0
2 −1 3
]
R2 → R2 − 2R1
∼
[
1 1 0
0 −3 3
]
R2 → −13R2
∼
[
1 1 0
0 1 −1
]
R1 → R1 − R2
∼
[
1 0 1
0 1 −1
]
So x = 1, y = −1.
11
1.2 Reduction of systems to row-echelon form
Definition (Leading entry)
The leftmost non-zero entry in each row of the matrix is called the
leading entry.
Definition (Row-echelon form)
A matrix is in row-echelon form if:
1. For any row with a leading entry, all elements below that entry and
in the same column as it, are zero.
2. For any non-zero two rows, the leading entry of the lower row is
further to the right than the leading entry in the higher row.
3. Any row that consists solely of zeros is lower than any row with
non-zero entries.
12
Examples[
1 −2 3 4 5 ] row-echelon form
1 0 0 30 4 1 2
0 0 0 3
row-echelon form
0 0 0 2 4
0 0 3 1 6
0 0 0 0 0
2 −3 6 −4 9
not row-echelon form
13
Gaussian elimination
Gaussian elimination is a systematic way to reduce a matrix to
row-echelon form using row operations.
Note:
The row-echelon form obtained is not unique.
Gaussian elimination
1. Interchange rows, if necessary, to bring a non-zero number to the
top of the first column with a non-zero entry.
2. Add suitable multiples of the top row to lower rows so that all
entries below the leading entry are zero. (Multiplying a row by a
constant is also allowed and is often useful.)
3. Start again at Step 1 applied to the matrix without the first row.
To solve a linear system we read off the equations from the row-echelon
matrix and then solve the equations to find the unknowns, starting with
the last equation. This final step is called back substitution.
14
Example 5.
Solve the following system of linear equations using Gaussian
elimination:
x − 3y + 2z = 11
2x − 3y − 2z = 13
4x − 2y + 5z = 31
Solution:
Step 1. Write the system in augmented matrix form.
1 −3 2 112 −3 −2 13
4 −2 5 31
15
Step 2. Use elementary row operations to reduce the augmented matrix
to row-echelon form.
1 −3 2 112 −3 −2 13
4 −2 5 31
R2 → R2 − 2R1
R3 → R3 − 4R1
∼
1 −3 2 110 3 −6 −9
0 10 −3 −13
R2 → 13R2
∼
1 −3 2 110 1 −2 −3
0 10 −3 −13
R3 → R3 − 10R2
∼
1 −3 2 110 1 −2 −3
0 0 17 17
16
Step 3. Read off the equations from the augmented matrix and use back
substitution to solve for the unknowns, starting with the last equation.
This gives us three equations:
17z = 17 ⇒ z = 1
y − 2z = −3 ⇒ y = 2− 3 = −1
x − 3y + 2z = 11 ⇒ x = −3− 2 + 11 = 6
17
1.3 Reduction of systems to reduced row-echelon form
Definition (Reduced row-echelon form)
A matrix is in reduced row-echelon form if the following three conditions
are satisfied:
1. It is in row-echelon form.
2. Each leading entry is equal to 1 (called a leading 1).
3. In each column containing a leading 1, all other entries are zero.
18
Examples[
1 −2 3 −4 5 ] reduced row-echelon form
[
1 2 0
0 0 1
]
reduced row-echelon form
1 0 0 30 1 1 2
0 0 0 3
is not in reduced row-echelon form
1 0 0 2 4
0 1 0 1 6
0 0 0 0 0
0 0 1 −4 9
is not in reduced row-echelon form
19
Gauss-Jordan elimination
Gauss-Jordan elimination is a systematic way to reduce a matrix to
reduced row-echelon form using row operations.
Note:
The reduced row-echelon form obtained is unique.
Gauss-Jordan elimination
1. Use Gaussian elimination to reduce matrix to row-echelon form.
2. Multiply each non-zero row by an appropriate number to create a
leading 1 (type 2 row operations).
3. Use row operations (of type 3) to create zeros above the leading
entries.
20
Example 6.
Solve the following system of linear equations using Gauss-Jordan
elimination:
x − 3y + 2z = 11
2x − 3y − 2z = 13
4x − 2y + 5z = 31
Solution:
Step 1. Use Gaussian elimination to reduce the augmented matrix to
row-echelon form.
From example 5, we have:
1 −3 2 112 −3 −2 13
4 −2 5 31
∼
1 −3 2 110 1 −2 −3
0 0 17 17
21
Step 2. Divide rows by their leading entry.
1 −3 2 110 1 −2 −3
0 0 17 17
R3 → 117R3
∼
1 −3 2 110 1 −2 −3
0 0 1 1
Step 3. Add multiples of the last row to the rows above to make the
entries above its leading 1 equal to zero.
1 −3 2 110 1 −2 −3
0 0 1 1
R1 → R1 − 2R3R2 → R2 + 2R3 ∼
1 −3 0 90 1 0 −1
0 0 1 1
22
Step 4. Add multiples of the penultimate (2nd last) row to the rows
above to make the entries above its leading 1 equal to zero.
1 −3 0 90 1 0 −1
0 0 1 1
R1 → R1 + 3R2 ∼
1 0 0 60 1 0 −1
0 0 1 1
Step 5. Read off the answers.
The solution is x = 6, y = −1, z = 1.
23
1.4 Consistent and inconsistent systems
Theorem
A system of linear equations has zero solutions, one solution, or
infinitely many solutions. There are no other possibilities.
We say that the system is:
◮ inconsistent if it has no solutions.
◮ consistent if it has at least one solution.
Note:
Every homogeneous linear system is consistent, since it always has at
least one solution: x1 = 0, . . . , xn = 0.
24
Inconsistent systems
We can determine whether a system is consistent or inconsistent by
reducing its augmented matrix to row-echelon form.
Theorem
The system is inconsistent if and only if there is at least one row in the
row-echelon matrix having all entries equal to zero except for a non-zero
final entry.
Example 7.
Solve the system with row-echelon form:
1 0 1 −20 2 2 4
0 0 0 −3
Solution:
The third equation says 0x1 + 0x2 + 0x3 = −3.
So the system is inconsistent with no solution.
25
Geometrically, an inconsistent system in 3 variables has no common
point of intersection for the planes determined by the system.
26
Consistent systems
Unique solution
For a consistent system with n variables, a unique solution exists when
the row reduced coefficient matrix and augmented matrix has n
non-zero rows. We can read off the solution from the reduced
row-echelon form of the matrix.
Example 8.
Solve the system with reduced row-echelon form:
1 0 0 20 1 0 −4
0 0 1 15
Solution:
Reading off the answers, we get
x1 = 2, x2 = −4, x3 = 15.
27
Infinitely many solutions
Example 9. Calculating flows in networks
At each node • we require
sum of flows in = sum of flows out.
Determine a, b, c and d in the following network.