math111_logo Composition and Matrix Multiplication


Exercise

1) Prove that transformations T and S are onto ⇒ The composition TS is onto.

Answer For any b, by T onto, we can find y, such that T(y) = b. For this y, by S onto, we can find x, such that S(x) = y. Then we have

TS(x) = T(S(x)) = T(y) = b.

Thus any b is the image of some element under the transformation TS. This shows TS is onto.

2) What about the converse? In other words, if the composition TS is onto, are the transformations T and S onto?

Answer If TS is onto, then for any b, we have x, such that T(S(x)) = b. In particular, b is the image of S(x) under the transformation T. The observation tells us T must be onto.

On the other hand, S is not necessarily onto. An example is given by S = IDs: student → integer, T = Last-Digit: integer → {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

3) Rephrase your conclusions in the first and second part in terms of matrix products.

Answer If Ay = b and Bx = c has solutions for any b and c, then ABx = b has solution for any b.

Conversely, if ABx = b has solutions for any b, then Ay = b has solutions for any b. However, Bx = c may not have solution for any c.

Alternatively: If all rows of A and B are pivot, then all rows of AB are pivot. Conversely, if all rows of AB are pivot, then all rows of A (but not necessarily B) are also pivot.