# Matrix Multiplication Interpretation

According to Lecture 3 (from approximately 07:00 - 12:00) of Gilbert Strang's course on linear algebra,

Given two matrices $A$, $B$ and their product $C$:

1) Columns of C are combinations of columns of A

2) Rows of C are combinations of rows of B

However, to me, it seems the opposite is observed. My confusion is probably best illustrated explicitly.

Suppose, as above, two matrices and their product such that:

$$\begin{bmatrix} a_{11} & \ldots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{m1} & \ldots & a_{mn} \end{bmatrix} \times \begin{bmatrix} b_{11} & \ldots & b_{1p} \\ \vdots & \ddots & \vdots \\ b_{n1} & \ldots & b_{np} \end{bmatrix} = \begin{bmatrix} c_{11} & \ldots & c_{1p} \\ \vdots & \ddots & \vdots \\ c_{m1} & \ldots & c_{mp} \end{bmatrix}$$

If we define a combination, $c_{ij}$, as the sum of $n$ products such that:

$$c_{ij} = \sum_{j=1}^{n} a_{ij}b_{ji} \ldots \text{ Note the iteration is across } j \text{ not } i.$$

Then entries for a given column, let's say column 1, in $C$ are given by:

$$\begin{bmatrix} c_{1,1} = \sum_{i=1}^{n}a_{1i}b_{i1} \\ c_{2,1} = \sum_{i=1}^{n}a_{2i}b_{i1} \\ \vdots \\ c_{m,1} = \sum_{i=1}^{n}a_{mi}b_{i1} \end{bmatrix}$$

Notice that the $b_{i1}$ term (column $1$ of $B$) is constant throughout the calculation of column 1, but the $a_{ji}$ term (rows of $A$) varies across the calculation of column 1 (depending on the corresponding element index); wouldn't this suggest that columns of $C$ are combinations of columns of $B$ (and not columns of $A$), and rather the rows of $A$ provide the coefficients for the combination resulting in element $i$ for a given column of $C$?

Using the same logic also suggests that rows of $C$ are various combinations of the rows of $A$ (as they are held constant across calculations for a given row, whilst the columns of $B$ provide the coefficients for the row of $A$ resulting in the elements of a given row of $C$).

-

Let $A = \begin{bmatrix} a_1 \cdots a_n\end{bmatrix}$. Then $Ax = \sum_k x_k a_k$, ie, $Ax$ is a combination of the columns of $A$.
If $B = \begin{bmatrix} b_1 \cdots b_m\end{bmatrix}$, then you can see that $C=AB = \begin{bmatrix} A b_1 \cdots A b_m\end{bmatrix}$, so the columns of $C$ are of the form $Ab_k$ and so are combinations of the columns of $A$.
Since $C^T = B^T A^T$, you can apply the above observation to see that the columns of $C^T$ are combinations of the columns of $B^T$. Since the columns of $C^T$ are the transposes of the rows of $C$, you have the desired result.
I believe I understand now. Given: $$A \times B = C$$ $$= \begin{bmatrix} a & b \\ c & d \end{bmatrix} \times \begin{bmatrix} e & f \\ g & h \end{bmatrix} = \begin{bmatrix} ae+bg & af+bh \\ ce+dg & cf+dh \end{bmatrix}$$ The first column of $C$, for example, is: $\begin{bmatrix}ae+bg\\ce+dg\end{bmatrix}$ is a combination of all of the columns of $A$ (with coefficients of $e$ and $g$ respectively), not just the first column; this was the source of my confusion. Thank you! –  Will Clyne Apr 7 '13 at 19:10