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
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
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
(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
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
Exercise 1 Solve the following systems of linear equations
using the Gauss-Jordan elimination
procedure and state whether case (a), (b) or (c) holds.
Exercise 2 Indicate whether the following linear system of
equations has 0, 1 or infinitely many
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:
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
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
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.