Oblivious Gauss–Jordan elimination returns a solution of every solvable linear system
ProvedOPI.GE.solution_solvesLet be a field and an augmented matrix, encoding the system for . Run oblivious Gauss–Jordan elimination: for each column in turn, select the first not-yet-used row with a nonzero entry in column (if any) as the pivot. Normalize it and eliminate column from all other rows, without swapping rows. The particular solution is read off at the end: is the final right-hand-side entry of the pivot row of column , and if column had no pivot (a free variable).
Statement. If the system has some solution, then the particular solution solves it:
This is the correctness of the linear-algebra step of the classical decoder. The relinearized system is solved in this oblivious way (Relin.decode_eq), and the same elimination is compiled into a straight-line program and then into a reversible circuit.
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.solution_solves (A0 : Aug K r c) (hsol : ∃ z, Solves A0 z) : Solves A0 (solution A0) := by sorry