Rank-one row increments and the fixed Boolean border
DefinitionOddPermSum_Evaluation_Supplement_rowUpdatealgebracomplexity-theorylinear-algebrap2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
For an index and a row , define . For a stored inverse , put . The candidate updated inverse is
Here is the ring inverse and is used as an inverse only when is a unit. The border is the published border with one new last index, row and column basis vector , and bottom-right entry .
These definitions construct the source's matrices rather than assuming arbitrary objects with their desired properties.
Definition code
import Definitions.Def_OddPermSum_Evaluation_border
set_option autoImplicit false
namespace OddPermSum.Evaluation.Supplement
noncomputable def rowUpdate {R : Type*} [CommRing R] {s : ℕ}
(A : Matrix (Fin s) (Fin s) R) (i : Fin s) (ρ : Fin s → R) : Matrix (Fin s) (Fin s) R :=
fun p j => A p j + if p = i then ρ j else 0
noncomputable def updateEta {R : Type*} [CommRing R] {s : ℕ}
(B : Matrix (Fin s) (Fin s) R) (i : Fin s) (ρ : Fin s → R) : R :=
1 + ∑ j, ρ j * B j i
noncomputable def inverseUpdate {R : Type*} [CommRing R] {s : ℕ}
(B : Matrix (Fin s) (Fin s) R) (i : Fin s) (ρ : Fin s → R) : Matrix (Fin s) (Fin s) R :=
fun p q => B p q + Ring.inverse (updateEta B i ρ) * B p i * (∑ j, ρ j * B j q)
noncomputable def fixedBorder {R : Type*} [CommRing R] {n : ℕ}
(u : Fin n) (X : Matrix (Fin n) (Fin n) R) (b : R) : Matrix (Fin (n+1)) (Fin (n+1)) R :=
border (fun _ : Fin 1 => u) (fun _ : Fin 1 => u) X (fun _ => b)
end OddPermSum.Evaluation.Supplement
Source
Boxuan Chen, Bin Cui, Hanqing Li, Xupeng Miao, Haoze Wang, STOC 2027 submission #716 (October 2026), p. 19–20, Eqs. (6.8), (6.11), (6.12)