Exercise $11$, Section $3.B$ - Linear Algebra Done Right Exercise: Suppose $S_1,\dots,S_n$ are injective linear maps such that $S_1S_2\cdots S_n$
makes sense. Prove that $S_1S_2\cdots S_n$ is injective.
Proof: We prove by induction. clearly $S_1$ is injective. Suppose inductively that $S_1S_2\cdots S_{n-1}$ is injective. We want to show that $S_1S_2\cdots S_n$ is injective. We are given that $S_n$ is injective and that $S_n(v)\in Domain(S_{n-1})$. By the induction hypothesis we know that $S_1S_2\cdots S_{n-1}$ is injective. Hence, $S_1S_2\dots S_n$ is injective.
Is the proof correct?
Edit: I thought of a different proof.
Proof $2$: Given that $S_1,\dots,S_n$ are all injective. We see that for any $u,v\in \text{domain }S_n$ we have that $S_n(u)=S_n(v)\implies u=v$.
Then we have that $S_{n-1}(S_nu)=S_{n-1}(S_nv)\implies S_n(u)=S_n(v)\implies u=v$.
Continuing on in this fashion we conclude that $S_1\cdots S_n$ is injective.
 A: There's one small subtlety, which is that at no point do you prove that the composition of exactly two injectives is injective. You can fix this in one of two ways. First, you can deduce this from your inductive hypothesis, by choosing $S'_1 = S_1...S_{n-1}$, $S'_2 = S_n$ and then choosing $n-2$ maps to be the identity, which are also injective, in order to apply the hypothesis.
The second thing you could do, is just use strong induction instead of induction. This is the same as induction, except instead of assuming that $S_1...S_{n-1}$ is injective, you assume all compositions of injectives of length less than $n$ remain injective. Now the hypothesis includes the case of $2$ maps.
A third thing you could do is make your base case for induction the case of $2$ linear maps. Then the proof of the inductive step would follow from the base case. This might be the most elegant approach.
That strong induction is equivalent to induction has been discussed elsewhere on this site.
A: Another method:
A matrix $M$ induces an injective linear map if and only if there is a matrix $B$ so that $BM = I$ (to see this, use the row reduction algorithm). So if each $M_i$ is injective we have a $B_i$ satisfying $B_iM_i = I$, and so $\prod M_i$ is injective by virtue of the fact that $\left(\prod B_{n-i}\right)\left( \prod M_i \right)= I$.
A: Let $S_1S_2...S_{n-1}S_n(u)=S_1S_2...S_{n-1}S_n(v)$ where $u,v\in domain(S_1S_2...S_n)$
or $S_1S_2...S_{n-1}(S_n(u))=S_1S_2...S_{n-1}(S_n(v))$
$\implies S_n(u)=S_n(v)\ \ \ \ \ \ \ \ \            (\because S_1S_2....S_{n-1}$ is injective by hypothesis)
$\implies u=v\ \ \ \ \   (\because S_n$ is injective)
so, $S_1S_2...S_{n-1}S_n$ is injective.
