math111_logo Composition and Matrix Multiplication


Exercise

1) Prove that transformations T and S are ono-to-one ⇒ The composition TS is one-to-one.

Answer Let T and S be one-to-one. Then

TS(x) = TS(x') ⇒ S(x) = S(x') ⇒ x = x'

where the first ⇒ follows from T being one-to-one, and the second ⇒ follows from S being one-to-one. The whole implication means TS is one-to-one.

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

Answer Suppose TS is ono-to-one. Then we have

S(x) = S(x') ⇒ TS(x) = TS(x') ⇒ x = x'

where the first ⇒ is obtained by applying T to both sides, and the second ⇒ follows from TS being one-to-one. The whole implication means S is one-to-one.

On the other hand, T is not necessarily one-to-one. An example is given by S = IDs: student → integer, T = Absolute-Value: integer → non-negative integer. Note that student ID numbers are always positive.

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

Answer If solutions of Ay = b and Bx = c are unique, then the solution of ABx = b is unique.

Conversely, if the solution of ABx = b is unique, then solution of Bx = c is unique. However, solution of Ay = b may not be unique.

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