Matrix multiplication: interpreting and understanding the process

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 transformations that aren't like that. For example, the linear transformation $T$ from $\mathbb{R}^3$ to $\mathbb{R}^2$ defined by $$T\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.

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.