← Back to Linear Algebra

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

Block matrix

Matrix partitioned into submatrices

Blockwise multiplication.

Check your understanding

Why do 2D graphics systems use 3 x 3 matrices for points in the plane?

← Previous lesson Next lesson →