Encoding lattice paths as walks on the path graph

Blake Shirman, York University

It is a fundamental result of algebraic graph theory that the uv-entry of the mth power of the adjacency matrix of a graph is equal to the number of m-step walks from vertex u to vertex v. One could certainly conceive of a bounded, oriented portion of the (gridded) integer lattice as a directed graph and compute select entries of powers of its adjacency matrix to count the number of lattice paths over such a region. The orientation would be necessary to ensure that these walks are indeed paths (no repeated vertices) in the graph theoretic sense. For instance, all {N, E}-lattice paths of certain length could be drawn as walks on some oriented rectangular region of the integer lattice, with each vertical arc (directed edge) pointing up ‘north’ and each horizontal arc pointing right ‘east.’ However, computing powers of the adjacency matrix is cumbersome for such a large graph, since an n by n lattice grid would have an (n+1)2 by (n+1)2 adjacency matrix. Luckily, walks on such a grid can be encoded as walks on the path graph with 2n + 1 vertices. Such an undirected graph has a diagonalizable adjacency matrix with a known spectral decomposition. Of course, {N, E}-lattice paths are easily counted by a combinatorial argument, but we may equate the resulting binomial coefficient to a trigonometric polynomial (sourced from the spectral decomposition of the path graph). We can apply the same process to Dyck paths, which are famously enumerated by the Catalan numbers (a central binomial coefficient). Equating the two results gives us a family of identities between the real and imaginary parts of various roots of unity. The utility of our method becomes apparent with height-restricted Dyck paths, for which combinatorial arguments become more cumbersome. The path graph encoding shines, giving us as close to a ‘closed formula’ as the problem might allow.