CUHK MATH1030

2024-2025 Term 2
Extra Ex 4
Last updated: January 16, 2025
Notation
In this exercise, D is the indexes of the pivot columns (or equivalents the indexes of
dependent variables) and F is the indexes of the non-pivot columns (or equivalently the
indexes of the free variables).
Questions
1. Write down 3 × 3 matrices that produce the following elimination steps:
(a) Subtract 4 times the first row from the third row.
(b) Adds 2 times the third row to −2 times the second row.
Answer.
(a)  
1 0 0
−4R +R3
I3 −−−1−−→  0 1 0
−4 0 1
(b)  
1 0 0
−2R2 ,2R3 +R2
I3 −−−−−−−−→ 0 −2 2
0 0 1

2. Let  
a11 a12 a13 a14
A = a21 a22 a23 a24  .
a31 a32 a33 a34
(a) Suppose that I 0 and A0 are obtained by
R ↔R R ↔R
I3 −−1−−→
2
I 0, A −−1−−→
2
A0 .
Show that
A0 = I 0 A.
(b) Let α ∈ R. Suppose I 0 and A0 are obtained by
αR αR
2
I3 −−→ I 0, 2
A −−→ A0 .

Show that
A0 = I 0 A.

1
 (c) Let α ∈ R. Suppose I 0 and A0 are obtained by
αR +R αR +R
I3 −−−2−−→
1
I 0, A −−−2−−→
1
A0 .
Show that
A0 = I 0 A.
This exercise shows that row operations are basically same as left multiplying by a
matrix.
Answer.
   
a21 a22 a23 a24 0 1 0
(a) A0 = a11 a12 a13 a14  I 0 = 1 0 0
a31 a32 a33 a34 0 0 1
  
0 1 0 a11 a12 a13 a14
I 0 A = 1 0 0 a21 a22 a23 a24  = A0
0 0 1 a31 a32 a33 a34
   
a11 a12 a13 a14 1 0 0
(b) A0 = αa21 αa22 αa23 αa24  I 0 = 0 α 0
a31 a32 a33 a34 0 0 1
  
1 0 0 a11 a12 a13 a14
I A = 0 α 0 a21 a22 a23 a24  = A0
0   
0 0 1 a31 a32 a33 a34
   
a11 + αa21 a12 + αa22 a13 + αa23 a14 + αa24 1 α 0
(c) A0 =  a21 a22 a23 a24  I 0 = 0 1 0
a31 a32 a33 a34 0 0 1
  
1 α 0 a11 a12 a13 a14
I A = 0 1 0 a21 a22 a23 a24  = A0
0 
0 0 1 a31 a32 a33 a34

3. Determine if the following matrices are of RREF.
If yes, copy the matrix on the answer sheets, circle the leading ones and write down
the index of the pivot columns.
If not, explain why it is not.

(a) (b)

 
  1 0 1 1
1 0 1 1 0 3 0 1 1 1
 
0 1 1 0 0 5 0 0 0 0
   
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1

2
(c) (f)  
1 0 0 1
 
1 0 1 0
0 2 1 0 0 0 1 1
0 0 0 1 0 1 0 0

(d) (g)  
  1 0 0 0
1 1 0 1 0 1 0 1 0 0
0
 0 1 1 0 −1


0 0 1

0
0 0 0 0 0 1 0 0 0 1
0 0 0 0 1 2
(h)
(e)
 
  1 0 2 0 0 1
1 3 0 1 1 1 0 1 2 0 0 1
 
0 0 1 1 0 −1 0 0 0 1 0 1
0 0 0 0 1 1 0 0 0 0 1 1

Answer.
(a) It is of RREF. The leading ones are circled as follows:
 
1 0 1 1 0 3
0 1 1 0 0 5
 
0 0 0 0 1 0
0 0 0 0 0 0
The pivot columns are D = {d1 , d2 , d3 } = {1, 2, 5}.
(b) It fails condition 1: row 3 is a zero row but row 5, which is under row 3, is not
a zero row.
(c) It fails condition 2: the leftmost nonzero entry of row 2 is not 1.
(d) It fails condition 4:
The index of the leftmost nonzero entry of row 3 is `3 = 6.
The index of the leftmost nonzero entry of row 4 is `4 = 5.
3 < 4 but `3 > `4 .
(e) It fails condition 3: For row 3, the column contains the left most nonzero entry
(i.e. column 5) has more than 1 nonzero entries.
(f) It fails condition 4:
The index of the leftmost nonzero entry of row 2 is `2 = 3.
The index of the leftmost nonzero entry of row 3 is `3 = 2.
2 < 3 but `2 > `3 .
(g) It is of RREF. The leading ones are circled as follows:
 
1 0 0 0
0 1 0 0
 
0 0 1 0
0 0 0 1
The pivot columns are D = {d1 , d2 , d3 , d4 } = {1, 2, 3, 4}.

3
 (h) It is of RREF. The leading ones are circled as follows:
 
1 0 2 0 0 1
0 1 2 0 0 1
 
0 0 0 1 0 1
0 0 0 0 1 1

The pivot columns are D = {d1 , d2 , d3 , d4 } = {1, 2, 4, 5}.


4. Determine if the following matrices are of reduced row echelon form.
If yes, write down the index of the pivot columns. If not, explain why it is not.

(a)   (c)
1 0 0 2  
0 1 4 1 0 1 1 0
 1 0 3
 0 0 0 1 2 0 0
0 0 0 0

0
 0 0 0 0 0 1 1
0 0 0
0 0 1 4
(d)
(b)    
1 0 1 0 0 1 1 0 0 0 1
0 1 1 0 0 −1 0 0 1 0 2
0 0 0 0 1 1 0 1 0 0 3

Answer.
(a) No, row 3 is a zero row, but row 5, which under row 3, is not a zero row.
 
1 0 1 0 0 1
(b) Yes. 0
 1 1 0 0 −1. D = {d1 , d2 , d3 } = {1, 2, 5}
0 0 0 0 1 1
(c) No. It’s because for row 3, the column consists of the leftmost nonzero entry
(i.e. column 6) has more than 1 nonzero entries.

(d) No. Since the indices of the leftmost nonzero entries of row 2 and row 3 are
d2 = 3 and d3 = 2 respectively. Hence, d2 > d3 but 2 < 3.

5. Find the RREF of the following matrix:
 
0 0 1 1 0 2
A = 1 2 1 2 1 1
2 4 2 4 3 5

State your steps clearly, e.g. R1 ↔ R2 .

4
 Answer.
 
0 0 1 1 0 2
1 2 1 2 1 1
2 4 2 4 3 5
 
1 2 1 2 1 1
R1 ↔R2
−−−−→ 0  0 1 1 0 2
2 4 2 4 3 5
 
1 2 1 2 1 1
−2R +R3
−−−1−−→ 0 0 1 1 0 2
0 0 0 0 1 3
 
1 2 0 1 1 −1
−R +R1
−−−2−−→ 0 0 1 1 0 2
0 0 0 0 1 3
 
1 2 0 1 0 −4
−R3 +R1
−−−−−→ 0  0 1 1 0 2
0 0 0 0 1 3


6. Find the solution sets of the following system of linear equations by finding the
RREF of the augmented matrices.
(a)
5x1 + 5x2 + 4x3 + 13x4 + 9x5 + 2x6 = 16
x1 + x2 + x4 + x5 =2
2x1 + 2x2 + 2x3 + 6x4 + 4x5 + x6 =7
2x1 + 2x2 + x3 + 4x4 + 3x5 + x6 =6

(b)

5x1 + 5x2 + 4x3 + 13x4 + 9x5 + 2x6 = 15

x1 + x2 + x4 + x5 =2
2x1 + 2x2 + 2x3 + 6x4 + 4x5 + x6 =7
2x1 + 2x2 + x3 + 4x4 + 3x5 + x6 =6

Answer.
(a) First, form the augmented matrix,
 
5 5 4 13 9 2 16
 1 1 0 1 1 0 2 
 
 2 2 2 6 4 1 7 
2 2 1 4 3 1 6

5
and work to reduced row-echelon form, first with j = 1,
 
1 1 0 1 1 0 2
R ↔R2  5 5 4 13 9 2 16 

−−1−−→  2 2 2 6 4 1 7 
2 2 1 4 3 1 6
 
1 1 0 1 1 0 2
−5R1 +R2 ,−2R1 +R3  0 0 4 8 4 2 6 
−−−−−−−−−−−−→   0 0 2 4 2 1 3 

−2R1 +R4
0 0 1 2 1 1 2
 
1 1 0 1 1 0 2
−4R +R2  0 0 0 0 0 −2 −2 

−−−4−−→
−2R4 +R3  0 0 0 0 0 −1 −1 
0 0 1 2 1 1 2

Now, with j = 2,
 
1 1 0 1 1 0 2
R2 ↔R4 
−−−−→  0 0 1 2 1 1 2 

 0 0 0 0 0 −1 −1 
0 0 0 0 0 −2 −2

And finally, with j = 3,

 
1 1 0 1 1 0 2
−2R +R4  0
 0 1 2 1 1 2 
−−−3−−→ 
 0 0 0 0 0 −1 −1 
0 0 0 0 0 0 0
 
1 1 0 1 1 0 2
R3 +R2 
−−−−→  0 0 1 2 1 0 1 
 0 0 0 0 0 −1 −1 
0 0 0 0 0 0 0
 
1 1 0 1 1 0 2
−R3  0
 0 1 2 1 0 1 
−−→  0 0 0 0

0 1 1 
0 0 0 0 0 0 0

Columns 1, 3 and 6 are pivot columns, so D = {1, 3, 6}. From this we know
that the variables x1 , x3 and x6 will be dependent variables, and each of the
r = 3 nonzero rows of the row-reduced matrix will yield an expression for one
of these three variables. The set F is all the remaining column indices, namely
F = {2, 4, 5, 7}. The column index 7 in F means that the final column is not
a pivot column, and thus the system is consistent. The remaining indices in F
indicate free variables, so x2 , x4 and x5 (the remaining variables) are our free

6
 variables. The resulting three equations that describe our solution set are then
(xd1 = x1 ) x1 = 2 − x2 − x4 − x5
(xd2 = x3 ) x3 = 1 − 2x4 − x5
(xd3 = x6 ) x6 = 1

Thus the solution set is

2 − x2 − x4 − x 5
  
 
x

 


  2  

 1 − 2x4 − x5 
  
S=   x2 , x4 , x5 real numbers .

  x4  





 x 5
 



1

(b) First, form the augmented matrix,

 
5 5 4 13 9 2 15
 1 1 0 1 1 0 2 
 
 2 2 2 6 4 1 7 
2 2 1 4 3 1 6

and work to reduced row-echelon form, first with j = 1,

 
1 1 0 1 1 0 2
R ↔R2  5 5 4 13 9 2 15 

−−1−−→  2 2 2 6 4 1 7 
2 2 1 4 3 1 6
 
1 1 0 1 1 0 2
−5R1 +R2 ,−2R1 +R3  0 0 4 8 4 2 5 
−−−−−−−−−−−−→   0 0 2 4 2 1 3 

−2R1 +R4
0 0 1 2 1 1 2
 
1 1 0 1 1 0 2
−4R4 +R2  0 0 0 0 0 −2 −3 
−−−−−→  
−2R4 +R3  0 0 0 0 0 −1 −1 
0 0 1 2 1 1 2

Now, with j = 2,
 
1 1 0 1 1 0 2
R ↔R4  0
 0 1 2 1 1 2 
−−2−−→ 
 0 0 0 0 0 −1 −1 
0 0 0 0 0 −2 −3

7
 Then, with j = 3,
 
1 1 0 1 1 0 2
−2R3 +R4 
−−−−−→  0 0 1 2 1 1 2 

 0 0 0 0 0 −1 −1 
0 0 0 0 0 0 −1
 
1 1 0 1 1 0 2
R +R2  0
 0 1 2 1 0 1 
−−3−−→ 
 0 0 0 0 0 −1 −1 
0 0 0 0 0 0 −1
 
1 1 0 1 1 0 2
−R3  0
 0 1 2 1 0 1 
−−→  0

0 0 0 0 1 1 
0 0 0 0 0 0 −1

And finally, with j = 4,

 
1 1 0 1 1 0 0
2R4 +R1 ,R4 +R2  0 0 1 2 1 0 0 
−−−−−−−−−→   0

R4 +R3 0 0 0 0 1 0 
0 0 0 0 0 0 −1
 
1 1 0 1 1 0 0
−R4  0 0 1 2 1 0 0 
−−→   0

0 0 0 0 1 0 
0 0 0 0 0 0 1

The last equation will read 0 = 1. This is patently false, all the time. No
choice of values for our variables will ever make it true. We are done. Since
we cannot even make the last equation true, we have no hope of making all of
the equations simultaneously true. So this system has no solutions, and its
solution set is the empty set:
S = ∅.

7. Construct matrices with the following properties, if no such matrix exists, simply
write ”no such matrix”.
(a) 4 × 7 RREF A, with D = {d1 = 1, d2 = 3, d3 = 6}.
(b) 3 × 6 RREF A, with F = {f1 = 1, f2 = 3, f3 = 5}.
(c) 5 × 3 RREF A and every column of A is a pivot column
(d) 4 × 5 RREF A, the last column is not a pivot column and all the other columns
are pivot columns
(e) 5 × 5 RREF A, the last column is not a pivot column and all the other columns
are pivot columns

8
 (f) 6 × 3 RREF A with rank r = 3.
(g) 3 × 6 RREF A with rank r = 4.
Answer.
 
1 0 0 0 0
0 0
0 0 1 0 0
0 0
(a) 
0 0
.
0 0 0
1 0
0 0 0 0 0
0 0
 
0 1 0 0 0 0
(b) 0 0
 0 1 0 0 .
0 0 0 0 0 1
 
1 0 0
0 1 0
 
0 0
(c)  1
.
0 0 0
0 0 0
 
1 0 0 0 0
0 1 0 0 0
(d) 
0 0
.
1 0 0
0 0 0 1 0
 
1 0 0 0 0
0 1 0 0 0
 
0 0
(e)  1 0 0.
0 0 0 1 0
0 0 0 0 0
1 0 0
 
0 1 0
0 0 1
 
(f)  .
0 0 0
0 0 0
0 0 0
(g) No such matrix. Because r = 4 is the number of nonzero rows ≤ number of
rows = 3, i.e. 4 ≤ 3. Contradiction.

8. Let A be a n × n matrix.
(a) Show that if (A + B)2 = A2 + 2AB + B 2 , then AB = BA.
(b) For n = 2, find an example such that (A + B)2 6= A2 + 2AB + B 2 and find an
example such that (A + B)2 = A2 + 2AB + B 2 .
Answer.

9
(a)
(A + B)2 = (A + B)(A + B)
= A2 + AB + BA + B 2
By assumption,
(A + B)2 = A2 + 2AB + B 2 .
If
(A + B)2 = A2 + 2AB + B 2 ,
then
A2 + AB + BA + B 2 = A2 + 2AB + B 2 .
A2 + AB + BA + B 2 − (A2 + AB + B 2 ) = A2 + 2AB + B 2 − (A2 + AB + B 2 ).
So
BA = AB.
(b) By the previous part, (A + B)2 = A2 + 2AB + B 2 if and only if AB = BA.
Let A = B = I2 . Then AB = I2 = BA. So (A + B)2 = A2 + 2AB + B 2 . We
can further verify it as following.
(A + B)2 = (2I2 )2 = 4I2

A2 + 2AB + B 2 = I22 + 2I2 I2 + I22

= I2 + 2I2 + I2
= 4I2 .
2
Again by the previous part,
 (A+B)
 6=A2 +2AB
 +B 2 if and only if AB 6= BA.
1 0 0 1
Counter example: A = ,B = .
0 −1 0 0
Then    
0 1 0 −1
AB = , BA = .
0 0 0 0
So (A + B)2 6= A2 + 2AB + B 2 .
 2   
2 1 1 1 1 1 1
(A + B) = =
0 −1 0 −1 0 −1
 
1 0
= .
0 1
We can further verify it by
        
2 2 1 0 1 0 1 0 0 1 0 1 0 1
A + 2AB + B = +2 +
0 −1 0 −1 0 −1 0 0 0 0 0 0
     
0 1 0 1 0 0
= +2 +
1 0 0 0 0 0
   
1 2 1 0
= 6= .
0 1 0 1

10
 
9. Let A and B be square matrices of size n.
(a) Show that
(A + B)(A − B) = A2 − B 2 (1)
if and only if
AB = BA.
(b) For n = 2, find an example A, B such that (i) none of the entries are zeros and
(ii) equation (1) does not hold. Explain your answer.
(c) For n = 3 (attention: n is 3). find an example A, B such that (i) none of the
entries are zeros (ii) A 6= B and (iii) equation (1) holds. Explain your answer.
Answer.
(a) Suppose (A + B)(A − B) = A2 − B 2 . Then A2 + BA − AB − B 2 = A2 − B 2 ,
and thus BA − AB = 0 and AB = BA.

Suppose AB = BA. Then (A + B)(A − B) = A2 + BA − AB − B 2 = A2 − B 2 .

Therefore, (A + B)(A − B) = A2 − B 2 if and only if AB = BA.

 
1 1
(b) Consider A = . We aim to pick a square matrix B of size 2 with nonzero
1 1
entries such that AB 6= BA; then by (a) equation (1) does not hold.

Notice that for any square matrix B of size 2, i, j = 1, 2, (AB)ij gives the sum
of the entries in the j th column of B, whereas (BA)ij gives the sum of the
entries in the ith row of B. It suffices to find a square matrix B with nonzero
entries such that not all of its column sums and row sums are equal.
 
1 2
A simple example is given by B = .
1 2
   
2 4 3 3
Then AB = and BA = .
2 4 3 3
As AB 6= BA, (A + B)(A − B) 6= A2 − B 2 .
(c) Note that for any square matrix A and α ∈ F, αA · A = αA2 = A · αA. Hence
for any α ∈/ {0, 1} and any square matrix A of size 3 with nonzero entries, A
together with B = αA satisfy the conditions.
   
1 1 1 2 2 2
A simple example is given by A = 1 1 1 and B = 2A = 2 2 2.
1 1 1 2 2 2

10. A square matrix A of size n is said to be anti-symmetric, if At = −A.
(a) If square matrix A, B of size n are anti-symmetric and α a real number, show
that A + B, αA are also anti-symmetric.

11
(b) Let C be a square matrix of size n, show that D = 21 (C + C t ) is symmetry,
E = 21 (C − C t ) is antisymmetric and C = D + E.
(c) Let C be a square matrix of size n, Show that if C = D + E with D symmetric
and E antisymmetric, then D and E are given as in the previous part.
Answer.
(a)

(A + B)t = At + B t
= −A + (−B)
= −(A + B)

(αA)t = αAt
= α(−A)
= −αA
Therefore A + B and αA are anti-symmetric.
(b)
1
Dt = ( (C + C t ))t
2
1 t
= (C + (C t )t )
2
1
= (C t + C) = D
2

1
E t = ( (C − C t ))t
2
1 t
= (C − (C t )t )
2
1
= (C t − C) = −E
2
Therefore D is symmetric and E is anti-symmetric.
1 1
D + E = (C + C t ) + (C − C t )
2 2
1 1 t
= (C + C) + (C − C t )
2 2
=C

(c)
C t = (D + E)t = Dt + E t = D − E (2)
C =D+E (3)

12
 Solve these equations, we have
1 1
D = (C + C t ) = (D + E + D − E) = D.
2 2
1 1
E = (C − C t ) = (D + E − (D − E)) = E.
2 2

11. Determine if the following statements are true, if yes, write down ”true” . If not,
find a counter example.
(a) If A is a 5 × 5 RREF, delete the third row of A and obtain a new matrix B.
Then B also a RREF.
(b) If A is a 5 × 5 RREF, delete the last column of A and obtain a new matrix B.
Then B also a RREF.
(c) If A is a 5 × 5 RREF, delete the third column of A and obtain a new matrix
B. Then B also a RREF.
Answer.
(a) True. If we trace carefully the 4 conditions in the definition of RREF(reduced
row-echelon form), namely
i.
If a row is a zero row, then all the rows under it are zero rows.
ii.
The leftmost nonzero entry of a row is equal to 1.
iii.
The leftmost nonzero entry of a row is the only nonzero entry in its column.
iv.If i < j and both row i and row j are not zero vectors, then `i < `j , i.e.
`1 , `2 , . . . are in ascending order.
Then we’ll find none is violated if we delete the third row (in fact, any row) of
A.
(b) True. Similar to (a). In fact, we have that, If A is RREF, then any upper left
rectangular part also form a RREF.
(c) False, counter example:
 
1 1 0 0 1
0 0 1 2 1
 
A= 0 0 0 0 0,
0 0 0 0 0
0 0 0 0 0

then  
1 1 0 1
0 0 2 1
 
0
B= 0 0 0

0 0 0 0
0 0 0 0
is not RREF because the left most nonzero entry of row two is not one.

13
 
12. Let A be a 3 × 5 matrix and
2R +R R ↔R 3R
A1 −−1−−→
3
A2 −−2−−→
3 1
A3 −−→ A4 .
(a) Find a matrix J1 , such that A2 = J1 A1 .
(b) Find a matrix J2 , such that A3 = J2 A2 .
(c) Find a matrix J3 , such that A4 = J3 A3 .
(d) Find a matrix J such that A4 = JA1 .
Answer.
(a) J1 can be obtained by applying the same row operation on I3 :
   
1 0 0 1 0 0
2R1 +R3
 0 1 0 − −−−→  0 1 0  = J1 .
0 0 1 2 0 1

(b) J2 can be obtained by applying the same row operation on I3 :

   
1 0 0 1 0 0
R2 ↔R3
 0 1 0 − −−−→  0 0 1  = J2 .
0 0 1 0 1 0

(c) J3 can be obtained by applying the same row operation on I3 :

   
1 0 0 3 0 0
3R1
 0 1 0 − −→  0 1 0  = J3 .
0 0 1 0 0 1

(d) A4 = J3 A3 = J3 J2 A2 = J3 J2 J1 A1 . We we can take

     
3 0 0 1 0 0 1 0 0 3 0 0
J = J3 J2 J1 =  0 1 0   0 0 1  0 1 0  =  2 0 1 
0 0 1 0 1 0 2 0 1 0 1 0

Alternate method:
     
1 0 0 1 0 0 3 0 0
2R +R3 R2 ↔R3 3R1
I3 −−1−−→ 0 1 0 −−−−→ 2 0 1 −−→ 2 0 1 = J
2 0 1 0 1 0 0 1 0


13. Write down the definition of a system linear equations being consistent.
Answer. A system of linear equations is said to be consistent if and only if the
system of linear equation has solution. 

14
14. Suppose the augmented matrix of a system of linear equations can be row reduced
to  
1 2 3 4 −1
 0 1 2 3 10 
0 0 0 0 7
Explain why the system in inconsistent (you don’t need to use RREF).
Answer.
The linear equation corresponding to the third row of the augmented matrix is:
0 = 0x1 + 0x2 + 0x3 + 0x4 = 7
Which is impossible. Therefore the system has no solution, and is inconsistent. 
15. Let B be the RREF of the augmented matrix of a system of linear equations, with
m equations and n variables.
(a) By B, how do you know if the system of linear equations is consistent or not.
(b) If the system of linear equations is consistent, express the the number of free
of variable in terms of r (=the rank of B).
Answer.
(a) The system of linear equations is consistent if and only if the last column of B
is not a pivot columns.
(b) Number of free variables is n − r.

16. In below are the augmented matrices of systems of linear equations, (i) determine
if the system of linear equation is consistent. (ii) If it is consistent, write down all
the free variables (iii) find the solution sets.
(a)  
1 0 1 0 2
 0 1 −2 0 3 
0 0 0 1 4
(b)  
1 0 −1 2 0
 0 1 2 3 0 
0 0 0 0 1
(c)  
1 0 1 2 0 −2 1
 0
 1 2 −3 0 3 −1 

 0 0 0 0 1 −4 2 
0 0 0 0 0 0 0
Answer.
(a) i. It is consistent.

15
 ii. The free variable is x3 .
iii. The solution set is   

 2 − x 3 

3 + 2x
 
3

 x3  3
 x ∈ R

 

 4 
.
(b) i. It is not consistent.
ii. (Not consistent)
iii. The solution set is ∅, the empty set.
(c) i. It is consistent.
ii. The free variables are x3 , x4 and x6 .
iii. The solution set is
1 − x3 − 2x4 + 2x6
  
 
−1 − 2x3 + 3x4 − 3x6 

 


 

x3
  
x , x , x ∈
 
 3 4 6 R
x4


   





 2 + 4x 6
 



x6
.

17. For the following system of linear equations
x1 + x2 + 2x5 =3
x3 + x4 + 5x5 =4
2x1 + 2x2 + x4 + 5x5 =9
−3x1 − 3x2 + x3 + 3x4 + x5 =1

(a) Write down the augmented matrix of the system.

(b) Row reduce the augmented matrix to a reduced row echelon form B.
State your steps clearly (example 2R2 + R1 ).
(c) Determine if the system is consistent. If it is consistent, Write down the solution
set.
Answer.
(a)  
1 1 0 0 2 3
 0 0 1 1 5 4 
 
 2 2 0 1 5 9 
−3 −3 1 3 1 1

16
 (b)    
1 1 0 0 2 3 1 1 0 0 2 3
 0 0 1 1 5 4  −2R1 +R 3
 0 0 1 1 5 4 
  −−−−−→  
 2 2 0 1 5 9  3R1 +R4  0 0 0 1 1 3 
−3 −3 1 3 1 1 0 0 1 3 7 10
   
1 1 0 0 2 3 1 1 0 0 2 3
−R2 +R4  0 0 1 1 5 4  −R3 +R2  0 0 1 0 4 1 
−−−−−→  − −−−−→  
−2R3 +R4  0 0 0 1 1 3   0 0 0 1 1 3 
0 0 0 0 0 0 0 0 0 0 0 0
(c) Solution set is :   

 3 − 2x 5 − x 2 

x
 
2

  

 
 1 − 4x5  x2 , x5 ∈ R
 


  3 − x5  


 
 x5 


18. For the following system of linear equations
x1 + x2 + x3 + x4 + x5 =2
2x1 + 2x2 + 2x3 + 2x4 + 2x5 =4
−x2 − 2x3 + x4 + 3x5 =7
x2 + 2x3 − x4 − x5 =3

(a) Row reduce the augmented matrix to a reduced row echelon form B.
State your steps clearly (example 2R2 + R1 ).
(b) Determine if the system is consistent. If it is consistent, write down the solution
set.
Answer.

17
 (a)
 
1 1 1 1 1 2
2 2 2 2 2 4
 
0 −1 −2 1 3 7
0 1 2 −1 −1 3
 
1 1 1 1 1 2
−2R +R2 0 1 2 −1 −1 3
−−−1−−→ 
R2 ↔R4 0 −1 −2 1 3 7
0 0 0 0 0 0
 
1 0 −1 2 2 −1
−R2 +R1 , R2 +R3 0 1 2 −1 −1 3
−−−− −−−−−−→  0

1
R →R3
2 3
0 0 0 1 5
0 0 0 0 0 0
 
1 0 −1 2 0 −11
−2R +R1  0
 1 2 −1 0 8 
−−−3−−→ 
R3 +R2  0 0 0 0 1 5 
0 0 0 0 0 0

(b) The system is consistent because the last column is not a pivot column.
The solution set is
  

 −11 + x3 − 2x4 

8 − 2x + x
 
3 4

  

 
x3  x3 , x4 ∈ R
 

x

4

   

 
 5 


19. (a) Give two examples of 4 × 5 matrices (i) all the entries either 0 or 1, (ii) rank
r = 3 and (iii) the corresponding system is consistent
(b) Give two examples of 4 × 5 matrices (i) all the entries either 0 or 1, (ii) rank
r = 3 and (iii) the corresponding system is inconsistent.
Answer.
(a)    
1 0 0 0 1 1 0 0 0 1
0 0 1 0 0 0 1 0 0 0
A=
0 ,B =  .
0 0 1 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0
(b)    
1 0 0 0 1 1 0 0 0 1
0 0 1 0 0 0 1 0 0 0
C=
0 ,D =  .
0 0 0 1 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0

18
 
20. Let n = 6, m = 4. Find a system of linear equation with n = 6 variables and m = 4
equations with the following property. If no such system exists, explain why.
(a) The system is consistent and has exactly 3 free variables.
(b) The system is consistent and has exactly 2 free variables.
(c) The system is consistent and has exactly 1 free variable.
(d) The system is inconsistent.
Answer.
(a) Such system exists. Example, a system with the following augmented matrix
 
1 0 0 1 2 3 −1
 0
 1 0 4 5 6 −2  
 0 0 1 7 8 9 −3 
0 0 0 0 0 0 0
Then x4 , x5 , x6 are free variables The solution set is
−1 − x4 − 2x5 − 3x6
  
 
 −2 − 4x4 − 5x5 − 6x6 

 

 

−3 − 7x4 − 8x5 − 9x6 
  
 x4 , x5 , x6 are real numbers
x4


   





 x 5
 



x6

If you feel uncomfortable about the last equation (0 = 0) you can change the
augmented matrix to  
1 0 0 1 2 3 −1
 0 1 0
 4 5 6 −2  
 0 0 1 7 8 9 −3 
0 0 1 7 8 9 −3
You can get the same solution sets.
(b) Such system exists. Example, a system with the following augmented matrix
 
1 0 0 0 1 2 −1
 0 1 0 0
 3 4 −2  
 0 0 1 0 5 6 −3 
0 0 0 1 7 8 −4
Then x5 , x6 are free variables The solution set is
−1 − x5 − 2x6
  
 
−2 − 3x − 4x

 


  5 6  

−3 − 5x5 − 6x6 
  
 x5 , x6 are real numbers
−4 − 7x5 − 8x6 


 





 x 5
 



x6

19
 (c) Let B be the RREF of the augmented matrix of the system. Then B is a 4 × 7
matrix. Let r be the rank of B.
r = number of nonzero rows of B ≤ number of rows of B ≤ 3.
The number of non-pivot columns of B = n − r ≥ n − 3 = 3.
Suppose the system is consistent, then the last column is a non-pivot columns.
So there are at least 3−1 non-pivot columns among the first 6 columns. As each
non-pivot columns among the first 6 columns corresponds to a free variables.
So the system has at least 2 free variables.
Therefore no system with exactly one free variable exists. See also proof of
Lecture 4 Theorem 6.
(d) Such system exists. Example, a system with the following augmented matrix
 
1 0 0 1 2 3 −1
 0 1 0 4 5 6 −2 
 
 0 0 1 7 8 0 −3 
0 0 0 0 0 0 −4
The last equation corresponding to 0 = 4. Hence it is not consistent.
If you feel uncomfortable about the equation corresponding to the last row
(0 = −4), you can change it by using 1R1 + R4 .
 
1 0 0 1 2 3 −1
 0 1 0 4 5 6 −2 
 
 0 0 1 7 8 0 −3 
1 0 0 1 2 3 −5


21. Given the following
   
1 0 1 1 2 1 0 1 1 2
1R +R3
A= 2 1 −1 −3 4  −−2−−→ 2 1 −1 −3 4
−2 −1 1 3 −3 0 0 0 0 1
   
1 0 1 1 2 1 0 1 1 0
−2R +R2 −2R3 +R1
−−−1−−→ 0 1 −3 −5 0 − −−−−→ B = 0 1 −3 −5 0
0 0 0 0 1 0 0 0 0 1
 
b1
(a) Let b = b2 . Apply the same row operations of the above on [A|b], i.e.

b3
1R +R −2R +R −2R +R
[A|b] −−2−−→
3
−−−1−−→
2
−−−3−−→
1
C.
Find C. Is it a RREF? Simply answer yes or no.
(b) Hence show that LS(A, b) is consistent for any b.
Answer.

20
 (a) The augmented matrix C is given by [B|c], where c is obtained via
       
b1 b1 b1 b1 − 2b2 − 2b3
1R +R3 −2R1 +R2 −2R +R1
b = b2  −−2−−→  b2  − −−−−→ −2b1 + b2  −−−3−−→ c =  −2b1 + b2  ,
b3 b2 + b3 b2 + b3 b2 + b3

hence  
1 0 1 1 0 b1 − 2b2 − 2b3
C=  0 1 −3 −5 0 −2b1 + b2 
0 0 0 0 1 b2 + b 3
Remark If you feel uncomfortable about applying row operation on the last
column b alone, here is the full version of the row operations:
   
1 0 1 1 2 b1 1 0 1 1 2 b1
1R +R3
[A|b] =  2 1 −1 −3 4 b2  −−2−−→  2 1 −1 −3 4 b2 
−2 −1 1 3 −3 b3 0 0 0 0 1 b 2 + b3
   
1 0 1 1 2 b1 1 0 1 1 0 b1 − 2b2 − 2b3
−2R +R2 −2R3 +R1
−−−1−−→  0 1 −3 −5 0 −2b1 + b2  − −−−−→  0 1 −3 −5 0 −2b1 + b2 
0 0 0 0 1 b2 + b3 0 0 0 0 1 b2 + b3
Yes, it is a RREF.
 
b1
(b) For any b = b2 , LS(A, b) has the nonempty solution set:

b3
  

 b 1 − 2b 2 − 2b 3 − x 3 − x 4 

−2b + b + 3x + 5x
 
1 2 3 4 

  


x3  x3 , x4 ∈ R
 





 x 4  


 b2 + b 3 

and is thus consistent.


22. Given the following
   
1 1 1 2 3 1 1 1 2 3
−1R +R2
A = 1 2 3 4 5 −−−1−−→ 0 1 2 2 2
2 3 4 6 8 2 3 4 6 8
   
1 1 1 2 3 1 1 1 2 3
−2R1 +R3 −1R2 +R3
−−−−−→ 0  1 2 2 2 −−−−−→ 0 1
  2 2 2
0 1 2 2 2 0 0 0 0 0
 
1 0 −1 0 1
−1R +R1
−−−2−−→ B = 0 1 2 2 2
0 0 0 0 0

21
  
b1
(a) Let b = b2 . Apply the same row operations on [A|b], i.e.

b3
−1R +R −2R +R −1R +R −1R +R
[A|b] −−−1−−→
2
−−−1−−→
3
−−−2−−→
3
−−−2−−→
1
C.
Find C.
(b) Show that if −b1 − b2 + b3 = 0, then it is a RREF with the last column a
non-pivot column.
(c) Note that C may or may not be a RREF. For −b1 − b2 + b3 6= 0, find the RREF
of C (and hence the RREF of [A|b]). Is the last column a pivot column?
(d) Show that LS(A, b) is consistent if and only if −b1 − b2 + b3 = 0.
(e) Hence find b such that LS(A, b) is inconsistent.
(f) Find the row operations that transform B to A.
(g) Applythe
 row operations you obtain from the previous part on [B|e3 ], where
0
e3 = 0. Show that the matrix you obtain is in the form [A|b]. Hence find
1
another b such that that LS(A, b) is inconsistent.
Answer.
(a) The augmented matrix C is given by [B|c], where c is obtained via
     
b1 b1 b1
−1R +R2 −2R1 +R3
b = b2  −−−1−−→ −b1 + b2  − −−−−→  −b1 + b2 
b3 b3 −2b1 + b3
   
b1 2b1 − b2
−1R +R3 −1R2 +R1
−−−2−−→  −b1 + b2  − −−−−→ c =  −b1 + b2  ,
−b1 − b2 + b3 −b1 − b2 + b3
hence  
1 0 −1 0 1 2b1 − b2
C= 0 1 2 2 2 −b1 + b2 
0 0 0 0 0 −b1 − b2 + b3
Remark If you feel uncomfortable about applying row operation on the last
column b alone, here is the full version of the row operations:
   
1 1 1 2 3 b1 1 1 1 2 3 b1
−1R +R2
[A|b] =  1 2 3 4 5 b2  −−−1−−→  0 1 2 2 2 −b1 + b2 
2 3 4 6 8 b3 2 3 4 6 8 b3
   
1 1 1 2 3 b1 1 1 1 2 3 b1
−2R +R3 −1R2 +R3
−−−1−−→  0 1 2 2 2 −b1 + b2  − −−−−→  0 1 2 2 2 −b1 + b2 
0 1 2 2 2 −2b1 + b3 0 0 0 0 0 −b1 − b2 + b3
 
1 0 −1 0 1 2b1 − b2
−1R +R1
−−−2−−→  0 1 2 2 2 −b1 + b2 
0 0 0 0 0 −b1 − b2 + b3

22
(b) If −b1 − b2 + b3 = 0, then
 
1 0 −1 0 1 2b1 − b2
C=  0 1 2 2 2 −b1 + b2 
0 0 0 0 0 0
is of RREF, and the last column is a non-pivot column.
(c) If −b1 − b2 + b3 6= 0, then we can obtain the RREF of C via
 
1 0 −1 0 1 2b1 − b2
C= 0 1 2 2 2 −b1 + b2 
0 0 0 0 0 −b1 − b2 + b3
 
1 0 −1 0 1 2b1 − b2
)−1 R
(−b1 −b2 +b3 3
−−−−−−−−−−→ 0 1  2 2 2 −b1 + b2 
0 0 0 0 0 1
 
1 0 −1 0 1 0
(−2b1 +b2 )R3 +R1
−−−−−−−−−−→  0 1 2 2 2 0 
(b1 −b2 )R3 +R2
0 0 0 0 0 1
Hence the last column is a pivot column.
(d) If −b1 −b2 +b3 = 0, then the last column of the RREF of the augmented matrix
[A|b] is a non-pivot column, and hence LS(A, b) is consistent.
If −b1 −b2 +b3 6= 0, then the last column of the RREF of the augmented matrix
[A|b] is a pivot column, and hence LS(A, b) is inconsistent.
Therefore, LS(A, b) is consistent if and only if −b1 − b2 + b3 = 0.
 
b1
(e) A vector b = b2  correspond to an inconsistent system LS(A, b) if and only
b3
 
1
−b1 − b2 + b3 6= 0. One example of such b is given by b = 0.
0
(f)
1R +R 1R +R 2R +R 1R +R
B −−2−−→
1
−−2−−→
3
−−1−−→
3
−−1−−→
2
A.
(g)    
1 0 −1 0 1 0 1 1 1 2 3 0
1R +R1
[B|e3 ] =  0 1 2 2 2 0  −−2−−→  0 1 2 2 2 0 
0 0 0 0 0 1 0 0 0 0 0 1
   
1 1 1 2 3 0 1 1 1 2 3 0
1R2 +R3 2R +R3
−−−−→ 0 1 2 2 2 0  −−1−−→  0 1 2 2 2 0 
0 1 2 2 2 1 2 3 4 6 8 1
 
1 1 1 2 3 0
1R +R2
−−1−−→  1 2 3 4 5 0 
2 3 4 6 8 1

23
  
0
Another example of b is given by b = 0.

1

23. Let A be a m × n matrix. Let B be the RREF of A. Let r be the rank of B. Let
b be a column vector of size m. Show that LS(A, b) is consistent for any b if and
only if r = m.
Answer.
As B is the RREF of A, we have a sequence of row operations Oi , such that
1O 2 O
n ··· O
A −→ −→ →−→
− B.
And hence we have an sequence of inverse row operations Oi0 , such that
0 0
O0
n
On−1
1 ··· O
B −→ −−−→−
→−→ A.

(if part: If r = m, then LS(A, b) is consistent for any b.)

Assume r = m.
Let b be arbitrary vector. The system LS(A, b) have the augmented matrix [A|b],
after the row operations Oi :
O O ··· O
1
[A|b] −→ 2
−→ − n
→−→ [B|b0 ], for some vector b0 .
As r = m, there is m pivot columns in B, then [B|b0 ] is already in RREF, and
the last column, b0 , cannot be pivot. The system LS(B, b0 ) is consistent. Hence
LS(A, b) is also consistent.

(only if part: If LS(A, b) is consistent for any b, then r = m.)

Assume LS(A, b) is consistent for any b.

Consider the augmented matrix [B|em ], where em is the vector with all entry 0
except the last entry (m-th entry) being 1.
Apply the sequence of row operations Oi0 on [B|em ], which is:
0 0
O0
n
On−11··· O
[B|em ] −→ −−−→−
→−→ [A|bm ], for some vector bm .
By the assumption (LS(A, b) is consistent for any b), so the system LS(A, bm ) is
consistent. The system LS(B, em ) before row operations is hence also consistent.
As LS(B, em ) consistent, last equation will not be 0 = 1. As last row of B non-
zero, B have m pivot column, which is r = m.


24. Let A and B be m × n matrix.

24
(a) Write down the definition of A being row equivalent to B.
(b) Suppose A is row equivalent to B, show that there exists a n × n matrix J,
such that JA = B.
(c) Suppose A is row equivalent to B, show that there exists a n × n matrix J,
such that JB = A (Hint: Use CW2, Q10)
Answer.
(a) A is called being row equivalent to B if B can be obtained by a sequences of
row operations from A.
(b) Denote the sequences of row operations by O1 , O2 , . . . , On , which transform A
to B.
1O 2 O i O n O
A = A0 −→ A1 −→ · · · Ai−1 −→ Ai · · · −→ An = B.
Define Ji by
i O
In −→ Ji .
By theorem in the lectures, Ai = Ji Ai−1 for i = 1, . . . , n.
B = An = Jn An−1 = Jn Jn−1 An−2 = Jn Jn−1 · · · J1 A.
Thus we can take
J = Jn Jn−1 · · · J1 .
Obviously B = JA.
(c) Similar to the discussion of CW2 Q12, For i 6= j,
Ri ↔Rj
C −−−−→ D,

then
Ri ↔Rj
D −−−−→ C.
For α 6= 0,
i αR
C −−→ D,
then
α−1 Rj
D −−−−→ C.
For i 6= j
αRi +Rj
C −−−−→ D,
then
−αRi +Rj
D −−−−−→ C.
Hence for
i O
Ai −→ Ai+1 ,
there exists a row operation Oi0 , such that
i O0
Ai+1 −→ Ai .

25
 Therefore 0
n O0 On−1 1 O0
B = An −→ An−1 −−−→ An−2 · · · A1 −→ A0 = A.
So B can be transformed to A by a sequence of row operations, thus by the
pervious part, there exists J such that JB = A.

25. A square matrix B of size n is said to be antisymmetric if B t = −B.
(a) Let A be a square matrix, show that A − At is antisymmetric.
(b) Let n = 3 and A a square matrix of size 3. Show that if AB = BA for any
antisymmetric matrix B, then A = cI3 for some real number c.
Hint: find some antisymmetric matrices B and find out when is AB = BA.
Answer.
(a) We claim that (A − At )t = −(A − At ):
(A − At )t = At − (At )t = At − A = −(A − At )
Therefore, by definition, A − At is antisymmetric.
(b) We are going to consider the following two antisymmetric matrices B1 , B2 and
see the conclusions of A by imposing equalities ABi = Bi A for i = 1, 2:
   
0 1 0 0 0 0
B1 = −1 0 0 ; B2 = 0 0 1
0 0 0 0 −1 0
Note that
       
0 1 0 0 0 0 0 0 0 0 0 0
B1 = 0 0 0 − 1 0 0 ; B2 = 0 0 1 − 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0
which implies
 that B1 , B
2 are antisymmetric by (a).
a11 a12 a13
Let A = a21 a22 a23 . First we consider AB1 = B1 A. This means
a31 a32 a33
     
a11 a12 a13 0 1 0 0 1 0 a11 a12 a13
a21 a22 a23  −1 0 0 = −1 0 0 a21 a22 a23 
a31 a32 a33 0 0 0 0 0 0 a31 a32 a33
which can be simplified to
   
−a12 a11 0 a21 a22 a23
−a22 a21 0 = −a11 −a12 −a13 
−a32 a31 0 0 0 0
By entrywise comparisons, we immediately have a23 = a32 = a13 = a31 = 0;
a11 = a22 ; a21 = −a12 .

26
 Similarly, we consider AB2 = B2 A. This means
     
a11 a12 a13 0 0 0 0 0 0 a11 a12 a13
a21 a22 a23  0 0 1 = 0 0 1 a21 a22 a23 
a31 a32 a33 0 −1 0 0 −1 0 a31 a32 a33
which can be simplified to
   
0 −a13 a12 0 0 0
0 −a23 a22  =  a31 a32 a33 
0 −a33 a32 −a21 −a22 −a23

By entrywise comparisons, we immediately have a12 = a21 = a13 = a31 = 0;

a22 = a33 ; a23 = −a32 .

Combining the above conclusions, we see that a12 = a21 = a13 = a31 = a23 =
a32 = 0; a11 = a22 = a33 . Let c = a11 , we have
 
c 0 0
A = 0 c 0 = cI3
0 0 c
which is the desired conclusion.

26. Denote Eij a m × n matrix with all entries being zero except the (i, j)-th entry
being one. e.g. For m = n = 3,
   
0 0 0 0 0 0
E22 = 0 1 0 , E23 = 0 0 1 .
0 0 0 0 0 0

In below, m = n = 3.
(a) Let  
a11 a12 a13
A = a21 a22 a23 
a31 a32 a33
i. Compute AE11 and E11 A.
ii. If AE11 = E11 A, show that a12 = a13 = a21 = a31 = 0.
iii. If AE22 = E22 A, what can you say about the entries of A? (No steps
required, as it is similar to part ii.)
iv. If AE33 = E33 A, what can you say about the entries of A? (No steps
required, as it is similar to the part ii)
(b) Let  
a11 0 0
A =  0 a22 0 
0 0 a33

27
 i. Compute AE12 and E12 A.
ii. If AE12 = E12 A, show that a11 = a22 .
iii. If AE13 = E13 A, what can you say about the entries of A? (No steps
required, as it is similar to part ii.)
iv. If AE23 = E23 A, what can you say about the entries of A? (No steps
required, as it is similar to the part ii)
(c) Let A be a 3 × 3 matrices. Show that if AB = BA for any 3 × 3 matrix B,
then A = cI3 for some scalar c.
Answer.
(a) i.
 
a11 0 0
AE11 =  a21 0 0 
a31 0 0
 
a11 a12 a13
E11 A =  0 0 0 
0 0 0
ii. By (i), AE11 = E11 A implies that a12 = a13 = a21 = a31 = 0.
iii.
 
0 a12 0
AE22 = 0 a22
 0 
0 a23 0
 
0 0 0
E22 A =  a21 a22 a23 
0 0 0
Then AE22 = E22 A implies that a12 = a21 = a23 = a32 = 0.
iv.
 
0 0 a13
AE33 =  0 0 a23 
0 0 a33
 
0 0 0
E33 A =  0 0 0 
a31 a32 a33
Then AE33 = E33 A implies that a13 = a31 = a23 = a32 = 0.
(b) i.
 
0 a11 0
AE12 = 0 0 0
0 0 0

28
  
0 a22 0
E12 A = 0 0 0
0 0 0

ii. By (i), AE12 = E12 A implies that a11 = a22 .

iii.
 
0 0 a11
AE13 = 0 0 0 
0 0 0

 
0 0 a33
E13 A = 0 0 0 
0 0 0

Then AE13 = E13 A implies that a11 = a33 .

iv.
 
0 0 0
AE23 = 0 0 a22 
0 0 0

 
0 0 0
E23 A = 0 0 a33 
0 0 0

Then AE23 = E23 A implies that a22 = a33 .

(c) Let B = E11 , E22 , E33 and then by (a), a12 = a21 = a13 = a31 = a23 = a32 = 0.
Let B = E12 , E13 , E23 and apply (b), a11 = a22 = a33 . Therefore A = cI3 where
c = a11 .

27. Let A be a square matrix of size n such that AB = BA for any square matrix B of
size n. Show that A = cIn for some real number c.
Hint: Consider B = Eij , which is a square matrix with all entries being zero except
the (i, j)-th being one.

Answer. First, for each 1 ≤ i ≤ n, let B = Eii .

0 ··· 0 a1i 0 ··· 0
 
0 · · · 0 a2i 0 ··· 0
AEii =  ... ... .. .. .. .. 
. . . . 
0 ··· 0 ani 0 ··· 0

29
  .. 
0 0 . 0
 . . .. .. 
 .. .. . . 
..
 
 
0 0 . 0
Eii A = a a · · ·

ain 

 i1 i2
 0 0 ··· 0

 . .. .. .. 
 .. . . . 
0 0 ··· 0
Then AEii = Ei A implies that aij = aji = 0 for j 6= i. Therefore A is diagonal:
a11 0 · · · 0
 
 0 a22 · · · 0 
A=  ... .. .. .. 
. . . 
0 0 · · · ann
Next, for each pair of distinct integers i 6= j, let B = Eij .
j
0 · · · 0 0 0 ··· 0
 ... ..
.
..
.
..
.
..
.
..
.
.. 
.
AEij = 0 · · ·

0 aii 0 ··· 0 i
 .. .. .. .. .. .. .. 

. . . . . . .
0 ··· 0 0 0 ··· 0

j
0 · · · 0 0 0 ··· 0
 ... ..
.
..
.
..
.
..
.
..
.
.. 
.
Eij A = 0 · · ·

0 ajj 0 ··· 0 i
 .. .. .. .. .. .. .. 

. . . . . . .
0 ··· 0 0 0 ··· 0

Then AEij = Eij A implies that aii = ajj . Hence above all, A = cIn where c = a11 .

28. (very difficult, used in proving the uniqueness of RREF) Suppose A is a
m × n matrix. The i-th column of A is denoted by Ai . Let 1 ≤ i1 , . . . , ik ≤ n.
Denote
[Ai1 |Ai2 | . . . |Aik ]
a m × k matrix with the j-th column equal to Aij .
(a) Let A, B be m × n matrices. Let 1 ≤ i1 , . . . , ik ≤ n. Let
A0 = [Ai1 |Ai2 | . . . |Aik ] , B 0 = [Bi1 |Bi2 | . . . |Bik ] .
Show that if A is row equivalent to B, then A0 is row equivalent to B 0 .

30
(b) Let A, B be m × n matrices. Suppose A and B are row equivalent and B is a
RREF. Let 1 ≤ d ≤ n. Let
A0 = [A1 |A2 | . . . |Ad−1 ] , B 0 = [B1 |B2 | . . . |Bd−1 ] .
Show that if column d of B is a pivot column, then LS(A0 , Ad ) has no solution.
(c) Let A, B be m × n matrices. Suppose A and B are row equivalent and B is
a RREF. Let 1 ≤ d ≤ n. Suppose column d of B is not a pivot column. Let
1 ≤ d1 < d2 < · · · < dk < d be all the indexes of pivot columns < d. Let

A0 = [Ad1 |Ad2 | . . . |Adk ] , B 0 = [Bd1 |Bd2 | . . . |Bdk ] .

Show that LS(A0 , Ad ) and LS(B 0 , Bd ) are equivalent and hence show that
LS(A0 , Ad ) has a unique solution. Furthermore, suppose (s1 , s2 , . . . , sk ) is the
solution, then  
s1
 .. 
.
s 
 
Bd =  k 
0
.
 .. 
0
(d) Let  
1 2 5
A= 1 1 3 
−1 0 −1
Let B be the RREF equivalent to A. Obviously column 1 of B is a pivot
column.
i. Using part (b), show that column 2 of B is a pivot column.
ii. Given that (1, 2, −1) is a solution of LS(A, 0). Using part (b), show that
column 3 of B is not a pivot column.
iii. Using part (c), find the last column of B. Hence find B.
iv. Suppose C is another RREF row equivalent to A, explain why B = C?
(e) Let A be a 3 × 5 matrix, given the following facts, find the RREF of A.
i. A1 is not a zero column.
ii. LS([A1 ], A2 ) has a unique solution x1 = 2.
iii. LS([A1 |A2 ], A3 ) has no solution.
iv. LS([A1 |A2 |A3 ], A4 ) has no solution.
v. LS([A1 |A3 |A4 ], A5 ) has a unique solution (−2, 3, 4).
(f) Let A be a m × n matrix. Suppose B is RREF and is row equivalent to A.
Show that B is unique (very very difficult).

Answer.

31
(a) Since A is row equivalent to B, there is a sequence of elementary row opera-
tions E1 , E2 , . . . , En preformed on A to get B. If we denote by EP the matrix
obtained from a matrix P by performing an elementary row operation E, then
we have B = En (En−1 (· · · (E2 (E1 A)) · · · )). For simplicity we omit the paren-
theses and just write B = En En−1 · · · E2 E1 A. Let us first show that if Q = EP
where P and Q are matrices and E is an elementary row operation, then

[Qi1 |Qi2 | . . . |Qik ] = E [Pi1 |Pi2 | . . . |Pik ] . (4)

0
Let P = (p`,j ) and Q = (q`,j ). Let q`,j be the (`, j)-entry of E [Pi1 |Pi2 | . . . |Pik ].
Suppose that E swaps two different rows of a matrix, say the r-th and the s-th
rows. Then for each j,

 p`,j if ` 6= r, s
q`,j = ps,j if ` = r .
pr,j if ` = s


Now we have, for each j,

 
 p`,ij if ` 6= r, s  q`,ij if ` 6= r, s
0
q`,j = ps,i if ` = r = qr,i if ` = r = q`,ij .
 p j if ` = s  q j if ` = s
r,ij s,ij

In other words, (1) is true for this type of E.

Suppose on the other hand that E adds the r-th row multiplied by a non-zero
constant c to the s-th row (r 6= s). The for each j,

p`,j if ` 6= s
q`,j = .
cpr,j + ps,j if ` = s
Now we have, for each j,
 
0 p`,ij if ` 6= s q`,ij if ` 6= s
q`,j = = = q`,ij .
cpr,ij + ps,ij if ` = s qs,ij if ` = s

In other words, (1) is also true for this type of E, and hence (1) is true for any
type of elementary row operations.
To complete the proof, let Pt (t = 0, 1, 2, . . . , n) be defined successively by
P (0) = A and P (t) = Et P (t−1) for 1 ≤ t ≤ n. Note that P (n) = B. Then
we apply what we have just proved to P (t) = Et P (t−1) and we get, for t =
1, 2, . . . , n,
h i h i
(t) (t) (t) (t−1) (t−1) (t−1)
Pi1 |Pi2 | . . . |Pik = Et Pi1 |Pi2 | . . . |Pik .

32
 It follows that
B 0 = [Bi1 |Bi2 | . . . |Bik ]
h i
(n) (n) (n)
= Pi1 |Pi2 | . . . |Pik
h i
(n−1) (n−1) (n−1)
= E n Pi 1 |Pi2 | . . . |Pik
h i
(n−2) (n−2) (n−2)
= En En−1 Pi1 |Pi2 | . . . |Pik
= ···
h i
(0) (0) (0)
= En En−1 · · · E2 E1 Pi1 |Pi2 | . . . |Pik
= En En−1 · · · E2 E1 [Ai1 |Ai2 | . . . |Aik ]
= En En−1 · · · E2 E1 A0

In other words, B 0 is obtained from A0 by performing the same sequence of ele-

mentary row operations as what are performed to transform A to B. Therefore,
A0 and B 0 are row equivalent.
(b) By (a), the systems LS(A0 , Ad ) and LS(B 0 , Bd ) are equivalent because all the
columns of these systems come fromA and B respectively. Then it suffices to
show that LS(B 0 , Bd ) has no solution. To show this, let the i-entry of Bd is 1.
Because Bd is a pivot columns, so the i-th row of B 0 is zero while the i-th entry
of Bd is 1. Therefore the i-row of the augmented matrix [B 0 |Bd ] corresponding
to the equations
0 = 1.
It follows that the system LS(B 0 , Bd ) is inconsistent.
(c) By (a), the systems LS(A0 , Ad ) and LS(B 0 , Bd ) are equivalent because all
the columns of these systems come from A and B respectively. Now consider
LS(B 0 , Bd ), its augmented matrix is a RREF (every column of B 0 is a pivot col-
umn!) and its (unique) solution is given by ([B]1d , [B]2d , . . . , [B]kd ). It follows
that if we denote the solution by (s1 , s2 , . . . , sk ), then sj = [B]jd for 1 ≤ j ≤ k.
Together with [B]jd = 0 for j > k (since Bd is not a pivot column), we conclude
that  
s1
 .. 
.
s 
 
Bd =  k  .
0
.
 .. 
0
(d) i. Suppose to the contrary that column 2 of B is a not pivot column. Then
apply (c) with d = 2 and d1 = 1 to the present situation, we see that the
system 
 x1 = 2
x1 = 1
−x1 = 0


33
 has a unique solution. But it is impossible since x1 cannot be equal to three
distinct numbers at the same time. Hence we conclude column 2 of B is a
pivot column.
ii. Suppose to the contrary that column 3 of B is a pivot column. Then
apply (b) with d = 3 to the present situation, we see that the system
LS([A1 |A2 ], A3 ) has no solution. But it is impossible since (1, 2) is a solu-
tion to this system by what is given. Hence we conclude column 3 of B is
not a pivot column.
iii. By (c), we get  
1
B3 = 2 .

0
Since the first and the second columns of B is pivot columns, it follows that
 
1 0 1
B = 0 1 2 .
0 0 0

iv. From (d)iii, we see that any matrix which is row equivalent to A must be
equal to  
1 0 1
0 1 2 .
0 0 0
That means if C is another such matrix, we must have B = C.
(e) • Let B be a RREF of A.
• Because of i. B1 is a pivot column.
• By (b) and (c), B2 is not a pivot column and is given by
 
2
0 .
0

• By (c), B3 is a pivot column (since LS([A1 |A2 ], A3 ) has no solution implies

LS(A1 , A3 )) has no solution).
• Similarly as above, B4 is a pivot column.
• By (b) and (c), B5 is not a pivot column and is given by
 
−2
 3  (we already know that B1 , B3 , B4 are pivot columns).
4

It follows that B is given by

 
1 2 0 0 −2
0 0 1 0 3  .
0 0 0 1 4

34
(f) Following up the idea from (e), we determine the matrix B as follows:
• If A1 = 0, then B1 = 0 by (a) (since A1 is row equivalent to B1 ). Otherwise
B1 is a pivot column.
• Continue the above step until we find a non-zero column of A, in which
case a pivot column of B is obtained.
• Assume we have determined the first d − 1 rows (d ≥ 2) of the matrix B.
Let 1 ≤ d1 < d2 < · · · < dk < d be all the indices of the pivot columns we
have found.
• Consider the system LS([A1 |A2 | . . . |Ad−1 ], Ad ). If it has a solution, then
Bd is not a pivot column by (b), and then by (c), we find that the system
LS([Ad1 |Ad2 | . . . |Adk ], Ad ) has a unique solution. Find it and use the same
part to determine Bd . If, to the contrary, the original system has no solu-
tion, then nor does the system LS([Ad1 |Ad2 | . . . |Adk ], Ad ), and by (c), we
see that Bd is a pivot column in this case. In any case, we obtain Bd .
• Continue the aforementioned step until d = n, and we obtain the whole
matrix B.
• Since the output Bd of each step is completely determined by the nature
of A (i.e. the solution sets of the systems LS([A1 |A2 | . . . |Ad−1 ], Ad ) and
LS([Ad1 |Ad2 | . . . |Adk ], Ad )), it follows that B is unique.


35