Partitioned matrices and applications
Large matrices are often handled in blocks, and matrix arithmetic models graphics, networks, and change over time. These applications show why matrix algebra matters.
Block matrices
A matrix can be partitioned into blocks, smaller matrices arranged in a grid. If the partitions are compatible, block matrices multiply using the same row-column rule with blocks in place of numbers: \(\begin{bmatrix} A & B \\ C & D \end{bmatrix}\begin{bmatrix} E \\ F \end{bmatrix} = \begin{bmatrix} AE + BF \\ CE + DF \end{bmatrix}\), keeping the order of each product since blocks do not commute.
Uses of blocks
Block structure reflects real structure: separate subsystems connected by a few couplings, or images split into tiles. High-performance libraries multiply large matrices block by block so that each block fits in fast cache memory, which is a key reason optimised matrix multiplication runs many times faster than naive loops.
Outer products and rank-one matrices
The product of a column vector and a row vector, \(\mathbf{u}\mathbf{v}^T\), is an outer product: a matrix in which every column is a multiple of \(\mathbf{u}\), so its rank is 1. Any matrix product AB equals the sum of outer products of A's columns with B's rows, a view that underlies low-rank approximations used in compression and recommendation systems.
Computer graphics
Rotating points in the plane by angle \(\theta\) multiplies them by \(\begin{bmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{bmatrix}\); scaling and shearing are also matrices. To include translations, graphics uses homogeneous coordinates, adding an extra coordinate so that 3 x 3 matrices transform 2D points and 4 x 4 matrices transform 3D points. Combining transformations is matrix multiplication.
Graphs and adjacency matrices
A network of n nodes can be stored as an n x n adjacency matrix with 1 where an edge connects nodes i and j. Remarkably, entry (i, j) of A^k counts the walks of length k from node i to node j. Google's original PageRank algorithm, described in 1998, ranked web pages using a matrix built from the web's link structure.
Markov chains
A Markov chain models a system moving between states with fixed probabilities, such as weather or customer behaviour. A stochastic matrix P has non-negative entries with columns summing to 1. If \(\mathbf{x}_k\) holds the state probabilities at step k, then \(\mathbf{x}_{k+1} = P\mathbf{x}_k\), so \(\mathbf{x}_k = P^k\mathbf{x}_0\). Many chains approach a steady state \(\mathbf{q}\) with \(P\mathbf{q} = \mathbf{q}\).
Computational cost
Multiplying two n x n matrices by the definition takes n^3 multiplications. Volker Strassen showed in 1969 that it can be done with fewer, about n^2.81, and theoretical algorithms have since lowered the exponent below 2.38, though practical libraries mostly use highly optimised versions of the standard method on GPUs and CPUs.
Worked example
A city's residents move each year: 90% of city dwellers stay and 10% move to the suburbs; 80% of suburban dwellers stay and 20% move to the city. With \(P = \begin{bmatrix} 0.9 & 0.2 \\ 0.1 & 0.8 \end{bmatrix}\) and starting split \((0.6, 0.4)\), next year is \((0.54 + 0.08, 0.06 + 0.32) = (0.62, 0.38)\). The steady state solves \(0.1q_1 = 0.2q_2\) with \(q_1 + q_2 = 1\): \(q = (\frac{2}{3}, \frac{1}{3})\).
Key takeaways
Partitioned matrices multiply block by block when compatible, keeping product order; blocking also speeds computation through cache use. Outer products u v^T have rank 1, and AB is a sum of column-row outer products, underpinning low-rank approximation. Graphics uses rotation, scaling, and shear matrices, with homogeneous coordinates for translations. Adjacency matrices store networks, and powers count walks; PageRank (1998) used link-matrix ideas. Markov chains evolve by x_{k+1} = P x_k towards steady states with Pq = q. Standard multiplication costs n^3; Strassen (1969) reduced the exponent to about 2.81.
Flashcard
Matrix partitioned into submatrices
Check your understanding
Why do 2D graphics systems use 3 x 3 matrices for points in the plane?
