The Setting
Let be a noncommutative rational formula in and a tuple of matrices over a field containing . The formula has a value at only if every inverse gate receives an invertible matrix, and hits when that value exists and is itself invertible. Proposition 4.2 reads both conditions off a short list of linear pencils of small order, one for each inverse gate of and one for its root, at points of any ring receiving . Headed by the trivial pencil of order one, the same list yields the condition polynomials, defined below.
Formulas and Their Evaluation
A rational formula in variables is a finite tree whose leaves are the variables or rational constants and whose inner vertices are sums , ordered products and inverses of formulas already built.✦ The size of is its number of vertices.✦ The vertex of itself is its root, and its vertices of the form are its inverse gates.
Let be a ring and a ring homomorphism. The evaluation of formulas at a point of is the least relation between formulas and elements of in which has value , a constant has value , and have values and whenever has value and has value , and has value whenever has a value with .✦ The evaluation domain of is the set of points of at which has a value, and is the set of those at which has a value that is a unit of .
A rational formula is nonzero if, for some , it has a value at some tuple of rational matrices, a constant being read as the scalar matrix .✦
The list of inverse occurrences of is the list of its subformulas of the form , one entry for each occurrence, defined by recursion on , with juxtaposition for concatenation: (1)✦ The certificate list of is the list of formulas (2) The last entry is not an inverse gate of ; its pencil is the augmentation of at its root.
Pencils
An affine form in variables is an expression with rational .✦ Its coefficient vector is .✦ An affine form is constant when its coefficient vector is .✦ The value of an affine form at is .✦
A pencil of order is a matrix of affine forms, written with coefficient matrices , and is the matrix of the values of its entries at . At a tuple of matrices, is the block matrix up to the order of the basis.
The pencil of a rational formula is the pencil of order , twice the number of leaves of plus the number of its inverse gates, defined by recursion on as a block matrix whose rational blocks enter as constant forms: (3) where the row and the column of a formula are the rational vectors of length given by the recursions (4) with the blocks following those of , the new index of last.
For a list of formulas, is the set of points at which is a unit of for every in .
The Condition Polynomials
Fix and put and . The -th cyclotomic field is with a primitive -th root of unity adjoined✦, and is the additive character of with values in ✦.
For a point and a natural number , the test matrix is the matrix over , with rows and columns indexed by through , of the Taylor test at with its columns from on set to zero: (5)✦ where is the coefficient of in . The test matrix at the point is written .
The lift of a matrix over indexed by is the matrix of polynomials over in the three variables given by (6)✦ where the Weyl monomial has entry in row and column when and otherwise, and the exponents of and are the least nonnegative representatives of and . The polynomials are the Fourier coefficients of : the coefficients of the cyclic-diagonal Fourier transform of along the Weyl monomials .
Given and , the condition polynomial of a pencil of order is the determinant of order (7)✦
The trivial pencil is the pencil of order one whose entry is the constant form : (8)✦ The condition list of a formula with is , the trivial pencil first.✦
The Claim
Theorem 1 (Proposition 4.2). Let be a rational formula in variables with certificate list , let and , and let be a ring with a ring homomorphism .
If , then (9)✦
The pencils of the inverse occurrences of are invertible on its evaluation domain, (10)✦ and has a value wherever they are all invertible: (11)✦
The certificate pencils are all invertible at a point exactly when has there a value that is a unit of : (12)✦
Suppose and is nonzero. Put and , and let and with and . Then, for these and , every polynomial of the condition list of is nonzero: (13)✦
In the paper, the result reads: for a formula of size at most , with and the indexed collection of the pencils of the inverse-node occurrences of together with the root augmentation , the collection contains at most affine pencils over , each of positive order at most ; at every tuple of matrices of a common positive order over a field extension of , all pencils in are invertible if and only if the original tree is defined there and its value is invertible; if is admissible, that is, defined at some tuple of rational matrices of positive order, and nonzero, there is a single tuple over some field extension of at which every pencil in is invertible; and adding the order-one constant pencil gives at most pencils of order at most with this last property, standing for and for .
What Is Checked
The claim is stated over rational formulas in variables, their size and their evaluation at points of a ring receiving , nonzero formulas, defined through tuples of rational matrices, the inverse occurrences and the certificate list, affine forms and the pencils with their entrywise values, and the condition polynomials over the cyclotomic field , built from the coefficient matrices, the Taylor test matrices with their columns from on set to zero, the Weyl monomials and the lift.
The sum of affine forms and in variables is the affine form whose coefficient vector is the sum of their coefficient vectors, and the zero form is the affine form in variables all of whose coefficients are zero. The value of an affine form at a point is additive in the form: the zero form has value , and for forms and .