The invariant of oblivious Gauss–Jordan elimination is preserved by one column step
ProvedOPI.GE.inv_succLet be a field. An augmented matrix encodes the linear system for . Oblivious Gauss–Jordan elimination processes the columns in order, keeping the current matrix and a "used" flag for each row. At column it selects the first unused row with a nonzero entry in column , if there is one, as the pivot. It then normalizes that row, subtracts multiples of it from all other rows so that column becomes a unit vector, and marks the row as used. If no row qualifies, nothing changes. Let be the state after columns, and say that row is the pivot of column if it was selected at step .
The invariant asserts three things:
- the current system has the same solutions as ;
- for each processed column : if row is its pivot, then is marked used and column of the current matrix is the unit vector ; if column has no pivot, every unused row has entry in column ;
- every used row is the pivot of some processed column.
Statement. For ,
By induction the invariant holds after all columns, which is the main input to the correctness theorem solution_solves. The elimination has a data-independent sequence of operations, which is what allows it to be compiled into a reversible circuit for the decoder.
import Definitions.Def_TwoFoldOPI_CL_Part01
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Circuit
import Definitions.Def_QAlgorithms_Defs_GradientMethods
import Definitions.Def_QAlgorithms_Defs_OPIOraclePrograms
import Definitions.Def_QAlgorithms_Defs_OPIUniformity
import Definitions.Def_QAlgorithms_Defs_Fourier
import Definitions.Def_TwoFoldOPI_elemBits
import Definitions.Def_TwoFoldOPI_schurSquare
import Definitions.Def_TwoFoldOPI_schurFailureSum
import Definitions.Def_CodingTheory
import Definitions.Def_OAIThreeMachineSched01
import Definitions.Def_CookLevin_Cost
import Definitions.Def_TwoFoldOPI_codeOf
import Definitions.Def_TwoFoldOPI_solves
import Definitions.Def_TwoFoldOPI_Input
import Definitions.Def_TwoFoldOPI_CLSerializableF
open OPI OPI.GE
variable {K : Type*} [Field K] [DecidableEq K] {r c : ℕ}
theorem OPI.GE.inv_succ (A0 : Aug K r c) (j : ℕ) (hj : j < c) (h : Inv A0 j) : Inv A0 (j + 1) := by sorry