# Matrix Multiplication and Function Composition

Given the vector space $F^n$ and two linear function $T,S:F^n \rightarrow F^n$ is it true that multiplying the representative matrices according to the standard basis of $T$ and $S$ is equivalent to the composition of their explicit formula's? I.E. Given a vector v in $F^n$ is $[T]_E[S]_Ev = [TS]_Ev = T(S(v))$ ?

-
Si, si può controllare scrivendo esplicitamente il prodotto matriciale. Usando la linearità è abbastanza immediato vedere che è così. –  Vittorio Patriarca Jun 13 '12 at 17:52
This follows naturally from the definition of $[T]_E$ and the fact that given matrices A, B and a vector x, $A(Bx) = (AB)x$. –  Karolis Juodelė Jun 13 '12 at 18:11
I guess this results also from the fact that the explicit formula for a linear function of the type mentioned above is always from the standard basis to the standard basis? –  Robert S. Barnes Jun 13 '12 at 18:15
In fact, matrix multiplication is defined the (somewhat strange) way it is precisely so that it corresponds to composition of linear transformations. –  Arturo Magidin Jun 13 '12 at 18:59

I'm reading this question as: "Does matrix multiplication really give rise to the matrix for the composition of maps that the matrices represent?" I'm always using matrices operating on the left of column vectors, in my notation below.

Define $\pi_i:F^n\rightarrow F$ by projecting onto the $i$th coordinate. Define $\mu_j:F\rightarrow F^n$ by inserting the input value into the $j$th coordinate.

How do these maps relate to the matrix representation of a function? Let $f:F^n\rightarrow F^n$ be represented by $A=[A]_{ij}$ in the standard basis. If you compute $\mu_j(1)$, you get the unit vector with a 1 in the $j$th coordinate. To affect $f$ on this, you multiply on the left with its matrix $A$. So, $A\mu_j(1)$ is the $j$th column of $A$. Now by applying $\pi_i$ after this, you will pick out the $i$th entry of the $j$th row. So, $\pi_i(A\mu_j(1))=A_{ij}$. This shows that $\pi_i f\mu_j=A_{ij}$. This last $A_{ij}$ is the $1\times 1$ matrix representation of a linear transformation of $F$ into $F$.

Can you see that $\sum_{k=1}^n\mu_k(\pi_k(v))=v$ for all $v\in F^n$? This means that $\sum_{k=1}^n\mu_k\pi_k=Id_V$, the identity on $V$.

Let a transformation $g:F^n\rightarrow F^n$ be represented by the matrix $B=[B]_{ij}$ in standard basis. We will now show that $[BA]_{ij}$ is the matrix representing the composition $gf$. This will be true if $\pi_i gf \mu_j=[BA]_{ij}$, by our discussion before.

We compute that $\pi_i gf \mu_j=\pi_i g \mathrm{Id}_V f \mu_j=\pi_i g(\sum_{k=1}^n \mu_k\pi_k)f \mu_j=\sum_{k=1}^n\pi_i g \mu_k\pi_kf \mu_j=\sum_{k=1}^n B_{ik}A_{kj}=[BA]_{ij}$. So there you have it: the components of $gf$ are given by matrix multiplication!

-
That is the question I'm asking, if somewhat more elegantly stated :-) –  Robert S. Barnes Jun 13 '12 at 19:08
@RobertS.Barnes I thought so... I remember learning this for the first time and finally thinking "Holy crap, matrix multiplication is natural!" –  rschwieb Jun 13 '12 at 19:47

More pedantically:

Let $[T]_{ij}$ be the representation in the standard basis $\{e_i\}$ of the operator $T$. Suppose $x\in F^n$, then we can write $x = \sum_j [x]_j e_j$.

The aim is to show that $[TS]_{ij} = \sum_k [T]_{ik} [S]_{kj}$. Note that since $\{e_i\}$ is a basis, the matrix representation is unique, ie, if the matrix $\alpha_1$ and $\alpha_2$ represent the operator $A$, then $\alpha_1 = \alpha_2$.

Then we have \begin{align} T(Sx) & = T(\sum_j [x]_j S e_j) \\ & = T(\sum_j [x]_j \sum_k [S]_{kj} e_k) \\ & = \sum_j [x]_j \sum_k [S]_{kj} T e_k \\ & = \sum_j [x]_j \sum_k [S]_{kj} \sum_i [T]_{ik} e_i \\ & = \sum_j [x]_j \sum_i \sum_k [T]_{ik} [S]_{kj} e_i \\ & = (TS)x \\ & = \sum_j [x]_j \sum_i [TS]_{ij} e_i. \end{align} The desired result follows from uniqueness.

-