# Multiplication of matrices of linear maps

Consider maps $S: U \mapsto V$ and $T:V\mapsto W.$ The composition $TS$ is a linear map from $U \mapsto W.$

Let $\mathcal{M(T)} = \begin{pmatrix} a_{1,1}& \ldots & a_{1,n}\\ \vdots & & \vdots \\ a_{m,1}& \ldots & a_{m,n} \end{pmatrix}$ and $\mathcal{M(S)} = \begin{pmatrix} b_{1,1}& \ldots & b_{1,p}\\ \vdots & & \vdots \\ b_{n,1}& \ldots & b_{n,p} \end{pmatrix}$

\begin{align} \mathcal{TS}u_k =& \mathcal{T} \left(\sum_{r=1}^n b_{r,k}v_r \right) \\=& \sum_{r=1}^n b_{r,k} \sum_{j=1}^m a_{j,r} w_j \\=&\sum_{j=1}^m \left(\sum_{r=1}^n a_{j,r} b_{r,k} \right)w_j\end{align}

My main question is, why can the matrix of a linear map be expressed as a sum?

In your notation, if $B = \{u_{1}, \dots, u_{p}\}$ is a basis of $U$, $B' = \{v_{1}, \dots, v_{n}\}$ is a basis of $V$, and $S:U \to V$ is linear, there exist unique scalars $b_{r,k}$ with $r = 1, \dots, n$ and $k=1, \dots, p$, such that $$S(u_{k}) = \sum_{r=1}^{n} b_{r,k} v_{r}.$$ The "matrix of $S$ with respect to the bases $B$ and $B'$" is, by definition, the rectangular array obtained by putting $b_{r,k}$ into the $r$th row and $k$th column. This array completely specifies $S$: Every element $u$ of $U$ can be written uniquely as a linear combination $u = \sum_k c_{k} u_{k}$ for some scalars $c_{k}$, and by linearity of $S$, $$S(u) = \sum_{k=1}^{p} c_{k} S(u_{k}) = \sum_{k=1}^{p} c_{k} \sum_{r=1}^{n} b_{r,k} v_{r} = \sum_{r=1}^{n} \left(\sum_{k=1}^{p} b_{r,k} c_{k} \right) v_{r}.$$ (This equation also explains where the seemingly-peculiar definition of matrix multiplication comes from. The expression in parentheses is the $r$th coordinate of $S(u)$, a.k.a. the $r$th row of the product of the matrix of $S$ with the coordinate vector of $u$ with respect to $B$.)