Finite tensor savings and exact Fourier circuits

Proof. We build a fixed word whose adjustable diagonal factors give a full-rank differential, then show that its actual values contain a nonempty Zariski open subset of \GL_q(\C). Every invertible target is a product of two values from this subset, so doubling the word gives the common pattern.

Let E_{ij} denote the matrix units. Let \mathfrak d\subset\Mat_q(\C) be the diagonal subspace and let \mathcal S be the semigroup of words in A and monomials, including identity. Inverses are not among the specified calls. First we prove

If A\mathfrak d A^{-1}\subset\mathfrak d, each rank-one idempotent A E_{ii}A^{-1} would be a diagonal rank-one idempotent, hence some E_{\pi(i)\pi(i)}. Orthogonality of these idempotents forces \pi to be a permutation. The identity A E_{ii}=E_{\pi(i)\pi(i)}A then says that column i of A is supported in row \pi(i); invertibility would make A monomial. Consequently some X\in A\mathfrak d A^{-1} has X_{ij}\ne0 for i\ne j.

Write \mathcal V for the span on the left of Equation (2.3). For every invertible diagonal D=\diag(d_1,\ldots,d_q), the matrix DXD^{-1} belongs to \mathcal V. If a linear functional \ell vanishes on \mathcal V, then

The Laurent monomials 1 and d_a/d_c for a\ne c are distinct and linearly independent. Thus X_{ij}\ell(E_{ij})=0, and so \ell(E_{ij})=0. Finite-dimensional linear duality gives E_{ij}\in\mathcal V. Conjugation by any permutation preserves \mathcal V, because left multiplication of a word by that permutation is again a word. Hence \mathcal V contains every off-diagonal matrix unit. It also contains \mathfrak d, using s=I_q. This proves Equation (2.3).

We next arrange the spanning directions along one word. Start with the prefix h_0=I_q and its diagonal directions. If the directions collected so far span a proper subspace and the current prefix is h, then

Choose a word s whose directions enlarge the collected span, and append it to the right of h in written product order. Each choice increases the dimension, so finitely many choices suffice. Denote the successive appended words by s_1,\ldots,s_r and their prefixes by h_i=s_1\cdots s_i. The spaces h_i\mathfrak d h_i^{-1}, including i=0, now span \Mat_q(\C).

Insert variable diagonal factors in the product

At D_0=\cdots=D_r=I_q, its value is h_r. Varying D_i in the diagonal direction E_{aa} gives the right-translated derivative

Thus the derivative has rank a=q^2. Choose a diagonal entries whose derivative columns are independent, and fix all other entries to 1. Listing matrix entries produces a polynomial map

whose Jacobian determinant is nonzero at (1,\ldots,1). Parameters in (\C^*)^a give admissible words. We show next that their image contains an actual nonempty Zariski open subset of \GL_q(\C).

Write x_1,\ldots,x_a for the selected parameters and f_1,\ldots,f_a for the output entries. The f_i are algebraically independent. Indeed, a nonzero polynomial relation P(f)=0 of least total degree would, upon differentiation and inversion of the Jacobian over \C(x_1,\ldots,x_a), imply (\partial P/\partial y_i)(f)=0 for every i. In characteristic zero at least one of these is a nonzero polynomial of smaller degree, a contradiction. Both fields in the inclusion

therefore have transcendence degree a. The latter is an algebraic extension generated by the finitely many x_i, so it is finite. Each of the finitely many elements x_i,x_i^{-1} satisfies a monic equation over the smaller field. Choose a nonzero polynomial g(y_1,\ldots,y_a) divisible by the denominators of all coefficients of these equations. With

all the displayed generators of B are integral over R. Reducing their powers by their monic equations shows directly that B is a finite R-module. Both are domains and R\hookrightarrow B is injective. This is the finite-type integral-extension criterion [19, Tag 02JJ, Lemma 10.36.5].

Fix any target y\in\C^a with g(y)\ne0, and let \mathfrak m=(f_1-y_1,\ldots,f_a-y_a)\subset R. Algebraic independence identifies R/\mathfrak m with \C. Localizing the inclusion above gives R_{\mathfrak m}\hookrightarrow B_{\mathfrak m} inside the field \C(x_1,\ldots,x_a), so B_{\mathfrak m} is a nonzero finite module over the local ring R_{\mathfrak m}. Its residue algebra

is nonzero. This is the lying-over step for the integral inclusion [19, Tag 00GQ, Lemma 10.36.17]. For completeness, if it were zero, a finite list of module generators b_1,\ldots,b_e would satisfy b_i=\sum_j c_{ij}b_j with all c_{ij} in the maximal ideal of R_{\mathfrak m}. The determinant of I-(c_{ij}) is a unit in this local ring. Multiplication by its adjugate forces every b_i to be zero, contradicting B_{\mathfrak m}\ne0.

The algebra in Equation (2.4) is finite dimensional over \C. A quotient by a maximal ideal is a finite field extension of \C, and hence is \C itself. The resulting homomorphism B\to\C sends x_i to some \xi_i\ne0, since x_i^{-1} is also in B. The polynomial identities defining the f_i descend to f_i(\xi)=y_i. These are actual admissible parameters of the fixed word. In particular its image contains

a nonempty open set, because g(Y)\det Y is a nonzero polynomial.

Finally fix H\in\GL_q(\C). There is a V for which both V\in\Omega and V^{-1}H\in\Omega. To see this without any limiting argument, clear powers of \det V from g(V^{-1}H). Its numerator is a nonzero polynomial: the substitution V\mapsto V^{-1}H is a bijection of \GL_q(\C), with inverse W\mapsto HW^{-1}, so this rational function is not identically zero. Avoid simultaneously the zeros of that numerator, g(V), and \det V. A finite product of nonzero polynomials over \C is nonzero and has a point where it does not vanish. This supplies the required V. Setting W=V^{-1}H gives H=VW, with both factors realized by the same fixed word pattern. Two copies of that pattern therefore realize every H.

The initial pattern contains at least one occurrence of A: otherwise its values have one fixed monomial support, a space of dimension q, contradicting the derivative rank q^2>q. Expanding the fixed words s_i and merging adjacent monomials in the doubled pattern gives Equation (2.2) with a fixed h>0. All inverses used in the argument occurred in matrix identities or parameter selection; every factor of the constructed words is a forward call to A or a monomial. For w>q, applying the same result to the nonmonomial matrix A\oplus I_{w-q} proves the wider-width assertion, because each call to this matrix is one embedded call to A.□

Proof. Let L_A(k) be the minimum scalar gate count for A^{\otimes k}, and put f(k)=L_A(k)/q^k. Here A^{\otimes0}=I_1 and f(0)=0. These minima exist: entrywise multiplication and addition give finite circuits, and a nonempty set of nonnegative integer gate counts has a minimum. Set

Tensor the winning word with itself over j groups, multiplying the corresponding slots together. The product of these slots is (A^{\otimes b})^{\otimes j}=A^{\otimes bj}.

A monomial slot remains monomial after taking this tensor power, and therefore costs at most Q^j scalar gates. Each call slot is permutation-conjugate to A\oplus I_{Q-q}. Its j-fold tensor power, after reordering coordinates, has the following exact direct-sum decomposition:

For a chosen subset of r active factors, the inactive factors supply (Q-q)^{j-r} independent scalar coordinate choices, explaining the multiplicity. The total width is \sum_r\binom jr q^r(Q-q)^{j-r}=Q^j. Computing the blocks separately with minimum circuits gives normalized cost at most

In particular, this distribution weights sectors by their coordinate dimensions; the sectors have different widths.

Replicate the resulting circuit over the coordinates of the remaining k-bj<b tensor axes. The normalized cost is unchanged by this replication. If a fixed circuit for A has \ell_A gates, applying A along each remaining axis costs \ell_Aq^{k-1} gates per axis. Since the number of monomial slots in the winning word is fixed, there is a constant C_0 independent of k such that

For j=0 the grouped part is identity and the same inequality follows from the bound on the fewer than b remaining axes. Every permutation used in deriving Equation (2.5) is only a reindexing; every diagonal scaling has already been charged.

Put \rho=q/(Qb). The strict saving gives g\rho<1, and hence we can choose 0<\alpha<1 sufficiently close to 1 that g\rho^\alpha<1. Choose also a number \gamma with g\rho^\alpha<\gamma<1. Since

there is k_0\geq1 such that this expression is at most \gamma for all k\geq k_0. Choose C at least C_0/(1-\gamma) and large enough that f(k)\leq C(k+1)^\alpha for k<k_0. For k\geq k_0, every value of K satisfies K\leq\lfloor k/b\rfloor<k. Strong induction, concavity of x\mapsto x^\alpha, and \mathbb E K=p\lfloor k/b\rfloor\leq\rho k therefore give

All circuits used in this induction compute exact matrices; the expectation is merely the finite weighted sum in Equation (2.6). Multiplying by q^k proves the scalar gate bound

□

Proof. Assign one distinct coordinate z_v to each gate v, ordered topologically. To simulate the gate, add its prescribed linear combination of predecessors into z_v. A scalar gate requires one shear, and an addition or subtraction requires at most two. An edge from the literal input zero is omitted. Predecessors are either original source coordinates or earlier gate coordinates; in particular none is the coordinate being updated. The forward sweep therefore has the form

where U is unit lower triangular in the chosen order. Write the designated output reads as Fz_{\rm current}+Dx; this includes outputs that are original inputs, and a zero output contributes no read. Each nonzero output is one designated read. Starting with zero gate coordinates computes the original DAG, so

Run the forward sweep, add its outputs into y, and undo every shear of that sweep in reverse order. The net effect on y is addition of

and every scratch coordinate returns to its initial value. Next run the same forward sweep with all edges from original source coordinates omitted. Omit the direct-source output term Dx as well. This sweep sends z to Uz. Subtract its outputs FUz from y and undo the sweep. This leaves exactly y+Mx and restores z once more. The target coordinates are never read by either sweep. These identities hold for independent formal variables x,y,z, hence remain valid after substituting correlated values for the initial scratch.

To obtain the layer bound, assign gates their longest-path depth levels. Within a level, all destinations are new gate coordinates and all predecessors belong to earlier levels or to the sources. The undirected multigraph of shear edges has maximum degree at most \Delta=\max\{2,\delta\}: a destination has at most two incoming edges and a predecessor has at most \delta uses. Repeated edges can be combined, or retained with their bounded multiplicity. Greedy edge coloring uses at most 2\Delta-1 colors, because an edge meets at most 2\Delta-2 other edges. Each color is a disjoint-pair layer. These shears can be reordered by colors because no destination in this level is a predecessor in the same level. Output additions have the same bounded-degree property on source or gate coordinates and target coordinates. Reversing the colored levels gives the exact inverse sweep. Thus four sweeps and two output rounds need at most 4(2\Delta-1)H+2(2\Delta-1) layers. Each sweep uses at most 2\ell shears and each output round at most a, proving the count.□

Proof. Write T_r=(h_{i-j})_{0\le j\le i<r}, with zero entries above the diagonal and h_0\ne0. Let g_0,g_1,\ldots be the coefficients of the inverse formal series to \sum_{j\ge0}h_jz^j, extending the specified h_j arbitrarily beyond those needed. Split at s=\lfloor r/2\rfloor, and put

First apply its two diagonal blocks recursively and in parallel. To finish, add from the first block into the second by C=BT_s^{-1}. With global row and column indices its entries are

Partition the source and target ranges into consecutive chunks, of a size to be specified below, and consider a chunk matrix M of size a\times e. Let S_a,S_e be lower-shift matrices, with ones in positions (u,u-1). For entries away from the first row and first column of the chunk, Equation (3.3) gives

The right side is an outer product on those entries. Extending this outer product to the whole chunk leaves only its first row and first column to correct; these have rank at most one each. Consequently

Nilpotence of the shifts gives the terminating telescoping identity

For one outer product vw^{\mathsf T} its summand matrix has entries \sum_{l\ge0}v_{u-l}w_{j-l}, with both vectors zero-extended. It applies to x\in\C^e by the two maps

The first is a convolution after reversing the input and selecting coefficients; the second is a truncated convolution. Sum the at most three resulting vectors. The preceding binary-FFT construction therefore supplies a DAG for Mx satisfying, for absolute constants C_0,C_1,\delta_0,

These bounds include the sums of the at most three terms and all output uses. In particular, copying the input to these three fixed networks multiplies its fan-out by only a constant. The constants do not depend on the Toeplitz entries or the chosen outer products.

Choose once and for all D\ge16C_0+16 and, for sufficiently large r, take chunk size

Choose a fixed threshold r_0 so that, for all r\ge r_0, h\ge r/(2D\log_2r)\ge1. The final chunk in either range may be shorter. For every chunk pair,

At least 7r/8 coordinates of this very recursion block lie outside the source and target chunks. They suffice for the \ell scratch coordinates in Lemma 3.1. No extra coordinate is introduced for the padded FFT: its zero inputs require no register, and every gate requiring a register is already counted in \ell. The lemma implements addition of this chunk’s contribution in O(\log r) pair layers and restores every other coordinate.

Process the chunk pairs serially. Source chunks remain unchanged, target additions accumulate, and coordinates in other chunks can be borrowed again with their current values, even if already updated. There are at most r/h+2=O(\log r) chunks in total and hence O(\log^2r) pairs. The cross-block update needs O(\log^3r) layers. For r<r_0, elimination expresses T_r using scalings and coordinate shears on the same coordinates, at a bounded cost depending only on the fixed r_0.

Let d(r) denote the worst mixed-round depth of this construction. The child recursions use only their own disjoint blocks, so their depths take a maximum, and

Summing along the O(\log r) balanced recursion levels gives d(r)=O(1+\log^4r). Splitting mixed rounds into at most two layers finishes the proof, still on exactly r coordinates.□

Proof. The case r=1 is identity. For r\ge2 put u=\zeta_r, and let P have as its kth column the coefficients of the monic Newton polynomial \prod_{j=0}^{k-1}(X-u^j), for 0\le k<r. Thus P is unit upper triangular. Evaluating these polynomials gives N=F_rP, a lower triangular matrix, with

Only H_0,\ldots,H_{r-1} occur, all nonzero since u is a primitive rth root. In particular N is invertible and

The middle matrix is invertible triangular Toeplitz, and the outer factors are invertible diagonal matrices.

Let D_N=\diag(N_{00},\ldots,N_{r-1,r-1}) and L=ND_N^{-1}. Then F_r=L D_N P^{-1} is a unit-lower/diagonal/unit-upper factorization. Such a factorization, when it exists, is unique: on equating two, a unit lower triangular matrix equals an upper triangular matrix, hence is identity, after which the diagonal and upper factors agree. Since F_r=F_r^{\mathsf T}, transposition supplies another such factorization. Uniqueness gives P^{-1}=L^{\mathsf T}, and therefore

Apply Lemma 3.2 to T and include its two diagonal factors to factor N. Transposing a product reverses its factor order; the transpose of each monomial or pair layer is again of that type. Thus Equation (3.8) has the asserted factorization.□

Proof. Fix the winning matrix A of width q, the winning tensor exponent, and the entire winning word. Since A is nonmonomial, q\ge2. By Lemma 2.3, there are fixed constants C and 0<\alpha<1 such that A^{\otimes k} has a scalar circuit of size at most Cq^k(k+1)^\alpha for every k\ge0. All constants depending on this win remain fixed from now on.

We first obtain enough moderately sized, distinct primes by an elementary estimate. If \pi(v) counts primes at most v, then

The first inequality follows because the central binomial coefficient is the largest of the 2h+1 coefficients whose sum is 4^h. For the second, the exponent of a prime p in that coefficient is

Here each term is zero or one, and the formula itself follows by counting the multiples of p,p^2,\ldots in a factorial. The total power contributed by each prime is consequently at most 2h. It follows that

With h=m^2, this exceeds m+\pi(2q) for all sufficiently large m. Let r_1<r_2<\cdots be the primes greater than 2q and put n_m=\prod_{i=1}^m r_i. Thus r_m\le2m^2 eventually, n_m\to\infty, and \log n_m\ge m\log2.

For clarity, the Chinese remainder factorization here involves only permutations. Write n=n_m and choose integers e_i whose residue is one modulo r_i and zero modulo every other r_j. These satisfy e_i^2=e_i, e_ie_j=0 for i\ne j, and \sum_i e_i=1, all modulo n. The bijections j=\sum_i e_i j_i, k=\sum_i e_i k_i yield

For example, take e_i=(n/r_i)d_i, where (n/r_i)d_i\equiv1\pmod {r_i}; then \zeta_n^{e_i}=\zeta_{r_i}^{d_i} and d_i is a unit modulo r_i. Permuting k_i by this unit converts the corresponding factor to F_{r_i}. Hence F_n is \bigotimes_{i=1}^mF_{r_i} up to input and output permutations.

By Lemma 3.3, each factor has at most

layers, uniformly for these r_i. Pad the shorter sequences in time by identity layers. We next refine a synchronized time step by a bounded number of slots depending only on A.

First reserve a monomial slot: on an axis whose current layer is monomial perform it, and on the other axes perform identity. On a pair-layer axis of width r_i, there are at most \lfloor r_i/2\rfloor pairs. Split them into at most q batches of at most \lfloor r_i/q\rfloor pairs each. Indeed \lfloor r_i/q\rfloor\ge r_i/(2q), so the required number of batches is at most q. Within a batch with t pairs, choose a disjoint q-tuple containing each pair: the 2t pair coordinates are already distinct and there are enough remaining coordinates because qt\le r_i. The desired map on that tuple is its prescribed pair operation together with identity on the q-2 spectators.

By Lemma 2.2, every such map has an implementation using the same fixed sequence of positive A-call slots and monomial slots; denote its total number of slots by s_A. Run these words in parallel on the disjoint tuples. At a monomial slot their disjoint union, with identity on unused coordinates, is monomial. At an A-call slot the layer is a disjoint union of embedded A calls and identity on unused coordinates. Use the same slots for every axis, padding to q batches and using identity throughout empty batches or axes. The number of refined slots per original time is at most 1+qs_A, independently of m and the r_i.

The spectator coordinates may belong to pairs processed in later batches. A completed tuple word is exactly the required pair map direct-sum identity, so every spectator is restored before the next batch on its axis. For simultaneous execution on different axes, the exact product identity

proves correctness even though intermediate spectator values change. We implement each tensor slot as a complete linear map; no assumption about intermediate values on other axes is required. Throughout, the coordinate width remains exactly n.

It remains to charge these refined slots in the scalar model. A tensor product of monomial layers is itself monomial and costs at most n scalar multiplications; permutations merely reindex available values. At an A-call slot, decompose each axis into its active q-tuples and its unused singleton coordinates. Distributing the tensor product over these blocks expresses that slot, up to permutation, as a direct sum of matrices A^{\otimes K} with 0\le K\le m. A sector of width q^K costs at most Cq^K(K+1)^\alpha\le Cq^K(m+1)^\alpha. The sector widths sum to n, so the whole slot costs at most Cn(m+1)^\alpha. The K=0 sectors are identities and need no gates.

Thus the complete circuit, including all monomial scalings, has size

The constants in tensor monomials, Fourier convolutions, and generation words may all be prechosen, as permitted by the nonuniform model. A shear uses at most a scalar multiplication and an addition, and each binary fixed-coefficient combination uses at most three charged gates; no unbounded-fan-in operation is used. Finally, division of Equation (3.10) by n_m\log_2n_m gives O\bigl((1+\log^4m)(m+1)^\alpha/m\bigr)\to0. All matrix identities and all circuits used above are exact.□

Proof. Suppose such a combination exists. We will choose a block-diagonal matrix J containing many copies of every A_i and many identity blocks, and compute J^{\otimes b} in fewer than the usual b|J|^{b-1} calls to J. Its tensor sectors give disjoint places to run copies of the comparison programs. The strict savings in every type leave room to spread these programs over fewer time slots while preserving each program’s order.

For a slot to be one call to J, however, it must contain exactly the prescribed number of calls to each A_i. Random start times will first keep all slot loads below these capacities. We then fill every vacancy with a call belonging to an identity word on separate coordinates. The construction must therefore provide both slack in each slot and enough unused coordinates for these identity words. We first choose block proportions that reserve enough identity space; the strict comparison savings will then supply the slot slack.

Fixed words, species, and proportions. Discard terms with coefficient zero. A comparison whose target has only monomial factors has \Delta^{(r)}_i=-g_i\leq0 for every i. Discarding these terms only increases the numbers s_i, so they may also be discarded. At least one comparison remains. Replace every monomial target factor by an identity of the same width. To obtain its new implementing word, append the inverse of that monomial along the appropriate tensor axis. The appended operation on the full sector is monomial, so all nonmonomial call counts are unchanged. Append width-one identity factors to make every target have the same number b\geq2 of factors. This changes neither its width nor its comparison vector. Keep the entire original type list, including types appearing only in some implementing words. A type absent from every retained target would have only nonpositive retained differences, contrary to s_i>0.

There are now finitely many block species: one species for each A_i, and one identity species I_d for every required identity dimension d, including d=1. Denote this finite dimension set by \mathcal D. By Lemma 2.2, for every i there is a fixed word on q_i coordinates implementing identity using exactly h_i>0 calls to A_i and monomials. Fix all these words and put H=\operatorname{lcm}(h_1,\ldots,h_m).

Choose positive integers a_i, each divisible by H, and positive integers u_d, d\in\mathcal D. By increasing u_1, arrange that, for

one has

This is possible since \theta tends to zero as u_1 increases. For each positive integer v, set

Thus |J|=w. The fixed copy ratios \rho_i=k_i/w=a_i/w_0 and \gamma_d=\ell_d/w=u_d/w_0 are all strictly positive. We let w tend to infinity only along these multiples of w_0. In particular every k_i is divisible by H, and the active coordinate fraction is exactly \sum_iq_i\rho_i=\theta.

The block decomposition of J^{\otimes b} has one sector for every choice of a block copy on each of its b axes. A sector with species pattern \sigma=(\sigma_1,\ldots,\sigma_b) has width equal to the product of those species’ widths. Write \tau_{A_i}=\rho_i and \tau_{I_d}=\gamma_d. The exact number of sectors with that ordered pattern is

Repeated species give ordinary powers in this product: choices on distinct tensor axes are independent, so the same block-copy label can occur on two different axes. Patterns differing in any species have disjoint sector sets.

Disjoint replacements and a fixed saving. Let \sigma(r) be comparison r’s ordered target pattern. Choose a fixed \eta>0 sufficiently small that

All quantities on the right have already been fixed and are positive. For comparison r, select

sectors of pattern \sigma(r). Equation (4.11) ensures that all selections can be disjoint, including selections of different comparisons having the same pattern. Run the comparison’s word on each selected sector. On every other sector run the standard axis program. Sectors containing only identity species require no operation, and no such sector was selected.

The standard sector programs would use G_i^0=b k_iw^{b-1} calls to A_i: choose the axis, one of its k_i copies of A_i, and one coordinate on each remaining axis. The programs after replacement use

where |E_i(w)|\leq H\sum_r|\Delta^{(r)}_i|. In particular G_i is a nonnegative integer divisible by H. There are only finitely many possible standard sector patterns and replacement words. Hence there is a fixed integer L\geq1 bounding the number of nonmonomial calls in every such program, independently of w. Monomials before, between, and after these calls are retained as part of the program.

Choose a fixed \eps>0 such that

and set

For all sufficiently large w, F>0 and

The constants in the error terms are independent of w. Fix a number \kappa>0 smaller than half the minimum of the positive coefficients in this display. Increasing the lower threshold on w if necessary gives simultaneously

Thus the finite comparisons, their words, b,h_i,H, the species proportions (and \theta), \eta,\xi_i,L, and finally \eps,\kappa have all been fixed before w is taken large.

A schedule respecting all dependencies. Independently for each sector program having at least one nonmonomial call, choose a start uniformly from \{1,\ldots,F\}. Put its successive nonmonomial calls in consecutive slots starting there. Every call lies in \{1,\ldots,T\}, and its internal order is preserved. For a fixed type i and slot t, let X_{i,t} be the number of scheduled calls of that type. A given sector contributes an indicator, even if its program uses A_i repeatedly: different positions in that program require different starts to fall at slot t, and these events are mutually exclusive. Its contribution has mean at most its number of A_i occurrences divided by F. Different sectors have independent starts. Consequently X_{i,t} is a sum of independent Bernoulli variables with \mathbb E X_{i,t}\leq G_i/F.

For completeness, write \rho_{\max}=\max_i\rho_i, and choose 0<a\leq1 so small that (e^a-1-a)\rho_{\max}\leq a\kappa/2. Such a choice follows, for example, from e^a-1-a\leq ea^2/2 on [0,1]. Independence, 1+x\leq e^x, and Markov’s inequality give

There are mT=O(w^{b-1}) pairs (i,t), with fixed m,b. The union bound therefore tends to zero. For a sufficiently large admissible w, fix one schedule for which X_{i,t}\leq k_i for every type and every slot. Independence between different slots is neither claimed nor needed.

Completing the vacancies with identities. For type i, the number of unfilled call positions is

It is divisible by H, hence by h_i. Moreover, Equation (4.13) gives

Let d_i=D_i/h_i; for sufficiently large w, every d_i>k_i. Allocate d_i disjoint ordered groups of q_i wires to run the fixed h_i-call identity word for A_i. All these groups, for all types together, fit in the union of the all-identity sectors. Indeed that region has exactly ((1-\theta)w)^b wires, whereas

We used h_i\geq1 and G_i\geq0 in the first inequality. A dummy group may cross the boundaries of the original identity sectors, since the prescribed action on their entire union is identity.

List the D_i idle positions for type i in chronological order, with any fixed order among positions in the same slot. Assign successive positions cyclically to its d_i dummy groups. Each group receives exactly h_i positions because D_i=d_i h_i. Two successive positions assigned to the same group are d_i places apart in this list. A single time contains at most k_i<d_i positions, so these two positions have strictly increasing times. Assign the identity word’s successive calls to these times. This argument permits arbitrary clustering of vacancies. We now have exactly k_i calls to every type i in every slot, on mutually disjoint tuples.

The exact word, including all monomials. The physical support of each active-sector program is fixed. Dummy groups have fixed supports disjoint from each other and from those sectors. Write any one of these programs chronologically as

where the O_{p,j} are monomials on that program’s support. Let its strictly increasing call times be t_{p,1},\ldots,t_{p,l_p}. Place O_{p,0} in the gap immediately before t_{p,1}, and place O_{p,j}, j\geq1, in the gap immediately after t_{p,j}. This is always before its next call, including when the times are consecutive. A program with no calls can place its single monomial in the initial gap. Operations in a gap on different program supports combine into one ambient monomial M_t, where gap t follows slot t, and gap zero precedes slot one. A sector monomial may permute all values on its support. Subsequent calls still use the fixed tuple indices prescribed by that same program, so this causes no change to the program’s meaning.

Let B_t be the simultaneous calls in slot t. There are exactly k_i ordered tuples for each A_i. Match them bijectively to the corresponding active blocks of J. Their union has \sum_iq_i k_i=\theta w wires. Complete this matching to an injection of all w coordinates of J by using (1-\theta)w further distinct wires as spectators for its identity blocks. There are enough: the ambient width is w^b\geq w. Extend the matching to a permutation P_t of all ambient wires. With the convention that P_t gathers into the canonical first w positions, one has exactly

The conjugate acts by the requested A_i on every called tuple and fixes every other physical wire pointwise. In particular a spectator can belong to an unfinished sector program or dummy word: both its value and its location are preserved by the complete gather–call–scatter operation. Figure 1 shows the chronological slots and the gather–call–scatter realization of each B_t.

Thus the matrix product

restricts to the prescribed program on every active sector and to identity on every dummy group and unused identity wire. It is exactly J^{\otimes b}. By Equation (4.15) it uses precisely T<bw^{b-1} calls to J, with all remaining operations monomial, on precisely w^b wires. Since at least one A_i occurs in J, the matrix J is nonmonomial. This is a finite win, contrary to the assumption.□

Proof. A shear adding a nonzero multiple of one coordinate into another is a monomial conjugate of U\oplus I, so its price is one by Equations (4.1), (4.4) and (4.6). For an invertible pair matrix, first permute rows if needed to make its upper-left entry nonzero. With entries \alpha,\beta,\gamma,\delta and determinant D\ne0, it factors as

This uses at most two nontrivial shears and a monomial. Finally an embedded call to A is a permutation conjugate of A\oplus I_{w-|A|}, omitting the identity block when it has size zero, whose price is p(A). Repeated product subadditivity gives the word bound. Identity padding has price zero by direct-sum additivity. The last assertion is an exact matrix identity on all input coordinates; it does not assume zero scratch values.□

Proof. A finite DAG has finite depth and finite maximum fan-out, counting repeated operand edges and designated output uses. Apply Lemma 3.1 to this DAG with source coordinates x, target coordinates y, and one additional coordinate per gate, with arbitrary initial values. It gives at most 8l+2a elementary shears realizing (x,y,z)\mapsto(x,y+Gx,z). Although depth and fan-out may vary with the DAG, the shear count is independent of both; the layer bound is not needed here. By Corollary 4.3 and identity padding, this proves Equation (5.1). If only a_0 rows are nonzero, apply the same replay to the submap of those rows, retaining all l gate coordinates, and identity-pad the omitted targets. This gives 8l+2a_0 instead; if a_0=0, the shear is identity.□

Proof. Only the first t coefficients of f affect the matrix. Pad these coefficients and the input coefficient vector to a power-of-two length m with 2t\le m<4t. A length-m Fourier transform, multiplication by the prechosen Fourier transform of the fixed kernel, and an inverse Fourier transform compute their ordinary convolution, since its degree is at most 2t-2<m. Selecting the first t coefficients gives \mathcal T_t(f). The binary Fourier recursion splits even and odd indices and combines each pair by one scalar multiplication and two additions or subtractions, so it and its inverse use O(m\log(2m)) permitted scalar gates. The frequency scalings and inverse normalization cost O(m) gates, even when some kernel frequencies are zero. This is a DAG construction and does not require those intermediate scalings to be invertible.

Exactly the same construction applies to the first t coefficients of 1/f, which exist because f(0)\ne0. Apply Lemma 5.2 and Equation (5.3) to these two DAGs. Every kernel coefficient and Fourier constant is prechosen; there is no charge for generating its description, but its multiplication on variable data has been included in the count.□

Proof. Write K=\begin{pmatrix}M&C\\0&D\end{pmatrix} and fix k\ge1. The usual computation of Y=D^{\otimes k} on R=r^k bottom coordinates applies D along axes 1,\ldots,k, using u=kr^{k-1} calls. Replace each call by a K call, supplying a fresh group of n data coordinates for its M side. Since these groups are used only once and do not affect the bottom coordinates, the resulting matrix is

We will compress the u whole n\times R row blocks of EY^{-1}. No independent change of its individual scalar rows is used.

Label a call by its axis j and fiber indices \mathbf i=(i_\ell)_{\ell\ne j}. For 1\le a\le n and a bottom multi-index \boldsymbol\ell=(\ell_1,\ldots,\ell_k), its row block R_{j,\mathbf i} in EY^{-1} has entries

To see this, the call’s contamination uses C at axis j, with D already applied on axes h<j and identity on axes h>j. Multiplication by Y^{-1} cancels the earlier D factors, leaves CD^{-1} locally, and introduces D^{-1} on the later axes.

For fixed j, insertion of the fixed matrix CD^{-1} in the jth slot defines a linear map from the complementary tensor covector space to \Mat_{n\times R}(\C). The complementary covectors in Equation (5.6) form a basis, because every D^{-1} is invertible. Coordinate covectors form another basis. The images of either basis therefore span the same image space, whether or not this linear map is injective. Images of coordinate covectors have at most nr nonzero entries. Taking their union over j gives a sparse spanning family for the span S of all actual row blocks. Select a basis B_1,\ldots,B_h from this family; then

Overlaps between axis spans and dependencies among rows of C can only decrease h.

The map \Phi:\C^u\longrightarrow S sending coefficients to their linear combination of the actual row blocks is surjective. Choose one lift of each B_i under \Phi, and append a basis of \ker\Phi. These u vectors form a basis of \C^u: applying \Phi to a relation first kills the coefficients of the B_i, and then independence in the kernel kills the others. Put these vectors as the rows of V\in\GL_u(\C). Postapply V\otimes I_n to the data groups. The data block becomes exactly

while its contamination expressed in the final bottom variables is the stack B_1,\ldots,B_h,0,\ldots,0. Cancel it by at most hnr elementary shears from those bottom variables into the data groups. The final map is exactly (V\otimes M)\oplus Y.

The previously proved price laws now give

The identical n p(V) terms cancel, without any estimate on V. Since h\le nr^k, division by u=kr^{k-1} yields

Let k tend to infinity with K,n,r fixed. This proves Equation (5.5). If r=1, the same construction has R=1, u=k and error at most n^2/k. If S=0, there are no B_i and a kernel basis alone supplies V; no cancellation shears are needed. Empty diagonal blocks simply reduce to the other block. Exchanging the two groups proves the lower triangular case, and induction on the number of blocks proves the last assertion.□

Proof. If r=0, the state is absent and H=M=K is constant. The exact tensor and direct-sum laws already give the assertion. Suppose r\ge1 and introduce polynomial matrices and scalar polynomials

Then H=F/a, H^{-1}=aJ/b, a(0)=1, and b(0)=\det M\ne0. We have

For n=1 the adjugate J is the constant 1, as required by these formulas. Cancelling the later-axis responses in Equation (5.8) gives

Thus q_k=b^k clears the entire matrix H_k^{-1}E. Its jth cleared block is the following explicit polynomial map W_j\to\C^N:

Its degree is at most

The scalar q_k has degree at most knr and has nonzero constant term. The identities also hold when any of the displayed matrix polynomials vanish.

Here is an explicit DAG bound for the nonzero time coordinates of Q_k(z)w=\sum_{j=1}^kQ_{k,j}(z)w_j. Put m=knr, and choose m distinct complex evaluation points. Because Equation (5.10) is polynomial, no avoidance of poles is needed. At one evaluation point, a rectangular application of JCR on its r-axis costs at most 2rN scalar gates. Applying J on the preceding j-1 axes costs at most 2n(j-1)N gates, by doing the fixed n\times n map on all fibers of each axis. The scalar factor costs at most N gates. Adding the k contributions costs at most (k-1)N more. One evaluation therefore uses at most

gates. All local entries and scalar powers here are prechosen constants. Applying the inverse scalar Vandermonde matrix to the m evaluations, separately on each of the N coordinates, recovers all m coefficient vectors using at most 2m^2N further scalar gates. The total is O_K((k+1)^3N). For any run length t, keep only the first \min(t,m) coefficient vectors; all other rows of the truncated response are zero. This bound is consequently uniform in t.

Set P=\mathcal T_t(1/q_k) and A'=A_{k,t}(P\otimes I_N). In formal series modulo z^t, A'^{-1}E_t is precisely the coefficient map of q_kH_k^{-1}E=Q_k just constructed. Hence Lemma 5.2, with zero output rows omitted, bounds the price of the shear with block -A'^{-1}E_t by O_K((k+1)^3N). This uses only the rectangular shear law, not a price bound for an arbitrary invertible circuit output.

Now form the exact product

Its top row of blocks is (A',0). Each factor is invertible, and A' is invertible because H(0)=M and q_k(0)\ne0. Therefore the other diagonal block of this lower triangular product is also invertible. By Lemma 5.4 its price is at least p(A'). There are tkn^{k-1} cell calls in \mathcal K_{k,t}, so

Here the tensor and direct-sum laws price the scalar preprocessing by Np(P), including its identity on the state. Finally A_{k,t}=A'(P^{-1}\otimes I_N) and inverse symmetry give

Apply Lemma 5.3 to P. Its bound is uniform even though q_k varies with k, proving Equation (5.9).□

Proof of Theorem 5.1. Independent row and column permutations move M to the top-left corner and preserve p(K). Write the resulting matrix as in Equation (5.7). If the complementary width is zero the claim is equality; otherwise apply Lemma 5.5. The matrix A_{k,t}=\mathcal T_t(H^{\otimes k}) is lower triangular in time with t identical diagonal blocks M^{\otimes k}. Thus Lemma 5.4 and the tensor law imply

Fix K,n,r first and use the bound of Equation (5.9). For example, choose t=t(k)=2^{\lceil8\log_2(k+1)\rceil}, so (k+1)^8\le t<2(k+1)^8. Division by tkn^{k-1}=tkN/n gives

Both errors tend to zero. The matrices M and K in this real inequality are fixed, so it proves the exact inequality p(M)\le p(K). No continuity assertion about the price, or limiting circuit for a matrix, has been used. A zero-size submatrix, if allowed, can simply be omitted and assigned price zero.□

Proof. G is an invertible square submatrix of \begin{pmatrix}I_m&G\\0&I_m\end{pmatrix}, so Theorem 5.1 gives its first inequality, and Lemma 5.2 gives the second. Although the proof of the corner law fixed each individual matrix while taking a limit, the resulting inequality is exact for every finite matrix. The numerical constants here come entirely from the dirty scratch simulation.□

Proof. Choose once and for all polynomial J(z) and scalar polynomial u(z) such that

for example, take J=\operatorname{adj}G and u=\det G. Write

These are degree bounds with zero coefficient matrices permitted. The subscript on G_j or J_i in this proof denotes a coefficient of the tensor power, rather than of the original fixed matrix. Both d and e are bounded by a fixed multiple of k. If d=0, multiplication is coefficientwise, so W=A_G and the result holds. Assume d>0 and set T=t-d.

Let L=W-A_G. An input supported at times less than T has product with G_k of degree less than t, so L has zero columns at those times. Scalar polynomial division also shows that, for every input x(z) of degree less than t,

Here v_x is minus the quotient of G_kx by \ell, with scalar division applied to every coordinate. The degree bound follows from \deg(G_kx)<t+d.

The invertible relative map and the scalar prefix map are

The series in P is regular and nonzero at zero. Since S has zero prefix columns and P^{-1} is identity on the suffix of length d,

This identity uses the entire prefix–suffix decomposition; a general scalar change of basis on all t times would not have this property.

On the prefix, the output of the correction in Equation (6.4) is, modulo z^T,

It therefore vanishes at prefix times greater than or equal to e+d. Define the disjoint sets

The correction has columns only in \mathcal B and rows only in \mathcal U, where |\mathcal U|\leq e+2d=O(k). Thus both blocks coupling \mathcal U to its complement are zero in the correction. A simultaneous permutation of rows and columns gives

Invertibility of the active block follows from invertibility of \widehat R. If the coarse early and suffix ranges would overlap, the minimum in \mathcal E truncates the former: the middle set is then empty and t\leq e+2d. The bound and the direct-sum conclusion still hold. Figure 3 displays the support of the correction \widehat R-I when the middle set is nonempty.

The small number of active times alone would not bound the cost of their N\times N spatial blocks. We next give an indexed formula that controls those blocks uniformly. For each integer m\geq0 that occurs below, divide the scalar monomial z^m by \ell and write

For m=b+j with 0\leq b<t and 0\leq j\leq d, we have \deg q_m<d. Set q_{s,m}=0 when s<0 or s\geq d; also q_m=0 when m<t. Let

All these scalars may depend on k,t,\ell. For 0\leq a,b<t, define

Then the exact block formula is

Indeed, on an input z^bx_b, scalar division gives v_x=-\sum_jq_{b+j}G_jx_b in Equation (6.3). The prefix correction is J_kv_x, which gives the first case of Equation (6.6). The suffix is unchanged by the left prefix map, so its correction is (\ell/u^k)J_kv_x modulo z^t, which gives the second case. Right conjugation has already disappeared by Equation (6.4). Every spatial product is ordered as J_iG_j: no commutation of coefficient matrices is used. Reduction and scalar convolution introduce only the displayed scalar weights, irrespective of the length of the underlying coefficient lists.

Here is a gate count for applying the active block. Applying a fixed n\times n matrix on each of the N/n fibers of one tensor axis uses at most 2nN scalar gates, by direct multiplication and addition. Consequently G(\xi)^{\otimes k} applies in at most 2nkN gates for any \xi\in\C, including points where G(\xi) is singular. At d+1 distinct points, interpolation expresses any chosen coefficient G_j as a scalar linear combination of these evaluation matrices. Running the d+1 evaluation circuits on the same input and combining their outputs uses at most

gates. The same argument with e+1 points applies to J_i, so the ordered product J_iG_j has a circuit of this order by composition. No inverse of an evaluation matrix is needed; only the scalar Vandermonde interpolation matrix is inverted in choosing constants.

There are O_G((k+1)^2) active ordered pairs of time indices and (e+1)(d+1)=O_G((k+1)^2) spatial generators in Equation (6.7). For each active block entry, apply each required generator to its input vector, multiply its output by \gamma_{abij}, and add the resulting vectors. The generator applications cost O_G((k+1)^6N) gates in total. The scalar weights and output additions cost only O_G((k+1)^4N) additional gates, and the identity contribution uses the already available input values. The output count is |\mathcal U|N=O_G((k+1)N). Thus the universal one-way DAG bound, Corollary 5.6, and Equation (6.5) give

The potentially complicated coefficients in Equation (6.6) are prechosen circuit scalars. Every use of such a scalar has been charged; the model does not charge for producing its description. This is precisely why the gate bound is independent of t and \ell.

By Lemma 5.3, direct-sum additivity and the tensor law,

Undoing the conjugation and using inverse symmetry gives

Finally W=A_GR and A_G=WR^{-1} imply |p(W)-p(A_G)|\leq p(R), proving Equation (6.1). Dividing that bound by tkN gives

For the choice of t in Equation (6.2), both terms tend to zero. Also t>d eventually, since G was fixed before k grows. Every estimate holds uniformly for all admissible \ell at that k,t.□

Proof. If there is no state block, H=M=K. With a state block present, s_0=0 is the invertible corner law, Theorem 5.1. We prove the claim for s_0\ne0 by fixing K,s_0 throughout the following estimates. Let

Then G is polynomial, q(0)=1, q(s_0)\ne0 and G(0)=M is invertible. Put N=n^k and choose t=t(k) as in Equation (6.2). For sufficiently large k, this choice meets the degree condition in Lemma 6.1.

Write A_H=\mathcal T_t(H(z)^{\otimes k}). The cascade estimate in Equation (5.9) gives, with constants depending only on the fixed cell,

Moreover,

and the scalar factor is invertible. The scalar-convolution bound and the product law in both directions show that

Its constant is independent of the degree or coefficients of q^k.

Apply the coefficient-boundary comparison with \ell(z)=(z-s_0)^t. To verify its remaining invertibility hypothesis, translate a polynomial to its coefficients at s_0. The scalar translation matrix V_{s_0} has entries

It is invertible with inverse V_{-s_0}. In the translated coordinates, multiplication modulo (z-s_0)^t becomes multiplication by G(s_0+w)^{\otimes k} modulo w^t. Hence

The right-hand side is lower triangular in time, with repeated invertible diagonal block G(s_0)^{\otimes k}. Thus W is invertible, as required.

The price of translation is also small. If D_!=\diag(0!,1!,\ldots, (t-1)!) and U_{s_0} is the upper triangular Toeplitz matrix with entry s_0^{j-i}/(j-i)! at j\geq i, then

Monomial invariance, transpose symmetry and Lemma 5.3 imply

Applying triangular monotonicity, Lemma 5.4, to Equation (6.13), then undoing its two scalar changes of basis, gives

For the equality, use the tensor law and the nonzero scalar relation G(s_0)=q(s_0)H(s_0), which preserves price.

Combining Equations (6.1), (6.11), (6.12) and (6.15) yields

Divide by tk n^{k-1}=tkN/n and let k tend to infinity with the single fixed choice of t in Equation (6.2). The error vanishes by Equation (6.9), proving Equation (6.10).□

Proof. Replace X(z) by X(z_0+z) and E by E-z_0, so it suffices to treat z_0=0. By regularity, the entries have polynomial denominator representations nonzero at zero. Their product gives a scalar polynomial q with q(0)\ne0 for which G=qX is polynomial. In particular G(0) is invertible. Enlarge the finite exceptional set to

At every s\notin E', the matrix G(s) is invertible and p(G(s))=p(X(s))\leq C_0.

Fix X,q,E' before letting k grow, put N=n^k, and again choose the single run length specified in Equation (6.2). For each such finite t, let \zeta_t be the specified primitive tth root of unity. Choose

Only finitely many complex numbers are forbidden, so this choice exists for every k. No fixed dilation is asserted to work for all k, and no bound on a_k is needed. The polynomial

has nonzero constant term and distinct roots s_h=a\zeta_t^h, all outside E'. Let W be multiplication by G_k modulo this polynomial. Scalar evaluation at the roots has matrix

The roots are distinct, so this matrix is invertible, and evaluation gives the exact conjugacy

This also proves that W is invertible.

Since t is a power of two, the binary FFT computes F_t with O(t\log(2t)) scalar gates. The universal DAG-price bound and monomial invariance therefore give

uniformly in a. The direct-sum and tensor laws applied to Equation (6.17) imply

On the other hand, A_G=\mathcal T_t(G_k) is lower triangular with diagonal G(0)^{\otimes k} repeated t times. Thus

For sufficiently large k the degree condition of Lemma 6.1 holds. Its uniform estimate applies to the modulus just chosen, even though a=a_k can vary. Combining it with Equations (6.18) and (6.19) and dividing by tkN/n proves

Letting k tend to infinity proves the assertion.□

Proof. Solving z_{\rm out}=Bx+Dz_{\rm in} gives the displayed formula. Its determinant is \det A/\det D, as follows by taking the Schur complement of D^{-1}, so it is invertible. Both pivot hypotheses are relevant: D makes the solve possible, whereas A makes its resulting transition invertible.

We realize this solve as a feedback operation to which Theorem 6.2 applies. Use data (x,y) of widths n,r and state z of width r. First apply, separately on the r pairs (y_i,z_i), the matrix

Next apply K on (x,z_{\rm in}), leaving \widehat y fixed. Finally apply

with outputs (y',z'). The full cell, denoted \mathcal K_\beta, sends (x,y,z) to (x',y',z'). Since \det P_\beta=\beta-1 and \det Q_\beta=-1, it is invertible whenever \beta\ne1, and

The blocks of this cell with respect to its data/state split are

Its direct data block

has polynomial determinant and satisfies M_0=K. Thus the precise genericity requirement is

This excludes only finitely many numbers and hence allows a choice of \beta. At feedback parameter one, the feedback denominator is \Id_r-(\Id_r-\beta D)=\beta D, which is invertible.

Indeed, closing the state by z=z' in z'=\beta y+z-\beta z_{\rm out} forces z_{\rm out}=y. Consequently

The feedback output map on (x,y) is therefore exactly \widetilde K, already proved invertible. The full cell, its direct block, its feedback denominator, and its output all meet the hypotheses of Theorem 6.2. That Theorem and Equation (7.2) prove the inequality.□

Proof. Let the shared coordinate occupy port i_0 of Y_1 and port j_0 of Y_2. Index the tensor grid by (i,j)\in\{1,\ldots,a\}\times\{1,\ldots,b\}. The usual word for Y_1\otimes Y_2 first applies Y_1 along each fiber with fixed j, and then Y_2 along each fiber with fixed i. Calls within either stage have disjoint coordinate sets, so put the j=j_0 call last in the first stage and the i=i_0 call first in the second stage. These two consecutive calls have the prescribed port identification: send port i of Y_1 to (i,j_0) and port j of Y_2 to (i_0,j). Figure 4 shows the selected fibers of this consecutive call pair and their single shared coordinate.

Their union has a+b-1 coordinates. On all other grid coordinates their product is identity, so the consecutive subproduct is a permutation conjugate of

The exact direct-sum law makes its price p(P), even when this padding is empty. Grouping these two calls in the tensor word yields

Thus p(P)\ge p(Y_1)+p(Y_2). Product subadditivity applied to the two identity-padded calls gives the reverse inequality.□

Proof. Write D=d\ne0. For each positive integer \ell, use \ell copies of K, with fresh data groups x_1,\ldots,x_\ell of width n and one shared state coordinate. In chronological order the recurrences are

Let \mathcal C_\ell send (x_1,\ldots,x_\ell,w_0) to (y_1,\ldots,y_\ell,w_\ell). At every extension the previous chain is regarded as a matrix only on its old data groups and its one state coordinate. The next data group is outside this set, so the intersection with the next call is exactly the one state coordinate. Coordinates fixed by the old chain remain members of its old set; no padding from the tensor-grid proof is added to it. Induction using Lemma 7.2 gives

The full chain is invertible as a product of invertible calls. Its state-to-state block is d^\ell, and its direct block on the data is lower block triangular with diagonal blocks A. In fact its (j,i) block for i<j is Cd^{j-1-i}B, and its blocks for i>j vanish. Both blocks required by Lemma 7.1 are therefore invertible for every \ell.

Pivoting the boundary state means that w_\ell is given and w_0 is requested. The exact backward recurrence is

Thus the pivoted chain \widetilde{\mathcal C}_\ell consists of copies of \widetilde K in the order j=\ell,\ldots,1, again with fresh data groups and one shared state. The same intersection argument gives

Put S=A-Cd^{-1}B. Since \det K=d\det S, the matrix S is invertible. The reverse chain has state block d^{-\ell} and a direct data block upper triangular in chronological order, with diagonal blocks S; equivalently it is lower triangular in reverse chronological order. Its full matrix is invertible too. Hence Lemma 7.1 applies both to the forward chain and to the reverse chain. Pivoting the reverse chain returns the forward chain, and therefore

Equivalently, |p(\widetilde K)-p(K)|\le4/\ell for every \ell. Letting \ell tend to infinity proves equality. The earlier pivot inequality is an exact statement for each finite matrix, so this argument requires no estimate uniform in the increasing data width.□

Proof. Relative to U, the coefficient matrices of U' and V' are

with determinants d and \det A, respectively. These give the asserted criterion exactly. When both are nonzero, the transition between them is Equation (7.1) with scalar pivot. Apply Lemma 7.3. Reorderings have zero price.□

Proof. For a pair matrix H, the tensor law reads p(H\otimes H)=4p(H). We therefore seek a four-coordinate map of price at most six that becomes a tensor square after monomial changes. Two shears and the basis exchanges below put this map into the form of a rank-one perturbation of the identity, making the required monomial changes explicit.

Fix \lambda\in\C\setminus\{0,1\} and four independent linear forms a,b,c,d. We first bound the transition from

Its matrix is \Id_4+J, where

Here J is monomial because \lambda\ne0, and

shows that \Id_4+J is invertible. Apply Theorem 6.2 at parameter one to

This full cell is invertible, its direct block and feedback denominator are identities, and its output is \Id_4+J. To implement \mathcal L, send (h,l) to (h,Jl) by a monomial, add h_i into the second coordinate of each of the four pairs, and swap the two blocks. Consequently

We change the first and third members on the Y side using two shears and legal exchanges. For clarity, all intermediate lists are displayed below. Put

Every determinant in the last two columns is computed from the coefficient rows in the original ordered basis (a,b,c,d).

The steps 0\to1 and 2\to3 exchange the second members; the steps 3\to4 and 5\to6 exchange the fourth members. The step 1\to2 adds the second member of Y into its first, and 4\to5 adds its fourth member into its third. These are the only two shears. The determinant table proves that every list is a basis, including on both sides of every exchange; it follows also by direct elementary row operations. Thus Corollary 7.4 applies at all four exchanges. Changing the source basis from Y to EY by a shear replaces its transition matrix T by TE^{-1}, increasing price by at most one. Together with Equation (7.10), this proves that the transition from the last Y list to X has price at most six.

Reorder these final lists as

Let

Then k^{\mathsf T}\overline Y=(1-\lambda)a and \overline X-\overline Y=\Delta a, so the transition matrix is the explicit rank-one perturbation

We now give the diagonal scalings. All their entries are nonzero under the stated hypotheses on \lambda. Set u=\lambda^{-1} and

The rank-one summand of L_1TR_1 has every entry equal to one, and a direct calculation gives

With the further scalings

we obtain

Write B(u)=\left(\begin{smallmatrix}1&1\\1&u\end{smallmatrix}\right). The (\alpha,\gamma) entry of B(u)\otimes B(u), for bit pairs \alpha,\gamma\in\{0,1\}^2, is u^{\alpha_1\gamma_1+\alpha_2\gamma_2}. Ordering its rows by 10,01,11,00 and its columns by 01,10,11,00 gives exactly Equation (7.12). All the scalings and permutations preserve price. The tensor law therefore yields

Every u\ne0,1 arises from the permitted choice \lambda=1/u, proving Equation (7.9).

Finally, if H=\left(\begin{smallmatrix}a&b\\c&d\end{smallmatrix}\right) is dense and invertible, then

Density makes ad/(bc)\ne0, and invertibility makes it different from one. Monomial invariance completes the proof.□

Proof. We have T_1=U, so p(T_1)=1. Put n=2^m and consider the transition from input forms x=(x_1,\ldots,x_{2n}) to output forms y=K_0x, where

We shall exchange each bottom input form with the corresponding bottom output form, using only the exact scalar pivot law of Lemma 7.3. Here is a determinant check for every intermediate exchange.

For any subset H\subseteq\{n+1,\ldots,2n\} of already exchanged positions, keep the forms in their original index positions and set

Let U_H,V_H be their coefficient matrices relative to x. Simultaneously permuting rows and columns to put H first gives

The row and column permutation signs cancel. Every principal submatrix of the unit lower triangular matrix K_0 is unit lower triangular, so

The empty principal minor, when it occurs, has determinant one. Thus both lists are bases and their current transition Q_H=V_HU_H^{-1} has determinant one.

For the next index j\notin H in the bottom half, replacing u_j by v_j changes the input determinant by the factor (Q_H)_{jj}. Replacing v_j by u_j changes the output determinant by (Q_H^{-1})_{jj}. Applying (8.2) to H and H\cup\{j\} therefore gives

Move position j to the last port in both bases. The scalar diagonal block required for the pivot is consequently one; the determinant of its complementary principal block is, by the cofactor identity,

Both hypotheses of Lemma 7.3 hold at every step, and each exchange preserves the price exactly.

After all bottom positions have been exchanged, write the original inputs as (a,b) and the bottom output as z=T_ma+T_mb. Solving gives b=T_m^{-1}z-a. Thus the final transition, from (a,z) to (T_ma,b), is

Conjugating by \diag(I,-I) changes the lower left block to I; the result is T_{m+1} by (8.1). Monomial invariance and the tensor law now give

which proves the formula by induction.□

Proof. Write e_{ij} for matrix units, and fix any order of the supported pairs. Form the polynomial matrix

Then K(0)=I and K'(0)=A. Outside a finite set E_0, the diagonal factor is an invertible monomial and every other factor acts on its two coordinates as the dense invertible matrix

For example, E_0 may contain zero, the roots of the diagonal-factor determinant, and all roots of 1-\eps^2A_{ij}^2 for the supported pairs. These are finitely many roots of nonzero polynomials. By Lemma 7.5, direct sums, and product subadditivity,

Put Q(\eps)=(K(\eps)-I)/\eps, with its polynomial extension Q(0)=A. First fix a parameter t outside the single finite set

The polynomial matrices

have nonzero determinants at zero, since I\pm tA are invertible. Consequently the rational output

is regular and invertible at zero.

For this fixed t, exclude also \eps=0,t,-t and the roots of \det C_+(\eps)\det C_-(\eps), in addition to E_0. This defines a finite set E_t, which may depend on t. For \eps\notin E_t define

and consider the data–state cell

The first factor is a direct sum, after reordering, of w scalar pair matrices. Their determinants are

Hence the cell is invertible. Its direct block mI_w is invertible, and its feedback denominator at feedback parameter one satisfies

so that denominator is invertible too. Its feedback output is exactly

The last equality follows from mI_w+(v-ms)K(\eps)=\eps C_+(\eps)/(\eps+t). The output is invertible by the choice of E_t, so every hypothesis of Theorem 6.2 is satisfied.

An invertible scalar pair has price at most two. The factorization (8.13) and (8.11) therefore imply

Apply Theorem 6.3 to the rational matrix H_t at \eps=0. This proves

The quantifiers here are useful: A,w,h and C_A were fixed first; for each t\notin\mathcal E there is a finite E_t giving the same bound, and specialization is applied separately for that t. Thus (8.15) holds for every t outside one finite set, with one price bound. Only the rational output is specialized. At \eps=0 the cell itself would have m=-1, s=1, v=0, and K=I, making its feedback denominator zero; no feedback law is applied to that cell.

For the second specialization use z=1/t and the rational matrix

By the Real Spectral Theorem, A=O\diag(\lambda_1,\ldots,\lambda_w) O^{\mathsf T} for a real orthogonal O and real eigenvalues \lambda_i. In this basis, the corresponding rational functions are (z+\lambda_i)/(z-\lambda_i). If \lambda_i=0, this function is identically one after cancellation; if \lambda_i\ne0, it is regular at zero with value minus one. It follows that Y is regular at zero and Y(0)=R, an invertible matrix. In particular, the zero eigenspace is semisimple; real symmetry supplies exactly the diagonalizability needed for this removable-singularity assertion.

For all z outside \{0\}\cup\{\lambda,-\lambda:\lambda\in\operatorname{spec}(A), \lambda\ne0\}, we may take t=1/z in (8.15). Hence p(Y(z))\leq C_A outside a finite set. A second application of Theorem 6.3 yields p(R)\leq C_A. The orthogonal diagonalization was used to identify a rational matrix and its value; it was not used as a priced implementation. Neither specialization assumes continuity of p.□

Proof. If there were no finite win, the preceding construction and all its price bounds would apply for every fixed integer d\geq1. Equations (8.16) and (8.22) would imply

Since w>0, this says d\leq30, contrary to choosing any fixed integer d>30. This contradiction proves the theorem.□