The Setting
A noncommutative rational formula in is evaluated at tuples of matrices, and more generally at points of for a ring into which maps; at a given point it may have no value, since each inverse needs an invertible operand. The item builds, by recursion over the structure of , a square matrix of affine forms with a rational row and a rational column .
Formulas and Their Values
A rational formula in variables is a finite rooted tree whose leaves carry the variables or rational constants and whose inner vertices, the gates, are sums , products taken in this order, and inverses .✦ The size of a formula is its number of vertices: for a variable or a constant, for and for , and for .✦
Fix a ring , not necessarily commutative, a ring homomorphism and a point . The evaluation relation at is the smallest relation between formulas and elements of in which has value , a constant has value , and have values and whenever and have values and , and has value whenever has a value with .✦ A formula is defined at when it has a value there. For the ring of matrices over a field containing , a point is a tuple of matrices.
Affine Pencils
An affine form in variables is an expression with rational .✦ The value of an affine form at is the element (1)✦ of .
An affine pencil of order is a matrix of affine forms, with rational matrices ; its evaluation is the matrix over whose entries are the values (1) of those of . For , the matrix , read as a matrix over , is up to the order of the basis. A rational matrix is read over through , entry by entry.
The Pencil of a Formula
The index set of a formula is the finite set built along : two elements for a variable or a constant, the disjoint union for and for , and with one new element for .✦ Its cardinality is (2)✦
The row and the column of are the rational vectors indexed by given by the recursions (3)✦ (4)✦ Here and are formulas, is a rational constant, and the blocks follow the decomposition of , the new element of last.
The pencil of a formula is the affine pencil indexed by given by the recursion (5)✦ in which the rational blocks , and stand for constant forms.
The Claim
Theorem 1 (Affine realization). Let be a ring with a ring homomorphism , let , and let be a rational formula in variables that has value at . Then has a two-sided inverse over , and (6)✦
In the paper, the result reads: for each subtree of a formula there are an affine pencil of order , with and the numbers of leaves and of inverse gates of , and a constant rational row and column of length , such that at every tuple of matrices over every field extension of at which is defined, is invertible and .
What Is Checked
The claim is stated over rational formulas and their evaluation relation at a point of , for a ring with a ring homomorphism , and over the index set, the row, the column and the pencil of a formula, (3), (4) and (5), the pencil evaluated entrywise by (1).
About these constructions the library proves the count (2) and the following. Evaluation at follows the recursion (5): for formulas and , (7)✦ (8)✦ (9)✦
For every , the matrix over has a two-sided inverse, and (10)✦
Let be a block matrix over whose block is square with a two-sided inverse . It has the Schur factorization (11)✦ and when also has a two-sided inverse, so does the block matrix, with (12)✦