Multiplying both sides by A−1 we get
A−1 = Ep · · · E1.
From a practical point of view, we can build up the product Ep · · · E1 by reducing to row
echelon form the augmented n × 2n matrix (A, In) obtained by adding the n columns of the
identity matrix to A. This is just another way of performing the Gauss–Jordan procedure.
Here is an example: let us find the inverse of the matrix
5 4
A =
.
6 5
6.5. REDUCED ROW ECHELON FORM
189
We form the 2 × 4 block matrix
5 4 1 0
(A, I) =
6 5 0 1
and apply elementary row operations to reduce A to the identity. For example:
5 4 1 0
5 4
1
0
(A, I) =
−→
6 5 0 1
1 1 −1 1
by subtracting row 1 from row 2,
5 4
1
0
1 0
5
−4
−→
1 1 −1 1
1 1 −1
1
by subtracting 4 × row 2 from row 1,
1 0
5
−4
1 0
5
−4
−→
= (I, A−1),
1 1 −1
1
0 1 −6
5
by subtracting row 1 from row 2. Thus
5
−4
A−1 =
.
−6
5
Proposition 6.17 can also be used to give an elementary proof of the fact that if a square
matrix A has a left inverse B (resp. a right inverse B), so that BA = I (resp. AB = I),
then A is invertible and A−1 = B. This is an interesting exercise, try it!
For the sake of completeness, we prove that the reduced row echelon form of a matrix is
unique. The neat proof given below is borrowed and adapted from W. Kahan.
Proposition 6.18. Let A be any m × n matrix. If U and V are two reduced row echelon
matrices obtained from A by applying two sequences of elementary row operations E1, . . . , Ep
and F1, . . . , Fq, so that
U = Ep · · · E1A and V = Fq · · · F1A,
then U = V and Ep · · · E1 = Fq · · · F1. In other words, the reduced row echelon form of any
matrix is unique.
Proof. Let
C = Ep · · · E1F −1
1
· · · F −1
q
so that
U = CV
and V = C−1U.
We prove by induction on n that U = V (and C = I).
190
CHAPTER 6. GAUSSIAN ELIMINATION, LU, CHOLESKY, ECHELON FORM
Let j denote the jth column of the identity matrix In, and let uj = U j, vj = V j,
cj = C j, and aj = A j, be the jth column of U, V , C, and A respectively.
First, I claim that uj = 0 iff vj = 0, iff aj = 0.
Indeed, if vj = 0, then (because U = CV ) uj = Cvj = 0, and if uj = 0, then vj =
C−1uj = 0. Since A = Ep · · · E1U, we also get aj = 0 iff uj = 0.
Therefore, we may simplify our task by striking out columns of zeros from U, V , and A,
since they will have corresponding indices. We still use n to denote the number of columns of
A. Observe that because U and V are reduced row echelon matrices with no zero columns,
we must have u1 = v1 = 1.
Claim. If U and V are reduced row echelon matrices without zero columns such that
U = CV , for all k ≥ 1, if k ≤ n, then k occurs in U iff k occurs in V , and if k does occurs
in U , then
1. k occurs for the same index jk in both U and V ;
2. the first jk columns of U and V match;
3. the subsequent columns in U and V (of index > jk) whose elements beyond the kth
all vanish also match;
4. the first k columns of C match the first k columns of In.
We prove this claim by induction on k.
For the base case k = 1, we already know that u1 = v1 = 1. We also have
c1 = C 1 = Cv1 = u1 = 1.
If vj = λ 1 for some µ ∈ R, then
uj = U 1 = CV 1 = Cvj = λC 1 = λ 1 = vj.
A similar argument using C−1 shows that if uj = λ 1, then vj = uj. Therefore, all the
columns of U and V proportional to 1 match, which establishes the base case. Observe that
if 2 appears in U, then it must appear in both U and V for the same index, and if not then
U = V .
Next us now prove the induction step; this is only necessary if k+1 appears in both U,
in wich case, by (3) of the induction hypothesis, it appears in both U and V for the same
index, say jk+1. Thus uj
= v
=
k+1
jk+1
k+1. It follows that
ck+1 = C k+1 = Cvj
= u
=
k+1
jk+1
k+1,
so the first k + 1 columns of C match the first k + 1 columns of In.
6.5. REDUCED ROW ECHELON FORM
191
Consider any subsequent column vj (with j > jk+1) whose elements beyond the (k + 1)th
all vanish. Then, vj is a linear combination of columns of V to the left of vj, so
uj = Cvj = vj.
because the first k + 1 columns of C match the first column of In. Similarly, any subsequent
column uj (with j > jk+1) whose elements beyond the (k + 1)th all vanish is equal to vj.
Therefore, all the subsequent columns in U and V (of index > jk+1) whose elements beyond
the (k + 1)th all vanish also match, which completes the induction hypothesis.
We can now prove that U = V (recall that we may assume that U and V have no zero
columns). We noted earlier that u1 = v1 = 1, so there is a largest k ≤ n such that k occurs
in U . Then, the previous claim implies that all the columns of U and V match, which means
that U = V .
The reduction to row echelon form also provides a method to describe the set of solutions
of a linear system of the form Ax = b. First, we have the following simple result.
Proposition 6.19. Let A be any m × n matrix and let b ∈ m
R
be any vector. If the system
Ax = b has a solution, then the set Z of all solutions of this system is the set
Z = x0 + Ker (A) = {x0 + x | Ax = 0},
where x
n
0 ∈ R
is any solution of the system Ax = b, which means that Ax0 = b (x0 is called
a special solution), and where Ker (A) = {x ∈
n
R
| Ax = 0}, the set of solutions of the
homogeneous system associated with Ax = b.
Proof. Assume that the system Ax = b is solvable and let x0 and x1 be any two solutions so
that Ax0 = b and Ax1 = b. Subtracting the first equation from the second, we get
A(x1 − x0) = 0,
which means that x1 − x0 ∈ Ker (A). Therefore, Z ⊆ x0 + Ker (A), where x0 is a special
solution of Ax = b. Conversely, if Ax0 = b, then for any z ∈ Ker (A), we have Az = 0, and
so
A(x0 + z) = Ax0 + Az = b + 0 = b,
which shows that x0 + Ker (A) ⊆ Z. Therefore, Z = x0 + Ker (A).
Given a linear system Ax = b, reduce the augmented matrix (A, b) to its row echelon
form (A , b ). As we showed before, the system Ax = b has a solution iff b contains no pivot.
Assume that this is the case. Then, if (A , b ) has r pivots, which means that A has r pivots
since b has no pivot, we know that the first r columns of In appear in A .
192
CHAPTER 6. GAUSSIAN ELIMINATION, LU, CHOLESKY, ECHELON FORM
We can permute the columns of A and renumber the variables in x correspondingly so
that the first r columns of In match the first r columns of A , and then our reduced echelon
matrix is of the form (R, b ) with
I
R =
r
F
0m−r,r 0m−r,n−r
and
d
b =
,
0m−r
where F is a r × (n − r) matrix and d ∈ r
R . Note that R has m − r zero rows.
Then, because
Ir
F
d
d
=
,
0m−r,r 0m−r,n−r
0n−r
0m−r
we see that
d
x0 = 0n−r
is a special solution of Rx = b , and thus to Ax = b. In other words, we get a special solution
by assigning the first r components of b to the pivot variables and setting the nonpivot
variables (the free variables) to zero.
We can also find a basis of the kernel (nullspace) of A using F . If x = (u, v) is in the
kernel of A, with u ∈ r
n−r
R and v ∈ R
, then x is also in the kernel of R, which means that
Rx = 0; that is,
Ir
F
u
u + F v
0
=
=
r
.
0m−r,r 0m−r,n−r
v
0m−r
0m−r
Therefore, u = −F v, and Ker (A) consists of all vectors of the form
−F v
−F
=
v,
v
In−r
for any arbitrary v ∈ n−r
R
. It follows that the n − r columns of the matrix
−F
N =
In−r
form a basis of the kernel of A. This is because N contains the identity matrix In−r as a
submatrix, so the columns of N are linearly independent. In summary, if N 1, . . . , N n−r are
the columns of N , then the general solution of the equation Ax = b is given by
d
x =
+ x
0
r+1N 1 + · · · + xnN n−r,
n−r
where xr+1, . . . , xn are the free variables, that is, the nonpivot variables.
6.5. REDUCED ROW ECHELON FORM
193
In the general case where the columns corresponding to pivots are mixed with the columns
corresponding to free variables, we find the special solution as follows. Let i1 < · · · < ir be
the indices of the columns corresponding to pivots. Then, assign b to the pivot variable
k
xi for k = 1, . . . , r, and set all other variables to 0. To find a basis of the kernel, we
k
form the n − r vectors Nk obtained as follows. Let j1 < · · · < jn−r be the indices of the
columns corresponding to free variables. For every column jk corresponding to a free variable
(1 ≤ k ≤ n − r), form the vector Nk defined so that the entries Nki , . . . , Nk are equal to the
1
ir
negatives of the first r entries in column jk (flip the sign of these entries); let Nkj = 1, and set
k
all other entries to zero. The presence of the 1 in position jk guarantees that N1, . . . , Nn−r
are linearly independent.
An illustration of the above method, consider the problem of finding a basis of the
subspace V of n × n matrices A ∈ Mn(R) satisfying the following properties:
1. The sum of the entries in every row has the same value (say c1);
2. The sum of the entries in every column has the same value (say c2).
It turns out that c1 = c2 and that the 2n−2 equations corresponding to the above conditions
are linearly independent. We leave the proof of these facts as an interesting exercise. By the
duality theorem, the dimension of the space V of matrices satisying the above equations is
n2 − (2n − 2). Let us consider the case n = 4. There are 6 equations, and the space V has
dimension 10. The equations are
a11 + a12 + a13 + a14 − a21 − a22 − a23 − a24 = 0
a21 + a22 + a23 + a24 − a31 − a32 − a33 − a34 = 0
a31 + a32 + a33 + a34 − a41 − a42 − a43 − a44 = 0
a11 + a21 + a31 + a41 − a12 − a22 − a32 − a42 = 0
a12 + a22 + a32 + a42 − a13 − a23 − a33 − a43 = 0
a13 + a23 + a33 + a43 − a14 − a24 − a34 − a44 = 0,
and the corresponding matrix is
1
1
1
1
−1 −1 −1 −1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
−1 −1 −1 −1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
−1 −1 −1 −1
A =
.
1
−1
0
0
1
−1
0
0
1
−1
0
0
1
−1
0
0
0
1
−1
0
0
1
−1
0
0
1
−1
0
0
1
−1
0
0
0
1
−1
0
0
1
−1
0
0
1
−1
0
0
1
−1
The result of performing the reduction to row echelon form yields the following matrix
194
CHAPTER 6. GAUSSIAN ELIMINATION, LU, CHOLESKY, ECHELON FORM
in rref:
1 0 0 0 0 −1 −1 −1 0 −1 −1 −1
2
1
1
1
0
1 0 0 0
1
0
0
0
1
0
0
−1
0
−1 −1
0 0 1 0 0
0
1
0
0
0
1
0
−1 −1
0
−1
U =
0
0 0 1 0
0
0
1
0
0
0
1
−1 −1 −1
0
0
0 0 0 1
1
1
1
0
0
0
0
−1 −1 −1 −1
0 0 0 0 0
0
0
0
1
1
1
1
−1 −1 −1 −1
The list pivlist of indices of the pivot variables and the list freelist of indices of the free
variables is given by
pivlist = (1, 2, 3, 4, 5, 9),
freelist = (6, 7, 8, 10, 11, 12, 13, 14, 15, 16).
After applying the algorithm to find a basis of the kernel of U , we find the following 16 × 10
matrix
1
1
1
1
1
1
−2 −1 −1 −1
−1
0
0
−1
0
0
1
0
1
1
0
−1
0
0
−1
0
1
1
0
1
0
0
−1
0
0
−1
1
1
1
0
−1
−1 −1
0
0
0
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
BK =
.
0
0
0
−1 −1 −1
1
1
1
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
The reader should check that that in each column j of BK, the lowest 1 belongs to the
row whose index is the jth element in freelist, and that in each column j of BK, the signs of
the entries whose indices belong to pivlist are the fipped signs of the 6 entries in the column
U corresponding to the jth index in freelist. We can now read off from BK the 4×4 matrices
that form a basis of V : every column of BK corresponds to a matrix whose rows have been
concatenated. We get the following 10 matrices:
1
−1 0 0
1
0 −1 0
1
0 0 −1
−1
1
0 0
−1 0
1
0
−1 0 0
1
M
1 =
,
M
,
M
0
0
0 0
2 = 0
0
0
0
3 = 0
0 0
0
0
0
0 0
0
0
0
0
0
0 0
0
6.5. REDUCED ROW ECHELON FORM
195
1
−1 0 0
1
0 −1 0
1
0 0 −1
0
0
0 0
0
0
0
0
0
0 0
0
M
4 =
,
M5 =
,
M6 =
−1
1
0 0
−1
0
1
0
−1
0 0
1
0
0
0 0
0
0
0
0
0
0 0
0
−2 1 1 1
−1 0 1 1
−1 1 0 1
1
0 0 0
1
0 0 0
1
0 0 0
M
7 =
,
M
,
M
1
0 0 0
8 = 1
0 0 0
9 = 1
0 0 0
1
0 0 0
0
1 0 0
0
0 1 0
−1 1 1 0
1
0 0 0
M
10 =
.
1
0 0 0
0
0 0 1
Recall that a magic square is a square matrix that satisfies the two conditions about
the sum of the entries in each row and in each column to be the same number, and also
the additional two constraints that the main descending and the main ascending diagonals
add up to this common number. Furthermore, the entries are also required to be positive
integers. For n = 4, the additional two equations are
a22 + a33 + a44 − a12 − a13 − a14 = 0
a41 + a32 + a23 − a11 − a12 − a13 = 0,
and the 8 equations stating that a matrix is a magic square are linearly independent. Again,
by running row elimination, we get a basis of the “generalized magic squares” whose entries
are not restricted to be positive integers. We find a basis of 8 matrices. For n = 3, we find
a basis of 3 matrices.
A magic square is said to be normal if its entries are precisely the integers 1, 2 . . . , n2.
Then, since the sum of these entries is
n2(n2 + 1)
1 + 2 + 3 + · · · +