Zulip Chat Archive

Stream: new members

Topic: how to prove the execution result of def = def


Alex (May 10 2025 at 12:01):

I want to use Lean to prove that the execution result of Gaussian elimination is a RowEchelonForm matrix. Is this possible?And what should I do? Thanks very much!

import Mathlib
universe u
variable {R : Type u} [Field R] [LinearOrder R] [IsStrictOrderedRing R]
def row_index_col_max_abs_arg  {m n :  } (A : Matrix (Fin m) (Fin n) R) (i : Fin m ) (j : Fin n ) :Option (Fin m)  :=
  --List.argmax (f := fun i => abs (A i j)) (l := (Finset.univ.sort (· ≤ ·)).filter ) -- l = [i,...,m]
  List.argmax (f := fun i => abs (A i j)) (l := (Finset.filter (fun ti => ti  i) (Finset.univ)).sort (·  ·) )-- l = [i,...,m]

def elementary_row_switch {tm tn : Type u} [Fintype tm] [DecidableEq tm][DecidableEq tn] [Fintype tn](A : Matrix tm tn R) (i j : tm ): Matrix tm tn R :=
  fun (r : tm ) => if r = i then A j  else
                        if r = j then A i else
                        A r
def elementary_row_addition {tm tn : Type u} [Fintype tm] [DecidableEq tm][DecidableEq tn] [Fintype tn] (A : Matrix ( tm) ( tn) R) (i j :  tm) (x : R) (hij : i  j) : Matrix ( tm) ( tn) R :=
  fun (r :  tm) => if r = j then x  A i + A j else A r

def row_update_by_eleRowAdd [Field R] {m n :  } (A : Matrix (Fin m) (Fin n) R) (i : Fin m ) (ti : Fin m) (hi': ti < i) (k : Fin n) : Matrix (Fin m) (Fin n) R :=
  if h1: i < m then
    let A' := elementary_row_addition A (j := i) (i := ti) (hij := ne_of_lt hi') (x := - A i k / A ti k )

    if h2: i + 1 < m then
      let isucc := (Fin.mk (i+1) (h2))
      have hi'' : ti < isucc := by
        unfold isucc
        apply lt_trans hi'
        apply Fin.lt_succ
      row_update_by_eleRowAdd A' isucc (ti := ti) (hi' :=hi'' ) (k := k)

    else A'
  else A
def elimination_loop   [Inhabited R] {m n :  } (A : Matrix (Fin m) (Fin n) R) (h : Fin m) (k: Fin n ) : Matrix (Fin m) (Fin n) R :=
  if  h <  m && k < n then
      /- Find the k-th pivot -/
      let i_max : Option (Fin m):= row_index_col_max_abs_arg A h k-- argmax (i = h ... m,abs (A [i,k]))
      match i_max with
      | none => panic "no pivot" -- panic 加Inhabited
      | some i_max' =>
      /-no pivot in this column, pass to the next column-/
        if A i_max' k = 0 then

          if hk : k + 1 < n then elimination_loop (A) (h) (Fin.mk (k + 1) (hk)) -- k' + 1
          else A
        else

          let A' := elementary_row_switch A h i_max'

          if h1: h +1 < m then
            let hsucc := (Fin.mk (h+1) (h1))
            /-+ (- A i k / A h k) * A h-/
            let A'' :=row_update_by_eleRowAdd A' hsucc (h) (hi':= by {unfold hsucc;apply Fin.lt_succ}) (k := k)
            if hk : k + 1 < n then
              elimination_loop (A'') (hsucc) (Fin.mk (k + 1) (hk)) -- k' + 1
            else A''
          else A'
  else A
def Gaussian_elimination   [Inhabited R] {m n :  } (hm : m > 0) (hn : n > 0) (A : Matrix (Fin m) (Fin n) R): Matrix (Fin m) (Fin n) R :=
  let h : Fin m := Fin.mk (0) hm /-Initialization of the pivot row-/
  let k : Fin n:= Fin.mk (0) hn /-Initialization of the pivot column -/
  elimination_loop A h k

def row_echelon_form_from_Gaussian_eli  [Inhabited R] {m n :  } (hm : m > 0) (hn : n > 0) (A : Matrix (Fin m) (Fin n) R): Matrix (Fin m) (Fin n) R := Gaussian_elimination hm hn A
def isRowEchelonForm {m n :  }  (A : Matrix (Fin m) (Fin n) R): Prop :=
   f : Fin m   ,
   ( i j, A i j  (0 : R)  f i  j.val)
   
   ( i : Fin m,(h : i.val < m -1)  f i < f (Fin.mk (i + 1) (Nat.succ_lt_of_lt_pred h))  f i = n)
/-I want to use Lean to prove that the execution result of Gaussian elimination is a RowEchelonForm matrix. Is this possible?-/
lemma rowEchelonFormOfGaussJordanEli_isRowEchelonForm {m n :  }[ Inhabited R]  (hm : m>0) (hn : n > 0)(A : Matrix (Fin m) (Fin n) R):
  isRowEchelonForm (row_echelon_form_from_Gaussian_eli hm hn A) :=
    sorry

Last updated: Dec 20 2025 at 21:32 UTC