Matroid Pathwidth Equals Code Trellis Width¶

Claim/Theorem¶

Let \(C\) be a linear code over a finite field \(\mathbf F\), and let \(M(C)\) be the vector matroid of any generator matrix of \(C\). Then the trellis-width of \(C\) is exactly the pathwidth of the associated matroid \(M(C)\).

Equivalently, if one defines

\[ \operatorname{pw}(M(C)) \;:=\; \min_{\pi} \max_i \lambda_{M(C)}(P_i^\pi), \]

where \(\pi\) ranges over coordinate orderings and \(P_i^\pi\) is the prefix set of the first \(i\) coordinates, then

\[ \operatorname{tw}_{\mathrm{trellis}}(C)=\operatorname{pw}(M(C)). \]

Because the matroid connectivity function satisfies

\[ \lambda_{M(C)}(J)=\dim(C|_J)+\dim(C|_{J^c})-\dim(C), \]

this is exactly the same ordering-profile quantity already used in [[balanced-linear-cut-rank-from-trellis-width.md]] and [[trellis-width-to-syndrome-depth-via-hardware-ordering.md]].

The paper also notes two immediate structural consequences:

for fixed field \(\mathbf F_q\) and fixed \(w\), the class of \(\mathbf F_q\)-representable matroids of pathwidth at most \(w\) is minor-closed;
pathwidth at most \(w\) implies branchwidth at most \(w\).

So the sweep-ordering route on the current graph is precisely a matroid-pathwidth route in disguise.

Dependencies¶

[[balanced-linear-cut-rank-from-trellis-width.md]]
[[trellis-width-to-syndrome-depth-via-hardware-ordering.md]]

Conflicts/Gaps¶

Pathwidth is the right invariant only for sweep-like or ordering-based hardware bottlenecks. It does not replace the broader separator-based route.
The theorem identifies the correct intrinsic parameter, but it still does not provide a strong lower bound on pathwidth for the specific classical constituent or parity-check matroids relevant to Quantum Tanner; [[wolf-parameter-bound-insufficient-for-css-qldpc-constituents.md]] explains why the standard parameter route remains too weak there.
Therefore this node sharpens the language of the ordering route, but it does not remove the main frontier gap.

Sources¶

10.48550/arXiv.0705.1384