1. SYSTEMS OF LINEAR EQUATIONS

The theory of linear equations plays an important and motivating role in the subject of this course. In fact, many problems in linear algebra are equivalent to studying a system of linear equations. Thus the techniques introduced in this chapter will be applicable to the more abstract treatment given later. On the other hand, some of the results of the abstract treatment will give us new insights into the structure of “concrete” systems of linear equations.

This chapter investigates systems of linear equations and describes in detail the Gaussian elimination algorithm which is used to find their solution. Matrices, together with certain operations on them, are also introduced here, since they are closely related to systems of linear equations and their solutions.

All our equaitons will involve specific numbers called constants or scalars. For simplicity, we will assume in this chapter that all our scalars are real numbers. The set of real numbers will be denoted, as usual, by ℝ. The solutions of our equations will also involve n-tupes

$u = [\begin{matrix} u_{1} \\ u_{2} \\ ⋮ \\ u_{n} \end{matrix}]$

of real numbers called column vectors. The set of all such n-tuples is denoted by ℝⁿ. We note that the results in this chapter also hold for equations over the complex numbers ℂ.

1.1. Linear equations and their solutions

By linear equations in the unknowns or variables x1, x2, …, x_n we mean an equation that can be written in the following standard form:

$a_{1} x_{1} + a_{2} x_{2} + \dots + a_{n} x_{n} = b (1.1)$

where a₁, a₂, …, a_n, b are scalars. The scalar a_k is called the coefficient of x_k and b is called the independent term of the equation.

A solution of the linear equation (1.1) is a list of scalars (s₁, s₂, …, s_n) with the property that the following statement (obtained by substituting each si for xi in the equation) is true:

a₁ s₁ + a₂ s₂ + … + a_n s_n = b.

This set of values is then said to satisfy the equation.

The set of all such solutions is called solution set or general solution, or, simply, the solution of the equation.

The above notions implicitly assume that there is an ordering of the variables. If the number of variables is small, then, in order to avoid subscripts, we will usually use the variables x, y, as ordered to denote two unknowns, x, y, z, as ordered, to denote three unknowns, x, y, z, t, as ordered, to denote four unknowns, and x, y, z, s, t, as ordered, to denote five unknowns.

Example 1.1

The equations

$4 x_{1} - 5 x_{2} + 2 = x_{1} and x_{2} = 2 (\sqrt{6} - x_{1}) + x_{3}$

are both linear because they can be rearranged algebraically as in (1.1):

$3 x_{1} - 5 x_{2} = - 2 and 2 x_{1} + x_{2} - x_{3} = 2 \sqrt{6}$

The equations

$4 x_{1} - 5 x_{2} = x_{1} x_{2} and x_{3} = 2 \sqrt{x_{1}} - 6$

are not linear because of the presence of x₁ x₂ in the first equation and $\sqrt{x_{1}}$ in the second.

Example 1.2

The equation x + 2y - 4z + t = 3 is linear in the four unknowns x, y, z, t. The list of scalars (3, 2, 1, 0) is a solution of the equation since

3 + 2(2) - 4(1) + 0 = 3

is a true statement. However the list (1, 2, 4, 5) is not a solution of the equation since

1 + 2(2) - 4(4) + 5 = 3

is not a true statement.

At this point, your algebra professor expects you to have carefully and thoroughly read the introduction section of these notes.

Definition 1.1

A linear equation is said to be degenerate if it has the form

0 x₁ + 0 x₂ + … + 0 x_n = b,

that is, if every coefficient is equal to zero.

The solutions of degenerate equations are described in the following theorem.

Theorem 1.1

Consider the degenerate linear equation 0 x₁ + 0 x₂ + … + 0 x_n = b.

1. If the constant b ≠ 0, then the equation has no solution.

2. If the constant b = 0, then every list of scalars (s₁, s₂, …, s_n) is a solution.

Proof. We begin by proving the first statement. Let (s₁, s₂, …, s_n) be any list of scalars.

Suppose that b ≠ 0. Substituting x_i = s_i in the equation we obtain:

0 s₁ + 0 s₂ + … + 0 s_n = b or 0 + 0 + … + 0 = b or 0 = b.

This is not a true statement since b ≠ 0. Hence no list of scalars is a solution.

Now we prove the second statement. Suppose b = 0. Substituting (s₁, s₂, …, s_n) in the equation we obtain:

0s₁ + 0s₂ + … + 0s_n = 0 or 0 + 0 + … + 0 = 0 or 0 = 0,

which is a true statement. Thus every list of scalars is a solution, as claimed.

1.2. Systems of linear equations and elementary operations

We now consider a system of m linear equations, say, L₁, L₂, …, L_m, in the n unknowns x₁, x₂, …, x_n which can be put in the standard form:

$\begin{aligned} L_{1} & : a_{11} x_{1} + a_{12} x_{2} + \dots + a_{1 n} x_{n} = b_{1} \\ L_{2} & : a_{21} x_{1} + a_{22} x_{2} + \dots + a_{2 n} x_{n} = b_{2} \\ \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \\ L_{m} & : a_{m 1} x_{1} + a_{m 2} x_{2} + \dots + a_{m n} x_{n} = b_{m} \end{aligned} (1.2)$

where the a_ij, b_i are constants.

A solution (or particular solution) of the above system is a list of scalars (s₁, s₂, …, s_n) which is simultaneously a solution of all the equations of the system. The set of all such solutions is called the solution set or the general solution of the system.

Example 1.3

Consider the system of equations:

L₁ : x + 2y − 4z + t = 3,
L₂ : 2x + y + 5z − 4t = 13.

We can verify that (3, 2, 1, 0) is a solution by substituting x = 3, y = 2, z = 1, and t = 0 in the equations of the system. Similarly, we can verify that (3, 2, 1, −3) is not a solution.

Systems of linear equations in the same unknowns are said to be equivalent if the systems have the same solution set. One way of producing a system which is equivalent to a given system, with linear equations L₁, L₂, …, L_m, is by applying a sequence of the following three basic operations called elementary operations:

Definition 1.2: Elementary operations

(E1) Interchange the ith equation and the jth equation: L_i ↔ L_j.

(E2) Multiply the ith equation by a non zero scalar k : kL_i → L_i, k ≠ 0.

(E3) Replace the ith equation by itself plus k times the jth equation: (kL_j + L_i) → L_i.

Remark 1.1

It is important that you understand that if one system of equations is obtained from another by applying elementary operations, then the two systems will be equivalent. This means that they will have the same solution set. The reason for this is that each elementary operation is reversible. The basic application of this fact is that we can replace one system with an equivalent system that is easier to solve.

Roughly speaking, the simplest equivalent version of a system is obtained using the elementary operations as follows. Use the x₁ term in the first equation of a system to eliminate the x₁ terms in the other equations. Then use the x₂ term in the second equation to eliminate the x₂ terms in the other equations, and so on, until you finally obtain the least amount of variables in common among the equations. The following example illustrates this strategy. Make sure to understand that we replace x₁, x₂, x₃ with x, y, z.

Example 1.4

The solution of the system

L₁ : x + 2y - 4z = -4,
L₂ : 5x+11y-21y= -22
L₃ : 3x - 2y + 3z = 11

is obtained as follows:

Use x in the first equation to eliminate it from the other equations. First we replace L₂ with -5L₁ + L₂:

$\begin{aligned} L_{1} : x + 2 y - 4 z = - 4 Operations: \\ L_{1} : x + 2 y - 4 z = - 4 \end{aligned}$

$L_{2} : 5 x + 11 y - 21 z = - 22 (- 5 L_{1} + L_{2}) \to L_{2} new L_{2} : y - z = - 2$

$L_{3} : 3 x - 2 y + 3 z = 11 L_{3} : (3 x - 2 y + 3 z = 11$

Next we keep the new L₂ and replace L₃ with -3L₁ + L₃:

$\begin{aligned} L_{1} : x + 2 y - 4 z = - 4 Operations: \\ L_{1} : x + 2 y - 4 z = - 4 \end{aligned}$

$L_{2} : y - z = - 2 (- 3 L_{1} + L_{3}) \to L_{3} L_{2} : y - z = - 2$

$L_{3} : 3 x - 2 y + 3 z = 11 new L_{3} : - 8 y + 15 z = 23$

Use y in the second equation to eliminate it from the other equations. We replace L₁ with -2L₂ + L₁ and replace L₃ with 8L₂ + L₃. We show both replacements at once:

$\begin{array}{rrcrr} L_{1} : & x + 2 y - 4 z = - 4 & Operations: & new L_{1} : & x - 2 z = 0 \\ L_{2} : & y - z = - 2 & (- 2 L_{2} + L_{1}) \to L_{1} & L_{2} : & y - z = - 2 \\ L_{3} : & - 8 y + 15 z = 23 & (8 L_{2} + L_{3}) \to L_{3} & new L_{3} : & 7 z = 7 \end{array}$

At this point, it is evident that z = 1 and that you can use this to solve for the other two variables. Nevertheless, our philosophy of using elementary operations to reach a system of equations with the least amount of variables in common among them will be the keystone to developing all the theory in the rest of the course. So, even if it seems somewhat unnecessary right row, we will continue to solve the system with elementary operations for illustrative purposes.

To simplify calculations, we can replace L₃ with $\frac{1}{7} L_{3}$ :

$\begin{array}{rrrr} L_{1} : x - 2 z = 0 Operations: L_{1} : \\ L_{2} : y - z - 2 z = 0 \\ L_{3} : 7 z = 7 \frac{1}{7} L_{3} \to L_{3} L_{2} : \\ y - z = - 2 \\ new L_{3} : z = 1 \end{array}$

Use z in the third equation and use it eliminate from the other equations. We replace L₁ with 2L₃ + L₁ and replace L₂ with L₃ + L₂ :

$\begin{array}{rrcrr} L_{1} : & x - 2 z = 0 & Operations: & new L_{1} : & x = 2 \\ L_{2} : & y - z = - 2 & (2 L_{3} + L_{1}) \to L_{1} & new L_{2} : & y = - 1 \\ L_{3} : & z = 1 & (L_{3} + L_{2}) \to L_{2} & L_{3} : & z = 1 \end{array}$

We have clearly arrived at the simplest equivalent system of equations. Notice that the three equations have no variables in common. This is the ideal scenario since we can readily deduce that the solution of the system is x = 2, y = −1, z = 1.

Suppose that you start with the system of equation (1.2) and use elementary operations to obtain a simpler equivalent version such that the equations have the least amount of variables in common. Then the first variable with non zero coefficient in each equation is called leading variable and the variables that are not leading variables are called free variables.

Recall from the beginning of this chapter that we have implicitly assumed that there is an ordering of the variables. Moreover, there may be more than one simpler system equivalent to (1.2). For this reason, we impose some additional requirements for writing a simpler equivalent version of (1.2). First, we will require that the equations should be rearranged so that the leading variables are order not only horizontally from left to right but also vertically from top to bottom. This can be accomplished by interchanging the necessary equations (recall that interchanging equations is an elementary operation). Second, we will require that the coefficient of each leading variable is 1^*. This is possible by rescaling the necessary equations. These two additional conditions ensure that the resulting simpler equivalent system is the simplest one, independently of the sequence of elementary operations that you use to arrive at it.

This notion of simplest equivalent system will be, in our opinion, the most useful tool at your disposal to develop and understand the material in this course. We will illustrate how to obtain such simplest equivalent system in the following examples.

Example 1.5

Consider the following system of equations:

$\begin{array}{lr} L_{1} : & y - 4 z = 8, \\ L_{2} : & 2 x - 3 y + 2 z = 1 \\ L_{3} : & 5 x - 8 y + 7 z = 1 \end{array}$

1. Find the simplest system of equations that is equivalent to the given one.

2. Indicate the leading variables and the free variables.

3. Find the solution of the given system of equation.

1. First, you need to remember that the variables need to be in the correct order horizontally and vertically, and that the coefficients of the leading variables should be equal to 1. This means that the variable x should appear as the leading variable of the first equation. This is not the case for the given system. One way to fix this is to interchange L₁ with either L₂ or L₃. Either option is good.

$L_{1} : y - 4 z = 8 Operations: new L_{1} : 2 x - 3 y + 2 z = 1$

$L_{2} : 2 x - 3 y + 2 z = 1 L_{1} \leftrightarrow L_{2} new L_{2} : y - 4 z = 8$

$L_{3} : 5 x - 8 y + 7 z = 1 L_{3} : 5 x - 8 y + 7 z = 1$

The coefficient of x in L₁ should be 1, so we rescale as follows:

$\begin{array}{rrrrr} L_{1} : 2 x - 3 y + 2 z = 1 Operations: new L_{1} : x - \frac{3}{2} y + z = \frac{1}{2} \\ L_{2} : y - 4 z = 8 \frac{1}{2} L_{1} \leftrightarrow L_{1} L_{2} : y - 4 z = 8 \\ L_{3} : 5 x - 8 y + 7 z = 1 L_{3} : 5 x - 8 y + 7 z = 1 \end{array}$

Use x in the first equation to eliminate it from the other equations.

$\begin{array}{rrrrr} L_{1} : x - \frac{3}{2} y + z = \frac{1}{2} Operations: L_{1} : x - \frac{3}{2} y + z = \frac{1}{2} \\ L_{2} : y - 4 z = 8 (- 5 L_{1} + L_{3}) \to L_{3} L_{2} : y - 4 z = 8 \\ L_{3} : 5 x - 8 y + 7 z = 1 new L_{3} : - \frac{1}{2} y + 2 z = - \frac{3}{2} \end{array}$

Use y in the second equation and use it eliminate from the other equations.

$\begin{array}{rrrrr} L_{1} : x - \frac{3}{2} y + z = \frac{1}{2} Operations: new L_{1} : x - 5 z = \frac{25}{2} \\ L_{2} : y - 4 z = 8 (\frac{3}{2} L_{2} + L_{1}) \to L_{1} L_{2} : y - 4 z = 8 \\ L_{3} : - \frac{1}{2} y + 2 z = - \frac{3}{2} new L_{3} : 0 = - \frac{5}{2} \end{array}$

We have ran out of non-degenerate equations, there is the least amount of variables in common among the equation, the variables are in the correct order, and the coefficients of the leading variables are 1. Therefore we have found the simplest equivalent system.

2. The leading variables are x and y because they are the first variables in each nondegenerate equation with non zero coefficient. The remainder variable, z, is a free variable.

3. It turns out that $L_{3} : 0 = - \frac{5}{2}$ is a degenerate equation with no solution which means that there is no values for x, y, z that will simultaneously satisfy all equations. Therefore, the given system of equations has no solution.

Before continuing on to the next example, we need to discuss free variables further. Suppose that after reducing (1.2) to its simplest equivalent version, you find that all of its degenerate equations (if any) are of the form 0 x₁ + 0 x₂ + … + 0x_n = 0, and that at least one of its variables is a free variable. Then the system has infinite number of solutions since each of the free variables may be assigned any real number. The general solution of the system is obtained as follows. Once the system has been reduced to its simplest form, arbitrary values, called parameters, are assigned to the free variables, and the non free variables can be solved in terms of these parameters.

Example 1.6

Find the general solution of the system

L₁ : x + 4y − 3z + 2t = 5
L₂ : −2x − 8y + 7z − 8t = −8

If the solution of the system is not obvious, then our best option to find it is to reduce the system to its simplest form. This is done as follows: First, we eliminate x from the second equation.

$\begin{array}{rrcrr} L_{1} : & x + 4 y - 3 z + 2 t = 5 & Operations: & L_{1} : & x + 4 y - 3 z + 2 t = 5 \\ L_{2} : & - 2 x - 8 y + 7 z - 8 t = - 8 & (2 L_{1} + L_{2}) \to L_{2} & L_{2} : & z - 4 t = 2 \end{array}$

It is not possible to eliminate y from L₁ since the leading variable of L₂ is z, which means that our next task is to eliminate z from L₁.

$\begin{array}{rrrrr} L_{1} : x + 4 y - 3 z + 2 t = 5 Operations: L_{1} : x + 4 y - 10 t = 11 \\ L_{2} : z - 4 t = 2 (3 L_{2} + L_{1}) \to L_{1} L_{2} : z - 4 t = 2 \end{array}$

The last system is the simplest equivalent version of the original one. Make sure to understand why this is so. The first variables with nonzero coefficients in each equation are x and z which means that these are the leading variables and that y and t are free variables. From the discussion above, we deduce that the system has infinite number solutions and the general solution is obtained as follows. We assign arbitrary values to the free variables y and t, say,

y = λ and t = μ, where λ, μ ∈ ℝ.

Then we solve for x and z in terms of λ and μ. We write the general solution:

x = 11 - 4λ + 10μ,
y=λ,
z = 2 + 4μ,
t = μ.

It is always a good idea to check that your final result is indeed the correct answer. In this case, you should verify that these expressions for x, y, z, t satisfy both equations of the original system. If you obtain two true statements then your answer is correct.

We finish this section by answering two fundamental questions about systems of linear equations:

1. Does at least one solution exist?

2. If a solution exists, is it the only one; that is, is the solution unique?

The answer to these questions are stated as a theorem.

Theorem 1.2

Any system of linear equations has either: (i) a unique solution, (ii) no solution, or (iii) an infinite number of solutions.

Proof. Given any system of linear equations, we apply elementary operations to reduce it to its simplest equivalent form. After this is done, we may get one of the following cases:

I. There is at least one degenerate equation of the form 0 x₁ + 0 x₂ + … + 0 x_n = b with b ≠ 0. This degenerate equation has no solution and, consequently, the system has no solution.

II. There is no degenerate equation of the form 0 x₁ + 0 x₂ + … + 0 x_n = b with b ≠ 0. We have two subcases.

a. There is at least one free variable. This means that the system has an infinite number of solutions.

b. There are no free variables. This means that all the variables are leading variables. This is only possible if the simplest equivalent version is of the form

$\begin{matrix} x_{1} = s_{1} \\ x_{2} = s_{2} \\ ⋮ \\ x_{n} = s_{n} \end{matrix}$

where s₁, s₂, …, s_n are real numbers. Then each variable has a unique value which means that the solution of the system is unique.

No other cases are possible, which proves the theorem.

Remark 1.2

Case II in the previous proof does not say that all the equations are non-degenerate. It only says that there are no degenerate equations that have no solution. In fact, this case may include degenerate equations of the form 0 x₁ + 0 x₂ + … + 0 x_n = 0. In the future, make sure you understand what a definition, theorem or proof says and does not say.

In light of Theorem 1.2, systems of linear equations can be classified according to the existence of solutions. A system is said to be consistent if it has at least one solution, and is said to be inconsistent if it has no solution.

1.3. Matrices and matrix operations

A matrix is a rectangular array of numbers:

$A = [\begin{array}{cccc} a_{11} & a_{12} & \dots & a_{1 n} \\ a_{21} & a_{22} & \dots & a_{2 n} \\ \dots & \dots & \dots & \dots \\ a_{m 1} & a_{m 2} & \dots & a_{m n} \end{array}]$

Such matrix may be denoted by A = (a_ij). Note that the element a_ij, called the (i, j)-entry, appears in the i-th row and the j-th column. A matrix with m rows and n columns is called and m × n matrix.

The first non zero entry of a row is called its leading entry. A row whose all of its entries consists of zeros has no leading entries.

Definition 1.3

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

1. All zero rows, if any, are at the bottom of the matrix.

2. Each leading entry of a row is in a column to the right of the leading entry of the row above it.

3. All entries in a column below a leading entry are zeros.

If a matrix in echelon form satisfies the following additional conditions, then it is in reduced echelon form (or row reduced echelon form):

4. The leading entry in each non zero row is 1.

5. Each leading 1 is the only non zero entry in its column.

Example 1.7

The following matrices are in echelon form. The leading entries (represented with ) may have any non zero value; the non leading entries (represented with ∗) may have any values (including zero).

The following matrices are in reduced echelon form because the leading entries are 1’s, and there are 0’s below and above each leading 1, that is, each leading 1 is the only non zero entry in its column.

Just like with systems of equations, we can operate with the rows of a matrix by applying the following three basic operations.

Definition 1.4: Elementary row operations

(E1) Interchange the ith row and the jth row: Ri ↔ Rj.

(E2) Multiply the ith row by a non zero scalar k: k Ri → Ri, k ≠ 0.

(E3) Replace the ith row by itself plus k times the jth row: (k Rj + Ri) → Ri.

A matrix A is said to be row equivalent to a matrix B, written A ∼ B, if B can be obtained from A by applying a finite sequence of elementary row operations.

Any non zero matrix is row equivalent to more than one matrix in echelon form that can be obtained by using different sequences of row operations. However, the reduced echelon form one obtains from a matrix is unique, independently of the row operations used to obtain it. We state this as a theorem without proof.

Theorem 1.3

Each matrix is row equivalent to one and only one reduced echelon matrix.

When row operations on a matrix produce an echelon form, further row operations to obtain the reduced echelon form do not change the positions of the leading entries. Since the reduced echelon form is unique, the leading entries are always in the same positions in any echelon form obtained from a given matrix. These leading entries correspond to leading 1’s in the reduced echelon form.

Definition 1.5

A pivot position in a matrix A is a location in A that corresponds to the leading 1 in the row reduced echelon form of A. A pivot column is a column of A that contains a pivot position.

Heuristically, pivot positions are non zero entries of a matrix that are used to create zeros as needed via elementary row operations to obtain a row reduced echelon form.

Example 1.8

Consider the matrix

$A = [\begin{array}{llll} 1 & 2 & - 3 & 0 \\ 2 & 4 & - 2 & 2 \\ 3 & 6 & - 4 & 3 \end{array}]$

1. Find an echelon form of A.

2. Find the row reduced echelon form of A.

3. Indicate the pivot positions of A.

1. There are more than one possible echelon form; each one is obtained depending on the sequence of elementary row operations used. We compute one of them. First, we start by using a₁₁ = 1 as pivot to create 0’s below a₁₁, that is, apply -2R₁ + R₂ → R₂ and −3R₁ + R₃ → R₃ to obtain

$[\begin{array}{cccc} 1 & 2 & - 3 & 0 \\ 0 & 0 & 4 & 2 \\ 0 & 0 & 5 & 3 \end{array}]$

Now use the new (2, 3)-entry as a pivot to create 0’s below it, that is, apply $- \frac{5}{4} R_{2} + R_{3} \to$ R₃ to obtain

$[\begin{array}{cccc} 1 & 2 & - 3 & 0 \\ 0 & 0 & 4 & 2 \\ 0 & 0 & 0 & \frac{1}{2} \end{array}]$

The matrix is now in echelon form.

2. We apply further elementary row operations to the echelon form above to obtain the unique row reduced echelon form. Each pivot position should be 1, so we apply $\frac{1}{4} R_{2} \to R_{2}$ and 2R₃ → R₃ to obtain

$[\begin{array}{cccc} 1 & 2 & - 3 & 0 \\ 0 & 0 & 1 & \frac{1}{2} \\ 0 & 0 & 0 & 1 \end{array}] .$

At this point, the fastest way to obtain the row reduced echelon form is to apply ¹₂ R3 + R₂ → R₂ to obtain

$[\begin{array}{cccc} 1 & 2 & - 3 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array}],$

followed by applying 3R₂ + R₁ → R₁ to obtain

$[\begin{array}{llll} 1 & 2 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array}] .$

The matrix is now in row reduced echelon form.

3. The locations in A that correspond to the leading 1’s in the row reduced echelon form are a₁₁ = 1, a₂₃ = −2, and a₃₄ = 3. These are the pivot positions of A.

Matrices will usually be denoted by capital letters A, B, … Two matrices A and B are equal, written A = B, if they have the same size, that is, the same number of rows and columns, and if the corresponding elements are equal. Thus the equality of two m × n matrices is equivalent to a system of mn equalities, one for each pair of elements. For instance, the statement

$[\begin{array}{cc} x + y & 2 z + 2 \\ x - y & z - 2 \end{array}] = [\begin{array}{ll} 3 & 5 \\ 1 & 4 \end{array}]$

is equivalent to the following system of equations:

x + y = 3
x − y = 1
2z + w = 5
z − 2 = 4.

The solution of the system is x = 2, y = 1, z = 3, w = -1. (Do not just accept that these are the answers. Try to solve the system by yourself.)

A matrix with one row is also referred to as a row matrix, and with one column as a column vector. In particular, a scalar can be viewed as a 1 × 1 matrix.

Let A = (a_ij) and B = (bij) be two matrices with the same size, say, m × n matrices. The sum of A and B, written A + B, is obtained by adding the corresponding entries:

$A + B = [\begin{array}{cccc} a_{11} + b_{11} & a_{12} + b_{12} & \dots & a_{1 n} + b_{1 n} \\ a_{21} + b_{21} & a_{22} + b_{22} & \dots & a_{2 n} + b_{2 n} \\ \dots & \dots & \dots & \dots \\ a_{m 1} + b_{m 1} & a_{2 m} + b_{2 m} & \dots & a_{m n} + b_{m n} \end{array}],$

or, more compactly, A + B = (a_ij + bij).

The product of a matrix A = (a_ij ) by a scalar k, written kA, is the matrix obtained by multiplying each entry of A by k: kA = (k aij). We also define -A = (−1) A and A − B = A + (−B).

The m × n matrix whose entries are all zeros is called the zero matrix. We usually write the zero matrix as 0 and its size is usually understood from context. The zero matrix is similar to the scalar 0. For any matrix A, A + 0 = 0 + A = A.

Basic properties of matrices under the operations of matrix addition and scalar multiplication follow.

Theorem 1.4

For any m × n matrices A, B, C and scalars α, β,

a) (A+B) +C = A+ (B+C)	b) A + 0 = A
c) A + (-A) = 0	d) A + B = B + A
e) α (A + B) = α A + α B	f) (α + β) A = α A + β A
g) (αβ)A = α(βA)	h) 1 A = A

Proof. We only prove the first property here. The rest are left as an exercise for the reader. Let A = (a_ij), B = (bij), and C = (cij) be matrices of the same size. Then

(A + B) + C = (a_ij + b_ij) + c_ij = a_ij + (b_ij + c_ij) = A + (B + C).

There are several ways to define matrix-vector multiplication. You have probably seen one way in high school. Nevertheless, we choose the following definition because it is the most convenient for developing the theoretical ideas throughout the course. It should not be difficult for you verify that the definition you learned in high school is equivalent to the one we present here.

Definition 1.6

If A is an m × n matrix, with columns a₁, …, a_n, and if x is a column vector in ℝⁿ, then the product of A and x, denoted by Ax, is defined as follows,

$A x = [\begin{array}{lll} a_{1} & a_{2} \dots a_{n} \end{array}] [\begin{matrix} x_{1} \\ ⋮ \\ x_{n} \end{matrix}] = x_{1} a_{1} + x_{2} a_{2} + \dots + x_{n} a_{n}$

In words, the product of a matrix A and a column vector x is the column vector that is equal to the weighted sum of the columns of A using the entries x as weights. Note that Ax is defined only if the number of columns of A equals the number of entries in x.

We take this opportunity to give this type of weighted sum a special name. Given vectors v₁, v₂, …, v_p in ℝⁿ and given scalars c₁, c₂, …, c_p, the vector y ∈ ℝⁿ defined by

y = c₁v₁ + c₂v₂ + … +c_pv_p

is called a linear combination of v₁, v₂, …, v_p with weights c₁, c₂, …, c_p.

Example 1.9

We compute

$[\begin{array}{lll} 3 & 1 & 0 \\ 2 & 2 & 5 \\ 1 & 0 & 4 \end{array}] [\begin{array}{l} 2 \\ 1 \\ 3 \end{array}] .$

By the definition of matrix-vector multiplication, we must compute the linear combination of the columns of the matrix using the entries of the vector as weights. Therefore,

$[\begin{array}{lll} 3 & 1 & 0 \\ 2 & 2 & 5 \\ 1 & 0 & 4 \end{array}] [\begin{array}{l} 2 \\ 1 \\ 3 \end{array}] = 2 [\begin{array}{l} 3 \\ 2 \\ 1 \end{array}] + 1 [\begin{array}{l} 1 \\ 2 \\ 0 \end{array}] + 3 [\begin{array}{l} 0 \\ 5 \\ 4 \end{array}] = [\begin{matrix} 7 \\ 21 \\ 14 \end{matrix}] .$

Remark 1.3

A common error that we see repeatedly is students treating vectors and matrices like fractions. For instance, some students will notice that the entries of the vector in the final result of the previous example share a common factor of 7; then they will proceed to “cancel” this common factor out like they would do with the numerator and denominator of a fraction and write the following as a final answer:

$[\begin{array}{lll} 3 & 1 & 0 \\ 2 & 2 & 5 \\ 1 & 0 & 4 \end{array}] [\begin{array}{l} 2 \\ 1 \\ 3 \end{array}] = [\begin{array}{l} 1 \\ 3 \\ 2 \end{array}] .$

This is, of course, absolutely wrong. If you write this, your algebra professor will realize that life is too short, immediately resign from teaching, and join a traveling circus. But not before changing your grade in the course to a zero.

Example 1.10

The product of a row matrix and a column vector is

$[\begin{array}{llll} u_{1} & u_{2} & \dots & u_{n} \end{array}] [\begin{matrix} v_{1} \\ v_{2} \\ ⋮ \\ v_{n} \end{matrix}] = u_{1} v_{1} + u_{2} v_{2} + \dots + u_{n} v_{n}$

Make sure you understand how the definition was used to find this product.

The properties of the matrix-vector multiplication in the next theorem are important and will be used throughout the course.

Theorem 1.5

For an m × n matrix A, vectors u and v in ℝⁿ, and scalar c,

a. A(u + v) = A u + A v

b. A (cu) = c (A u)

Proof. Let ui and vi be the i-th entries of u and v, respectively. To prove the first statement, use the definition of matrix-vector multiplication to compute A(u + v):

$\begin{aligned} A (u + v) & = [\begin{array}{ll} a_{1} a_{2} \dots a_{n} \end{array}] [\begin{array}{c} u_{1} + v_{1} \\ u_{2} + v_{2} \\ ⋮ \\ u_{n} + v_{n} \end{array}] \\ = (u_{1} + v_{1}) a_{1} + (u_{2} + v_{2}) a_{2} + \dots + (u_{n} + v_{n}) a_{n} \\ = (u_{1} a_{1} + u_{2} a_{2} + \dots + u_{n} a_{n}) + (v_{1} a_{1} + v_{2} a_{2} + \dots + v_{n} a_{n}) \\ = A u + A v \end{aligned}$

The proof of the second statement is left as an exercise for the reader.

You have certainly seen how to multiply matrices in high school. Nevertheless, such a definition is not very useful for theoretical purposes. We now give an equivalent abstract definition of matrix multiplication.

Definition 1.7

Let A be an m × p matrix, and let B be a p × n matrix. The product of A and B, denoted by AB, is the unique m × n matrix such that, for every vector x ∈ ℝⁿ, (AB) x = A (B x).

It is possible to find a (less abstract) representation of AB in terms of matrix-vector multiplication. We provide this representation in the following theorem.

Theorem 1.6

Let A be an m × p matrix, and let B be a p × n matrix with columns b₁, b₂, …, b_n, then the product AB is the unique m × n matrix whose columns are Ab₁, Ab₂, …, Ab_n. That is,

AB= [Ab₁ Ab₂ ... Ab_n].

Proof. Following the definition of AB, let x be an arbitrary vector in ℝⁿ. Let

$y = B x = [\begin{array}{llll} b_{1} & b_{2} & \dots & b_{n} \end{array}] [\begin{matrix} x_{1} \\ x_{2} \\ ⋮ \\ x_{n} \end{matrix}] = x_{1} b_{1} + x_{2} b_{2} + \dots + x_{n} b_{n}$

Then,

$\begin{aligned} A B x & = A (B x) = A y \\ = A (x_{1} b_{1} + x_{2} b_{2} + \dots + x_{n} b_{n}) \\ = x_{1} A b_{1} + x_{2} A b_{2} + \dots + x_{n} A b_{n} \\ = [\begin{array}{llll} A b_{1} & A b_{2} & \dots & A b_{n} \end{array}] x . \end{aligned}$

This is true for every choice of x and each product A b_i is uniquely determined. This proves the theorem.

Example 1.11

Compute AB, where

$A = [\begin{array}{cc} 2 & 3 \\ 1 & - 5 \end{array}] and B = [\begin{array}{ccc} 4 & 3 & 6 \\ 1 & - 2 & 3 \end{array}]$

Write B = [b₁ b₂ b₃], and compute

$\begin{aligned} A b_{1} & = [\begin{array}{cc} 2 & 3 \\ 1 & - 5 \end{array}] [\begin{matrix} 4 \\ 1 \end{matrix}], & A b_{2} & = [\begin{array}{cc} 2 & 3 \\ 1 & - 5 \end{array}] [\begin{array}{c} 3 \\ - 2 \end{array}], \end{aligned} \begin{array}{ll} A b_{3} & = [\begin{array}{cc} 2 & 3 \\ 1 & - 5 \end{array}] [\begin{matrix} 6 \\ 3 \end{matrix}] . \\ = [\begin{array}{c} 11 \\ - 1 \end{array}] \end{array}$

Then,

$A B = [\begin{array}{lll} A b_{1} & A b_{2} & A b_{3} \end{array}] = [\begin{array}{ccc} 11 & 0 & 21 \\ - 1 & 13 & - 9 \end{array}] .$

The following theorem lists the standard properties of matrix multiplication. We note that I_m denotes the unique m × m, called the identity matrix, such that I_m x = x for all x in ℝⁿ. The identity matrix has the following representation:

$I_{m} = [\begin{array}{ccccc} 1 & 0 & 0 & \dots & 0 \\ 0 & 1 & 0 & \dots & 0 \\ 0 & 0 & 1 & \dots & 0 \\ ⋮ & ⋮ & ⋮ & ⋱ \\ 0 & 0 & 0 & \dots & 1 \end{array}]$

Theorem 1.7

Let A be an m × n matrix, and let B and C have sizes for which the indicated sums and products are defined.

a.	A(BC) = (AB)C	(associative law of multiplication)
b.	A(B + C) = AB + AC	(left distributive law)
c.	(B+C)A = BA + CA	(right distributive law)
d.	r(AB) = (rA)B = A(rB)	for any scalar r
e.	I_mA = A = AI_m	(identity for matrix multiplication)

Proof. Let C = [c₁ … c_p]. By Theorem 1.6,

BC = B c₁ … B c_p,
A(BC) = A (B c₁) ... A (B c_p),

By the definition of matrix multiplication, A (B x) = (A B) x for all x, so

A(BC) = (AB) c₁ … (AB)c_p = (AB)C.

The rest of the properties are left for the reader to prove.

The left-to-right order in matrix products is critical because AB and BA are usually not the same. On one hand, the sizes of A and B are such that AB is well defined but BA may not be even possible to compute. For instance, if A is a 3 × 5 matrix and B is a 5 × 1 matrix, then we can compute AB because the number of columns of A is equal to the number of rows of B, but it is not possible to compute BA because the number of columns of B is not equal to the number of rows of A. on the other hand, the columns of AB are linear combinations of the columns of A, whereas the columns of BA are constructed from the columns of B. If AB = BA, we say that A and B commute with one another.

Remark 1.4

We have already discussed that, in general, matrix products do not commute, that is, AB ≠ BA. There two more important differences between matrix algebra and ordinary algebra that you need to keep in mind.

1. The cancellation laws do not hold for matrix multiplication. That is, if AB = AC, then it is not true, in general, that B = C. For instance, let

$A = [\begin{array}{cc} 2 & - 3 \\ - 4 & 6 \end{array}], B = [\begin{array}{ll} 8 & 4 \\ 5 & 5 \end{array}], C = [\begin{array}{cc} 5 & - 2 \\ 3 & 1 \end{array}] .$

Verify that AB = AC and yet B ≠ C.

2. If a product AB is the zero matrix, you cannot conclude, in general, that either A = 0 or B = 0. For instance, let

$A = [\begin{array}{cc} 3 & - 6 \\ - 1 & 2 \end{array}] B = [\begin{array}{ll} 2 & 6 \\ 1 & 3 \end{array}]$

Verify that AB = 0 and yet A ≠ 0 and B ≠ 0.

Every now and then we need to compute a particular entry of the product AB without computing the whole matrix product. In this case, we do so by recalling the matrix multiplication rule you learned in high school (which can be deduced from Theorem 1.6).

Theorem 1.8

Let A = (a_ij) be an m × p matrix and let B = (b_ij) be a p × n matrix. If (AB)_ij denotes the (i, j)-entry in AB, then

$(A B)_{i j} = [\begin{array}{llll} a_{i 1} & a_{i 2} & \dots & a_{i p} \end{array}] [\begin{matrix} b_{1 j} \\ b_{2 j} \\ ⋮ \\ b_{p j} \end{matrix}] = a_{i 1} b_{1 j} + a_{i 2} b_{2 j} + \dots + a_{i p} b_{p j}$

Given an m × n matrix A = (a_ij), the transpose of A, denoted by A^⊤, is the n × m matrix $A^{⊤} = (a_{i j}^{⊤})$ , where $a_{i j}^{⊤} = a_{j i}$ . That is, A^⊤ is obtained by changing the columns of A into columns, or, equivalently, by changing the rows of A into columns. So, if we write A = [a₁ … a_n], then

$A^{⊤} = [\begin{matrix} a_{1}^{⊤} \\ ⋮ \\ a_{n}^{⊤} \end{matrix}]$

Theorem 1.9

Let A and B denote matrices whose sizes are appropriate for the following sums and products.

a. (A^⊤)^⊤ = A

b. (A+B)^⊤ =A^⊤+B^⊤

c. For any scalar r, (rA)^⊤ = rA^⊤

d. (AB)^⊤ = B^⊤A^⊤

Proof. We only prove the last statement. The rest are left for the reader as exercises. First, observe that

${[(A B)^{⊤}]}_{i j} = (A B)_{j i} = a_{j 1} b_{1 i} + a_{j 2} b_{2 i} + \dots + a_{j p} b_{p i} = [\begin{array}{llll} b_{1 i} & b_{2 i} & \dots & b_{p i} \end{array}] [\begin{matrix} a_{j 1} \\ a_{j 2} \\ ⋮ \\ a_{j p} \end{matrix}] .$

On the other hand,

${[B^{⊤} A^{⊤}]}_{i j} = [\begin{array}{llll} b_{i 1}^{⊤} & b_{i 2}^{⊤} & \dots & b_{i p}^{⊤} \end{array}] [\begin{matrix} a_{1 j}^{⊤} \\ a_{2 j}^{⊤} \\ ⋮ \\ a_{p j}^{⊤} \end{matrix}] = [\begin{array}{llll} b_{1 i} & b_{2 i} & \dots & b_{p i} \end{array}] [\begin{matrix} a_{j 1} \\ a_{j 2} \\ ⋮ \\ a_{j p} \end{matrix}]$

which shows that the (i, j)-entry of (AB)^⊤ is equal to the corresponding entry of B^⊤A^⊤. Therefore, (AB)^⊤ = B^⊤A^⊤.

1.4. Systems of linear equations and matrices

Consider again a system of m linear equations and n unknowns:

$\begin{aligned} L_{1} & : a_{11} x_{1} + a_{12} x_{2} + \dots + a_{1 n} x_{n} = b_{1}, \\ L_{2} & : a_{21} x_{1} + a_{22} x_{2} + \dots + a_{2 n} x_{n} = b_{2}, \\ \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \\ L_{m} & : a_{m 1} x_{1} + a_{m 2} x_{2} + \dots + a_{m n} x_{n} = b_{m} . \end{aligned} (1.3)$

We can interpret (1.3) the equations resulting from considering two equal column vectors:

$[\begin{matrix} a_{11} x_{1} + a_{12} x_{2} + \dots + a_{1 n} x_{n} \\ a_{21} x_{1} + a_{22} x_{2} + \dots + a_{2 n} x_{n} \\ ⋮ \\ a_{m 1} x_{1} + a_{m 2} x_{2} + \dots + a_{m n} x_{n} \end{matrix}] = [\begin{matrix} b_{1} \\ b_{2} \\ ⋮ \\ b_{n} \end{matrix}] .$

Then, L_i is obtained by setting the i-th entry of the vector on the left side equal to the i-th entry of the vector on the right side. We can also operate on the left-hand side vector as follows:

$\begin{aligned} [\begin{array}{c} a_{11} x_{1} + a_{12} x_{2} + \dots + a_{1 n} x_{n} \\ a_{21} x_{1} + a_{22} x_{2} + \dots + a_{2 n} x_{n} \\ ⋮ \\ a_{m 1} x_{1} + a_{m 2} x_{2} + \dots + a_{m n} x_{n} \end{array}] & = [\begin{array}{c} a_{11} x_{1} \\ a_{21} x_{1} \\ ⋮ \\ a_{m 1} x_{1} \end{array}] + [\begin{array}{c} a_{12} x_{2} \\ a_{22} x_{2} \\ ⋮ \\ a_{m 2} x_{2} \end{array}] + \dots + [\begin{array}{c} a_{1 n} x_{n} \\ a_{2 n} x_{n} \\ ⋮ \\ a_{m n} x_{n} \end{array}] \\ = x_{1} [\begin{array}{c} a_{11} \\ a_{21} \\ ⋮ \\ a_{m 1} \end{array}] + x_{2} [\begin{array}{c} a_{12} \\ a_{22} \\ ⋮ \\ a_{m 2} \end{array}] + \dots + x_{n} [\begin{array}{c} a_{1 n} \\ a_{2 n} \\ ⋮ \\ a_{m n} \end{array}] \\ = [\begin{array}{cccc} a_{11} & a_{12} & \dots & a_{1 n} \\ a_{21} & a_{22} & \dots & a_{2 n} \\ \dots & \dots & \dots & \dots \\ a_{m 1} & a_{m 2} & \dots & a_{m n} \end{array}] [\begin{array}{c} x_{1} \\ x_{2} \\ ⋮ \\ x_{n} \end{array}] \end{aligned}$

So, if we let

$A = [\begin{array}{cccc} a_{11} & a_{12} & \dots & a_{1 n} \\ a_{21} & a_{22} & \dots & a_{2 n} \\ \dots & \dots & \dots & \dots \\ a_{m 1} & a_{m 2} & \dots & a_{m n} \end{array}], x = [\begin{matrix} x_{1} \\ x_{2} \\ ⋮ \\ x_{n} \end{matrix}], b = [\begin{matrix} b_{1} \\ b_{2} \\ ⋮ \\ b_{n} \end{matrix}],$

we can write (1.3) more compactly as the vector equation

$A x = b (1.4)$

The matrix A is called the matrix coefficient, x is the unknown vector, and b is the independent term. We make the following key observation:

Observation 1.1

Every solution of the system (1.3) is solution of the vector equation (1.4), and vice versa.

The augmented matrix of (1.3) is the following matrix:

$[\begin{array}{ll} A & b \end{array}] = [\begin{array}{ccccc} a_{11} & a_{12} & \dots & a_{1 n} & b_{1} \\ a_{21} & a_{22} & \dots & a_{2 n} & b_{2} \\ \dots & \dots & \dots & \dots & \dots \\ a_{m 1} & a_{m 2} & \dots & a_{m n} & b_{n} \end{array}]$

That is, the augmented matrix of the system (1.3) is the matrix which consists of the matrix A concatenated by the vector b. Observe that the system (1.3) is completely determined by the vector equation (1.4) which, in turn, is completely determined by its augmented matrix. In light of this, we have the following theorem.

Theorem 1.10

If A is an m × n matrix, with columns a₁, …, a_n, and if b is in ℝ^m, the matrix equation

Ax = b

has the same solution set as the vector equation

x₁ a₁ + x₂ a₂ + … + x_n a_n = b

which, in turn, has the same solution set as the system of linear equations whose augmented matrix is

a₁ a₂ … a_n b.

From now on, we will use the language and theory of matrices to study systems of linear equations. We reframe the question of existence of solutions in terms of matrices. Given a particular vector b, it is easy to deduce from Theorem 1.10 that the equation Ax = b has a solution if and only if b is a linear combination of the columns of A.

Example 1.12

Consider the following system of equations

x₁ + 2x₂ + 7x₃ = b₁
-2x₁ + 5x₂ + 4x₃ = b₂,

where b₁ and b₂ are arbitrary real numbers. Let

$A = [\begin{array}{ccc} 1 & 2 & 7 \\ - 2 & 5 & 4 \end{array}], x = [\begin{array}{l} x_{1} \\ x_{2} \\ x_{2} \end{array}], and b = [\begin{array}{l} b_{1} \\ b_{2} \end{array}] .$

Then the system can be written more compactly as the vector equation Ax = b. Notice that b is a generic vector. Keeping this vector arbitrary will allow us to deduce general results about the system of equations since these results will not depend on a particular choice of b. Here, we will study the existence of solutions by solving the system with a generic vector b. To do so, we row reduce the augmented [A b] as follows:

$[\begin{array}{cccc} 1 & 2 & 7 & b_{1} \\ - 2 & 5 & 4 & b_{2} \end{array}] \sim [\begin{array}{cccc} 1 & 2 & 7 & b_{1} \\ 0 & 9 & 18 & 2 b_{1} + b_{2} \end{array}] \sim [\begin{array}{cccc} 1 & 2 & 7 & b_{1} \\ 0 & 1 & 2 & \frac{2 b_{1} + b_{2}}{9} \end{array}] \sim [\begin{array}{cccc} 1 & 0 & 3 & \frac{5 b_{1} - 2 b_{2}}{9} \\ 0 & 1 & 2 & \frac{2 b_{1} + b_{2}}{9} \end{array}]$

The last matrix is the row reduced echelon form which, in turn, corresponds to an augmented matrix of a simpler equivalent system of equations. In fact, it corresponds to the simplest equivalent system. Indeed, if we write down the system that is determined by the row reduced echelon form:

$\begin{aligned} x_{1} + 3 x_{3} = \frac{5 b_{1} - 2 b_{2}}{9} \\ x_{2} + 2 x_{3} = \frac{2 b_{1} + b_{2}}{9} \end{aligned}$

it becomes clear that the equations have the least amount of variables in common, the variables are in the correct order, and the coefficients of the leading variables are 1’s. The presence of the free variable x₃ indicates that this system has an infinite number of solutions, which are as follows:

$\begin{aligned} x_{1} = \frac{5 b_{1} - 2 b_{2}}{9} - 3 λ, \\ x_{2} = \frac{2 b_{1} + b_{2}}{9} - 2 λ, \\ x_{3} = λ, λ \in R . \end{aligned}$

Observe that it is possible to find a solution without putting any restriction on the vector b, which allows us to conclude that for each b in ℝ², the equation Ax = b has a solution. Moreover, by the definition of the product A x, we can write

$[\begin{array}{l} b_{1} \\ b_{2} \end{array}] = (\frac{5 b_{1} - 2 b_{2}}{9} - 3 λ) [\begin{matrix} 1 \\ - 2 \end{matrix}] + (\frac{2 b_{1} + b_{2}}{9} - 2 λ) [\begin{array}{l} 2 \\ 5 \end{array}] + λ [\begin{array}{l} 7 \\ 4 \end{array}], λ \in R .$

The most useful interpretation of the equation above is that each b in ℝ² can be written as a linear combination of the columns of A. In this case, there is an infinite number of ways to write each b as a linear combination of the columns of A since there is an infinite number of options for the choice of values for the parameter λ.

You should always be on the look out for important observations when studying the material. In the previous example, observe that the pivot positions in the row reduced echelon form correspond to leading variables and that non pivot positions correspond to free variables. A moment’s thought should convince you that this is true in general. This is such an important observation that we must highlight it.

Observation 1.2

The pivot columns of coefficient matrix of a system correspond to the leading variables of the system, and the non pivot columns correspond to free variables. Therefore, a system has an infinite number of solutions if its coefficient matrix has at least one non pivot column. Conversely, if every column of the coefficient matrix is a pivot column, then every variable is a leading variable and, thus, the system has a unique solution.

Warning: The last sentence of the observation above is about the columns of the coefficient matrix not about the augmented matrix nor about the rows of the coefficient matrix. On one hand, if every column of the augmented matrix is a pivot column, then it has a row of the form

[0 0 … 0 1]

which corresponds to a degenerate equation of the form 0 = 1, which clearly has no solution. On the other hand, the uniqueness of the solution cannot be deduced if the coefficient matrix has a pivot in every row. The system in Example 1.12 has an augmented matrix with a pivot in every row and yet it has an infinite number of solutions.

Example 1.13

Let

$A = [\begin{array}{ccc} 1 & 3 & 4 \\ - 4 & 2 & - 6 \\ - 3 & - 2 & - 7 \end{array}] and b = [\begin{array}{l} b_{1} \\ b_{2} \\ b_{3} \end{array}] .$

Is the equation A x = b consistent for all possible b?

Row reduce the augment matrix of A x = b:

$[\begin{array}{cccc} 1 & 3 & 4 & b_{1} \\ - 4 & 2 & - 6 & b_{2} \\ - 3 & - 2 & - 7 & b_{3} \end{array}] \sim [\begin{array}{cccc} 1 & 3 & 4 & b_{1} \\ 0 & 14 & 10 & 4 b_{1} + b_{2} \\ 0 & 7 & 5 & 3 b_{1} + b_{3} \end{array}] \sim [\begin{array}{cccc} 1 & 3 & 4 & b_{1} \\ 0 & 14 & 10 & 4 b_{1} + b_{2} \\ 0 & 0 & 0 & b_{1} - \frac{1}{2} b_{2} + b_{3} \end{array}]$

The third row in the last matrix corresponds to a degenerate equation of the form

$0 = b_{1} - \frac{1}{2} b_{2} + b_{3}$

If we proceed further applying elementary operations, this row will not change. Therefore, the system is consistent only if the entries of b satisfy the equation $0 = b_{1} - \frac{1}{2} b_{2} + b_{3}$ . Clearly, not every b satisfies this condition (an easy example is b = [1 0 0]^⊤). If A had a pivot in all three rows, we would not care about the calculations in the augmented column because in this case an echelon form of the augmented matrix could not have a row such as [0 0 0 1] corresponding to a degenerate equation with no solutions.

1.5. Solution sets of linear systems

The system of linear equations (1.3) is said to be homogeneous if all the independent terms are equal to zero, that is, if it can be written in the form A x = 0, where A is its m × n coefficient matrix and 0 is the zero vector in ℝ^m. The homogeneous equation A x = 0 always has a solution, namely x = 0, the zero vector in ℝⁿ, called the trivial solution. Any other solution, if it exists, is called a non trivial solution.

For a given equation A x = 0, the important question is whether there is a non trivial solution. A non trivial solution exists if and only if the trivial solution is not a unique solution. The proof of Theorem 1.2 leads immediately to the following fact:

Remark 1.5

The homogeneous equation A x = 0 has a non trivial solution if and only if the equation has at least one free variable.

Example 1.14

Determine if the following homogeneous system has a non trivial solution. Then describe the solution set.

x + 2y - 3z + w = 0,
x - 3y + z - 2w = 0,
2x + y - 3z + 5w = 0.

Row reduce the augmented matrix to row reduced echelon form:

$\begin{aligned} [\begin{array}{ccccc} 1 & 2 & - 3 & 1 & 0 \\ 1 & - 3 & 1 & - 2 & 0 \\ 2 & 1 & - 3 & 5 & 0 \end{array}] \sim [\begin{array}{ccccc} 1 & 2 & - 3 & 1 & 0 \\ 0 & - 5 & 4 & - 3 & 0 \\ 0 & - 3 & 3 & 3 & 0 \end{array}] \sim [\begin{array}{ccccc} 1 & 2 & - 3 & 1 & 0 \\ 0 & - 5 & 4 & - 3 & 0 \\ 0 & 1 & - 1 & - 1 & 0 \end{array}] \\ \sim [\begin{array}{ccccc} 1 & 2 & - 3 & 1 & 0 \\ 0 & 1 & - 1 & - 1 & 0 \\ 0 & - 5 & 4 & - 3 & 0 \end{array}] \sim [\begin{array}{ccccc} 1 & 0 & - 1 & 3 & 0 \\ 0 & 1 & - 1 & - 1 & 0 \\ 0 & 0 & - 1 & - 8 & 0 \end{array}] \sim [\begin{array}{ccccc} 1 & 0 & - 1 & 3 & 0 \\ 0 & 1 & - 1 & - 1 & 0 \\ 0 & 0 & 1 & 8 & 0 \end{array}] \\ \sim [\begin{array}{ccccc} 1 & 0 & 0 & 11 & 0 \\ 0 & 1 & 0 & 7 & 0 \\ 0 & 0 & 1 & 8 & 0 \end{array}] \end{aligned}$

The last matrix is the row reduced echelon form which, in turn, is the augmented matrix of the simplest equivalent system:

x + 11w = 0,
y+ 7w = 0,
z + 8w = 0.

Notice that w is a free variable. It is possible to deduce this in advanced from the row reduced echelon form since the fourth column is not a pivot column (which means that w is not a leading variable; thus, w is free). By the previous remark, the system has a non trivial solution. After solving the simplified system, we deduce that the solution set consists of

x = -11λ,
y = -7λ,
z = -8λ,
w = λ ∈ ℝ,

or, equivalently, the solution of the equation Ax = 0 where A is the coefficient matrix of the system, consists of all vector in ℝ⁴ of the form

$x = [\begin{array}{r} - 11 λ \\ - 7 λ \\ - 8 λ \\ λ \end{array}] = λ [\begin{array}{r} - 11 \\ - 7 \\ - 8 \\ 1 \end{array}], λ \in R .$

That is, the solution of Ax = 0 consists of all the scalar multiples of the vector

$[\begin{array}{r} - 11 \\ - 7 \\ - 8 \\ 1 \end{array}] .$

Example 1.15

A single linear equation can be treated as a system with one equation. Describe the solution set of the homogeneous system

10x₁ - 3x₂ - 2x₃ = 0.

Obviously, there is no need to write its augmented matrix or to apply elementary row operations. We can directly solve for x₁ (respecting the implicit ordering of the variables). In other words, x₁ is the leading variable and the rest of variables are free:

$\begin{aligned} x_{1} = \frac{3}{10} λ + \frac{1}{5} μ, λ, μ \in R, \\ x_{2} = λ, \\ x_{3} = μ . \end{aligned} .$

As a vector equation A x = 0 (here 0 = 0 ∈ ℝ), where

A= [10 -3 -2]

the general solution is

$x = [\begin{matrix} \frac{3}{10} λ + \frac{1}{5} μ \\ λ \\ μ \end{matrix}] = λ [\begin{matrix} \frac{3}{10} \\ 1 \\ 0 \end{matrix}] + μ [\begin{array}{l} \frac{1}{5} \\ 0 \\ 1 \end{array}] .$

In words, the general solution consists of all possible linear combinations of two vectors:

$[\begin{matrix} \frac{3}{10} \\ 1 \\ 0 \end{matrix}], [\begin{array}{l} \frac{1}{5} \\ 0 \\ 1 \end{array}] .$

When a non homogeneous system has more than one solution, two distinct solutions satisfy a simple but important relation between them, and the set of solutions of the homogeneous system characterizes this relation. We make this precise in the following theorem.

Theorem 1.11

Suppose that the equation A x = b is consistent for some given non zero b, and let u and v be two distinct solutions. Then there is some h satisfying A h = 0, such that u = v + h.

Proof. Let u and v be two distinct solutions of the equation A x = b. Then

A(u − v) = b − b = 0.

This means that h = u - v is a solution of the homogeneous equation A x = 0. This proves the theorem.

Another way to sate the previous theorem is as follows.

Theorem 1.12

Suppose that the equation A x = b is consistent for some given non zero b, and let v be a particular solution. Then the solution set of A x = b consists of the set of all vectors of the form u = v + h, where h is any solution of the homogeneous equation A x = 0.

Warning: The previous theorem applies only when A x = b. If the equation has no solution, then the solution set is empty.

Example 1.16

Recall the system in Example 1.12:

x₁ + 2x₂ + 7x₃ = b₁
-2x₁ + 5x₂ + 4x₃ = b₂,

which is consistent for each b₁, b₂ ∈ ℝ. Its matrix coefficient is

$A = [\begin{array}{ccc} 1 & 2 & 7 \\ - 2 & 5 & 4 \end{array}],$

and, in vector form, its general solution is

$x = [\begin{matrix} \frac{5 b_{1} - 2 b_{2}}{9} \\ \frac{2 b_{1} + b_{2}}{9} \\ 0 \end{matrix}] + λ [\begin{matrix} - 3 \\ - 2 \\ 1 \end{matrix}], λ \in R .$

We now verify that this general solution is of the form u + h, where u satisfies A u = b and h satisfies A h = 0. Let

$u = [\begin{matrix} \frac{5 b_{1} - 2 b_{2}}{9} \\ \frac{2 b_{1} + b_{2}}{9} \\ 0 \end{matrix}] and h = λ [\begin{matrix} - 3 \\ - 2 \\ 1 \end{matrix}] .$

Then

$A u = [\begin{array}{ccc} 1 & 2 & 7 \\ - 2 & 5 & 4 \end{array}] [\begin{matrix} \frac{5 b_{1} - 2 b_{2}}{9} \\ \frac{2 b_{1} + b_{2}}{9} \\ 0 \end{matrix}] = (\frac{5 b_{1} - 2 b_{2}}{9}) [\begin{matrix} 1 \\ - 2 \end{matrix}] + (\frac{2 b_{1} + b_{2}}{9}) [\begin{array}{l} 2 \\ 5 \end{array}] + 0 [\begin{array}{l} 7 \\ 4 \end{array}] = [\begin{array}{l} b_{1} \\ b_{2} \end{array}],$

and

$A h = [\begin{array}{ccc} 1 & 2 & 7 \\ - 2 & 5 & 4 \end{array}] [\begin{matrix} - 3 λ \\ - 2 λ \\ λ \end{matrix}] = - 3 λ [\begin{matrix} 1 \\ - 2 \end{matrix}] - 2 λ [\begin{array}{l} 2 \\ 5 \end{array}] + λ [\begin{array}{l} 7 \\ 4 \end{array}] = [\begin{array}{l} 0 \\ 0 \end{array}] .$

1.6. Invertible matrices

An n × n matrix A is said to be invertible if there is an n × n matrix C such that

CA = I and AC = I

where I = I_n is the identity matrix. In this case, C is an inverse of A.

Theorem 1.13

The inverse of an n × n matrix A is unique.

Proof. Suppose that C and B are both inverses of A. Then,

B = BI = B(AC) = (BA)C = IC = C.

Therefore, B = C which means that the inverse is uniquely determined by A.

Since the inverse of a matrix A is uniquely determined by A, we can assign it a specia notation. This unique inverse is denoted by A^-1, so that

A^-1A = I and AA^-1 = I.

A matrix that is not invertible is sometimes called a singular matrix, and an invertible matrix is called a non singular matrix.

Invertible matrices are indispensable in linear algebra – mainly for algebraic calculations and formula derivation. In particular, they play an important role in solving systems of equations.

Theorem 1.14

If A is an invertible n × n matrix, then for each b ∈ ℝⁿ, the equation A x = b has the unique solution x = A^-1b.

Proof. For any b ∈ ℝⁿ, x = A^-1b is solution since:

Ax = A(A^-1b) = (AA^-1) b = Ib = b.

If u is another solution, then

A(u - A^-1b) = b - b = 0.

Therefore,

u-A^-1b = I(u - A^-1b) = A^-1A (u - A^-1b) = A^-10 = 0.

This implies u = A^-1b, which means that the solution x = A^-1b is unique.

The following theorem provides three useful properties of invertible matrices.

Theorem 1.15

a. If A is an invertible matrix, then A^-1 is invertible and

(A^-1)^-1 = A.

b. If A and B are n × n invertible matrices, then AB is invertible and

(AB)^-1 = B^-1A^-1.

c. If A is invertible, then A^⊤ is invertible and

(A^⊤)^-1 = (A^-1)^⊤.

Proof. a. We already know that A satisfies

AA^-1 = I and A^-1A = I.

Therefore, the inverse of A^-1 is A, that is, (A^-1)^-1 = A.

b. On one hand,

(B^-1A^-1)AB = B^-1(A^-1A)B = B^-1IB = B^-1B = I.

On the other hand,

AB(B^-1A^-1) = A(B^-1B)A^-1 = AIA^-1 = AA^-1 = I.

Therefore, (AB)^-1 = B^-1A^-1.

c. We compute

(A^-1)^⊤A^⊤ = (AA^-1)^⊤ = I^⊤ = I.

Similarly,

A^⊤(A^-1)^⊤ = (A^-1A)^⊤ = I^⊤ = I.

Therefore, (A^⊤)^-1 = (A^-1)^⊤.

We have treated inverses abstractly. Now we describe a procedure for computing them.

Theorem 1.16

If A is an invertible matrix, then

[A I] ∼ [I A^-1].

Consequently, A is invertible if and only if it is row equivalent to the identity matrix I.

Proof. Write I = [e₁e₂… e_n]. Recall that A is invertible if and only if there is a unique matrix C such that

AC = I and CA = I.

Write C = [c₁ c₂… c_n]. Since

AC= Ac₁ Ac₂… Ac_n,

then AC = I if and only if all the equations

A c_i = e_i for i = 1, 2, …, n.

have unique solutions. Each equation has an augmented matrix [A e_i]. We can apply the same sequence of row elementary operations to reduce all the augmented matrix to a row reduced echelon form. But instead of applying these same sequences of row operations n times, we could just apply them once to the augmented matrix

[A e₁e₂… e_n] = [A I ].

Recall that each A c_i = e_i has a unique solution if and only if all the columns of A are pivot columns implying that A ∼ I and

[A I] ∼ [I c₁ c₂… c_n] = [A C].

This proves the theorem because C = A^-1.

We use this procedure to recover the well-known formula for the inverse of a 2 × 2 matrix.

Example 1.17

Let

$A = [\begin{array}{ll} a & b \\ c & d \end{array}] .$

Suppose that ad - bc ≠ 0. We compute

$\begin{aligned} [\begin{array}{ll} A & I_{2} \end{array}] = [\begin{array}{llll} a & b & 1 & 0 \\ c & d & 0 & 1 \end{array}] \sim [\begin{array}{cccc} a c & b c & c & 0 \\ a c & a d & 0 & a \end{array}] \sim [\begin{array}{cccc} a c & b c & c & 0 \\ 0 & a d - b c & - c & a \end{array}] \\ \sim [\begin{array}{cccc} a c & b c & c & 0 \\ 0 & 1 & \frac{- c}{a d - b c} & \frac{a}{a d - b c} \end{array}] \sim [\begin{array}{cccc} a c & 0 & c + \frac{b c^{2}}{a d - b c} & \frac{- a b c}{a d - b c} \\ 0 & 1 & \frac{- c}{a d - b c} & \frac{a}{a d - b c} \end{array}] \\ = [\begin{array}{cccc} a c & 0 & \frac{a c d}{a d - b c} & \frac{- a b c}{a d - b c} \\ 0 & 1 & \frac{- c}{a d - b c} & \frac{a}{a d - b c} \end{array}] \sim [\begin{array}{cccc} 1 & 0 & \frac{d}{a d - b c} & \frac{- b}{a d - b c} \\ 0 & 1 & \frac{- c}{a d - b c} & \frac{a}{a d - b c} \end{array}] . \end{aligned}$

Hence,

$A^{- 1} = [\begin{array}{cc} \frac{d}{a d - b c} & \frac{- b}{a d - b c} \\ \frac{- c}{a d - b c} & \frac{a}{a d - b c} \end{array}] .$

We must admit that we cheated. In the last reduction step, we divided by ac without knowing if ac ≠ 0. Nevertheless, it is possible to deduce the same formula for A^-1 when ac = 0. We leave it to the reader to treat this case. (Hint: consider two cases: a ≠ 0, c = 0 and a = 0, c ≠ 0. The case a = c = 0 is excluded because this implies ad - bc = 0.)

1.7. Determinants

Each n × n matrix A is assigned a special scalar called the determinant of A, denoted by det A or |A|. We give a recursive definition of a determinant.

Definition 1.8

The determinant of a 1 × 1 matrix A = [a] is defined as |A| = a. For n ≥ 2, the determinant of an n × n matrix A = (a_ij) is defined as

$\det A = \sum_{j = 1}^{n} (- 1)^{1 + j} a_{1 j} \det A_{1 j}$

where A_ij is the (n - 1) × (n - 1) matrix obtained from A by deleting the i-th row and the j-th column.

Example 1.18

Let us recover the well-known expression for the determinant of a 2 × 2 matrix. Let

$A = [\begin{array}{ll} a & b \\ c & d \end{array}] .$

Then A₁₁ = d and A₁₂ = c. Using the definition of det A, we get

det A = a det A₁₁ - b det A₁₂ = ad - bc.

Example 1.19

Let us show another well-known result. Let

$A = [\begin{array}{ll} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array}], x = [\begin{array}{l} x_{1} \\ x_{2} \end{array}], and b = [\begin{array}{l} b_{1} \\ b_{2} \end{array}] .$

If det A = a₁₁a₂₂ − a₁₂a₂₁ ≠ 0, then it is possible to express the solution of A x = b in terms of determinants. This result is known as Cramer’s rule. Here we show how to obtain x₁. The remaining variable is left for the reader to compute.

Write I₂ = [e₁e₂]. Notice that if x satisfies Ax = b, we have

$A [\begin{array}{ll} x & e_{2} \end{array}] = [\begin{array}{ll} A x & A e_{2} \end{array}] = [\begin{array}{ll} b_{1} & a_{12} \\ b_{2} & a_{22} \end{array}],$

were we have used the definition of matrix multiplication. On the other hand, we also have

$A [\begin{array}{ll} x & e_{2} \end{array}] = [\begin{array}{ll} A x & A e_{2} \end{array}] = [\begin{array}{ll} a_{11} x_{1} + a_{12} x_{2} & a_{12} \\ a_{21} x_{1} + a_{22} x_{2} & a_{22} \end{array}]$

Then,

$\det [\begin{array}{ll} a_{11} x_{1} + a_{12} x_{2} & a_{12} \\ a_{21} x_{1} + a_{22} x_{2} & a_{22} \end{array}] = \det [\begin{array}{ll} b_{1} & a_{12} \\ b_{2} & a_{22} \end{array}] .$

We use the definition of determinant to compute the left hand side of the equation:

$\begin{aligned} \det [\begin{array}{ll} a_{11} x_{1} + a_{12} x_{2} & a_{12} \\ a_{21} x_{1} + a_{22} x_{2} & a_{22} \end{array}] & = a_{22} (a_{11} x_{1} + a_{12} x_{2}) - a_{12} (a_{21} x_{1} + a_{22} x_{2}) \\ = (a_{11} a_{22} - a_{12} a_{21}) x_{1} + (a_{12} a_{22} - a_{12} a_{22}) x_{2} \\ = x_{1} \det A \end{aligned} .$

Therefore,

$x_{1} \det A = \det [\begin{array}{ll} b_{1} & a_{12} \\ b_{2} & a_{22} \end{array}]$

which gives us the expression for x₁:

$x_{1} = \frac{\det [\begin{array}{ll} b_{1} & a_{12} \\ b_{2} & a_{22} \end{array}]}{\det A} .$

Observe that the definition of determinant of a matrix A involves the first row of A. It turns out that it is possible to use any row or any column of A to compute its determinant. To state the next theorem, we introduce the following notation. The (i, j)-cofactor of A is the number C_ij given by

Cij = (-1)ⁱ⁺^j det A_ij.

We omit the proof of the following fundamental theorem to avoid a lenthy digression.

Theorem 1.17

The determinant of an n × n matrix A = (a_ij) can be computed by a cofactor expansion across any row or down any column. The expansion across the i-th row is

$\det A = a_{i 1} C_{i 1} + a_{i 2} C_{i 2} + \dots + a_{i n} C_{i n}$

The cofactor expansion down the j-th column is

$\det A = a_{1 j} C_{1 j} + a_{2 j} C_{2 j} + \dots + a_{n j} C_{n j}$

Example 1.20

Use a cofactor expansion to compute det A, where

$A = [\begin{array}{ccc} 1 & 0 & 5 \\ 2 & 4 & - 1 \\ - 2 & 0 & 2 \end{array}] .$

It is always desirable to minimize computational effort. If we choose to expand the determinant down the second column, then the cofactor expansion involves only one term because a₁₂ = a₃₂ = 0:

$\det A = 4 C_{22} = 4 \cdot (- 1)^{2 + 2} \det [\begin{array}{cc} 1 & 5 \\ - 2 & 2 \end{array}] = 4 (12) = 48 .$

Let A = (a_ij) be an m × n matrix. We say that a_ii are elements in the main diagonal. A matrix is said to be lower triangular if a_ij = 0 when i > j, that is, when all the elements above the main diagonal are all zero. A matrix is said to be upper triangular if a_ij = 0 when i < j, that is, when all the elements below the main diagonal are all zero. Some examples of lower triangular matrices are

$[\begin{array}{lll} 1 & 0 & 0 \\ 3 & 2 & 0 \\ 4 & 6 & 1 \end{array}], [\begin{array}{lll} 2 & 0 & 0 \\ 3 & 1 & 0 \end{array}], [\begin{array}{lll} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}], [\begin{array}{lll} 0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{array}] .$

Some examples of upper triangular matrices are

$[\begin{array}{lll} 1 & 3 & 4 \\ 0 & 2 & 6 \\ 0 & 0 & 1 \end{array}], [\begin{array}{lll} 2 & 3 & 5 \\ 0 & 1 & 4 \end{array}], [\begin{array}{lll} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}], [\begin{array}{lll} 0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 2 \\ 0 & 0 & 0 \end{array}] .$

Matrices in echelon form are upper triangular matrices.

Theorem 1.18

If A is an n × n triangular matrix, then det A is the product of the entries on the main diagonal of A.

Proof. We present the proof only for upper triangular matrices. The proof for lower triangular matrix is similar.

We prove this by induction on the size of the matrix. We start by verifying the first non trivial case. Then, for a 2 × 2 upper triangular matrix, we have

$\det [\begin{array}{cc} a_{11} & a_{12} \\ 0 & a_{22} \end{array}] = a_{11} a_{12} - 0 \cdot a_{22} = a_{11} a_{12} .$

Suppose that the theorem has been established for (k - 1) × (k - 1) upper triangular matrices. For a k × k upper triangular matrix, expand its determinant across its last row:

$\det [\begin{array}{ccccc} a_{11} & a_{12} & a_{13} & \dots & a_{1 k} \\ 0 & a_{22} & a_{23} & \dots & a_{2 k} \\ 0 & 0 & a_{33} & \dots & a_{3 k} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & 0 & \dots & a_{k k} \end{array}] = a_{k k} C_{k k} = a_{k k} (- 1)^{2 k} \det [\begin{array}{ccccc} a_{11} & a_{12} & a_{13} & \dots & a_{1 (k - 1)} \\ 0 & a_{22} & a_{23} & \dots & a_{2 (k - 1)} \\ 0 & 0 & a_{33} & \dots & a_{3 k} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & 0 & \dots & a_{(k - 1) (k - 1)} \end{array}] .$

The last matrix is a (k - 1) × (k - 1) upper triangular matrix. So by the induction hypothesis, we obtain

Then, by mathematical induction, the theorem is proved for all n × n upper triangular matrices.

One of the most important properties of determinants is they “behave well” under the applications of elementary row operations.

Theorem 1.19

Let A be a square matrix.

a. If the matrix B is obtained from A by interchanging two rows, then det A = − det B.

b. If the matrix B is obtained from A by multiplying one row by a scalar k, then det $A = \frac{1}{k}$ det B.

c. If the matrix B is obtained from A by adding a multiple of a row to another row, then det A = det B.

A common strategy in hand calculations is to reduce A to echelon form and then to use the fact that the determinant of a triangular matrix is the product of the entries in its main diagonal.

Example 1.21

Compute det A, where

$A = [\begin{array}{cccc} 2 & - 8 & 6 & 8 \\ 3 & - 9 & 5 & 10 \\ - 3 & 0 & 1 & - 2 \\ 1 & - 4 & 0 & 6 \end{array}] .$

First, we interchange the first and the last row, which changes the sign of the determinant:

$\det A = - \det [\begin{array}{cccc} 1 & - 4 & 0 & 6 \\ 3 & - 9 & 5 & 10 \\ - 3 & 0 & 1 & - 2 \\ 2 & - 8 & 6 & 8 \end{array}] .$

Next, we replace rows in order to produce 0’ under the pivot in the first column. These replacements do not change the determinant:

$\det A = - \det [\begin{array}{cccc} 1 & - 4 & 0 & 6 \\ 0 & 3 & 5 & - 8 \\ 0 & - 12 & 1 & 16 \\ 0 & 0 & 6 & - 4 \end{array}] .$

We continue to replace rows to produce 0’s under a₂₂ = 3. determinant:

$\det A = - \det [\begin{array}{cccc} 1 & - 4 & 0 & 6 \\ 0 & 3 & 5 & - 8 \\ 0 & 0 & 21 & - 16 \\ 0 & 0 & 6 & - 4 \end{array}] .$

If we rescale the last row by a factor of $\frac{1}{2}$ , the determinant changes as follows:

$\det A = - 2 \det [\begin{array}{cccc} 1 & - 4 & 0 & 6 \\ 0 & 3 & 5 & - 8 \\ 0 & 0 & 21 & - 16 \\ 0 & 0 & 3 & - 2 \end{array}] .$

The third row can be replaced by itself plus -7 times the last row, which does not change the determinant:

$\det A = - 2 \det [\begin{array}{cccc} 1 & - 4 & 0 & 6 \\ 0 & 3 & 5 & - 8 \\ 0 & 0 & 0 & - 2 \\ 0 & 0 & 3 & - 2 \end{array}] .$

Finally, we obtain a triangular matrix if we interchange the last two rows, which changes the sign of the determinant:

$\det A = 2 \det [\begin{array}{cccc} 1 & - 4 & 0 & 6 \\ 0 & 3 & 5 & - 8 \\ 0 & 0 & 3 & - 2 \\ 0 & 0 & 0 & - 2 \end{array}] .$

Therefore,

det A = 2(1)(3)(3)(-2) = -36.

We are ready to state the main theorem of this section.

Theorem 1.20

A square matrix A is invertible if and only if det A ≠ 0.

Proof. Suppose that A has been reduced to an echelon form U by row replacements and row interchanges (no rescaling). Clearly, this is always possible. Each row interchange produces a change of sign; so if there are r row interchanges, by Theorem 1.19, we have

det A = (-1)^r det U.

Since U is in echelon form, it is an upper triangular matrix, and so det U is the product of its diagonal entries u₁₁, u₂₂, …, u_nn.

If A is invertible, then all the entries uii are pivots because A ∼ I, which means that u_ii ≠ 0 for all i = 1, 2, …, n. Therefore,

det A = (-1)^ru₁₁ u₂₂ … u_nn ≠ 0.

If A is not invertible, the at least one entry, say ukk, is not a pivot, which means that ukk = 0. Consequently, det A = 0.

We conclude this section by stating two more properties of the determinant.

Theorem 1.21

If A and B are n × n matrices, then

a. det A^⊤ = det A

b. det AB = (det A) (det B)

_______________________________

* This format of writing the simplest version is called the row reduced echelon form, but we are reserving this name for matrices.