Source lean/Determinize/Proof/FiniteModel/LinearBounds.lean
import Determinize.Proof.FiniteModel.Pathsimport Mathlib.LinearAlgebra.FiniteDimensional.Basicnamespace Determinize.Proof.FiniteModelopen Spec.FiniteModel/-- A finite chain with paths to a boundary has an invertible boundary-value operator. -/theorem linear_exists (model : Model) (paths : Paths model) (valid : paths.Valid model)    (rhs : Fin model.size → Rat) :    ∃ v : Fin model.size → Rat, ∀ i, v i = rhs i +      if model.kind i = .transient then ∑ j, model.transition i j * v j else 0 := by  let L : (Fin model.size → Rat) →ₗ[Rat] (Fin model.size → Rat) :=    { toFun := fun v i ↦ v i - if model.kind i = .transient then          ∑ j, model.transition i j * v j else 0      map_add' := by        intro v w        funext i        dsimp        split_ifs <;> simp [mul_add, Finset.sum_add_distrib]        ring      map_smul' := by        intro c v        funext i        dsimp        split_ifs <;> simp [Finset.mul_sum, mul_sub, mul_left_comm] }  have injective : Function.Injective L := by    apply (LinearMap.ker_eq_bot).mp    apply LinearMap.ker_eq_bot'.mpr    intro v zero    have eqs (i) : v i = if model.kind i = .transient then        ∑ j, model.transition i j * v j else 0 := by      have h := congrFun zero i      exact sub_eq_zero.mp h    have h := paths_unique model paths valid (fun i ↦ (v i : ℝ)) (by      intro i      rw [eqs i]      split_ifs <;> simp)    funext i    exact_mod_cast h i  obtain ⟨v, hv⟩ := LinearMap.surjective_of_injective injective rhs  refine ⟨v, fun i ↦ ?_⟩  have h := congrFun hv i  change v i - _ = rhs i at h  exact sub_eq_iff_eq_add.mp h/-- The inverse boundary-value operator preserves nonnegativity. -/theorem linear_nonnegative (model : Model) (paths : Paths model) (valid : paths.Valid model)    (rhs v : Fin model.size → Rat) (nonnegative : ∀ i, 0 ≤ rhs i)    (eqs : ∀ i, v i = rhs i + if model.kind i = .transient then      ∑ j, model.transition i j * v j else 0) : ∀ i, 0 ≤ v i := by  obtain ⟨smallest, _, bound⟩ := Finset.exists_min_image Finset.univ v    ⟨model.initial, Finset.mem_univ _⟩  let M := v smallest  have bounded : ∀ i, M ≤ v i := fun i ↦ bound i (Finset.mem_univ _)  have minimum_next (i) (transient : model.kind i = .transient) (minimum : v i = M) :      v (paths.next i) = M := by    have h := eqs i    rw [ite_eq_left transient, minimum] at h    have sumDiff : (∑ j, model.transition i j * (v j - M)) =        (∑ j, model.transition i j * v j) - M := by      simp only [mul_sub, Finset.sum_sub_distrib, ← Finset.sum_mul, model.normalized, one_mul]    have term := Finset.single_le_sum      (fun j (_ : j ∈ Finset.univ) ↦ mul_nonneg (model.nonnegative i j)        (sub_nonneg.mpr (bounded j))) (Finset.mem_univ (paths.next i))    rw [sumDiff] at term    have positive := (valid i transient).1    have hn := nonnegative i    have hb := bounded (paths.next i)    nlinarith  have descend : ∀ n i, paths.rank i = n → v i = M → 0 ≤ M := by    intro n    induction n using Nat.strong_induction_on with    | h n ih =>      intro i rank minimum      by_cases transient : model.kind i = .transient      · exact ih (paths.rank (paths.next i)) (rank ▸ (valid i transient).2)          (paths.next i) rfl (minimum_next i transient minimum)      · have h := eqs i        rw [ite_eq_right transient, add_zero, minimum] at h        exact h ▸ nonnegative i  exact fun i ↦ (descend _ smallest rfl rfl).trans (bounded i)end Determinize.Proof.FiniteModel