Matrix Multiplication

## The definition Matrix multiplication is defined entry by entry, and every shape rule follows from that definition rather than from convention. Let `A` have `m` rows and `n` columns, and let `B` have `n` rows and `p` columns. The product `C = AB` has `m` rows and `p` columns, and its entries are ``` C[i,j] = A[i,1]*B[1,j] + A[i,2]*B[2,j] + ... + A[i,n]*B[n,j] ``` which is the sum over `k` from 1 to `n` of `A[i,k] * B[k,j]`. In words: **entry (i,j) of the product is the dot product of row i of the left matrix with column j of the right matrix.** That sentence contains the whole shape rule. A dot product is only defined between two vectors of the same length. Row `i` of `A` has length `n` (one number per column of `A`); column `j` of `B` has length `n` (one number per row of `B`). So the number of columns of `A` must equal the number of rows of `B`. Nothing else has to match. ## Reading shapes off the page A reliable habit is to write the shapes next to each other with the operands in order: ``` (m x n)(n x p) -> m x p ``` The two inner numbers must be equal; they are consumed by the summation and vanish. The two outer numbers survive and become the shape of the answer. Some worked cases: - `(4 x 7)(7 x 3)` is fine and gives `4 x 3`. - `(3 x 2)(3 x 2)` is **not** defined: inner numbers 2 and 3 disagree. - `(1 x 4)(4 x 1)` gives `1 x 1` — a single number, the dot product of the two vectors. - `(4 x 1)(1 x 4)` gives `4 x 4` — an outer product, a whole matrix from the same two vectors. The last two lines are worth staring at. The same pair of length-4 vectors produces either a scalar or a 4-by-4 matrix depending purely on the order and orientation, which is the first concrete sign that order matters in matrix multiplication. ## Why identical shapes are not the rule A very common beginner error is to assume `A` and `B` must have the same shape, by analogy with addition. Matrix addition **is** entrywise: `A + B` requires identical shapes and adds corresponding cells. Matrix multiplication is not entrywise at all — it is a structured collection of dot products, and it exists to represent the *composition of linear maps*. If `B` maps vectors from a `p`-dimensional space into an `n`-dimensional space and `A` maps that `n`-dimensional space into an `m`-dimensional one, then `AB` maps the `p`-dimensional space straight into the `m`-dimensional one. The shape rule is the algebraic shadow of "the output space of the second map must be the input space of the first". There *is* an entrywise product of two equally shaped matrices (often called the elementwise or Hadamard product), but it is a different operation with different rules, and writing `AB` never means it. ## Counting the work Each of the `m * p` entries of the result costs `n` multiplications and `n - 1` additions, so the standard algorithm performs about `m * n * p` multiply-add operations. That count is worth remembering: it is the basis for reasoning about which order to evaluate a longer chain of products, and it explains why the shared inner dimension, not the visible output size, usually drives the cost. ## Special shapes - **Square matrices** (`n x n`) can always be multiplied by each other, in either order, and both products are `n x n`. - **Matrix times column vector**: `(m x n)(n x 1)` gives an `m x 1` column — the most common case in practice. - **Row vector times matrix**: `(1 x m)(m x n)` gives a `1 x n` row. - Vectors are just matrices with a 1 in one slot, so they obey exactly the same rule; most "dimension mismatch" confusion comes from forgetting whether a vector is a row or a column. ## Checking your own work Before computing anything by hand, write the shape chain. If you can carry `(m x n)(n x p)(p x q)` through and the inner numbers pair up all the way along, the expression is well formed and the answer is `m x q`. If any adjacent pair disagrees, the expression is meaningless and no amount of arithmetic will rescue it — one of the operands needs to be transposed or the order needs to change.