Thinking in matrices is useful because it turns graph problems into algebraic ones, where composition of paths becomes multiplication and “either/or” reachability becomes boolean matrix operations.

On dense graphs especially, that viewpoint lets you use highly optimized matrix kernels and even asymptotically faster matrix-multiplication algorithms in some problems.

For dense graphs, this is often especially attractive because adjacency matrices already take \(O(n^2)\)space, and matrix algorithms can exploit cache locality, bitsets, or subcubic algebraic methods.

Example Problems

Transitive closure / reachability matrix

You want \(M[u][v]=1\) iff u can reach v. This is the boolean transitive closure of the graph.

A standard solution is Warshall/Floyd-Warshall style dynamic programming in \(O(n^3)\), while more advanced approaches use boolean matrix multiplication or fast algebraic matrix multiplication to improve asymptotic performance in dense settings.

Counting paths of fixed length k

If A is the adjacency matrix, then \((A^k)[u][v]\) gives the number of walks of length exactly kk from uu to vv under ordinary integer multiplication and addition.

The solution is to compute \(A^k\) by fast exponentiation in \(O(\log k)\) matrix multiplications (see Fast Exponentiation), or use repeated squaring with a fast matrix-multiply subroutine.

All-pairs shortest paths

For weighted graphs, the problem can be expressed with the min-plus semiring instead of ordinary arithmetic. Matrix products are then replaced by “distance multiplication,” where multiplication becomes addition of edge weights and addition becomes taking minima.

This leads to APSP algorithms based on repeated min-plus products, and in some dense-graph regimes, fast matrix multiplication gives subcubic methods.

Bottleneck / maximum-capacity paths

For each pair u,vu,v, you may want the path that maximizes the minimum edge capacity along the route. This is the all-pairs bottleneck paths problem, which can be formulated using (max⁡,min⁡)(max,min)-style matrix products.

Then the graph problem becomes computing a transitive closure under that semiring, and fast matrix methods apply to the corresponding matrix product.

Triangle Detection

Given an undirected graph 𝐺 in the form of an adjacency matrix, the goal is to count the number of triangles in the graph.