From Dyck Paths to Random Matrices

The Trace-Loop Theorem

5 Matrices as Graphs

  • Interpretation: A symmetric $n \times n$ matrix $A$ can be viewed as the adjacency matrix of a weighted graph with $N$ vertices.
  • The Theorem: The trace of the $k$-th power of the matrix, $\text{Tr}(A^k)$, is exactly equal to the sum of weights of all closed loops of length $k$ in the graph.

VISUALIZER Graph Walk & Trace

Visualize how matrix multiplication counts paths.

3
3
Matrix $A$ (Symmetric)

Click cells to flip signs ($\pm 1$)

+
Positive Edge
-
Negative Edge
Current Term (Path Weight)
Start
Accumulated Sum (Trace)
0
Loop 0 / 0

Exhaustive Analysis

Explore all $2^{n(n+1)/2}$ possible symmetric matrices to verify the Trace Theorem.

INSIGHT

Why Catalan Numbers?

We observed that the average scaled trace for even powers $k=2m$ converges to the Catalan number $C_m$. Why does this happen?

1. Dominant Terms: As $n \to \infty$, the only paths that survive the averaging process are those where every edge is traversed exactly twice (once in each direction). Any path with a "single" edge traversal cancels out due to the random $\pm 1$ signs.

2. Tree Structure: These valid paths effectively trace out a "tree" on the graph nodes. A walk on a tree that returns to the start corresponds exactly to a Dyck Path!

$$ \lim_{n \to \infty} \frac{1}{n^{k/2+1}} \mathbb{E}[\text{Tr}(A^k)] = \begin{cases} C_{k/2} & \text{if } k \text{ is even} \\ 0 & \text{if } k \text{ is odd} \end{cases} $$

This result links the combinatorics of Dyck paths directly to the moments of the Wigner Semicircle distribution.

6 Connection to Dyck Paths

  • Trace & Moments: We study symmetric matrices $A$ with random $\pm 1$ entries. The expected trace $\mathbb{E}[\text{Tr}(A^k)]$ relates to closed loops on a graph.
  • The Link: As matrix size $n \to \infty$, the contribution of "crossing" paths vanishes. The surviving dominant terms map 1-to-1 with Dyck paths!

Tree-Loop Bijection Explorer

See how a closed Dyck path maps to a closed walk on a Tree.

Graph View (Nodes & Walk)
Tree Structure View
6
Corresponding Dyck Path