# Theory SparseMatrix

Up to index of Isabelle/HOL/HOL-Complex/HOL-Complex-Matrix

theory SparseMatrix
imports Matrix
begin

    (*  Title:      HOL/Matrix/SparseMatrix.thy
        ID:         $Id: SparseMatrix.thy,v 1.9 2005/06/20 20:14:01 wenzelm Exp $
        Author:     Steven Obua
    *)

    theory SparseMatrix imports Matrix begin

    types
      'a spvec = "(nat * 'a) list"
      'a spmat = "('a spvec) spvec"

    consts
      sparse_row_vector :: "('a::lordered_ring) spvec => 'a matrix"
      sparse_row_matrix :: "('a::lordered_ring) spmat => 'a matrix"

    defs
      sparse_row_vector_def : "sparse_row_vector arr == foldl (% m x. m + (singleton_matrix 0 (fst x) (snd x))) 0 arr"
      sparse_row_matrix_def : "sparse_row_matrix arr == foldl (% m r. m + (move_matrix (sparse_row_vector (snd r)) (int (fst r)) 0)) 0 arr"

    lemma sparse_row_vector_empty[simp]: "sparse_row_vector [] = 0"
      by (simp add: sparse_row_vector_def)

    lemma sparse_row_matrix_empty[simp]: "sparse_row_matrix [] = 0"
      by (simp add: sparse_row_matrix_def)

    lemma foldl_distrstart[rule_format]: "! a x y. (f (g x y) a = g x (f y a)) ==> ! x y. (foldl f (g x y) l = g x (foldl f y l))"
      by (induct l, auto)

    lemma sparse_row_vector_cons[simp]: "sparse_row_vector (a#arr) = (singleton_matrix 0 (fst a) (snd a)) + (sparse_row_vector arr)"
      apply (induct arr)
      apply (auto simp add: sparse_row_vector_def)
      apply (simp add: foldl_distrstart[of "λm x. m + singleton_matrix 0 (fst x) (snd x)" "λx m. singleton_matrix 0 (fst x) (snd x) + m"])
      done

    lemma sparse_row_vector_append[simp]: "sparse_row_vector (a @ b) = (sparse_row_vector a) + (sparse_row_vector b)"
      by (induct a, auto)

    lemma nrows_spvec[simp]: "nrows (sparse_row_vector x) <= (Suc 0)"
      apply (induct x)
      apply (simp_all add: add_nrows)
      done

    lemma sparse_row_matrix_cons: "sparse_row_matrix (a#arr) = ((move_matrix (sparse_row_vector (snd a)) (int (fst a)) 0)) + sparse_row_matrix arr"
      apply (induct arr)
      apply (auto simp add: sparse_row_matrix_def)
      apply (simp add: foldl_distrstart[of "λm x. m + (move_matrix (sparse_row_vector (snd x)) (int (fst x)) 0)"
        "% a m. (move_matrix (sparse_row_vector (snd a)) (int (fst a)) 0) + m"])
      done

    lemma sparse_row_matrix_append: "sparse_row_matrix (arr@brr) = (sparse_row_matrix arr) + (sparse_row_matrix brr)"
      apply (induct arr)
      apply (auto simp add: sparse_row_matrix_cons)
      done

    consts
      sorted_spvec :: "'a spvec => bool"
      sorted_spmat :: "'a spmat => bool"

    primrec
      "sorted_spmat [] = True"
      "sorted_spmat (a#as) = ((sorted_spvec (snd a)) & (sorted_spmat as))"

    primrec
      "sorted_spvec [] = True"
    sorted_spvec_step:  "sorted_spvec (a#as) = (case as of [] => True | b#bs => ((fst a < fst b) & (sorted_spvec as)))"

    declare sorted_spvec.simps [simp del]

    lemma sorted_spvec_empty[simp]: "sorted_spvec [] = True"
    by (simp add: sorted_spvec.simps)

    lemma sorted_spvec_cons1: "sorted_spvec (a#as) ==> sorted_spvec as"
    apply (induct as)
    apply (auto simp add: sorted_spvec.simps)
    done

    lemma sorted_spvec_cons2: "sorted_spvec (a#b#t) ==> sorted_spvec (a#t)"
    apply (induct t)
    apply (auto simp add: sorted_spvec.simps)
    done

    lemma sorted_spvec_cons3: "sorted_spvec(a#b#t) ==> fst a < fst b"
    apply (auto simp add: sorted_spvec.simps)
    done

    lemma sorted_sparse_row_vector_zero[rule_format]: "m <= n --> sorted_spvec ((n,a)#arr) --> Rep_matrix (sparse_row_vector arr) j m = 0"
    apply (induct arr)
    apply (auto)
    apply (frule sorted_spvec_cons2,simp)+
    apply (frule sorted_spvec_cons3, simp)
    done

    lemma sorted_sparse_row_matrix_zero[rule_format]: "m <= n --> sorted_spvec ((n,a)#arr) --> Rep_matrix (sparse_row_matrix arr) m j = 0"
      apply (induct arr)
      apply (auto)
      apply (frule sorted_spvec_cons2, simp)
      apply (frule sorted_spvec_cons3, simp)
      apply (simp add: sparse_row_matrix_cons neg_def)
      done

    consts
      abs_spvec :: "('a::lordered_ring) spvec => 'a spvec"
      minus_spvec ::  "('a::lordered_ring) spvec => 'a spvec"
      smult_spvec :: "('a::lordered_ring) => 'a spvec => 'a spvec"
      addmult_spvec :: "('a::lordered_ring) * 'a spvec * 'a spvec => 'a spvec"

    primrec
      "minus_spvec [] = []"
      "minus_spvec (a#as) = (fst a, -(snd a))#(minus_spvec as)"

    primrec
      "abs_spvec [] = []"
      "abs_spvec (a#as) = (fst a, abs (snd a))#(abs_spvec as)"

    lemma sparse_row_vector_minus:
      "sparse_row_vector (minus_spvec v) = - (sparse_row_vector v)"
      apply (induct v)
      apply (simp_all add: sparse_row_vector_cons)
      apply (simp add: Rep_matrix_inject[symmetric])
      apply (rule ext)+
      apply simp
      done

    lemma sparse_row_vector_abs:
      "sorted_spvec v ==> sparse_row_vector (abs_spvec v) = abs (sparse_row_vector v)"
      apply (induct v)
      apply (simp_all add: sparse_row_vector_cons)
      apply (frule_tac sorted_spvec_cons1, simp)
      apply (simp only: Rep_matrix_inject[symmetric])
      apply (rule ext)+
      apply auto
      apply (subgoal_tac "Rep_matrix (sparse_row_vector v) 0 a = 0")
      apply (simp)
      apply (rule sorted_sparse_row_vector_zero)
      apply auto
      done

    lemma sorted_spvec_minus_spvec:
      "sorted_spvec v ==> sorted_spvec (minus_spvec v)"
      apply (induct v)
      apply (simp)
      apply (frule sorted_spvec_cons1, simp)
      apply (simp add: sorted_spvec.simps split:list.split_asm)
      done

    lemma sorted_spvec_minus_spvec:
      "sorted_spvec v ==> sorted_spvec (minus_spvec v)"
      apply (induct v)
      apply (simp)
      apply (frule sorted_spvec_cons1, simp)
      apply (simp add: sorted_spvec.simps split:list.split_asm)
      done

    lemma sorted_spvec_abs_spvec:
      "sorted_spvec v ==> sorted_spvec (abs_spvec v)"
      apply (induct v)
      apply (simp)
      apply (frule sorted_spvec_cons1, simp)
      apply (simp add: sorted_spvec.simps split:list.split_asm)
      done

    defs
      smult_spvec_def: "smult_spvec y arr == map (% a. (fst a, y * snd a)) arr"

    lemma smult_spvec_empty[simp]: "smult_spvec y [] = []"
      by (simp add: smult_spvec_def)

    lemma smult_spvec_cons: "smult_spvec y (a#arr) = (fst a, y * (snd a)) # (smult_spvec y arr)"
      by (simp add: smult_spvec_def)

    recdef addmult_spvec "measure (% (y, a, b). length a + (length b))"
      "addmult_spvec (y, arr, []) = arr"
      "addmult_spvec (y, [], brr) = smult_spvec y brr"
      "addmult_spvec (y, a#arr, b#brr) = (
        if (fst a) < (fst b) then (a#(addmult_spvec (y, arr, b#brr)))
        else (if (fst b < fst a) then ((fst b, y * (snd b))#(addmult_spvec (y, a#arr, brr)))
        else ((fst a, (snd a)+ y*(snd b))#(addmult_spvec (y, arr,brr)))))"

    lemma addmult_spvec_empty1[simp]: "addmult_spvec (y, [], a) = smult_spvec y a"
      by (induct a, auto)

    lemma addmult_spvec_empty2[simp]: "addmult_spvec (y, a, []) = a"
      by (induct a, auto)

    lemma sparse_row_vector_map: "(! x y. f (x+y) = (f x) + (f y)) ==> (f::'a=>('a::lordered_ring)) 0 = 0 ==>
      sparse_row_vector (map (% x. (fst x, f (snd x))) a) = apply_matrix f (sparse_row_vector a)"
      apply (induct a)
      apply (simp_all add: apply_matrix_add)
      done

    lemma sparse_row_vector_smult: "sparse_row_vector (smult_spvec y a) = scalar_mult y (sparse_row_vector a)"
      apply (induct a)
      apply (simp_all add: smult_spvec_cons scalar_mult_add)
      done

    lemma sparse_row_vector_addmult_spvec: "sparse_row_vector (addmult_spvec (y::'a::lordered_ring, a, b)) =
      (sparse_row_vector a) + (scalar_mult y (sparse_row_vector b))"
      apply (rule addmult_spvec.induct[of _ y])
      apply (simp add: scalar_mult_add smult_spvec_cons sparse_row_vector_smult singleton_matrix_add)+
      done

    lemma sorted_smult_spvec[rule_format]: "sorted_spvec a ==> sorted_spvec (smult_spvec y a)"
      apply (auto simp add: smult_spvec_def)
      apply (induct a)
      apply (auto simp add: sorted_spvec.simps split:list.split_asm)
      done

    lemma sorted_spvec_addmult_spvec_helper: "[|sorted_spvec (addmult_spvec (y, (a, b) # arr, brr)); aa < a; sorted_spvec ((a, b) # arr);
      sorted_spvec ((aa, ba) # brr)|] ==> sorted_spvec ((aa, y * ba) # addmult_spvec (y, (a, b) # arr, brr))"
      apply (induct brr)
      apply (auto simp add: sorted_spvec.simps)
      apply (simp split: list.split)
      apply (auto)
      apply (simp split: list.split)
      apply (auto)
      done

    lemma sorted_spvec_addmult_spvec_helper2:
     "[|sorted_spvec (addmult_spvec (y, arr, (aa, ba) # brr)); a < aa; sorted_spvec ((a, b) # arr); sorted_spvec ((aa, ba) # brr)|]
           ==> sorted_spvec ((a, b) # addmult_spvec (y, arr, (aa, ba) # brr))"
      apply (induct arr)
      apply (auto simp add: smult_spvec_def sorted_spvec.simps)
      apply (simp split: list.split)
      apply (auto)
      done

    lemma sorted_spvec_addmult_spvec_helper3[rule_format]:
      "sorted_spvec (addmult_spvec (y, arr, brr)) --> sorted_spvec ((aa, b) # arr) --> sorted_spvec ((aa, ba) # brr)
         --> sorted_spvec ((aa, b + y * ba) # (addmult_spvec (y, arr, brr)))"
      apply (rule addmult_spvec.induct[of _ y arr brr])
      apply (simp_all add: sorted_spvec.simps smult_spvec_def)
      done

    lemma sorted_addmult_spvec[rule_format]: "sorted_spvec a --> sorted_spvec b --> sorted_spvec (addmult_spvec (y, a, b))"
      apply (rule addmult_spvec.induct[of _ y a b])
      apply (simp_all add: sorted_smult_spvec)
      apply (rule conjI, intro strip)
      apply (case_tac "~(a < aa)")
      apply (simp_all)
      apply (frule_tac as=brr in sorted_spvec_cons1)
      apply (simp add: sorted_spvec_addmult_spvec_helper)
      apply (intro strip | rule conjI)+
      apply (frule_tac as=arr in sorted_spvec_cons1)
      apply (simp add: sorted_spvec_addmult_spvec_helper2)
      apply (intro strip)
      apply (frule_tac as=arr in sorted_spvec_cons1)
      apply (frule_tac as=brr in sorted_spvec_cons1)
      apply (simp)
      apply (simp_all add: sorted_spvec_addmult_spvec_helper3)
      done

    consts
      mult_spvec_spmat :: "('a::lordered_ring) spvec * 'a spvec * 'a spmat  => 'a spvec"

    recdef mult_spvec_spmat "measure (% (c, arr, brr). (length arr) + (length brr))"
      "mult_spvec_spmat (c, [], brr) = c"
      "mult_spvec_spmat (c, arr, []) = c"
      "mult_spvec_spmat (c, a#arr, b#brr) = (
         if ((fst a) < (fst b)) then (mult_spvec_spmat (c, arr, b#brr))
         else (if ((fst b) < (fst a)) then (mult_spvec_spmat (c, a#arr, brr))
         else (mult_spvec_spmat (addmult_spvec (snd a, c, snd b), arr, brr))))"

    lemma sparse_row_mult_spvec_spmat[rule_format]: "sorted_spvec (a::('a::lordered_ring) spvec) --> sorted_spvec B -->
      sparse_row_vector (mult_spvec_spmat (c, a, B)) = (sparse_row_vector c) + (sparse_row_vector a) * (sparse_row_matrix B)"
    proof -
      have comp_1: "!! a b. a < b ==> Suc 0 <= nat ((int b)-(int a))" by arith
      have not_iff: "!! a b. a = b ==> (~ a) = (~ b)" by simp
      have max_helper: "!! a b. ~ (a <= max (Suc a) b) ==> False"
        by arith
      {
        fix a
        fix v
        assume a:"a < nrows(sparse_row_vector v)"
        have b:"nrows(sparse_row_vector v) <= 1" by simp
        note dummy = less_le_trans[of a "nrows (sparse_row_vector v)" 1, OF a b]
        then have "a = 0" by simp
      }
      note nrows_helper = this
      show ?thesis
        apply (rule mult_spvec_spmat.induct)
        apply simp+
        apply (rule conjI)
        apply (intro strip)
        apply (frule_tac as=brr in sorted_spvec_cons1)
        apply (simp add: ring_eq_simps sparse_row_matrix_cons)
        apply (simplesubst Rep_matrix_zero_imp_mult_zero)
        apply (simp)
        apply (intro strip)
        apply (rule disjI2)
        apply (intro strip)
        apply (subst nrows)
        apply (rule  order_trans[of _ 1])
        apply (simp add: comp_1)+
        apply (subst Rep_matrix_zero_imp_mult_zero)
        apply (intro strip)
        apply (case_tac "k <= aa")
        apply (rule_tac m1 = k and n1 = a and a1 = b in ssubst[OF sorted_sparse_row_vector_zero])
        apply (simp_all)
        apply (rule impI)
        apply (rule disjI2)
        apply (rule nrows)
        apply (rule order_trans[of _ 1])
        apply (simp_all add: comp_1)

        apply (intro strip | rule conjI)+
        apply (frule_tac as=arr in sorted_spvec_cons1)
        apply (simp add: ring_eq_simps)
        apply (subst Rep_matrix_zero_imp_mult_zero)
        apply (simp)
        apply (rule disjI2)
        apply (intro strip)
        apply (simp add: sparse_row_matrix_cons neg_def)
        apply (case_tac "a <= aa")
        apply (erule sorted_sparse_row_matrix_zero)
        apply (simp_all)
        apply (intro strip)
        apply (case_tac "a=aa")
        apply (simp_all)
        apply (frule_tac as=arr in sorted_spvec_cons1)
        apply (frule_tac as=brr in sorted_spvec_cons1)
        apply (simp add: sparse_row_matrix_cons ring_eq_simps sparse_row_vector_addmult_spvec)
        apply (rule_tac B1 = "sparse_row_matrix brr" in ssubst[OF Rep_matrix_zero_imp_mult_zero])
        apply (auto)
        apply (rule sorted_sparse_row_matrix_zero)
        apply (simp_all)
        apply (rule_tac A1 = "sparse_row_vector arr" in ssubst[OF Rep_matrix_zero_imp_mult_zero])
        apply (auto)
        apply (rule_tac m=k and n = aa and a = b and arr=arr in sorted_sparse_row_vector_zero)
        apply (simp_all)
        apply (simp add: neg_def)
        apply (drule nrows_notzero)
        apply (drule nrows_helper)
        apply (arith)

        apply (subst Rep_matrix_inject[symmetric])
        apply (rule ext)+
        apply (simp)
        apply (subst Rep_matrix_mult)
        apply (rule_tac j1=aa in ssubst[OF foldseq_almostzero])
        apply (simp_all)
        apply (intro strip, rule conjI)
        apply (intro strip)
        apply (drule_tac max_helper)
        apply (simp)
        apply (auto)
        apply (rule zero_imp_mult_zero)
        apply (rule disjI2)
        apply (rule nrows)
        apply (rule order_trans[of _ 1])
        apply (simp)
        apply (simp)
        done
    qed

    lemma sorted_mult_spvec_spmat[rule_format]:
      "sorted_spvec (c::('a::lordered_ring) spvec) --> sorted_spmat B --> sorted_spvec (mult_spvec_spmat (c, a, B))"
      apply (rule mult_spvec_spmat.induct[of _ c a B])
      apply (simp_all add: sorted_addmult_spvec)
      done

    consts
      mult_spmat :: "('a::lordered_ring) spmat => 'a spmat => 'a spmat"

    primrec
      "mult_spmat [] A = []"
      "mult_spmat (a#as) A = (fst a, mult_spvec_spmat ([], snd a, A))#(mult_spmat as A)"

    lemma sparse_row_mult_spmat[rule_format]:
      "sorted_spmat A --> sorted_spvec B --> sparse_row_matrix (mult_spmat A B) = (sparse_row_matrix A) * (sparse_row_matrix B)"
      apply (induct A)
      apply (auto simp add: sparse_row_matrix_cons sparse_row_mult_spvec_spmat ring_eq_simps move_matrix_mult)
      done

    lemma sorted_spvec_mult_spmat[rule_format]:
      "sorted_spvec (A::('a::lordered_ring) spmat) --> sorted_spvec (mult_spmat A B)"
      apply (induct A)
      apply (auto)
      apply (drule sorted_spvec_cons1, simp)
      apply (case_tac A)
      apply (auto simp add: sorted_spvec.simps)
      done

    lemma sorted_spmat_mult_spmat[rule_format]:
      "sorted_spmat (B::('a::lordered_ring) spmat) --> sorted_spmat (mult_spmat A B)"
      apply (induct A)
      apply (auto simp add: sorted_mult_spvec_spmat)
      done

    consts
      add_spvec :: "('a::lordered_ab_group) spvec * 'a spvec => 'a spvec"
      add_spmat :: "('a::lordered_ab_group) spmat * 'a spmat => 'a spmat"

    recdef add_spvec "measure (% (a, b). length a + (length b))"
      "add_spvec (arr, []) = arr"
      "add_spvec ([], brr) = brr"
      "add_spvec (a#arr, b#brr) = (
      if (fst a) < (fst b) then (a#(add_spvec (arr, b#brr)))
         else (if (fst b < fst a) then (b#(add_spvec (a#arr, brr)))
         else ((fst a, (snd a)+(snd b))#(add_spvec (arr,brr)))))"

    lemma add_spvec_empty1[simp]: "add_spvec ([], a) = a"
      by (induct a, auto)

    lemma add_spvec_empty2[simp]: "add_spvec (a, []) = a"
      by (induct a, auto)

    lemma sparse_row_vector_add: "sparse_row_vector (add_spvec (a,b)) = (sparse_row_vector a) + (sparse_row_vector b)"
      apply (rule add_spvec.induct[of _ a b])
      apply (simp_all add: singleton_matrix_add)
      done

    recdef add_spmat "measure (% (A,B). (length A)+(length B))"
      "add_spmat ([], bs) = bs"
      "add_spmat (as, []) = as"
      "add_spmat (a#as, b#bs) = (
      if fst a < fst b then
        (a#(add_spmat (as, b#bs)))
      else (if fst b < fst a then
        (b#(add_spmat (a#as, bs)))
      else
        ((fst a, add_spvec (snd a, snd b))#(add_spmat (as, bs)))))"

    lemma sparse_row_add_spmat: "sparse_row_matrix (add_spmat (A, B)) = (sparse_row_matrix A) + (sparse_row_matrix B)"
      apply (rule add_spmat.induct)
      apply (auto simp add: sparse_row_matrix_cons sparse_row_vector_add move_matrix_add)
      done

    lemma sorted_add_spvec_helper1[rule_format]: "add_spvec ((a,b)#arr, brr) = (ab, bb) # list --> (ab = a | (brr ≠ [] & ab = fst (hd brr)))"
      proof -
        have "(! x ab a. x = (a,b)#arr --> add_spvec (x, brr) = (ab, bb) # list --> (ab = a | (ab = fst (hd brr))))"
          by (rule add_spvec.induct[of _ _ brr], auto)
        then show ?thesis
          by (case_tac brr, auto)
      qed

    lemma sorted_add_spmat_helper1[rule_format]: "add_spmat ((a,b)#arr, brr) = (ab, bb) # list --> (ab = a | (brr ≠ [] & ab = fst (hd brr)))"
      proof -
        have "(! x ab a. x = (a,b)#arr --> add_spmat (x, brr) = (ab, bb) # list --> (ab = a | (ab = fst (hd brr))))"
          by (rule add_spmat.induct[of _ _ brr], auto)
        then show ?thesis
          by (case_tac brr, auto)
      qed

    lemma sorted_add_spvec_helper[rule_format]: "add_spvec (arr, brr) = (ab, bb) # list --> ((arr ≠ [] & ab = fst (hd arr)) | (brr ≠ [] & ab = fst (hd brr)))"
      apply (rule add_spvec.induct[of _ arr brr])
      apply (auto)
      done

    lemma sorted_add_spmat_helper[rule_format]: "add_spmat (arr, brr) = (ab, bb) # list --> ((arr ≠ [] & ab = fst (hd arr)) | (brr ≠ [] & ab = fst (hd brr)))"
      apply (rule add_spmat.induct[of _ arr brr])
      apply (auto)
      done

    lemma add_spvec_commute: "add_spvec (a, b) = add_spvec (b, a)"
      by (rule add_spvec.induct[of _ a b], auto)

    lemma add_spmat_commute: "add_spmat (a, b) = add_spmat (b, a)"
      apply (rule add_spmat.induct[of _ a b])
      apply (simp_all add: add_spvec_commute)
      done

    lemma sorted_add_spvec_helper2: "add_spvec ((a,b)#arr, brr) = (ab, bb) # list ==> aa < a ==> sorted_spvec ((aa, ba) # brr) ==> aa < ab"
      apply (drule sorted_add_spvec_helper1)
      apply (auto)
      apply (case_tac brr)
      apply (simp_all)
      apply (drule_tac sorted_spvec_cons3)
      apply (simp)
      done

    lemma sorted_add_spmat_helper2: "add_spmat ((a,b)#arr, brr) = (ab, bb) # list ==> aa < a ==> sorted_spvec ((aa, ba) # brr) ==> aa < ab"
      apply (drule sorted_add_spmat_helper1)
      apply (auto)
      apply (case_tac brr)
      apply (simp_all)
      apply (drule_tac sorted_spvec_cons3)
      apply (simp)
      done

    lemma sorted_spvec_add_spvec[rule_format]: "sorted_spvec a --> sorted_spvec b --> sorted_spvec (add_spvec (a, b))"
      apply (rule add_spvec.induct[of _ a b])
      apply (simp_all)
      apply (rule conjI)
      apply (intro strip)
      apply (simp)
      apply (frule_tac as=brr in sorted_spvec_cons1)
      apply (simp)
      apply (subst sorted_spvec_step)
      apply (simp split: list.split)
      apply (clarify, simp)
      apply (simp add: sorted_add_spvec_helper2)
      apply (clarify)
      apply (rule conjI)
      apply (case_tac "a=aa")
      apply (simp)
      apply (clarify)
      apply (frule_tac as=arr in sorted_spvec_cons1, simp)
      apply (subst sorted_spvec_step)
      apply (simp split: list.split)
      apply (clarify, simp)
      apply (simp add: sorted_add_spvec_helper2 add_spvec_commute)
      apply (case_tac "a=aa")
      apply (simp_all)
      apply (clarify)
      apply (frule_tac as=arr in sorted_spvec_cons1)
      apply (frule_tac as=brr in sorted_spvec_cons1)
      apply (simp)
      apply (subst sorted_spvec_step)
      apply (simp split: list.split)
      apply (clarify, simp)
      apply (drule_tac sorted_add_spvec_helper)
      apply (auto)
      apply (case_tac arr)
      apply (simp_all)
      apply (drule sorted_spvec_cons3)
      apply (simp)
      apply (case_tac brr)
      apply (simp_all)
      apply (drule sorted_spvec_cons3)
      apply (simp)
      done

    lemma sorted_spvec_add_spmat[rule_format]: "sorted_spvec A --> sorted_spvec B --> sorted_spvec (add_spmat (A, B))"
      apply (rule add_spmat.induct[of _ A B])
      apply (simp_all)
      apply (rule conjI)
      apply (intro strip)
      apply (simp)
      apply (frule_tac as=bs in sorted_spvec_cons1)
      apply (simp)
      apply (subst sorted_spvec_step)
      apply (simp split: list.split)
      apply (clarify, simp)
      apply (simp add: sorted_add_spmat_helper2)
      apply (clarify)
      apply (rule conjI)
      apply (case_tac "a=aa")
      apply (simp)
      apply (clarify)
      apply (frule_tac as=as in sorted_spvec_cons1, simp)
      apply (subst sorted_spvec_step)
      apply (simp split: list.split)
      apply (clarify, simp)
      apply (simp add: sorted_add_spmat_helper2 add_spmat_commute)
      apply (case_tac "a=aa")
      apply (simp_all)
      apply (clarify)
      apply (frule_tac as=as in sorted_spvec_cons1)
      apply (frule_tac as=bs in sorted_spvec_cons1)
      apply (simp)
      apply (subst sorted_spvec_step)
      apply (simp split: list.split)
      apply (clarify, simp)
      apply (drule_tac sorted_add_spmat_helper)
      apply (auto)
      apply (case_tac as)
      apply (simp_all)
      apply (drule sorted_spvec_cons3)
      apply (simp)
      apply (case_tac bs)
      apply (simp_all)
      apply (drule sorted_spvec_cons3)
      apply (simp)
      done

    lemma sorted_spmat_add_spmat[rule_format]: "sorted_spmat A --> sorted_spmat B --> sorted_spmat (add_spmat (A, B))"
      apply (rule add_spmat.induct[of _ A B])
      apply (simp_all add: sorted_spvec_add_spvec)
      done

    consts
      le_spvec :: "('a::lordered_ab_group) spvec * 'a spvec => bool"
      le_spmat :: "('a::lordered_ab_group) spmat * 'a spmat => bool"

    recdef le_spvec "measure (% (a,b). (length a) + (length b))"
      "le_spvec ([], []) = True"
      "le_spvec (a#as, []) = ((snd a <= 0) & (le_spvec (as, [])))"
      "le_spvec ([], b#bs) = ((0 <= snd b) & (le_spvec ([], bs)))"
      "le_spvec (a#as, b#bs) = (
      if (fst a < fst b) then
        ((snd a <= 0) & (le_spvec (as, b#bs)))
      else (if (fst b < fst a) then
        ((0 <= snd b) & (le_spvec (a#as, bs)))
      else
        ((snd a <= snd b) & (le_spvec (as, bs)))))"

    recdef le_spmat "measure (% (a,b). (length a) + (length b))"
      "le_spmat ([], []) = True"
      "le_spmat (a#as, []) = (le_spvec (snd a, []) & (le_spmat (as, [])))"
      "le_spmat ([], b#bs) = (le_spvec ([], snd b) & (le_spmat ([], bs)))"
      "le_spmat (a#as, b#bs) = (
      if fst a < fst b then
        (le_spvec(snd a,[]) & le_spmat(as, b#bs))
      else (if (fst b < fst a) then
        (le_spvec([], snd b) & le_spmat(a#as, bs))
      else
        (le_spvec(snd a, snd b) & le_spmat (as, bs))))"

    constdefs
      disj_matrices :: "('a::zero) matrix => 'a matrix => bool"
      "disj_matrices A B == (! j i. (Rep_matrix A j i ≠ 0) --> (Rep_matrix B j i = 0)) & (! j i. (Rep_matrix B j i ≠ 0) --> (Rep_matrix A j i = 0))"

    ML {* simp_depth_limit := 6 *}

    lemma disj_matrices_contr1: "disj_matrices A B ==> Rep_matrix A j i ≠ 0 ==> Rep_matrix B j i = 0"
       by (simp add: disj_matrices_def)

    lemma disj_matrices_contr2: "disj_matrices A B ==> Rep_matrix B j i ≠ 0 ==> Rep_matrix A j i = 0"
       by (simp add: disj_matrices_def)

    lemma disj_matrices_add: "disj_matrices A B ==> disj_matrices C D ==> disj_matrices A D ==> disj_matrices B C ==>
      (A + B <= C + D) = (A <= C & B <= (D::('a::lordered_ab_group) matrix))"
      apply (auto)
      apply (simp (no_asm_use) only: le_matrix_def disj_matrices_def)
      apply (intro strip)
      apply (erule conjE)+
      apply (drule_tac j=j and i=i in spec2)+
      apply (case_tac "Rep_matrix B j i = 0")
      apply (case_tac "Rep_matrix D j i = 0")
      apply (simp_all)
      apply (simp (no_asm_use) only: le_matrix_def disj_matrices_def)
      apply (intro strip)
      apply (erule conjE)+
      apply (drule_tac j=j and i=i in spec2)+
      apply (case_tac "Rep_matrix A j i = 0")
      apply (case_tac "Rep_matrix C j i = 0")
      apply (simp_all)
      apply (erule add_mono)
      apply (assumption)
      done

    lemma disj_matrices_zero1[simp]: "disj_matrices 0 B"
    by (simp add: disj_matrices_def)

    lemma disj_matrices_zero2[simp]: "disj_matrices A 0"
    by (simp add: disj_matrices_def)

    lemma disj_matrices_commute: "disj_matrices A B = disj_matrices B A"
    by (auto simp add: disj_matrices_def)

    lemma disj_matrices_add_le_zero: "disj_matrices A B ==>
      (A + B <= 0) = (A <= 0 & (B::('a::lordered_ab_group) matrix) <= 0)"
    by (rule disj_matrices_add[of A B 0 0, simplified])

    lemma disj_matrices_add_zero_le: "disj_matrices A B ==>
      (0 <= A + B) = (0 <= A & 0 <= (B::('a::lordered_ab_group) matrix))"
    by (rule disj_matrices_add[of 0 0 A B, simplified])

    lemma disj_matrices_add_x_le: "disj_matrices A B ==> disj_matrices B C ==>
      (A <= B + C) = (A <= C & 0 <= (B::('a::lordered_ab_group) matrix))"
    by (auto simp add: disj_matrices_add[of 0 A B C, simplified])

    lemma disj_matrices_add_le_x: "disj_matrices A B ==> disj_matrices B C ==>
      (B + A <= C) = (A <= C &  (B::('a::lordered_ab_group) matrix) <= 0)"
    by (auto simp add: disj_matrices_add[of B A 0 C,simplified] disj_matrices_commute)

    lemma disj_sparse_row_singleton: "i <= j ==> sorted_spvec((j,y)#v) ==> disj_matrices (sparse_row_vector v) (singleton_matrix 0 i x)"
      apply (simp add: disj_matrices_def)
      apply (rule conjI)
      apply (rule neg_imp)
      apply (simp)
      apply (intro strip)
      apply (rule sorted_sparse_row_vector_zero)
      apply (simp_all)
      apply (intro strip)
      apply (rule sorted_sparse_row_vector_zero)
      apply (simp_all)
      done

    lemma disj_matrices_x_add: "disj_matrices A B ==> disj_matrices A C ==> disj_matrices (A::('a::lordered_ab_group) matrix) (B+C)"
      apply (simp add: disj_matrices_def)
      apply (auto)
      apply (drule_tac j=j and i=i in spec2)+
      apply (case_tac "Rep_matrix B j i = 0")
      apply (case_tac "Rep_matrix C j i = 0")
      apply (simp_all)
      done

    lemma disj_matrices_add_x: "disj_matrices A B ==> disj_matrices A C ==> disj_matrices (B+C) (A::('a::lordered_ab_group) matrix)"
      by (simp add: disj_matrices_x_add disj_matrices_commute)

    lemma disj_singleton_matrices[simp]: "disj_matrices (singleton_matrix j i x) (singleton_matrix u v y) = (j ≠ u | i ≠ v | x = 0 | y = 0)"
      by (auto simp add: disj_matrices_def)

    lemma disj_move_sparse_vec_mat[simplified disj_matrices_commute]:
      "j <= a ==> sorted_spvec((a,c)#as) ==> disj_matrices (move_matrix (sparse_row_vector b) (int j) i) (sparse_row_matrix as)"
      apply (auto simp add: neg_def disj_matrices_def)
      apply (drule nrows_notzero)
      apply (drule less_le_trans[OF _ nrows_spvec])
      apply (subgoal_tac "ja = j")
      apply (simp add: sorted_sparse_row_matrix_zero)
      apply (arith)
      apply (rule nrows)
      apply (rule order_trans[of _ 1 _])
      apply (simp)
      apply (case_tac "nat (int ja - int j) = 0")
      apply (case_tac "ja = j")
      apply (simp add: sorted_sparse_row_matrix_zero)
      apply arith+
      done

    lemma disj_move_sparse_row_vector_twice:
      "j ≠ u ==> disj_matrices (move_matrix (sparse_row_vector a) j i) (move_matrix (sparse_row_vector b) u v)"
      apply (auto simp add: neg_def disj_matrices_def)
      apply (rule nrows, rule order_trans[of _ 1], simp, drule nrows_notzero, drule less_le_trans[OF _ nrows_spvec], arith)+
      done

    lemma le_spvec_iff_sparse_row_le[rule_format]: "(sorted_spvec a) --> (sorted_spvec b) --> (le_spvec (a,b)) = (sparse_row_vector a <= sparse_row_vector b)"
      apply (rule le_spvec.induct)
      apply (simp_all add: sorted_spvec_cons1 disj_matrices_add_le_zero disj_matrices_add_zero_le
        disj_sparse_row_singleton[OF order_refl] disj_matrices_commute)
      apply (rule conjI, intro strip)
      apply (simp add: sorted_spvec_cons1)
      apply (subst disj_matrices_add_x_le)
      apply (simp add: disj_sparse_row_singleton[OF less_imp_le] disj_matrices_x_add disj_matrices_commute)
      apply (simp add: disj_sparse_row_singleton[OF order_refl] disj_matrices_commute)
      apply (simp, blast)
      apply (intro strip, rule conjI, intro strip)
      apply (simp add: sorted_spvec_cons1)
      apply (subst disj_matrices_add_le_x)
      apply (simp_all add: disj_sparse_row_singleton[OF order_refl] disj_sparse_row_singleton[OF less_imp_le] disj_matrices_commute disj_matrices_x_add)
      apply (blast)
      apply (intro strip)
      apply (simp add: sorted_spvec_cons1)
      apply (case_tac "a=aa", simp_all)
      apply (subst disj_matrices_add)
      apply (simp_all add: disj_sparse_row_singleton[OF order_refl] disj_matrices_commute)
      done

    lemma le_spvec_empty2_sparse_row[rule_format]: "(sorted_spvec b) --> (le_spvec (b,[]) = (sparse_row_vector b <= 0))"
      apply (induct b)
      apply (simp_all add: sorted_spvec_cons1)
      apply (intro strip)
      apply (subst disj_matrices_add_le_zero)
      apply (simp add: disj_matrices_commute disj_sparse_row_singleton sorted_spvec_cons1)
      apply (rule_tac y = "snd a" in disj_sparse_row_singleton[OF order_refl])
      apply (simp_all)
      done

    lemma le_spvec_empty1_sparse_row[rule_format]: "(sorted_spvec b) --> (le_spvec ([],b) = (0 <= sparse_row_vector b))"
      apply (induct b)
      apply (simp_all add: sorted_spvec_cons1)
      apply (intro strip)
      apply (subst disj_matrices_add_zero_le)
      apply (simp add: disj_matrices_commute disj_sparse_row_singleton sorted_spvec_cons1)
      apply (rule_tac y = "snd a" in disj_sparse_row_singleton[OF order_refl])
      apply (simp_all)
      done

    lemma le_spmat_iff_sparse_row_le[rule_format]: "(sorted_spvec A) --> (sorted_spmat A) --> (sorted_spvec B) --> (sorted_spmat B) -->
      le_spmat(A, B) = (sparse_row_matrix A <= sparse_row_matrix B)"
      apply (rule le_spmat.induct)
      apply (simp add: sparse_row_matrix_cons disj_matrices_add_le_zero disj_matrices_add_zero_le disj_move_sparse_vec_mat[OF order_refl]
        disj_matrices_commute sorted_spvec_cons1 le_spvec_empty2_sparse_row le_spvec_empty1_sparse_row)+
      apply (rule conjI, intro strip)
      apply (simp add: sorted_spvec_cons1)
      apply (subst disj_matrices_add_x_le)
      apply (rule disj_matrices_add_x)
      apply (simp add: disj_move_sparse_row_vector_twice)
      apply (simp add: disj_move_sparse_vec_mat[OF less_imp_le] disj_matrices_commute)
      apply (simp add: disj_move_sparse_vec_mat[OF order_refl] disj_matrices_commute)
      apply (simp, blast)
      apply (intro strip, rule conjI, intro strip)
      apply (simp add: sorted_spvec_cons1)
      apply (subst disj_matrices_add_le_x)
      apply (simp add: disj_move_sparse_vec_mat[OF order_refl])
      apply (rule disj_matrices_x_add)
      apply (simp add: disj_move_sparse_row_vector_twice)
      apply (simp add: disj_move_sparse_vec_mat[OF less_imp_le] disj_matrices_commute)
      apply (simp, blast)
      apply (intro strip)
      apply (case_tac "a=aa")
      apply (simp_all)
      apply (subst disj_matrices_add)
      apply (simp_all add: disj_matrices_commute disj_move_sparse_vec_mat[OF order_refl])
      apply (simp add: sorted_spvec_cons1 le_spvec_iff_sparse_row_le)
      done

    ML {* simp_depth_limit := 999 *}

    consts
       abs_spmat :: "('a::lordered_ring) spmat => 'a spmat"
       minus_spmat :: "('a::lordered_ring) spmat => 'a spmat"

    primrec
      "abs_spmat [] = []"
      "abs_spmat (a#as) = (fst a, abs_spvec (snd a))#(abs_spmat as)"

    primrec
      "minus_spmat [] = []"
      "minus_spmat (a#as) = (fst a, minus_spvec (snd a))#(minus_spmat as)"

    lemma sparse_row_matrix_minus:
      "sparse_row_matrix (minus_spmat A) = - (sparse_row_matrix A)"
      apply (induct A)
      apply (simp_all add: sparse_row_vector_minus sparse_row_matrix_cons)
      apply (subst Rep_matrix_inject[symmetric])
      apply (rule ext)+
      apply simp
      done

    lemma Rep_sparse_row_vector_zero: "x ≠ 0 ==> Rep_matrix (sparse_row_vector v) x y = 0"
    proof -
      assume x:"x ≠ 0"
      have r:"nrows (sparse_row_vector v) <= Suc 0" by (rule nrows_spvec)
      show ?thesis
        apply (rule nrows)
        apply (subgoal_tac "Suc 0 <= x")
        apply (insert r)
        apply (simp only:)
        apply (insert x)
        apply arith
        done
    qed

    lemma sparse_row_matrix_abs:
      "sorted_spvec A ==> sorted_spmat A ==> sparse_row_matrix (abs_spmat A) = abs (sparse_row_matrix A)"
      apply (induct A)
      apply (simp_all add: sparse_row_vector_abs sparse_row_matrix_cons)
      apply (frule_tac sorted_spvec_cons1, simp)
      apply (simplesubst Rep_matrix_inject[symmetric])
      apply (rule ext)+
      apply auto
      apply (case_tac "x=a")
      apply (simp)
      apply (simplesubst sorted_sparse_row_matrix_zero)
      apply auto
      apply (simplesubst Rep_sparse_row_vector_zero)
      apply (simp_all add: neg_def)
      done

    lemma sorted_spvec_minus_spmat: "sorted_spvec A ==> sorted_spvec (minus_spmat A)"
      apply (induct A)
      apply (simp)
      apply (frule sorted_spvec_cons1, simp)
      apply (simp add: sorted_spvec.simps split:list.split_asm)
      done

    lemma sorted_spvec_abs_spmat: "sorted_spvec A ==> sorted_spvec (abs_spmat A)"
      apply (induct A)
      apply (simp)
      apply (frule sorted_spvec_cons1, simp)
      apply (simp add: sorted_spvec.simps split:list.split_asm)
      done

    lemma sorted_spmat_minus_spmat: "sorted_spmat A ==> sorted_spmat (minus_spmat A)"
      apply (induct A)
      apply (simp_all add: sorted_spvec_minus_spvec)
      done

    lemma sorted_spmat_abs_spmat: "sorted_spmat A ==> sorted_spmat (abs_spmat A)"
      apply (induct A)
      apply (simp_all add: sorted_spvec_abs_spvec)
      done

    constdefs
      diff_spmat :: "('a::lordered_ring) spmat => 'a spmat => 'a spmat"
      "diff_spmat A B == add_spmat (A, minus_spmat B)"

    lemma sorted_spmat_diff_spmat: "sorted_spmat A ==> sorted_spmat B ==> sorted_spmat (diff_spmat A B)"
      by (simp add: diff_spmat_def sorted_spmat_minus_spmat sorted_spmat_add_spmat)

    lemma sorted_spvec_diff_spmat: "sorted_spvec A ==> sorted_spvec B ==> sorted_spvec (diff_spmat A B)"
      by (simp add: diff_spmat_def sorted_spvec_minus_spmat sorted_spvec_add_spmat)

    lemma sparse_row_diff_spmat: "sparse_row_matrix (diff_spmat A B ) = (sparse_row_matrix A) - (sparse_row_matrix B)"
      by (simp add: diff_spmat_def sparse_row_add_spmat sparse_row_matrix_minus)

    constdefs
      sorted_sparse_matrix :: "'a spmat => bool"
      "sorted_sparse_matrix A == (sorted_spvec A) & (sorted_spmat A)"

    lemma sorted_sparse_matrix_imp_spvec: "sorted_sparse_matrix A ==> sorted_spvec A"
      by (simp add: sorted_sparse_matrix_def)

    lemma sorted_sparse_matrix_imp_spmat: "sorted_sparse_matrix A ==> sorted_spmat A"
      by (simp add: sorted_sparse_matrix_def)

    lemmas sorted_sp_simps =
      sorted_spvec.simps
      sorted_spmat.simps
      sorted_sparse_matrix_def

    lemma bool1: "(¬ True) = False"  by blast
    lemma bool2: "(¬ False) = True"  by blast
    lemma bool3: "((P::bool) ∧ True) = P" by blast
    lemma bool4: "(True ∧ (P::bool)) = P" by blast
    lemma bool5: "((P::bool) ∧ False) = False" by blast
    lemma bool6: "(False ∧ (P::bool)) = False" by blast
    lemma bool7: "((P::bool) ∨ True) = True" by blast
    lemma bool8: "(True ∨ (P::bool)) = True" by blast
    lemma bool9: "((P::bool) ∨ False) = P" by blast
    lemma bool10: "(False ∨ (P::bool)) = P" by blast
    lemmas boolarith = bool1 bool2 bool3 bool4 bool5 bool6 bool7 bool8 bool9 bool10

    lemma if_case_eq: "(if b then x else y) = (case b of True => x | False => y)" by simp

    consts
      pprt_spvec :: "('a::{lordered_ab_group}) spvec => 'a spvec"
      nprt_spvec :: "('a::{lordered_ab_group}) spvec => 'a spvec"
      pprt_spmat :: "('a::{lordered_ab_group}) spmat => 'a spmat"
      nprt_spmat :: "('a::{lordered_ab_group}) spmat => 'a spmat"

    primrec
      "pprt_spvec [] = []"
      "pprt_spvec (a#as) = (fst a, pprt (snd a)) # (pprt_spvec as)"

    primrec
      "nprt_spvec [] = []"
      "nprt_spvec (a#as) = (fst a, nprt (snd a)) # (nprt_spvec as)"

    primrec
      "pprt_spmat [] = []"
      "pprt_spmat (a#as) = (fst a, pprt_spvec (snd a))#(pprt_spmat as)"
      (*case (pprt_spvec (snd a)) of [] => (pprt_spmat as) | y#ys => (fst a, y#ys)#(pprt_spmat as))"*)

    primrec
      "nprt_spmat [] = []"
      "nprt_spmat (a#as) = (fst a, nprt_spvec (snd a))#(nprt_spmat as)"
      (*case (nprt_spvec (snd a)) of [] => (nprt_spmat as) | y#ys => (fst a, y#ys)#(nprt_spmat as))"*)

    lemma pprt_add: "disj_matrices A (B::(_::lordered_ring) matrix) ==> pprt (A+B) = pprt A + pprt B"
      apply (simp add: pprt_def join_matrix)
      apply (simp add: Rep_matrix_inject[symmetric])
      apply (rule ext)+
      apply simp
      apply (case_tac "Rep_matrix A x xa ≠ 0")
      apply (simp_all add: disj_matrices_contr1)
      done

    lemma nprt_add: "disj_matrices A (B::(_::lordered_ring) matrix) ==> nprt (A+B) = nprt A + nprt B"
      apply (simp add: nprt_def meet_matrix)
      apply (simp add: Rep_matrix_inject[symmetric])
      apply (rule ext)+
      apply simp
      apply (case_tac "Rep_matrix A x xa ≠ 0")
      apply (simp_all add: disj_matrices_contr1)
      done

    lemma pprt_singleton[simp]: "pprt (singleton_matrix j i (x::_::lordered_ring)) = singleton_matrix j i (pprt x)"
      apply (simp add: pprt_def join_matrix)
      apply (simp add: Rep_matrix_inject[symmetric])
      apply (rule ext)+
      apply simp
      done

    lemma nprt_singleton[simp]: "nprt (singleton_matrix j i (x::_::lordered_ring)) = singleton_matrix j i (nprt x)"
      apply (simp add: nprt_def meet_matrix)
      apply (simp add: Rep_matrix_inject[symmetric])
      apply (rule ext)+
      apply simp
      done

    lemma less_imp_le: "a < b ==> a <= (b::_::order)" by (simp add: less_def)

    lemma sparse_row_vector_pprt: "sorted_spvec v ==> sparse_row_vector (pprt_spvec v) = pprt (sparse_row_vector v)"
      apply (induct v)
      apply (simp_all)
      apply (frule sorted_spvec_cons1, auto)
      apply (subst pprt_add)
      apply (subst disj_matrices_commute)
      apply (rule disj_sparse_row_singleton)
      apply auto
      done

    lemma sparse_row_vector_nprt: "sorted_spvec v ==> sparse_row_vector (nprt_spvec v) = nprt (sparse_row_vector v)"
      apply (induct v)
      apply (simp_all)
      apply (frule sorted_spvec_cons1, auto)
      apply (subst nprt_add)
      apply (subst disj_matrices_commute)
      apply (rule disj_sparse_row_singleton)
      apply auto
      done

    lemma pprt_move_matrix: "pprt (move_matrix (A::('a::lordered_ring) matrix) j i) = move_matrix (pprt A) j i"
      apply (simp add: pprt_def)
      apply (simp add: join_matrix)
      apply (simp add: Rep_matrix_inject[symmetric])
      apply (rule ext)+
      apply (simp)
      done

    lemma nprt_move_matrix: "nprt (move_matrix (A::('a::lordered_ring) matrix) j i) = move_matrix (nprt A) j i"
      apply (simp add: nprt_def)
      apply (simp add: meet_matrix)
      apply (simp add: Rep_matrix_inject[symmetric])
      apply (rule ext)+
      apply (simp)
      done

    lemma sparse_row_matrix_pprt: "sorted_spvec m ==> sorted_spmat m ==> sparse_row_matrix (pprt_spmat m) = pprt (sparse_row_matrix m)"
      apply (induct m)
      apply simp
      apply simp
      apply (frule sorted_spvec_cons1)
      apply (simp add: sparse_row_matrix_cons sparse_row_vector_pprt)
      apply (subst pprt_add)
      apply (subst disj_matrices_commute)
      apply (rule disj_move_sparse_vec_mat)
      apply auto
      apply (simp add: sorted_spvec.simps)
      apply (simp split: list.split)
      apply auto
      apply (simp add: pprt_move_matrix)
      done

    lemma sparse_row_matrix_nprt: "sorted_spvec m ==> sorted_spmat m ==> sparse_row_matrix (nprt_spmat m) = nprt (sparse_row_matrix m)"
      apply (induct m)
      apply simp
      apply simp
      apply (frule sorted_spvec_cons1)
      apply (simp add: sparse_row_matrix_cons sparse_row_vector_nprt)
      apply (subst nprt_add)
      apply (subst disj_matrices_commute)
      apply (rule disj_move_sparse_vec_mat)
      apply auto
      apply (simp add: sorted_spvec.simps)
      apply (simp split: list.split)
      apply auto
      apply (simp add: nprt_move_matrix)
      done

    lemma sorted_pprt_spvec: "sorted_spvec v ==> sorted_spvec (pprt_spvec v)"
      apply (induct v)
      apply (simp)
      apply (frule sorted_spvec_cons1)
      apply simp
      apply (simp add: sorted_spvec.simps split:list.split_asm)
      done

    lemma sorted_nprt_spvec: "sorted_spvec v ==> sorted_spvec (nprt_spvec v)"
      apply (induct v)
      apply (simp)
      apply (frule sorted_spvec_cons1)
      apply simp
      apply (simp add: sorted_spvec.simps split:list.split_asm)
      done

    lemma sorted_spvec_pprt_spmat: "sorted_spvec m ==> sorted_spvec (pprt_spmat m)"
      apply (induct m)
      apply (simp)
      apply (frule sorted_spvec_cons1)
      apply simp
      apply (simp add: sorted_spvec.simps split:list.split_asm)
      done

    lemma sorted_spvec_nprt_spmat: "sorted_spvec m ==> sorted_spvec (nprt_spmat m)"
      apply (induct m)
      apply (simp)
      apply (frule sorted_spvec_cons1)
      apply simp
      apply (simp add: sorted_spvec.simps split:list.split_asm)
      done

    lemma sorted_spmat_pprt_spmat: "sorted_spmat m ==> sorted_spmat (pprt_spmat m)"
      apply (induct m)
      apply (simp_all add: sorted_pprt_spvec)
      done

    lemma sorted_spmat_nprt_spmat: "sorted_spmat m ==> sorted_spmat (nprt_spmat m)"
      apply (induct m)
      apply (simp_all add: sorted_nprt_spvec)
      done

    constdefs
      mult_est_spmat :: "('a::lordered_ring) spmat => 'a spmat => 'a spmat => 'a spmat => 'a spmat"
      "mult_est_spmat r1 r2 s1 s2 ==
      add_spmat (mult_spmat (pprt_spmat s2) (pprt_spmat r2), add_spmat (mult_spmat (pprt_spmat s1) (nprt_spmat r2),
      add_spmat (mult_spmat (nprt_spmat s2) (pprt_spmat r1), mult_spmat (nprt_spmat s1) (nprt_spmat r1))))"

    lemmas sparse_row_matrix_op_simps =
      sorted_sparse_matrix_imp_spmat sorted_sparse_matrix_imp_spvec
      sparse_row_add_spmat sorted_spvec_add_spmat sorted_spmat_add_spmat
      sparse_row_diff_spmat sorted_spvec_diff_spmat sorted_spmat_diff_spmat
      sparse_row_matrix_minus sorted_spvec_minus_spmat sorted_spmat_minus_spmat
      sparse_row_mult_spmat sorted_spvec_mult_spmat sorted_spmat_mult_spmat
      sparse_row_matrix_abs sorted_spvec_abs_spmat sorted_spmat_abs_spmat
      le_spmat_iff_sparse_row_le
      sparse_row_matrix_pprt sorted_spvec_pprt_spmat sorted_spmat_pprt_spmat
      sparse_row_matrix_nprt sorted_spvec_nprt_spmat sorted_spmat_nprt_spmat

    lemma zero_eq_Numeral0: "(0::_::number_ring) = Numeral0" by simp

    lemmas sparse_row_matrix_arith_simps[simplified zero_eq_Numeral0] =
      mult_spmat.simps mult_spvec_spmat.simps
      addmult_spvec.simps
      smult_spvec_empty smult_spvec_cons
      add_spmat.simps add_spvec.simps
      minus_spmat.simps minus_spvec.simps
      abs_spmat.simps abs_spvec.simps
      diff_spmat_def
      le_spmat.simps le_spvec.simps
      pprt_spmat.simps pprt_spvec.simps
      nprt_spmat.simps nprt_spvec.simps
      mult_est_spmat_def

    (*lemma spm_linprog_dual_estimate_1:
      assumes
      "sorted_sparse_matrix A1"
      "sorted_sparse_matrix A2"
      "sorted_sparse_matrix c1"
      "sorted_sparse_matrix c2"
      "sorted_sparse_matrix y"
      "sorted_spvec b"
      "sorted_spvec r"
      "le_spmat ([], y)"
      "A * x ≤ sparse_row_matrix (b::('a::lordered_ring) spmat)"
      "sparse_row_matrix A1 <= A"
      "A <= sparse_row_matrix A2"
      "sparse_row_matrix c1 <= c"
      "c <= sparse_row_matrix c2"
      "abs x ≤ sparse_row_matrix r"
      shows
      "c * x ≤ sparse_row_matrix (add_spmat (mult_spmat y b, mult_spmat (add_spmat (add_spmat (mult_spmat y (diff_spmat A2 A1),
      abs_spmat (diff_spmat (mult_spmat y A1) c1)), diff_spmat c2 c1)) r))"
      by (insert prems, simp add: sparse_row_matrix_op_simps linprog_dual_estimate_1[where A=A])
    *)

    lemma spm_mult_le_dual_prts:
      assumes
      "sorted_sparse_matrix A1"
      "sorted_sparse_matrix A2"
      "sorted_sparse_matrix c1"
      "sorted_sparse_matrix c2"
      "sorted_sparse_matrix y"
      "sorted_sparse_matrix r1"
      "sorted_sparse_matrix r2"
      "sorted_spvec b"
      "le_spmat ([], y)"
      "sparse_row_matrix A1 ≤ A"
      "A ≤ sparse_row_matrix A2"
      "sparse_row_matrix c1 ≤ c"
      "c ≤ sparse_row_matrix c2"
      "sparse_row_matrix r1 ≤ x"
      "x ≤ sparse_row_matrix r2"
      "A * x ≤ sparse_row_matrix (b::('a::lordered_ring) spmat)"
      shows
      "c * x ≤ sparse_row_matrix (add_spmat (mult_spmat y b,
      (let s1 = diff_spmat c1 (mult_spmat y A2); s2 = diff_spmat c2 (mult_spmat y A1) in
      add_spmat (mult_spmat (pprt_spmat s2) (pprt_spmat r2), add_spmat (mult_spmat (pprt_spmat s1) (nprt_spmat r2),
      add_spmat (mult_spmat (nprt_spmat s2) (pprt_spmat r1), mult_spmat (nprt_spmat s1) (nprt_spmat r1)))))))"
      apply (simp add: Let_def)
      apply (insert prems)
      apply (simp add: sparse_row_matrix_op_simps ring_eq_simps)
      apply (rule mult_le_dual_prts[where A=A, simplified Let_def ring_eq_simps])
      apply (auto)
      done

    lemma spm_mult_le_dual_prts_no_let:
      assumes
      "sorted_sparse_matrix A1"
      "sorted_sparse_matrix A2"
      "sorted_sparse_matrix c1"
      "sorted_sparse_matrix c2"
      "sorted_sparse_matrix y"
      "sorted_sparse_matrix r1"
      "sorted_sparse_matrix r2"
      "sorted_spvec b"
      "le_spmat ([], y)"
      "sparse_row_matrix A1 ≤ A"
      "A ≤ sparse_row_matrix A2"
      "sparse_row_matrix c1 ≤ c"
      "c ≤ sparse_row_matrix c2"
      "sparse_row_matrix r1 ≤ x"
      "x ≤ sparse_row_matrix r2"
      "A * x ≤ sparse_row_matrix (b::('a::lordered_ring) spmat)"
      shows
      "c * x ≤ sparse_row_matrix (add_spmat (mult_spmat y b,
      mult_est_spmat r1 r2 (diff_spmat c1 (mult_spmat y A2)) (diff_spmat c2 (mult_spmat y A1))))"
      by (simp add: prems mult_est_spmat_def spm_mult_le_dual_prts[where A=A, simplified Let_def])

    end

lemma sparse_row_vector_empty:

      sparse_row_vector [] = 0

lemma sparse_row_matrix_empty:

      sparse_row_matrix [] = 0

lemma foldl_distrstart:

      (!!a x y. f (g x y) a = g x (f y a)) ==> foldl f (g x y) l = g x (foldl f y l)

lemma sparse_row_vector_cons:

      sparse_row_vector (a # arr) =
      singleton_matrix 0 (fst a) (snd a) + sparse_row_vector arr

lemma sparse_row_vector_append:

      sparse_row_vector (a @ b) = sparse_row_vector a + sparse_row_vector b

lemma nrows_spvec:

      nrows (sparse_row_vector x) ≤ Suc 0

lemma sparse_row_matrix_cons:

      sparse_row_matrix (a # arr) =
      move_matrix (sparse_row_vector (snd a)) (int (fst a)) 0 + sparse_row_matrix arr

lemma sparse_row_matrix_append:

      sparse_row_matrix (arr @ brr) = sparse_row_matrix arr + sparse_row_matrix brr

lemma sorted_spvec_empty:

      sorted_spvec [] = True

lemma sorted_spvec_cons1:

      sorted_spvec (a # as) ==> sorted_spvec as

lemma sorted_spvec_cons2:

      sorted_spvec (a # b # t) ==> sorted_spvec (a # t)

lemma sorted_spvec_cons3:

      sorted_spvec (a # b # t) ==> fst a < fst b

lemma sorted_sparse_row_vector_zero:

      [| m ≤ n; sorted_spvec ((n, a) # arr) |]
      ==> Rep_matrix (sparse_row_vector arr) j m = (0::'a)

lemma sorted_sparse_row_matrix_zero:

      [| m ≤ n; sorted_spvec ((n, a) # arr) |]
      ==> Rep_matrix (sparse_row_matrix arr) m j = (0::'a)

lemma sparse_row_vector_minus:

      sparse_row_vector (minus_spvec v) = - sparse_row_vector v

lemma sparse_row_vector_abs:

      sorted_spvec v ==> sparse_row_vector (abs_spvec v) = ¦sparse_row_vector v¦

lemma sorted_spvec_minus_spvec:

      sorted_spvec v ==> sorted_spvec (minus_spvec v)

lemma sorted_spvec_minus_spvec:

      sorted_spvec v ==> sorted_spvec (minus_spvec v)

lemma sorted_spvec_abs_spvec:

      sorted_spvec v ==> sorted_spvec (abs_spvec v)

lemma smult_spvec_empty:

      smult_spvec y [] = []

lemma smult_spvec_cons:

      smult_spvec y (a # arr) = (fst a, y * snd a) # smult_spvec y arr

lemma addmult_spvec_empty1:

      addmult_spvec (y, [], a) = smult_spvec y a

lemma addmult_spvec_empty2:

      addmult_spvec (y, a, []) = a

lemma sparse_row_vector_map:

      [| ∀x y. f (x + y) = f x + f y; f (0::'a) = (0::'a) |]
      ==> sparse_row_vector (map (%x. (fst x, f (snd x))) a) =
          apply_matrix f (sparse_row_vector a)

lemma sparse_row_vector_smult:

      sparse_row_vector (smult_spvec y a) = scalar_mult y (sparse_row_vector a)

lemma sparse_row_vector_addmult_spvec:

      sparse_row_vector (addmult_spvec (y, a, b)) =
      sparse_row_vector a + scalar_mult y (sparse_row_vector b)

lemma sorted_smult_spvec:

      sorted_spvec a ==> sorted_spvec (smult_spvec y a)

lemma sorted_spvec_addmult_spvec_helper:

      [| sorted_spvec (addmult_spvec (y, (a, b) # arr, brr)); aa < a;
         sorted_spvec ((a, b) # arr); sorted_spvec ((aa, ba) # brr) |]
      ==> sorted_spvec ((aa, y * ba) # addmult_spvec (y, (a, b) # arr, brr))

lemma sorted_spvec_addmult_spvec_helper2:

      [| sorted_spvec (addmult_spvec (y, arr, (aa, ba) # brr)); a < aa;
         sorted_spvec ((a, b) # arr); sorted_spvec ((aa, ba) # brr) |]
      ==> sorted_spvec ((a, b) # addmult_spvec (y, arr, (aa, ba) # brr))

lemma sorted_spvec_addmult_spvec_helper3:

      [| sorted_spvec (addmult_spvec (y, arr, brr)); sorted_spvec ((aa, b) # arr);
         sorted_spvec ((aa, ba) # brr) |]
      ==> sorted_spvec ((aa, b + y * ba) # addmult_spvec (y, arr, brr))

lemma sorted_addmult_spvec:

      [| sorted_spvec a; sorted_spvec b |] ==> sorted_spvec (addmult_spvec (y, a, b))

lemma sparse_row_mult_spvec_spmat:

      [| sorted_spvec a; sorted_spvec B |]
      ==> sparse_row_vector (mult_spvec_spmat (c, a, B)) =
          sparse_row_vector c + sparse_row_vector a * sparse_row_matrix B

lemma sorted_mult_spvec_spmat:

      [| sorted_spvec c; sorted_spmat B |]
      ==> sorted_spvec (mult_spvec_spmat (c, a, B))

lemma sparse_row_mult_spmat:

      [| sorted_spmat A; sorted_spvec B |]
      ==> sparse_row_matrix (mult_spmat A B) =
          sparse_row_matrix A * sparse_row_matrix B

lemma sorted_spvec_mult_spmat:

      sorted_spvec A ==> sorted_spvec (mult_spmat A B)

lemma sorted_spmat_mult_spmat:

      sorted_spmat B ==> sorted_spmat (mult_spmat A B)

lemma add_spvec_empty1:

      add_spvec ([], a) = a

lemma add_spvec_empty2:

      add_spvec (a, []) = a

lemma sparse_row_vector_add:

      sparse_row_vector (add_spvec (a, b)) = sparse_row_vector a + sparse_row_vector b

lemma sparse_row_add_spmat:

      sparse_row_matrix (add_spmat (A, B)) = sparse_row_matrix A + sparse_row_matrix B

lemma sorted_add_spvec_helper1:

      add_spvec ((a, b) # arr, brr) = (ab, bb) # list
      ==> ab = a ∨ brr ≠ [] ∧ ab = fst (hd brr)

lemma sorted_add_spmat_helper1:

      add_spmat ((a, b) # arr, brr) = (ab, bb) # list
      ==> ab = a ∨ brr ≠ [] ∧ ab = fst (hd brr)

lemma sorted_add_spvec_helper:

      add_spvec (arr, brr) = (ab, bb) # list
      ==> arr ≠ [] ∧ ab = fst (hd arr) ∨ brr ≠ [] ∧ ab = fst (hd brr)

lemma sorted_add_spmat_helper:

      add_spmat (arr, brr) = (ab, bb) # list
      ==> arr ≠ [] ∧ ab = fst (hd arr) ∨ brr ≠ [] ∧ ab = fst (hd brr)

lemma add_spvec_commute:

      add_spvec (a, b) = add_spvec (b, a)

lemma add_spmat_commute:

      add_spmat (a, b) = add_spmat (b, a)

lemma sorted_add_spvec_helper2:

      [| add_spvec ((a, b) # arr, brr) = (ab, bb) # list; aa < a;
         sorted_spvec ((aa, ba) # brr) |]
      ==> aa < ab

lemma sorted_add_spmat_helper2:

      [| add_spmat ((a, b) # arr, brr) = (ab, bb) # list; aa < a;
         sorted_spvec ((aa, ba) # brr) |]
      ==> aa < ab

lemma sorted_spvec_add_spvec:

      [| sorted_spvec a; sorted_spvec b |] ==> sorted_spvec (add_spvec (a, b))

lemma sorted_spvec_add_spmat:

      [| sorted_spvec A; sorted_spvec B |] ==> sorted_spvec (add_spmat (A, B))

lemma sorted_spmat_add_spmat:

      [| sorted_spmat A; sorted_spmat B |] ==> sorted_spmat (add_spmat (A, B))

lemma disj_matrices_contr1:

      [| disj_matrices A B; Rep_matrix A j i ≠ (0::'a) |]
      ==> Rep_matrix B j i = (0::'a)

lemma disj_matrices_contr2:

      [| disj_matrices A B; Rep_matrix B j i ≠ (0::'a) |]
      ==> Rep_matrix A j i = (0::'a)

lemma disj_matrices_add:

      [| disj_matrices A B; disj_matrices C D; disj_matrices A D; disj_matrices B C |]
      ==> (A + B ≤ C + D) = (A ≤ C ∧ B ≤ D)

lemma disj_matrices_zero1:

      disj_matrices 0 B

lemma disj_matrices_zero2:

      disj_matrices A 0

lemma disj_matrices_commute:

      disj_matrices A B = disj_matrices B A

lemma disj_matrices_add_le_zero:

      disj_matrices A B ==> (A + B ≤ 0) = (A ≤ 0 ∧ B ≤ 0)

lemma disj_matrices_add_zero_le:

      disj_matrices A B ==> (0 ≤ A + B) = (0 ≤ A ∧ 0 ≤ B)

lemma disj_matrices_add_x_le:

      [| disj_matrices A B; disj_matrices B C |] ==> (A ≤ B + C) = (A ≤ C ∧ 0 ≤ B)

lemma disj_matrices_add_le_x:

      [| disj_matrices A B; disj_matrices B C |] ==> (B + A ≤ C) = (A ≤ C ∧ B ≤ 0)

lemma disj_sparse_row_singleton:

      [| i ≤ j; sorted_spvec ((j, y) # v) |]
      ==> disj_matrices (sparse_row_vector v) (singleton_matrix 0 i x)

lemma disj_matrices_x_add:

      [| disj_matrices A B; disj_matrices A C |] ==> disj_matrices A (B + C)

lemma disj_matrices_add_x:

      [| disj_matrices A B; disj_matrices A C |] ==> disj_matrices (B + C) A

lemma disj_singleton_matrices:

      disj_matrices (singleton_matrix j i x) (singleton_matrix u v y) =
      (j ≠ u ∨ i ≠ v ∨ x = (0::'a) ∨ y = (0::'a))

lemma disj_move_sparse_vec_mat:

      [| j ≤ a; sorted_spvec ((a, c) # as) |]
      ==> disj_matrices (sparse_row_matrix as)
           (move_matrix (sparse_row_vector b) (int j) i)

lemma disj_move_sparse_row_vector_twice:

      j ≠ u
      ==> disj_matrices (move_matrix (sparse_row_vector a) j i)
           (move_matrix (sparse_row_vector b) u v)

lemma le_spvec_iff_sparse_row_le:

      [| sorted_spvec a; sorted_spvec b |]
      ==> le_spvec (a, b) = (sparse_row_vector a ≤ sparse_row_vector b)

lemma le_spvec_empty2_sparse_row:

      sorted_spvec b ==> le_spvec (b, []) = (sparse_row_vector b ≤ 0)

lemma le_spvec_empty1_sparse_row:

      sorted_spvec b ==> le_spvec ([], b) = (0 ≤ sparse_row_vector b)

lemma le_spmat_iff_sparse_row_le:

      [| sorted_spvec A; sorted_spmat A; sorted_spvec B; sorted_spmat B |]
      ==> le_spmat (A, B) = (sparse_row_matrix A ≤ sparse_row_matrix B)

lemma sparse_row_matrix_minus:

      sparse_row_matrix (minus_spmat A) = - sparse_row_matrix A

lemma Rep_sparse_row_vector_zero:

      x ≠ 0 ==> Rep_matrix (sparse_row_vector v) x y = (0::'a)

lemma sparse_row_matrix_abs:

      [| sorted_spvec A; sorted_spmat A |]
      ==> sparse_row_matrix (abs_spmat A) = ¦sparse_row_matrix A¦

lemma sorted_spvec_minus_spmat:

      sorted_spvec A ==> sorted_spvec (minus_spmat A)

lemma sorted_spvec_abs_spmat:

      sorted_spvec A ==> sorted_spvec (abs_spmat A)

lemma sorted_spmat_minus_spmat:

      sorted_spmat A ==> sorted_spmat (minus_spmat A)

lemma sorted_spmat_abs_spmat:

      sorted_spmat A ==> sorted_spmat (abs_spmat A)

lemma sorted_spmat_diff_spmat:

      [| sorted_spmat A; sorted_spmat B |] ==> sorted_spmat (diff_spmat A B)

lemma sorted_spvec_diff_spmat:

      [| sorted_spvec A; sorted_spvec B |] ==> sorted_spvec (diff_spmat A B)

lemma sparse_row_diff_spmat:

      sparse_row_matrix (diff_spmat A B) = sparse_row_matrix A - sparse_row_matrix B

lemma sorted_sparse_matrix_imp_spvec:

      sorted_sparse_matrix A ==> sorted_spvec A

lemma sorted_sparse_matrix_imp_spmat:

      sorted_sparse_matrix A ==> sorted_spmat A

lemmas sorted_sp_simps:

      sorted_spvec [] = True

      sorted_spvec (a # as) =
      (case as of [] => True | b # bs => fst a < fst b ∧ sorted_spvec as)

      sorted_spmat [] = True

      sorted_spmat (a # as) = (sorted_spvec (snd a) ∧ sorted_spmat as)

      sorted_sparse_matrix A == sorted_spvec A ∧ sorted_spmat A

lemmas sorted_sp_simps:

      sorted_spvec [] = True

      sorted_spvec (a # as) =
      (case as of [] => True | b # bs => fst a < fst b ∧ sorted_spvec as)

      sorted_spmat [] = True

      sorted_spmat (a # as) = (sorted_spvec (snd a) ∧ sorted_spmat as)

      sorted_sparse_matrix A == sorted_spvec A ∧ sorted_spmat A

lemma bool1:

      (¬ True) = False

lemma bool2:

      (¬ False) = True

lemma bool3:

      (P ∧ True) = P

lemma bool4:

      (True ∧ P) = P

lemma bool5:

      (P ∧ False) = False

lemma bool6:

      (False ∧ P) = False

lemma bool7:

      (P ∨ True) = True

lemma bool8:

      (True ∨ P) = True

lemma bool9:

      (P ∨ False) = P

lemma bool10:

      (False ∨ P) = P

lemmas boolarith:

      (¬ True) = False

      (¬ False) = True

      (P ∧ True) = P

      (True ∧ P) = P

      (P ∧ False) = False

      (False ∧ P) = False

      (P ∨ True) = True

      (True ∨ P) = True

      (P ∨ False) = P

      (False ∨ P) = P

lemmas boolarith:

      (¬ True) = False

      (¬ False) = True

      (P ∧ True) = P

      (True ∧ P) = P

      (P ∧ False) = False

      (False ∧ P) = False

      (P ∨ True) = True

      (True ∨ P) = True

      (P ∨ False) = P

      (False ∨ P) = P

lemma if_case_eq:

      (if b then x else y) = (case b of True => x | False => y)

lemma pprt_add:

      disj_matrices A B ==> pprt (A + B) = pprt A + pprt B

lemma nprt_add:

      disj_matrices A B ==> nprt (A + B) = nprt A + nprt B

lemma pprt_singleton:

      pprt (singleton_matrix j i x) = singleton_matrix j i (pprt x)

lemma nprt_singleton:

      nprt (singleton_matrix j i x) = singleton_matrix j i (nprt x)

lemma less_imp_le:

      a < b ==> a ≤ b

lemma sparse_row_vector_pprt:

      sorted_spvec v ==> sparse_row_vector (pprt_spvec v) = pprt (sparse_row_vector v)

lemma sparse_row_vector_nprt:

      sorted_spvec v ==> sparse_row_vector (nprt_spvec v) = nprt (sparse_row_vector v)

lemma pprt_move_matrix:

      pprt (move_matrix A j i) = move_matrix (pprt A) j i

lemma nprt_move_matrix:

      nprt (move_matrix A j i) = move_matrix (nprt A) j i

lemma sparse_row_matrix_pprt:

      [| sorted_spvec m; sorted_spmat m |]
      ==> sparse_row_matrix (pprt_spmat m) = pprt (sparse_row_matrix m)

lemma sparse_row_matrix_nprt:

      [| sorted_spvec m; sorted_spmat m |]
      ==> sparse_row_matrix (nprt_spmat m) = nprt (sparse_row_matrix m)

lemma sorted_pprt_spvec:

      sorted_spvec v ==> sorted_spvec (pprt_spvec v)

lemma sorted_nprt_spvec:

      sorted_spvec v ==> sorted_spvec (nprt_spvec v)

lemma sorted_spvec_pprt_spmat:

      sorted_spvec m ==> sorted_spvec (pprt_spmat m)

lemma sorted_spvec_nprt_spmat:

      sorted_spvec m ==> sorted_spvec (nprt_spmat m)

lemma sorted_spmat_pprt_spmat:

      sorted_spmat m ==> sorted_spmat (pprt_spmat m)

lemma sorted_spmat_nprt_spmat:

      sorted_spmat m ==> sorted_spmat (nprt_spmat m)

lemmas sparse_row_matrix_op_simps:

      sorted_sparse_matrix A ==> sorted_spmat A

      sorted_sparse_matrix A ==> sorted_spvec A

      sparse_row_matrix (add_spmat (A, B)) = sparse_row_matrix A + sparse_row_matrix B

      [| sorted_spvec A; sorted_spvec B |] ==> sorted_spvec (add_spmat (A, B))

      [| sorted_spmat A; sorted_spmat B |] ==> sorted_spmat (add_spmat (A, B))

      sparse_row_matrix (diff_spmat A B) = sparse_row_matrix A - sparse_row_matrix B

      [| sorted_spvec A; sorted_spvec B |] ==> sorted_spvec (diff_spmat A B)

      [| sorted_spmat A; sorted_spmat B |] ==> sorted_spmat (diff_spmat A B)

      sparse_row_matrix (minus_spmat A) = - sparse_row_matrix A

      sorted_spvec A ==> sorted_spvec (minus_spmat A)

      sorted_spmat A ==> sorted_spmat (minus_spmat A)

      [| sorted_spmat A; sorted_spvec B |]
      ==> sparse_row_matrix (mult_spmat A B) =
          sparse_row_matrix A * sparse_row_matrix B

      sorted_spvec A ==> sorted_spvec (mult_spmat A B)

      sorted_spmat B ==> sorted_spmat (mult_spmat A B)

      [| sorted_spvec A; sorted_spmat A |]
      ==> sparse_row_matrix (abs_spmat A) = ¦sparse_row_matrix A¦

      sorted_spvec A ==> sorted_spvec (abs_spmat A)

      sorted_spmat A ==> sorted_spmat (abs_spmat A)

      [| sorted_spvec A; sorted_spmat A; sorted_spvec B; sorted_spmat B |]
      ==> le_spmat (A, B) = (sparse_row_matrix A ≤ sparse_row_matrix B)

      [| sorted_spvec m; sorted_spmat m |]
      ==> sparse_row_matrix (pprt_spmat m) = pprt (sparse_row_matrix m)

      sorted_spvec m ==> sorted_spvec (pprt_spmat m)

      sorted_spmat m ==> sorted_spmat (pprt_spmat m)

      [| sorted_spvec m; sorted_spmat m |]
      ==> sparse_row_matrix (nprt_spmat m) = nprt (sparse_row_matrix m)

      sorted_spvec m ==> sorted_spvec (nprt_spmat m)

      sorted_spmat m ==> sorted_spmat (nprt_spmat m)

lemmas sparse_row_matrix_op_simps:

      sorted_sparse_matrix A ==> sorted_spmat A

      sorted_sparse_matrix A ==> sorted_spvec A

      sparse_row_matrix (add_spmat (A, B)) = sparse_row_matrix A + sparse_row_matrix B

      [| sorted_spvec A; sorted_spvec B |] ==> sorted_spvec (add_spmat (A, B))

      [| sorted_spmat A; sorted_spmat B |] ==> sorted_spmat (add_spmat (A, B))

      sparse_row_matrix (diff_spmat A B) = sparse_row_matrix A - sparse_row_matrix B

      [| sorted_spvec A; sorted_spvec B |] ==> sorted_spvec (diff_spmat A B)

      [| sorted_spmat A; sorted_spmat B |] ==> sorted_spmat (diff_spmat A B)

      sparse_row_matrix (minus_spmat A) = - sparse_row_matrix A

      sorted_spvec A ==> sorted_spvec (minus_spmat A)

      sorted_spmat A ==> sorted_spmat (minus_spmat A)

      [| sorted_spmat A; sorted_spvec B |]
      ==> sparse_row_matrix (mult_spmat A B) =
          sparse_row_matrix A * sparse_row_matrix B

      sorted_spvec A ==> sorted_spvec (mult_spmat A B)

      sorted_spmat B ==> sorted_spmat (mult_spmat A B)

      [| sorted_spvec A; sorted_spmat A |]
      ==> sparse_row_matrix (abs_spmat A) = ¦sparse_row_matrix A¦

      sorted_spvec A ==> sorted_spvec (abs_spmat A)

      sorted_spmat A ==> sorted_spmat (abs_spmat A)

      [| sorted_spvec A; sorted_spmat A; sorted_spvec B; sorted_spmat B |]
      ==> le_spmat (A, B) = (sparse_row_matrix A ≤ sparse_row_matrix B)

      [| sorted_spvec m; sorted_spmat m |]
      ==> sparse_row_matrix (pprt_spmat m) = pprt (sparse_row_matrix m)

      sorted_spvec m ==> sorted_spvec (pprt_spmat m)

      sorted_spmat m ==> sorted_spmat (pprt_spmat m)

      [| sorted_spvec m; sorted_spmat m |]
      ==> sparse_row_matrix (nprt_spmat m) = nprt (sparse_row_matrix m)

      sorted_spvec m ==> sorted_spvec (nprt_spmat m)

      sorted_spmat m ==> sorted_spmat (nprt_spmat m)

lemma zero_eq_Numeral0:

      (0::'a) = Numeral0

lemmas sparse_row_matrix_arith_simps:

      mult_spmat [] A = []

      mult_spmat (a # as) A =
      (fst a, mult_spvec_spmat ([], snd a, A)) # mult_spmat as A

      mult_spvec_spmat (c, [], brr) = c

      mult_spvec_spmat (c, y # z, []) = c

      mult_spvec_spmat (c, a # arr, b # brr) =
      (if fst a < fst b then mult_spvec_spmat (c, arr, b # brr)
       else if fst b < fst a then mult_spvec_spmat (c, a # arr, brr)
            else mult_spvec_spmat (addmult_spvec (snd a, c, snd b), arr, brr))

      addmult_spvec (y, arr, []) = arr

      addmult_spvec (y, [], ae # af) = smult_spvec y (ae # af)

      addmult_spvec (y, a # arr, b # brr) =
      (if fst a < fst b then a # addmult_spvec (y, arr, b # brr)
       else if fst b < fst a then (fst b, y * snd b) # addmult_spvec (y, a # arr, brr)
            else (fst a, snd a + y * snd b) # addmult_spvec (y, arr, brr))

      smult_spvec y [] = []

      smult_spvec y (a # arr) = (fst a, y * snd a) # smult_spvec y arr

      add_spmat ([], bs) = bs

      add_spmat (w # x, []) = w # x

      add_spmat (a # as, b # bs) =
      (if fst a < fst b then a # add_spmat (as, b # bs)
       else if fst b < fst a then b # add_spmat (a # as, bs)
            else (fst a, add_spvec (snd a, snd b)) # add_spmat (as, bs))

      add_spvec (arr, []) = arr

      add_spvec ([], ab # ac) = ab # ac

      add_spvec (a # arr, b # brr) =
      (if fst a < fst b then a # add_spvec (arr, b # brr)
       else if fst b < fst a then b # add_spvec (a # arr, brr)
            else (fst a, snd a + snd b) # add_spvec (arr, brr))

      minus_spmat [] = []

      minus_spmat (a # as) = (fst a, minus_spvec (snd a)) # minus_spmat as

      minus_spvec [] = []

      minus_spvec (a # as) = (fst a, - snd a) # minus_spvec as

      abs_spmat [] = []

      abs_spmat (a # as) = (fst a, abs_spvec (snd a)) # abs_spmat as

      abs_spvec [] = []

      abs_spvec (a # as) = (fst a, ¦snd a¦) # abs_spvec as

      diff_spmat A B == add_spmat (A, minus_spmat B)

      le_spmat ([], []) = True

      le_spmat (a # as, []) = (le_spvec (snd a, []) ∧ le_spmat (as, []))

      le_spmat ([], b # bs) = (le_spvec ([], snd b) ∧ le_spmat ([], bs))

      le_spmat (a # as, b # bs) =
      (if fst a < fst b then le_spvec (snd a, []) ∧ le_spmat (as, b # bs)
       else if fst b < fst a then le_spvec ([], snd b) ∧ le_spmat (a # as, bs)
            else le_spvec (snd a, snd b) ∧ le_spmat (as, bs))

      le_spvec ([], []) = True

      le_spvec (a # as, []) = (snd a ≤ (0::'a) ∧ le_spvec (as, []))

      le_spvec ([], b # bs) = ((0::'a) ≤ snd b ∧ le_spvec ([], bs))

      le_spvec (a # as, b # bs) =
      (if fst a < fst b then snd a ≤ (0::'a) ∧ le_spvec (as, b # bs)
       else if fst b < fst a then (0::'a) ≤ snd b ∧ le_spvec (a # as, bs)
            else snd a ≤ snd b ∧ le_spvec (as, bs))

      pprt_spmat [] = []

      pprt_spmat (a # as) = (fst a, pprt_spvec (snd a)) # pprt_spmat as

      pprt_spvec [] = []

      pprt_spvec (a # as) = (fst a, pprt (snd a)) # pprt_spvec as

      nprt_spmat [] = []

      nprt_spmat (a # as) = (fst a, nprt_spvec (snd a)) # nprt_spmat as

      nprt_spvec [] = []

      nprt_spvec (a # as) = (fst a, nprt (snd a)) # nprt_spvec as

      mult_est_spmat r1.0 r2.0 s1.0 s2.0 ==
      add_spmat
       (mult_spmat (pprt_spmat s2.0) (pprt_spmat r2.0),
        add_spmat
         (mult_spmat (pprt_spmat s1.0) (nprt_spmat r2.0),
          add_spmat
           (mult_spmat (nprt_spmat s2.0) (pprt_spmat r1.0),
            mult_spmat (nprt_spmat s1.0) (nprt_spmat r1.0))))

lemmas sparse_row_matrix_arith_simps:

      mult_spmat [] A = []

      mult_spmat (a # as) A =
      (fst a, mult_spvec_spmat ([], snd a, A)) # mult_spmat as A

      mult_spvec_spmat (c, [], brr) = c

      mult_spvec_spmat (c, y # z, []) = c

      mult_spvec_spmat (c, a # arr, b # brr) =
      (if fst a < fst b then mult_spvec_spmat (c, arr, b # brr)
       else if fst b < fst a then mult_spvec_spmat (c, a # arr, brr)
            else mult_spvec_spmat (addmult_spvec (snd a, c, snd b), arr, brr))

      addmult_spvec (y, arr, []) = arr

      addmult_spvec (y, [], ae # af) = smult_spvec y (ae # af)

      addmult_spvec (y, a # arr, b # brr) =
      (if fst a < fst b then a # addmult_spvec (y, arr, b # brr)
       else if fst b < fst a then (fst b, y * snd b) # addmult_spvec (y, a # arr, brr)
            else (fst a, snd a + y * snd b) # addmult_spvec (y, arr, brr))

      smult_spvec y [] = []

      smult_spvec y (a # arr) = (fst a, y * snd a) # smult_spvec y arr

      add_spmat ([], bs) = bs

      add_spmat (w # x, []) = w # x

      add_spmat (a # as, b # bs) =
      (if fst a < fst b then a # add_spmat (as, b # bs)
       else if fst b < fst a then b # add_spmat (a # as, bs)
            else (fst a, add_spvec (snd a, snd b)) # add_spmat (as, bs))

      add_spvec (arr, []) = arr

      add_spvec ([], ab # ac) = ab # ac

      add_spvec (a # arr, b # brr) =
      (if fst a < fst b then a # add_spvec (arr, b # brr)
       else if fst b < fst a then b # add_spvec (a # arr, brr)
            else (fst a, snd a + snd b) # add_spvec (arr, brr))

      minus_spmat [] = []

      minus_spmat (a # as) = (fst a, minus_spvec (snd a)) # minus_spmat as

      minus_spvec [] = []

      minus_spvec (a # as) = (fst a, - snd a) # minus_spvec as

      abs_spmat [] = []

      abs_spmat (a # as) = (fst a, abs_spvec (snd a)) # abs_spmat as

      abs_spvec [] = []

      abs_spvec (a # as) = (fst a, ¦snd a¦) # abs_spvec as

      diff_spmat A B == add_spmat (A, minus_spmat B)

      le_spmat ([], []) = True

      le_spmat (a # as, []) = (le_spvec (snd a, []) ∧ le_spmat (as, []))

      le_spmat ([], b # bs) = (le_spvec ([], snd b) ∧ le_spmat ([], bs))

      le_spmat (a # as, b # bs) =
      (if fst a < fst b then le_spvec (snd a, []) ∧ le_spmat (as, b # bs)
       else if fst b < fst a then le_spvec ([], snd b) ∧ le_spmat (a # as, bs)
            else le_spvec (snd a, snd b) ∧ le_spmat (as, bs))

      le_spvec ([], []) = True

      le_spvec (a # as, []) = (snd a ≤ (0::'a) ∧ le_spvec (as, []))

      le_spvec ([], b # bs) = ((0::'a) ≤ snd b ∧ le_spvec ([], bs))

      le_spvec (a # as, b # bs) =
      (if fst a < fst b then snd a ≤ (0::'a) ∧ le_spvec (as, b # bs)
       else if fst b < fst a then (0::'a) ≤ snd b ∧ le_spvec (a # as, bs)
            else snd a ≤ snd b ∧ le_spvec (as, bs))

      pprt_spmat [] = []

      pprt_spmat (a # as) = (fst a, pprt_spvec (snd a)) # pprt_spmat as

      pprt_spvec [] = []

      pprt_spvec (a # as) = (fst a, pprt (snd a)) # pprt_spvec as

      nprt_spmat [] = []

      nprt_spmat (a # as) = (fst a, nprt_spvec (snd a)) # nprt_spmat as

      nprt_spvec [] = []

      nprt_spvec (a # as) = (fst a, nprt (snd a)) # nprt_spvec as

      mult_est_spmat r1.0 r2.0 s1.0 s2.0 ==
      add_spmat
       (mult_spmat (pprt_spmat s2.0) (pprt_spmat r2.0),
        add_spmat
         (mult_spmat (pprt_spmat s1.0) (nprt_spmat r2.0),
          add_spmat
           (mult_spmat (nprt_spmat s2.0) (pprt_spmat r1.0),
            mult_spmat (nprt_spmat s1.0) (nprt_spmat r1.0))))

lemma spm_mult_le_dual_prts:

      [| sorted_sparse_matrix A1.0; sorted_sparse_matrix A2.0;
         sorted_sparse_matrix c1.0; sorted_sparse_matrix c2.0; sorted_sparse_matrix y;
         sorted_sparse_matrix r1.0; sorted_sparse_matrix r2.0; sorted_spvec b;
         le_spmat ([], y); sparse_row_matrix A1.0 ≤ A; A ≤ sparse_row_matrix A2.0;
         sparse_row_matrix c1.0 ≤ c; c ≤ sparse_row_matrix c2.0;
         sparse_row_matrix r1.0 ≤ x; x ≤ sparse_row_matrix r2.0;
         A * x ≤ sparse_row_matrix b |]
      ==> c * x
          ≤ sparse_row_matrix
             (add_spmat
               (mult_spmat y b,
                let s1 = diff_spmat c1.0 (mult_spmat y A2.0);
                    s2 = diff_spmat c2.0 (mult_spmat y A1.0)
                in add_spmat
                    (mult_spmat (pprt_spmat s2) (pprt_spmat r2.0),
                     add_spmat
                      (mult_spmat (pprt_spmat s1) (nprt_spmat r2.0),
                       add_spmat
                        (mult_spmat (nprt_spmat s2) (pprt_spmat r1.0),
                         mult_spmat (nprt_spmat s1) (nprt_spmat r1.0))))))

lemma spm_mult_le_dual_prts_no_let:

      [| sorted_sparse_matrix A1.0; sorted_sparse_matrix A2.0;
         sorted_sparse_matrix c1.0; sorted_sparse_matrix c2.0; sorted_sparse_matrix y;
         sorted_sparse_matrix r1.0; sorted_sparse_matrix r2.0; sorted_spvec b;
         le_spmat ([], y); sparse_row_matrix A1.0 ≤ A; A ≤ sparse_row_matrix A2.0;
         sparse_row_matrix c1.0 ≤ c; c ≤ sparse_row_matrix c2.0;
         sparse_row_matrix r1.0 ≤ x; x ≤ sparse_row_matrix r2.0;
         A * x ≤ sparse_row_matrix b |]
      ==> c * x
          ≤ sparse_row_matrix
             (add_spmat
               (mult_spmat y b,
                mult_est_spmat r1.0 r2.0 (diff_spmat c1.0 (mult_spmat y A2.0))
                 (diff_spmat c2.0 (mult_spmat y A1.0))))