The Setting
Take a noncommutative rational formula in and a tuple of rational matrices. Evaluating at asks at each inverse gate whether the value of the operand is invertible, and hits when every answer is yes and the value of is invertible as well. The questions at the inverse gates concern the inside of ; the last one concerns its root. The root augmentation is a single matrix for that last question, built from the linear pencil of ; it decides whether the value of is invertible.
The library states the construction over any ring with a ring homomorphism , at any point of ; tuples of rational matrices are the case where is the matrix ring .
Formulas, Values and Pencils
A rational formula in variables is a finite tree built from the variables and rational constants by addition , multiplication in this order, and inversion .✦ The inverse nodes of are its subformulas of the form , one for each inverse gate, listed in the order in which a depth-first walk from the root meets them, left operand before right.✦
The value relation at a point of is the least relation between formulas and elements of in which has value , the constant has value , the sum and the product have values and when has value and has value , and has value when has a value with .✦ A formula is defined at a point of when it has a value at in the value relation.
A square matrix over of order is invertible when it has a two-sided inverse, a matrix over with .
An affine form in variables is an expression with rational coefficients ✦, and its value at is the element (1)✦ of .
The pencil of is a square matrix of affine forms, of order , defined by recursion on together with a rational column and a rational row of length . The order is at a leaf, at and at , and at ✦; the pencil is (2)✦ and the column and row are (3) with zero blocks of the sizes the orders give. The value of the pencil at is the matrix over obtained by evaluating each entry at ✦, and and are and with applied to each entry.
The Claim
Theorem 1. Let be a rational formula in variables with inverse nodes , let be a ring with a ring homomorphism , and let be a point of . The certificate nodes of are its inverse nodes followed by , (4)✦ and the root augmentation of is the pencil of the last of them, whose value at is (5)✦ If is a square matrix of order over with a two-sided inverse , and and are and matrices over , then (6)✦ where is the Schur complement of . If has value at , then (7)✦
In the paper, the result reads: the root augmentation is the matrix , of the block form of the pencil at an inverse gate, with no inverse gate added to .
What Is Checked
The claim is stated over rational formulas in variables and their inverse nodes, the value relation in a ring with a ring homomorphism from , affine forms and their values at a point of , and the pencil of a formula with its order, column and row. Beyond the claim, the library proves that evaluation at a point is additive on affine forms: the zero form has value , and the sum of two forms has value .