(c)2024 C.

Karimianpour

MAT188 WEEK 2 Systems of Linear Equations

Chapter 1 Learning Standards

(1) I can perform row reduction on any matrix and reduce it to REF and RREF. (Computation)
(2) I can determine when a matrix is in REF or RRFF form. (Conceptual )
(3) Given an augmented matrix of a linear system, I can find the general solution to the system.
(Computation)
(4) Given the general solution to a system of linear equations, I can find particular solutions.
(Computation)
(5) Given the REF of an augmented matrix, I can determine the type of solution set the system has
(no solution, a unique solution, infinitely many solutions). (Conceptual )
(6) I can identify the solution type of a system based on information about the rank of its augmented
and coefficient matrices. (Conceptual )
(7) Given a system of linear equations in R2 or R3 , I can visualize the system and its general
solution. (Visual/Geometry)
(8) Given the matrix form A⃗x = ⃗b where ⃗b is a vector in R2 or R3 , I can visualize a particular solution
for the system by writing ⃗b as a linear combination of the columns of A. (Visual/Geometry)
(9) I can visualize the linear combination of vectors in R2 and R3 . (Visual/Geometry)
(10) I can interpret matrix-vector multiplication in terms of a linear combination of the columns
of the matrix. (Conceptual )
(11) I can interpret matrix-vector multiplication using dot products. (Conceptual )
(12) I can add matrices of the same size, multiply a matrix by a scalar and I can multiply a matrix by
a vector if the dimensions match up. (Computation)
(13) I can describe the general solution of a system parametrically and as a linear combination of
vectors using correct mathematical notation. (Writing)
(14) I can describe a system in matrix-vector multiplication notation. (Writing)

Vocabulary: system of linear equations, augmented matrix, coefficient matrix, elementary row reduc-
tion, Gaussian algorithm, (reduced) row-echelon form, solution type, rank, matrix algebra, matrix-vector
product, matrix form of a linear system, linear combination

Reading from the textbook: : Sec 1.1-1.3

1
 MAT188 WEEK 2 Systems of Linear Equations 2

Introduce
A duck costs four coins, five sparrows cost one coin, and a rooster costs one coin. Someone
purchases 100 birds for 100 coins. How many birds of each kind can they buy?

This problem appears in Key to Arithmetic by Jamshid Kashani, 15th century Persian mathematician.
If you denote the number of ducks, sparrows, and roosters by variables D, S, and R, to solve the problem
you need to find values for D, S, and R that simultaneously satisfy the following two equations:

D + S + R = 100 (number of birds)

1
4D + S + R = 100 (total cost)
5

Solving multiple equations simultaneously has been at the heart of many problems throughout history
and has enormous application to this day. Our main goal this week is to develop a technique to solve
a collection of linear equations simultaneously. In general, solving an equation is not an easy task, and
solving multiple equations at the same time is even harder. However, the equations we will consider in
this course are all linear. We will learn how to simultaneously solve any number of linear equations with
any number of variables. The techniques we learn this week are crucial to the rest of the course.

Definition (Linear Equation)

A linear equation with variables x1 , · · · , xm is an equation of the form a1 x1 +a2 x2 +· · ·+am xm = b

where a1 , · · · , am and b are scalars.
A (particular) solution to the equation is a tuple (c1 , · · · , cm ) that makes the equation true. That
is a1 c1 + a2 c2 + · · · + am cm = b

Now let’s consider a collection of such linear equations:

 
 2x1 + 4x2
 =8  4x1 − 8x2
 = 8x3
Example (2.1) 4x1 + 3x2 = 10 (2.2) 22x1 + 3x3 = 33

 2x − x 
1 2 =2  11x + 2x
2 3 = −2x1 + 1

Each collection is called a system of linear equations or just a linear system.

 MAT188 WEEK 2 Systems of Linear Equations 3

Definition (System of Linear Equations)

A system of linear equations or a linear system with m variables and n equations is a collection
of n linear equations in m variables and can be written in the form
a11 x1 + a12 x2 + · · · + a1m xm = b1
a21 x1 + a22 x2 + · · · + a2m xm = b2
.. .. ..
. . .
an1 x1 + an2 x2 + · · · + anm xm = bn .
Here aij ’s and di ’s are scalars and xi ’s are variables. A particular solution to a system of
linear equations is a tuple (c1 , · · · , cm ) that makes all n equations true simultaneously. That is
a11 c1 + a12 c2 + · · · + a1m cm = b1
a21 c1 + a22 c2 + · · · + a2m cm = b2
.. .. ..
. . .
an1 c1 + an2 c2 + · · · + anm cm = bn .
The set of all the possible solutions to a system of linear equations is called the solution set or
the general solution of the system.

Solution to Linear Systems. For each system of linear equations, the goal is to find all possible values
of xi ’s (unknows) that make all the linear equations hold simultaneously. We will call this the general
solution to the system. Although for the above examples you can use the substitution method that you
have learned in high school to find the general solution (stop reading and find the general solutions to the
systems in the above example), that method is not useful when equations have more unknowns - think
in the magnitude of hundreds of variables and equations!
To help, we can interpret linear equations geometrically. For example, the equation 2x1 + 3x2 = 5 with
only two variables x1 and x2 1 represents a line in R2 . The linear equation 2x1 + 3x
 2+ 4x3 = 0 represents
2
a plane that passes through the origin (0, 0, 0) and is perpendicular to the vector 3 in the 3D space R3 .
4
A collection of equations with the same number of variables therefore, can be thought of as a collection
of these geometrical objects.
In general, we can interpret a system of linear equations geometrically. Linear equations with n variables
represent flat objects in Rn . A system of linear equations represents a collection of such flat objects and
any solution to the system is a point (or more accurately a position vector of a point) that lies on ALL
of the objects in the system, a.k.a on their intersection. Hence, the general solution to the system is the
intersection of these geometrical flat objects.
Example These figures show you the geometrical interpretations of the systems from the previous Ex-
ample. Note that the first system with (two variables) is a collection of geometrical objects in R2 , whereas
the second one is a collection of geometrical objects in R3 (why?).

1You may be more familiar with calling your variable x and y and think about the line 2x + 3y = 5 instead. When
working with equations with many unknowns, it is more useful to use an indexed variable, like xi , for the unknowns.
 MAT188 WEEK 2 Systems of Linear Equations 4

In this course, we will learn how to “visualize” linear equations with more than three variables - but we
still have a long way to go before getting there.
Exercise Find the general solution for the following system of linear equations. What does each equation
represent geometrically? What does the general solution represent geometrically?
(
2x1 + 4x2 = 8
4x1 + 8x2 = 16

Solution. Note that we can eliminate the second equation by subtracting two times the first equation
from it. We get x1 = 4−2x2 , and x2 can be any real number. Geometrically, both equations represent
the same line. Hence their intersection is exactly that line.

To find the general solution of a linear system, we can manipulate the equations into a simpler system
with the same solution set, and solve the simpler system instead. There is a systematic way of simplifying
equations usually referred to as Gauss-Jordan elimination. The type of manipulations that do not
change the general solution of a system are: multiplying an equation by a scalar, adding a multiple of
an equation to another one, and switching the order of equations. In order to perform a series of such
manipulations to an equation, it is convenient to keep track of essential information from a linear system
using matrices. For now, let’s define a matrix to be an array of numbers. If the matrix had n rows and
m columns, we say it is n × m. There are two matrices associated with any system of linear equations:
the coefficient matrix and the augmented matrix, which combines the coefficient matrix with a column
of the constant terms. Here is an example:
Linear System Coefficient Matrix Augmented Matrix

 2x1 + 4x2 =8
   
Example  2 4 2 4 8
(2.3) 4x1 + 3x2 = 10 4 3  4 3 10
1 −1 1 −1 2

x − x
1 2 =2

The line that separates the last column in the augmented matrix is not part of the matrix notation. It
is there to remind us that this is an augmented matrix of a linear system, and the last column gives the
numbers on the right-hand side of the equal signs in the corresponding system, which are not coefficients
of any variable. The last column in the augmented matrix is called the augmented column.
Coefficient Matrix Augmented Matrix
In general, given the linear sys- 
a11 a12 · · · a1m
 
a11 a12 · · · a1m b1

tem (2.5), we can associate the  a21 a22 · · · a2m   a21 a22 · · · a2m b2 
following matrices to it:  .
 .. .. .. ..   .
 .. .. .. .. .. 
. . .  . . . .
an1 an2 · · · anm an1 an2 · · · anm bn
 MAT188 WEEK 2 Systems of Linear Equations 5

Watch a video: watch this video for an example of the coefficient and augmented matrix of a linear
system.

Exercise Write down the coefficient and the augmented matrices of the following linear system. Make
sure to first reorder the equations so that the variables are in the same order in all the equations.
4x1 − 8x2 = 8x3
22x1 + 3x3 = 33
11x2 + 2x3 = −2x1

Solution. First we pick an order for the variables and make sure that all equations are in that
order. It doesn’t matter which order we pick, as long as we are consistent and we keep a record of
which column of our augmented matrix corresponds to which variable. Here, let’s pick the natural
order indicated by their indices: x1 , x2 and x3 .
linear system
coefficient matrix augmented matrix
4x1 − 8x2 − 8x3 = 0    
4 −8 −8 4 −8 −8 0
22x1 + 0x2 + 3x3 = 33 22 0 3 22 0 3 33
2x1 + 11x2 + 2x3 = 0 2 11 2 2 11 2 0

The set of manipulations that one can perform to simplify a linear system can be translated into a
set of operations on the rows of the corresponding augmented matrix. We refer to these operations as
Elementary Row Operations. We can summarize them as follows:
(1) Interchanging two rows.
(2) Multiplying one row by a nonzero number.
(3) Replacing a row by itself plus a multiple of a different row.
To row reduce a matrix means to apply a collection of elementary row operations to it with the goal of
making it somehow simpler. Let B = [A|⃗b] be the augmented matrix of a system of linear equations with
the coefficient matrix A and the augmented column ⃗b. In Gauss-Jordan elimination, our goal is to row
reduce B into a matrix whose corresponding linear system (a) has the same solution set as the linear
system we began with and (b) is easy to solve. The best matrix type we can hope to row reduce into is
called Reduced Row Echelon Form (RREF). The linear system corresponding to a matrix in RREF is
easy to solve. Indeed, once B is reduced to RREF we can “read off” the general solution of the linear
system. Below is an example of a matrix and its RREF form. Think about the visual properties this
matrix has.
Example
     
1 0 2 4 −8 1 0 2 4 −8 1 0 2 0 0
0 1 −3 −1 6 
 0 1 3 −1 6 
 0 1 −3 0 4 
 row reduces to  row reduces to  
3 4 −6 8 0  −−−−−−−−−−−→ 0 0 0 3 −6 −−−−−−−−−−−→ 0 0 0 1 −2
0 −1 3 4 −12 0 0 0 0 0 0 0 0 0 0

Watch a video: watch this video that shows you how to apply Gauss-Jordan elimination to row reduce
a matrix into REF and RREF. 2
Let us define what we mean by RREF. A non-zero row in a matrix is a row with at least one non-zero
entry. The leftmost non-zero entry of a non-zero row in a matrix is called a leading entry.
2
You are expected to master the concept of how to row reduce matrices to RREF by hand over the next two weeks. To
help you check your work when you work out examples you can use this online row reduction tool.
 MAT188 WEEK 2 Systems of Linear Equations 6

Definition (REF and RREF)

A matrix is in row echelon form (REF) if it has the following properties

(1) All zero rows are at the bottom.
(2) The leading entry in each row is to the right of the leading entry of the row above.
(3) All entries below a leading entry are zero.
A matrix is in reduced row echelon form (RREF) if it is in REF form and in addition
(4) All the leading entries are 1. In this case, we call them “leading ones.”
(5) Each leading 1 is the only nonzero entry in its entire column.

Given a matrix B, there are many REF that B row reduces into. However, there is only one RREF
equivalent to B. We say that the RREF is unique. Note that the concepts of row reduction, REF, and
RREF make sense for any matrix, regardless of whether or not it is connected to a linear system.
 MAT188 WEEK 2 Systems of Linear Equations 7

Solidify
Now that we know how to modify a linear system into another easy-to-solve linear system via Gauss-
Jordan elimination, we can easily describe the general solution of our system.
Example
     
1 0 2 4 −8 1 0 2 4 −8 1 0 2 0 0
0 1 −3 −1 6  0 1 3 −1 6  0 1 −3 0 4 
3 4 −6 8 0 row reduces to 0

0 0 3 −6 row reduces to 
−2
−−−−−−−−−−→ −−−−−−−−−−→ 0 0 0 1
0 −1 3 4 −12 0 0 0 0 0 0 0 0 0 0

To describe the process, we need to establish some terminology. Remember that the first nonzero entry
in each row of a matrix is called the leading entry of that row. If that number is equal to 1, we call
it a leading 1. A pivot position is a location in a matrix that corresponds to a leading 1 in RREF
of that matrix. A pivot column is a column of the matrix that contains a pivot position. Suppose B
is the augmented matrix of a linear system. A variable in a linear system is called a leading variable
or a basic variable or a dependent variable if its corresponding column in B is a pivot column. A
variable is called a free variable if its corresponding column in B is a NOT a pivot column. In the
example above, x1 , x2 and x4 are basic variables and x3 is a free variable. To write the general solution
of our linear system, we translate the RREF of the augmented matrix into a system of equations, and
solve for basic variables in terms of the free variables. Any choice of value of free variables will result in
a particular solution to our system.
Watch a video: This video gives an example of finding the general solution of a system from RREF of
its augmented matrix in Example
The following summarizes the process of solving a system of linear equations.
• Write the system in a standard form by ordering the variables and transferring its infor-
mation to the corresponding augmented matrix B.
• Row reduce B to its RREF.
• Identify free variable and basic variables.
• Transform the reduced matrix back into equation form. You will get a linear system that
is, often, significantly simpler than the one you started with.
• Solve for basic variables in terms of free variables. That is, we describe each basis variable
in terms of free variables. This is always possible precisely because you have already row
reduced into RREF and hence there is only one basic variable in each equation.
• Let free variables run over all scalars.
• We typically write the general solution in set builder notation, and if possible interpret
it geometrically.

Solution Types. Do all linear systems have a solution? Can we examine how many solutions a system
of linear equations has without completely solving it? These are the questions we will consider next.
A system of equations is said to be consistent if there is at least one solution; it is inconsistent if
there are no solutions.
First off, let’s build some geometrical intuition about the possible number of solutions of a linear
system. You need to grab a pencil and a piece of paper and work on the following two questions.
Exercise Consider the system of two equations with two unknowns below.
(
ax1 + bx2 = e
cx1 + dx2 = f
 MAT188 WEEK 2 Systems of Linear Equations 8

You can visualize each equation as a line in R2 . The general solution is the intersection of these two lines.
What are the possibilities for two lines intersecting in R2 ? Can you think of an inconsistent example?
Write down your examples. What does the RREF of the system look like in each case?
Exercise Consider the system of three equations with three unknowns below.

 ax1 + bx2 + cx3 =
 j
dx1 + ex2 + f x3 = k

 gx + hx + ix =
1 2 3 l
You can visualize each equation as a plane in R3 . The general solution is the common intersection of these
planes. What are the possibilities for intersection of three plane in R3 ? Can you think of an inconsistent
example? What does the RREF of the system looks like in that case?
Indeed, what you noticed for the linear systems given above holds in general and is summarized in the
following important theorem.
Theorem (Solution Type). A linear system is inconsistent if and only if the reduced row-echelon form
of its augmented matrix contains the row 0 0 · · · 0 1, representing the equation 0 = 1. In other words, a
linear system is inconsistent if and only if the augmented column of the RREF of its augmented matrix
is a pivot column.
If a linear system is consistent, then it has either
• exactly one solution (if all the variables are leading).
• infinitely many solutions (if there is at least one free variable), or
Watch a video:: This video will walk you through determining the solution type of a system from REF.

Notice how the concept of leading ones comes into play. If you row reduced an augmented matrix of a
system and there is a leading one in the augmented column, then your system must be inconsistent. If
you row reduce an augmented matrix, and there is no leading one in the augmented column, but there is
a leading one in all other columns (all the columns of the coefficient matrix) then your system can not
have a free variable and hence there is exactly one solution. Reversely, if there are some columns in the
coefficient matrix without a leading one, provided that the system is consistent, there will be infinitely
many solutions. Let’s introduce a terminology for the number of leading ones in the RREF of a matrix.

Definition (Rank)

The rank of a matrix A is the number of leading ones in rref(A).

The Theorem (Solution Type) can be rephrased using this new term: Suppose A and B are the coefficient
and augmented matrix of a linear system respectively. Suppose A is an n × m matrix. Then the system
is inconsistent exactly when (if and only if) Rank(B) > Rank(A). The system is consistent exactly when
Rank(B) = Rank(A).

Exercise Write a condition on the rank of A and B that is equivalent to saying the corresponding system
is consistent with exactly one solution.
 MAT188 WEEK 2 Systems of Linear Equations 9

Expand
Next, we present some definitions and rules of matrix algebra, which will help us develop a matrix
language to explore linear equations. Recall that a matrix is an array of numbers. The size of a matrix
is (the number of its rows) × (the number of its columns). For example a 3 × 4 matrix has 3 rows and 4
columns. It is customary to label the entries of an n × m matrix with double subscripts. For example
 
a11 a12 a13 a14
A = a21 a22 a23 a24 
a31 a32 a33 a34
The first subscript refers to the row, and the second to the column: The entry aij is located in the i-th
row and the jth column. For short, we may write A = (aij ). Two matrices A and B are equal if they are
the same size and if all corresponding entries are equal: aij = bij for all i and j. If the number of rows
of a matrix A equals the number of columns (A is n × n), then A is called a square matrix, and the
entries a11 , a22 , · · · , ann form the (main) diagonal of A. A square matrix A is called diagonal if all its
entries above and below the main diagonal are zero; that is, aij = 0 whenever i ̸= j. A square matrix A
is called upper triangular if all its entries below the main diagonal are zero; that is, aij = 0 whenever
i exceeds j. Lower triangular matrices are defined analogously. A matrix whose entries are all zero is
called a zero matrix and is denoted by 0. A diagonal square matrix whose main diagonal entries are all
equal to 1, that is aii = 1 for all i is called an identity matrix and is denoted by In , where n indicates
that the matrix is n × n. We can add two matrices of the same size by adding up their corresponding
entries. We can multiply a scalar into a matrix by multiplying it into all the entries of the matrix.

Example
 
1 2 3
(1) B = 0 5 6 is a 3 × 3 square matrix. The entry on the second row, third column of B is
0 0 9
b23 =6. B is an upper triangular matrix.
1 0
(2) D= is a 2 × 2 diagonal matrix.
0 6
 
1 0
(3) I2 =
0 1
       
1 2 −1 1 0 3 2 2 2 3 6 −3
(4) Let C = and E = . Then C + E = and 3C = .
0 2 1 5 1 3 5 3 4 0 6 3

Matrix form of linear systems Recall that given two vectors ⃗v and w ⃗ in Rn with components v1 , · · · , vn
and w1 , · · · , wn respectively we define their dot product ⃗v · w
⃗ to be the scalar v1 w1 + v2 w2 + · · · + vn wn .
Note that definition of dot product isn’t row or column sensitive. We can dot product columns vectors
and/or row vectors.
   
Example Given ⃗v = 1 3 , w ⃗ = −1 4 . Then ⃗v · w ⃗ = −1 + 12 = 11.
 MAT188 WEEK 2 Systems of Linear Equations 10

Definition (Matrix-Vector Product)

Let A be an n × m matrix with row vectors w ⃗ n and ⃗x be a vector in Rm . Define

⃗ 1, · · · , w
_ w ⃗1 _ ⃗ 1 · ⃗x
w
   
_ w ⃗ 2 _ w⃗ · ⃗x 
A⃗x =  .  ⃗x =  2.  .
_ .. _  .. 
_ w
⃗n _ ⃗ n · ⃗x
w
Note that A⃗x is a column vector with n components, that is, a vector in Rn . The i-th component
of A⃗x is the dot product of the i-th row of A and the vector ⃗x.

Theorem (Algebraic rules for A⃗x). If A is an n × m matrix, ⃗x and ⃗y are vectors in Rm , and k is a
scalar, then
(1) A(⃗x + ⃗y ) = A⃗x + A⃗y ,
(2) A(k⃗x) = k(A⃗x)

Every system of linear equation can be translated into a matrix equation. We see this in an example.
Example Let’s look back at the linear system in (2.4). Consider the product of the coefficient matrix
of this system with the unknown vector that holds the variables x1 and x2 .
   
2 4   2x1 + 4x2
4 3  x1 = 4x1 + 3x2 
x2
1 −1 x1 − x2

Notice that the result of this matrix-vector product is a vector that holds the information on the left
hand side of the system. To obtain the full equations, we can equate this vector with the augmented
column
   
2 4   8
4 3  x1 = 10 .
x2
1 −1 2
Note that two vectors are equal exactly when all of their components are equal. That is,

 2x1 + 4x2 = 8

(2.4) 4x1 + 3x2 = 10

x − x
1 2 =2

Theorem (Matrix form of a linear system). We can write the linear system with augmented matrix [A|⃗b]
in matrix form as A⃗x = ⃗b.

Theorem (The product A⃗x in terms of the columns of A). If the column vectors of an n × m matrix A
are ⃗v1 , . . . , ⃗vm and ⃗x is a vector in Rm with components x1 , · · · , xm then

 x1
 

| | | x 
2
A⃗x = ⃗v1 ⃗v2
 · · · ⃗vm  
 ...  = x1⃗v1 + · · · + xm⃗vm

| | |
⃗xm
 MAT188 WEEK 2 Systems of Linear Equations 11

Definition (Linear Combination)

A linear combination of the finitely many vectors ⃗v1 , . . . , ⃗vn in Rn is an expression of the form
c1⃗v1 + · · · + cn⃗vn
where each ci is a scalar.

c1
 

By Theorem (Matrix form of a linear system) finding a particular solution ⃗c =  ...  to the system of
cm
linear equation with the augmented matrix [A|⃗b] is equivalent to finding a vector ⃗c such that A⃗c = ⃗b which
by Theorem (The product A⃗x in terms of the columns of A) and the definition of a linear combination is
equivalent to writing ⃗b as a linear combination of columns of the matrix A.

Summary: Let L be a linear system with m variables and n equations with the coefficient matrix A
and augmented matrix [A|⃗b].
• we can solve L by row reducing [A|⃗b] into RREF and read off the general solution.
• there are only three possible types of solution to L: no solution, a unique solution, or infinitely
many solutions.
• we can determine the solution type of L from any REF of [A|⃗b].
• L can be represented in matrix form as A⃗x = ⃗b. Here ⃗x is a vector variable in Rm .
• solving the system L is equivalent to finding all possible ⃗x in Rm such that A⃗x = ⃗b, which is
equivalent to finding all possible ways of writing ⃗b a linear combination of columns of A.
 MAT188 WEEK 2 Systems of Linear Equations 12

List of Definitions
Chapter 1 Definitions
Definition 1.1 (Linear Equation) A linear equation with variables x1 , · · · , xm is an equation of the
form a1 x1 + a2 x2 + · · · + am xm = b where a1 , · · · , am and b are scalars.
A (particular) solution to the equation is a tuple (c1 , · · · , cm ) that makes the equation true. That is
a1 c1 + a2 c2 + · · · + am cm = b

Definition 1.2 (System of Linear Equations) A system of linear equations or a linear system with
m variables and n equations is a collection of n linear equations in m variables and can be written in the
form
a11 x1 + a12 x2 + · · · + a1m xm = b1
a21 x1 + a22 x2 + · · · + a2m xm = b2
.. .. ..
. . .
an1 x1 + an2 x2 + · · · + anm xm = bn .
Here aij ’s and di ’s are scalars and xi ’s are variables. A particular solution to a system of linear
equations is a tuple (c1 , · · · , cm ) that makes all n equations true simultaneously. That is
a11 c1 + a12 c2 + · · · + a1m cm = b1
a21 c1 + a22 c2 + · · · + a2m cm = b2
.. .. ..
. . .
an1 c1 + an2 c2 + · · · + anm cm = bn .
The set of all the possible solutions to a system of linear equations is called the solution set or the
general solution of the system.

Definition 1.3 (Pivot) Let A be a matrix in REF form. An entry of A is called a pivot entry if it is
the first non-zero entry of a row. A column of A is called a pivot column if it contains a pivot entry. If
A is also in RREF, pivot entries are called leading ones.
Definition 1.4 (Basic and Free Variables) Given a system of linear equations with m variables and n
equations, with coefficient matrix A and augmented matrix [A|⃗b]
(1) a variable is called a free variable if its corresponding column in rrefA does not contain a pivot
(or a leading one).
(2) a variable is called a leading variable or a basic variable or a dependent variable if its
corresponding column in rrefA contains a pivot (or a leading one).
.

Definition 1.5 (Identity Matrix) The identity matrix In is an n × n matrix whose diagonal entries
are 1 and off-diagonal entries are 0.

Definition 1.6 (Zero Matrix) The zero matrix 0n×m is an n × m matrix with all zero entries.
Definition 1.7 (REF and RREF) A matrix is in row echelon form (REF) if it has the following
properties
(1) All zero rows are at the bottom.
(2) The leading entry in each row is to the right of the leading entry of the row above.
(3) All entries below a leading entry are zero.
A matrix is in reduced row echelon form (RREF) if it is in REF form and in addition
 MAT188 WEEK 2 Systems of Linear Equations 13

(4) All the leading entries are 1. In this case, we call them “leading ones.”
(5) Each leading 1 is the only nonzero entry in its entire column.

Definition 1.8 (Rank) The rank of a matrix A is the number of leading ones in rref(A).
Definition 1.9 (Matrix-Vector Product) Let A be an n × m matrix with row vectors w
⃗ 1, · · · , w
⃗ n and ⃗x
be a vector in Rm . Define
_ w
⃗1 _ ⃗ 1 · ⃗x
w
   
_ w
⃗ 2 _ w⃗ · ⃗x 
A⃗x =  ..  ⃗x =  2.  .
_ . _  .. 
_ w ⃗n _ ⃗ n · ⃗x
w
Note that A⃗x is a column vector with n components, that is, a vector in Rn . The i-th component of A⃗x
is the dot product of the i-th row of A and the vector ⃗x.

Definition 1.10 (Linear Combination) A linear combination of the finitely many vectors ⃗v1 , . . . , ⃗vn
in Rn is an expression of the form
c1⃗v1 + · · · + cn⃗vn
where each ci is a scalar.