Zulip Chat Archive
Stream: mathlib4
Topic: Formal Verification of Gauss-Jordan Elimination
crazerist (Oct 03 2025 at 17:58):
I found the Gaussian elimination method in Mathlib/Tactic/Linarith/Oracle/SimplexAlgorithm/Gauss.lean. I'd like to know if there's a proof to verify the correctness of the algorithm? Specifically, there's a predicate that describes the row echelon form or row simplest form of a matrix, and the coefficient matrix obtained by the algorithm satisfies the definition of the predicate.If so, please let me know the location, thank you very much :)
Vasilii Nesterov (Oct 03 2025 at 18:29):
I don't think it was verified, because it's monadic code which is (was?) hard to verify. There is a
#general > new monadic program verification framework, but I'm not sure it's ready for such a verification.
Yves Jäckle (Oct 04 2025 at 06:32):
I remember coming across this repository, but it's in Lean 3.
Martin Dvořák (Oct 04 2025 at 14:51):
We formalized a part of the theory as a key step in the Seymour project:
https://github.com/Ivan-Sergeyev/seymour/blob/main/Seymour/Matrix/Pivoting.lean
Note that only the pivoting steps have a definition and API; Guassian elimination itself was used implicitly in some inductive proofs and isn't defined as such.
Last updated: Dec 20 2025 at 21:32 UTC