Basic Linear Algebra

Linear equations form the basis of linear programming. If you have a good understanding of the
Gauss-Jordan method for solving linear equations, then you can also understand the solution of
linear programs. In addition, this chapter introduces matrix notation and concepts that will be
used in Chapters 3 and 4 (optimizing functions of several variables).

1.1 Linear Equations

The Gauss-Jordan elimination procedure is a systematic method for solving systems of linear equa-
tions. It works one variable at a time, eliminating it in all rows but one, and then moves on to the
next variable. We illustrate the procedure on three examples.

Example 1.1.1 (Solving linear equations)

In the first step of the procedure, we use the first equation to eliminate from the other two.
Specifically, in order to eliminate from the second equation, we multiply the first equation by 2
and subtract the result from the second equation. Similarly, to eliminate from the third equation,
we subtract the first equation from the third. Such steps are called elementary row operations. We
keep the first equation and the modified second and third equations. The resulting equations are

Note that only one equation was used to eliminate in all the others. This guarantees that the
new system of equations has exactly the same solution(s) as the original one. In the second step of
the procedure, we divide the second equation by -5 to make the coefficient of equal to 1. Then,
we use this equation to eliminate from equations 1 and 3. This yields the following new system
of equations.

Once again, only one equation was used to eliminate in all the others and that guarantees
that the new system has the same solution(s) as the original one. Finally, in the last step of the
procedure, we use equation 3 to eliminate   in equations 1 and 2

So, there is a unique solution. Note that, throughout the procedure, we were careful to keep three
equations that have the same solution(s) as the original three equations. Why is it useful? Because,
linear systems of equations do not always have a unique solution and it is important to identify
such situations.

Another example:

First we eliminate from equations 2 and 3

Then we eliminate from equations 1 and 3.

Equation 3 shows that the linear system has no solution.

A third example:

Doing the same as above, we end up with

Now equation 3 is an obvious equality. It can be discarded to obtain

The situation where we can express some of the variables (here and ) in terms of the remaining
variables (here ) is important. These variables are said to be basic and nonbasic respectively.
Any choice of the nonbasic variable yields a solution of the linear system. Therefore the system
has infinitely many solutions.

It is generally true that a system of m linear equations in n variables has either: (a) no solution, (b) a unique solution, (c) infinitely many solutions. The Gauss-Jordan elimination procedure solves the system of linear equa- tions using two elementary row operations: • modify some equation by multiplying it by a nonzero scalar (a scalar is an actual real number, such as or -2, it cannot be one of the variables in the problem), • modify some equation by adding to it a scalar multiple of another equation. The resulting system of m linear equations has the same solution(s) as the original system. If an equation 0 = 0 is produced, it is discarded and the procedure is continued. If an equation 0 = a is produced where a is a nonzero scalar, the procedure is stopped: in this case, the system has no solution. At each step of the procedure, a new variable is made basic: it has coefficient 1 in one of the equations and 0 in all the others. The procedure stops when each equation has a basic variable associated with it. Say p equations remain (remember that some of the original m equations may have been discarded). When n = p, the system has a unique solution. When n > p, then p variables are basic and the remaining n - p are nonbasic. In this case, the system has infinitely many solutions.

Exercise 1 Solve the following systems of linear equations using the Gauss-Jordan elimination
procedure and state whether case (a), (b) or (c) holds.

(1)

(2)

(3)

Exercise 2 Indicate whether the following linear system of equations has 0, 1 or infinitely many
solutions.

1.2 Operations on Vectors and Matrices

It is useful to formalize the operations on vectors and matrices that form the basis of linear algebra.
For our purpose, the most useful definitions are the following.
A matrix is a rectangular array of numbers written in the form

The matrix A has dimensions m × n if it has m rows and n columns. When m = 1, the matrix is
called a row vector, when n = 1, the matrix is called a column vector. A vector can be represented
either by a row vector or a column vector.

Equality of two matrices of same dimensions:

Let and .

Then A = B means that for all i, j.

Multiplication of a matrix A by a scalar k:

Addition of two matrices of same dimensions:

Let and .
Then .

Note that A + B is not defined when A and B have different dimensions.

Exercise 3 Compute

Multiplication of a matrix of dimensions m × n by a matrix of dimensions n × p:

Let and .

Then AB is a matrix of dimensions m × p computed as follows.

As an example, let us multiply the matrices

and .

The result is

Note that AB is defined only when the number of columns of A equals the number of rows of B.
An important remark: even when both AB and BA are defined, the results are usually different.
A property of matrix multiplication is the following:

(AB)C = A(BC).

That is, if you have three matrices A, B, C to multiply and the product is legal (the number of
columns of A equals the number of rows of B and the number of columns of B equals the number
of rows of C), then you have two possibilities: you can first compute AB and multiply the result
by C, or you can first compute BC and multiply A by the result.

Exercise 4 Consider the following matrices

When possible, compute the following quantities:

Remark: A system of linear equations can be written conveniently using matrix notation. Namely

can be written as

or as

So a matrix equation Ax = b where A is a given m × n matrix, b is a given m-column vector
and x is an unknown n-column vector, is a linear system of m equations in n variables. Similarly, a
vector equation where , b are given m-column vectors and
are n unknown real numbers, is also a system of m equations in n variables.