# Matrix multiplication: interpreting and understanding the process

I have just watched the first half of the 3rd lecture of Gilbert Strang on the open course ware with link:

http://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-spring-2010/video-lectures/

It seems that with a matrix multiplication $AB=C$, that the entries as scalars, are formed from the dot product computations of the rows of $A$ with the columns of $B$. Visual interpretations from mechanics of overlpaing forces come to mind immediately because that is the source for the dot product (inner product).

I see the rows of $C$ as being the dot product of the rows of $B$, with the dot product of a particular row of $A$. Similar to the above and it is easy to see this from the individual entries in the matrix $C$ as to which elements change to give which dot products.

For understanding matrix multiplication there is the geometrical interpretation, that the matrix multiplication is a change in the reference system since matrix $B$ can be seen as a transormation operator for rotation, scalling, reflection and skew. It is easy to see this by constructing example $B$ matrices with these effects on $A$. This decomposition is a strong argument and is strongly convincing of its generality. This interpreation is strong but not smooth because I would find smoother an explanation which would be an interpretation begining from the dot product of vectors and using this to explain the process and the interpretation of the results (one which is a bit easier to see without many examples of the putting numbers in and seeing what comes out which students go through).

I can hope that sticking to dot products throughout the explanation and THEN seeing how these can be seen to produce scalings, rotations, and skewings would be better. But, after some simple graphical examples I saw this doesn't work as the order of the columns in matrix $B$ are important and don't show in the graphical representation.

The best explanation I can find is at Yahoo Answers. It is convincing but a bit disappointing (explains why this approach preserves the "composition of linear transformations"; thanks @Arturo Magidin). So the question is: Why does matrix multiplication happen as it does, and are there good practical examples to support it? Preferably not via rotations/scalings/skews (thanks @lhf).

-
What is your question? –  lhf Mar 1 '11 at 19:01
Matrix multiplication is defined the way it does because it then coincides with composition of linear transformations. There are other matrix multiplications (e.g., the Kronecker product, which is entry-by-entry), but the great advantage of the "usual" matrix multiplication is that it corresponds to composition of linear transformations. –  Arturo Magidin Mar 1 '11 at 19:09
Matrix multiplication doesn't "happen", it is defined a certain way. Why it is defined that way is precisely so that it corresponds to compositions of linear transformations: nothing more and nothing else. For "practical examples", write out linear transformations in terms of the basis, write out what the composition is, and you'll see it corresponds exactly to matrix multiplication. There is nothing to "support", the definition was made with one particular purpose in mind, and it achieves that purpose, period. –  Arturo Magidin Mar 1 '11 at 19:26
Supporting Arturo: Matrices are just used to visualise linear transformations, in in this manner the composition of two linear transformations $L_1$ and $L_2$ is a new linear transformation $L_3=L_1\circ L_2$ which when you write it out as matrices is the product of the matrices. –  AD. Mar 1 '11 at 19:45
I feel like this is then a question about history: why did (= what historical motivations) matrix multiplication get defined like it is? Did the dot product (which is itself magical in that it gives a projection) come first? –  Mitch Mar 1 '11 at 21:11

Some comments first. There are several serious confusions in what you write. For example, in the third paragraph, having seen that the entries of $AB$ are obtained by taking the dot product of the corresponding row of $A$ with column of $B$, you write that you view $AB$ as a dot product of rows of $B$ and rows of $A$. It's not.

For another example, you talk about matrix multiplication "happening". Matrices aren't running wild in the hidden jungles of the Amazon, where things "happen" without human beings. Matrix multiplication is defined a certain way, and then the definition is why matrix multiplication is done the way it is done. You may very well ask why matrix multiplication is defined the way it is defined, and whether there are other ways of defining a "multiplication" on matrices (yes, there are; read further), but that's a completely separate question. "Why does matrix multiplication happen the way it does?" is pretty incoherent on its face.

Another example of confusion is that not every matrix corresponds to a "change in reference system". This is only true, viewed from the correct angle, for invertible matrices.

Standard matrix multiplication. Matrix multiplication is defined the way it is because it corresponds to composition of linear transformations. Though this is valid in extremely great generality, let's focus on linear transformations $T\colon \mathbb{R}^n\to\mathbb{R}^m$. Since linear transformations satisfy $T(\alpha\mathbf{x}+\beta\mathbf{y}) = \alpha T(\mathbf{x})+\beta T(\mathbf{y})$, if you know the value of $T$ at each of $\mathbf{e}_1,\ldots,\mathbf{e}_n$, where $\mathbf{e}^n_i$ is the (column) $n$-vector that has $0$s in each coordinate except the $i$th coordinate where it has a $1$, then you know the value of $T$ at every single vector of $\mathbb{R}^n$.

So in order to describe the value of $T$, I just need to tell you what $T(\mathbf{e}_i)$ is. For example, we can take $$T(\mathbf{e}_i) = \left(\begin{array}{c}a_{1i}\\a_{2i}\\ \vdots\\ a_{mi}\end{array}\right).$$ Then, since $$\left(\begin{array}{c}k_1\\k_2\\ \vdots\\k_n\end{array}\right) = k_1\mathbf{e}_1 + \cdots +k_n\mathbf{e}_n,$$ we have $$T\left(\begin{array}{c}k_1\\k_2\\ \vdots\\ k_n\end{array}\right) = k_1T(\mathbf{e}_1) + \cdots +k_nT(\mathbf{e}_n) = k_1\left(\begin{array}{c}a_{11}\\a_{21}\\ \vdots\\a_{m1}\end{array}\right) + \cdots + k_n\left(\begin{array}{c}a_{1n}\\a_{2n}\\ \vdots\\ a_{mn}\end{array}\right).$$

It is very fruitful, then to keep track of the $a_{ij}$ in some way, and given the expression above, we keep track of them in a matrix, which is just a rectangular array of real numbers. We then think of $T$ as being "given" by the matrix $$\left(\begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & \cdots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{array}\right).$$ If we want to keep track of $T$ this way, then for an arbitrary vector $\mathbf{x} = (x_1,\ldots,x_n)^t$ (the ${}^t$ means "transpose"; turn every rown into a column, every column into a row), then we have that $T(\mathbf{x})$ corresponds to: $$\left(\begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & \cdots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{array}\right) \left(\begin{array}{c} x_1\\x_2\\ \vdots\\ x_n\end{array}\right) = \left(\begin{array}{c} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n\\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n\\ \vdots\\ a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n \end{array}\right).$$

What happens when we have two linear transformations, $T\colon \mathbb{R}^n\to\mathbb{R}^m$ and $S\colon\mathbb{R}^p\to\mathbb{R}^n$? If $T$ corresponds as above to a certain $m\times n$ matrix, then $S$ will likewise correspond to a certain $n\times p$ matrix, say $$\left(\begin{array}{cccc} b_{11} & b_{12} & \cdots & b_{1p}\\ b_{21} & b_{22} & \cdots & b_{2p}\\ \vdots & \vdots & \ddots & \vdots\\ b_{n1} & b_{n2} & \cdots & b_{np} \end{array}\right).$$ What is $T\circ S$? First, it is a linear transformation because composition of linear transformations yields a linear transformation. Second, it goes from $\mathbb{R}^p$ to $\mathbb{R}^m$, so it should correspond to an $m\times p$ matrix. Which matrix? If we let $\mathbf{f}_1,\ldots,\mathbf{f}_p$ be the (column) $p$-vectors given by letting $\mathbf{f}_j$ have $0$s everywhere and a $1$ in the $j$th entry, then the matrix above tells us that $$S(\mathbf{f}_j) = \left(\begin{array}{c}b_{1j}\\b_{2j}\\ \vdots \\b_{nj}\end{array}\right) = b_{1j}\mathbf{e}_1+\cdots + b_{nj}\mathbf{e}_n.$$

So, what is $T\circ S(\mathbf{f}_j)$? This is what goes in the $j$th column of the matrix that corresponds to $T\circ S$. Evaluating, we have: \begin{align*} T\circ S(\mathbf{f}_j) &= T\Bigl( S(\mathbf{f}_j)\Bigr)\\ &= T\Bigl( b_{1j}\mathbf{e}_1 + \cdots + b_{nj}\mathbf{e}_n\Bigr)\\ &= b_{1j} T(\mathbf{e}_1) + \cdots + b_{nj}T(\mathbf{e}_n)\\ &= b_{1j}\left(\begin{array}{c} a_{11}\\ a_{21}\\ \vdots\\ a_{m1}\end{array}\right) + \cdots + b_{nj}\left(\begin{array}{c} a_{1n}\\a_{2n}\\ \vdots\\ a_{mn}\end{array}\right)\\ &= \left(\begin{array}{c} a_{11}b_{1j} + a_{12}b_{2j} + \cdots + a_{1n}b_{nj}\\ a_{21}b_{1j} + a_{22}b_{2j} + \cdots + a_{2n}b_{nj}\\ \vdots\\ a_{m1}b_{1j} + a_{m2}b_{2j} + \cdots + a_{mn}b_{nj} \end{array}\right). \end{align*} So if we want to write down the matrix that corresponds to $T\circ S$, then the $(i,j)$th entry will be $$a_{i1}b_{1j} + a_{i2}b_{2j} + \cdots + a_{in}b_{nj}.$$ So we define the "composition" or product of the matrix of $T$ with the matrix of $S$ to be precisely the matrix of $T\circ S$. We can make this definition without reference to the linear transformations that gave it birth: if the matrix of $T$ is $m\times n$ with entries $a_{ij}$ (let's call it $A$); and the matrix of $S$ is $n\times p$ with entries $b_{rs}$ (let's call it $B$), then the matrix of $T\circ S$ (let's call it $A\circ B$ or $AB$) is $m\times p$ and with entries $c_{k\ell}$, where $$c_{k\ell} = a_{k1}b_{1\ell} + a_{k2}b_{2\ell} + \cdots + a_{kn}b_{n\ell}$$ by definition. Why? Because then the matrix of the composition of two functions is precisely the product of the matrices of the two functions. We can work with the matrices directly without having to think about the functions.

In point of fact, there is nothing about the dot product which is at play in this definition. It is essentially by happenstance that the $(i,j)$ entry can be obtained as a dot product of something. In fact, the $(i,j)$th entry is obtained as the matrix product of the $1\times n$ matrix consisting of the $i$th row of $A$, with the $n\times 1$ matrix consisting of the $j$th column of $B$. Only if you transpose this column can you try to interpret this as a dot product. (In fact, the modern view is the other way around: we define the dot product of two vectors as a special case of a more general inner product, called the Frobenius inner product, which is defined in terms of matrix multiplication, $\langle\mathbf{x},\mathbf{y}\rangle =\mathrm{trace}(\overline{\mathbf{y}^t}\mathbf{x})$).

And because product of matrices corresponds to composition of linear transformations, all the nice properties that composition of linear functions has will automatically also be true for product of matrices, because products of matrices is nothing more than a book-keeping device for keeping track of the composition of linear transformations. So $(AB)C = A(BC)$, because composition of functions is associative. $A(B+C) = AB + AC$ because composition of linear transformations distributes over sums of linear transformations (sums of matrices are defined entry-by-entry because that agrees precisely with the sum of linear transformations). $A(\alpha B) = \alpha(AB) = (\alpha A)B$, because composition of linear transformations behaves that way with scalar multiplication (products of matrices by scalar are defined the way they are precisely so that they will correspond to the operation with linear transformations).

So we define product of matrices explicitly so that it will match up composition of linear transformations. There really is no deeper hidden reason. It seems a bit incongruous, perhaps, that such a simple reason results in such a complicated formula, but such is life.

Another reason why it is somewhat misguided to try to understand matrix product in terms of dot product is that the matrix product keeps track of all the information lying around about the two compositions, but the dot product loses a lot of information about the two vectors in question. Knowing that $\mathbf{x}\cdot\mathbf{y}=0$ only tells you that $\mathbf{x}$ and $\mathbf{y}$ are perpendicular, it doesn't really tell you anything else. There is a lot of informational loss in the dot product, and trying to explain matrix product in terms of the dot product requires that we "recover" all of this lost information in some way. In practice, it means keeping track of all the original information, which makes trying to shoehorn the dot product into the explanation unnecessary, because you will already have all the information to get the product directly.

Examples that are not just "changes in reference system". Note that any linear transformation corresponds to a matrix. But the only linear transformations that can be thought of as "changes in perspective" are the linear transformations that map $\mathbb{R}^n$ to itself, and which are one-to-one and onto. There are lots of linear transfomrations that aren't like that. For example, the linear transformation $D$ from $\mathbb{R}^3$ to $\mathbb{R}^2$ defined by $$D\left(\begin{array}{c} a\\b\\c\end{array}\right) = \left(\begin{array}{c}b\\2c\end{array}\right)$$ is not a "change in reference system" (because lots of nonzero vectors go to zero, but there is no way to just "change your perspective" and start seeing a nonzero vector as zero) but is a linear transformation nonetheless. The corresponding matrix is $2\times 3$, and is $$\left(\begin{array}{cc} 0 & 1 & 0\\ 0 & 0 & 2 \end{array}\right).$$ Now consider the linear transformation $U\colon\mathbb{R}^2\to\mathbb{R}^2$ given by $$U\left(\begin{array}{c}x\\y\end{array}\right) = \left(\begin{array}{c}3x+2y\\ 9x + 6y\end{array}\right).$$ Again, this is not a "change in perspective", because the vector $\binom{2}{-3}$ is mapped to $\binom{0}{0}$. It has a matrix, $2\times 2$, which is $$\left(\begin{array}{cc} 3 & 2\\ 9 & 6 \end{array}\right).$$ So the composition $U\circ T$ has matrix: $$\left(\begin{array}{cc} 3 & 2\\ 9 & 6 \end{array}\right) \left(\begin{array}{ccc} 0 & 1 & 0\\ 0 & 0 & 2 \end{array}\right) = \left(\begin{array}{ccc} 0 & 3 & 4\\ 0 & 9 & 12 \end{array}\right),$$ which tells me that $$U\circ T\left(\begin{array}{c}x\\y\\z\end{array}\right) = \left(\begin{array}{c} 3y + 4z\\ 9y+12z\end{array}\right).$$

Other matrix products. Are there other ways to define the product of two matrices? Sure. There's the Hadamard product, which is the "obvious" thing to try: you can multiply two matrices of the same size (and only of the same size), and you do it entry by entry, just the same way that you add two matrices. This has some nice properties, but it has nothing to do with linear transformations. There's the Kronecker product, which takes an $m\times n$ matrix times a $p\times q$ matrix and gives an $mp\times nq$ matrix. This one is associated to the tensor product of linear transformations. They are defined differently because they are meant to model other operations that one does with matrices or vectors.

-
Wow. I would have liked to give +2 rep for this, but that's not possible... –  Gottfried Helms Mar 1 '11 at 21:02
an amazing answer. this is better than some textbooks or internet resources –  Vass Mar 2 '11 at 12:53
is a linear combination also a linear transform? –  Vass Mar 2 '11 at 14:57
@Vass: No. A linear transformation is a function from a vector space to a vector space that is additive and homogeneous. A linear combination of vectors is the result of adding up scalar multiples of those vectors; it's not a function. –  Arturo Magidin Mar 2 '11 at 16:52
@Vass, as you clearly seem to be happy with this answer, you should "accept" it as best answer by clicking the tick/check mark on the left of it. –  Rahul Apr 8 '11 at 17:13

I think part of the problem people have with getting used to linear transformations vs. matrices is that they have probably never seen an example of a linear transformation defined without reference to a matrix or a basis. So here is such an example. Let $V$ be the vector space of real polynomials of degree at most $3$, and let $f : V \to V$ be the derivative.

$V$ does not come equipped with a natural choice of basis. You might argue that $\{ 1, x, x^2, x^3 \}$ is natural, but it's only convenient: there's no reason to privilege this basis over $\{ 1, (x+c), (x+c)^2, (x+c)^3 \}$ for any $c \in \mathbb{R}$ (and, depending on what my definitions are, it is literally impossible to do so). More generally, $\{ a_0(x), a_1(x), a_2(x), a_3(x) \}$ is a basis for any collection of polynomials $a_i$ of degree $i$.

$V$ also does not come equipped with a natural choice of dot product, so there's no way to include those in the discussion without making an arbitrary choice. It really is just a vector space equipped with a linear transformation.

Since we want to talk about composition, let's write down a second linear transformation. $g : V \to V$ will send a polynomial $p(x)$ to the polynomial $p(x + 1)$. Note that, once again, I do not need to refer to a basis to define $g$.

Then the abstract composition $gf : V \to V$ is well-defined; it sends a polynomial $p(x)$ to the polynomial $p'(x + 1)$. I don't need to refer to a basis or multiply any matrices to see this; all I am doing is composing two functions.

Now let's do everything in a particular basis to see that we get the same answer using the correct and natural definition of matrix multiplication. We'll use the basis $\{ 1, x, x^2, x^3 \}$. In this basis $f$ has matrix

$$\left[ \begin{array}{cccc} 0 & 1 & 0 & 0 \\\ 0 & 0 & 2 & 0 \\\ 0 & 0 & 0 & 3 \\\ 0 & 0 & 0 & 0 \end{array} \right]$$

and $g$ has matrix

$$\left[ \begin{array}{cccc} 1 & 1 & 1 & 1 \\\ 0 & 1 & 2 & 3 \\\ 0 & 0 & 1 & 3 \\\ 0 & 0 & 0 & 1 \end{array} \right].$$

Now I encourage you to go through all the generalities in Arturo's post in this example to verify that $gf$ has the matrix it is supposed to have.

-