A D V E R T |
I S E M E N T |
| Math Sites: lean ages 13-∞ readme referees parents | >>> MAITH GAMES <<< | all 372 compute stand |
|
LEVEL 3 OF 3 · Uniform identity testing for noncommutative formulas
Polynomial Hitting Lists for Noncommutative Rational Formulas
expertly designed by an internal OpenAI model · released 2026-09-24
· original PDF
IntroductionA noncommutative rational formula is a rooted tree whose leaves are variables or rational constants, whose binary gates are addition or ordered multiplication, and whose unary gates are inversion. Its size is its number of vertices, including leaves and inverse gates. At a tuple of square rational matrices, a scalar is interpreted as a scalar multiple of the identity. Evaluation is defined only when every inverse gate encounters an invertible matrix. Call a formula admissible if it has a defined rational matrix evaluation of some positive dimension, and nonzero if one of its defined rational matrix evaluations is nonzero. These operational definitions suffice for the hitting-list theorem; its proof does not need a construction of the free skew field. In particular, algebraic cancellations do not enlarge a formula’s domain of evaluation. Identity testing asks whether an admissible formula is zero at every defined evaluation. Scalar substitutions cannot answer this question: for example, \(x_1x_2-x_2x_1\) vanishes on all scalar tuples but is nonzero on matrices. A matrix hitting list is a fixed finite list of tuples that supplies a defined nonzero evaluation for each nonzero formula in the prescribed class. Such a list permits testing through evaluations without access to the formula tree. With inverse gates, the same tuple must satisfy every domain condition imposed by that tree, including conditions in branches that later cancel. In oracle terminology, an undefined evaluation is reported as such; only defined outputs are tested for zero. Theorem 1. There are a deterministic Turing machine \(G\) and fixed positive integers \(C,k\) with the following property. Given \(1^n,1^s\), where \(n,s\geq1\), the machine outputs a finite list \(\mathcal H_{n,s}\) of \(n\)-tuples of rational square matrices, in at most \(C(n+s+1)^k\) bit operations. The entire output, with signed binary numerators and positive binary denominators, has at most \(C(n+s+1)^k\) bits. For every nonzero admissible rational formula \(\Phi\) in \(n\) variables of size at most \(s\), some tuple in \(\mathcal H_{n,s}\) is a defined evaluation of \(\Phi\) with invertible value. The same list works for all such formulas, regardless of the bit lengths of their rational constants or their inverse depth. The generator receives no formula, oracle, randomness, or advice. The invertible-value conclusion is stronger than the nonzero-value requirement. All tuples produced below even have one common dimension depending only on \(n,s\). ContextThe algebraic setting comes from the theory of rational identities and universal fields of fractions (Amitsur 1966; Cohn 2006). Affine-matrix representations of free-field elements appear in Cohn and Reutenauer (Cohn and Reutenauer 1994, sec. 3.1); Kaliuzhnyi-Verbovetskyi and Vinnikov give a systematic account of matrix evaluation domains and rational functions (Kaliuzhnyi-Verbovetskyi and Vinnikov 2010, sec. 2). The distinction between a rational function and an expression representing it matters here: equivalent expressions can impose different conditions on their intermediate inverses. Our operational formulation retains the original expression throughout. For division-free computation, Nisan’s coefficient-matrix characterization made rank a central tool in noncommutative branching-program complexity (Nisan 1991). Raz and Shpilka gave deterministic polynomial-time identity testing with access to a formula or branching program (Raz and Shpilka 2005). Bogdanov and Wee developed randomized black-box matrix evaluation for bounded-degree noncommutative polynomials (Bogdanov and Wee 2005), and Forbes and Shpilka constructed deterministic quasipolynomial-size matrix hitting sets for noncommutative algebraic branching programs, a model including division-free formulas (Forbes and Shpilka 2013). For computation with division, Hrubeš and Wigderson developed the rational-formula model and its reduction to linear-matrix singularity testing (Hrubeš and Wigderson 2015). Their inverse-matrix realizations and tests for the domains of gate subformulas are direct predecessors of our certificate construction. Deterministic polynomial-time algorithms with access to the input formula followed from operator scaling and constructive noncommutative-rank computation (Garg et al. 2016, 2020; Ivanyos et al. 2018). These algorithms use the given coefficients, with their encoding lengths included in the bit model. Derksen and Makam established polynomial bounds on the dimensions needed for an admissible rational formula to have a defined evaluation, and derived randomized polynomial-time rational identity testing (Derksen and Makam 2017, sec. 6). Small witnesses and algorithms that depend on the input coefficients leave open the construction of a universal deterministic list from size bounds alone. Arvind, Chatterjee, and Mukhopadhyay obtained deterministic quasipolynomial-size hitting sets for rational formulas of inversion height two (Arvind et al. 2022, Theorem 1.1). Their subsequent general result handles unrestricted inverse nesting with quasipolynomial-size rational matrix hitting sets (Arvind et al. 2026); the quantitative bounds used in this comparison are Theorem 2, Corollary 3, and the paragraph following Remark 52 of the specified preprint version (Arvind et al. 2025). Thus rational matrix outputs and arbitrary inverse nesting already occur in the preceding literature. Invertible evaluations are also used in the division-algebra methods of these works (Arvind et al. 2022, 2025). Their general treatment states a depth reduction that preserves the input formula’s evaluation domain (Arvind et al. 2025, Fact 1). Theorem 1 gives polynomial bounds on construction time, total binary output length, and matrix dimension. Its complexity bound concerns generation of the list; the cost of evaluating an unknown formula with arbitrarily large rational constants is not included. The result resolves, over \(\mathbb Q\), the explicit polynomial-size hitting-set problem for this formula model, and gives the polynomial matrix dimension asked for in the conclusion of Arvind et al. (2025). The proof of Theorem 1 below establishes all the algebraic and algorithmic ingredients it uses. The proof also draws on established methods. The multiplicity argument for explicit subspace designs of Guruswami and Kopparty (Guruswami and Kopparty 2016), and the connection between subspace designs, rank condensers, and dimension expansion studied by Forbes and Guruswami (Forbes and Guruswami 2015), provide context for our construction. The underlying Wronskian calculation is classical (Bostan and Dumas 2010). The common-subspace obstruction to invertibility belongs to noncommutative-rank theory (Fortin and Reutenauer 2004), while cyclic division algebras and rank divisibility underlie the regularity methods of Ivanyos, Qiao, and Subrahmanyam (Ivanyos et al. 2017, 2018). We prove the precise expansion, deformation, and domain statements needed here, without importing the stronger general algorithms from those works. The construction and its logicWrite \(\mathop{\mathrm{Mat}}_q(F)\) for the \(q\) by \(q\) matrices over a field \(F\). The bridge from formula evaluation to linear algebra is an affine linear pencil, a matrix \[L(x)=A_0+\sum_{i=1}^n A_ix_i,\qquad A_i\in\mathop{\mathrm{Mat}}_q(\mathbb Q),\] of order \(q\). Its evaluation at matrices \(X_i\in\mathop{\mathrm{Mat}}_e(E)\) over an extension field \(E/\mathbb Q\) is \(A_0\otimes I_e+\sum_iA_i\otimes X_i\). Call the pencil feasible if one such evaluation is invertible. Tensor products and ranks are taken over the indicated field. A size-\(s\) formula gives at most \(s+1\) pencils of order at most \(B=2s+1\). Their simultaneous invertibility certifies that every inverse occurrence in the original tree is defined and that the final value is invertible. A nonzero admissible formula has a matrix evaluation over an extension field satisfying all these conditions. Section 4 proves this reduction, including the exact conditions at the inverse gates. The construction therefore seeks a universal rational list on which each such finite family of feasible pencils is simultaneously invertible. Two obstacles remain: obtaining full rank at matrices independent of the pencil coefficients, and keeping all conditions valid when the parameters become rational numbers. The proof handles them in the following order.
The witnesses, subspaces, and formula-specific determinant products in this proof certify the construction. None is computed by \(G\). In particular, the dimension of an initial witness for a formula has no effect on the generator’s resource bounds. The construction also hits every feasible rational affine pencil of bounded order; see Corollary 13. In particular, it answers the rational-coefficient version of the black-box Singular construction question for homogeneous pencils posed by Garg, Gurvits, Oliveira, and Wigderson (Garg et al. 2020, sec. 6, p. 280). Section 6 then treats rectangular affine pencils. Their noncommutative rank is their rank over the free skew field. Corollary 15 constructs a universal nonadaptive list whose normalized evaluation ranks recover this rank for every rectangular rational affine pencil with prescribed row, column, and variable counts. It permits exact matrix-value or ordinary-rank responses and accounts for their processing costs. Rectangular tests from subspace expansionFix the variable and formula-size bounds \(n,s\geq1\). We construct rectangular matrices \(T_0,\ldots,T_n\) such that \(\sum_{i=0}^n A_i\otimes T_i\) is injective whenever \(A_0+\sum_{i=1}^n A_i x_i\) is a feasible affine pencil of order at most \(2s+1\). The construction uses an indeterminate \(t\); no specialization of a formal Laurent series will be needed. Set \[ \begin{gathered} w=n+1,\qquad B=2s+1,\qquad \Delta=2w^3B,\\ M=\min\{2^a:a\in\mathbb Z_{\geq0},\ 2^a>B\Delta\}, \qquad N=M-\Delta. \end{gathered} \tag{1}\] The bound \(B\) will accommodate all certificate pencils in Proposition 10. The padding width \(\Delta\) provides the expansion margin, while \(M>B\Delta\) makes the eventual rank deficit smaller than one block. These choices give \(1\leq N<M\leq2B\Delta\). For a field \(K\) and an integer \(d\geq 1\), let \[\mathcal P_d(K)=\{f\in K[z]:\deg f<d\},\] with its monomial basis. Put \(F=\mathbb Q((t))\) and \(\mathcal O=\mathbb Q[[t]]\). For \(0\leq i\leq n\), define an \(F\)-linear map \(T_i\colon\mathcal P_N(F)\longrightarrow\mathcal P_M(F)\) by \[ f=\sum_{a=0}^{N-1}c_{ia}(f)(z-i)^a, \qquad T_i f=\sum_{a=0}^{N-1}c_{ia}(f)t^a(z-i)^{M-1-a}. \tag{2}\] The exponents in the output are nonnegative and distinct. Since each \(t^a\) is nonzero in \(F\), every \(T_i\) is injective. Its matrix in the monomial bases has entries in \(\mathbb Z[t]\). More explicitly, its column corresponding to \(z^b\), for \(0\leq b<N\), is the coefficient vector of \[ T_i(z^b)=\sum_{a=0}^{b}\binom{b}{a}i^{b-a}t^a(z-i)^{M-1-a}. \tag{3}\] Thus all its entries have \(t\)-degree at most \(N-1\). Let \(R_i(t)\) be the \(M\times M\) matrix obtained by appending \(M-N\) zero columns to \(T_i\). The conclusion of this section is the following proposition. Proposition 2 (Rectangular rank bound). Let \(1\leq q\leq B\) and \(A_0,\ldots,A_n\in\mathop{\mathrm{Mat}}_q(\mathbb Q)\). Suppose that, for some extension field \(E/\mathbb Q\), some integer \(e\geq1\), and some \(X_1,\ldots,X_n\in\mathop{\mathrm{Mat}}_e(E)\), the matrix \[A_0\otimes I_e+\sum_{i=1}^n A_i\otimes X_i\] is invertible. Then \(\sum_{i=0}^n A_i\otimes T_i\) is injective over \(F\), and \[ \mathop{\mathrm{rank}}_{\mathbb Q(t)}\left(\sum_{i=0}^n A_i\otimes R_i(t)\right) \geq qN>(q-1)M. \tag{4}\] We prove the proposition by showing that the maps \(T_i\) jointly expand every nonzero subspace of dimension at most \(B\). Two elementary facts will control the vanishing orders of their leading coefficients. The ordinary-Wronskian multiplicity method used in the subspace designs of Guruswami and Kopparty (Guruswami and Kopparty 2016, sec. 5.1 of the preprint) is a predecessor of this argument. Their construction bounds intersections with multiplicity subspaces; here Taylor reversal relates the vanishing sequences of the input and image spaces. Forbes and Guruswami (Forbes and Guruswami 2015) explain broader connections among subspace designs, rank condensers, and dimension expansion. The lossless and unbalanced dimension expanders of Guruswami, Resch, and Xing (Guruswami et al. 2018) provided a comparison for the required small-subspace expansion parameters during development. Their linearized-polynomial construction is not used here. We prove the order estimate and the rectangular expansion statement directly for the maps above. Vanishing orders and integral reductionLet \(V\subseteq\mathcal P_d(\mathbb Q)\) have dimension \(h\geq1\). Row reduction of Taylor coefficient vectors about \(z=i\) gives a basis with distinct vanishing orders \[0\leq d_{i1}<\cdots<d_{ih}<d.\] These orders describe the entire vanishing filtration: for every integer \(r\geq0\), \[ \dim_{\mathbb Q}\{f\in V:(z-i)^r\text{ divides }f\} =\#\{j:d_{ij}\geq r\}. \tag{5}\] Indeed, in a nonzero linear combination of the echelon basis, the first basis vector with a nonzero coefficient supplies its lowest Taylor term. The leading-term Wronskian computation in the following lemma is classical; the echelon-basis and Vandermonde argument is also presented by Bostan and Dumas (Bostan and Dumas 2010, Lemmas 1–3). Lemma 3 (Wronskian order bound). With the notation above, at the \(w=n+1\) points \(0,\ldots,n\) one has \[ \sum_{i=0}^n\sum_{j=1}^h d_{ij} \leq h(d-1)+w\binom{h}{2}. \tag{6}\] Proof. For a basis \(f_1,\ldots,f_h\) of \(V\), consider its Wronskian \[\mathcal W(z)=\det\bigl(f_j^{(r)}(z)\bigr)_{ 0\leq r<h,\,1\leq j\leq h}.\] Changing the basis multiplies \(\mathcal W\) by a nonzero rational constant. At a fixed point \(i\), use the echelon basis and write \(f_j=\alpha_j(z-i)^{d_{ij}}+\) higher powers, where \(\alpha_j\neq0\). The contribution of these leading terms to the determinant is \[\left(\prod_{j=1}^h\alpha_j\right) \det\bigl((d_{ij})_r\bigr)_{ 0\leq r<h,\,1\leq j\leq h} (z-i)^{\sum_jd_{ij}-\binom h2},\] where \((X)_r=X(X-1)\cdots(X-r+1)\) and \((X)_0=1\). Because these are monic polynomials of successive degrees, the displayed coefficient determinant is the Vandermonde \(\prod_{a<b}(d_{ib}-d_{ia})\), which is nonzero. Terms using a higher power from any \(f_j\) have strictly larger total exponent, or vanish on differentiation. The displayed exponent is nonnegative because the \(d_{ij}\) are distinct nonnegative integers. Consequently \[\mathop{\mathrm{ord}}_{z=i}\mathcal W =\sum_{j=1}^h d_{ij}-\binom h2,\] and in particular \(\mathcal W\) is not the zero polynomial. Each entry in its determinant has degree at most \(d-1\), so \(\deg\mathcal W\leq h(d-1)\). The sum of its vanishing orders at the distinct points \(0,\ldots,n\) is at most its degree. This gives (6). ◻ For a subspace \(U\subseteq F^D\), define its reduction by \[\overline U =\{u\bmod t:u\in U\cap\mathcal O^D\}\subseteq\mathbb Q^D.\] It is important here to use all integral vectors of the subspace, not merely the reductions of an arbitrarily chosen basis. Lemma 4 (Integral bases of Laurent-series subspaces). Every \(k\)-dimensional subspace \(U\subseteq F^D\) has a basis \(u_1,\ldots,u_k\in\mathcal O^D\) whose reductions are linearly independent. For such a basis, \[ U\cap\mathcal O^D=\bigoplus_{j=1}^k\mathcal O u_j, \qquad \dim_{\mathbb Q}\overline U=k. \tag{7}\] Proof. We first construct the basis by induction on \(k\), the case \(k=0\) being immediate. Multiply a nonzero vector of \(U\) by a power of \(t\) so that all its coordinates are integral and some coordinate is a unit. Call this vector \(u_1\) and its unit coordinate \(c\). The subspace of \(U\) whose \(c\)-th coordinate is zero has dimension \(k-1\). By induction it has an integral basis with independent reductions. All those reductions have zero \(c\)-th coordinate, whereas the reduction of \(u_1\) does not. Together they are therefore independent and form a basis of \(U\) over \(F\). Some \(k\times k\) coordinate minor of the resulting basis matrix is a unit in \(\mathcal O\). If an \(F\)-linear combination of its columns is integral, restriction to those coordinates and inversion of that minor show that all its coefficients belong to \(\mathcal O\). This proves the first assertion of (7); reducing its coefficients modulo \(t\) proves the second. ◻ For a nonzero vector \(f\) with Laurent-series coordinates, let \(\nu_t(f)\) denote the minimum of their \(t\)-valuations. Its leading reduction is the nonzero vector \(t^{-\nu_t(f)}f\bmod t\). Any invertible coordinate change over \(\mathbb Q\) preserves both the integral lattice and this minimum valuation: the change-of-basis matrix and its inverse both have entries in \(\mathcal O\). In particular, this applies to conversion between monomial and Taylor coordinates. All these statements concern formal series and require no convergence assumption. Expansion of every small subspaceFor an integral input having a unit Taylor coefficient with index \(a\leq A\), the leading reduction of its image uses only indices \(a\leq A\); reversal turns these into output orders at least \(M-1-A\). The Wronskian bound then rules out too small a common image space. The proof below applies this observation to a suitable subspace for each vanishing order. Lemma 5 (Small-subspace expansion). For every \(k\)-dimensional subspace \(U\subseteq\mathcal P_N(F)\) with \(1\leq k\leq B\), \[ \dim_F\left(\sum_{i=0}^n T_iU\right)>(w-1)k. \tag{8}\] Proof. Put \(W=\sum_{i=0}^nT_iU\) and \(\ell=\dim_FW\). Since \(T_0\) is injective, \(\ell\geq k\). By Lemma 4, \(\overline U\subseteq\mathcal P_N(\mathbb Q)\) has dimension \(k\) and \(\overline W\subseteq\mathcal P_M(\mathbb Q)\) has dimension \(\ell\). Write their increasing vanishing orders at \(i\) as \[a_{i1}<\cdots<a_{ik}, \qquad b_{i1}<\cdots<b_{i\ell}.\] We claim that, for every \(i\) and every \(1\leq j\leq k\), \[ b_{i,\ell-j+1}\geq M-1-a_{ij}. \tag{9}\] Fix \(i,j\) and set \(A=a_{ij}\). Projection of \(\overline U\) onto its Taylor coefficients of orders \(0,\ldots,A\) has rank \(j\). Choose \(j\) vectors in \(\overline U\) whose projections are independent, lift them to integral vectors of \(U\), and let \(U'\) be their \(F\)-span. Their reductions are independent, so Lemma 4 shows that these reductions form a basis of \(\overline{U'}\). The chosen Taylor projection is therefore injective on \(\overline{U'}\). Take a nonzero \(f\in U'\) and multiply it by a power of \(t\) so that \(\nu_t(f)=0\). All its Taylor coefficients \(c_{ia}(f)\) are integral. Because its nonzero reduction has a nonzero low Taylor projection, at least one coefficient with \(a\leq A\) is a unit. With the convention \(\nu_t(0)=+\infty\), put \[m=\min_{0\leq a<N}\bigl(\nu_t(c_{ia}(f))+a\bigr).\] Then \(m\leq A\), whereas for every \(a>A\) one has \(\nu_t(c_{ia}(f))+a\geq a>A\geq m\). Thus the leading reduction of \(T_i f\) uses only output powers \((z-i)^{M-1-a}\) with \(a\leq A\). These powers are independent, so their leading coefficients cannot all cancel. Since Taylor coordinate changes preserve minimum valuation, \(m\) is also the minimum valuation of the output in monomial coordinates. Its leading reduction consequently vanishes at \(i\) to order at least \(M-1-A\). Figure 1 illustrates this reversal. This conclusion controls the whole reduction \(\overline{T_iU'}\). Indeed, every nonzero \(v\in T_iU'\) has a preimage \(f\in U'\). Normalizing \(f\) multiplies \(v\) by the same power of \(t\), so the leading reduction of \(v\) is exactly the leading reduction already considered. An integral \(v\) reduces either to this leading reduction or to zero. We have not assumed that \(T_i(U'\cap\mathcal O^N)\) is the full integral lattice of \(T_iU'\). By injectivity of \(T_i\) and Lemma 4, \(\overline{T_iU'}\) has dimension \(j\). It lies in \(\overline W\) and in its vanishing filtration of order at least \(M-1-A\). Formula (5) now gives (9). For each fixed \(i\), summing (9) over \(j=1,\ldots,k\) uses the largest \(k\) distinct orders of the same space \(\overline W\). The remaining orders are nonnegative. Although the auxiliary spaces \(U'\) may depend on \(j\), these are bounds on the fixed filtration of \(\overline W\) and can therefore be summed. Applying Lemma 3 to both reduced spaces gives \[\begin{align*} \ell(M-1)+w\binom\ell2 &\geq\sum_{i=0}^n\sum_{h=1}^{\ell}b_{ih}\\ &\geq wk(M-1)-\sum_{i=0}^n\sum_{j=1}^k a_{ij}\\ &\geq wk(M-1)-k(N-1)-w\binom k2\\ &=(w-1)k(M-1)+k\Delta-w\binom k2. \end{align*}\] If \(\ell\leq(w-1)k\), this implies \[k\Delta\leq w\left(\binom k2+\binom\ell2\right) \leq\frac w2\bigl(1+(w-1)^2\bigr)k^2 \leq\frac{w^3}{2}Bk <2w^3Bk=k\Delta,\] a contradiction. This proves the strict expansion bound. ◻ From expansion to the rank boundThe proof uses the standard shrunk-subspace obstruction: if every coefficient matrix sends a common subspace into one of smaller dimension, no matrix substitution can be invertible. This is the elementary obstruction direction of the noncommutative-rank characterization of Fortin and Reutenauer (Fortin and Reutenauer 2004, sec. 2, Theorem 1); see also Ivanyos et al. (2018, Definition 1.1 and Section 5.1). We derive the obstruction from expansion and give the required extension-field comparison explicitly. Proof of Proposition 2. Suppose that \(\sum_iA_i\otimes T_i\) has a nonzero kernel vector, written as \(q\) components \(f_1,\ldots,f_q\in\mathcal P_N(F)\). Let \(U\) be their span, of dimension \(1\leq k\leq q\leq B\), and choose a basis \(u_1,\ldots,u_k\) of \(U\). Write \[f_\alpha=\sum_{j=1}^k P_{\alpha j}u_j, \qquad P\in\mathop{\mathrm{Mat}}_{q\times k}(F).\] Since the \(f_\alpha\) span \(U\), the matrix \(P\) has rank \(k\). Each row of the concatenated matrix \[C=[\,A_0P\ \ A_1P\ \ \cdots\ \ A_nP\,]\] is a relation among the \(wk\) vectors \(T_i u_j\): this is exactly the corresponding component of the kernel equation. Those vectors span \(\sum_iT_iU\), whose dimension is greater than \((w-1)k\) by Lemma 5. Their relation space therefore has dimension less than \(k\), and hence \(\mathop{\mathrm{rank}}C<k\). Let \(V\) be the column space of \(P\) and \(V_-\) the column space of \(C\), both in \(F^q\). Equality of row rank and column rank yields \[ \dim_F V=k,\qquad \dim_FV_-<k, \qquad A_iV\subseteq V_-\quad(0\leq i\leq n). \tag{10}\] Thus every coefficient matrix sends the same input subspace into a strictly smaller common output subspace. To compare this obstruction with the given witness over \(E\), introduce a fresh formal variable \(\tau\) and work in \(J=E((\tau))\). Embed \(E\) as the constant series and embed \(F\) by \[\sum_m q_m t^m\longmapsto\sum_m q_m\tau^m.\] These embeddings agree on \(\mathbb Q\), which contains all the \(A_i\). A transcendental element already in \(E\), even one named \(t\), remains a coefficient and is not identified with \(\tau\). The embeddings preserve matrix ranks, since nonzero minors stay nonzero. Denote the extended subspaces in (10) by \(V_J\) and \((V_-)_J\). Putting \(X_0=I_e\), the witness evaluation maps \[\left(\sum_{i=0}^n A_i\otimes X_i\right) (V_J\otimes_J J^e) \subseteq (V_-)_J\otimes_J J^e.\] The domain on the left has dimension \(ke\), and the space on the right has dimension strictly less than \(ke\). This contradicts invertibility of the witness matrix, whose inverse over \(E\) remains an inverse over \(J\). The rectangular evaluation is therefore injective. In the padded evaluation \(\sum_iA_i\otimes R_i(t)\), selecting the first \(N\) columns within each of the \(q\) blocks recovers the rectangular evaluation. Its rank over \(F\) is at least \(qN\). The corresponding nonzero maximal minor belongs to \(\mathbb Q[t]\), so it is also nonzero over \(\mathbb Q(t)\). In particular, no coefficient of the formal subspaces or their bases has to be specialized. Finally, \[qN-(q-1)M=M-q\Delta\geq M-B\Delta>0,\] which proves (4). ◻ Deformation inside a division algebraThe rank bound from Proposition 2 is close to full rank. We now deform the test matrices so that every possible rank is a multiple of their block size. The same deformation will also turn a defined nonzero value of a rational formula into an invertible value over an extension field. The construction is a form of the generic cyclic, or symbol, division algebra. Explicit split representations and block-rank divisibility appear in the constructive regularity methods of Ivanyos, Qiao, and Subrahmanyam (Ivanyos et al. 2017, sec. 4.3 and 5.2 of the preprint); see also their later regularity algorithm (Ivanyos et al. 2018, sec. 4). Division-algebra witnesses and invertible hits are also used in rational-formula black-box testing by Arvind, Chatterjee, and Mukhopadhyay (Arvind et al. 2022, 2025). Here the needed deformation and rank-divisibility statement have a direct proof using two explicit matrices. This matrix embedding is distinct from the rational multiplication representation in Section 5. Lemma 6 (A matrix lift into a division algebra). Let \(d\geq 1\), let \(K\) be a field of characteristic zero, and let \(\omega\in K\) be a primitive \(d\)th root of unity. On the standard basis \(e_0,\ldots,e_{d-1}\) of \(K^d\), with subscripts taken modulo \(d\), set \[De_j=\omega^j e_j, \qquad Se_j=e_{j+1}.\] For algebraically independent indeterminates \(p,r\) over \(K\), there is a division algebra \[\mathcal D\subseteq\mathop{\mathrm{Mat}}_d\bigl(K(p,r)\bigr)\] containing, for every \(R\in\mathop{\mathrm{Mat}}_d(K)\), the matrix \[ R^*=\sum_{a,b=0}^{d-1}c_{ab}p^a r^bD^aS^b, \qquad c_{ab}=\frac1d\sum_{j=0}^{d-1}\omega^{-aj}R_{j,j-b}. \tag{11}\] The matrix \(R^*\) specializes to \(R\) at \(p=r=1\). Moreover, \(\mathcal D\) has dimension \(d^2\) over the central subfield \(K(p^d,r^d)\), and every matrix with blocks in \(\mathcal D\) has rank over \(K(p,r)\) divisible by \(d\). Proof. For each \(b\), the only potentially nonzero entries of \(D^aS^b\) have the form \[(D^aS^b)_{j,j-b}=\omega^{aj}.\] The identity \[\sum_{j=0}^{d-1}\omega^{(a-a')j} =\begin{cases}d,&a=a',\\0,&a\ne a',\end{cases} \qquad 0\leq a,a'<d,\] therefore gives Fourier inversion separately on each of these cyclic diagonals. In particular, the \(d^2\) matrices \(D^aS^b\) form a basis of \(\mathop{\mathrm{Mat}}_d(K)\), with the coefficients displayed in (11). This proves the asserted specialization. Put \(X=pD\) and \(Y=rS\), and let \(\mathcal A\) be the unital \(K\)-algebra they generate inside \(\mathop{\mathrm{Mat}}_d(K(p,r))\). Since \(DS=\omega SD\), we have \[ XY=\omega YX, \qquad (X^iY^j)(X^kY^\ell) =\omega^{-jk}X^{i+k}Y^{j+\ell} \quad(i,j,k,\ell\geq0). \tag{12}\] Thus the ordered monomials \(X^iY^j\) span \(\mathcal A\) over \(K\). They are also linearly independent: in any finite relation, the coefficient of the scalar monomial \(p^i r^j\) is the corresponding scalar coefficient times the invertible constant matrix \(D^iS^j\). Algebraic independence of \(p,r\) forces each such coefficient to vanish. Order the exponent pairs lexicographically. For two nonzero elements of \(\mathcal A\), the largest exponent in their product is the sum of their largest exponents, by (12). Its coefficient is the product of two nonzero coefficients and a nonzero power of \(\omega\). Hence \(\mathcal A\) has no zero divisors. The elements \[X^d=p^dI_d, \qquad Y^d=r^dI_d\] are scalar matrices. We may consequently invert every nonzero element of the central polynomial ring \(K[p^d,r^d]I_d\) and obtain a subalgebra \(\mathcal D\) of \(\mathop{\mathrm{Mat}}_d(K(p,r))\). Every element of this localization can be written \(a/z\) with \(a\in\mathcal A\) and \(0\ne z\in K[p^d,r^d]\). Products of nonzero such fractions remain nonzero, so \(\mathcal D\) still has no zero divisors. Let \(F_0=K(p^d,r^d)\). Reducing the exponents of \(X,Y\) modulo \(d\) shows that \[ \{X^aY^b:0\leq a,b<d\} \tag{13}\] spans \(\mathcal D\) over \(F_0\). To see independence over \(F_0\), clear a common denominator in a proposed relation. Expanding the resulting coefficients in \(K[p^d,r^d]\) gives a relation among the ordered monomials over \(K\); distinct pairs \((a,b)\) in (13) have distinct exponent residues modulo \(d\). All its coefficients must therefore vanish. It follows that \(\dim_{F_0}\mathcal D=d^2\). For a nonzero \(z\in\mathcal D\), left and right multiplication by \(z\) are injective \(F_0\)-linear maps from this finite-dimensional space to itself, and hence are surjective. There exist \(b,c\in\mathcal D\) with \(zb=1\) and \(cz=1\), and associativity gives \(c=c(zb)=(cz)b=b\). Thus \(z\) has a two-sided inverse in \(\mathcal D\). This proves that \(\mathcal D\) is a division algebra. Since \(p^ar^bD^aS^b=X^aY^b\), every lift in (11) belongs already to \(\mathcal A\). Finally, consider an arbitrary block matrix with entries in \(\mathcal D\). If it has a nonzero block, move that block to the first position by block row and column permutations. Writing the result as \[\begin{pmatrix}a&b\\c&E\end{pmatrix},\qquad a\ne0,\] block elimination gives \[\begin{pmatrix}1&0\\-c&I\end{pmatrix} \begin{pmatrix}a^{-1}&0\\0&I\end{pmatrix} \begin{pmatrix}a&b\\c&E\end{pmatrix} \begin{pmatrix}1&-a^{-1}b\\0&I\end{pmatrix} = \begin{pmatrix}1&0\\0&E-ca^{-1}b\end{pmatrix}.\] All blocks and all these invertible operations remain in \(\mathcal D\). Iterating reduces the matrix to identity blocks and zero blocks. Each identity block is an ordinary \(d\times d\) identity matrix, and the operations are invertible over \(K(p,r)\) as well. Its ordinary rank is therefore \(d\) times the number of identity blocks, as required. ◻ The scalar fields in this lemma have different roles. Finite dimensionality and the division property are proved over the central field \(K(p^d,r^d)\). Ordinary matrix rank is measured over the larger field \(K(p,r)\) in the given embedding. The elimination proof uses only operations in \(\mathcal D\); it does not enlarge that algebra by arbitrary scalars from \(K(p,r)\). Proposition 7 (Full-rank deformed pencils). Fix a primitive \(M\)th root of unity \(\omega\in\mathbb C\), and lift the padded matrices \(R_0(t),\ldots,R_n(t)\) by Lemma 6 with \(d=M\) and \(K=\mathbb Q(\omega)(t)\). Let \[L(x)=A_0+\sum_{i=1}^n A_i x_i, \qquad A_i\in\mathop{\mathrm{Mat}}_q(\mathbb Q),\qquad 1\leq q\leq B,\] be an affine pencil admitting an invertible matrix evaluation over some extension field of \(\mathbb Q\). Then \[ P_{L,\omega}(t,p,r) :=\det\!\left(\sum_{i=0}^n A_i\otimes R_i^*(t,p,r)\right) \ne0. \tag{14}\] This is a polynomial in \(\mathbb Q(\omega)[t,p,r]\) of total degree at most \(3BM^2\). In particular \(\det R_0^*\) is a nonzero polynomial. Proof. Proposition 2 gives \[\mathop{\mathrm{rank}}_{\mathbb Q(t)}\left(\sum_{i=0}^n A_i\otimes R_i(t)\right) \geq qN>(q-1)M.\] Choose a nonzero minor of order greater than \((q-1)M\). It remains nonzero over \(\mathbb Q(\omega)(t)\). The corresponding minor of the lifted matrix specializes to it at \(p=r=1\), so the lifted minor is not identically zero. The lifted matrix consequently has rank greater than \((q-1)M\) over \(\mathbb Q(\omega)(t,p,r)\). Its \(M\times M\) blocks belong to the division algebra of Lemma 6: each is a rational linear combination of the \(R_i^*\). Its rank is thus a multiple of \(M\). As the whole matrix has order \(qM\), its rank must be \(qM\), proving (14). The entries of \(R_i(t)\) lie in \(\mathbb Z[t]\) and have degree at most \(N-1\). The Fourier coefficients in (11) introduce only the constant denominator \(M\), while the factors \(p^ar^b\) have total degree at most \(2(M-1)\). Every lifted entry is therefore a polynomial of total degree at most \(N-1+2(M-1)<3M\). A determinant of order \(qM\) has total degree at most \(3qM^2\leq3BM^2\). For the last assertion, apply the result to the order-one constant pencil \(L=1\), whose coefficient \(A_0\) is \(1\) and whose other coefficients vanish. Its determinant in (14) is exactly \(\det R_0^*\). ◻ At any specialization at which \(R_0^*\) is invertible, set \(X_i=(R_0^*)^{-1}R_i^*\) for \(1\leq i\leq n\). The identity \[ A_0\otimes I_M+\sum_{i=1}^n A_i\otimes X_i = \bigl(I_q\otimes(R_0^*)^{-1}\bigr) \left(\sum_{i=0}^n A_i\otimes R_i^*\right) \tag{15}\] shows that simultaneous nonvanishing of the determinant constraints in Proposition 7, including the constant-pencil constraint, makes the corresponding affine pencils invertible on this normalized tuple. The order of multiplication in (15) is part of the identity. Lemma 8 (An invertible witness for a nonzero formula). Every admissible nonzero rational formula over \(\mathbb Q\) has a defined evaluation at matrices over an extension field of \(\mathbb Q\) for which its value is invertible. Proof. By the definition of nonzero, there is a tuple \(W=(W_1,\ldots,W_n)\) of rational matrices of some common dimension \(d\geq1\) at which the given formula is defined and has nonzero value. Choose a primitive \(d\)th root \(\omega\), put \(K=\mathbb Q(\omega)\), and lift each \(W_i\) to \(W_i^*\) by Lemma 6. We first verify the domain of the actual formula tree independently of the division-algebra argument. Inside \(K(p,r)\) consider the commutative ring \[\mathcal O= \left\{\frac{f}{g}: f,g\in K[p,r],\ g(1,1)\ne0\right\}.\] Evaluation at \((1,1)\) is a ring homomorphism \(\varepsilon:\mathcal O\to K\). An element of \(\mathcal O\) whose image under \(\varepsilon\) is nonzero is a unit in \(\mathcal O\): if it is written \(f/g\), then \(f(1,1)\ne0\) and its inverse is \(g/f\). We claim, by induction up the original tree, that each subtree evaluated at the lifted inputs gives a matrix over \(\mathcal O\) whose image under \(\varepsilon\) is its value at \(W\). This holds for leaves by the specialization property of the lift, and is preserved by addition and ordered multiplication. At an inverse gate, let \(G\in\mathop{\mathrm{Mat}}_d(\mathcal O)\) be the already constructed value of the child. Since the original evaluation is defined, \(\varepsilon(G)\) is invertible. Consequently \[\varepsilon(\det G)=\det\varepsilon(G)\ne0,\] so \(\det G\) is a unit of \(\mathcal O\). The formula \[G^{-1}=\frac{\operatorname{adj}(G)}{\det G}\] then constructs its inverse in \(\mathop{\mathrm{Mat}}_d(\mathcal O)\) and gives the correct specialized inverse. This proves the claim at every inverse gate, regardless of its nesting depth. The lifted formula is therefore defined over \(K(p,r)\). Its final matrix is nonzero, because one of its entries specializes to a nonzero entry of the original final value. Now use the division algebra \(\mathcal D\) from Lemma 6. Every lifted input and every rational scalar constant belongs to \(\mathcal D\). A second induction shows that every intermediate value belongs to \(\mathcal D\): sums and products stay in it, and an operand at an inverse gate is already known to be invertible as an ambient matrix, hence is nonzero in \(\mathcal D\). Its inverse in \(\mathcal D\) equals its ordinary matrix inverse by uniqueness. The final nonzero value is thus a nonzero element of a division algebra, and is invertible as a matrix over \(K(p,r)\). ◻ Only those entries proved to lie in \(\mathcal O\) are specialized in this argument. No specialization map on the whole division algebra is needed. In particular, the inverse of the final value may have a pole at \((1,1)\) when the original nonzero value is singular; its invertibility is asserted only at the lifted tuple over the extension field. If \(d=1\), the lift leaves every input scalar unchanged, and a nonzero scalar final value is already invertible. The witness dimension \(d\) in Lemma 8 is purely existential and need not be bounded. The matrices used in the construction instead have the predetermined block size \(M\). Encoding a formula and its evaluation domainWe now turn the conditions imposed by a rational formula into finitely many affine-pencil invertibility conditions. We keep the original formula tree: an inverse gate must have an invertible operand even when its contribution later cancels or is multiplied by zero. Affine-matrix representations of free-field elements appear in Cohn and Reutenauer (Cohn and Reutenauer 1994, sec. 3.1). Linear realizations by block inverses and tests for the original domain appear in Hrubeš and Wigderson (Hrubeš and Wigderson 2015, Theorem 2.6, Section 6, and Proposition 7.1). Their domain criterion retains pencils for all gate subformulas. We give the recursions and the domain argument in full for the precise tree-size convention used here, and show why the inverse-node pencils together with one root augmentation suffice. The argument concerns the given tree and requires no domain-preserving balancing transformation. For a subtree \(h\), let \(|h|\) denote its number of vertices, let \(\lambda(h)\) denote its number of leaves, and let \(\iota(h)\) denote its number of inverse gates. Each occurrence of a subtree is treated separately. A pencil of order \(q\) has the form \[L(x)=A_0+\sum_{i=1}^n A_i x_i, \qquad A_0,\ldots,A_n\in\mathop{\mathrm{Mat}}_q(\mathbb Q).\] At a tuple \(X=(X_1,\ldots,X_n)\) of matrices of order \(d\) over a field extension of \(\mathbb Q\), its evaluation is \[L(X)=A_0\otimes I_d+\sum_{i=1}^n A_i\otimes X_i.\] When a constant row \(u\) or column \(v\) is used with such an evaluation, we write \(u\) and \(v\) for \(u\otimes I_d\) and \(v\otimes I_d\), respectively. Thus the expression \(uL(X)^{-1}v\) is a matrix of order \(d\). Lemma 9 (Affine realization of a subtree). For each subtree \(h\) there are an affine pencil \(L_h\) of order \(q_h\), a constant rational row \(u_h\) of length \(q_h\), and a constant rational column \(v_h\) of length \(q_h\), such that \[ q_h=2\lambda(h)+\iota(h)=|h|+1. \tag{16}\] At every matrix tuple over every field extension of \(\mathbb Q\) where the original subtree \(h\) is defined, \(L_h\) is invertible and \[ h=u_hL_h^{-1}v_h. \tag{17}\] Proof. Here are the constructions, followed by verification of the invariant. All zero blocks have the sizes prescribed by the adjacent blocks. Leaf. If \(h\) is a variable or a rational constant, set \[L_h=\begin{pmatrix}1&-h\\0&1\end{pmatrix}, \qquad u_h=\begin{pmatrix}1&0\end{pmatrix}, \qquad v_h=\begin{pmatrix}0\\1\end{pmatrix}.\] Addition. For \(h=f+g\), set \[L_h=\begin{pmatrix}L_f&0\\0&L_g\end{pmatrix}, \qquad u_h=\begin{pmatrix}u_f&u_g\end{pmatrix}, \qquad v_h=\begin{pmatrix}v_f\\v_g\end{pmatrix}.\] Ordered multiplication. For \(h=fg\), set \[L_h=\begin{pmatrix}L_f&-v_fu_g\\0&L_g\end{pmatrix}, \qquad u_h=\begin{pmatrix}u_f&0\end{pmatrix}, \qquad v_h=\begin{pmatrix}0\\v_g\end{pmatrix}.\] Inversion. For \(h=g^{-1}\), set \[L_h=\begin{pmatrix}L_g&v_g\\u_g&0\end{pmatrix}, \qquad u_h=\begin{pmatrix}0&-1\end{pmatrix}, \qquad v_h=\begin{pmatrix}0\\1\end{pmatrix},\] where the zero part of each selector has length \(q_g\). Equivalently, \(u_h=-e_{q_g+1}^{\mathsf T}\) and \(v_h=e_{q_g+1}\). The rows and columns just specified are constant. In particular, \(v_fu_g\) is a constant matrix, so every displayed pencil is affine in the original variables. No multiplication of variable entries is introduced into a pencil. Fix an evaluation tuple and prove the invariant by induction on the subtree. A leaf pencil has inverse \(\left(\begin{smallmatrix}I_d&h\\0&I_d\end{smallmatrix}\right)\), and its selectors give \(h\). At an addition gate, definedness of the gate implies definedness of both children. Their pencils are invertible by induction, and block-diagonal inversion gives the sum of the two represented values. At a multiplication gate, the same induction gives \[L_h^{-1}= \begin{pmatrix} L_f^{-1}&L_f^{-1}v_fu_gL_g^{-1}\\ 0&L_g^{-1} \end{pmatrix}.\] The selected block is consequently \[u_fL_f^{-1}v_fu_gL_g^{-1}v_g =(u_fL_f^{-1}v_f)(u_gL_g^{-1}v_g)=fg,\] with the required order of multiplication. At an inverse gate \(h=g^{-1}\), definedness means that \(g\) is defined and its value is invertible. By induction \(L_g\) is invertible and \(u_gL_g^{-1}v_g=g\). The block factorization \[ \begin{pmatrix}L_g&v_g\\u_g&0\end{pmatrix} = \begin{pmatrix}I&0\\u_gL_g^{-1}&I\end{pmatrix} \begin{pmatrix}L_g&0\\0&-g\end{pmatrix} \begin{pmatrix}I&L_g^{-1}v_g\\0&I\end{pmatrix} \tag{18}\] shows that \(L_h\) is invertible. The lower-right block of its inverse is \((-g)^{-1}=-g^{-1}\), so the negative row selector gives precisely \(g^{-1}\). This proves the invariant in all four cases. The orders are \(2\) at leaves, add at binary gates, and increase by one at inverse gates. Hence \(q_h=2\lambda(h)+\iota(h)\). A rooted tree whose internal vertices have one or two children has \(\lambda(h)-1\) binary vertices: counting edges both by vertices and by children gives this identity. Thus \[|h|=\lambda(h)+(\lambda(h)-1)+\iota(h) =2\lambda(h)+\iota(h)-1,\] which proves (16). ◻ For the root formula \(\Phi\), define its root augmentation by \[ J_\Phi= \begin{pmatrix}L_\Phi&v_\Phi\\u_\Phi&0\end{pmatrix}. \tag{19}\] This has the same block form as an inverse-node pencil, but no inverse gate is being added to the formula or counted in its size. Proposition 10 (Pencil certificates for the original formula tree). Let \(\Phi\) be a formula of size at most \(s\), and put \(B=2s+1\). Form the indexed collection \(\mathcal C_\Phi\) consisting of \(L_h\) for every inverse-node occurrence \(h\) of \(\Phi\), together with \(J_\Phi\). Then:
Adding the order-one constant pencil \(1\) for normalization gives at most \(s+2\) pencils, still of order at most \(B\), with the same simultaneous feasibility property in the third assertion. Proof. There are at most \(s\) inverse-node occurrences. By Lemma 9, each corresponding pencil has order \(|h|+1\le s+1\le B\). The augmentation has order \(|\Phi|+2\le s+2\le2s+1=B\), where the last inequality uses \(s\ge1\). This proves the first assertion. The extra constant pencil has order one and evaluates to an identity matrix at every tuple. For one implication in the second assertion, assume that \(\Phi\) is defined and its value is invertible. Each subtree is then defined, so Lemma 9 makes every inverse-node pencil invertible. The same lemma makes \(L_\Phi\) invertible and gives \(u_\Phi L_\Phi^{-1}v_\Phi=\Phi\). Applying factorization (18) at the root shows that \(J_\Phi\) is invertible, because its Schur complement is \(-\Phi\). Conversely, suppose all pencils in \(\mathcal C_\Phi\) are invertible. First establish that the original tree is defined, proceeding from the leaves toward the root. Leaves are always defined. At an addition or multiplication gate, both children have already been shown defined, so the gate is defined. At an inverse gate \(h=g^{-1}\), all gates in the child subtree have already been handled; in particular \(g\) is defined. Lemma 9 therefore makes \(L_g\) invertible and represents \(g\) by \(u_gL_g^{-1}v_g\). The pencil \(L_h\) is one of the assumed invertible pencils. The two outer factors in (18) are invertible, so the middle factor is invertible as well. It follows that \(g\) is invertible, which is exactly the condition needed for this inverse gate to be defined. This induction proves definedness of the entire original tree. It also explains why no separate constraint on the pencil of an ordinary subtree is needed: whenever that pencil is used, its invertibility already follows from the established definedness of its subtree. Now \(L_\Phi\) is invertible by the realization lemma. The assumed invertibility of \(J_\Phi\), whose Schur complement is \(-\Phi\), forces the final value \(\Phi\) to be invertible. This proves the reverse implication without simplifying the formula or enlarging its domain. Finally, if \(\Phi\) is admissible and nonzero, Lemma 8 supplies an evaluation over a field extension of \(\mathbb Q\) at which the original tree is defined and its value is invertible. The second assertion makes every pencil in \(\mathcal C_\Phi\) invertible at this one evaluation. The constant pencil \(1\) is invertible there as well. This proves the third assertion and the normalization statement. ◻ Remark 11 (Why every inverse occurrence is retained). Consider the scalar expression \[a=x^{-1},\qquad b=a^{-1},\qquad \Phi=b+1.\] It is undefined at \(x=0\), although its simplified rational function is \(x+1\). For the pencils above, direct computation gives \[\det L_a=-x,\qquad \det L_b=1,\qquad \det J_\Phi=-(x+1).\] Thus the outer inverse pencil and the root augmentation alone would accept \(x=0\). The retained inner inverse pencil \(L_a\) rejects it. Likewise, the formula \(1+0\cdot x^{-1}\) retains the requirement that \(x\) be invertible. The certificate collection is indexed by gates of the given tree, including gates in branches whose later contributions cancel. The witnesses and pencils in this section are used to prove the hitting property; the generator will receive only \(n,s\) and will not construct them from an unknown formula. The order and count bounds depend only on the number of vertices. They impose no restriction on inverse nesting or on the bit lengths of the rational leaf constants. A rational hitting list and its bit complexityProposition 7 supplies polynomial matrices \(R_i^*(t,p,r)\) for which \(\sum_i A_i\otimes R_i^*\) is invertible over \(\mathbb Q(\omega)(t,p,r)\) whenever the pencil \(A_0+\sum_{i=1}^n A_i x_i\) is feasible and has order at most \(B\). We now replace the root-of-unity coefficients and specialize the three parameters to obtain a single list of rational matrix tuples. The parameters \(w,B,\Delta,M,N\) retain their earlier definitions. To remove the root of unity, we represent multiplication in a finite-dimensional rational algebra. Over \(\mathbb C\) this representation is a direct sum of root evaluations, so our invertibility conditions must hold simultaneously at all roots. Set \[ \ell=\frac M2,\qquad D=M\ell=\frac{M^2}{2},\qquad H=1+3(s+2)BM^3, \qquad \mathcal R=\mathbb Q[\xi]/(\xi^\ell+1). \tag{20}\] Here and below \(\xi\) also denotes its residue class. In particular, \(\xi^\ell=-1\) and \(\xi^M=1\), so every integral power of \(\xi\), including a negative power, reduces to a signed member of the basis \(1,\xi,\ldots,\xi^{\ell-1}\). The rational representation and the generatorLet \(\Omega\) be the set of complex roots of \(X^\ell+1\). Since \(M\) is a power of two, these are the \(\ell\) distinct numbers \[\exp\!\left(\frac{2\pi\mathrm{i}(2j+1)}{M}\right), \qquad 0\le j<\ell.\] Every one is a primitive \(M\)th root of unity: its exponent \(2j+1\) is coprime to \(M\). Evaluation at these roots is an algebra isomorphism \[ \mathcal R\otimes_{\mathbb Q}\mathbb C \longrightarrow \prod_{\omega\in\Omega}\mathbb C, \qquad f\longmapsto \bigl(f(\omega)\bigr)_{\omega\in\Omega}. \tag{21}\] Indeed, a polynomial of degree less than \(\ell\) is uniquely determined by its values at \(\ell\) distinct points, and interpolation gives a polynomial with any prescribed values there. For \(a\in\mathcal R\), let \(\rho(a)\in\mathop{\mathrm{Mat}}_\ell(\mathbb Q)\) be the matrix of multiplication by \(a\) in the power basis. This is a unital algebra homomorphism. It is computed using only rational arithmetic and the relation \(\xi^\ell=-1\). To make its splitting explicit, let \(V\) be the evaluation matrix whose \((\omega,j)\) entry is \(\omega^j\), for \(\omega\in\Omega\) and \(0\le j<\ell\). Interpolation says that \(V\) is invertible, and \[ V\rho(a)V^{-1} =\operatorname{diag}\bigl(a(\omega):\omega\in\Omega\bigr). \tag{22}\] If \(Q\in\mathop{\mathrm{Mat}}_d(\mathcal R)\), write \(\rho_d(Q)\) for the rational \(d\ell\) by \(d\ell\) matrix obtained by applying \(\rho\) to every entry. First changing basis by \(I_d\otimes V\), and then reordering the basis to group together coordinates belonging to the same root, gives \[ \rho_d(Q)\sim_{\mathbb C} \bigoplus_{\omega\in\Omega}Q(\omega). \tag{23}\] In particular, \(\rho_d(Q)\) is invertible if and only if every \(Q(\omega)\) is invertible. These complex basis changes are used to prove this assertion; the generator will not compute them. We use the lift of Lemma 6, now with \(\xi\) in place of a primitive root. For clarity, it can be computed directly over \(\mathcal R\). Number the coordinates from \(0\) to \(M-1\) and set \[D_\xi e_j=\xi^j e_j,\qquad Se_j=e_{j+1},\] with indices taken modulo \(M\). For \(0\le i\le n\) define \[\begin{align*} \widetilde c_{i,a,b}(t) &=\frac1M\sum_{j=0}^{M-1} \xi^{-aj}(R_i(t))_{j,j-b}, &&0\le a,b<M,\\ \widetilde R_i(t,p,r) &=\sum_{a,b=0}^{M-1} \widetilde c_{i,a,b}(t)p^a r^bD_\xi^aS^b \in\mathop{\mathrm{Mat}}_M\bigl(\mathcal R[t,p,r]\bigr). \tag{24}\end{align*}\] Evaluating its coefficients at \(\xi=\omega\) gives exactly the lifted matrix \(R_i^{*,\omega}(t,p,r)\) from Proposition 7. In particular, no choice of a complex root is needed to compute (24). The generator, on input \(1^n,1^s\), performs the following finite computation in a fixed order.
Denote the resulting list by \(\mathcal H_{n,s}\). Repetitions are harmless. Every tuple has the same positive matrix dimension \(D\). The hitting propertyProposition 12. Every nonzero admissible formula of size at most \(s\) has a defined, invertible evaluation at a tuple in \(\mathcal H_{n,s}\). Proof. Fix one such formula \(\Phi\). By Proposition 10, there is a family of at most \(s+1\) affine linear pencils over \(\mathbb Q\), each of order at most \(B\), whose simultaneous invertibility ensures that the original formula tree is defined and has an invertible value. These are the pencils of all inverse-node occurrences and the root augmentation. Each has an invertible evaluation over an extension field. Add the order-one constant pencil \(1\) to this family, and call the resulting family \(\widehat{\mathcal C}_\Phi\). Thus \(|\widehat{\mathcal C}_\Phi|\le s+2\). For \(L=A_0+\sum_{i=1}^n A_i x_i\in\widehat{\mathcal C}_\Phi\) and \(\omega\in\Omega\), recall from Proposition 7 that \[P_{L,\omega}(t,p,r) =\det\!\left(\sum_{i=0}^n A_i\otimes R_i^{*,\omega}(t,p,r)\right).\] Proposition 7 says that each of these is a nonzero polynomial of total degree at most \(3BM^2\). Regard all of them as polynomials in the one integral domain \(\mathbb C[t,p,r]\) and form \[P_\Phi(t,p,r) =\prod_{L\in\widehat{\mathcal C}_\Phi} \prod_{\omega\in\Omega} P_{L,\omega}(t,p,r).\] This is a finite product of nonzero polynomials, and \[ \deg P_\Phi \le (s+2)\frac M2\,3BM^2 =\frac32(s+2)BM^3 <H. \tag{26}\] The extension field used to witness invertibility of a pencil is not part of this coefficient ring: the \(A_i\) are rational, and the displayed lift has coefficients in \(\mathbb Q(\omega)\). Thus there is no need to embed that witness field into \(\mathbb C\). A nonzero polynomial in three variables of total degree less than \(H\) cannot vanish on all of \(\{1,\ldots,H\}^3\). To see this, suppose it did. Fixing the last two coordinates gives a univariate polynomial of degree less than \(H\) with \(H\) roots, so every coefficient in the first variable vanishes on the two-dimensional grid. Repeating the same argument for the second and then the third variable makes every coefficient zero, a contradiction. Choose a triple at which \(P_\Phi\) is nonzero. At this triple every root evaluation of \(\widetilde R_0\) is invertible, by the factor corresponding to the constant pencil \(1\). Equation (23) therefore shows that \(Z_0\) is invertible, so the generator retains the triple. The same equation, applied to each raw pencil, shows that \[\sum_{i=0}^n A_i\otimes Z_i\] is invertible for every \(L\in\widehat{\mathcal C}_\Phi\). If \(L\) has order \(q\), left multiplication gives the exact identity \[ (I_q\otimes Z_0^{-1}) \left(\sum_{i=0}^n A_i\otimes Z_i\right) =A_0\otimes I_D+ \sum_{i=1}^n A_i\otimes(Z_0^{-1}Z_i). \tag{27}\] Hence all the certificate pencils are invertible on the rational tuple (25). The preceding splitting proved invertibility after extending scalars to \(\mathbb C\). For a rational matrix this implies that its rational determinant is nonzero; the adjugate formula then supplies its inverse over \(\mathbb Q\). We may consequently apply Proposition 10 directly over \(\mathbb Q\) to the output tuple. It makes every required inverse of the original tree defined over \(\mathbb Q\) and makes the final value invertible. This also shows why no assertion about preservation of arbitrary inverse domains under a homomorphism is needed. ◻ Corollary 13. Let \(L=A_0+\sum_{i=1}^n A_i x_i\) be a rational affine linear pencil of order \(q\le B\) that admits an invertible matrix evaluation over an extension field of \(\mathbb Q\). There is a tuple \(X\in\mathcal H_{n,s}\) for which \(L(X)\) is invertible. Proof. Use the same argument with the two pencils \(L\) and \(1\). The product of their determinant polynomials over all \(\omega\in\Omega\) is nonzero and has total degree at most \(3BM^3<H\). A grid point where this product is nonzero is retained by the generator, and (27) makes \(L\) invertible at its output tuple. ◻ The proof of Proposition 12 fixes \(\Phi\) only after the list has been specified. Its polynomial \(P_\Phi\) is used solely to prove the existence of a good triple in the fixed grid; the generator never constructs this polynomial, the certificates, or a witness evaluation. Different formulas may use different triples. Arbitrarily large rational constants change the coefficients of \(P_\Phi\), but neither its degree bound nor the construction of \(\mathcal H_{n,s}\). Bit complexity and output lengthProposition 14. The list \(\mathcal H_{n,s}\) can be constructed and written by one deterministic Turing machine in a number of bit operations bounded by a fixed polynomial in \(n+s+1\). Its entire binary encoding has length bounded by a fixed polynomial in the same quantity. Proof. Put \(m=n+s+1\). The parameter definitions give \[w\le m,\qquad B\le2m,\qquad \Delta\le4m^4,\qquad M\le2B\Delta\le16m^5.\] Consequently \[ H=O(m^{17}),\qquad D=O(m^{10}),\qquad H^3=O(m^{51}). \tag{28}\] Counting the unary inputs, forming these parameters, and finding \(M\) by successive doubling all take polynomial time. We first bound the integers actually computed at a grid triple. For an input monomial \(z^j\), where \(0\le j<N\), the defining formula for \(T_i\) gives \[ T_i z^j =\sum_{a=0}^j \binom ja i^{j-a}t^a(z-i)^{M-1-a}. \tag{29}\] Expanding each power in the monomial basis computes every entry using integer arithmetic. Each coefficient in either of the two basis expansions has absolute value at most \(2^M w^M\). At a grid value \(1\le t\le H\), an entry of the padded matrix \(R_i(t)\) therefore has absolute value at most \[M\,2^{2M}w^{2M}H^M.\] In (24), the only division of a coefficient is by \(M\). All powers of \(\xi\) reduce to signed basis monomials. The Fourier sum and the lift involve polynomially many terms, and \(p^a r^b\le H^{2M}\) on the grid. For example, the absolute values of the power-basis coefficients of every entry of \(M\widetilde R_i(t,p,r)\) are bounded by \[M^4\,2^{2M}w^{2M}H^{3M}.\] Multiplication by a power-basis monomial merely permutes those coefficients and changes signs. Thus \[ U_i:=MZ_i\in\mathop{\mathrm{Mat}}_D(\mathbb Z),\qquad b=O\!\left(M\log\bigl((w+1)(H+1)\bigr)+\log M\right) =O(m^5\log m) \tag{30}\] is a common bound on the bit lengths of their entries. These calculations have explicit nested loops of polynomial length: binomial coefficients may be formed by Pascal’s recurrence, integer powers by repeated multiplication, and all ring coefficients by the signed reductions just described. Every intermediate sum and product in these loops has polynomial bit length. The matrices \(U_i\) can therefore be constructed in polynomial bit time. The common clearing factor cancels in normalization: \[ Z_0^{-1}Z_i=U_0^{-1}U_i. \tag{31}\] If \(U_0\) is nonsingular, Cramer’s rule computes each column of this matrix using \(\det U_0\) and determinants of \(U_0\) with one column replaced by a column of \(U_i\). All these are integer matrices of order \(D\) with the same entry bit bound \(b\). Every minor of any such matrix has absolute value at most \(D!2^{Db}\). Hence its bit length is bounded by \[ \Lambda=O\bigl(D(b+\log(D+1))\bigr) =O(m^{15}\log m). \tag{32}\] Each output entry is a ratio of two such determinants. It can be written with a signed binary numerator and a positive binary denominator using \(O(\Lambda)\) bits, changing both signs if necessary. Cancelling their gcd is optional for this encoding. For completeness, exact Gaussian elimination computes the needed determinants in polynomial bit time without permitting fractions to grow unchecked. Let \(A\) be any one of these integer matrices. After \(k\) successful pivots, let \(I_k\) be the ordered list of the selected original row indices, and let \[B_k=A[I_k,\{1,\ldots,k\}].\] This submatrix is invertible. For an unselected row index \(u\) and a column \(v>k\), the remaining Gaussian entry is \[ A_{uv}-A[u,\{1,\ldots,k\}]\, B_k^{-1}A[I_k,v] =\frac{ \det\begin{pmatrix} B_k&A[I_k,v]\\ A[u,\{1,\ldots,k\}]&A_{uv} \end{pmatrix}} {\det B_k}. \tag{33}\] For \(k=0\) the denominator is \(1\) and the entry is \(A_{uv}\). The determinant identity follows by subtracting the appropriate linear combination of the first \(k\) block rows from the last row. It also shows inductively that ordinary Gaussian updates compute the displayed entries. If the next pivot column has a nonzero remaining entry, swap its row into the pivot position and append that original row index to \(I_k\). These swaps involve only unselected rows, so they do not change any previously selected submatrix. Writing the next pivot as \(p_{k+1}\), equation (33) gives \[p_{k+1}=\frac{\det B_{k+1}}{\det B_k}, \qquad p_1\cdots p_k=\det B_k.\] If the entire next remaining column is zero, the Schur complement is singular and \(\det A=0\). Otherwise all \(D\) pivots can be taken, and their product, multiplied by the sign of the accumulated row permutation, equals \(\det A\). Both the stored Gaussian entries and the accumulated pivot products, when reduced to fractions, therefore have \(O(\Lambda)\)-bit numerators and denominators: they are ratios of minors or minors themselves. Each individual update combines only a constant number of these fractions, so its intermediate products and sums also have \(O(\Lambda)\) bits before reduction. Integer addition, multiplication, and division on such operands have polynomial bit cost by the elementary digit algorithms. Gcd reduction does as well: in the Euclidean algorithm the nonzero remainders decrease by a factor of at least two within every two steps, so there are \(O(\Lambda)\) polynomial-cost divisions. There are \(O(D^3)\) Gaussian arithmetic updates. Pivot searches, row swaps, and sign bookkeeping also have polynomial cost. This proves polynomial bit time for each determinant, including singular matrices and all the column-replaced matrices used by Cramer’s rule. At each grid triple, at most \(nD^2+1\) determinants suffice for the singularity test and all output entries. Equations (28)–(32) therefore give a fixed polynomial bound on the total computation. The complete list contains at most \(H^3 nD^2\) rational entries, so its encoding length is \[ O(H^3 nD^2\Lambda)=O(m^{87}\log m). \tag{34}\] Dimensions, signs, and fixed delimiters fit within the same bound. A fixed delimited encoding allows the list to be written as its entries are produced; if its length is placed first, one may instead buffer the polynomial-length list or make a preliminary counting pass. Finally, these arithmetic and loop bounds give a Turing-machine bound as well. All arrays have polynomially many entries of polynomial bit length. They may be stored as indexed binary records on work tapes; even scanning all records for each requested access adds only a fixed polynomial factor. The loops, elementary digit algorithms, and delimiters are fixed in advance. Thus one deterministic Turing machine performs the construction and writes the whole list within \(C(n+s+1)^k\) bit operations for some fixed positive integers \(C,k\). None of its arithmetic uses the constants or coefficients of an unknown formula. ◻ Completion of the proof of Theorem 1. Use the generator just defined. Proposition 12 gives the universal hitting property, with invertible and therefore nonzero output values. Proposition 14 gives both required polynomial bounds, after increasing the same fixed constants \(C,k\) if necessary. The generator is deterministic and depends only on its two unary inputs. ◻ A universal rank-detecting listThe hitting list and its complexity bounds are now established. We use the pencil-hitting consequence to recover the exact noncommutative rank of a rectangular affine pencil from one list that is independent of all coefficient values. The additional input is the characterization of free-field rank by normalized matrix-evaluation ranks, recalled in the proof. Corollary 15. Let \(a,b\geq1\) and \(k\geq0\), and put \(P=a+b+k+1\). From these parameters in unary, a deterministic generator constructs a nonempty finite list \(\mathcal R_{a,b,k}\) of pairs \[(e,X),\qquad e\geq1,\quad X=(X_1,\ldots,X_k)\in\mathop{\mathrm{Mat}}_e(\mathbb Q)^k,\] in a fixed polynomial in \(P\) bit operations. Its number of entries, total binary encoding length, and every matrix dimension \(e\) are bounded by fixed polynomials in \(P\). The list depends only on \(a,b,k\). For every rectangular rational affine pencil \[A(x)=A_0+\sum_{i=1}^k A_i x_i,\qquad A_i\in\mathbb Q^{a\times b},\] write \(\operatorname{ncrk}A\) for its rank over the free skew field on \(x_1,\ldots,x_k\) over \(\mathbb Q\), with ordinary rational rank when \(k=0\). Then the exact identity \[ \operatorname{ncrk}A =\max_{(e,X)\in\mathcal R_{a,b,k}} \frac{\mathop{\mathrm{rank}}_{\mathbb Q}\!\left(A_0\otimes I_e+ \sum_{i=1}^k A_i\otimes X_i\right)}{e} \tag{35}\] holds for all choices and bit lengths of the coefficients. Suppose that, at each requested pair \((e,X)\), an oracle returns either the complete exact rational \(ae\) by \(be\) matrix in (35), in binary rational encoding, or its exact ordinary rank. Querying the whole list nonadaptively and taking the maximum of the exact quotients returns \(\operatorname{ncrk}A\). If \(L\) is the total binary length of the responses, list generation, query writing, and response processing use \(\operatorname{poly}(P+L)\) bit operations, in addition to the sum of the oracle’s costs. The response lengths and oracle costs may depend on the coefficient heights. If \(a=0\) or \(b=0\), the rank is zero and no queries are needed. Proof. Affine evaluations and free-field rank. Put \(H(z)=\sum_{i=0}^k A_i z_i\), with a new variable \(z_0\). The coefficient-span invariance of Fortin and Reutenauer (Fortin and Reutenauer 2004, sec. 2, Corollary 1, and Section 3, Lemma 1) includes the constant coefficient: the free-field rank of a rectangular affine linear matrix depends only on the span of all its coefficient matrices. The coefficient spans of \(A\) and \(H\) are both \(\mathop{\mathrm{span}}_{\mathbb Q}\{A_0,\ldots,A_k\}\), so their free-field ranks agree. This uses coefficient-span invariance, not a specialization \(z_0=1\) in a free skew field. For \(e\geq1\), let \(h_e\) be the maximum rank of \(\sum_{i=0}^k A_i\otimes Z_i\) over \(Z_i\in\mathop{\mathrm{Mat}}_e(\mathbb Q)\), and let \(\alpha_e\) be the maximum rank of \(A_0\otimes I_e+\sum_{i=1}^k A_i\otimes X_i\) over rational \(X_i\). Zero-padding the \(A_i\) to square matrices of order \(\max(a,b)\) preserves both free-field rank and every ordinary blow-up rank. The homogeneous blow-up characterization and its attainment over \(\mathbb Q\) (Ivanyos et al. 2018, arXiv version, Definition 1.2 and its discussion, Theorem 1.5) therefore give \[r:=\operatorname{ncrk}A=\max_{e\geq1}\frac{h_e}{e},\] with the maximum attained. The tensor order used in that reference differs from \(A_i\otimes Z_i\) only by row and column permutations. Here padding is used to preserve ranks, not to test invertibility. For each fixed \(e\), taking \(Z_0=I_e\) gives \(\alpha_e\leq h_e\). If \(h_e>0\), some \(h_e\) by \(h_e\) minor is a nonzero polynomial \(p\) in the entries of the \(Z_i\). The polynomial \(p\det Z_0\) is nonzero; since \(\mathbb Q\) is infinite, it is nonzero at a rational tuple. There \(Z_0\) is invertible and the rank is \(h_e\). Right multiplication gives \[\left(\sum_{i=0}^k A_i\otimes Z_i\right) (I_b\otimes Z_0^{-1}) =A_0\otimes I_e+\sum_{i=1}^k A_i\otimes(Z_iZ_0^{-1}),\] without changing rank. The case \(h_e=0\) is immediate, so \(\alpha_e=h_e\) for every \(e\). Consequently \[ r=\max_{e\geq1}\frac{\alpha_e}{e} \tag{36}\] is attained: every individual affine evaluation has rank at most \(re\), and some rational evaluation has rank exactly \(re\). No bound on the dimension or entry heights of this existence witness will be used. Square completions for rank thresholds. For \(0\leq t\leq\min(a,b)\), form the square affine pencil \[C_t=\begin{pmatrix}A&U_t\\ V_t&0\end{pmatrix}, \qquad U_t:a\times(a-t),\quad V_t:(b-t)\times b.\] The entries of \(U_t,V_t\) are independent variables, so their dimension-\(e\) evaluations may be arbitrary matrices of the displayed block sizes multiplied by \(e\). For a fixed rational tuple \(X\), there exist rational choices of these completion blocks making \(C_t(X,U_t,V_t)\) invertible if and only if \(\mathop{\mathrm{rank}}A(X)\geq te\). Necessity follows by splitting the completed matrix into its \(A(X)\) and two off-diagonal blocks: \[(a+b-t)e=\mathop{\mathrm{rank}}C_t(X,U_t,V_t) \leq\mathop{\mathrm{rank}}A(X)+(a-t)e+(b-t)e.\] For sufficiency, choose a \(te\)-dimensional subspace \(K\subseteq\mathbb Q^{be}\) on which \(A(X)\) is injective. Take \(V_t\) to be surjective with kernel \(K\), and take \(U_t\) to map isomorphically onto a complement of \(A(X)K\) in \(\mathbb Q^{ae}\). A vector in the kernel of the completed matrix then has its first component in \(K\), and the direct sum \(A(X)K\oplus\operatorname{im}U_t\) makes both components zero. This proves invertibility. It includes \(t=0\) and all empty-block cases; in particular \(C_0\) can always be made invertible. A coefficient-independent list. Reserve \(a^2\) variables \(u_{ij}\) and \(b^2\) variables \(v_{ij}\), disjoint from the first \(k\) variables. For \(C_t\), use the first \(a-t\) columns of the \(u\)-pool for \(U_t\) and the first \(b-t\) rows of the \(v\)-pool for \(V_t\). The pools can be reused for different \(t\). Thus every \(C_t\) is a pencil in the same \(N=k+a^2+b^2\) variables, with unused variables allowed, and has order \(a+b-t\leq a+b\). Set \(s=a+b\), so this order is at most \(B=2s+1\). Both \(N\) and \(s\) are positive. Apply the single list \(\mathcal H_{N,s}\) from Corollary 13, and project each output onto its first \(k\) matrices, retaining its dimension \(e\) and any repetitions. This defines \(\mathcal R_{a,b,k}\); it is nonempty because \(C_0\) is feasible. For \(t=r\), equation (36) and the completion criterion make \(C_r\) feasible. A hit for \(C_r\) therefore has projected rank at least \(re\), while every projected evaluation has rank at most \(re\). This proves (35) exactly, without rounding; individual ranks need not be divisible by \(e\). The argument includes \(r=0\). When \(k=0\), the projected tuple is empty but still carries \(e\), and the identity also follows directly from \(\mathop{\mathrm{rank}}(A_0\otimes I_e)=e\mathop{\mathrm{rank}}A_0\). Since \(N+s+1\) is polynomial in \(P\), Proposition 14 and the dimension bound (28) give the stated generation, query-encoding, and dimension bounds. The generator never constructs \(C_t\), learns \(r\), or reads the coefficients: \(C_r\) is used only in the existence proof. For complete matrix responses, exact rational elimination is polynomial in the encoded response lengths and dimensions. For ordinary-rank responses, only exact comparison of the rank/dimension quotients is needed. These observations give the stated cost accounting. ◻ The assertion concerns exact matrix values or ordinary ranks, not singularity-bit access to the original pencil. It makes no claim for arbitrary rational circuits, finite fields, or total oracle-computation bit time independent of coefficient heights. If complete scalar value queries at zero and the standard basis points are also available, then \(k+1\) such queries reveal all coefficients, after which known coefficient-aware rank algorithms apply with those bit lengths counted (Ivanyos et al. 2018, arXiv version, Theorem 1.5). The distinct conclusion here is the universal nonadaptive coefficient-independent list, which also works with ordinary-rank responses.
Amitsur, S. A. 1966. “Rational Identities and Applications to Algebra and Geometry.” Journal of Algebra 3: 304–59. https://doi.org/10.1016/0021-8693(66)90004-4.
Arvind, V., Abhranil Chatterjee, and Partha Mukhopadhyay. 2022. “Black-Box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial Time.” Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022), Leibniz international proceedings in informatics, vol. 245: 23:1–22. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.23.
Arvind, V., Abhranil Chatterjee, and Partha Mukhopadhyay. 2025. Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time. https://arxiv.org/abs/2309.15647v4.
Arvind, V., Abhranil Chatterjee, and Partha Mukhopadhyay. 2026. “Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time.” SIAM Journal on Computing, ahead of print. https://doi.org/10.1137/24M1689508.
Bogdanov, Andrej, and Hoeteck Wee. 2005. “More on Noncommutative Polynomial Identity Testing.” Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC), 92–99. https://doi.org/10.1109/CCC.2005.13.
Bostan, Alin, and Philippe Dumas. 2010. “Wronskians and Linear Independence.” The American Mathematical Monthly 117 (8): 722–27. https://doi.org/10.4169/000298910X515785.
Cohn, P. M. 2006. Free Ideal Rings and Localization in General Rings. Cambridge University Press.
Cohn, P. M., and C. Reutenauer. 1994. “A Normal Form in Free Fields.” Canadian Journal of Mathematics 46: 517–31.
Derksen, Harm, and Visu Makam. 2017. “Polynomial Degree Bounds for Matrix Semi-Invariants.” Advances in Mathematics 310: 44–63. https://doi.org/10.1016/j.aim.2017.01.018.
Forbes, Michael A., and Venkatesan Guruswami. 2015. “Dimension Expanders via Rank Condensers.” Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015), Leibniz international proceedings in informatics, vol. 40: 800–814. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.800.
Forbes, Michael A., and Amir Shpilka. 2013. “Quasipolynomial-Time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs.” Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 243–52. https://doi.org/10.1109/FOCS.2013.34.
Fortin, Marc, and Christophe Reutenauer. 2004. “Commutative/Noncommutative Rank of Linear Matrices and Subspaces of Matrices of Low Rank.” Séminaire Lotharingien de Combinatoire 52: Article B52f, 12 pp. https://www.mat.univie.ac.at/~slc/s/s52reut.pdf.
Garg, Ankit, Leonid Gurvits, Rafael Oliveira, and Avi Wigderson. 2016. “A Deterministic Polynomial Time Algorithm for Non-Commutative Rational Identity Testing.” Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 109–17. https://doi.org/10.1109/FOCS.2016.95.
Garg, Ankit, Leonid Gurvits, Rafael Oliveira, and Avi Wigderson. 2020. “Operator Scaling: Theory and Applications.” Foundations of Computational Mathematics 20: 223–90. https://doi.org/10.1007/s10208-019-09417-z.
Guruswami, Venkatesan, and Swastik Kopparty. 2016. “Explicit Subspace Designs.” Combinatorica 36: 161–85. https://doi.org/10.1007/s00493-014-3169-1.
Guruswami, Venkatesan, Nicolas Resch, and Chaoping Xing. 2018. “Lossless Dimension Expanders via Linearized Polynomials and Subspace Designs.” 33rd Computational Complexity Conference (CCC 2018). https://doi.org/10.4230/LIPIcs.CCC.2018.4.
Hrubeš, Pavel, and Avi Wigderson. 2015. “Non-Commutative Arithmetic Circuits with Division.” Theory of Computing 11 (14): 357–93. https://doi.org/10.4086/toc.2015.v011a014.
Ivanyos, Gábor, Youming Qiao, and K. V. Subrahmanyam. 2017. “Non-Commutative Edmonds’ Problem and Matrix Semi-Invariants.” Computational Complexity 26 (3): 717–63. https://doi.org/10.1007/s00037-016-0143-x.
Ivanyos, Gábor, Youming Qiao, and K. V. Subrahmanyam. 2018. “Constructive Non-Commutative Rank Computation Is in Deterministic Polynomial Time.” Computational Complexity 27 (4): 561–93. https://doi.org/10.1007/s00037-018-0165-7.
Kaliuzhnyi-Verbovetskyi, Dmitry S., and Victor Vinnikov. 2010. Noncommutative Rational Functions, Their Difference-Differential Calculus and Realizations. https://arxiv.org/abs/1003.0695.
Nisan, Noam. 1991. “Lower Bounds for Non-Commutative Computation (Extended Abstract).” Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (STOC), 410–18. https://doi.org/10.1145/103418.103462.
Raz, Ran, and Amir Shpilka. 2005. “Deterministic Polynomial Identity Testing in Non-Commutative Models.” Computational Complexity 14 (1): 1–19. https://doi.org/10.1007/s00037-005-0188-8.
|
| ||||||||
|