Matrix Multiplication and Factorization Encode Composition

What This Concept Is

Matrix multiplication is not a decorative rule for arranging indices. It is the algebra of composition. If $B$ acts first and $A$ acts second on a vector $v$, then the combined action is $(AB)v = A(Bv)$. That single fact explains why order matters, why inner dimensions must match, why matrices naturally represent chained transformations, and why elimination packages up into a factorization $A = LU$ (or $PA = LU$ when row exchanges are needed).

Multiplication can be read four different ways, and fluency requires all four. Row-times-column: entry $(AB){ij}$ is the dot product of row $i$ of $A$ with column $j$ of $B$. Column picture: column $j$ of $AB$ is $A$ times column $j$ of $B$, so $AB$ is "apply $A$ to each column of $B$." Row picture: row $i$ of $AB$ is row $i$ of $A$ times $B$. Outer-product sum: $AB = \sum_k A{:k} B_{k:}$, a sum of rank-one matrices built from column $k$ of $A$ and row $k$ of $B$ -- this is the viewpoint SVD and low-rank approximation require.

Factorization matters because it turns one expensive operation into reusable structure. $LU$ comes from elimination without row exchanges; $PA = LU$ from elimination with partial pivoting; $QR$ comes from orthogonalizing the columns (covered in Cluster 3); $A = S\Lambda S^{-1}$ from eigenvectors; $A = U\Sigma V^T$ from SVD. Every factorization takes the form "write $A$ as a product of structured factors whose action on vectors is easy to execute."

For a nonsingular square matrix, row-pivoted LU supports repeated solves. Cholesky exploits symmetric positive definiteness. QR handles full-column-rank least squares without explicitly forming a Gram matrix. Rank-revealing QR or SVD supports rank-deficient problems. Leading dense arithmetic counts depend on matrix shape and the requested factors; sparse costs also depend on fill-in and ordering.

The column picture is also the fastest way to remember the legality rule. If $A$ is $m \times k$ and $B$ is $k \times n$, each column of $B$ lives in $\mathbb{R}^k$; $A$ eats vectors in $\mathbb{R}^k$ and emits vectors in $\mathbb{R}^m$; the output has $n$ columns like $B$ and $m$ rows like $A$. Inner dimensions match or the product is meaningless -- not a convention, a type constraint. Every shape mistake in a NumPy traceback is a violation of this composition constraint.

Why It Matters Here

You will use multiplication and factorization everywhere: composing linear transformations, expressing repeated action as $A^k$, building least-squares systems from $A^TA$, defining similarity transforms $S^{-1}AS$, and understanding $QR$ and SVD as organized products of orthogonal and triangular or diagonal pieces. If multiplication remains a memorized row-by-column ritual, the rest of the module stays shallow.

Factorization is also where asymptotic complexity meets software engineering. Once you see that $LU$ can be amortized across many right-hand sides, you understand why every linear-algebra library separates factor and solve phases; why sparse solvers (SuiteSparse, MUMPS) publish their symbolic and numeric steps separately; and why cache-aware blocked factorizations exist.

In the conventional dense arithmetic model, LU factorization costs about $2n^3/3$ operations and each additional solve costs order $n^2$. Forming an explicit inverse adds work and storage. Report dimensions, precision, library and hardware when comparing measured runtimes; symbolic operation counts are not wall-clock guarantees.

Concrete Examples

Example 1 -- order matters. Let

$$B = \begin{pmatrix} 1 & 2 \ 0 & 1 \end{pmatrix}, \quad A = \begin{pmatrix} 2 & 0 \ 0 & 3 \end{pmatrix}.$$

$B$ is a horizontal shear; $A$ is an anisotropic scaling. Then

$$AB = \begin{pmatrix} 2 & 4 \ 0 & 3 \end{pmatrix}, \quad BA = \begin{pmatrix} 2 & 6 \ 0 & 3 \end{pmatrix}.$$

They are different because $AB$ means "shear, then scale," whereas $BA$ means "scale, then shear." The unit square maps to different parallelograms depending on the order. That is non-commutativity made visible.

Each view answers a different question cleanly. Need to know if $b$ is reachable as $ABx$? Use the column view. Need to know which inputs are silenced? Use the row view. For a low-rank approximation, an arbitrary outer-product expansion does not inherit SVD optimality; discarded terms can interact or cancel.

Example 2 -- LU captures elimination. For

$$A = \begin{pmatrix} 2 & 1 & 1 \ 4 & 3 & 3 \ 8 & 7 & 9 \end{pmatrix},$$

run elimination and store the multipliers $\ell_{21} = 2$, $\ell_{31} = 4$, $\ell_{32} = 3$ in $L$:

$$L = \begin{pmatrix} 1 & 0 & 0 \ 2 & 1 & 0 \ 4 & 3 & 1 \end{pmatrix}, \quad U = \begin{pmatrix} 2 & 1 & 1 \ 0 & 1 & 1 \ 0 & 0 & 2 \end{pmatrix}.$$

Verify $LU = A$ by block multiplication. To solve $Ax = b$ for any right-hand side, run forward substitution $Ly = b$ ($O(n^2)$), then back substitution $Ux = y$ ($O(n^2)$). The one-time $O(n^3)$ factor is amortized across all right-hand sides.

Example 3 -- outer-product view. The product

$$\begin{pmatrix} 1 \ 2 \ 3 \end{pmatrix}\begin{pmatrix} 4 & 5 \end{pmatrix} = \begin{pmatrix} 4 & 5 \ 8 & 10 \ 12 & 15 \end{pmatrix}$$

is a rank-1 matrix; every column is a scalar multiple of $(1,2,3)^T$. Every matrix can be written as a sum of rank-1 outer products (this is the column picture with the sum reordered), which is exactly the statement that SVD approximates $A$ by truncating such a sum.

Example 4 -- block multiplication. If $A$ and $B$ are partitioned into compatible blocks, the product obeys the same row-by-column rule at the block level:

$$\begin{pmatrix} A_{11} & A_{12} \ A_{21} & A_{22} \end{pmatrix}\begin{pmatrix} B_{11} & B_{12} \ B_{21} & B_{22} \end{pmatrix} = \begin{pmatrix} A_{11}B_{11} + A_{12}B_{21} & A_{11}B_{12} + A_{12}B_{22} \ A_{21}B_{11} + A_{22}B_{21} & A_{21}B_{12} + A_{22}B_{22} \end{pmatrix}.$$

This is not a convenience -- it is the structural reason cache-blocked GEMM works. Tile the matrices into blocks that fit in L1/L2 cache, multiply blocks via the formula above, to improve data reuse; actual throughput depends on hardware and implementation. Strassen's $O(n^{\log_2 7})$ algorithm uses algebraic identities for the 2×2 block product that trades more additions for fewer multiplications.

Common Confusion / Misconceptions

"$AB$ is close to $BA$ in practice." False. A shared eigenbasis is sufficient for commutation. The converse requires extra hypotheses: the identity commutes with a defective Jordan block even though that block has no eigenbasis. In general $AB \ne BA$, and the commutator $[A,B] = AB - BA$ is itself an important object (in physics, Lie theory, and parallel-algorithm analysis).

"Matrix multiplication is associative and distributive because the definition is." Associativity $(AB)C = A(BC)$ is a theorem, not a definition, and it is the reason the function-composition picture is consistent. Distributivity $A(B+C) = AB + AC$ follows from the same row-by-column structure.

"One factorization solves every matrix problem." LU is a standard general square-system method, but Cholesky, QR and SVD have different assumptions and purposes. Select the method from the actual structure and requested evidence.

"Factorization is only about speed." Factorization is also about structure recovery: $LU$ exposes pivots and rank, $QR$ exposes orthogonal bases of the column space, Cholesky certifies positive definiteness, and SVD exposes singular values. Each factorization answers a different structural question in addition to accelerating solves.

"The row-by-column rule is the only way to think about $AB$." It is the computational rule; it is not the insight. When you need to reason about what $AB$ does, reach for one of the other three views. Column view for "what lives in the range." Row view for "what coordinates survive." Outer-product view for "how much rank can accumulate." Experienced practitioners switch views constantly mid-derivation without noticing.

How To Use It

When multiplying matrices, ask:

1. What acts first, and what acts second? Write the composition in the correct order.
2. Do the inner dimensions match? If $A$ is $m\times k$ and $B$ is $k\times n$, then $AB$ is $m\times n$.
3. Which of the four views (row-by-column, column action, row action, outer-product sum) best answers my question?
4. Is this composition legal in the spaces involved?
5. Is there a factorization that makes repeated solves or powers cheaper?

When you see a long chain of operations, stop expanding blindly and look for structure: triangular factors, diagonal factors, orthogonal factors. Those factorizations are where computational advantage comes from.

For dense n-by-n factors and a single vector, applying factors successively avoids forming full products. For rectangular, sparse or structured factors, compare actual dimensions, nonzero patterns, reuse and rounding before choosing a multiplication order. Matrix-chain optimization makes these costs explicit.

For code, use the factorization matching the stated shape, rank and objective. Reuse factors for repeated right-hand sides. SVD is useful for low-rank approximation and pseudoinverses as well as rank questions; it is not restricted to a single use case.

A practical diagnostic. Any expression of the form $M = F_1 F_2 \cdots F_k$ where the $F_i$ are structured (diagonal, triangular, orthogonal) is an opportunity. You can often solve $Mx = b$ by walking the factors in sequence, each costing $O(n^2)$ or better, instead of materializing $M$ and paying $O(n^3)$. The discipline is "see the factorization, then solve through it" -- not "multiply out, then solve."

Transfer to the calibration project

Use this concept to justify a result or reject an assumption in the calibration project. Name the matrix shape, objective, scalar field and available evidence before interpreting the result.

Check Yourself

1. Why does "$AB$ means do $B$ first" follow from the definition of matrix-vector multiplication?
2. What practical advantage does $A = LU$ give over solving from scratch each time?
3. Why is matrix multiplication dimension-sensitive, and what goes wrong if you multiply a $3\times 2$ by a $3\times 2$?
4. Give a $2\times 2$ example where $AB = BA$ and explain structurally why.
5. When is $LU$ not sufficient, and what alternative factorization do you use?
6. Why does the outer-product view matter for compression?
7. How does block multiplication let a $1000 \times 1000$ GEMM run near hardware peak?
8. Why does the transpose identity $(AB)^T = B^T A^T$ follow from "$AB$ means do $B$ first"?

Mini Drill or Application

1. Compute $AB$ and $BA$ for $A = \begin{pmatrix} 1 & 1 \ 0 & 1 \end{pmatrix}$ and $B = \begin{pmatrix} 0 & 1 \ 1 & 0 \end{pmatrix}$. Describe in words what each product does to a vector.
2. Solve one $3\times 3$ system by elimination and extract the elimination multipliers you would store in $L$.
3. In NumPy, compute from scipy.linalg import lu_factor, lu_solve; lu, piv = lu_factor(A); x = lu_solve((lu, piv), b). Time this against np.linalg.solve(A, b) inside a loop of 1000 calls with varying $b$; explain the speedup.
4. Given two rank-1 matrices $u_1 v_1^T$ and $u_2 v_2^T$, show by the outer-product view that their sum has rank at most 2. Find a specific choice where the rank is exactly 1.
5. Compute $A^2$, $A^3$, $A^4$ for $A = \begin{pmatrix} 1 & 1 \ 0 & 1 \end{pmatrix}$ and spot the pattern. How does this connect to Jordan blocks (preview of Cluster 4)?
6. Using block multiplication, verify that the $2\times 2$ block form of $I$ times $A = \begin{pmatrix} A_{11} & A_{12} \ A_{21} & A_{22} \end{pmatrix}$ reproduces $A$ block-by-block. Explain why this legality underpins cache-tiled GEMM.
7. Compute both $AB$ and $BA$ for $A, B \in \mathbb{R}^{3\times 3}$ of your choice. Report the commutator $[A, B] = AB - BA$ and verify $\text{tr}([A, B]) = 0$ always. What does the vanishing trace say about the composition?

Read This Only If Stuck

Use the bounded reading guide and the Strang book index. The book link opens an index; find the named topic in your edition, read a small section and reconstruct one argument with the book closed.

A product is a typed composition

Let B map R^p to R^n and A map R^n to R^m. Draw the sequence R^p → R^n → R^m before multiplying; AB has shape m-by-p. The intermediate basis must also agree. Shape compatibility alone does not repair mismatched physical units or coordinate conventions.

To check a proposed factorization, reconstruct A from the factors. That catches ordering and permutation mistakes, but numerical work also needs a scaled norm of A−reconstruction. A low-rank approximation requires an error criterion; an arbitrary sum of outer products is not an optimal ordering. Transfer: use the QR reconstruction and SVD tail checks in Labs 2 and 4.

After an independent attempt, use practice feedback and model contracts to check your reasoning.