Page 11 - Matrix Analysis & Applied Linear Algebra

1.2 Gaussian Elimination and Matrices 3
1.2 GAUSSIAN ELIMINATION AND MATRICES

The problem is to calculate, if possible, a common solution for a system of m
linear algebraic equations in n unknowns
a 11 x 1 + a 12 x 2 + ··· + a 1n x n = b 1 ,
a 21 x 1 + a 22 x 2 + ··· + a 2n x n = b 2 ,
. . .
a m1 x 1 + a m2 x 2 + ··· + a mn x n = b m ,

where the x i ’s are the unknowns and the a ij ’s and the b i ’s are known constants.
The a ij ’s are called the coefficients of the system, and the set of b i ’s is referred
to as the right-hand side of the system. For any such system, there are exactly
three possibilities for the set of solutions.

Three Possibilities

• UNIQUE SOLUTION: There is one and only one set of values
for the x i ’s that satisfies all equations simultaneously.

• NO SOLUTION: There is no set of values for the x i ’s that
satisfies all equations simultaneously—the solution set is empty.

• INFINITELY MANY SOLUTIONS: There are infinitely
many different sets of values for the x i ’s that satisfy all equations
simultaneously. It is not difficult to prove that if a system has more
than one solution, then it has infinitely many solutions. For example,
it is impossible for a system to have exactly two different solutions.

Part of the job in dealing with a linear system is to decide which one of these
three possibilities is true. The other part of the task is to compute the solution
if it is unique or to describe the set of all solutions if there are many solutions.
Gaussian elimination is a tool that can be used to accomplish all of these goals.
Gaussian elimination is a methodical process of systematically transform-
ing one system into another simpler, but equivalent, system (two systems are
called equivalent if they possess equal solution sets) by successively eliminating
unknowns and eventually arriving at a system that is easily solvable. The elimi-
nation process relies on three simple operations by which to transform one system
to another equivalent system. To describe these operations, let E k denote the
k th equation
E k : a k1 x 1 + a k2 x 2 + ··· + a kn x n = b k