9.2 Circuit model and metric comparison
On this page · Permalink · Source line 1153
9.2.1 Transvections and row conventions
On this page · Permalink · Source line 1155
Fix a nonzero commutative ring \(R\) with identity and an integer \(n\ge2\). Rows and columns are indexed by
For \(s\ne t\) and \(a\in R\setminus\{0\}\), set
Left multiplication by \(\tau_{t,s}(a)\) performs
We call \(s\) the source and \(t\) the target. A circuit word
produces
Let
and
Both sets are symmetric because
Let
When \(R={\mathbb F}\) is a field and \(n\ge2\), elementary elimination gives
The ambient metric below is therefore the transvection word metric in \({\operatorname{SL}}_n({\mathbb F})\), viewed inside \({\operatorname{GL}}_n({\mathbb F})\). When \({\mathbb F}={\mathbb F}_2\), one has \({\operatorname{SL}}_n({\mathbb F}_2)={\operatorname{GL}}_n({\mathbb F}_2)\), every generator is an involution, and it is exactly a CNOT gate under the usual row-action convention.
Lemma 9.12
The set \(S_n^\downarrow(R)\) generates \({\operatorname{U}}_n(R)\). Every prefix of a lower-directed circuit belongs to \({\operatorname{U}}_n(R)\).
Proof
A lower-directed transvection is lower unitriangular, and products of lower-unitriangular matrices remain lower unitriangular. Conversely, ordinary elimination of the strict lower entries, processed in a compatible order, expresses every element of \({\operatorname{U}}_n(R)\) as a product of lower-directed transvections.
Definition 9.13: Intrinsic and ambient lengths
For \(A\in{\operatorname{U}}_n(R)\), define
The catalytic defect is
The inequality follows because \(S_n^\downarrow(R)\subseteq S_n^*(R)\). The central question is whether the inclusion can be strict on a lower-unitriangular target.
9.2.2 Frame and flag interpretation
On this page · Permalink · Source line 1225
For the geometric interpretation in this subsection, assume \(R={\mathbb F}\) is a field. An invertible matrix is an ordered basis
of \({\mathbb F}^n\). A transvection replaces one basis vector by its sum with a nonzero multiple of another. Let
A matrix lies in \({\operatorname{U}}_n({\mathbb F})\) exactly when
for every \(i\). Thus lower circuits move among frames compatible with the standard complete flag
An upper-directed gate leaves this fiber of the flag map. A strict defect means that the flag-compatible frame subgraph is not geodesically convex in the full transvection graph.
9.2.3 Schreier holonomy
On this page · Permalink · Source line 1245
Set
Consider the right Schreier graph on the left cosets \(H\backslash G\): a generator \(s\in S_n^*(R)\) gives an edge
A word representing \(h\in H\) traces a based loop at the coset \(H\). Its label product is the holonomy \(h\).
Proposition 9.14: Holonomy-compression interpretation
For \(h\in H\), the ambient length \({\ell_{*}}(h)\) is the least length of a labeled based loop in \(H\backslash G\) with holonomy \(h\). The restricted length \({\ell_{\downarrow}}(h)\) is the least length among such words whose every prefix remains in \(H\). Consequently,
Proof
A word \(w=s_1\cdots s_k\) ends at the coset \(Hw\). It is a based loop exactly when \(w\in H\), and its label product is then the represented element of \(H\). Minimizing over all transvection words representing \(h\) gives \({\ell_{*}}(h)\). Requiring every generator to be lower directed keeps every prefix in \(H\) and gives \({\ell_{\downarrow}}(h)\).
A catalytic shortcut is therefore a nonconstant quotient excursion whose accumulated holonomy is more expensive to produce inside the base fiber.
9.2.4 Two elementary counting lemmas
On this page · Permalink · Source line 1276
The proofs of the universal atom use only target counts and pivot support.
Lemma 9.15: Target count
Suppose a circuit starts at the identity and finishes at \(A\).
If row \(i\) of \(A\) differs from \(e_i\), then row \(i\) is targeted at least once.
If row \(i\) of \(A\) equals \(e_i\) and is targeted, then it is targeted at least twice.
Proof
A row changes only when it is targeted. Every row of an invertible matrix over \(R\) is unimodular. If \(aR_s=0\) for such a row, then multiplying a unimodular relation for \(R_s\) by \(a\) gives \(a=0\). Hence a gate with nonzero coefficient changes its target by a nonzero vector, so one targeting cannot leave that row equal to its initial value.
Lemma 9.16: One-target source condition
Let \(W\le R^n\). Suppose row \(t\) starts at \(e_t\), is targeted exactly once, and finishes at
where at least one coordinate of \(w\) is a unit of \(R\). At the moment of its unique targeting, the gate coefficient is a unit and the source row is a unit multiple of \(w\).
Proof
If the unique gate is \(R_t\leftarrow R_t+aR_s\), then \(aR_s=w\). Choose a coordinate \(j\) for which \(w_j\) is a unit. Since \(a(R_s)_j=w_j\), the factor \(a\) is a unit in the commutative ring \(R\). Hence \(R_s=a^{-1}w\).
The second lemma is especially restrictive when \(W\) is a low-dimensional source space and output rows carry unique pivot coordinates outside \(W\).