Linear Algebra Module I: Linear Systems
Linear Algebra Module I: Linear Systems
Summer Term 2021
Linear Algebra Module I: Linear Systems Summer Term 2021 1 / 75
Table of Contents
1 Systems of Linear Equations
2 Solving Systems of Equations – Row Reduction
Overview
Plan for Row Reduction
Notation for Row Reduction
Algorithm for Row Reduction
3 Matrices
Definition of a Matrix
Matrix Operations
Matrix Equations
4 The Superposition Principle
5 Elementary matrices
6 The Dimensions of a System of Equations, and Generalized Equivalence
Linear Algebra Module I: Linear Systems Summer Term 2021 2 / 75
Overview
Linear algebra begins with linear systems.
Linear Algebra Module I: Linear Systems Summer Term 2021 3 / 75
Table of Contents
1 Systems of Linear Equations
2 Solving Systems of Equations – Row Reduction
Overview
Plan for Row Reduction
Notation for Row Reduction
Algorithm for Row Reduction
3 Matrices
Definition of a Matrix
Matrix Operations
Matrix Equations
4 The Superposition Principle
5 Elementary matrices
6 The Dimensions of a System of Equations, and Generalized Equivalence
Linear Algebra Module I: Linear Systems Summer Term 2021 4 / 75
Systems of Linear Equations
Definition
A linear equation in one variable is of the form ax = b where x is a
variable and a, b are numbers (or scalars as they are referred to in linear
algebra). It is homogeneous if b = 0.
Similarly, a linear equation in n variables is one of the form
a1x1 + a2x2 + . . . anxn = b
where the expression on the left is a linear homogeneous function in n
variables, and the term on the right is a constant.
A solution to a linear equation is an assignment of values to each of the
variables appearing which makes the equation hold true.
Linear Algebra Module I: Linear Systems Summer Term 2021 5 / 75
Systems of Linear Equations
Definition
A linear equation in one variable is of the form ax = b where x is a
variable and a, b are numbers (or scalars as they are referred to in linear
algebra). It is homogeneous if b = 0.
Similarly, a linear equation in n variables is one of the form
a1x1 + a2x2 + . . . anxn = b
where the expression on the left is a linear homogeneous function in n
variables, and the term on the right is a constant.
A solution to a linear equation is an assignment of values to each of the
variables appearing which makes the equation hold true.
Linear Algebra Module I: Linear Systems Summer Term 2021 5 / 75
Systems of Linear Equations
Definition
A linear equation in one variable is of the form ax = b where x is a
variable and a, b are numbers (or scalars as they are referred to in linear
algebra). It is homogeneous if b = 0.
Similarly, a linear equation in n variables is one of the form
a1x1 + a2x2 + . . . anxn = b
where the expression on the left is a linear homogeneous function in n
variables, and the term on the right is a constant.
A solution to a linear equation is an assignment of values to each of the
variables appearing which makes the equation hold true.
Linear Algebra Module I: Linear Systems Summer Term 2021 5 / 75
Definition of a System of Linear Equations
Definition
A system of equations is a collection of linear equations in the same set
of variables, or unknowns
a11x1 +a12x2+ . . . +a1nxn = b1 (1)
a21x1+ a22x2+ . . . +a2nxn = b2
…
… . . .
…
…
am1x1+am2x2+ . . .+amnxn= bm
and a solution to that system is an assignment of values to the variables
which make each equation hold true. The solution set of a system of
equations is the set of all the solutions of that system (which will be
empty if the system has no solutions). Given m equations in the same set
of n unknowns, the pair of integers (m, n) are the dimensions of the
system, and the system is referred to as an m × n system of equations.
Linear Algebra Module I: Linear Systems Summer Term 2021 6 / 75
Definition of a System of Linear Equations
Definition
A system of equations is a collection of linear equations in the same set
of variables, or unknowns
a11x1 +a12x2+ . . . +a1nxn = b1 (1)
a21x1+ a22x2+ . . . +a2nxn = b2
…
… . . .
…
…
am1x1+am2x2+ . . .+amnxn= bm
and a solution to that system is an assignment of values to the variables
which make each equation hold true. The solution set of a system of
equations is the set of all the solutions of that system (which will be
empty if the system has no solutions). Given m equations in the same set
of n unknowns, the pair of integers (m, n) are the dimensions of the
system, and the system is referred to as an m × n system of equations.
Linear Algebra Module I: Linear Systems Summer Term 2021 6 / 75
Definition of a System of Linear Equations
Definition
A system of equations is a collection of linear equations in the same set
of variables, or unknowns
a11x1 +a12x2+ . . . +a1nxn = b1 (1)
a21x1+ a22x2+ . . . +a2nxn = b2
…
… . . .
…
…
am1x1+am2x2+ . . .+amnxn= bm
and a solution to that system is an assignment of values to the variables
which make each equation hold true.
The solution set of a system of
equations is the set of all the solutions of that system (which will be
empty if the system has no solutions). Given m equations in the same set
of n unknowns, the pair of integers (m, n) are the dimensions of the
system, and the system is referred to as an m × n system of equations.
Linear Algebra Module I: Linear Systems Summer Term 2021 6 / 75
Definition of a System of Linear Equations
Definition
A system of equations is a collection of linear equations in the same set
of variables, or unknowns
a11x1 +a12x2+ . . . +a1nxn = b1 (1)
a21x1+ a22x2+ . . . +a2nxn = b2
…
… . . .
…
…
am1x1+am2x2+ . . .+amnxn= bm
and a solution to that system is an assignment of values to the variables
which make each equation hold true. The solution set of a system of
equations is the set of all the solutions of that system (which will be
empty if the system has no solutions).
Given m equations in the same set
of n unknowns, the pair of integers (m, n) are the dimensions of the
system, and the system is referred to as an m × n system of equations.
Linear Algebra Module I: Linear Systems Summer Term 2021 6 / 75
Definition of a System of Linear Equations
Definition
A system of equations is a collection of linear equations in the same set
of variables, or unknowns
a11x1 +a12x2+ . . . +a1nxn = b1 (1)
a21x1+ a22x2+ . . . +a2nxn = b2
…
… . . .
…
…
am1x1+am2x2+ . . .+amnxn= bm
and a solution to that system is an assignment of values to the variables
which make each equation hold true. The solution set of a system of
equations is the set of all the solutions of that system (which will be
empty if the system has no solutions). Given m equations in the same set
of n unknowns, the pair of integers (m, n) are the dimensions of the
system, and the system is referred to as an m × n system of equations.
Linear Algebra Module I: Linear Systems Summer Term 2021 6 / 75
Systems of Linear Equations
Examples
Even a single equation, need not have a solution. Consider
0x1 + 0x2 + 0x3 = 4
Any set of values substituted into the left-hand side of this equation will
give zero, which is not equal to 4.
But even non-zero systems might not have a solution. Consider
x1−2×2= 7
2×1−4×2=16
The left-hand side of the second equation is twice that of the first. If we
take any solution of the first equation and plug in those values on the
left-hand side of the second equation, we will always get 2 ∗ 7 = 14 6= 16.
So these two equations will never be simultaneously satisfied, and the
system doesn’t have a solution.
Linear Algebra Module I: Linear Systems Summer Term 2021 7 / 75
Systems of Linear Equations
Examples
Even a single equation, need not have a solution. Consider
0x1 + 0x2 + 0x3 = 4
Any set of values substituted into the left-hand side of this equation will
give zero, which is not equal to 4.
But even non-zero systems might not have a solution. Consider
x1−2×2= 7
2×1−4×2=16
The left-hand side of the second equation is twice that of the first. If we
take any solution of the first equation and plug in those values on the
left-hand side of the second equation, we will always get 2 ∗ 7 = 14 6= 16.
So these two equations will never be simultaneously satisfied, and the
system doesn’t have a solution.
Linear Algebra Module I: Linear Systems Summer Term 2021 7 / 75
Systems of Linear Equations
Examples
Even a single equation, need not have a solution. Consider
0x1 + 0x2 + 0x3 = 4
Any set of values substituted into the left-hand side of this equation will
give zero, which is not equal to 4.
But even non-zero systems might not have a solution. Consider
x1−2×2= 7
2×1−4×2=16
The left-hand side of the second equation is twice that of the first. If we
take any solution of the first equation and plug in those values on the
left-hand side of the second equation, we will always get 2 ∗ 7 = 14 6= 16.
So these two equations will never be simultaneously satisfied, and the
system doesn’t have a solution.
Linear Algebra Module I: Linear Systems Summer Term 2021 7 / 75
Systems of Linear Equations
Examples
Even a single equation, need not have a solution. Consider
0x1 + 0x2 + 0x3 = 4
Any set of values substituted into the left-hand side of this equation will
give zero, which is not equal to 4.
But even non-zero systems might not have a solution. Consider
x1−2×2= 7
2×1−4×2=16
The left-hand side of the second equation is twice that of the first. If we
take any solution of the first equation and plug in those values on the
left-hand side of the second equation, we will always get 2 ∗ 7 = 14 6= 16.
So these two equations will never be simultaneously satisfied, and the
system doesn’t have a solution.
Linear Algebra Module I: Linear Systems Summer Term 2021 7 / 75
Systems of Linear Equations
Definition
A system which has at least one solution is called consistent. If it doesn’t
have any solutions it is called inconsistent.
In the following discussion, the main questions we want to answer are:
Given a system of equations, does it have one or more solutions (in
other words is it consistent)?
If it is consistent, what are the solutions?
Is there a systematic way of finding the solutions?
Linear Algebra Module I: Linear Systems Summer Term 2021 8 / 75
Systems of Linear Equations
Definition
A system which has at least one solution is called consistent. If it doesn’t
have any solutions it is called inconsistent.
In the following discussion, the main questions we want to answer are:
Given a system of equations, does it have one or more solutions (in
other words is it consistent)?
If it is consistent, what are the solutions?
Is there a systematic way of finding the solutions?
Linear Algebra Module I: Linear Systems Summer Term 2021 8 / 75
Systems of Linear Equations
Definition
A system which has at least one solution is called consistent. If it doesn’t
have any solutions it is called inconsistent.
In the following discussion, the main questions we want to answer are:
Given a system of equations, does it have one or more solutions (in
other words is it consistent)?
If it is consistent, what are the solutions?
Is there a systematic way of finding the solutions?
Linear Algebra Module I: Linear Systems Summer Term 2021 8 / 75
Systems of Linear Equations
Definition
A system which has at least one solution is called consistent. If it doesn’t
have any solutions it is called inconsistent.
In the following discussion, the main questions we want to answer are:
Given a system of equations, does it have one or more solutions (in
other words is it consistent)?
If it is consistent, what are the solutions?
Is there a systematic way of finding the solutions?
Linear Algebra Module I: Linear Systems Summer Term 2021 8 / 75
Systems of Linear Equations
Definition
A system which has at least one solution is called consistent. If it doesn’t
have any solutions it is called inconsistent.
In the following discussion, the main questions we want to answer are:
Given a system of equations, does it have one or more solutions (in
other words is it consistent)?
If it is consistent, what are the solutions?
Is there a systematic way of finding the solutions?
Linear Algebra Module I: Linear Systems Summer Term 2021 8 / 75
The material in the first module is focused on answering
these questions.
Linear Algebra Module I: Linear Systems Summer Term 2021 9 / 75
Table of Contents
1 Systems of Linear Equations
2 Solving Systems of Equations – Row Reduction
Overview
Plan for Row Reduction
Notation for Row Reduction
Algorithm for Row Reduction
3 Matrices
Definition of a Matrix
Matrix Operations
Matrix Equations
4 The Superposition Principle
5 Elementary matrices
6 The Dimensions of a System of Equations, and Generalized Equivalence
Linear Algebra Module I: Linear Systems Summer Term 2021 10 / 75
Row Reduction – Overview
We row reduce a system by performing row operations, in
order to find a simpler but equivalent system for which
the solution set is easily read off.
A central idea in solving systems of equations is the
notion of equivalence.
Linear Algebra Module I: Linear Systems Summer Term 2021 11 / 75
Row Reduction – Overview
We row reduce a system by performing row operations, in
order to find a simpler but equivalent system for which
the solution set is easily read off.
A central idea in solving systems of equations is the
notion of equivalence.
Linear Algebra Module I: Linear Systems Summer Term 2021 11 / 75
Equivalence
Definition
Two systems of equations of the same dimensions are equivalent if they
have the same set of solutions.
Given a system of equations, how can we find its solution set?
The answer is by finding a simpler but equivalent system for which the
solution set is easily read off. The method used for finding this simpler
system is called row reduction.
Linear Algebra Module I: Linear Systems Summer Term 2021 12 / 75
Equivalence
Definition
Two systems of equations of the same dimensions are equivalent if they
have the same set of solutions.
Given a system of equations, how can we find its solution set?
The answer is by finding a simpler but equivalent system for which the
solution set is easily read off. The method used for finding this simpler
system is called row reduction.
Linear Algebra Module I: Linear Systems Summer Term 2021 12 / 75
Equivalence
Definition
Two systems of equations of the same dimensions are equivalent if they
have the same set of solutions.
Given a system of equations, how can we find its solution set?
The answer is by finding a simpler but equivalent system for which the
solution set is easily read off. The method used for finding this simpler
system is called row reduction.
Linear Algebra Module I: Linear Systems Summer Term 2021 12 / 75
Plan for row reduction
The operations used to perform row reduction are called row operations,
of which there are three types.
[Type I] Switching two rows;
[Type II] Multiplying a row by a non-zero scalar α;
[Type III] Adding a multiple of one row to another distinct row.
It is quite easy to see the first two types of row operations won’t change
the solution set, and it can also be shown that the third doesn’t either.
Linear Algebra Module I: Linear Systems Summer Term 2021 13 / 75
Plan for row reduction
The operations used to perform row reduction are called row operations,
of which there are three types.
[Type I] Switching two rows;
[Type II] Multiplying a row by a non-zero scalar α;
[Type III] Adding a multiple of one row to another distinct row.
It is quite easy to see the first two types of row operations won’t change
the solution set, and it can also be shown that the third doesn’t either.
Linear Algebra Module I: Linear Systems Summer Term 2021 13 / 75
Plan for row reduction
The operations used to perform row reduction are called row operations,
of which there are three types.
[Type I] Switching two rows;
[Type II] Multiplying a row by a non-zero scalar α;
[Type III] Adding a multiple of one row to another distinct row.
It is quite easy to see the first two types of row operations won’t change
the solution set, and it can also be shown that the third doesn’t either.
Linear Algebra Module I: Linear Systems Summer Term 2021 13 / 75
Plan for row reduction
The operations used to perform row reduction are called row operations,
of which there are three types.
[Type I] Switching two rows;
[Type II] Multiplying a row by a non-zero scalar α;
[Type III] Adding a multiple of one row to another distinct row.
It is quite easy to see the first two types of row operations won’t change
the solution set, and it can also be shown that the third doesn’t either.
Linear Algebra Module I: Linear Systems Summer Term 2021 13 / 75
Plan for row reduction
The operations used to perform row reduction are called row operations,
of which there are three types.
[Type I] Switching two rows;
[Type II] Multiplying a row by a non-zero scalar α;
[Type III] Adding a multiple of one row to another distinct row.
It is quite easy to see the first two types of row operations won’t change
the solution set, and it can also be shown that the third doesn’t either.
Linear Algebra Module I: Linear Systems Summer Term 2021 13 / 75
Plan for row reduction
Definition
Two systems of the same dimensions are row equivalent if one can be
gotten from the other by a sequence of row operations.
The following theorem tells us about when this happens.
Theorem
Two systems of the same dimensions are row equivalent if and only if they
are equivalent.
Linear Algebra Module I: Linear Systems Summer Term 2021 14 / 75
Plan for row reduction
Definition
Two systems of the same dimensions are row equivalent if one can be
gotten from the other by a sequence of row operations.
The following theorem tells us about when this happens.
Theorem
Two systems of the same dimensions are row equivalent if and only if they
are equivalent.
Linear Algebra Module I: Linear Systems Summer Term 2021 14 / 75
Plan for row reduction
Definition
Two systems of the same dimensions are row equivalent if one can be
gotten from the other by a sequence of row operations.
The following theorem tells us about when this happens.
Theorem
Two systems of the same dimensions are row equivalent if and only if they
are equivalent.
Linear Algebra Module I: Linear Systems Summer Term 2021 14 / 75
Plan for row reduction
To proceed in an efficient manner we will use the augmented coefficient
matrix or ACM corresponding to a given system.
Starting with the
m× n system appearing in (1), its associated augmented coefficient matrix
is given by
A =
a11 a12 . . . a1n b1
a21 a22 . . . a2n b2
…
… . . .
…
…
am1 am2 . . . amn bm
This matrix has m rows and (n + 1) columns. Executing a sequence of
row operations and then computing the ACM gives the same result as first
forming the ACM and performing the same sequence of row operations on
that matrix. As the ACM contains all of the information relevant for
solving the system but is easier to work with, we will always form the ACM
first, and perform row operations on that matrix.
Linear Algebra Module I: Linear Systems Summer Term 2021 15 / 75
Plan for row reduction
To proceed in an efficient manner we will use the augmented coefficient
matrix or ACM corresponding to a given system. Starting with the
m× n system appearing in (1), its associated augmented coefficient matrix
is given by
A =
a11 a12 . . . a1n b1
a21 a22 . . . a2n b2
…
… . . .
…
…
am1 am2 . . . amn bm
This matrix has m rows and (n + 1) columns. Executing a sequence of
row operations and then computing the ACM gives the same result as first
forming the ACM and performing the same sequence of row operations on
that matrix. As the ACM contains all of the information relevant for
solving the system but is easier to work with, we will always form the ACM
first, and perform row operations on that matrix.
Linear Algebra Module I: Linear Systems Summer Term 2021 15 / 75
Plan for row reduction
To proceed in an efficient manner we will use the augmented coefficient
matrix or ACM corresponding to a given system. Starting with the
m× n system appearing in (1), its associated augmented coefficient matrix
is given by
A =
a11 a12 . . . a1n b1
a21 a22 . . . a2n b2
…
… . . .
…
…
am1 am2 . . . amn bm
This matrix has m rows and (n + 1) columns. Executing a sequence of
row operations and then computing the ACM gives the same result as first
forming the ACM and performing the same sequence of row operations on
that matrix. As the ACM contains all of the information relevant for
solving the system but is easier to work with, we will always form the ACM
first, and perform row operations on that matrix.
Linear Algebra Module I: Linear Systems Summer Term 2021 15 / 75
Plan for row reduction
To proceed in an efficient manner we will use the augmented coefficient
matrix or ACM corresponding to a given system. Starting with the
m× n system appearing in (1), its associated augmented coefficient matrix
is given by
A =
a11 a12 . . . a1n b1
a21 a22 . . . a2n b2
…
… . . .
…
…
am1 am2 . . . amn bm
This matrix has m rows and (n + 1) columns.
Executing a sequence of
row operations and then computing the ACM gives the same result as first
forming the ACM and performing the same sequence of row operations on
that matrix. As the ACM contains all of the information relevant for
solving the system but is easier to work with, we will always form the ACM
first, and perform row operations on that matrix.
Linear Algebra Module I: Linear Systems Summer Term 2021 15 / 75
Plan for row reduction
To proceed in an efficient manner we will use the augmented coefficient
matrix or ACM corresponding to a given system. Starting with the
m× n system appearing in (1), its associated augmented coefficient matrix
is given by
A =
a11 a12 . . . a1n b1
a21 a22 . . . a2n b2
…
… . . .
…
…
am1 am2 . . . amn bm
This matrix has m rows and (n + 1) columns. Executing a sequence of
row operations and then computing the ACM gives the same result as first
forming the ACM and performing the same sequence of row operations on
that matrix.
As the ACM contains all of the information relevant for
solving the system but is easier to work with, we will always form the ACM
first, and perform row operations on that matrix.
Linear Algebra Module I: Linear Systems Summer Term 2021 15 / 75
Plan for row reduction
To proceed in an efficient manner we will use the augmented coefficient
matrix or ACM corresponding to a given system. Starting with the
m× n system appearing in (1), its associated augmented coefficient matrix
is given by
A =
a11 a12 . . . a1n b1
a21 a22 . . . a2n b2
…
… . . .
…
…
am1 am2 . . . amn bm
This matrix has m rows and (n + 1) columns. Executing a sequence of
row operations and then computing the ACM gives the same result as first
forming the ACM and performing the same sequence of row operations on
that matrix. As the ACM contains all of the information relevant for
solving the system but is easier to work with, we will always form the ACM
first, and perform row operations on that matrix.
Linear Algebra Module I: Linear Systems Summer Term 2021 15 / 75
Plan for Row Reduction – Reduced Row Echelon Form
The simplified form in which we would like to get our matrix is referred to
as reduced row echelon form. This is a term which applies to matrices
in general, not just augmented coefficient matrices.
Definition
A matrix B of numbers is in row echelon form if
Every row of zeros lies below every non-zero row;
the left-most non-zero entry of a non-zero row is 1 (called a leading
1);
if both row k and row (k + 1) are non-zero, the leading 1 in row
(k + 1) appears to the right of the leading 1 in row k.
It is in reduced row echelon form if in addition to being in row echelon
form it satisfies the property that
In every column that contains a leading 1, that leading 1 is the only
non-zero entry.
Linear Algebra Module I: Linear Systems Summer Term 2021 16 / 75
Plan for Row Reduction – Reduced Row Echelon Form
The simplified form in which we would like to get our matrix is referred to
as reduced row echelon form. This is a term which applies to matrices
in general, not just augmented coefficient matrices.
Definition
A matrix B of numbers is in row echelon form if
Every row of zeros lies below every non-zero row;
the left-most non-zero entry of a non-zero row is 1 (called a leading
1);
if both row k and row (k + 1) are non-zero, the leading 1 in row
(k + 1) appears to the right of the leading 1 in row k.
It is in reduced row echelon form if in addition to being in row echelon
form it satisfies the property that
In every column that contains a leading 1, that leading 1 is the only
non-zero entry.
Linear Algebra Module I: Linear Systems Summer Term 2021 16 / 75
Plan for Row Reduction – Reduced Row Echelon Form
The simplified form in which we would like to get our matrix is referred to
as reduced row echelon form. This is a term which applies to matrices
in general, not just augmented coefficient matrices.
Definition
A matrix B of numbers is in row echelon form if
Every row of zeros lies below every non-zero row;
the left-most non-zero entry of a non-zero row is 1 (called a leading
1);
if both row k and row (k + 1) are non-zero, the leading 1 in row
(k + 1) appears to the right of the leading 1 in row k.
It is in reduced row echelon form if in addition to being in row echelon
form it satisfies the property that
In every column that contains a leading 1, that leading 1 is the only
non-zero entry.
Linear Algebra Module I: Linear Systems Summer Term 2021 16 / 75
Plan for Row Reduction – Reduced Row Echelon Form
The simplified form in which we would like to get our matrix is referred to
as reduced row echelon form. This is a term which applies to matrices
in general, not just augmented coefficient matrices.
Definition
A matrix B of numbers is in row echelon form if
Every row of zeros lies below every non-zero row;
the left-most non-zero entry of a non-zero row is 1 (called a leading
1);
if both row k and row (k + 1) are non-zero, the leading 1 in row
(k + 1) appears to the right of the leading 1 in row k.
It is in reduced row echelon form if in addition to being in row echelon
form it satisfies the property that
In every column that contains a leading 1, that leading 1 is the only
non-zero entry.
Linear Algebra Module I: Linear Systems Summer Term 2021 16 / 75
Plan for Row Reduction – Reduced Row Echelon Form
The simplified form in which we would like to get our matrix is referred to
as reduced row echelon form. This is a term which applies to matrices
in general, not just augmented coefficient matrices.
Definition
A matrix B of numbers is in row echelon form if
Every row of zeros lies below every non-zero row;
the left-most non-zero entry of a non-zero row is 1 (called a leading
1);
if both row k and row (k + 1) are non-zero, the leading 1 in row
(k + 1) appears to the right of the leading 1 in row k.
It is in reduced row echelon form if in addition to being in row echelon
form it satisfies the property that
In every column that contains a leading 1, that leading 1 is the only
non-zero entry.
Linear Algebra Module I: Linear Systems Summer Term 2021 16 / 75
Reduced Row Echelon Form
Examples
Consider the three matrices
A =
1 2 −1 40 0 1 3
0 1 0 2
, B =
1 2 3 40 1 5 7
0 0 0 1
, C =
1 0 0 40 1 0 3
0 0 1 1
The matrix A is not in row echelon form, while B is in row echelon but not
reduced row echelon form, and C is in reduced row echelon form (the
reader should check this, and understand why for each example). The
main fact we will need to know is
Theorem
Every matrix of numbers is row-equivalent to one which is in reduced row
echelon form.
Linear Algebra Module I: Linear Systems Summer Term 2021 17 / 75
Reduced Row Echelon Form
Examples
Consider the three matrices
A =
1 2 −1 40 0 1 3
0 1 0 2
, B =
1 2 3 40 1 5 7
0 0 0 1
, C =
1 0 0 40 1 0 3
0 0 1 1
The matrix A is not in row echelon form, while B is in row echelon but not
reduced row echelon form, and C is in reduced row echelon form (the
reader should check this, and understand why for each example). The
main fact we will need to know is
Theorem
Every matrix of numbers is row-equivalent to one which is in reduced row
echelon form.
Linear Algebra Module I: Linear Systems Summer Term 2021 17 / 75
Reduced Row Echelon Form
Examples
Consider the three matrices
A =
1 2 −1 40 0 1 3
0 1 0 2
, B =
1 2 3 40 1 5 7
0 0 0 1
, C =
1 0 0 40 1 0 3
0 0 1 1
The matrix A is not in row echelon form, while B is in row echelon but not
reduced row echelon form, and C is in reduced row echelon form (the
reader should check this, and understand why for each example). The
main fact we will need to know is
Theorem
Every matrix of numbers is row-equivalent to one which is in reduced row
echelon form.
Linear Algebra Module I: Linear Systems Summer Term 2021 17 / 75
Reduced Row Echelon Form
When A is the ACM of a system of equations, rref (A) tells us everything
we would like to know about the original system.
Theorem
Let A be the ACM of an m × n system of equations. Then the system
is inconsistent precisely when rref (A) contains a row of the form
[0 0 0 0 . . . 0 | 1];
has a unique solution precisely when each column of rref (A) except
the right-most column contains a leading 1;
has infinitely many solutions when it is i) consistent, and ii) at least
one of the first n columns of rref (A) does not contain a leading 1.
In the last case, the solution set is parametrized by the variables appearing
in the original system which are indexed by the columns of rref (A) to the
left of the bar which do not contain a leading 1.
Linear Algebra Module I: Linear Systems Summer Term 2021 18 / 75
Reduced Row Echelon Form
When A is the ACM of a system of equations, rref (A) tells us everything
we would like to know about the original system.
Theorem
Let A be the ACM of an m × n system of equations. Then the system
is inconsistent precisely when rref (A) contains a row of the form
[0 0 0 0 . . . 0 | 1];
has a unique solution precisely when each column of rref (A) except
the right-most column contains a leading 1;
has infinitely many solutions when it is i) consistent, and ii) at least
one of the first n columns of rref (A) does not contain a leading 1.
In the last case, the solution set is parametrized by the variables appearing
in the original system which are indexed by the columns of rref (A) to the
left of the bar which do not contain a leading 1.
Linear Algebra Module I: Linear Systems Summer Term 2021 18 / 75
Reduced Row Echelon Form
When A is the ACM of a system of equations, rref (A) tells us everything
we would like to know about the original system.
Theorem
Let A be the ACM of an m × n system of equations. Then the system
is inconsistent precisely when rref (A) contains a row of the form
[0 0 0 0 . . . 0 | 1];
has a unique solution precisely when each column of rref (A) except
the right-most column contains a leading 1;
has infinitely many solutions when it is i) consistent, and ii) at least
one of the first n columns of rref (A) does not contain a leading 1.
In the last case, the solution set is parametrized by the variables appearing
in the original system which are indexed by the columns of rref (A) to the
left of the bar which do not contain a leading 1.
Linear Algebra Module I: Linear Systems Summer Term 2021 18 / 75
Reduced Row Echelon Form
When A is the ACM of a system of equations, rref (A) tells us everything
we would like to know about the original system.
Theorem
Let A be the ACM of an m × n system of equations. Then the system
is inconsistent precisely when rref (A) contains a row of the form
[0 0 0 0 . . . 0 | 1];
has a unique solution precisely when each column of rref (A) except
the right-most column contains a leading 1;
has infinitely many solutions when it is i) consistent, and ii) at least
one of the first n columns of rref (A) does not contain a leading 1.
In the last case, the solution set is parametrized by the variables appearing
in the original system which are indexed by the columns of rref (A) to the
left of the bar which do not contain a leading 1.
Linear Algebra Module I: Linear Systems Summer Term 2021 18 / 75
Reduced Row Echelon Form
When A is the ACM of a system of equations, rref (A) tells us everything
we would like to know about the original system.
Theorem
Let A be the ACM of an m × n system of equations. Then the system
is inconsistent precisely when rref (A) contains a row of the form
[0 0 0 0 . . . 0 | 1];
has a unique solution precisely when each column of rref (A) except
the right-most column contains a leading 1;
has infinitely many solutions when it is i) consistent, and ii) at least
one of the first n columns of rref (A) does not contain a leading 1.
In the last case, the solution set is parametrized by the variables appearing
in the original system which are indexed by the columns of rref (A) to the
left of the bar which do not contain a leading 1.
Linear Algebra Module I: Linear Systems Summer Term 2021 18 / 75
Reduced Row Echelon Form
When A is the ACM of a system of equations, rref (A) tells us everything
we would like to know about the original system.
Theorem
Let A be the ACM of an m × n system of equations. Then the system
is inconsistent precisely when rref (A) contains a row of the form
[0 0 0 0 . . . 0 | 1];
has a unique solution precisely when each column of rref (A) except
the right-most column contains a leading 1;
has infinitely many solutions when it is i) consistent, and ii) at least
one of the first n columns of rref (A) does not contain a leading 1.
In the last case, the solution set is parametrized by the variables appearing
in the original system which are indexed by the columns of rref (A) to the
left of the bar which do not contain a leading 1.
Linear Algebra Module I: Linear Systems Summer Term 2021 18 / 75
Reduced Row Echelon Form
When A is the ACM of a system, rref (A) is the ACM of another system
equivalent to the original one, which is the reduced row echelon form of
the original system.
Examples
The rref of the ACM is given by
rref (A) =
1 2 3 0 00 0 0 1 0
0 0 0 0 1
In this case, we would conclude that the system is inconsistent, because of
the last row.
Linear Algebra Module I: Linear Systems Summer Term 2021 19 / 75
Reduced Row Echelon Form
When A is the ACM of a system, rref (A) is the ACM of another system
equivalent to the original one, which is the reduced row echelon form of
the original system.
Examples
The rref of the ACM is given by
rref (A) =
1 2 3 0 00 0 0 1 0
0 0 0 0 1
In this case, we would conclude that the system is inconsistent, because of
the last row.
Linear Algebra Module I: Linear Systems Summer Term 2021 19 / 75
Reduced Row Echelon Form
When A is the ACM of a system, rref (A) is the ACM of another system
equivalent to the original one, which is the reduced row echelon form of
the original system.
Examples
The rref of the ACM is given by
rref (A) =
1 2 3 0 00 0 0 1 0
0 0 0 0 1
In this case, we would conclude that the system is inconsistent, because of
the last row.
Linear Algebra Module I: Linear Systems Summer Term 2021 19 / 75
Reduced Row Echelon Form
When A is the ACM of a system, rref (A) is the ACM of another system
equivalent to the original one, which is the reduced row echelon form of
the original system.
Examples
The rref of the ACM is given by
rref (A) =
1 0 0 0 5
0 1 0 0 −2
0 0 1 0 4
0 0 0 1 10
In this case, every column to the left of the bar dividing the coefficient
matrix from the augmented part contains a leading 1. Hence there is a
unique solution.
Linear Algebra Module I: Linear Systems Summer Term 2021 20 / 75
Reduced Row Echelon Form
When A is the ACM of a system, rref (A) is the ACM of another system
equivalent to the original one, which is the reduced row echelon form of
the original system.
Examples
The rref of the ACM is given by
rref (A) =
1 0 0 0 5
0 1 0 0 −2
0 0 1 0 4
0 0 0 1 10
In this case, every column to the left of the bar dividing the coefficient
matrix from the augmented part contains a leading 1. Hence there is a
unique solution.
Linear Algebra Module I: Linear Systems Summer Term 2021 20 / 75
Reduced Row Echelon Form
When A is the ACM of a system, rref (A) is the ACM of another system
equivalent to the original one, which is the reduced row echelon form of
the original system.
Examples
The rref of the ACM is given by
rref (A) =
1 0 0 0 5
0 1 0 0 −2
0 0 1 0 4
0 0 0 1 10
In this case, every column to the left of the bar dividing the coefficient
matrix from the augmented part contains a leading 1. Hence there is a
unique solution.
Linear Algebra Module I: Linear Systems Summer Term 2021 20 / 75
Reduced Row Echelon Form
When A is the ACM of a system, rref (A) is the ACM of another system
equivalent to the original one, which is the reduced row echelon form of
the original system.
Examples
The rref of the ACM is given by
rref (A) =
1 0 0 3 7
0 1 0 1 5
0 0 1 2 2
0 0 0 0 0
Here we have a 4× 4 system which has infinitely many solutions; this is
seen by noting i) it is consistent, and ii) the fourth column does not
contains a leading 1.
Linear Algebra Module I: Linear Systems Summer Term 2021 21 / 75
Reduced Row Echelon Form
When A is the ACM of a system, rref (A) is the ACM of another system
equivalent to the original one, which is the reduced row echelon form of
the original system.
Examples
The rref of the ACM is given by
rref (A) =
1 0 0 3 7
0 1 0 1 5
0 0 1 2 2
0 0 0 0 0
Here we have a 4× 4 system which has infinitely many solutions; this is
seen by noting i) it is consistent, and ii) the fourth column does not
contains a leading 1.
Linear Algebra Module I: Linear Systems Summer Term 2021 21 / 75
Reduced Row Echelon Form
When A is the ACM of a system, rref (A) is the ACM of another system
equivalent to the original one, which is the reduced row echelon form of
the original system.
Examples
The rref of the ACM is given by
rref (A) =
1 0 0 3 7
0 1 0 1 5
0 0 1 2 2
0 0 0 0 0
Here we have a 4× 4 system which has infinitely many solutions; this is
seen by noting i) it is consistent, and ii) the fourth column does not
contains a leading 1.
Linear Algebra Module I: Linear Systems Summer Term 2021 21 / 75
Notation for Row Reduction
In the process of putting the ACM into reduced row echelon form, it is
often desirable to keep track of the precise row operations being used. For
this, some notation is useful. The following summarizes the notation we
use in this course.
Type I operation
What it does: switches i th and jth rows.
Indicated by: Ri ↔ Rj
Type II operation
What it does: multiplies i th row by r 6= 0.
Indicated by: r · Ri
Type III operation
What it does: adds a times the i th row to the jth row
Indicated by: Rj := Rj + a · Ri or “a · Ri added to Rj”
Linear Algebra Module I: Linear Systems Summer Term 2021 22 / 75
Notation for Row Reduction
In the process of putting the ACM into reduced row echelon form, it is
often desirable to keep track of the precise row operations being used. For
this, some notation is useful. The following summarizes the notation we
use in this course.
Type I operation
What it does: switches i th and jth rows.
Indicated by: Ri ↔ Rj
Type II operation
What it does: multiplies i th row by r 6= 0.
Indicated by: r · Ri
Type III operation
What it does: adds a times the i th row to the jth row
Indicated by: Rj := Rj + a · Ri or “a · Ri added to Rj”
Linear Algebra Module I: Linear Systems Summer Term 2021 22 / 75
Notation for Row Reduction
In the process of putting the ACM into reduced row echelon form, it is
often desirable to keep track of the precise row operations being used. For
this, some notation is useful. The following summarizes the notation we
use in this course.
Type I operation
What it does: switches i th and jth rows.
Indicated by: Ri ↔ Rj
Type II operation
What it does: multiplies i th row by r 6= 0.
Indicated by: r · Ri
Type III operation
What it does: adds a times the i th row to the jth row
Indicated by: Rj := Rj + a · Ri or “a · Ri added to Rj”
Linear Algebra Module I: Linear Systems Summer Term 2021 22 / 75
Notation for Row Reduction
In the process of putting the ACM into reduced row echelon form, it is
often desirable to keep track of the precise row operations being used. For
this, some notation is useful. The following summarizes the notation we
use in this course.
Type I operation
What it does: switches i th and jth rows.
Indicated by: Ri ↔ Rj
Type II operation
What it does: multiplies i th row by r 6= 0.
Indicated by: r · Ri
Type III operation
What it does: adds a times the i th row to the jth row
Indicated by: Rj := Rj + a · Ri or “a · Ri added to Rj”
Linear Algebra Module I: Linear Systems Summer Term 2021 22 / 75
Notation for Row Reduction
In the process of putting the ACM into reduced row echelon form, it is
often desirable to keep track of the precise row operations being used. For
this, some notation is useful. The following summarizes the notation we
use in this course.
Type I operation
What it does: switches i th and jth rows.
Indicated by: Ri ↔ Rj
Type II operation
What it does: multiplies i th row by r 6= 0.
Indicated by: r · Ri
Type III operation
What it does: adds a times the i th row to the jth row
Indicated by: Rj := Rj + a · Ri or “a · Ri added to Rj”
Linear Algebra Module I: Linear Systems Summer Term 2021 22 / 75
Notation for Row Reduction
In the process of putting the ACM into reduced row echelon form, it is
often desirable to keep track of the precise row operations being used. For
this, some notation is useful. The following summarizes the notation we
use in this course.
Type I operation
What it does: switches i th and jth rows.
Indicated by: Ri ↔ Rj
Type II operation
What it does: multiplies i th row by r 6= 0.
Indicated by: r · Ri
Type III operation
What it does: adds a times the i th row to the jth row
Indicated by: Rj := Rj + a · Ri or “a · Ri added to Rj”
Linear Algebra Module I: Linear Systems Summer Term 2021 22 / 75
Notation for Row Reduction
In the process of putting the ACM into reduced row echelon form, it is
often desirable to keep track of the precise row operations being used. For
this, some notation is useful. The following summarizes the notation we
use in this course.
Type I operation
What it does: switches i th and jth rows.
Indicated by: Ri ↔ Rj
Type II operation
What it does: multiplies i th row by r 6= 0.
Indicated by: r · Ri
Type III operation
What it does: adds a times the i th row to the jth row
Indicated by: Rj := Rj + a · Ri or “a · Ri added to Rj”
Linear Algebra Module I: Linear Systems Summer Term 2021 22 / 75
Notation for Row Reduction
In the process of putting the ACM into reduced row echelon form, it is
often desirable to keep track of the precise row operations being used. For
this, some notation is useful. The following summarizes the notation we
use in this course.
Type I operation
What it does: switches i th and jth rows.
Indicated by: Ri ↔ Rj
Type II operation
What it does: multiplies i th row by r 6= 0.
Indicated by: r · Ri
Type III operation
What it does: adds a times the i th row to the jth row
Indicated by: Rj := Rj + a · Ri or “a · Ri added to Rj”
Linear Algebra Module I: Linear Systems Summer Term 2021 22 / 75
Notation for Row Reduction
In the process of putting the ACM into reduced row echelon form, it is
often desirable to keep track of the precise row operations being used. For
this, some notation is useful. The following summarizes the notation we
use in this course.
Type I operation
What it does: switches i th and jth rows.
Indicated by: Ri ↔ Rj
Type II operation
What it does: multiplies i th row by r 6= 0.
Indicated by: r · Ri
Type III operation
What it does: adds a times the i th row to the jth row
Indicated by: Rj := Rj + a · Ri or “a · Ri added to Rj”
Linear Algebra Module I: Linear Systems Summer Term 2021 22 / 75
Notation for Row Reduction
In the process of putting the ACM into reduced row echelon form, it is
often desirable to keep track of the precise row operations being used. For
this, some notation is useful. The following summarizes the notation we
use in this course.
Type I operation
What it does: switches i th and jth rows.
Indicated by: Ri ↔ Rj
Type II operation
What it does: multiplies i th row by r 6= 0.
Indicated by: r · Ri
Type III operation
What it does: adds a times the i th row to the jth row
Indicated by: Rj := Rj + a · Ri or “a · Ri added to Rj”
Linear Algebra Module I: Linear Systems Summer Term 2021 22 / 75
Notation for Row Reduction
Examples
An example of a specific type I operation switching the 2nd and 3rd rows is
3 2 74 1 9
1 0 −2
R2↔R3−−−−→
3 2 71 0 −2
4 1 9
Linear Algebra Module I: Linear Systems Summer Term 2021 23 / 75
Notation for Row Reduction
Examples
An example of a specific type I operation switching the 2nd and 3rd rows is
3 2 74 1 9
1 0 −2
R2↔R3−−−−→
3 2 71 0 −2
4 1 9
Linear Algebra Module I: Linear Systems Summer Term 2021 23 / 75
Notation for Row Reduction
Examples
Suppose we started with the same matrix, but performed a type II
operation instead, where the second row is multiplied by 3. Then using the
above conventions, we would denote that by
3 2 74 1 9
1 0 −2
3·R2−−→
3 2 712 3 27
1 0 −2
Linear Algebra Module I: Linear Systems Summer Term 2021 24 / 75
Notation for Row Reduction
Examples
Suppose we started with the same matrix, but performed a type II
operation instead, where the second row is multiplied by 3. Then using the
above conventions, we would denote that by
3 2 74 1 9
1 0 −2
3·R2−−→
3 2 712 3 27
1 0 −2
Linear Algebra Module I: Linear Systems Summer Term 2021 24 / 75
Notation for Row Reduction
Examples
Suppose we started with the same matrix, but performed a type III
operation, where the second row is multiplied by −4 and added to the first
row. Then using the above conventions, we would denote that by
3 2 74 1 9
1 0 −2
R1:=R1+(−4)·R2−−−−−−−−−−→
−13 −2 −294 1 9
1 0 −2
Linear Algebra Module I: Linear Systems Summer Term 2021 25 / 75
Notation for Row Reduction
Examples
Suppose we started with the same matrix, but performed a type III
operation, where the second row is multiplied by −4 and added to the first
row. Then using the above conventions, we would denote that by
3 2 74 1 9
1 0 −2
R1:=R1+(−4)·R2−−−−−−−−−−→
−13 −2 −294 1 9
1 0 −2
Linear Algebra Module I: Linear Systems Summer Term 2021 25 / 75
Algorithm for Row Reduction
At this point, we see that the reduced row echelon form of the ACM
allows us to solve the system. However, we have not discussed how the
transition to that form is accomplished. The following algorithm describes
that process.
[Step 1] Determine the left-most column containing a non-zero entry
(it exists if the matrix is non-zero).
[Step 2] If needed, perform a type I operation so that the first
non-zero column has a non-zero entry in the first row.
[Step 3] If needed, perform a type II operation to make that first
non-zero entry 1 (the leading 1 in the first row).
[Step 4] Perform type III operations to make the entries below this
leading 1 equal to 0.
[Step 5] Repeat the previous four steps on the submatrix consisting
of all except the first row, until reaching the end of the rows.
[Step 6] For each row containing a leading 1, proceed upward using
type III operations to make zero any entry appearing above a leading
1.
Linear Algebra Module I: Linear Systems Summer Term 2021 26 / 75
Algorithm for Row Reduction
At this point, we see that the reduced row echelon form of the ACM
allows us to solve the system. However, we have not discussed how the
transition to that form is accomplished. The following algorithm describes
that process.
[Step 1] Determine the left-most column containing a non-zero entry
(it exists if the matrix is non-zero).
[Step 2] If needed, perform a type I operation so that the first
non-zero column has a non-zero entry in the first row.
[Step 3] If needed, perform a type II operation to make that first
non-zero entry 1 (the leading 1 in the first row).
[Step 4] Perform type III operations to make the entries below this
leading 1 equal to 0.
[Step 5] Repeat the previous four steps on the submatrix consisting
of all except the first row, until reaching the end of the rows.
[Step 6] For each row containing a leading 1, proceed upward using
type III operations to make zero any entry appearing above a leading
1.
Linear Algebra Module I: Linear Systems Summer Term 2021 26 / 75
Algorithm for Row Reduction
At this point, we see that the reduced row echelon form of the ACM
allows us to solve the system. However, we have not discussed how the
transition to that form is accomplished. The following algorithm describes
that process.
[Step 1] Determine the left-most column containing a non-zero entry
(it exists if the matrix is non-zero).
[Step 2] If needed, perform a type I operation so that the first
non-zero column has a non-zero entry in the first row.
[Step 3] If needed, perform a type II operation to make that first
non-zero entry 1 (the leading 1 in the first row).
[Step 4] Perform type III operations to make the entries below this
leading 1 equal to 0.
[Step 5] Repeat the previous four steps on the submatrix consisting
of all except the first row, until reaching the end of the rows.
[Step 6] For each row containing a leading 1, proceed upward using
type III operations to make zero any entry appearing above a leading
1.
Linear Algebra Module I: Linear Systems Summer Term 2021 26 / 75
Algorithm for Row Reduction
At this point, we see that the reduced row echelon form of the ACM
allows us to solve the system. However, we have not discussed how the
transition to that form is accomplished. The following algorithm describes
that process.
[Step 1] Determine the left-most column containing a non-zero entry
(it exists if the matrix is non-zero).
[Step 2] If needed, perform a type I operation so that the first
non-zero column has a non-zero entry in the first row.
[Step 3] If needed, perform a type II operation to make that first
non-zero entry 1 (the leading 1 in the first row).
[Step 4] Perform type III operations to make the entries below this
leading 1 equal to 0.
[Step 5] Repeat the previous four steps on the submatrix consisting
of all except the first row, until reaching the end of the rows.
[Step 6] For each row containing a leading 1, proceed upward using
type III operations to make zero any entry appearing above a leading
1.
Linear Algebra Module I: Linear Systems Summer Term 2021 26 / 75
Algorithm for Row Reduction
At this point, we see that the reduced row echelon form of the ACM
allows us to solve the system. However, we have not discussed how the
transition to that form is accomplished. The following algorithm describes
that process.
[Step 1] Determine the left-most column containing a non-zero entry
(it exists if the matrix is non-zero).
[Step 2] If needed, perform a type I operation so that the first
non-zero column has a non-zero entry in the first row.
[Step 3] If needed, perform a type II operation to make that first
non-zero entry 1 (the leading 1 in the first row).
[Step 4] Perform type III operations to make the entries below this
leading 1 equal to 0.
[Step 5] Repeat the previous four steps on the submatrix consisting
of all except the first row, until reaching the end of the rows.
[Step 6] For each row containing a leading 1, proceed upward using
type III operations to make zero any entry appearing above a leading
1.
Linear Algebra Module I: Linear Systems Summer Term 2021 26 / 75
Algorithm for Row Reduction
At this point, we see that the reduced row echelon form of the ACM
allows us to solve the system. However, we have not discussed how the
transition to that form is accomplished. The following algorithm describes
that process.
[Step 1] Determine the left-most column containing a non-zero entry
(it exists if the matrix is non-zero).
[Step 2] If needed, perform a type I operation so that the first
non-zero column has a non-zero entry in the first row.
[Step 3] If needed, perform a type II operation to make that first
non-zero entry 1 (the leading 1 in the first row).
[Step 4] Perform type III operations to make the entries below this
leading 1 equal to 0.
[Step 5] Repeat the previous four steps on the submatrix consisting
of all except the first row, until reaching the end of the rows.
[Step 6] For each row containing a leading 1, proceed upward using
type III operations to make zero any entry appearing above a leading
1.
Linear Algebra Module I: Linear Systems Summer Term 2021 26 / 75
Algorithm for Row Reduction
At this point, we see that the reduced row echelon form of the ACM
allows us to solve the system. However, we have not discussed how the
transition to that form is accomplished. The following algorithm describes
that process.
[Step 1] Determine the left-most column containing a non-zero entry
(it exists if the matrix is non-zero).
[Step 2] If needed, perform a type I operation so that the first
non-zero column has a non-zero entry in the first row.
[Step 3] If needed, perform a type II operation to make that first
non-zero entry 1 (the leading 1 in the first row).
[Step 4] Perform type III operations to make the entries below this
leading 1 equal to 0.
[Step 5] Repeat the previous four steps on the submatrix consisting
of all except the first row, until reaching the end of the rows.
[Step 6] For each row containing a leading 1, proceed upward using
type III operations to make zero any entry appearing above a leading
1.
Linear Algebra Module I: Linear Systems Summer Term 2021 26 / 75
Algorithm for Row Reduction
To summarize,
Theorem
Every system of equations is uniquely represented by its associated
augmented coefficient matrix (ACM), and every ACM results from a
unique system of equations, up to a labeling of the indeterminates.
The solution set to the system can be determined by
putting the ACM in reduced row echelon form (rref), and
reading off the solution(s) from the resulting matrix.
Moreover, the computation of rref(ACM) can be performed in a systematic
fashion, by following the algorithmic procedure listed above.
Linear Algebra Module I: Linear Systems Summer Term 2021 27 / 75
Algorithm for Row Reduction
To summarize,
Theorem
Every system of equations is uniquely represented by its associated
augmented coefficient matrix (ACM), and every ACM results from a
unique system of equations, up to a labeling of the indeterminates.
The solution set to the system can be determined by
putting the ACM in reduced row echelon form (rref), and
reading off the solution(s) from the resulting matrix.
Moreover, the computation of rref(ACM) can be performed in a systematic
fashion, by following the algorithmic procedure listed above.
Linear Algebra Module I: Linear Systems Summer Term 2021 27 / 75
Algorithm for Row Reduction
To summarize,
Theorem
Every system of equations is uniquely represented by its associated
augmented coefficient matrix (ACM), and every ACM results from a
unique system of equations, up to a labeling of the indeterminates.
The solution set to the system can be determined by
putting the ACM in reduced row echelon form (rref), and
reading off the solution(s) from the resulting matrix.
Moreover, the computation of rref(ACM) can be performed in a systematic
fashion, by following the algorithmic procedure listed above.
Linear Algebra Module I: Linear Systems Summer Term 2021 27 / 75
Algorithm for Row Reduction
To summarize,
Theorem
Every system of equations is uniquely represented by its associated
augmented coefficient matrix (ACM), and every ACM results from a
unique system of equations, up to a labeling of the indeterminates.
The solution set to the system can be determined by
putting the ACM in reduced row echelon form (rref), and
reading off the solution(s) from the resulting matrix.
Moreover, the computation of rref(ACM) can be performed in a systematic
fashion, by following the algorithmic procedure listed above.
Linear Algebra Module I: Linear Systems Summer Term 2021 27 / 75
Algorithm for Row Reduction
Examples
We will continue with a series of examples, using MATLAB/Octave
Linear Algebra Module I: Linear Systems Summer Term 2021 28 / 75
Table of Contents
1 Systems of Linear Equations
2 Solving Systems of Equations – Row Reduction
Overview
Plan for Row Reduction
Notation for Row Reduction
Algorithm for Row Reduction
3 Matrices
Definition of a Matrix
Matrix Operations
Matrix Equations
4 The Superposition Principle
5 Elementary matrices
6 The Dimensions of a System of Equations, and Generalized Equivalence
Linear Algebra Module I: Linear Systems Summer Term 2021 29 / 75
Matrices – Definitions and terminology
In the previous chapter we have already invoked the concept of matrices.
However before going further we will need to establish a framework for
them, and some of their basic properties.
Definition of a matrix
A matrix is a rectangular array whose entries are of the same type.
An m × n matrix is one which has m rows and n columns. The numbers
m and n are referred to as the dimensons of the matrix.
The collection of all m × n matrices of real numbers will be denoted
by Rm×n.
We will use MATLAB convention in which the (i , j)th entry of the matrix
A (the entry in row i and column j) is denoted by A(i , j). Also we will
write the i th row as A(i , :), and the jth column as A(:, j).
Linear Algebra Module I: Linear Systems Summer Term 2021 30 / 75
Matrices – Definitions and terminology
In the previous chapter we have already invoked the concept of matrices.
However before going further we will need to establish a framework for
them, and some of their basic properties.
Definition of a matrix
A matrix is a rectangular array whose entries are of the same type.
An m × n matrix is one which has m rows and n columns. The numbers
m and n are referred to as the dimensons of the matrix.
The collection of all m × n matrices of real numbers will be denoted
by Rm×n.
We will use MATLAB convention in which the (i , j)th entry of the matrix
A (the entry in row i and column j) is denoted by A(i , j). Also we will
write the i th row as A(i , :), and the jth column as A(:, j).
Linear Algebra Module I: Linear Systems Summer Term 2021 30 / 75
Matrices – Definitions and terminology
In the previous chapter we have already invoked the concept of matrices.
However before going further we will need to establish a framework for
them, and some of their basic properties.
Definition of a matrix
A matrix is a rectangular array whose entries are of the same type.
An m × n matrix is one which has m rows and n columns. The numbers
m and n are referred to as the dimensons of the matrix.
The collection of all m × n matrices of real numbers will be denoted
by Rm×n.
We will use MATLAB convention in which the (i , j)th entry of the matrix
A (the entry in row i and column j) is denoted by A(i , j). Also we will
write the i th row as A(i , :), and the jth column as A(:, j).
Linear Algebra Module I: Linear Systems Summer Term 2021 30 / 75
Matrices – Definitions and terminology
In the previous chapter we have already invoked the concept of matrices.
However before going further we will need to establish a framework for
them, and some of their basic properties.
Definition of a matrix
A matrix is a rectangular array whose entries are of the same type.
An m × n matrix is one which has m rows and n columns. The numbers
m and n are referred to as the dimensons of the matrix.
The collection of all m × n matrices of real numbers will be denoted
by Rm×n.
We will use MATLAB convention in which the (i , j)th entry of the matrix
A (the entry in row i and column j) is denoted by A(i , j). Also we will
write the i th row as A(i , :), and the jth column as A(:, j).
Linear Algebra Module I: Linear Systems Summer Term 2021 30 / 75
Matrices – Definitions and terminology
In the previous chapter we have already invoked the concept of matrices.
However before going further we will need to establish a framework for
them, and some of their basic properties.
Definition of a matrix
A matrix is a rectangular array whose entries are of the same type.
An m × n matrix is one which has m rows and n columns. The numbers
m and n are referred to as the dimensons of the matrix.
The collection of all m × n matrices of real numbers will be denoted
by Rm×n.
We will use MATLAB convention in which the (i , j)th entry of the matrix
A (the entry in row i and column j) is denoted by A(i , j). Also we will
write the i th row as A(i , :), and the jth column as A(:, j).
Linear Algebra Module I: Linear Systems Summer Term 2021 30 / 75
Matrices – Definitions and terminology
In the previous chapter we have already invoked the concept of matrices.
However before going further we will need to establish a framework for
them, and some of their basic properties.
Definition of a matrix
A matrix is a rectangular array whose entries are of the same type.
An m × n matrix is one which has m rows and n columns. The numbers
m and n are referred to as the dimensons of the matrix.
The collection of all m × n matrices of real numbers will be denoted
by Rm×n.
We will use MATLAB convention in which the (i , j)th entry of the matrix
A (the entry in row i and column j) is denoted by A(i , j). Also we will
write the i th row as A(i , :), and the jth column as A(:, j).
Linear Algebra Module I: Linear Systems Summer Term 2021 30 / 75
Matrices – Definitions and terminology
We need to make precise what it means for two matrices to be equal.
Definition
Two matrices A and B are equal if A(i , j) = B(i , j) for all i , j .
Note that this equality forces A and B to have the same dimensions,
because if they had different dimensions, there would have to be a choice
of indices (i , j) for which one side of the equation exists, but the other
does not.
Thus, equality can be reformulated as saying: A and B have the same
dimensions, and the same entry in each place.
Linear Algebra Module I: Linear Systems Summer Term 2021 31 / 75
Matrices – Definitions and terminology
We need to make precise what it means for two matrices to be equal.
Definition
Two matrices A and B are equal if A(i , j) = B(i , j) for all i , j .
Note that this equality forces A and B to have the same dimensions,
because if they had different dimensions, there would have to be a choice
of indices (i , j) for which one side of the equation exists, but the other
does not.
Thus, equality can be reformulated as saying: A and B have the same
dimensions, and the same entry in each place.
Linear Algebra Module I: Linear Systems Summer Term 2021 31 / 75
Matrices – Definitions and terminology
We need to make precise what it means for two matrices to be equal.
Definition
Two matrices A and B are equal if A(i , j) = B(i , j) for all i , j .
Note that this equality forces A and B to have the same dimensions,
because if they had different dimensions, there would have to be a choice
of indices (i , j) for which one side of the equation exists, but the other
does not.
Thus, equality can be reformulated as saying: A and B have the same
dimensions, and the same entry in each place.
Linear Algebra Module I: Linear Systems Summer Term 2021 31 / 75
Matrices – Definitions and terminology
We need to make precise what it means for two matrices to be equal.
Definition
Two matrices A and B are equal if A(i , j) = B(i , j) for all i , j .
Note that this equality forces A and B to have the same dimensions,
because if they had different dimensions, there would have to be a choice
of indices (i , j) for which one side of the equation exists, but the other
does not.
Thus, equality can be reformulated as saying: A and B have the same
dimensions, and the same entry in each place.
Linear Algebra Module I: Linear Systems Summer Term 2021 31 / 75
Matrices – Definitions and terminology
In this course we will only be concerned with finite matrices; those with
finitely many rows and columns.
Note that in order to precisely specify what a given matrix A is, it suffices
to know
i) its dimensions m and n and
ii) the value of the entry A(i , j) for each 1 ≤ i ≤ m and 1 ≤ j ≤ n.
When working with a fixed system of numbers such as R (real numbers) or
C (complex numbers), the elements of that number system in linear
algebra are referred to as scalars.
Linear Algebra Module I: Linear Systems Summer Term 2021 32 / 75
Matrices – Definitions and terminology
In this course we will only be concerned with finite matrices; those with
finitely many rows and columns.
Note that in order to precisely specify what a given matrix A is, it suffices
to know
i) its dimensions m and n and
ii) the value of the entry A(i , j) for each 1 ≤ i ≤ m and 1 ≤ j ≤ n.
When working with a fixed system of numbers such as R (real numbers) or
C (complex numbers), the elements of that number system in linear
algebra are referred to as scalars.
Linear Algebra Module I: Linear Systems Summer Term 2021 32 / 75
Matrices – Definitions and terminology
In this course we will only be concerned with finite matrices; those with
finitely many rows and columns.
Note that in order to precisely specify what a given matrix A is, it suffices
to know
i) its dimensions m and n and
ii) the value of the entry A(i , j) for each 1 ≤ i ≤ m and 1 ≤ j ≤ n.
When working with a fixed system of numbers such as R (real numbers) or
C (complex numbers), the elements of that number system in linear
algebra are referred to as scalars.
Linear Algebra Module I: Linear Systems Summer Term 2021 32 / 75
Matrices – Definitions and terminology
In this course we will only be concerned with finite matrices; those with
finitely many rows and columns.
Note that in order to precisely specify what a given matrix A is, it suffices
to know
i) its dimensions m and n and
ii) the value of the entry A(i , j) for each 1 ≤ i ≤ m and 1 ≤ j ≤ n.
When working with a fixed system of numbers such as R (real numbers) or
C (complex numbers), the elements of that number system in linear
algebra are referred to as scalars.
Linear Algebra Module I: Linear Systems Summer Term 2021 32 / 75
Matrices – Definitions and terminology
In this course we will only be concerned with finite matrices; those with
finitely many rows and columns.
Note that in order to precisely specify what a given matrix A is, it suffices
to know
i) its dimensions m and n and
ii) the value of the entry A(i , j) for each 1 ≤ i ≤ m and 1 ≤ j ≤ n.
When working with a fixed system of numbers such as R (real numbers) or
C (complex numbers), the elements of that number system in linear
algebra are referred to as scalars.
Linear Algebra Module I: Linear Systems Summer Term 2021 32 / 75
Matrix Operations – Definition
There are three types of matrix operations.
Matrix Addition
If A and B have the same dimensions, then the sum A + B is the matrix
whose entries are given by
(A + B)(i , j) := A(i , j) + B(i , j)
Note that the dimensions of A + B are the same as those of (both) A
and B. If A and B do not have the same dimensions, then the sum A + B
is not defined; in other words, it doesn’t exist.
Linear Algebra Module I: Linear Systems Summer Term 2021 33 / 75
Matrix Operations – Definition
There are three types of matrix operations.
Matrix Addition
If A and B have the same dimensions, then the sum A + B is the matrix
whose entries are given by
(A + B)(i , j) := A(i , j) + B(i , j)
Note that the dimensions of A + B are the same as those of (both) A
and B. If A and B do not have the same dimensions, then the sum A + B
is not defined; in other words, it doesn’t exist.
Linear Algebra Module I: Linear Systems Summer Term 2021 33 / 75
Matrix Operations – Definition
There are three types of matrix operations.
Matrix Addition
If A and B have the same dimensions, then the sum A + B is the matrix
whose entries are given by
(A + B)(i , j) := A(i , j) + B(i , j)
Note that the dimensions of A + B are the same as those of (both) A
and B. If A and B do not have the same dimensions, then the sum A + B
is not defined; in other words, it doesn’t exist.
Linear Algebra Module I: Linear Systems Summer Term 2021 33 / 75
Matrix Operations – Definition
There are three types of matrix operations.
Matrix Addition
If A and B have the same dimensions, then the sum A + B is the matrix
whose entries are given by
(A + B)(i , j) := A(i , j) + B(i , j)
Note that the dimensions of A + B are the same as those of (both) A
and B. If A and B do not have the same dimensions, then the sum A + B
is not defined; in other words, it doesn’t exist.
Linear Algebra Module I: Linear Systems Summer Term 2021 33 / 75
Matrix Operations – Definition
Scalar Multiplication
If A is a matrix and α a scalar, the scalar product of α with A is the
matrix αA whose entries are given by
(αA)(i , j) := (α)A(i , j)
There are no restrictions on the dimensions of A in order for this
operation to be defined; the scalar product always exists.
Linear Algebra Module I: Linear Systems Summer Term 2021 34 / 75
Matrix Operations – Definition
Scalar Multiplication
If A is a matrix and α a scalar, the scalar product of α with A is the
matrix αA whose entries are given by
(αA)(i , j) := (α)A(i , j)
There are no restrictions on the dimensions of A in order for this
operation to be defined; the scalar product always exists.
Linear Algebra Module I: Linear Systems Summer Term 2021 34 / 75
Matrix Operations – Definition
Scalar Multiplication
If A is a matrix and α a scalar, the scalar product of α with A is the
matrix αA whose entries are given by
(αA)(i , j) := (α)A(i , j)
There are no restrictions on the dimensions of A in order for this
operation to be defined; the scalar product always exists.
Linear Algebra Module I: Linear Systems Summer Term 2021 34 / 75
Matrix Operations – Definition
Scalar Multiplication
If A is a matrix and α a scalar, the scalar product of α with A is the
matrix αA whose entries are given by
(αA)(i , j) := (α)A(i , j)
There are no restrictions on the dimensions of A in order for this
operation to be defined; the scalar product always exists.
Linear Algebra Module I: Linear Systems Summer Term 2021 34 / 75
Matrix Operations – Definition
Matrix Multiplication
If A is m × n and B is p × q, then in order for the product A ∗ B to be
defined, we require that n = p; this condition is expressed by saying that
the internal dimensions agree. In this case the product A ∗ B is the
matrix whose entries are given by
(A ∗ B)(i , k) :=
n∑
j=1
A(i , j)B(j , k)
The dimensions of the product are m × q. If the internal dimensions of A
and B do not agree, then the product A ∗ B doesn’t exist.
It is important to note that matrix multiplication can be performed
whenever the sum of products appearing on the right-hand side of the
defining equation makes sense algebraically; in other words, for more than
just numerical matrices. This fact will come into play later on.
Linear Algebra Module I: Linear Systems Summer Term 2021 35 / 75
Matrix Operations – Definition
Matrix Multiplication
If A is m × n and B is p × q, then in order for the product A ∗ B to be
defined, we require that n = p; this condition is expressed by saying that
the internal dimensions agree. In this case the product A ∗ B is the
matrix whose entries are given by
(A ∗ B)(i , k) :=
n∑
j=1
A(i , j)B(j , k)
The dimensions of the product are m × q. If the internal dimensions of A
and B do not agree, then the product A ∗ B doesn’t exist.
It is important to note that matrix multiplication can be performed
whenever the sum of products appearing on the right-hand side of the
defining equation makes sense algebraically; in other words, for more than
just numerical matrices. This fact will come into play later on.
Linear Algebra Module I: Linear Systems Summer Term 2021 35 / 75
Matrix Operations – Definition
Matrix Multiplication
If A is m × n and B is p × q, then in order for the product A ∗ B to be
defined, we require that n = p; this condition is expressed by saying that
the internal dimensions agree. In this case the product A ∗ B is the
matrix whose entries are given by
(A ∗ B)(i , k) :=
n∑
j=1
A(i , j)B(j , k)
The dimensions of the product are m × q. If the internal dimensions of A
and B do not agree, then the product A ∗ B doesn’t exist.
It is important to note that matrix multiplication can be performed
whenever the sum of products appearing on the right-hand side of the
defining equation makes sense algebraically; in other words, for more than
just numerical matrices. This fact will come into play later on.
Linear Algebra Module I: Linear Systems Summer Term 2021 35 / 75
Matrix Operations – Definition
Matrix Multiplication
If A is m × n and B is p × q, then in order for the product A ∗ B to be
defined, we require that n = p; this condition is expressed by saying that
the internal dimensions agree. In this case the product A ∗ B is the
matrix whose entries are given by
(A ∗ B)(i , k) :=
n∑
j=1
A(i , j)B(j , k)
The dimensions of the product are m × q. If the internal dimensions of A
and B do not agree, then the product A ∗ B doesn’t exist.
It is important to note that matrix multiplication can be performed
whenever the sum of products appearing on the right-hand side of the
defining equation makes sense algebraically; in other words, for more than
just numerical matrices. This fact will come into play later on.
Linear Algebra Module I: Linear Systems Summer Term 2021 35 / 75
Matrix Operations – Definition
Matrix Multiplication
If A is m × n and B is p × q, then in order for the product A ∗ B to be
defined, we require that n = p; this condition is expressed by saying that
the internal dimensions agree. In this case the product A ∗ B is the
matrix whose entries are given by
(A ∗ B)(i , k) :=
n∑
j=1
A(i , j)B(j , k)
The dimensions of the product are m × q. If the internal dimensions of A
and B do not agree, then the product A ∗ B doesn’t exist.
It is important to note that matrix multiplication can be performed
whenever the sum of products appearing on the right-hand side of the
defining equation makes sense algebraically; in other words, for more than
just numerical matrices. This fact will come into play later on.
Linear Algebra Module I: Linear Systems Summer Term 2021 35 / 75
Matrix Operations – Examples
Examples
Suppose A =
[
2 3
−1 5
]
and B =
[
4 −1
2 −2
]
. Then A + B is well-defined
because the two matrices have the same dimension, and is computed by
adding entrywise:
A + B =
[
(2 + 4) (3 + (−1))
(−1 + 2) (5 + (−2))
]
=
[
6 2
1 3
]
Linear Algebra Module I: Linear Systems Summer Term 2021 36 / 75
Matrix Operations – Examples
Examples
Suppose A =
[
2 3
−1 5
]
and B =
[
4 −1
2 −2
]
. Then A + B is well-defined
because the two matrices have the same dimension, and is computed by
adding entrywise:
A + B =
[
(2 + 4) (3 + (−1))
(−1 + 2) (5 + (−2))
]
=
[
6 2
1 3
]
Linear Algebra Module I: Linear Systems Summer Term 2021 36 / 75
Matrix Operations – Examples
Examples
Suppose A =
[
2 3
−1 5
]
and B =
[
4 −1
2 −2
]
. Then A + B is well-defined
because the two matrices have the same dimension, and is computed by
adding entrywise:
A + B =
[
(2 + 4) (3 + (−1))
(−1 + 2) (5 + (−2))
]
=
[
6 2
1 3
]
Linear Algebra Module I: Linear Systems Summer Term 2021 36 / 75
Matrix Operations – Examples
Examples
Suppose A and B are as in the previous example. Then the matrix product
A ∗ B is well-defined because the internal dimensions agree (the number of
columns of A equals the number of rows of B), with the (i , j)th entry of
the product computed by multiplying the i th row or A with the jth column
of B. The answer is
A ∗ B =
[
(2 ∗ 4 + 3 ∗ 2) (2 ∗ (−1) + 3 ∗ (−2))
((−1) ∗ 4 + 5 ∗ 2) ((−1) ∗ (−1) + 5 ∗ (−2)
]
=
[
14 −8
6 −9
]
Linear Algebra Module I: Linear Systems Summer Term 2021 37 / 75
Matrix Operations – Examples
Examples
Suppose A and B are as in the previous example. Then the matrix product
A ∗ B is well-defined because the internal dimensions agree (the number of
columns of A equals the number of rows of B), with the (i , j)th entry of
the product computed by multiplying the i th row or A with the jth column
of B. The answer is
A ∗ B =
[
(2 ∗ 4 + 3 ∗ 2) (2 ∗ (−1) + 3 ∗ (−2))
((−1) ∗ 4 + 5 ∗ 2) ((−1) ∗ (−1) + 5 ∗ (−2)
]
=
[
14 −8
6 −9
]
Linear Algebra Module I: Linear Systems Summer Term 2021 37 / 75
Matrix Operations – Examples
Examples
Suppose A and B are as in the previous example. Then the matrix product
A ∗ B is well-defined because the internal dimensions agree (the number of
columns of A equals the number of rows of B), with the (i , j)th entry of
the product computed by multiplying the i th row or A with the jth column
of B. The answer is
A ∗ B =
[
(2 ∗ 4 + 3 ∗ 2) (2 ∗ (−1) + 3 ∗ (−2))
((−1) ∗ 4 + 5 ∗ 2) ((−1) ∗ (−1) + 5 ∗ (−2)
]
=
[
14 −8
6 −9
]
Linear Algebra Module I: Linear Systems Summer Term 2021 37 / 75
Matrix Operations – Examples
Examples
Suppose A is as above. Then the scalar product αA is well-defined for any
scalar α, because there are no restrictions on the scalar product existing.
In particular, taking α = 5, the scalar product 5A is
5A =
[
5 ∗ 2 5 ∗ 3
5 ∗ (−1) 5 ∗ 5
]
=
[
10 15
−5 25
]
Linear Algebra Module I: Linear Systems Summer Term 2021 38 / 75
Matrix Operations – Examples
Examples
Suppose A is as above. Then the scalar product αA is well-defined for any
scalar α, because there are no restrictions on the scalar product existing.
In particular, taking α = 5, the scalar product 5A is
5A =
[
5 ∗ 2 5 ∗ 3
5 ∗ (−1) 5 ∗ 5
]
=
[
10 15
−5 25
]
Linear Algebra Module I: Linear Systems Summer Term 2021 38 / 75
Matrix Operations – Examples
Examples
Suppose A is as above. Then the scalar product αA is well-defined for any
scalar α, because there are no restrictions on the scalar product existing.
In particular, taking α = 5, the scalar product 5A is
5A =
[
5 ∗ 2 5 ∗ 3
5 ∗ (−1) 5 ∗ 5
]
=
[
10 15
−5 25
]
Linear Algebra Module I: Linear Systems Summer Term 2021 38 / 75
Matrix Operations – Properties
The fundamental properties of these three operations are summarized in
the following theorem.
Theorem – Properties of matrix operations
(3.2.1) A + B = B + A (commutativity of addition);
(3.2.2) A + (B + C) = (A + B) + C (associativity of addition);
(3.2.3) α(A + B) = αA + αB (scalar multiplication distributes over
matrix addition);
(3.2.4) A ∗ (B + C) = A ∗ B + A ∗ C (matrix multiplication
left-distributes over matrix addition);
(3.2.5) (A + B) ∗ C = A ∗ C + B ∗ C (matrix multiplication
right-distributes over matrix addition);
(3.2.6) (αβ)A = α(βA) (associativity of scalar multiplication);
(3.2.7) A ∗ (B ∗ C) = (A ∗ B) ∗ C (associativity of matrix
multiplication).
Linear Algebra Module I: Linear Systems Summer Term 2021 39 / 75
Matrix Operations – Properties
The fundamental properties of these three operations are summarized in
the following theorem.
Theorem – Properties of matrix operations
(3.2.1) A + B = B + A (commutativity of addition);
(3.2.2) A + (B + C) = (A + B) + C (associativity of addition);
(3.2.3) α(A + B) = αA + αB (scalar multiplication distributes over
matrix addition);
(3.2.4) A ∗ (B + C) = A ∗ B + A ∗ C (matrix multiplication
left-distributes over matrix addition);
(3.2.5) (A + B) ∗ C = A ∗ C + B ∗ C (matrix multiplication
right-distributes over matrix addition);
(3.2.6) (αβ)A = α(βA) (associativity of scalar multiplication);
(3.2.7) A ∗ (B ∗ C) = (A ∗ B) ∗ C (associativity of matrix
multiplication).
Linear Algebra Module I: Linear Systems Summer Term 2021 39 / 75
Matrix Operations – Properties
The fundamental properties of these three operations are summarized in
the following theorem.
Theorem – Properties of matrix operations
(3.2.1) A + B = B + A (commutativity of addition);
(3.2.2) A + (B + C) = (A + B) + C (associativity of addition);
(3.2.3) α(A + B) = αA + αB (scalar multiplication distributes over
matrix addition);
(3.2.4) A ∗ (B + C) = A ∗ B + A ∗ C (matrix multiplication
left-distributes over matrix addition);
(3.2.5) (A + B) ∗ C = A ∗ C + B ∗ C (matrix multiplication
right-distributes over matrix addition);
(3.2.6) (αβ)A = α(βA) (associativity of scalar multiplication);
(3.2.7) A ∗ (B ∗ C) = (A ∗ B) ∗ C (associativity of matrix
multiplication).
Linear Algebra Module I: Linear Systems Summer Term 2021 39 / 75
Matrix Operations – Properties
The fundamental properties of these three operations are summarized in
the following theorem.
Theorem – Properties of matrix operations
(3.2.1) A + B = B + A (commutativity of addition);
(3.2.2) A + (B + C) = (A + B) + C (associativity of addition);
(3.2.3) α(A + B) = αA + αB (scalar multiplication distributes over
matrix addition);
(3.2.4) A ∗ (B + C) = A ∗ B + A ∗ C (matrix multiplication
left-distributes over matrix addition);
(3.2.5) (A + B) ∗ C = A ∗ C + B ∗ C (matrix multiplication
right-distributes over matrix addition);
(3.2.6) (αβ)A = α(βA) (associativity of scalar multiplication);
(3.2.7) A ∗ (B ∗ C) = (A ∗ B) ∗ C (associativity of matrix
multiplication).
Linear Algebra Module I: Linear Systems Summer Term 2021 39 / 75
Matrix Operations – Properties
The fundamental properties of these three operations are summarized in
the following theorem.
Theorem – Properties of matrix operations
(3.2.1) A + B = B + A (commutativity of addition);
(3.2.2) A + (B + C) = (A + B) + C (associativity of addition);
(3.2.3) α(A + B) = αA + αB (scalar multiplication distributes over
matrix addition);
(3.2.4) A ∗ (B + C) = A ∗ B + A ∗ C (matrix multiplication
left-distributes over matrix addition);
(3.2.5) (A + B) ∗ C = A ∗ C + B ∗ C (matrix multiplication
right-distributes over matrix addition);
(3.2.6) (αβ)A = α(βA) (associativity of scalar multiplication);
(3.2.7) A ∗ (B ∗ C) = (A ∗ B) ∗ C (associativity of matrix
multiplication).
Linear Algebra Module I: Linear Systems Summer Term 2021 39 / 75
Matrix Operations – Properties
The fundamental properties of these three operations are summarized in
the following theorem.
Theorem – Properties of matrix operations
(3.2.1) A + B = B + A (commutativity of addition);
(3.2.2) A + (B + C) = (A + B) + C (associativity of addition);
(3.2.3) α(A + B) = αA + αB (scalar multiplication distributes over
matrix addition);
(3.2.4) A ∗ (B + C) = A ∗ B + A ∗ C (matrix multiplication
left-distributes over matrix addition);
(3.2.5) (A + B) ∗ C = A ∗ C + B ∗ C (matrix multiplication
right-distributes over matrix addition);
(3.2.6) (αβ)A = α(βA) (associativity of scalar multiplication);
(3.2.7) A ∗ (B ∗ C) = (A ∗ B) ∗ C (associativity of matrix
multiplication).
Linear Algebra Module I: Linear Systems Summer Term 2021 39 / 75
Matrix Operations – Properties
The fundamental properties of these three operations are summarized in
the following theorem.
Theorem – Properties of matrix operations
(3.2.1) A + B = B + A (commutativity of addition);
(3.2.2) A + (B + C) = (A + B) + C (associativity of addition);
(3.2.3) α(A + B) = αA + αB (scalar multiplication distributes over
matrix addition);
(3.2.4) A ∗ (B + C) = A ∗ B + A ∗ C (matrix multiplication
left-distributes over matrix addition);
(3.2.5) (A + B) ∗ C = A ∗ C + B ∗ C (matrix multiplication
right-distributes over matrix addition);
(3.2.6) (αβ)A = α(βA) (associativity of scalar multiplication);
(3.2.7) A ∗ (B ∗ C) = (A ∗ B) ∗ C (associativity of matrix
multiplication).
Linear Algebra Module I: Linear Systems Summer Term 2021 39 / 75
Matrix Operations – Properties
The fundamental properties of these three operations are summarized in
the following theorem.
Theorem – Properties of matrix operations
(3.2.1) A + B = B + A (commutativity of addition);
(3.2.2) A + (B + C) = (A + B) + C (associativity of addition);
(3.2.3) α(A + B) = αA + αB (scalar multiplication distributes over
matrix addition);
(3.2.4) A ∗ (B + C) = A ∗ B + A ∗ C (matrix multiplication
left-distributes over matrix addition);
(3.2.5) (A + B) ∗ C = A ∗ C + B ∗ C (matrix multiplication
right-distributes over matrix addition);
(3.2.6) (αβ)A = α(βA) (associativity of scalar multiplication);
(3.2.7) A ∗ (B ∗ C) = (A ∗ B) ∗ C (associativity of matrix
multiplication).
Linear Algebra Module I: Linear Systems Summer Term 2021 39 / 75
Additional Matrix Operations – Transpose
We introduce a few more fundamental matrix operations.
Transpose
The transpose of the matrix A, written as AT , is always defined, and
given by (
AT
)
(i , j) := A(j , i)
The way this operation relates to the algebraic operations defined above is
described by the next theorem.
Theorem
Let A and B be matrices. Then
(A + B)T = AT + BT ;
(A ∗ B)T = BT ∗ AT ;(
AT
)T
= A.
Linear Algebra Module I: Linear Systems Summer Term 2021 40 / 75
Additional Matrix Operations – Transpose
We introduce a few more fundamental matrix operations.
Transpose
The transpose of the matrix A, written as AT , is always defined, and
given by
(
AT
)
(i , j) := A(j , i)
The way this operation relates to the algebraic operations defined above is
described by the next theorem.
Theorem
Let A and B be matrices. Then
(A + B)T = AT + BT ;
(A ∗ B)T = BT ∗ AT ;(
AT
)T
= A.
Linear Algebra Module I: Linear Systems Summer Term 2021 40 / 75
Additional Matrix Operations – Transpose
We introduce a few more fundamental matrix operations.
Transpose
The transpose of the matrix A, written as AT , is always defined, and
given by (
AT
)
(i , j) := A(j , i)
The way this operation relates to the algebraic operations defined above is
described by the next theorem.
Theorem
Let A and B be matrices. Then
(A + B)T = AT + BT ;
(A ∗ B)T = BT ∗ AT ;(
AT
)T
= A.
Linear Algebra Module I: Linear Systems Summer Term 2021 40 / 75
Additional Matrix Operations – Transpose
We introduce a few more fundamental matrix operations.
Transpose
The transpose of the matrix A, written as AT , is always defined, and
given by (
AT
)
(i , j) := A(j , i)
The way this operation relates to the algebraic operations defined above is
described by the next theorem.
Theorem
Let A and B be matrices. Then
(A + B)T = AT + BT ;
(A ∗ B)T = BT ∗ AT ;(
AT
)T
= A.
Linear Algebra Module I: Linear Systems Summer Term 2021 40 / 75
Additional Matrix Operations – Transpose
We introduce a few more fundamental matrix operations.
Transpose
The transpose of the matrix A, written as AT , is always defined, and
given by (
AT
)
(i , j) := A(j , i)
The way this operation relates to the algebraic operations defined above is
described by the next theorem.
Theorem
Let A and B be matrices. Then
(A + B)T = AT + BT ;
(A ∗ B)T = BT ∗ AT ;(
AT
)T
= A.
Linear Algebra Module I: Linear Systems Summer Term 2021 40 / 75
Additional Matrix Operations – Transpose
We introduce a few more fundamental matrix operations.
Transpose
The transpose of the matrix A, written as AT , is always defined, and
given by (
AT
)
(i , j) := A(j , i)
The way this operation relates to the algebraic operations defined above is
described by the next theorem.
Theorem
Let A and B be matrices. Then
(A + B)T = AT + BT ;
(A ∗ B)T = BT ∗ AT ;(
AT
)T
= A.
Linear Algebra Module I: Linear Systems Summer Term 2021 40 / 75
Additional Matrix Operations – Transpose
We introduce a few more fundamental matrix operations.
Transpose
The transpose of the matrix A, written as AT , is always defined, and
given by (
AT
)
(i , j) := A(j , i)
The way this operation relates to the algebraic operations defined above is
described by the next theorem.
Theorem
Let A and B be matrices. Then
(A + B)T = AT + BT ;
(A ∗ B)T = BT ∗ AT ;
(
AT
)T
= A.
Linear Algebra Module I: Linear Systems Summer Term 2021 40 / 75
Additional Matrix Operations – Transpose
We introduce a few more fundamental matrix operations.
Transpose
The transpose of the matrix A, written as AT , is always defined, and
given by (
AT
)
(i , j) := A(j , i)
The way this operation relates to the algebraic operations defined above is
described by the next theorem.
Theorem
Let A and B be matrices. Then
(A + B)T = AT + BT ;
(A ∗ B)T = BT ∗ AT ;(
AT
)T
= A.
Linear Algebra Module I: Linear Systems Summer Term 2021 40 / 75
Additional Matrix Operations – Concatenation
One can concatenate matrices.
Concatenation
If A is m × n and B is m × p, then the horizontal concatenation of A
and B is written as [
A B
]
;
it is the m × (n + p) matrix where A appears as the left-most m × n
block, and B appears as the right-most m × p block.
Similarly, if C is q × n, then the vertical concatenation of A and C is
written as [
A
C
]
;
It is the (m + q)× n matrix where A appears in the upper m × n block,
and C in the lower q × n block.
Linear Algebra Module I: Linear Systems Summer Term 2021 41 / 75
Additional Matrix Operations – Concatenation
One can concatenate matrices.
Concatenation
If A is m × n and B is m × p, then the horizontal concatenation of A
and B is written as
[
A B
]
;
it is the m × (n + p) matrix where A appears as the left-most m × n
block, and B appears as the right-most m × p block.
Similarly, if C is q × n, then the vertical concatenation of A and C is
written as [
A
C
]
;
It is the (m + q)× n matrix where A appears in the upper m × n block,
and C in the lower q × n block.
Linear Algebra Module I: Linear Systems Summer Term 2021 41 / 75
Additional Matrix Operations – Concatenation
One can concatenate matrices.
Concatenation
If A is m × n and B is m × p, then the horizontal concatenation of A
and B is written as [
A B
]
;
it is the m × (n + p) matrix where A appears as the left-most m × n
block, and B appears as the right-most m × p block.
Similarly, if C is q × n, then the vertical concatenation of A and C is
written as [
A
C
]
;
It is the (m + q)× n matrix where A appears in the upper m × n block,
and C in the lower q × n block.
Linear Algebra Module I: Linear Systems Summer Term 2021 41 / 75
Additional Matrix Operations – Concatenation
One can concatenate matrices.
Concatenation
If A is m × n and B is m × p, then the horizontal concatenation of A
and B is written as [
A B
]
;
it is the m × (n + p) matrix where A appears as the left-most m × n
block, and B appears as the right-most m × p block.
Similarly, if C is q × n, then the vertical concatenation of A and C is
written as [
A
C
]
;
It is the (m + q)× n matrix where A appears in the upper m × n block,
and C in the lower q × n block.
Linear Algebra Module I: Linear Systems Summer Term 2021 41 / 75
Additional Matrix Operations – Concatenation
One can concatenate matrices.
Concatenation
If A is m × n and B is m × p, then the horizontal concatenation of A
and B is written as [
A B
]
;
it is the m × (n + p) matrix where A appears as the left-most m × n
block, and B appears as the right-most m × p block.
Similarly, if C is q × n, then the vertical concatenation of A and C is
written as
[
A
C
]
;
It is the (m + q)× n matrix where A appears in the upper m × n block,
and C in the lower q × n block.
Linear Algebra Module I: Linear Systems Summer Term 2021 41 / 75
Additional Matrix Operations – Concatenation
One can concatenate matrices.
Concatenation
If A is m × n and B is m × p, then the horizontal concatenation of A
and B is written as [
A B
]
;
it is the m × (n + p) matrix where A appears as the left-most m × n
block, and B appears as the right-most m × p block.
Similarly, if C is q × n, then the vertical concatenation of A and C is
written as [
A
C
]
;
It is the (m + q)× n matrix where A appears in the upper m × n block,
and C in the lower q × n block.
Linear Algebra Module I: Linear Systems Summer Term 2021 41 / 75
Additional Matrix Operations – Concatenation
Concatenation
Concatenation can be done multiple times. Any matrix A can be viewed as
the horizontal concatenation of its columns, and
the vertical concatenation of its rows.
Some Properties
Let A,B,C ,D denote matrices all with the same number of rows.
If the pairs A,C and B,D have the same number of columns as well,
then
[
A B
]
+
[
C D
]
=
[
(A + C) (B + D)
]
.
If E is a p × q matrix where q equals the number of rows of A, then
E ∗
[
A B
]
=
[
E ∗ A E ∗ B
]
.
With respect to transpose, one has
[
A B
]T
=
[
AT
BT
]
.
Linear Algebra Module I: Linear Systems Summer Term 2021 42 / 75
Additional Matrix Operations – Concatenation
Concatenation
Concatenation can be done multiple times. Any matrix A can be viewed as
the horizontal concatenation of its columns, and
the vertical concatenation of its rows.
Some Properties
Let A,B,C ,D denote matrices all with the same number of rows.
If the pairs A,C and B,D have the same number of columns as well,
then
[
A B
]
+
[
C D
]
=
[
(A + C) (B + D)
]
.
If E is a p × q matrix where q equals the number of rows of A, then
E ∗
[
A B
]
=
[
E ∗ A E ∗ B
]
.
With respect to transpose, one has
[
A B
]T
=
[
AT
BT
]
.
Linear Algebra Module I: Linear Systems Summer Term 2021 42 / 75
Additional Matrix Operations – Concatenation
Concatenation
Concatenation can be done multiple times. Any matrix A can be viewed as
the horizontal concatenation of its columns, and
the vertical concatenation of its rows.
Some Properties
Let A,B,C ,D denote matrices all with the same number of rows.
If the pairs A,C and B,D have the same number of columns as well,
then
[
A B
]
+
[
C D
]
=
[
(A + C) (B + D)
]
.
If E is a p × q matrix where q equals the number of rows of A, then
E ∗
[
A B
]
=
[
E ∗ A E ∗ B
]
.
With respect to transpose, one has
[
A B
]T
=
[
AT
BT
]
.
Linear Algebra Module I: Linear Systems Summer Term 2021 42 / 75
Additional Matrix Operations – Concatenation
Concatenation
Concatenation can be done multiple times. Any matrix A can be viewed as
the horizontal concatenation of its columns, and
the vertical concatenation of its rows.
Some Properties
Let A,B,C ,D denote matrices all with the same number of rows.
If the pairs A,C and B,D have the same number of columns as well,
then
[
A B
]
+
[
C D
]
=
[
(A + C) (B + D)
]
.
If E is a p × q matrix where q equals the number of rows of A, then
E ∗
[
A B
]
=
[
E ∗ A E ∗ B
]
.
With respect to transpose, one has
[
A B
]T
=
[
AT
BT
]
.
Linear Algebra Module I: Linear Systems Summer Term 2021 42 / 75
Additional Matrix Operations – Concatenation
Concatenation
Concatenation can be done multiple times. Any matrix A can be viewed as
the horizontal concatenation of its columns, and
the vertical concatenation of its rows.
Some Properties
Let A,B,C ,D denote matrices all with the same number of rows.
If the pairs A,C and B,D have the same number of columns as well,
then
[
A B
]
+
[
C D
]
=
[
(A + C) (B + D)
]
.
If E is a p × q matrix where q equals the number of rows of A, then
E ∗
[
A B
]
=
[
E ∗ A E ∗ B
]
.
With respect to transpose, one has
[
A B
]T
=
[
AT
BT
]
.
Linear Algebra Module I: Linear Systems Summer Term 2021 42 / 75
Additional Matrix Operations – Concatenation
Concatenation
Concatenation can be done multiple times. Any matrix A can be viewed as
the horizontal concatenation of its columns, and
the vertical concatenation of its rows.
Some Properties
Let A,B,C ,D denote matrices all with the same number of rows.
If the pairs A,C and B,D have the same number of columns as well,
then
[
A B
]
+
[
C D
]
=
[
(A + C) (B + D)
]
.
If E is a p × q matrix where q equals the number of rows of A, then
E ∗
[
A B
]
=
[
E ∗ A E ∗ B
]
.
With respect to transpose, one has
[
A B
]T
=
[
AT
BT
]
.
Linear Algebra Module I: Linear Systems Summer Term 2021 42 / 75
Additional Matrix Operations – Concatenation
Concatenation
Concatenation can be done multiple times. Any matrix A can be viewed as
the horizontal concatenation of its columns, and
the vertical concatenation of its rows.
Some Properties
Let A,B,C ,D denote matrices all with the same number of rows.
If the pairs A,C and B,D have the same number of columns as well,
then
[
A B
]
+
[
C D
]
=
[
(A + C) (B + D)
]
.
If E is a p × q matrix where q equals the number of rows of A, then
E ∗
[
A B
]
=
[
E ∗ A E ∗ B
]
.
With respect to transpose, one has
[
A B
]T
=
[
AT
BT
]
.
Linear Algebra Module I: Linear Systems Summer Term 2021 42 / 75
Additional Matrix Operations – Concatenation
Concatenation
Concatenation can be done multiple times. Any matrix A can be viewed as
the horizontal concatenation of its columns, and
the vertical concatenation of its rows.
Some Properties
Let A,B,C ,D denote matrices all with the same number of rows.
If the pairs A,C and B,D have the same number of columns as well,
then
[
A B
]
+
[
C D
]
=
[
(A + C) (B + D)
]
.
If E is a p × q matrix where q equals the number of rows of A, then
E ∗
[
A B
]
=
[
E ∗ A E ∗ B
]
.
With respect to transpose, one has
[
A B
]T
=
[
AT
BT
]
.
Linear Algebra Module I: Linear Systems Summer Term 2021 42 / 75
Matrix Equations
Vectors
A matrix with one row is called a row vector , and if it has one column a
column vector . The term vector , for now, will refer to a column vector.
Linear Algebra Module I: Linear Systems Summer Term 2021 43 / 75
Matrix Equations
Vectors
A matrix with one row is called a row vector , and if it has one column a
column vector . The term vector , for now, will refer to a column vector.
Linear Algebra Module I: Linear Systems Summer Term 2021 43 / 75
Matrix Equations
Matrix equations
Matrices and vectors can be used to rewrite systems of equations as a
single equation. First, notice that the system appearing in (1) can be
expressed as the single vector equation.
a11x1 + a12x2 + . . . + a1nxn
a21x1 + a22x2 + . . . + a2nxn
…
… . . .
…
am1x1 + am2x2 + . . . + amnxn
=
b1
b2
…
bm
(2)
The vector on the left of (2) consists of entries which are linear
homogeneous functions in the variables x1, x2, . . . , xn.
A solution to this vector equation will be exactly what it was before; an
assignment of values to the variables x1, x2, . . . , xn which make the
equation true.
Linear Algebra Module I: Linear Systems Summer Term 2021 44 / 75
Matrix Equations
Matrix equations
Matrices and vectors can be used to rewrite systems of equations as a
single equation. First, notice that the system appearing in (1) can be
expressed as the single vector equation.
a11x1 + a12x2 + . . . + a1nxn
a21x1 + a22x2 + . . . + a2nxn
…
… . . .
…
am1x1 + am2x2 + . . . + amnxn
=
b1
b2
…
bm
(2)
The vector on the left of (2) consists of entries which are linear
homogeneous functions in the variables x1, x2, . . . , xn.
A solution to this vector equation will be exactly what it was before; an
assignment of values to the variables x1, x2, . . . , xn which make the
equation true.
Linear Algebra Module I: Linear Systems Summer Term 2021 44 / 75
Matrix Equations
Matrix equations
Matrices and vectors can be used to rewrite systems of equations as a
single equation. First, notice that the system appearing in (1) can be
expressed as the single vector equation.
a11x1 + a12x2 + . . . + a1nxn
a21x1 + a22x2 + . . . + a2nxn
…
… . . .
…
am1x1 + am2x2 + . . . + amnxn
=
b1
b2
…
bm
(2)
The vector on the left of (2) consists of entries which are linear
homogeneous functions in the variables x1, x2, . . . , xn.
A solution to this vector equation will be exactly what it was before; an
assignment of values to the variables x1, x2, . . . , xn which make the
equation true.
Linear Algebra Module I: Linear Systems Summer Term 2021 44 / 75
Matrix Equations
Matrix equations
Matrices and vectors can be used to rewrite systems of equations as a
single equation. First, notice that the system appearing in (1) can be
expressed as the single vector equation.
a11x1 + a12x2 + . . . + a1nxn
a21x1 + a22x2 + . . . + a2nxn
…
… . . .
…
am1x1 + am2x2 + . . . + amnxn
=
b1
b2
…
bm
(2)
The vector on the left of (2) consists of entries which are linear
homogeneous functions in the variables x1, x2, . . . , xn.
A solution to this vector equation will be exactly what it was before; an
assignment of values to the variables x1, x2, . . . , xn which make the
equation true.
Linear Algebra Module I: Linear Systems Summer Term 2021 44 / 75
Matrix Equations
Matrix equations
Matrices and vectors can be used to rewrite systems of equations as a
single equation. First, notice that the system appearing in (1) can be
expressed as the single vector equation.
a11x1 + a12x2 + . . . + a1nxn
a21x1 + a22x2 + . . . + a2nxn
…
… . . .
…
am1x1 + am2x2 + . . . + amnxn
=
b1
b2
…
bm
(2)
The vector on the left of (2) consists of entries which are linear
homogeneous functions in the variables x1, x2, . . . , xn.
A solution to this vector equation will be exactly what it was before; an
assignment of values to the variables x1, x2, . . . , xn which make the
equation true.
Linear Algebra Module I: Linear Systems Summer Term 2021 44 / 75
Matrix Equations
Matrix Equations
The LHS of (2) can be written as a sum of its components, where the xi
component is gotten by setting all of the other variables to zero. The
result is
a11x1
a21x1
…
am1x1
+
a12x2
a22x2
…
am2x2
+ · · ·+
a1nxn
a2nxn
…
amnxn
=
b1
b2
…
bm
(3)
Linear Algebra Module I: Linear Systems Summer Term 2021 45 / 75
Matrix Equations
Matrix Equations
The LHS of (2) can be written as a sum of its components, where the xi
component is gotten by setting all of the other variables to zero. The
result is
a11x1
a21x1
…
am1x1
+
a12x2
a22x2
…
am2x2
+ · · ·+
a1nxn
a2nxn
…
amnxn
=
b1
b2
…
bm
(3)
Linear Algebra Module I: Linear Systems Summer Term 2021 45 / 75
Matrix Equations
Matrix Equations
The LHS of (2) can be written as a sum of its components, where the xi
component is gotten by setting all of the other variables to zero. The
result is
a11x1
a21x1
…
am1x1
+
a12x2
a22x2
…
am2x2
+ · · ·+
a1nxn
a2nxn
…
amnxn
=
b1
b2
…
bm
(3)
Linear Algebra Module I: Linear Systems Summer Term 2021 45 / 75
Matrix Equations
Matrix Equations
We see that the i th component, which involves only xi , can be factored as
a scalar product
a1i xi
a2i xi
…
ami xi
= xi
a1i
a2i
…
ami
Using this, the vector equation (3) may be rewritten as
x1
a11
a21
…
am1
+ x2
a12
a22
…
am2
+ · · ·+ xn
a1n
a2n
…
amn
=
b1
b2
…
bm
(4)
Linear Algebra Module I: Linear Systems Summer Term 2021 46 / 75
Matrix Equations
Matrix Equations
We see that the i th component, which involves only xi , can be factored as
a scalar product
a1i xi
a2i xi
…
ami xi
= xi
a1i
a2i
…
ami
Using this, the vector equation (3) may be rewritten as
x1
a11
a21
…
am1
+ x2
a12
a22
…
am2
+ · · ·+ xn
a1n
a2n
…
amn
=
b1
b2
…
bm
(4)
Linear Algebra Module I: Linear Systems Summer Term 2021 46 / 75
Matrix Equations
Matrix Equations
We see that the i th component, which involves only xi , can be factored as
a scalar product
a1i xi
a2i xi
…
ami xi
= xi
a1i
a2i
…
ami
Using this, the vector equation (3) may be rewritten as
x1
a11
a21
…
am1
+ x2
a12
a22
…
am2
+ · · ·+ xn
a1n
a2n
…
amn
=
b1
b2
…
bm
(4)
Linear Algebra Module I: Linear Systems Summer Term 2021 46 / 75
Matrix Equations
Matrix Equations
We see that the i th component, which involves only xi , can be factored as
a scalar product
a1i xi
a2i xi
…
ami xi
= xi
a1i
a2i
…
ami
Using this, the vector equation (3) may be rewritten as
x1
a11
a21
…
am1
+ x2
a12
a22
…
am2
+ · · ·+ xn
a1n
a2n
…
amn
=
b1
b2
…
bm
(4)
Linear Algebra Module I: Linear Systems Summer Term 2021 46 / 75
Matrix Equations
Matrix Equations
We see that the i th component, which involves only xi , can be factored as
a scalar product
a1i xi
a2i xi
…
ami xi
= xi
a1i
a2i
…
ami
Using this, the vector equation (3) may be rewritten as
x1
a11
a21
…
am1
+ x2
a12
a22
…
am2
+ · · ·+ xn
a1n
a2n
…
amn
=
b1
b2
…
bm
(4)
Linear Algebra Module I: Linear Systems Summer Term 2021 46 / 75
Matrix Equations
The left-hand side of this last equation leads us to one of the central
constructions in all of Linear Algebra.
Linear Combinations
Given a collection of vectors {v1, v2, . . . , vn}, a linear combination of
these vectors is a sum of the form
α1v1 + α2v2 + · · ·+ αnvn
where the coefficients αi are scalars.
In other words, it is a sum of scalar multiples of the vectors
v1, v2, . . . vn.
The expression on the left of (4) is a linear combination of sorts, but
where the coefficients are scalar-valued variables rather than actual scalars.
So for any assignment of values to the variables x1, x2, . . . xn we get an
actual linear combination.
Linear Algebra Module I: Linear Systems Summer Term 2021 47 / 75
Matrix Equations
The left-hand side of this last equation leads us to one of the central
constructions in all of Linear Algebra.
Linear Combinations
Given a collection of vectors {v1, v2, . . . , vn}, a linear combination of
these vectors is a sum of the form
α1v1 + α2v2 + · · ·+ αnvn
where the coefficients αi are scalars.
In other words, it is a sum of scalar multiples of the vectors
v1, v2, . . . vn.
The expression on the left of (4) is a linear combination of sorts, but
where the coefficients are scalar-valued variables rather than actual scalars.
So for any assignment of values to the variables x1, x2, . . . xn we get an
actual linear combination.
Linear Algebra Module I: Linear Systems Summer Term 2021 47 / 75
Matrix Equations
The left-hand side of this last equation leads us to one of the central
constructions in all of Linear Algebra.
Linear Combinations
Given a collection of vectors {v1, v2, . . . , vn}, a linear combination of
these vectors is a sum of the form
α1v1 + α2v2 + · · ·+ αnvn
where the coefficients αi are scalars.
In other words, it is a sum of scalar multiples of the vectors
v1, v2, . . . vn.
The expression on the left of (4) is a linear combination of sorts, but
where the coefficients are scalar-valued variables rather than actual scalars.
So for any assignment of values to the variables x1, x2, . . . xn we get an
actual linear combination.
Linear Algebra Module I: Linear Systems Summer Term 2021 47 / 75
Matrix Equations
The left-hand side of this last equation leads us to one of the central
constructions in all of Linear Algebra.
Linear Combinations
Given a collection of vectors {v1, v2, . . . , vn}, a linear combination of
these vectors is a sum of the form
α1v1 + α2v2 + · · ·+ αnvn
where the coefficients αi are scalars.
In other words, it is a sum of scalar multiples of the vectors
v1, v2, . . . vn.
The expression on the left of (4) is a linear combination of sorts, but
where the coefficients are scalar-valued variables rather than actual scalars.
So for any assignment of values to the variables x1, x2, . . . xn we get an
actual linear combination.
Linear Algebra Module I: Linear Systems Summer Term 2021 47 / 75
Matrix Equations
The left-hand side of this last equation leads us to one of the central
constructions in all of Linear Algebra.
Linear Combinations
Given a collection of vectors {v1, v2, . . . , vn}, a linear combination of
these vectors is a sum of the form
α1v1 + α2v2 + · · ·+ αnvn
where the coefficients αi are scalars.
In other words, it is a sum of scalar multiples of the vectors
v1, v2, . . . vn.
The expression on the left of (4) is a linear combination of sorts, but
where the coefficients are scalar-valued variables rather than actual scalars.
So for any assignment of values to the variables x1, x2, . . . xn we get an
actual linear combination.
Linear Algebra Module I: Linear Systems Summer Term 2021 47 / 75
Matrix Equations
Returning to equation (2) we observe that the left-hand side can be
written as A ∗ x, where A is the m × n coefficient matrix
A =
a11 a12 . . . a1n
a21 a22 . . . a2n
…
… . . .
…
am1 am2 . . . amn
(5)
and x is the n × 1 vector variable
x =
x1
x2
…
xn
Linear Algebra Module I: Linear Systems Summer Term 2021 48 / 75
Matrix Equations
This leads to our final equivalent form of (2):
The matrix equation associated to the system of equations
A ∗ x = b (6)
where A is the matrix of coefficients and b is the vector
b := [b1 b2 . . . bm]T .
As with (2), a solution to this matrix equation is an assignment of a
particular numerical vector to x making the equation true, and the matrix
equation is consistent iff such an x exists.
Linear Algebra Module I: Linear Systems Summer Term 2021 49 / 75
Matrix Equations
This leads to our final equivalent form of (2):
The matrix equation associated to the system of equations
A ∗ x = b (6)
where A is the matrix of coefficients and b is the vector
b := [b1 b2 . . . bm]T .
As with (2), a solution to this matrix equation is an assignment of a
particular numerical vector to x making the equation true, and the matrix
equation is consistent iff such an x exists.
Linear Algebra Module I: Linear Systems Summer Term 2021 49 / 75
Matrix Equations
This leads to our final equivalent form of (2):
The matrix equation associated to the system of equations
A ∗ x = b (6)
where A is the matrix of coefficients and b is the vector
b := [b1 b2 . . . bm]T .
As with (2), a solution to this matrix equation is an assignment of a
particular numerical vector to x making the equation true, and the matrix
equation is consistent iff such an x exists.
Linear Algebra Module I: Linear Systems Summer Term 2021 49 / 75
Matrix Equations
Summarizing
Theorem
The system of equations appearing in (1) is equivalently represented by
the vector equations appearing in (2), (3), (4), as well as the matrix
equation (6).
Moreover, the system is consistent precisely when the vector b can be
written as a linear combination of the columns of the coefficient matrix A.
The last part of this theorem is often called the consistency theorem for
systems of equations. We will refer to it in this way.
Linear Algebra Module I: Linear Systems Summer Term 2021 50 / 75
Matrix Equations
Summarizing
Theorem
The system of equations appearing in (1) is equivalently represented by
the vector equations appearing in (2), (3), (4), as well as the matrix
equation (6).
Moreover, the system is consistent precisely when the vector b can be
written as a linear combination of the columns of the coefficient matrix A.
The last part of this theorem is often called the consistency theorem for
systems of equations. We will refer to it in this way.
Linear Algebra Module I: Linear Systems Summer Term 2021 50 / 75
Matrix Equations
Summarizing
Theorem
The system of equations appearing in (1) is equivalently represented by
the vector equations appearing in (2), (3), (4), as well as the matrix
equation (6).
Moreover, the system is consistent precisely when the vector b can be
written as a linear combination of the columns of the coefficient matrix A.
The last part of this theorem is often called the consistency theorem for
systems of equations. We will refer to it in this way.
Linear Algebra Module I: Linear Systems Summer Term 2021 50 / 75
Matrix Equations
Summarizing
Theorem
The system of equations appearing in (1) is equivalently represented by
the vector equations appearing in (2), (3), (4), as well as the matrix
equation (6).
Moreover, the system is consistent precisely when the vector b can be
written as a linear combination of the columns of the coefficient matrix A.
The last part of this theorem is often called the consistency theorem for
systems of equations. We will refer to it in this way.
Linear Algebra Module I: Linear Systems Summer Term 2021 50 / 75
Matrix Equations
Finally, we consider the case of a matrix equation
A ∗ x = b (7)
when A is invertible.
If we assume x0 is a solution, we can multiply both sides of the equation
on the left by A−1 to get
x0 = I ∗ x0 = (A−1 ∗ A) ∗ x0 = A−1 ∗ (A ∗ x0) = A−1 ∗ b
On the other hand, if we take x = A−1 ∗ b and substitute into equation
(7), we get A ∗ (A−1 ∗ b) = (A ∗ A−1) ∗ b = I ∗ b = b In other words, we
have shown
Linear Algebra Module I: Linear Systems Summer Term 2021 51 / 75
Matrix Equations
Finally, we consider the case of a matrix equation
A ∗ x = b (7)
when A is invertible.
If we assume x0 is a solution, we can multiply both sides of the equation
on the left by A−1 to get
x0 = I ∗ x0 = (A−1 ∗ A) ∗ x0 = A−1 ∗ (A ∗ x0) = A−1 ∗ b
On the other hand, if we take x = A−1 ∗ b and substitute into equation
(7), we get A ∗ (A−1 ∗ b) = (A ∗ A−1) ∗ b = I ∗ b = b In other words, we
have shown
Linear Algebra Module I: Linear Systems Summer Term 2021 51 / 75
Matrix Equations
Finally, we consider the case of a matrix equation
A ∗ x = b (7)
when A is invertible.
If we assume x0 is a solution, we can multiply both sides of the equation
on the left by A−1 to get
x0 = I ∗ x0 = (A−1 ∗ A) ∗ x0 = A−1 ∗ (A ∗ x0) = A−1 ∗ b
On the other hand, if we take x = A−1 ∗ b and substitute into equation
(7), we get A ∗ (A−1 ∗ b) = (A ∗ A−1) ∗ b = I ∗ b = b In other words, we
have shown
Linear Algebra Module I: Linear Systems Summer Term 2021 51 / 75
Matrix Equations
Finally, we consider the case of a matrix equation
A ∗ x = b (7)
when A is invertible.
If we assume x0 is a solution, we can multiply both sides of the equation
on the left by A−1 to get
x0 = I ∗ x0 = (A−1 ∗ A) ∗ x0 = A−1 ∗ (A ∗ x0) = A−1 ∗ b
On the other hand, if we take x = A−1 ∗ b and substitute into equation
(7), we get A ∗ (A−1 ∗ b) = (A ∗ A−1) ∗ b = I ∗ b = b
In other words, we
have shown
Linear Algebra Module I: Linear Systems Summer Term 2021 51 / 75
Matrix Equations
Finally, we consider the case of a matrix equation
A ∗ x = b (7)
when A is invertible.
If we assume x0 is a solution, we can multiply both sides of the equation
on the left by A−1 to get
x0 = I ∗ x0 = (A−1 ∗ A) ∗ x0 = A−1 ∗ (A ∗ x0) = A−1 ∗ b
On the other hand, if we take x = A−1 ∗ b and substitute into equation
(7), we get A ∗ (A−1 ∗ b) = (A ∗ A−1) ∗ b = I ∗ b = b In other words, we
have shown
Linear Algebra Module I: Linear Systems Summer Term 2021 51 / 75
Matrix Equations
Theorem
If A is an invertible n × n matrix, then for any n × 1 vector b and n × 1
vector variable x, the matrix equation
A ∗ x = b
is consistent, and has a unique solution given by x = A−1 ∗ b.
Note also that the above matrix formulations give us an equivalent
perspective on the augmented coefficient matrix of the original system.
Theorem
The original system of equations given in (1) has an ACM given as the
concatenated matrix [A b], where A and b are as in (6), the matrix
equation corresponding to (1).
Linear Algebra Module I: Linear Systems Summer Term 2021 52 / 75
Matrix Equations
Theorem
If A is an invertible n × n matrix, then for any n × 1 vector b and n × 1
vector variable x, the matrix equation
A ∗ x = b
is consistent, and has a unique solution given by x = A−1 ∗ b.
Note also that the above matrix formulations give us an equivalent
perspective on the augmented coefficient matrix of the original system.
Theorem
The original system of equations given in (1) has an ACM given as the
concatenated matrix [A b], where A and b are as in (6), the matrix
equation corresponding to (1).
Linear Algebra Module I: Linear Systems Summer Term 2021 52 / 75
Matrix Equations
Theorem
If A is an invertible n × n matrix, then for any n × 1 vector b and n × 1
vector variable x, the matrix equation
A ∗ x = b
is consistent, and has a unique solution given by x = A−1 ∗ b.
Note also that the above matrix formulations give us an equivalent
perspective on the augmented coefficient matrix of the original system.
Theorem
The original system of equations given in (1) has an ACM given as the
concatenated matrix [A b], where A and b are as in (6), the matrix
equation corresponding to (1).
Linear Algebra Module I: Linear Systems Summer Term 2021 52 / 75
Matrix Equations
Theorem
If A is an invertible n × n matrix, then for any n × 1 vector b and n × 1
vector variable x, the matrix equation
A ∗ x = b
is consistent, and has a unique solution given by x = A−1 ∗ b.
Note also that the above matrix formulations give us an equivalent
perspective on the augmented coefficient matrix of the original system.
Theorem
The original system of equations given in (1) has an ACM given as the
concatenated matrix [A b], where A and b are as in (6), the matrix
equation corresponding to (1).
Linear Algebra Module I: Linear Systems Summer Term 2021 52 / 75
Matrix Equations
Theorem
If A is an invertible n × n matrix, then for any n × 1 vector b and n × 1
vector variable x, the matrix equation
A ∗ x = b
is consistent, and has a unique solution given by x = A−1 ∗ b.
Note also that the above matrix formulations give us an equivalent
perspective on the augmented coefficient matrix of the original system.
Theorem
The original system of equations given in (1) has an ACM given as the
concatenated matrix [A b], where A and b are as in (6), the matrix
equation corresponding to (1).
Linear Algebra Module I: Linear Systems Summer Term 2021 52 / 75
Table of Contents
1 Systems of Linear Equations
2 Solving Systems of Equations – Row Reduction
Overview
Plan for Row Reduction
Notation for Row Reduction
Algorithm for Row Reduction
3 Matrices
Definition of a Matrix
Matrix Operations
Matrix Equations
4 The Superposition Principle
5 Elementary matrices
6 The Dimensions of a System of Equations, and Generalized Equivalence
Linear Algebra Module I: Linear Systems Summer Term 2021 53 / 75
Superposition Principle
Associated Homogeneous Equation
Given a matrix equation A ∗ x = b, its associated homogeneous
equation is the equation A ∗ x = 0 that results from replacing b by 0.
Note that consistency status may change in passing from an arbitrary
non-homogeneous equation to its associated counterpart. However, if the
original system is consistent, there is an important relation between the
two solution sets, which is a manifestation of the superposition principle.
Linear Algebra Module I: Linear Systems Summer Term 2021 54 / 75
Superposition Principle
Associated Homogeneous Equation
Given a matrix equation A ∗ x = b, its associated homogeneous
equation is the equation A ∗ x = 0 that results from replacing b by 0.
Note that consistency status may change in passing from an arbitrary
non-homogeneous equation to its associated counterpart. However, if the
original system is consistent, there is an important relation between the
two solution sets, which is a manifestation of the superposition principle.
Linear Algebra Module I: Linear Systems Summer Term 2021 54 / 75
Superposition Principle
Associated Homogeneous Equation
Given a matrix equation A ∗ x = b, its associated homogeneous
equation is the equation A ∗ x = 0 that results from replacing b by 0.
Note that consistency status may change in passing from an arbitrary
non-homogeneous equation to its associated counterpart. However, if the
original system is consistent, there is an important relation between the
two solution sets, which is a manifestation of the superposition principle.
Linear Algebra Module I: Linear Systems Summer Term 2021 54 / 75
Superposition Principle
If x′, x′′ are two solutions to the consistent matrix equation A ∗ x = b, then
A ∗ (x′ − x′′) = A ∗ x′ − A ∗ x′′ = b− b = 0
so (x′ − x′′) is a solution to the associated homogeneous equation.
On the other hand, given a solution xh to the associated homogeneous
equation, and a solution x to the original equation, we see
A ∗ (xh + x) = A ∗ xh + A ∗ x = 0 + b = b
so xh + x is again a solution to the original equation.
Superposition Principle
Suppose A ∗ x = b is a consistent matrix equation, with xp a particular
solution to the equation. Then the set of solutions to the original equation
can be expressed as
{xh + xp | xh ∈ S0}
where S0 denotes the set of solutions to the associated homogeneous
equation.
Linear Algebra Module I: Linear Systems Summer Term 2021 55 / 75
Superposition Principle
If x′, x′′ are two solutions to the consistent matrix equation A ∗ x = b, then
A ∗ (x′ − x′′) = A ∗ x′ − A ∗ x′′ = b− b = 0
so (x′ − x′′) is a solution to the associated homogeneous equation.
On the other hand, given a solution xh to the associated homogeneous
equation, and a solution x to the original equation, we see
A ∗ (xh + x) = A ∗ xh + A ∗ x = 0 + b = b
so xh + x is again a solution to the original equation.
Superposition Principle
Suppose A ∗ x = b is a consistent matrix equation, with xp a particular
solution to the equation. Then the set of solutions to the original equation
can be expressed as
{xh + xp | xh ∈ S0}
where S0 denotes the set of solutions to the associated homogeneous
equation.
Linear Algebra Module I: Linear Systems Summer Term 2021 55 / 75
Superposition Principle
If x′, x′′ are two solutions to the consistent matrix equation A ∗ x = b, then
A ∗ (x′ − x′′) = A ∗ x′ − A ∗ x′′ = b− b = 0
so (x′ − x′′) is a solution to the associated homogeneous equation.
On the other hand, given a solution xh to the associated homogeneous
equation, and a solution x to the original equation, we see
A ∗ (xh + x) = A ∗ xh + A ∗ x = 0 + b = b
so xh + x is again a solution to the original equation.
Superposition Principle
Suppose A ∗ x = b is a consistent matrix equation, with xp a particular
solution to the equation. Then the set of solutions to the original equation
can be expressed as
{xh + xp | xh ∈ S0}
where S0 denotes the set of solutions to the associated homogeneous
equation.
Linear Algebra Module I: Linear Systems Summer Term 2021 55 / 75
Superposition Principle
If x′, x′′ are two solutions to the consistent matrix equation A ∗ x = b, then
A ∗ (x′ − x′′) = A ∗ x′ − A ∗ x′′ = b− b = 0
so (x′ − x′′) is a solution to the associated homogeneous equation.
On the other hand, given a solution xh to the associated homogeneous
equation, and a solution x to the original equation, we see
A ∗ (xh + x) = A ∗ xh + A ∗ x = 0 + b = b
so xh + x is again a solution to the original equation.
Superposition Principle
Suppose A ∗ x = b is a consistent matrix equation, with xp a particular
solution to the equation. Then the set of solutions to the original equation
can be expressed as
{xh + xp | xh ∈ S0}
where S0 denotes the set of solutions to the associated homogeneous
equation.
Linear Algebra Module I: Linear Systems Summer Term 2021 55 / 75
Superposition Principle
Examples
Suppose we are given a 3× 5 matrix A and a 3× 1 vector b with
A =
−8 8 15 1 1110 11 2 −2 13
−19 −7 −14 8 −4
, b =
355
21
and we want to describe the set of solutions to the equation A ∗ x = b.
Using Octave or MATLAB, we compute the rref(ACM):
rref ([A b]) =
1 0 0 −475/1419 −853/4021 −666/3350 1 0 636/4021 5619/4021 9041/4021
0 0 1 −789/4021 −503/4021 297/4021
The columns (except the right-most) that do not contain leading ones are
the fourth and fifth. We also see that the system is consistent.
Linear Algebra Module I: Linear Systems Summer Term 2021 56 / 75
Superposition Principle
Examples
Suppose we are given a 3× 5 matrix A and a 3× 1 vector b with
A =
−8 8 15 1 1110 11 2 −2 13
−19 −7 −14 8 −4
, b =
355
21
and we want to describe the set of solutions to the equation A ∗ x = b.
Using Octave or MATLAB, we compute the rref(ACM):
rref ([A b]) =
1 0 0 −475/1419 −853/4021 −666/3350 1 0 636/4021 5619/4021 9041/4021
0 0 1 −789/4021 −503/4021 297/4021
The columns (except the right-most) that do not contain leading ones are
the fourth and fifth. We also see that the system is consistent.
Linear Algebra Module I: Linear Systems Summer Term 2021 56 / 75
Superposition Principle
Examples
Suppose we are given a 3× 5 matrix A and a 3× 1 vector b with
A =
−8 8 15 1 1110 11 2 −2 13
−19 −7 −14 8 −4
, b =
355
21
and we want to describe the set of solutions to the equation A ∗ x = b.
Using Octave or MATLAB, we compute the rref(ACM):
rref ([A b]) =
1 0 0 −475/1419 −853/4021 −666/3350 1 0 636/4021 5619/4021 9041/4021
0 0 1 −789/4021 −503/4021 297/4021
The columns (except the right-most) that do not contain leading ones are
the fourth and fifth. We also see that the system is consistent.
Linear Algebra Module I: Linear Systems Summer Term 2021 56 / 75
Superposition Principle
Examples
It follows that there is a 2-parameter family of solutions parametrized by
the free, or independent variables x4 and x5, with the dependent variables
x1, x2, x3 expressable as linear functions in x4 and x5. Written in standard
parametrized form, the full solution set is then given by
x1 = (475/1419)x4 + (853/4021)x5 − 666/335
x2 = (−636/4021)x4 − (5619/4021)x5 + 9041/4021
x3 = (789/4021)x4 + (503/4021)x5 + 297/4021
x4 = x4
x5 = x5
Linear Algebra Module I: Linear Systems Summer Term 2021 57 / 75
Superposition Principle
Examples
It follows that there is a 2-parameter family of solutions parametrized by
the free, or independent variables x4 and x5, with the dependent variables
x1, x2, x3 expressable as linear functions in x4 and x5. Written in standard
parametrized form, the full solution set is then given by
x1 = (475/1419)x4 + (853/4021)x5 − 666/335
x2 = (−636/4021)x4 − (5619/4021)x5 + 9041/4021
x3 = (789/4021)x4 + (503/4021)x5 + 297/4021
x4 = x4
x5 = x5
Linear Algebra Module I: Linear Systems Summer Term 2021 57 / 75
Superposition Principle
Examples
To rewrite in superpositional format, we first choose a particular solution.
The easiest one to compute is that corresponding to x4 = x5 = 0. In other
words the vector determined by the constant terms appearing on the
right-hand sides of the above set of equations:
xp =
−666/335
9041/4021
297/4021
0
0
Linear Algebra Module I: Linear Systems Summer Term 2021 58 / 75
Superposition Principle
Examples
To rewrite in superpositional format, we first choose a particular solution.
The easiest one to compute is that corresponding to x4 = x5 = 0. In other
words the vector determined by the constant terms appearing on the
right-hand sides of the above set of equations:
xp =
−666/335
9041/4021
297/4021
0
0
Linear Algebra Module I: Linear Systems Summer Term 2021 58 / 75
Superposition Principle
Examples
The homogeneous part is then given as the 2-parameter set of vectors
corresponding to the linear part of the same set of equations:
xh = x4
475/1419
−636/4021
789/4021
1
0
+ x5
853/4021
5619/4021
503/4021
0
1
The solution set can then be alternately expressed as x = xp + xh where
xp and xh are as given above.
Linear Algebra Module I: Linear Systems Summer Term 2021 59 / 75
Superposition Principle
Examples
The homogeneous part is then given as the 2-parameter set of vectors
corresponding to the linear part of the same set of equations:
xh = x4
475/1419
−636/4021
789/4021
1
0
+ x5
853/4021
5619/4021
503/4021
0
1
The solution set can then be alternately expressed as x = xp + xh where
xp and xh are as given above.
Linear Algebra Module I: Linear Systems Summer Term 2021 59 / 75
Table of Contents
1 Systems of Linear Equations
2 Solving Systems of Equations – Row Reduction
Overview
Plan for Row Reduction
Notation for Row Reduction
Algorithm for Row Reduction
3 Matrices
Definition of a Matrix
Matrix Operations
Matrix Equations
4 The Superposition Principle
5 Elementary matrices
6 The Dimensions of a System of Equations, and Generalized Equivalence
Linear Algebra Module I: Linear Systems Summer Term 2021 60 / 75
Elementary Matrices
As we have seen, systems of equations—or equivalently matrix
equations—are solved by i) forming the ACM associated with the set of
equations and ii) applying row operations to the ACM until it is in reduced
row echelon form.
It turns out these row operations can be realized by left multiplication by a
certain type of matrix, and these matrices have uses beyond that of
performing row operations.
Linear Algebra Module I: Linear Systems Summer Term 2021 61 / 75
Elementary Matrices
As we have seen, systems of equations—or equivalently matrix
equations—are solved by i) forming the ACM associated with the set of
equations and ii) applying row operations to the ACM until it is in reduced
row echelon form.
It turns out these row operations can be realized by left multiplication by a
certain type of matrix, and these matrices have uses beyond that of
performing row operations.
Linear Algebra Module I: Linear Systems Summer Term 2021 61 / 75
Elementary Matrices
As we have seen, systems of equations—or equivalently matrix
equations—are solved by i) forming the ACM associated with the set of
equations and ii) applying row operations to the ACM until it is in reduced
row echelon form.
It turns out these row operations can be realized by left multiplication by a
certain type of matrix, and these matrices have uses beyond that of
performing row operations.
Linear Algebra Module I: Linear Systems Summer Term 2021 61 / 75
Elementary Matrices
To explain how matrix multiplication comes into play, let us write R(−)
for a particular row operation on m × n matrices, so that the given
operation is represented by A 7→ R(A).
It turns out that for any of the three types of row operations we have
considered above, one has the identity
R(A) = R(I ∗ A) = R(I) ∗ A
In other words,
the row operation R(−), applied to A, can be realized in terms of
left multiplication by the m ×m matrix R(I) gotten by applying R
to the m ×m identity matrix.
Linear Algebra Module I: Linear Systems Summer Term 2021 62 / 75
Elementary Matrices
To explain how matrix multiplication comes into play, let us write R(−)
for a particular row operation on m × n matrices, so that the given
operation is represented by A 7→ R(A).
It turns out that for any of the three types of row operations we have
considered above, one has the identity
R(A) = R(I ∗ A) = R(I) ∗ A
In other words,
the row operation R(−), applied to A, can be realized in terms of
left multiplication by the m ×m matrix R(I) gotten by applying R
to the m ×m identity matrix.
Linear Algebra Module I: Linear Systems Summer Term 2021 62 / 75
Elementary Matrices
To explain how matrix multiplication comes into play, let us write R(−)
for a particular row operation on m × n matrices, so that the given
operation is represented by A 7→ R(A).
It turns out that for any of the three types of row operations we have
considered above, one has the identity
R(A) = R(I ∗ A) = R(I) ∗ A
In other words,
the row operation R(−), applied to A, can be realized in terms of
left multiplication by the m ×m matrix R(I) gotten by applying R
to the m ×m identity matrix.
Linear Algebra Module I: Linear Systems Summer Term 2021 62 / 75
Elementary Matrices
To explain how matrix multiplication comes into play, let us write R(−)
for a particular row operation on m × n matrices, so that the given
operation is represented by A 7→ R(A).
It turns out that for any of the three types of row operations we have
considered above, one has the identity
R(A) = R(I ∗ A) = R(I) ∗ A
In other words,
the row operation R(−), applied to A, can be realized in terms of
left multiplication by the m ×m matrix R(I) gotten by applying R
to the m ×m identity matrix.
Linear Algebra Module I: Linear Systems Summer Term 2021 62 / 75
Elementary Matrices
To explain how matrix multiplication comes into play, let us write R(−)
for a particular row operation on m × n matrices, so that the given
operation is represented by A 7→ R(A).
It turns out that for any of the three types of row operations we have
considered above, one has the identity
R(A) = R(I ∗ A) = R(I) ∗ A
In other words,
the row operation R(−), applied to A, can be realized in terms of
left multiplication by the m ×m matrix R(I) gotten by applying R
to the m ×m identity matrix.
Linear Algebra Module I: Linear Systems Summer Term 2021 62 / 75
Elementary Matrices
To explain how matrix multiplication comes into play, let us write R(−)
for a particular row operation on m × n matrices, so that the given
operation is represented by A 7→ R(A).
It turns out that for any of the three types of row operations we have
considered above, one has the identity
R(A) = R(I ∗ A) = R(I) ∗ A
In other words,
the row operation R(−), applied to A, can be realized in terms of
left multiplication by the m ×m matrix R(I) gotten by applying R
to the m ×m identity matrix.
Linear Algebra Module I: Linear Systems Summer Term 2021 62 / 75
Elementary Matrices
One has – for each row operation – a corresponding elementary matrix
derived from the identity matrix of the appropriate dimension by
application of that given operation.
These matrices, and the notation used to define them, can be recorded in
an expanded version of the table above in which we indicated the types of
operations and their representation:
Linear Algebra Module I: Linear Systems Summer Term 2021 63 / 75
Elementary Matrices
One has – for each row operation – a corresponding elementary matrix
derived from the identity matrix of the appropriate dimension by
application of that given operation.
These matrices, and the notation used to define them, can be recorded in
an expanded version of the table above in which we indicated the types of
operations and their representation:
Linear Algebra Module I: Linear Systems Summer Term 2021 63 / 75
Elementary Matrices
One has – for each row operation – a corresponding elementary matrix
derived from the identity matrix of the appropriate dimension by
application of that given operation.
These matrices, and the notation used to define them, can be recorded in
an expanded version of the table above in which we indicated the types of
operations and their representation:
Linear Algebra Module I: Linear Systems Summer Term 2021 63 / 75
Elementary Matrices
Type What it does Indicated by Elementary
matrix
Switches
Type I i th and j th Ri ↔ Rj R(I) = Pij
rows
Multiplies
Type II i th row r · Ri R(I) = Di(r)
by r 6= 0
Adds
Type III a times the i th row a · Ri added to Rj R(I) = Eji(a)
to the j th row
Linear Algebra Module I: Linear Systems Summer Term 2021 64 / 75
Elementary Matrices
In an analogous fashion, one can also perform column operations on a
matrix. As with row operations there are three types, and each type can
be achieved via right multiplication with the corresponding matrix.
In other words, if C(−) indicates the given column operation, then for each
type one has
C(A) = C(A ∗ I) = A ∗ C(I)
Denoting the kth column by Ck , we have
Linear Algebra Module I: Linear Systems Summer Term 2021 65 / 75
Elementary Matrices
In an analogous fashion, one can also perform column operations on a
matrix. As with row operations there are three types, and each type can
be achieved via right multiplication with the corresponding matrix.
In other words, if C(−) indicates the given column operation, then for each
type one has
C(A) = C(A ∗ I) = A ∗ C(I)
Denoting the kth column by Ck , we have
Linear Algebra Module I: Linear Systems Summer Term 2021 65 / 75
Elementary Matrices
In an analogous fashion, one can also perform column operations on a
matrix. As with row operations there are three types, and each type can
be achieved via right multiplication with the corresponding matrix.
In other words, if C(−) indicates the given column operation, then for each
type one has
C(A) = C(A ∗ I) = A ∗ C(I)
Denoting the kth column by Ck , we have
Linear Algebra Module I: Linear Systems Summer Term 2021 65 / 75
Elementary Matrices
In an analogous fashion, one can also perform column operations on a
matrix. As with row operations there are three types, and each type can
be achieved via right multiplication with the corresponding matrix.
In other words, if C(−) indicates the given column operation, then for each
type one has
C(A) = C(A ∗ I) = A ∗ C(I)
Denoting the kth column by Ck , we have
Linear Algebra Module I: Linear Systems Summer Term 2021 65 / 75
Elementary Matrices
Type What it does Indicated by Elementary
matrix
Switches
Type I i th and j th Ci ↔ Cj C(I) = Pij
colmns
Multiplies
Type II i th column r · Ci C(I) = Di(r)
by r 6= 0
Adds
Type III a times the i th column a · Ci added to Cj C(I) = Eij(a)
to the j th column
Linear Algebra Module I: Linear Systems Summer Term 2021 66 / 75
Elementary Matrices
Each elementary matrix is invertible, and of the same type. The following
indicates how each elementary matrix behaves under
i) inversion and ii) transposition:
P−1ij = Pij , P
T
ij = Pij (1)
Di (r)−1 = Di (r−1), Di (r)T = Di (r) (2)
Eij(a)−1 = Eij(−a), Eij(a)T = Eji (a) (3)
Linear Algebra Module I: Linear Systems Summer Term 2021 67 / 75
Elementary Matrices
Each elementary matrix is invertible, and of the same type. The following
indicates how each elementary matrix behaves under
i) inversion and
ii) transposition:
P−1ij = Pij , P
T
ij = Pij (1)
Di (r)−1 = Di (r−1), Di (r)T = Di (r) (2)
Eij(a)−1 = Eij(−a), Eij(a)T = Eji (a) (3)
Linear Algebra Module I: Linear Systems Summer Term 2021 67 / 75
Elementary Matrices
Each elementary matrix is invertible, and of the same type. The following
indicates how each elementary matrix behaves under
i) inversion and ii) transposition:
P−1ij = Pij , P
T
ij = Pij (1)
Di (r)−1 = Di (r−1), Di (r)T = Di (r) (2)
Eij(a)−1 = Eij(−a), Eij(a)T = Eji (a) (3)
Linear Algebra Module I: Linear Systems Summer Term 2021 67 / 75
Elementary Matrices
Each elementary matrix is invertible, and of the same type. The following
indicates how each elementary matrix behaves under
i) inversion and ii) transposition:
P−1ij = Pij , P
T
ij = Pij (1)
Di (r)−1 = Di (r−1), Di (r)T = Di (r) (2)
Eij(a)−1 = Eij(−a), Eij(a)T = Eji (a) (3)
Linear Algebra Module I: Linear Systems Summer Term 2021 67 / 75
Elementary Matrices
Elementary matrices are useful in problems where one wants to express the
inverse of a matrix explicitly as a product of elementary matrices.
We have already seen that a square matrix A is invertible iff is is row
equivalent to the identity matrix. By keeping track of the row operations
used and then realizing them in terms of left multiplication by elementary
matrices, we can write down a product of matrices ending in A that equals
I.
The product of elementary matrices appearing to the left of A must then
be equal to A−1. With such an expression for A−1 we can also represent A
itself as a product of elementray matrices.
Linear Algebra Module I: Linear Systems Summer Term 2021 68 / 75
Elementary Matrices
Elementary matrices are useful in problems where one wants to express the
inverse of a matrix explicitly as a product of elementary matrices.
We have already seen that a square matrix A is invertible iff is is row
equivalent to the identity matrix. By keeping track of the row operations
used and then realizing them in terms of left multiplication by elementary
matrices, we can write down a product of matrices ending in A that equals
I.
The product of elementary matrices appearing to the left of A must then
be equal to A−1. With such an expression for A−1 we can also represent A
itself as a product of elementray matrices.
Linear Algebra Module I: Linear Systems Summer Term 2021 68 / 75
Elementary Matrices
Elementary matrices are useful in problems where one wants to express the
inverse of a matrix explicitly as a product of elementary matrices.
We have already seen that a square matrix A is invertible iff is is row
equivalent to the identity matrix. By keeping track of the row operations
used and then realizing them in terms of left multiplication by elementary
matrices, we can write down a product of matrices ending in A that equals
I.
The product of elementary matrices appearing to the left of A must then
be equal to A−1. With such an expression for A−1 we can also represent A
itself as a product of elementray matrices.
Linear Algebra Module I: Linear Systems Summer Term 2021 68 / 75
Elementary Matrices
Examples
Suppose A =
[
2 3
3 5
]
. The following (non-unique) sequence of row
operations reduces A to I:
[
2 3
3 5
]
R2:=R2+(−1)∗R1−−−−−−−−−−→
[
2 3
1 2
]
R1:=R1+(−2)∗R2−−−−−−−−−−→
[
0 −1
1 2
]
R2:=R2+2∗R1−−−−−−−−→
[
0 −1
1 0
]
R1↔R2−−−−→
[
1 0
0 −1
]
(−1)∗R2−−−−−→
[
1 0
0 1
]
Remembering that elementary matrices realize row operations via
left-multiplication, transforming the above sequence into a product yields
the equation
D2(−1) ∗ P12 ∗ E21(2) ∗ E12(−2) ∗ E21(−1) ∗ A = I
Linear Algebra Module I: Linear Systems Summer Term 2021 69 / 75
Elementary Matrices
Examples
Suppose A =
[
2 3
3 5
]
. The following (non-unique) sequence of row
operations reduces A to I:[
2 3
3 5
]
R2:=R2+(−1)∗R1−−−−−−−−−−→
[
2 3
1 2
]
R1:=R1+(−2)∗R2−−−−−−−−−−→
[
0 −1
1 2
]
R2:=R2+2∗R1−−−−−−−−→
[
0 −1
1 0
]
R1↔R2−−−−→
[
1 0
0 −1
]
(−1)∗R2−−−−−→
[
1 0
0 1
]
Remembering that elementary matrices realize row operations via
left-multiplication, transforming the above sequence into a product yields
the equation
D2(−1) ∗ P12 ∗ E21(2) ∗ E12(−2) ∗ E21(−1) ∗ A = I
Linear Algebra Module I: Linear Systems Summer Term 2021 69 / 75
Elementary Matrices
Examples
Suppose A =
[
2 3
3 5
]
. The following (non-unique) sequence of row
operations reduces A to I:[
2 3
3 5
]
R2:=R2+(−1)∗R1−−−−−−−−−−→
[
2 3
1 2
]
R1:=R1+(−2)∗R2−−−−−−−−−−→
[
0 −1
1 2
]
R2:=R2+2∗R1−−−−−−−−→
[
0 −1
1 0
]
R1↔R2−−−−→
[
1 0
0 −1
]
(−1)∗R2−−−−−→
[
1 0
0 1
]
Remembering that elementary matrices realize row operations via
left-multiplication, transforming the above sequence into a product yields
the equation
D2(−1) ∗ P12 ∗ E21(2) ∗ E12(−2) ∗ E21(−1) ∗ A = I
Linear Algebra Module I: Linear Systems Summer Term 2021 69 / 75
Elementary Matrices
Examples
Suppose A =
[
2 3
3 5
]
. The following (non-unique) sequence of row
operations reduces A to I:[
2 3
3 5
]
R2:=R2+(−1)∗R1−−−−−−−−−−→
[
2 3
1 2
]
R1:=R1+(−2)∗R2−−−−−−−−−−→
[
0 −1
1 2
]
R2:=R2+2∗R1−−−−−−−−→
[
0 −1
1 0
]
R1↔R2−−−−→
[
1 0
0 −1
]
(−1)∗R2−−−−−→
[
1 0
0 1
]
Remembering that elementary matrices realize row operations via
left-multiplication, transforming the above sequence into a product yields
the equation
D2(−1) ∗ P12 ∗ E21(2) ∗ E12(−2) ∗ E21(−1) ∗ A = I
Linear Algebra Module I: Linear Systems Summer Term 2021 69 / 75
Elementary Matrices
Examples
Setting B = D2(−1) ∗ P12 ∗ E21(2) ∗ E12(−2) ∗ E21(−1), we see that
B ∗ A = I. But we have already seen that this implies B = A−1, the
unique inverse of A.
Now if we want to also represent A as a product of elementary matrices,
we could do so by the sequence of equalities
A =
(
A−1
)−1
=
(
D2(−1) ∗ P12 ∗ E21(2) ∗ E12(−2) ∗ E21(−1)
)−1
= E21(−1)−1 ∗ E12(−2)−1 ∗ E21(2)−1 ∗ P−112 ∗ D2(−1)
−1
= E21(1) ∗ E12(2) ∗ E21(−2) ∗ P12 ∗ D2(−1)
Linear Algebra Module I: Linear Systems Summer Term 2021 70 / 75
Elementary Matrices
Examples
Setting B = D2(−1) ∗ P12 ∗ E21(2) ∗ E12(−2) ∗ E21(−1), we see that
B ∗ A = I. But we have already seen that this implies B = A−1, the
unique inverse of A.
Now if we want to also represent A as a product of elementary matrices,
we could do so by the sequence of equalities
A =
(
A−1
)−1
=
(
D2(−1) ∗ P12 ∗ E21(2) ∗ E12(−2) ∗ E21(−1)
)−1
= E21(−1)−1 ∗ E12(−2)−1 ∗ E21(2)−1 ∗ P−112 ∗ D2(−1)
−1
= E21(1) ∗ E12(2) ∗ E21(−2) ∗ P12 ∗ D2(−1)
Linear Algebra Module I: Linear Systems Summer Term 2021 70 / 75
Elementary Matrices
Examples
Setting B = D2(−1) ∗ P12 ∗ E21(2) ∗ E12(−2) ∗ E21(−1), we see that
B ∗ A = I. But we have already seen that this implies B = A−1, the
unique inverse of A.
Now if we want to also represent A as a product of elementary matrices,
we could do so by the sequence of equalities
A =
(
A−1
)−1
=
(
D2(−1) ∗ P12 ∗ E21(2) ∗ E12(−2) ∗ E21(−1)
)−1
= E21(−1)−1 ∗ E12(−2)−1 ∗ E21(2)−1 ∗ P−112 ∗ D2(−1)
−1
= E21(1) ∗ E12(2) ∗ E21(−2) ∗ P12 ∗ D2(−1)
Linear Algebra Module I: Linear Systems Summer Term 2021 70 / 75
Table of Contents
1 Systems of Linear Equations
2 Solving Systems of Equations – Row Reduction
Overview
Plan for Row Reduction
Notation for Row Reduction
Algorithm for Row Reduction
3 Matrices
Definition of a Matrix
Matrix Operations
Matrix Equations
4 The Superposition Principle
5 Elementary matrices
6 The Dimensions of a System of Equations, and Generalized Equivalence
Linear Algebra Module I: Linear Systems Summer Term 2021 71 / 75
Dimensions of Systems and Equivalence
We conclude the first module with a brief discussion of dimensions for
systems of equations, the impact changing dimensions can have on the set
of solutions to a given system, and when two systems of different
dimensions could still have the same solution set.
Consider the 1× 2 system given by the equation 2×1 − x2 = 3, and the
related 2× 2 system
2×1 − x2 =3
0x1 + 0x2 =0
It is easily seen that these two systems have the same set of solutions; the
ACM for the second system is derived from the ACM for the first system
by adding a row of zeros. Importantly, adding such a row does not change
the set of variables or unknowns involved.
Linear Algebra Module I: Linear Systems Summer Term 2021 72 / 75
Dimensions of Systems and Equivalence
We conclude the first module with a brief discussion of dimensions for
systems of equations, the impact changing dimensions can have on the set
of solutions to a given system, and when two systems of different
dimensions could still have the same solution set.
Consider the 1× 2 system given by the equation 2×1 − x2 = 3, and the
related 2× 2 system
2×1 − x2 =3
0x1 + 0x2 =0
It is easily seen that these two systems have the same set of solutions; the
ACM for the second system is derived from the ACM for the first system
by adding a row of zeros. Importantly, adding such a row does not change
the set of variables or unknowns involved.
Linear Algebra Module I: Linear Systems Summer Term 2021 72 / 75
Dimensions of Systems and Equivalence
We conclude the first module with a brief discussion of dimensions for
systems of equations, the impact changing dimensions can have on the set
of solutions to a given system, and when two systems of different
dimensions could still have the same solution set.
Consider the 1× 2 system given by the equation 2×1 − x2 = 3, and the
related 2× 2 system
2×1 − x2 =3
0x1 + 0x2 =0
It is easily seen that these two systems have the same set of solutions; the
ACM for the second system is derived from the ACM for the first system
by adding a row of zeros. Importantly, adding such a row does not change
the set of variables or unknowns involved.
Linear Algebra Module I: Linear Systems Summer Term 2021 72 / 75
Dimensions of Systems and Equivalence
On the other hand, we can consider a different scenario:
a 2× 2 system
given by
5×1 − 2×2 =3
2×1 + 4×2 =6
and a 2× 3 system given by
5×1 − 2×2 + 0x3 =3
2×1 + 4×2 + 0x3 =6
On first glance it seems these are essentially the same; the second system
in some sense contains the first, and differs by adding a variable with
coefficient zero. However, computing rref of their respective ACMs reveals
an important difference.
Linear Algebra Module I: Linear Systems Summer Term 2021 73 / 75
Dimensions of Systems and Equivalence
On the other hand, we can consider a different scenario: a 2× 2 system
given by
5×1 − 2×2 =3
2×1 + 4×2 =6
and a 2× 3 system given by
5×1 − 2×2 + 0x3 =3
2×1 + 4×2 + 0x3 =6
On first glance it seems these are essentially the same; the second system
in some sense contains the first, and differs by adding a variable with
coefficient zero. However, computing rref of their respective ACMs reveals
an important difference.
Linear Algebra Module I: Linear Systems Summer Term 2021 73 / 75
Dimensions of Systems and Equivalence
On the other hand, we can consider a different scenario: a 2× 2 system
given by
5×1 − 2×2 =3
2×1 + 4×2 =6
and a 2× 3 system given by
5×1 − 2×2 + 0x3 =3
2×1 + 4×2 + 0x3 =6
On first glance it seems these are essentially the same; the second system
in some sense contains the first, and differs by adding a variable with
coefficient zero. However, computing rref of their respective ACMs reveals
an important difference.
Linear Algebra Module I: Linear Systems Summer Term 2021 73 / 75
Dimensions of Systems and Equivalence
On the other hand, we can consider a different scenario: a 2× 2 system
given by
5×1 − 2×2 =3
2×1 + 4×2 =6
and a 2× 3 system given by
5×1 − 2×2 + 0x3 =3
2×1 + 4×2 + 0x3 =6
On first glance it seems these are essentially the same; the second system
in some sense contains the first, and differs by adding a variable with
coefficient zero. However, computing rref of their respective ACMs reveals
an important difference.
Linear Algebra Module I: Linear Systems Summer Term 2021 73 / 75
Dimensions of Systems and Equivalence
For the first system we have
ACM =
(
5 −2 3
2 4 6
)
rref (−)−−−−→ rref (ACM) =
(
1 0 1
0 1 1
)
while in the case of the second system the same computations yield
ACM =
(
5 −2 0 3
2 4 0 6
)
rref (−)−−−−→ rref (ACM) =
(
1 0 0 1
0 1 0 1
)
Both systems arre consistent. However, in the first case we see there
exists a unique solution: x1 = x2 = 1, while in the second case rref (ACM)
indicates that x3 is a free variable, with the 1-parameter family of solutions
given in vector form by
S =
11
x3
, x3 ∈ R
Linear Algebra Module I: Linear Systems Summer Term 2021 74 / 75
Dimensions of Systems and Equivalence
For the first system we have
ACM =
(
5 −2 3
2 4 6
)
rref (−)−−−−→ rref (ACM) =
(
1 0 1
0 1 1
)
while in the case of the second system the same computations yield
ACM =
(
5 −2 0 3
2 4 0 6
)
rref (−)−−−−→ rref (ACM) =
(
1 0 0 1
0 1 0 1
)
Both systems arre consistent. However, in the first case we see there
exists a unique solution: x1 = x2 = 1, while in the second case rref (ACM)
indicates that x3 is a free variable, with the 1-parameter family of solutions
given in vector form by
S =
11
x3
, x3 ∈ R
Linear Algebra Module I: Linear Systems Summer Term 2021 74 / 75
Dimensions of Systems and Equivalence
For the first system we have
ACM =
(
5 −2 3
2 4 6
)
rref (−)−−−−→ rref (ACM) =
(
1 0 1
0 1 1
)
while in the case of the second system the same computations yield
ACM =
(
5 −2 0 3
2 4 0 6
)
rref (−)−−−−→ rref (ACM) =
(
1 0 0 1
0 1 0 1
)
Both systems arre consistent. However, in the first case we see there
exists a unique solution: x1 = x2 = 1, while in the second case rref (ACM)
indicates that x3 is a free variable, with the 1-parameter family of solutions
given in vector form by
S =
11
x3
, x3 ∈ R
Linear Algebra Module I: Linear Systems Summer Term 2021 74 / 75
Dimensions of Systems and Equivalence
For the first system we have
ACM =
(
5 −2 3
2 4 6
)
rref (−)−−−−→ rref (ACM) =
(
1 0 1
0 1 1
)
while in the case of the second system the same computations yield
ACM =
(
5 −2 0 3
2 4 0 6
)
rref (−)−−−−→ rref (ACM) =
(
1 0 0 1
0 1 0 1
)
Both systems arre consistent. However, in the first case we see there
exists a unique solution: x1 = x2 = 1, while in the second case rref (ACM)
indicates that x3 is a free variable, with the 1-parameter family of solutions
given in vector form by
S =
11
x3
, x3 ∈ R
Linear Algebra Module I: Linear Systems Summer Term 2021 74 / 75
Dimensions of Systems and Equivalence
These two examples are illustrations of the following general fact
Theorem
If two linear systems have the same set of unknowns, and differ from one
another only by the addition or deletion of equations of the form
0x1 + 0x2 + · · ·+ 0xn = 0
then the two systems will have the same solution set.
On the other hand, if the two systems differ by the inclusion or deletion of
one or more variables then the two systems, if consistant, will not have the
same set of solutions, even if the added or deleted variables always appear
with 0 coefficient.
Linear Algebra Module I: Linear Systems Summer Term 2021 75 / 75
Dimensions of Systems and Equivalence
These two examples are illustrations of the following general fact
Theorem
If two linear systems have the same set of unknowns, and differ from one
another only by the addition or deletion of equations of the form
0x1 + 0x2 + · · ·+ 0xn = 0
then the two systems will have the same solution set.
On the other hand, if the two systems differ by the inclusion or deletion of
one or more variables then the two systems, if consistant, will not have the
same set of solutions, even if the added or deleted variables always appear
with 0 coefficient.
Linear Algebra Module I: Linear Systems Summer Term 2021 75 / 75
Dimensions of Systems and Equivalence
These two examples are illustrations of the following general fact
Theorem
If two linear systems have the same set of unknowns, and differ from one
another only by the addition or deletion of equations of the form
0x1 + 0x2 + · · ·+ 0xn = 0
then the two systems will have the same solution set.
On the other hand, if the two systems differ by the inclusion or deletion of
one or more variables then the two systems, if consistant, will not have the
same set of solutions, even if the added or deleted variables always appear
with 0 coefficient.
Linear Algebra Module I: Linear Systems Summer Term 2021 75 / 75
Dimensions of Systems and Equivalence
These two examples are illustrations of the following general fact
Theorem
If two linear systems have the same set of unknowns, and differ from one
another only by the addition or deletion of equations of the form
0x1 + 0x2 + · · ·+ 0xn = 0
then the two systems will have the same solution set.
On the other hand, if the two systems differ by the inclusion or deletion of
one or more variables then the two systems, if consistant, will not have the
same set of solutions, even if the added or deleted variables always appear
with 0 coefficient.
Linear Algebra Module I: Linear Systems Summer Term 2021 75 / 75
Systems of Linear Equations
Solving Systems of Equations – Row Reduction
Overview
Plan for Row Reduction
Notation for Row Reduction
Algorithm for Row Reduction
Matrices
Definition of a Matrix
Matrix Operations
Matrix Equations
The Superposition Principle
Elementary matrices
The Dimensions of a System of Equations, and Generalized Equivalence