Page 233 -

200 ALGEBRA

Suppose that det A ≠ 0. Then by consecutive elementary transformations, the augmented
matrix of the system A 1 [see (5.5.1.4)] of size n × (n + 1) can be reduced to the form

⎛ ⎞
1 u 12 ··· u 1n y 1
⎜ 0 1 ··· u 2n y 2 ⎟
U 1 ≡ ⎜ . . . . . ⎟
⎝ . . . .
. . . . . . ⎠
0 0 ··· 1 y n
and one obtains an equivalent system with an upper triangular basic matrix,

x 1 + u 12 x 2 + u 13 x 3 + ··· + u 1n x n = y 1 ,
x 2 + u 23 x 3 + ··· + u 2n x n = y 2 ,
... ... ... ... ... ... ... ... ...
x n = y n .

This system is solved by the so-called “backward substitution”: inserting x n = y n (obtained
from the last equation) into the preceding (n – 1)st equation, one finds x n–1 . Then inserting
the values obtained for x n , x n–1 into the (n – 2)nd equation, one finds x n–2 . Proceeding in
this way, one finally finds x 1 . This back substitution process is described by the formulas

n

x k = y k – u ks x s (k = n – 1, n – 2, ... , 1).
s=k+1

Suppose that det A = 0 and rank (A)= r, 0 < r < n. In this case, the system is
either inconsistent (i.e., has no solutions) or has infinitely many solutions. By elementary
transformations and, possibly, reindexing the unknown quantities (i.e., introducing new
unknown quantities y 1 = x σ(1) , ... , y n = x σ(n) ,where σ(1), ... , σ(n) is a permutation of
the indices 1, 2, ... , n), one obtains a system of the form (for the sake of brevity, we retain
the notation x j for the reindexed unknown quantities)

c 11 x 1 + ··· + c 1r x r + c 1,r+1 x r+1 + ··· + c 1n x n = d 1 ,
... ........ ........ ........ ........ ......... ......
c rr x r + c r,r+1 x r+1 + ··· + c rn x n = d r ,
0 = d r+1 ,
...
0 = d n ,

where the matrix [c ij ](i, j = 1, 2, ... , r)of size r × r is nondegenerate. If at least one
of the right-hand sides d r+1 , ... , d n is different from zero, then the system is inconsistent.
If d r+1 = ... = d n = 0, then the last n – r equations can be dropped and it remains to find all
solutions of the first r equations. Transposing all terms containing the variables x r+1 , ... , x n
to the right-hand sides and regarding these variables as arbitrary free parameters, we obtain
a linear system for the unknown quantities x 1 , ... , x r with the nondegenerate basic matrix
[c ij ](j, j = 1, 2, ... , r).
Example 2. Let us find a solution of the system from Example 1 by the Gaussian elimination method.
By elementary transformations of the augmented matrix, we obtain
⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞
214 16 11/22 8 11/2 2 8 11/2 2 8
⎝ 321 10 ⎠ → ⎝ 01/2 –5 –14 ⎠ → ⎝ 01 –10 –28 ⎠ → ⎝ 01 –10 –28 ⎠ .
133 16 05/21 8 00 26 78 00 1 3