src/HOL/Analysis/Determinants.thy
 changeset 63627 6ddb43c6b711 parent 63469 b6900858dcb9 child 63918 6bf55e6e0b75
```     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/HOL/Analysis/Determinants.thy	Mon Aug 08 14:13:14 2016 +0200
1.3 @@ -0,0 +1,1249 @@
1.4 +(*  Title:      HOL/Analysis/Determinants.thy
1.5 +    Author:     Amine Chaieb, University of Cambridge
1.6 +*)
1.7 +
1.8 +section \<open>Traces, Determinant of square matrices and some properties\<close>
1.9 +
1.10 +theory Determinants
1.11 +imports
1.12 +  Cartesian_Euclidean_Space
1.13 +  "~~/src/HOL/Library/Permutations"
1.14 +begin
1.15 +
1.16 +subsection \<open>Trace\<close>
1.17 +
1.18 +definition trace :: "'a::semiring_1^'n^'n \<Rightarrow> 'a"
1.19 +  where "trace A = setsum (\<lambda>i. ((A\$i)\$i)) (UNIV::'n set)"
1.20 +
1.21 +lemma trace_0: "trace (mat 0) = 0"
1.22 +  by (simp add: trace_def mat_def)
1.23 +
1.24 +lemma trace_I: "trace (mat 1 :: 'a::semiring_1^'n^'n) = of_nat(CARD('n))"
1.25 +  by (simp add: trace_def mat_def)
1.26 +
1.27 +lemma trace_add: "trace ((A::'a::comm_semiring_1^'n^'n) + B) = trace A + trace B"
1.28 +  by (simp add: trace_def setsum.distrib)
1.29 +
1.30 +lemma trace_sub: "trace ((A::'a::comm_ring_1^'n^'n) - B) = trace A - trace B"
1.31 +  by (simp add: trace_def setsum_subtractf)
1.32 +
1.33 +lemma trace_mul_sym: "trace ((A::'a::comm_semiring_1^'n^'m) ** B) = trace (B**A)"
1.34 +  apply (simp add: trace_def matrix_matrix_mult_def)
1.35 +  apply (subst setsum.commute)
1.36 +  apply (simp add: mult.commute)
1.37 +  done
1.38 +
1.39 +text \<open>Definition of determinant.\<close>
1.40 +
1.41 +definition det:: "'a::comm_ring_1^'n^'n \<Rightarrow> 'a" where
1.42 +  "det A =
1.43 +    setsum (\<lambda>p. of_int (sign p) * setprod (\<lambda>i. A\$i\$p i) (UNIV :: 'n set))
1.44 +      {p. p permutes (UNIV :: 'n set)}"
1.45 +
1.46 +text \<open>A few general lemmas we need below.\<close>
1.47 +
1.48 +lemma setprod_permute:
1.49 +  assumes p: "p permutes S"
1.50 +  shows "setprod f S = setprod (f \<circ> p) S"
1.51 +  using assms by (fact setprod.permute)
1.52 +
1.53 +lemma setproduct_permute_nat_interval:
1.54 +  fixes m n :: nat
1.55 +  shows "p permutes {m..n} \<Longrightarrow> setprod f {m..n} = setprod (f \<circ> p) {m..n}"
1.56 +  by (blast intro!: setprod_permute)
1.57 +
1.58 +text \<open>Basic determinant properties.\<close>
1.59 +
1.60 +lemma det_transpose: "det (transpose A) = det (A::'a::comm_ring_1 ^'n^'n)"
1.61 +proof -
1.62 +  let ?di = "\<lambda>A i j. A\$i\$j"
1.63 +  let ?U = "(UNIV :: 'n set)"
1.64 +  have fU: "finite ?U" by simp
1.65 +  {
1.66 +    fix p
1.67 +    assume p: "p \<in> {p. p permutes ?U}"
1.68 +    from p have pU: "p permutes ?U"
1.69 +      by blast
1.70 +    have sth: "sign (inv p) = sign p"
1.71 +      by (metis sign_inverse fU p mem_Collect_eq permutation_permutes)
1.72 +    from permutes_inj[OF pU]
1.73 +    have pi: "inj_on p ?U"
1.74 +      by (blast intro: subset_inj_on)
1.75 +    from permutes_image[OF pU]
1.76 +    have "setprod (\<lambda>i. ?di (transpose A) i (inv p i)) ?U =
1.77 +      setprod (\<lambda>i. ?di (transpose A) i (inv p i)) (p ` ?U)"
1.78 +      by simp
1.79 +    also have "\<dots> = setprod ((\<lambda>i. ?di (transpose A) i (inv p i)) \<circ> p) ?U"
1.80 +      unfolding setprod.reindex[OF pi] ..
1.81 +    also have "\<dots> = setprod (\<lambda>i. ?di A i (p i)) ?U"
1.82 +    proof -
1.83 +      {
1.84 +        fix i
1.85 +        assume i: "i \<in> ?U"
1.86 +        from i permutes_inv_o[OF pU] permutes_in_image[OF pU]
1.87 +        have "((\<lambda>i. ?di (transpose A) i (inv p i)) \<circ> p) i = ?di A i (p i)"
1.88 +          unfolding transpose_def by (simp add: fun_eq_iff)
1.89 +      }
1.90 +      then show "setprod ((\<lambda>i. ?di (transpose A) i (inv p i)) \<circ> p) ?U =
1.91 +        setprod (\<lambda>i. ?di A i (p i)) ?U"
1.92 +        by (auto intro: setprod.cong)
1.93 +    qed
1.94 +    finally have "of_int (sign (inv p)) * (setprod (\<lambda>i. ?di (transpose A) i (inv p i)) ?U) =
1.95 +      of_int (sign p) * (setprod (\<lambda>i. ?di A i (p i)) ?U)"
1.96 +      using sth by simp
1.97 +  }
1.98 +  then show ?thesis
1.99 +    unfolding det_def
1.100 +    apply (subst setsum_permutations_inverse)
1.101 +    apply (rule setsum.cong)
1.102 +    apply (rule refl)
1.103 +    apply blast
1.104 +    done
1.105 +qed
1.106 +
1.107 +lemma det_lowerdiagonal:
1.108 +  fixes A :: "'a::comm_ring_1^('n::{finite,wellorder})^('n::{finite,wellorder})"
1.109 +  assumes ld: "\<And>i j. i < j \<Longrightarrow> A\$i\$j = 0"
1.110 +  shows "det A = setprod (\<lambda>i. A\$i\$i) (UNIV:: 'n set)"
1.111 +proof -
1.112 +  let ?U = "UNIV:: 'n set"
1.113 +  let ?PU = "{p. p permutes ?U}"
1.114 +  let ?pp = "\<lambda>p. of_int (sign p) * setprod (\<lambda>i. A\$i\$p i) (UNIV :: 'n set)"
1.115 +  have fU: "finite ?U"
1.116 +    by simp
1.117 +  from finite_permutations[OF fU] have fPU: "finite ?PU" .
1.118 +  have id0: "{id} \<subseteq> ?PU"
1.119 +    by (auto simp add: permutes_id)
1.120 +  {
1.121 +    fix p
1.122 +    assume p: "p \<in> ?PU - {id}"
1.123 +    from p have pU: "p permutes ?U" and pid: "p \<noteq> id"
1.124 +      by blast+
1.125 +    from permutes_natset_le[OF pU] pid obtain i where i: "p i > i"
1.126 +      by (metis not_le)
1.127 +    from ld[OF i] have ex:"\<exists>i \<in> ?U. A\$i\$p i = 0"
1.128 +      by blast
1.129 +    from setprod_zero[OF fU ex] have "?pp p = 0"
1.130 +      by simp
1.131 +  }
1.132 +  then have p0: "\<forall>p \<in> ?PU - {id}. ?pp p = 0"
1.133 +    by blast
1.134 +  from setsum.mono_neutral_cong_left[OF fPU id0 p0] show ?thesis
1.135 +    unfolding det_def by (simp add: sign_id)
1.136 +qed
1.137 +
1.138 +lemma det_upperdiagonal:
1.139 +  fixes A :: "'a::comm_ring_1^'n::{finite,wellorder}^'n::{finite,wellorder}"
1.140 +  assumes ld: "\<And>i j. i > j \<Longrightarrow> A\$i\$j = 0"
1.141 +  shows "det A = setprod (\<lambda>i. A\$i\$i) (UNIV:: 'n set)"
1.142 +proof -
1.143 +  let ?U = "UNIV:: 'n set"
1.144 +  let ?PU = "{p. p permutes ?U}"
1.145 +  let ?pp = "(\<lambda>p. of_int (sign p) * setprod (\<lambda>i. A\$i\$p i) (UNIV :: 'n set))"
1.146 +  have fU: "finite ?U"
1.147 +    by simp
1.148 +  from finite_permutations[OF fU] have fPU: "finite ?PU" .
1.149 +  have id0: "{id} \<subseteq> ?PU"
1.150 +    by (auto simp add: permutes_id)
1.151 +  {
1.152 +    fix p
1.153 +    assume p: "p \<in> ?PU - {id}"
1.154 +    from p have pU: "p permutes ?U" and pid: "p \<noteq> id"
1.155 +      by blast+
1.156 +    from permutes_natset_ge[OF pU] pid obtain i where i: "p i < i"
1.157 +      by (metis not_le)
1.158 +    from ld[OF i] have ex:"\<exists>i \<in> ?U. A\$i\$p i = 0"
1.159 +      by blast
1.160 +    from setprod_zero[OF fU ex] have "?pp p = 0"
1.161 +      by simp
1.162 +  }
1.163 +  then have p0: "\<forall>p \<in> ?PU -{id}. ?pp p = 0"
1.164 +    by blast
1.165 +  from setsum.mono_neutral_cong_left[OF fPU id0 p0] show ?thesis
1.166 +    unfolding det_def by (simp add: sign_id)
1.167 +qed
1.168 +
1.169 +lemma det_diagonal:
1.170 +  fixes A :: "'a::comm_ring_1^'n^'n"
1.171 +  assumes ld: "\<And>i j. i \<noteq> j \<Longrightarrow> A\$i\$j = 0"
1.172 +  shows "det A = setprod (\<lambda>i. A\$i\$i) (UNIV::'n set)"
1.173 +proof -
1.174 +  let ?U = "UNIV:: 'n set"
1.175 +  let ?PU = "{p. p permutes ?U}"
1.176 +  let ?pp = "\<lambda>p. of_int (sign p) * setprod (\<lambda>i. A\$i\$p i) (UNIV :: 'n set)"
1.177 +  have fU: "finite ?U" by simp
1.178 +  from finite_permutations[OF fU] have fPU: "finite ?PU" .
1.179 +  have id0: "{id} \<subseteq> ?PU"
1.180 +    by (auto simp add: permutes_id)
1.181 +  {
1.182 +    fix p
1.183 +    assume p: "p \<in> ?PU - {id}"
1.184 +    then have "p \<noteq> id"
1.185 +      by simp
1.186 +    then obtain i where i: "p i \<noteq> i"
1.187 +      unfolding fun_eq_iff by auto
1.188 +    from ld [OF i [symmetric]] have ex:"\<exists>i \<in> ?U. A\$i\$p i = 0"
1.189 +      by blast
1.190 +    from setprod_zero [OF fU ex] have "?pp p = 0"
1.191 +      by simp
1.192 +  }
1.193 +  then have p0: "\<forall>p \<in> ?PU - {id}. ?pp p = 0"
1.194 +    by blast
1.195 +  from setsum.mono_neutral_cong_left[OF fPU id0 p0] show ?thesis
1.196 +    unfolding det_def by (simp add: sign_id)
1.197 +qed
1.198 +
1.199 +lemma det_I: "det (mat 1 :: 'a::comm_ring_1^'n^'n) = 1"
1.200 +proof -
1.201 +  let ?A = "mat 1 :: 'a::comm_ring_1^'n^'n"
1.202 +  let ?U = "UNIV :: 'n set"
1.203 +  let ?f = "\<lambda>i j. ?A\$i\$j"
1.204 +  {
1.205 +    fix i
1.206 +    assume i: "i \<in> ?U"
1.207 +    have "?f i i = 1"
1.208 +      using i by (vector mat_def)
1.209 +  }
1.210 +  then have th: "setprod (\<lambda>i. ?f i i) ?U = setprod (\<lambda>x. 1) ?U"
1.211 +    by (auto intro: setprod.cong)
1.212 +  {
1.213 +    fix i j
1.214 +    assume i: "i \<in> ?U" and j: "j \<in> ?U" and ij: "i \<noteq> j"
1.215 +    have "?f i j = 0" using i j ij
1.216 +      by (vector mat_def)
1.217 +  }
1.218 +  then have "det ?A = setprod (\<lambda>i. ?f i i) ?U"
1.219 +    using det_diagonal by blast
1.220 +  also have "\<dots> = 1"
1.221 +    unfolding th setprod.neutral_const ..
1.222 +  finally show ?thesis .
1.223 +qed
1.224 +
1.225 +lemma det_0: "det (mat 0 :: 'a::comm_ring_1^'n^'n) = 0"
1.226 +  by (simp add: det_def setprod_zero)
1.227 +
1.228 +lemma det_permute_rows:
1.229 +  fixes A :: "'a::comm_ring_1^'n^'n"
1.230 +  assumes p: "p permutes (UNIV :: 'n::finite set)"
1.231 +  shows "det (\<chi> i. A\$p i :: 'a^'n^'n) = of_int (sign p) * det A"
1.232 +  apply (simp add: det_def setsum_right_distrib mult.assoc[symmetric])
1.233 +  apply (subst sum_permutations_compose_right[OF p])
1.234 +proof (rule setsum.cong)
1.235 +  let ?U = "UNIV :: 'n set"
1.236 +  let ?PU = "{p. p permutes ?U}"
1.237 +  fix q
1.238 +  assume qPU: "q \<in> ?PU"
1.239 +  have fU: "finite ?U"
1.240 +    by simp
1.241 +  from qPU have q: "q permutes ?U"
1.242 +    by blast
1.243 +  from p q have pp: "permutation p" and qp: "permutation q"
1.244 +    by (metis fU permutation_permutes)+
1.245 +  from permutes_inv[OF p] have ip: "inv p permutes ?U" .
1.246 +  have "setprod (\<lambda>i. A\$p i\$ (q \<circ> p) i) ?U = setprod ((\<lambda>i. A\$p i\$(q \<circ> p) i) \<circ> inv p) ?U"
1.247 +    by (simp only: setprod_permute[OF ip, symmetric])
1.248 +  also have "\<dots> = setprod (\<lambda>i. A \$ (p \<circ> inv p) i \$ (q \<circ> (p \<circ> inv p)) i) ?U"
1.249 +    by (simp only: o_def)
1.250 +  also have "\<dots> = setprod (\<lambda>i. A\$i\$q i) ?U"
1.251 +    by (simp only: o_def permutes_inverses[OF p])
1.252 +  finally have thp: "setprod (\<lambda>i. A\$p i\$ (q \<circ> p) i) ?U = setprod (\<lambda>i. A\$i\$q i) ?U"
1.253 +    by blast
1.254 +  show "of_int (sign (q \<circ> p)) * setprod (\<lambda>i. A\$ p i\$ (q \<circ> p) i) ?U =
1.255 +    of_int (sign p) * of_int (sign q) * setprod (\<lambda>i. A\$i\$q i) ?U"
1.256 +    by (simp only: thp sign_compose[OF qp pp] mult.commute of_int_mult)
1.257 +qed rule
1.258 +
1.259 +lemma det_permute_columns:
1.260 +  fixes A :: "'a::comm_ring_1^'n^'n"
1.261 +  assumes p: "p permutes (UNIV :: 'n set)"
1.262 +  shows "det(\<chi> i j. A\$i\$ p j :: 'a^'n^'n) = of_int (sign p) * det A"
1.263 +proof -
1.264 +  let ?Ap = "\<chi> i j. A\$i\$ p j :: 'a^'n^'n"
1.265 +  let ?At = "transpose A"
1.266 +  have "of_int (sign p) * det A = det (transpose (\<chi> i. transpose A \$ p i))"
1.267 +    unfolding det_permute_rows[OF p, of ?At] det_transpose ..
1.268 +  moreover
1.269 +  have "?Ap = transpose (\<chi> i. transpose A \$ p i)"
1.270 +    by (simp add: transpose_def vec_eq_iff)
1.271 +  ultimately show ?thesis
1.272 +    by simp
1.273 +qed
1.274 +
1.275 +lemma det_identical_rows:
1.276 +  fixes A :: "'a::linordered_idom^'n^'n"
1.277 +  assumes ij: "i \<noteq> j"
1.278 +    and r: "row i A = row j A"
1.279 +  shows "det A = 0"
1.280 +proof-
1.281 +  have tha: "\<And>(a::'a) b. a = b \<Longrightarrow> b = - a \<Longrightarrow> a = 0"
1.282 +    by simp
1.283 +  have th1: "of_int (-1) = - 1" by simp
1.284 +  let ?p = "Fun.swap i j id"
1.285 +  let ?A = "\<chi> i. A \$ ?p i"
1.286 +  from r have "A = ?A" by (simp add: vec_eq_iff row_def Fun.swap_def)
1.287 +  then have "det A = det ?A" by simp
1.288 +  moreover have "det A = - det ?A"
1.289 +    by (simp add: det_permute_rows[OF permutes_swap_id] sign_swap_id ij th1)
1.290 +  ultimately show "det A = 0" by (metis tha)
1.291 +qed
1.292 +
1.293 +lemma det_identical_columns:
1.294 +  fixes A :: "'a::linordered_idom^'n^'n"
1.295 +  assumes ij: "i \<noteq> j"
1.296 +    and r: "column i A = column j A"
1.297 +  shows "det A = 0"
1.298 +  apply (subst det_transpose[symmetric])
1.299 +  apply (rule det_identical_rows[OF ij])
1.300 +  apply (metis row_transpose r)
1.301 +  done
1.302 +
1.303 +lemma det_zero_row:
1.304 +  fixes A :: "'a::{idom, ring_char_0}^'n^'n"
1.305 +  assumes r: "row i A = 0"
1.306 +  shows "det A = 0"
1.307 +  using r
1.308 +  apply (simp add: row_def det_def vec_eq_iff)
1.309 +  apply (rule setsum.neutral)
1.310 +  apply (auto simp: sign_nz)
1.311 +  done
1.312 +
1.313 +lemma det_zero_column:
1.314 +  fixes A :: "'a::{idom,ring_char_0}^'n^'n"
1.315 +  assumes r: "column i A = 0"
1.316 +  shows "det A = 0"
1.317 +  apply (subst det_transpose[symmetric])
1.318 +  apply (rule det_zero_row [of i])
1.319 +  apply (metis row_transpose r)
1.320 +  done
1.321 +
1.323 +  fixes a b c :: "'n::finite \<Rightarrow> _ ^ 'n"
1.324 +  shows "det((\<chi> i. if i = k then a i + b i else c i)::'a::comm_ring_1^'n^'n) =
1.325 +    det((\<chi> i. if i = k then a i else c i)::'a::comm_ring_1^'n^'n) +
1.326 +    det((\<chi> i. if i = k then b i else c i)::'a::comm_ring_1^'n^'n)"
1.327 +  unfolding det_def vec_lambda_beta setsum.distrib[symmetric]
1.328 +proof (rule setsum.cong)
1.329 +  let ?U = "UNIV :: 'n set"
1.330 +  let ?pU = "{p. p permutes ?U}"
1.331 +  let ?f = "(\<lambda>i. if i = k then a i + b i else c i)::'n \<Rightarrow> 'a::comm_ring_1^'n"
1.332 +  let ?g = "(\<lambda> i. if i = k then a i else c i)::'n \<Rightarrow> 'a::comm_ring_1^'n"
1.333 +  let ?h = "(\<lambda> i. if i = k then b i else c i)::'n \<Rightarrow> 'a::comm_ring_1^'n"
1.334 +  fix p
1.335 +  assume p: "p \<in> ?pU"
1.336 +  let ?Uk = "?U - {k}"
1.337 +  from p have pU: "p permutes ?U"
1.338 +    by blast
1.339 +  have kU: "?U = insert k ?Uk"
1.340 +    by blast
1.341 +  {
1.342 +    fix j
1.343 +    assume j: "j \<in> ?Uk"
1.344 +    from j have "?f j \$ p j = ?g j \$ p j" and "?f j \$ p j= ?h j \$ p j"
1.345 +      by simp_all
1.346 +  }
1.347 +  then have th1: "setprod (\<lambda>i. ?f i \$ p i) ?Uk = setprod (\<lambda>i. ?g i \$ p i) ?Uk"
1.348 +    and th2: "setprod (\<lambda>i. ?f i \$ p i) ?Uk = setprod (\<lambda>i. ?h i \$ p i) ?Uk"
1.349 +    apply -
1.350 +    apply (rule setprod.cong, simp_all)+
1.351 +    done
1.352 +  have th3: "finite ?Uk" "k \<notin> ?Uk"
1.353 +    by auto
1.354 +  have "setprod (\<lambda>i. ?f i \$ p i) ?U = setprod (\<lambda>i. ?f i \$ p i) (insert k ?Uk)"
1.355 +    unfolding kU[symmetric] ..
1.356 +  also have "\<dots> = ?f k \$ p k * setprod (\<lambda>i. ?f i \$ p i) ?Uk"
1.357 +    apply (rule setprod.insert)
1.358 +    apply simp
1.359 +    apply blast
1.360 +    done
1.361 +  also have "\<dots> = (a k \$ p k * setprod (\<lambda>i. ?f i \$ p i) ?Uk) + (b k\$ p k * setprod (\<lambda>i. ?f i \$ p i) ?Uk)"
1.362 +    by (simp add: field_simps)
1.363 +  also have "\<dots> = (a k \$ p k * setprod (\<lambda>i. ?g i \$ p i) ?Uk) + (b k\$ p k * setprod (\<lambda>i. ?h i \$ p i) ?Uk)"
1.364 +    by (metis th1 th2)
1.365 +  also have "\<dots> = setprod (\<lambda>i. ?g i \$ p i) (insert k ?Uk) + setprod (\<lambda>i. ?h i \$ p i) (insert k ?Uk)"
1.366 +    unfolding  setprod.insert[OF th3] by simp
1.367 +  finally have "setprod (\<lambda>i. ?f i \$ p i) ?U = setprod (\<lambda>i. ?g i \$ p i) ?U + setprod (\<lambda>i. ?h i \$ p i) ?U"
1.368 +    unfolding kU[symmetric] .
1.369 +  then show "of_int (sign p) * setprod (\<lambda>i. ?f i \$ p i) ?U =
1.370 +    of_int (sign p) * setprod (\<lambda>i. ?g i \$ p i) ?U + of_int (sign p) * setprod (\<lambda>i. ?h i \$ p i) ?U"
1.371 +    by (simp add: field_simps)
1.372 +qed rule
1.373 +
1.374 +lemma det_row_mul:
1.375 +  fixes a b :: "'n::finite \<Rightarrow> _ ^ 'n"
1.376 +  shows "det((\<chi> i. if i = k then c *s a i else b i)::'a::comm_ring_1^'n^'n) =
1.377 +    c * det((\<chi> i. if i = k then a i else b i)::'a::comm_ring_1^'n^'n)"
1.378 +  unfolding det_def vec_lambda_beta setsum_right_distrib
1.379 +proof (rule setsum.cong)
1.380 +  let ?U = "UNIV :: 'n set"
1.381 +  let ?pU = "{p. p permutes ?U}"
1.382 +  let ?f = "(\<lambda>i. if i = k then c*s a i else b i)::'n \<Rightarrow> 'a::comm_ring_1^'n"
1.383 +  let ?g = "(\<lambda> i. if i = k then a i else b i)::'n \<Rightarrow> 'a::comm_ring_1^'n"
1.384 +  fix p
1.385 +  assume p: "p \<in> ?pU"
1.386 +  let ?Uk = "?U - {k}"
1.387 +  from p have pU: "p permutes ?U"
1.388 +    by blast
1.389 +  have kU: "?U = insert k ?Uk"
1.390 +    by blast
1.391 +  {
1.392 +    fix j
1.393 +    assume j: "j \<in> ?Uk"
1.394 +    from j have "?f j \$ p j = ?g j \$ p j"
1.395 +      by simp
1.396 +  }
1.397 +  then have th1: "setprod (\<lambda>i. ?f i \$ p i) ?Uk = setprod (\<lambda>i. ?g i \$ p i) ?Uk"
1.398 +    apply -
1.399 +    apply (rule setprod.cong)
1.400 +    apply simp_all
1.401 +    done
1.402 +  have th3: "finite ?Uk" "k \<notin> ?Uk"
1.403 +    by auto
1.404 +  have "setprod (\<lambda>i. ?f i \$ p i) ?U = setprod (\<lambda>i. ?f i \$ p i) (insert k ?Uk)"
1.405 +    unfolding kU[symmetric] ..
1.406 +  also have "\<dots> = ?f k \$ p k  * setprod (\<lambda>i. ?f i \$ p i) ?Uk"
1.407 +    apply (rule setprod.insert)
1.408 +    apply simp
1.409 +    apply blast
1.410 +    done
1.411 +  also have "\<dots> = (c*s a k) \$ p k * setprod (\<lambda>i. ?f i \$ p i) ?Uk"
1.412 +    by (simp add: field_simps)
1.413 +  also have "\<dots> = c* (a k \$ p k * setprod (\<lambda>i. ?g i \$ p i) ?Uk)"
1.414 +    unfolding th1 by (simp add: ac_simps)
1.415 +  also have "\<dots> = c* (setprod (\<lambda>i. ?g i \$ p i) (insert k ?Uk))"
1.416 +    unfolding setprod.insert[OF th3] by simp
1.417 +  finally have "setprod (\<lambda>i. ?f i \$ p i) ?U = c* (setprod (\<lambda>i. ?g i \$ p i) ?U)"
1.418 +    unfolding kU[symmetric] .
1.419 +  then show "of_int (sign p) * setprod (\<lambda>i. ?f i \$ p i) ?U =
1.420 +    c * (of_int (sign p) * setprod (\<lambda>i. ?g i \$ p i) ?U)"
1.421 +    by (simp add: field_simps)
1.422 +qed rule
1.423 +
1.424 +lemma det_row_0:
1.425 +  fixes b :: "'n::finite \<Rightarrow> _ ^ 'n"
1.426 +  shows "det((\<chi> i. if i = k then 0 else b i)::'a::comm_ring_1^'n^'n) = 0"
1.427 +  using det_row_mul[of k 0 "\<lambda>i. 1" b]
1.428 +  apply simp
1.429 +  apply (simp only: vector_smult_lzero)
1.430 +  done
1.431 +
1.432 +lemma det_row_operation:
1.433 +  fixes A :: "'a::linordered_idom^'n^'n"
1.434 +  assumes ij: "i \<noteq> j"
1.435 +  shows "det (\<chi> k. if k = i then row i A + c *s row j A else row k A) = det A"
1.436 +proof -
1.437 +  let ?Z = "(\<chi> k. if k = i then row j A else row k A) :: 'a ^'n^'n"
1.438 +  have th: "row i ?Z = row j ?Z" by (vector row_def)
1.439 +  have th2: "((\<chi> k. if k = i then row i A else row k A) :: 'a^'n^'n) = A"
1.440 +    by (vector row_def)
1.441 +  show ?thesis
1.442 +    unfolding det_row_add [of i] det_row_mul[of i] det_identical_rows[OF ij th] th2
1.443 +    by simp
1.444 +qed
1.445 +
1.446 +lemma det_row_span:
1.447 +  fixes A :: "real^'n^'n"
1.448 +  assumes x: "x \<in> span {row j A |j. j \<noteq> i}"
1.449 +  shows "det (\<chi> k. if k = i then row i A + x else row k A) = det A"
1.450 +proof -
1.451 +  let ?U = "UNIV :: 'n set"
1.452 +  let ?S = "{row j A |j. j \<noteq> i}"
1.453 +  let ?d = "\<lambda>x. det (\<chi> k. if k = i then x else row k A)"
1.454 +  let ?P = "\<lambda>x. ?d (row i A + x) = det A"
1.455 +  {
1.456 +    fix k
1.457 +    have "(if k = i then row i A + 0 else row k A) = row k A"
1.458 +      by simp
1.459 +  }
1.460 +  then have P0: "?P 0"
1.461 +    apply -
1.462 +    apply (rule cong[of det, OF refl])
1.463 +    apply (vector row_def)
1.464 +    done
1.465 +  moreover
1.466 +  {
1.467 +    fix c z y
1.468 +    assume zS: "z \<in> ?S" and Py: "?P y"
1.469 +    from zS obtain j where j: "z = row j A" "i \<noteq> j"
1.470 +      by blast
1.471 +    let ?w = "row i A + y"
1.472 +    have th0: "row i A + (c*s z + y) = ?w + c*s z"
1.473 +      by vector
1.474 +    have thz: "?d z = 0"
1.475 +      apply (rule det_identical_rows[OF j(2)])
1.476 +      using j
1.477 +      apply (vector row_def)
1.478 +      done
1.479 +    have "?d (row i A + (c*s z + y)) = ?d (?w + c*s z)"
1.480 +      unfolding th0 ..
1.481 +    then have "?P (c*s z + y)"
1.482 +      unfolding thz Py det_row_mul[of i] det_row_add[of i]
1.483 +      by simp
1.484 +  }
1.485 +  ultimately show ?thesis
1.486 +    apply -
1.487 +    apply (rule span_induct_alt[of ?P ?S, OF P0, folded scalar_mult_eq_scaleR])
1.488 +    apply blast
1.489 +    apply (rule x)
1.490 +    done
1.491 +qed
1.492 +
1.493 +text \<open>
1.494 +  May as well do this, though it's a bit unsatisfactory since it ignores
1.495 +  exact duplicates by considering the rows/columns as a set.
1.496 +\<close>
1.497 +
1.498 +lemma det_dependent_rows:
1.499 +  fixes A:: "real^'n^'n"
1.500 +  assumes d: "dependent (rows A)"
1.501 +  shows "det A = 0"
1.502 +proof -
1.503 +  let ?U = "UNIV :: 'n set"
1.504 +  from d obtain i where i: "row i A \<in> span (rows A - {row i A})"
1.505 +    unfolding dependent_def rows_def by blast
1.506 +  {
1.507 +    fix j k
1.508 +    assume jk: "j \<noteq> k" and c: "row j A = row k A"
1.509 +    from det_identical_rows[OF jk c] have ?thesis .
1.510 +  }
1.511 +  moreover
1.512 +  {
1.513 +    assume H: "\<And> i j. i \<noteq> j \<Longrightarrow> row i A \<noteq> row j A"
1.514 +    have th0: "- row i A \<in> span {row j A|j. j \<noteq> i}"
1.515 +      apply (rule span_neg)
1.516 +      apply (rule set_rev_mp)
1.517 +      apply (rule i)
1.518 +      apply (rule span_mono)
1.519 +      using H i
1.520 +      apply (auto simp add: rows_def)
1.521 +      done
1.522 +    from det_row_span[OF th0]
1.523 +    have "det A = det (\<chi> k. if k = i then 0 *s 1 else row k A)"
1.524 +      unfolding right_minus vector_smult_lzero ..
1.525 +    with det_row_mul[of i "0::real" "\<lambda>i. 1"]
1.526 +    have "det A = 0" by simp
1.527 +  }
1.528 +  ultimately show ?thesis by blast
1.529 +qed
1.530 +
1.531 +lemma det_dependent_columns:
1.532 +  assumes d: "dependent (columns (A::real^'n^'n))"
1.533 +  shows "det A = 0"
1.534 +  by (metis d det_dependent_rows rows_transpose det_transpose)
1.535 +
1.536 +text \<open>Multilinearity and the multiplication formula.\<close>
1.537 +
1.538 +lemma Cart_lambda_cong: "(\<And>x. f x = g x) \<Longrightarrow> (vec_lambda f::'a^'n) = (vec_lambda g :: 'a^'n)"
1.539 +  by (rule iffD1[OF vec_lambda_unique]) vector
1.540 +
1.541 +lemma det_linear_row_setsum:
1.542 +  assumes fS: "finite S"
1.543 +  shows "det ((\<chi> i. if i = k then setsum (a i) S else c i)::'a::comm_ring_1^'n^'n) =
1.544 +    setsum (\<lambda>j. det ((\<chi> i. if i = k then a  i j else c i)::'a^'n^'n)) S"
1.545 +proof (induct rule: finite_induct[OF fS])
1.546 +  case 1
1.547 +  then show ?case
1.548 +    apply simp
1.549 +    unfolding setsum.empty det_row_0[of k]
1.550 +    apply rule
1.551 +    done
1.552 +next
1.553 +  case (2 x F)
1.554 +  then show ?case
1.556 +qed
1.557 +
1.558 +lemma finite_bounded_functions:
1.559 +  assumes fS: "finite S"
1.560 +  shows "finite {f. (\<forall>i \<in> {1.. (k::nat)}. f i \<in> S) \<and> (\<forall>i. i \<notin> {1 .. k} \<longrightarrow> f i = i)}"
1.561 +proof (induct k)
1.562 +  case 0
1.563 +  have th: "{f. \<forall>i. f i = i} = {id}"
1.564 +    by auto
1.565 +  show ?case
1.566 +    by (auto simp add: th)
1.567 +next
1.568 +  case (Suc k)
1.569 +  let ?f = "\<lambda>(y::nat,g) i. if i = Suc k then y else g i"
1.570 +  let ?S = "?f ` (S \<times> {f. (\<forall>i\<in>{1..k}. f i \<in> S) \<and> (\<forall>i. i \<notin> {1..k} \<longrightarrow> f i = i)})"
1.571 +  have "?S = {f. (\<forall>i\<in>{1.. Suc k}. f i \<in> S) \<and> (\<forall>i. i \<notin> {1.. Suc k} \<longrightarrow> f i = i)}"
1.572 +    apply (auto simp add: image_iff)
1.573 +    apply (rule_tac x="x (Suc k)" in bexI)
1.574 +    apply (rule_tac x = "\<lambda>i. if i = Suc k then i else x i" in exI)
1.575 +    apply auto
1.576 +    done
1.577 +  with finite_imageI[OF finite_cartesian_product[OF fS Suc.hyps(1)], of ?f]
1.578 +  show ?case
1.579 +    by metis
1.580 +qed
1.581 +
1.582 +
1.583 +lemma det_linear_rows_setsum_lemma:
1.584 +  assumes fS: "finite S"
1.585 +    and fT: "finite T"
1.586 +  shows "det ((\<chi> i. if i \<in> T then setsum (a i) S else c i):: 'a::comm_ring_1^'n^'n) =
1.587 +    setsum (\<lambda>f. det((\<chi> i. if i \<in> T then a i (f i) else c i)::'a^'n^'n))
1.588 +      {f. (\<forall>i \<in> T. f i \<in> S) \<and> (\<forall>i. i \<notin> T \<longrightarrow> f i = i)}"
1.589 +  using fT
1.590 +proof (induct T arbitrary: a c set: finite)
1.591 +  case empty
1.592 +  have th0: "\<And>x y. (\<chi> i. if i \<in> {} then x i else y i) = (\<chi> i. y i)"
1.593 +    by vector
1.594 +  from empty.prems show ?case
1.595 +    unfolding th0 by (simp add: eq_id_iff)
1.596 +next
1.597 +  case (insert z T a c)
1.598 +  let ?F = "\<lambda>T. {f. (\<forall>i \<in> T. f i \<in> S) \<and> (\<forall>i. i \<notin> T \<longrightarrow> f i = i)}"
1.599 +  let ?h = "\<lambda>(y,g) i. if i = z then y else g i"
1.600 +  let ?k = "\<lambda>h. (h(z),(\<lambda>i. if i = z then i else h i))"
1.601 +  let ?s = "\<lambda> k a c f. det((\<chi> i. if i \<in> T then a i (f i) else c i)::'a^'n^'n)"
1.602 +  let ?c = "\<lambda>j i. if i = z then a i j else c i"
1.603 +  have thif: "\<And>a b c d. (if a \<or> b then c else d) = (if a then c else if b then c else d)"
1.604 +    by simp
1.605 +  have thif2: "\<And>a b c d e. (if a then b else if c then d else e) =
1.606 +     (if c then (if a then b else d) else (if a then b else e))"
1.607 +    by simp
1.608 +  from \<open>z \<notin> T\<close> have nz: "\<And>i. i \<in> T \<Longrightarrow> i = z \<longleftrightarrow> False"
1.609 +    by auto
1.610 +  have "det (\<chi> i. if i \<in> insert z T then setsum (a i) S else c i) =
1.611 +    det (\<chi> i. if i = z then setsum (a i) S else if i \<in> T then setsum (a i) S else c i)"
1.612 +    unfolding insert_iff thif ..
1.613 +  also have "\<dots> = (\<Sum>j\<in>S. det (\<chi> i. if i \<in> T then setsum (a i) S else if i = z then a i j else c i))"
1.614 +    unfolding det_linear_row_setsum[OF fS]
1.615 +    apply (subst thif2)
1.616 +    using nz
1.617 +    apply (simp cong del: if_weak_cong cong add: if_cong)
1.618 +    done
1.619 +  finally have tha:
1.620 +    "det (\<chi> i. if i \<in> insert z T then setsum (a i) S else c i) =
1.621 +     (\<Sum>(j, f)\<in>S \<times> ?F T. det (\<chi> i. if i \<in> T then a i (f i)
1.622 +                                else if i = z then a i j
1.623 +                                else c i))"
1.624 +    unfolding insert.hyps unfolding setsum.cartesian_product by blast
1.625 +  show ?case unfolding tha
1.626 +    using \<open>z \<notin> T\<close>
1.627 +    by (intro setsum.reindex_bij_witness[where i="?k" and j="?h"])
1.628 +       (auto intro!: cong[OF refl[of det]] simp: vec_eq_iff)
1.629 +qed
1.630 +
1.631 +lemma det_linear_rows_setsum:
1.632 +  fixes S :: "'n::finite set"
1.633 +  assumes fS: "finite S"
1.634 +  shows "det (\<chi> i. setsum (a i) S) =
1.635 +    setsum (\<lambda>f. det (\<chi> i. a i (f i) :: 'a::comm_ring_1 ^ 'n^'n)) {f. \<forall>i. f i \<in> S}"
1.636 +proof -
1.637 +  have th0: "\<And>x y. ((\<chi> i. if i \<in> (UNIV:: 'n set) then x i else y i) :: 'a^'n^'n) = (\<chi> i. x i)"
1.638 +    by vector
1.639 +  from det_linear_rows_setsum_lemma[OF fS, of "UNIV :: 'n set" a, unfolded th0, OF finite]
1.640 +  show ?thesis by simp
1.641 +qed
1.642 +
1.643 +lemma matrix_mul_setsum_alt:
1.644 +  fixes A B :: "'a::comm_ring_1^'n^'n"
1.645 +  shows "A ** B = (\<chi> i. setsum (\<lambda>k. A\$i\$k *s B \$ k) (UNIV :: 'n set))"
1.646 +  by (vector matrix_matrix_mult_def setsum_component)
1.647 +
1.648 +lemma det_rows_mul:
1.649 +  "det((\<chi> i. c i *s a i)::'a::comm_ring_1^'n^'n) =
1.650 +    setprod (\<lambda>i. c i) (UNIV:: 'n set) * det((\<chi> i. a i)::'a^'n^'n)"
1.652 +  let ?U = "UNIV :: 'n set"
1.653 +  let ?PU = "{p. p permutes ?U}"
1.654 +  fix p
1.655 +  assume pU: "p \<in> ?PU"
1.656 +  let ?s = "of_int (sign p)"
1.657 +  from pU have p: "p permutes ?U"
1.658 +    by blast
1.659 +  have "setprod (\<lambda>i. c i * a i \$ p i) ?U = setprod c ?U * setprod (\<lambda>i. a i \$ p i) ?U"
1.660 +    unfolding setprod.distrib ..
1.661 +  then show "?s * (\<Prod>xa\<in>?U. c xa * a xa \$ p xa) =
1.662 +    setprod c ?U * (?s* (\<Prod>xa\<in>?U. a xa \$ p xa))"
1.663 +    by (simp add: field_simps)
1.664 +qed rule
1.665 +
1.666 +lemma det_mul:
1.667 +  fixes A B :: "'a::linordered_idom^'n^'n"
1.668 +  shows "det (A ** B) = det A * det B"
1.669 +proof -
1.670 +  let ?U = "UNIV :: 'n set"
1.671 +  let ?F = "{f. (\<forall>i\<in> ?U. f i \<in> ?U) \<and> (\<forall>i. i \<notin> ?U \<longrightarrow> f i = i)}"
1.672 +  let ?PU = "{p. p permutes ?U}"
1.673 +  have fU: "finite ?U"
1.674 +    by simp
1.675 +  have fF: "finite ?F"
1.676 +    by (rule finite)
1.677 +  {
1.678 +    fix p
1.679 +    assume p: "p permutes ?U"
1.680 +    have "p \<in> ?F" unfolding mem_Collect_eq permutes_in_image[OF p]
1.681 +      using p[unfolded permutes_def] by simp
1.682 +  }
1.683 +  then have PUF: "?PU \<subseteq> ?F" by blast
1.684 +  {
1.685 +    fix f
1.686 +    assume fPU: "f \<in> ?F - ?PU"
1.687 +    have fUU: "f ` ?U \<subseteq> ?U"
1.688 +      using fPU by auto
1.689 +    from fPU have f: "\<forall>i \<in> ?U. f i \<in> ?U" "\<forall>i. i \<notin> ?U \<longrightarrow> f i = i" "\<not>(\<forall>y. \<exists>!x. f x = y)"
1.690 +      unfolding permutes_def by auto
1.691 +
1.692 +    let ?A = "(\<chi> i. A\$i\$f i *s B\$f i) :: 'a^'n^'n"
1.693 +    let ?B = "(\<chi> i. B\$f i) :: 'a^'n^'n"
1.694 +    {
1.695 +      assume fni: "\<not> inj_on f ?U"
1.696 +      then obtain i j where ij: "f i = f j" "i \<noteq> j"
1.697 +        unfolding inj_on_def by blast
1.698 +      from ij
1.699 +      have rth: "row i ?B = row j ?B"
1.700 +        by (vector row_def)
1.701 +      from det_identical_rows[OF ij(2) rth]
1.702 +      have "det (\<chi> i. A\$i\$f i *s B\$f i) = 0"
1.703 +        unfolding det_rows_mul by simp
1.704 +    }
1.705 +    moreover
1.706 +    {
1.707 +      assume fi: "inj_on f ?U"
1.708 +      from f fi have fith: "\<And>i j. f i = f j \<Longrightarrow> i = j"
1.709 +        unfolding inj_on_def by metis
1.710 +      note fs = fi[unfolded surjective_iff_injective_gen[OF fU fU refl fUU, symmetric]]
1.711 +      {
1.712 +        fix y
1.713 +        from fs f have "\<exists>x. f x = y"
1.714 +          by blast
1.715 +        then obtain x where x: "f x = y"
1.716 +          by blast
1.717 +        {
1.718 +          fix z
1.719 +          assume z: "f z = y"
1.720 +          from fith x z have "z = x"
1.721 +            by metis
1.722 +        }
1.723 +        with x have "\<exists>!x. f x = y"
1.724 +          by blast
1.725 +      }
1.726 +      with f(3) have "det (\<chi> i. A\$i\$f i *s B\$f i) = 0"
1.727 +        by blast
1.728 +    }
1.729 +    ultimately have "det (\<chi> i. A\$i\$f i *s B\$f i) = 0"
1.730 +      by blast
1.731 +  }
1.732 +  then have zth: "\<forall> f\<in> ?F - ?PU. det (\<chi> i. A\$i\$f i *s B\$f i) = 0"
1.733 +    by simp
1.734 +  {
1.735 +    fix p
1.736 +    assume pU: "p \<in> ?PU"
1.737 +    from pU have p: "p permutes ?U"
1.738 +      by blast
1.739 +    let ?s = "\<lambda>p. of_int (sign p)"
1.740 +    let ?f = "\<lambda>q. ?s p * (\<Prod>i\<in> ?U. A \$ i \$ p i) * (?s q * (\<Prod>i\<in> ?U. B \$ i \$ q i))"
1.741 +    have "(setsum (\<lambda>q. ?s q *
1.742 +        (\<Prod>i\<in> ?U. (\<chi> i. A \$ i \$ p i *s B \$ p i :: 'a^'n^'n) \$ i \$ q i)) ?PU) =
1.743 +      (setsum (\<lambda>q. ?s p * (\<Prod>i\<in> ?U. A \$ i \$ p i) * (?s q * (\<Prod>i\<in> ?U. B \$ i \$ q i))) ?PU)"
1.744 +      unfolding sum_permutations_compose_right[OF permutes_inv[OF p], of ?f]
1.745 +    proof (rule setsum.cong)
1.746 +      fix q
1.747 +      assume qU: "q \<in> ?PU"
1.748 +      then have q: "q permutes ?U"
1.749 +        by blast
1.750 +      from p q have pp: "permutation p" and pq: "permutation q"
1.751 +        unfolding permutation_permutes by auto
1.752 +      have th00: "of_int (sign p) * of_int (sign p) = (1::'a)"
1.753 +        "\<And>a. of_int (sign p) * (of_int (sign p) * a) = a"
1.754 +        unfolding mult.assoc[symmetric]
1.755 +        unfolding of_int_mult[symmetric]
1.756 +        by (simp_all add: sign_idempotent)
1.757 +      have ths: "?s q = ?s p * ?s (q \<circ> inv p)"
1.758 +        using pp pq permutation_inverse[OF pp] sign_inverse[OF pp]
1.759 +        by (simp add:  th00 ac_simps sign_idempotent sign_compose)
1.760 +      have th001: "setprod (\<lambda>i. B\$i\$ q (inv p i)) ?U = setprod ((\<lambda>i. B\$i\$ q (inv p i)) \<circ> p) ?U"
1.761 +        by (rule setprod_permute[OF p])
1.762 +      have thp: "setprod (\<lambda>i. (\<chi> i. A\$i\$p i *s B\$p i :: 'a^'n^'n) \$i \$ q i) ?U =
1.763 +        setprod (\<lambda>i. A\$i\$p i) ?U * setprod (\<lambda>i. B\$i\$ q (inv p i)) ?U"
1.764 +        unfolding th001 setprod.distrib[symmetric] o_def permutes_inverses[OF p]
1.765 +        apply (rule setprod.cong[OF refl])
1.766 +        using permutes_in_image[OF q]
1.767 +        apply vector
1.768 +        done
1.769 +      show "?s q * setprod (\<lambda>i. (((\<chi> i. A\$i\$p i *s B\$p i) :: 'a^'n^'n)\$i\$q i)) ?U =
1.770 +        ?s p * (setprod (\<lambda>i. A\$i\$p i) ?U) * (?s (q \<circ> inv p) * setprod (\<lambda>i. B\$i\$(q \<circ> inv p) i) ?U)"
1.771 +        using ths thp pp pq permutation_inverse[OF pp] sign_inverse[OF pp]
1.772 +        by (simp add: sign_nz th00 field_simps sign_idempotent sign_compose)
1.773 +    qed rule
1.774 +  }
1.775 +  then have th2: "setsum (\<lambda>f. det (\<chi> i. A\$i\$f i *s B\$f i)) ?PU = det A * det B"
1.776 +    unfolding det_def setsum_product
1.777 +    by (rule setsum.cong [OF refl])
1.778 +  have "det (A**B) = setsum (\<lambda>f.  det (\<chi> i. A \$ i \$ f i *s B \$ f i)) ?F"
1.779 +    unfolding matrix_mul_setsum_alt det_linear_rows_setsum[OF fU]
1.780 +    by simp
1.781 +  also have "\<dots> = setsum (\<lambda>f. det (\<chi> i. A\$i\$f i *s B\$f i)) ?PU"
1.782 +    using setsum.mono_neutral_cong_left[OF fF PUF zth, symmetric]
1.783 +    unfolding det_rows_mul by auto
1.784 +  finally show ?thesis unfolding th2 .
1.785 +qed
1.786 +
1.787 +text \<open>Relation to invertibility.\<close>
1.788 +
1.789 +lemma invertible_left_inverse:
1.790 +  fixes A :: "real^'n^'n"
1.791 +  shows "invertible A \<longleftrightarrow> (\<exists>(B::real^'n^'n). B** A = mat 1)"
1.792 +  by (metis invertible_def matrix_left_right_inverse)
1.793 +
1.794 +lemma invertible_righ_inverse:
1.795 +  fixes A :: "real^'n^'n"
1.796 +  shows "invertible A \<longleftrightarrow> (\<exists>(B::real^'n^'n). A** B = mat 1)"
1.797 +  by (metis invertible_def matrix_left_right_inverse)
1.798 +
1.799 +lemma invertible_det_nz:
1.800 +  fixes A::"real ^'n^'n"
1.801 +  shows "invertible A \<longleftrightarrow> det A \<noteq> 0"
1.802 +proof -
1.803 +  {
1.804 +    assume "invertible A"
1.805 +    then obtain B :: "real ^'n^'n" where B: "A ** B = mat 1"
1.806 +      unfolding invertible_righ_inverse by blast
1.807 +    then have "det (A ** B) = det (mat 1 :: real ^'n^'n)"
1.808 +      by simp
1.809 +    then have "det A \<noteq> 0"
1.810 +      by (simp add: det_mul det_I) algebra
1.811 +  }
1.812 +  moreover
1.813 +  {
1.814 +    assume H: "\<not> invertible A"
1.815 +    let ?U = "UNIV :: 'n set"
1.816 +    have fU: "finite ?U"
1.817 +      by simp
1.818 +    from H obtain c i where c: "setsum (\<lambda>i. c i *s row i A) ?U = 0"
1.819 +      and iU: "i \<in> ?U"
1.820 +      and ci: "c i \<noteq> 0"
1.821 +      unfolding invertible_righ_inverse
1.822 +      unfolding matrix_right_invertible_independent_rows
1.823 +      by blast
1.824 +    have *: "\<And>(a::real^'n) b. a + b = 0 \<Longrightarrow> -a = b"
1.825 +      apply (drule_tac f="op + (- a)" in cong[OF refl])
1.826 +      apply (simp only: ab_left_minus add.assoc[symmetric])
1.827 +      apply simp
1.828 +      done
1.829 +    from c ci
1.830 +    have thr0: "- row i A = setsum (\<lambda>j. (1/ c i) *s (c j *s row j A)) (?U - {i})"
1.831 +      unfolding setsum.remove[OF fU iU] setsum_cmul
1.832 +      apply -
1.833 +      apply (rule vector_mul_lcancel_imp[OF ci])
1.834 +      apply (auto simp add: field_simps)
1.835 +      unfolding *
1.836 +      apply rule
1.837 +      done
1.838 +    have thr: "- row i A \<in> span {row j A| j. j \<noteq> i}"
1.839 +      unfolding thr0
1.840 +      apply (rule span_setsum)
1.841 +      apply simp
1.842 +      apply (rule span_mul [where 'a="real^'n", folded scalar_mult_eq_scaleR])+
1.843 +      apply (rule span_superset)
1.844 +      apply auto
1.845 +      done
1.846 +    let ?B = "(\<chi> k. if k = i then 0 else row k A) :: real ^'n^'n"
1.847 +    have thrb: "row i ?B = 0" using iU by (vector row_def)
1.848 +    have "det A = 0"
1.849 +      unfolding det_row_span[OF thr, symmetric] right_minus
1.850 +      unfolding det_zero_row[OF thrb] ..
1.851 +  }
1.852 +  ultimately show ?thesis
1.853 +    by blast
1.854 +qed
1.855 +
1.856 +text \<open>Cramer's rule.\<close>
1.857 +
1.858 +lemma cramer_lemma_transpose:
1.859 +  fixes A:: "real^'n^'n"
1.860 +    and x :: "real^'n"
1.861 +  shows "det ((\<chi> i. if i = k then setsum (\<lambda>i. x\$i *s row i A) (UNIV::'n set)
1.862 +                             else row i A)::real^'n^'n) = x\$k * det A"
1.863 +  (is "?lhs = ?rhs")
1.864 +proof -
1.865 +  let ?U = "UNIV :: 'n set"
1.866 +  let ?Uk = "?U - {k}"
1.867 +  have U: "?U = insert k ?Uk"
1.868 +    by blast
1.869 +  have fUk: "finite ?Uk"
1.870 +    by simp
1.871 +  have kUk: "k \<notin> ?Uk"
1.872 +    by simp
1.873 +  have th00: "\<And>k s. x\$k *s row k A + s = (x\$k - 1) *s row k A + row k A + s"
1.874 +    by (vector field_simps)
1.875 +  have th001: "\<And>f k . (\<lambda>x. if x = k then f k else f x) = f"
1.876 +    by auto
1.877 +  have "(\<chi> i. row i A) = A" by (vector row_def)
1.878 +  then have thd1: "det (\<chi> i. row i A) = det A"
1.879 +    by simp
1.880 +  have thd0: "det (\<chi> i. if i = k then row k A + (\<Sum>i \<in> ?Uk. x \$ i *s row i A) else row i A) = det A"
1.881 +    apply (rule det_row_span)
1.882 +    apply (rule span_setsum)
1.883 +    apply (rule span_mul [where 'a="real^'n", folded scalar_mult_eq_scaleR])+
1.884 +    apply (rule span_superset)
1.885 +    apply auto
1.886 +    done
1.887 +  show "?lhs = x\$k * det A"
1.888 +    apply (subst U)
1.889 +    unfolding setsum.insert[OF fUk kUk]
1.890 +    apply (subst th00)
1.893 +    unfolding thd0
1.894 +    unfolding det_row_mul
1.895 +    unfolding th001[of k "\<lambda>i. row i A"]
1.896 +    unfolding thd1
1.897 +    apply (simp add: field_simps)
1.898 +    done
1.899 +qed
1.900 +
1.901 +lemma cramer_lemma:
1.902 +  fixes A :: "real^'n^'n"
1.903 +  shows "det((\<chi> i j. if j = k then (A *v x)\$i else A\$i\$j):: real^'n^'n) = x\$k * det A"
1.904 +proof -
1.905 +  let ?U = "UNIV :: 'n set"
1.906 +  have *: "\<And>c. setsum (\<lambda>i. c i *s row i (transpose A)) ?U = setsum (\<lambda>i. c i *s column i A) ?U"
1.907 +    by (auto simp add: row_transpose intro: setsum.cong)
1.908 +  show ?thesis
1.909 +    unfolding matrix_mult_vsum
1.910 +    unfolding cramer_lemma_transpose[of k x "transpose A", unfolded det_transpose, symmetric]
1.911 +    unfolding *[of "\<lambda>i. x\$i"]
1.912 +    apply (subst det_transpose[symmetric])
1.913 +    apply (rule cong[OF refl[of det]])
1.914 +    apply (vector transpose_def column_def row_def)
1.915 +    done
1.916 +qed
1.917 +
1.918 +lemma cramer:
1.919 +  fixes A ::"real^'n^'n"
1.920 +  assumes d0: "det A \<noteq> 0"
1.921 +  shows "A *v x = b \<longleftrightarrow> x = (\<chi> k. det(\<chi> i j. if j=k then b\$i else A\$i\$j) / det A)"
1.922 +proof -
1.923 +  from d0 obtain B where B: "A ** B = mat 1" "B ** A = mat 1"
1.924 +    unfolding invertible_det_nz[symmetric] invertible_def
1.925 +    by blast
1.926 +  have "(A ** B) *v b = b"
1.927 +    by (simp add: B matrix_vector_mul_lid)
1.928 +  then have "A *v (B *v b) = b"
1.929 +    by (simp add: matrix_vector_mul_assoc)
1.930 +  then have xe: "\<exists>x. A *v x = b"
1.931 +    by blast
1.932 +  {
1.933 +    fix x
1.934 +    assume x: "A *v x = b"
1.935 +    have "x = (\<chi> k. det(\<chi> i j. if j=k then b\$i else A\$i\$j) / det A)"
1.936 +      unfolding x[symmetric]
1.937 +      using d0 by (simp add: vec_eq_iff cramer_lemma field_simps)
1.938 +  }
1.939 +  with xe show ?thesis
1.940 +    by auto
1.941 +qed
1.942 +
1.943 +text \<open>Orthogonality of a transformation and matrix.\<close>
1.944 +
1.945 +definition "orthogonal_transformation f \<longleftrightarrow> linear f \<and> (\<forall>v w. f v \<bullet> f w = v \<bullet> w)"
1.946 +
1.947 +lemma orthogonal_transformation:
1.948 +  "orthogonal_transformation f \<longleftrightarrow> linear f \<and> (\<forall>(v::real ^_). norm (f v) = norm v)"
1.949 +  unfolding orthogonal_transformation_def
1.950 +  apply auto
1.951 +  apply (erule_tac x=v in allE)+
1.952 +  apply (simp add: norm_eq_sqrt_inner)
1.954 +  done
1.955 +
1.956 +definition "orthogonal_matrix (Q::'a::semiring_1^'n^'n) \<longleftrightarrow>
1.957 +  transpose Q ** Q = mat 1 \<and> Q ** transpose Q = mat 1"
1.958 +
1.959 +lemma orthogonal_matrix: "orthogonal_matrix (Q:: real ^'n^'n) \<longleftrightarrow> transpose Q ** Q = mat 1"
1.960 +  by (metis matrix_left_right_inverse orthogonal_matrix_def)
1.961 +
1.962 +lemma orthogonal_matrix_id: "orthogonal_matrix (mat 1 :: _^'n^'n)"
1.963 +  by (simp add: orthogonal_matrix_def transpose_mat matrix_mul_lid)
1.964 +
1.965 +lemma orthogonal_matrix_mul:
1.966 +  fixes A :: "real ^'n^'n"
1.967 +  assumes oA : "orthogonal_matrix A"
1.968 +    and oB: "orthogonal_matrix B"
1.969 +  shows "orthogonal_matrix(A ** B)"
1.970 +  using oA oB
1.971 +  unfolding orthogonal_matrix matrix_transpose_mul
1.972 +  apply (subst matrix_mul_assoc)
1.973 +  apply (subst matrix_mul_assoc[symmetric])
1.974 +  apply (simp add: matrix_mul_rid)
1.975 +  done
1.976 +
1.977 +lemma orthogonal_transformation_matrix:
1.978 +  fixes f:: "real^'n \<Rightarrow> real^'n"
1.979 +  shows "orthogonal_transformation f \<longleftrightarrow> linear f \<and> orthogonal_matrix(matrix f)"
1.980 +  (is "?lhs \<longleftrightarrow> ?rhs")
1.981 +proof -
1.982 +  let ?mf = "matrix f"
1.983 +  let ?ot = "orthogonal_transformation f"
1.984 +  let ?U = "UNIV :: 'n set"
1.985 +  have fU: "finite ?U" by simp
1.986 +  let ?m1 = "mat 1 :: real ^'n^'n"
1.987 +  {
1.988 +    assume ot: ?ot
1.989 +    from ot have lf: "linear f" and fd: "\<forall>v w. f v \<bullet> f w = v \<bullet> w"
1.990 +      unfolding  orthogonal_transformation_def orthogonal_matrix by blast+
1.991 +    {
1.992 +      fix i j
1.993 +      let ?A = "transpose ?mf ** ?mf"
1.994 +      have th0: "\<And>b (x::'a::comm_ring_1). (if b then 1 else 0)*x = (if b then x else 0)"
1.995 +        "\<And>b (x::'a::comm_ring_1). x*(if b then 1 else 0) = (if b then x else 0)"
1.996 +        by simp_all
1.997 +      from fd[rule_format, of "axis i 1" "axis j 1",
1.998 +        simplified matrix_works[OF lf, symmetric] dot_matrix_vector_mul]
1.999 +      have "?A\$i\$j = ?m1 \$ i \$ j"
1.1000 +        by (simp add: inner_vec_def matrix_matrix_mult_def columnvector_def rowvector_def
1.1001 +            th0 setsum.delta[OF fU] mat_def axis_def)
1.1002 +    }
1.1003 +    then have "orthogonal_matrix ?mf"
1.1004 +      unfolding orthogonal_matrix
1.1005 +      by vector
1.1006 +    with lf have ?rhs
1.1007 +      by blast
1.1008 +  }
1.1009 +  moreover
1.1010 +  {
1.1011 +    assume lf: "linear f" and om: "orthogonal_matrix ?mf"
1.1012 +    from lf om have ?lhs
1.1013 +      apply (simp only: orthogonal_matrix_def norm_eq orthogonal_transformation)
1.1014 +      apply (simp only: matrix_works[OF lf, symmetric])
1.1015 +      apply (subst dot_matrix_vector_mul)
1.1016 +      apply (simp add: dot_matrix_product matrix_mul_lid)
1.1017 +      done
1.1018 +  }
1.1019 +  ultimately show ?thesis
1.1020 +    by blast
1.1021 +qed
1.1022 +
1.1023 +lemma det_orthogonal_matrix:
1.1024 +  fixes Q:: "'a::linordered_idom^'n^'n"
1.1025 +  assumes oQ: "orthogonal_matrix Q"
1.1026 +  shows "det Q = 1 \<or> det Q = - 1"
1.1027 +proof -
1.1028 +  have th: "\<And>x::'a. x = 1 \<or> x = - 1 \<longleftrightarrow> x*x = 1" (is "\<And>x::'a. ?ths x")
1.1029 +  proof -
1.1030 +    fix x:: 'a
1.1031 +    have th0: "x * x - 1 = (x - 1) * (x + 1)"
1.1032 +      by (simp add: field_simps)
1.1033 +    have th1: "\<And>(x::'a) y. x = - y \<longleftrightarrow> x + y = 0"
1.1034 +      apply (subst eq_iff_diff_eq_0)
1.1035 +      apply simp
1.1036 +      done
1.1037 +    have "x * x = 1 \<longleftrightarrow> x * x - 1 = 0"
1.1038 +      by simp
1.1039 +    also have "\<dots> \<longleftrightarrow> x = 1 \<or> x = - 1"
1.1040 +      unfolding th0 th1 by simp
1.1041 +    finally show "?ths x" ..
1.1042 +  qed
1.1043 +  from oQ have "Q ** transpose Q = mat 1"
1.1044 +    by (metis orthogonal_matrix_def)
1.1045 +  then have "det (Q ** transpose Q) = det (mat 1:: 'a^'n^'n)"
1.1046 +    by simp
1.1047 +  then have "det Q * det Q = 1"
1.1048 +    by (simp add: det_mul det_I det_transpose)
1.1049 +  then show ?thesis unfolding th .
1.1050 +qed
1.1051 +
1.1052 +text \<open>Linearity of scaling, and hence isometry, that preserves origin.\<close>
1.1053 +
1.1054 +lemma scaling_linear:
1.1055 +  fixes f :: "real ^'n \<Rightarrow> real ^'n"
1.1056 +  assumes f0: "f 0 = 0"
1.1057 +    and fd: "\<forall>x y. dist (f x) (f y) = c * dist x y"
1.1058 +  shows "linear f"
1.1059 +proof -
1.1060 +  {
1.1061 +    fix v w
1.1062 +    {
1.1063 +      fix x
1.1064 +      note fd[rule_format, of x 0, unfolded dist_norm f0 diff_0_right]
1.1065 +    }
1.1066 +    note th0 = this
1.1067 +    have "f v \<bullet> f w = c\<^sup>2 * (v \<bullet> w)"
1.1068 +      unfolding dot_norm_neg dist_norm[symmetric]
1.1069 +      unfolding th0 fd[rule_format] by (simp add: power2_eq_square field_simps)}
1.1070 +  note fc = this
1.1071 +  show ?thesis
1.1072 +    unfolding linear_iff vector_eq[where 'a="real^'n"] scalar_mult_eq_scaleR
1.1074 +qed
1.1075 +
1.1076 +lemma isometry_linear:
1.1077 +  "f (0:: real^'n) = (0:: real^'n) \<Longrightarrow> \<forall>x y. dist(f x) (f y) = dist x y \<Longrightarrow> linear f"
1.1078 +  by (rule scaling_linear[where c=1]) simp_all
1.1079 +
1.1080 +text \<open>Hence another formulation of orthogonal transformation.\<close>
1.1081 +
1.1082 +lemma orthogonal_transformation_isometry:
1.1083 +  "orthogonal_transformation f \<longleftrightarrow> f(0::real^'n) = (0::real^'n) \<and> (\<forall>x y. dist(f x) (f y) = dist x y)"
1.1084 +  unfolding orthogonal_transformation
1.1085 +  apply (rule iffI)
1.1086 +  apply clarify
1.1087 +  apply (clarsimp simp add: linear_0 linear_diff[symmetric] dist_norm)
1.1088 +  apply (rule conjI)
1.1089 +  apply (rule isometry_linear)
1.1090 +  apply simp
1.1091 +  apply simp
1.1092 +  apply clarify
1.1093 +  apply (erule_tac x=v in allE)
1.1094 +  apply (erule_tac x=0 in allE)
1.1095 +  apply (simp add: dist_norm)
1.1096 +  done
1.1097 +
1.1098 +text \<open>Can extend an isometry from unit sphere.\<close>
1.1099 +
1.1100 +lemma isometry_sphere_extend:
1.1101 +  fixes f:: "real ^'n \<Rightarrow> real ^'n"
1.1102 +  assumes f1: "\<forall>x. norm x = 1 \<longrightarrow> norm (f x) = 1"
1.1103 +    and fd1: "\<forall> x y. norm x = 1 \<longrightarrow> norm y = 1 \<longrightarrow> dist (f x) (f y) = dist x y"
1.1104 +  shows "\<exists>g. orthogonal_transformation g \<and> (\<forall>x. norm x = 1 \<longrightarrow> g x = f x)"
1.1105 +proof -
1.1106 +  {
1.1107 +    fix x y x' y' x0 y0 x0' y0' :: "real ^'n"
1.1108 +    assume H:
1.1109 +      "x = norm x *\<^sub>R x0"
1.1110 +      "y = norm y *\<^sub>R y0"
1.1111 +      "x' = norm x *\<^sub>R x0'" "y' = norm y *\<^sub>R y0'"
1.1112 +      "norm x0 = 1" "norm x0' = 1" "norm y0 = 1" "norm y0' = 1"
1.1113 +      "norm(x0' - y0') = norm(x0 - y0)"
1.1114 +    then have *: "x0 \<bullet> y0 = x0' \<bullet> y0' + y0' \<bullet> x0' - y0 \<bullet> x0 "
1.1116 +    have "norm(x' - y') = norm(x - y)"
1.1117 +      apply (subst H(1))
1.1118 +      apply (subst H(2))
1.1119 +      apply (subst H(3))
1.1120 +      apply (subst H(4))
1.1121 +      using H(5-9)
1.1122 +      apply (simp add: norm_eq norm_eq_1)
1.1123 +      apply (simp add: inner_diff scalar_mult_eq_scaleR)
1.1124 +      unfolding *
1.1125 +      apply (simp add: field_simps)
1.1126 +      done
1.1127 +  }
1.1128 +  note th0 = this
1.1129 +  let ?g = "\<lambda>x. if x = 0 then 0 else norm x *\<^sub>R f (inverse (norm x) *\<^sub>R x)"
1.1130 +  {
1.1131 +    fix x:: "real ^'n"
1.1132 +    assume nx: "norm x = 1"
1.1133 +    have "?g x = f x"
1.1134 +      using nx by auto
1.1135 +  }
1.1136 +  then have thfg: "\<forall>x. norm x = 1 \<longrightarrow> ?g x = f x"
1.1137 +    by blast
1.1138 +  have g0: "?g 0 = 0"
1.1139 +    by simp
1.1140 +  {
1.1141 +    fix x y :: "real ^'n"
1.1142 +    {
1.1143 +      assume "x = 0" "y = 0"
1.1144 +      then have "dist (?g x) (?g y) = dist x y"
1.1145 +        by simp
1.1146 +    }
1.1147 +    moreover
1.1148 +    {
1.1149 +      assume "x = 0" "y \<noteq> 0"
1.1150 +      then have "dist (?g x) (?g y) = dist x y"
1.1151 +        apply (simp add: dist_norm)
1.1152 +        apply (rule f1[rule_format])
1.1153 +        apply (simp add: field_simps)
1.1154 +        done
1.1155 +    }
1.1156 +    moreover
1.1157 +    {
1.1158 +      assume "x \<noteq> 0" "y = 0"
1.1159 +      then have "dist (?g x) (?g y) = dist x y"
1.1160 +        apply (simp add: dist_norm)
1.1161 +        apply (rule f1[rule_format])
1.1162 +        apply (simp add: field_simps)
1.1163 +        done
1.1164 +    }
1.1165 +    moreover
1.1166 +    {
1.1167 +      assume z: "x \<noteq> 0" "y \<noteq> 0"
1.1168 +      have th00:
1.1169 +        "x = norm x *\<^sub>R (inverse (norm x) *\<^sub>R x)"
1.1170 +        "y = norm y *\<^sub>R (inverse (norm y) *\<^sub>R y)"
1.1171 +        "norm x *\<^sub>R f ((inverse (norm x) *\<^sub>R x)) = norm x *\<^sub>R f (inverse (norm x) *\<^sub>R x)"
1.1172 +        "norm y *\<^sub>R f (inverse (norm y) *\<^sub>R y) = norm y *\<^sub>R f (inverse (norm y) *\<^sub>R y)"
1.1173 +        "norm (inverse (norm x) *\<^sub>R x) = 1"
1.1174 +        "norm (f (inverse (norm x) *\<^sub>R x)) = 1"
1.1175 +        "norm (inverse (norm y) *\<^sub>R y) = 1"
1.1176 +        "norm (f (inverse (norm y) *\<^sub>R y)) = 1"
1.1177 +        "norm (f (inverse (norm x) *\<^sub>R x) - f (inverse (norm y) *\<^sub>R y)) =
1.1178 +          norm (inverse (norm x) *\<^sub>R x - inverse (norm y) *\<^sub>R y)"
1.1179 +        using z
1.1180 +        by (auto simp add: field_simps intro: f1[rule_format] fd1[rule_format, unfolded dist_norm])
1.1181 +      from z th0[OF th00] have "dist (?g x) (?g y) = dist x y"
1.1182 +        by (simp add: dist_norm)
1.1183 +    }
1.1184 +    ultimately have "dist (?g x) (?g y) = dist x y"
1.1185 +      by blast
1.1186 +  }
1.1187 +  note thd = this
1.1188 +    show ?thesis
1.1189 +    apply (rule exI[where x= ?g])
1.1190 +    unfolding orthogonal_transformation_isometry
1.1191 +    using g0 thfg thd
1.1192 +    apply metis
1.1193 +    done
1.1194 +qed
1.1195 +
1.1196 +text \<open>Rotation, reflection, rotoinversion.\<close>
1.1197 +
1.1198 +definition "rotation_matrix Q \<longleftrightarrow> orthogonal_matrix Q \<and> det Q = 1"
1.1199 +definition "rotoinversion_matrix Q \<longleftrightarrow> orthogonal_matrix Q \<and> det Q = - 1"
1.1200 +
1.1201 +lemma orthogonal_rotation_or_rotoinversion:
1.1202 +  fixes Q :: "'a::linordered_idom^'n^'n"
1.1203 +  shows " orthogonal_matrix Q \<longleftrightarrow> rotation_matrix Q \<or> rotoinversion_matrix Q"
1.1204 +  by (metis rotoinversion_matrix_def rotation_matrix_def det_orthogonal_matrix)
1.1205 +
1.1206 +text \<open>Explicit formulas for low dimensions.\<close>
1.1207 +
1.1208 +lemma setprod_neutral_const: "setprod f {(1::nat)..1} = f 1"
1.1209 +  by simp
1.1210 +
1.1211 +lemma setprod_2: "setprod f {(1::nat)..2} = f 1 * f 2"
1.1212 +  by (simp add: eval_nat_numeral atLeastAtMostSuc_conv mult.commute)
1.1213 +
1.1214 +lemma setprod_3: "setprod f {(1::nat)..3} = f 1 * f 2 * f 3"
1.1215 +  by (simp add: eval_nat_numeral atLeastAtMostSuc_conv mult.commute)
1.1216 +
1.1217 +lemma det_1: "det (A::'a::comm_ring_1^1^1) = A\$1\$1"
1.1218 +  by (simp add: det_def of_nat_Suc sign_id)
1.1219 +
1.1220 +lemma det_2: "det (A::'a::comm_ring_1^2^2) = A\$1\$1 * A\$2\$2 - A\$1\$2 * A\$2\$1"
1.1221 +proof -
1.1222 +  have f12: "finite {2::2}" "1 \<notin> {2::2}" by auto
1.1223 +  show ?thesis
1.1224 +    unfolding det_def UNIV_2
1.1225 +    unfolding setsum_over_permutations_insert[OF f12]
1.1226 +    unfolding permutes_sing
1.1227 +    by (simp add: sign_swap_id sign_id swap_id_eq)
1.1228 +qed
1.1229 +
1.1230 +lemma det_3:
1.1231 +  "det (A::'a::comm_ring_1^3^3) =
1.1232 +    A\$1\$1 * A\$2\$2 * A\$3\$3 +
1.1233 +    A\$1\$2 * A\$2\$3 * A\$3\$1 +
1.1234 +    A\$1\$3 * A\$2\$1 * A\$3\$2 -
1.1235 +    A\$1\$1 * A\$2\$3 * A\$3\$2 -
1.1236 +    A\$1\$2 * A\$2\$1 * A\$3\$3 -
1.1237 +    A\$1\$3 * A\$2\$2 * A\$3\$1"
1.1238 +proof -
1.1239 +  have f123: "finite {2::3, 3}" "1 \<notin> {2::3, 3}"
1.1240 +    by auto
1.1241 +  have f23: "finite {3::3}" "2 \<notin> {3::3}"
1.1242 +    by auto
1.1243 +
1.1244 +  show ?thesis
1.1245 +    unfolding det_def UNIV_3
1.1246 +    unfolding setsum_over_permutations_insert[OF f123]
1.1247 +    unfolding setsum_over_permutations_insert[OF f23]
1.1248 +    unfolding permutes_sing
1.1249 +    by (simp add: sign_swap_id permutation_swap_id sign_compose sign_id swap_id_eq)
1.1250 +qed
1.1251 +
1.1252 +end
```