author  paulson <lp15@cam.ac.uk> 
Wed, 09 May 2018 22:11:02 +0100  
changeset 68134  cfe796bf59da 
parent 68074  8d50467f7555 
child 68138  c738f40e88d4 
permissions  rwrr 
63627  1 
(* Title: HOL/Analysis/Determinants.thy 
41959  2 
Author: Amine Chaieb, University of Cambridge 
33175  3 
*) 
4 

60420  5 
section \<open>Traces, Determinant of square matrices and some properties\<close> 
33175  6 

7 
theory Determinants 

44228
5f974bead436
get Multivariate_Analysis/Determinants.thy compiled and working again
huffman
parents:
41959
diff
changeset

8 
imports 
5f974bead436
get Multivariate_Analysis/Determinants.thy compiled and working again
huffman
parents:
41959
diff
changeset

9 
Cartesian_Euclidean_Space 
66453
cc19f7ca2ed6
sessionqualified theory imports: isabelle imports U i d '~~/src/Benchmarks' a;
wenzelm
parents:
64272
diff
changeset

10 
"HOLLibrary.Permutations" 
33175  11 
begin 
12 

60420  13 
subsection \<open>Trace\<close> 
33175  14 

53253  15 
definition trace :: "'a::semiring_1^'n^'n \<Rightarrow> 'a" 
64267  16 
where "trace A = sum (\<lambda>i. ((A$i)$i)) (UNIV::'n set)" 
33175  17 

53854  18 
lemma trace_0: "trace (mat 0) = 0" 
33175  19 
by (simp add: trace_def mat_def) 
20 

53854  21 
lemma trace_I: "trace (mat 1 :: 'a::semiring_1^'n^'n) = of_nat(CARD('n))" 
33175  22 
by (simp add: trace_def mat_def) 
23 

34291
4e896680897e
finite annotation on cartesian product is now implicit.
hoelzl
parents:
34289
diff
changeset

24 
lemma trace_add: "trace ((A::'a::comm_semiring_1^'n^'n) + B) = trace A + trace B" 
64267  25 
by (simp add: trace_def sum.distrib) 
33175  26 

34291
4e896680897e
finite annotation on cartesian product is now implicit.
hoelzl
parents:
34289
diff
changeset

27 
lemma trace_sub: "trace ((A::'a::comm_ring_1^'n^'n)  B) = trace A  trace B" 
64267  28 
by (simp add: trace_def sum_subtractf) 
33175  29 

53854  30 
lemma trace_mul_sym: "trace ((A::'a::comm_semiring_1^'n^'m) ** B) = trace (B**A)" 
33175  31 
apply (simp add: trace_def matrix_matrix_mult_def) 
66804
3f9bb52082c4
avoid name clashes on interpretation of abstract locales
haftmann
parents:
66453
diff
changeset

32 
apply (subst sum.swap) 
57512
cc97b347b301
reduced name variants for assoc and commute on plus and mult
haftmann
parents:
57418
diff
changeset

33 
apply (simp add: mult.commute) 
53253  34 
done 
33175  35 

68134  36 
subsubsection \<open>Definition of determinant\<close> 
33175  37 

34291
4e896680897e
finite annotation on cartesian product is now implicit.
hoelzl
parents:
34289
diff
changeset

38 
definition det:: "'a::comm_ring_1^'n^'n \<Rightarrow> 'a" where 
53253  39 
"det A = 
64272  40 
sum (\<lambda>p. of_int (sign p) * prod (\<lambda>i. A$i$p i) (UNIV :: 'n set)) 
53253  41 
{p. p permutes (UNIV :: 'n set)}" 
33175  42 

68134  43 
text \<open>Basic determinant properties\<close> 
33175  44 

67673
c8caefb20564
lots of new material, ultimately related to measure theory
paulson <lp15@cam.ac.uk>
parents:
67399
diff
changeset

45 
lemma det_transpose [simp]: "det (transpose A) = det (A::'a::comm_ring_1 ^'n^'n)" 
53253  46 
proof  
33175  47 
let ?di = "\<lambda>A i j. A$i$j" 
48 
let ?U = "(UNIV :: 'n set)" 

49 
have fU: "finite ?U" by simp 

53253  50 
{ 
51 
fix p 

52 
assume p: "p \<in> {p. p permutes ?U}" 

53854  53 
from p have pU: "p permutes ?U" 
54 
by blast 

33175  55 
have sth: "sign (inv p) = sign p" 
44260
7784fa3232ce
Determinants.thy: avoid using mem_def/Collect_def
huffman
parents:
44228
diff
changeset

56 
by (metis sign_inverse fU p mem_Collect_eq permutation_permutes) 
33175  57 
from permutes_inj[OF pU] 
53854  58 
have pi: "inj_on p ?U" 
59 
by (blast intro: subset_inj_on) 

33175  60 
from permutes_image[OF pU] 
64272  61 
have "prod (\<lambda>i. ?di (transpose A) i (inv p i)) ?U = 
62 
prod (\<lambda>i. ?di (transpose A) i (inv p i)) (p ` ?U)" 

53854  63 
by simp 
64272  64 
also have "\<dots> = prod ((\<lambda>i. ?di (transpose A) i (inv p i)) \<circ> p) ?U" 
65 
unfolding prod.reindex[OF pi] .. 

66 
also have "\<dots> = prod (\<lambda>i. ?di A i (p i)) ?U" 

53253  67 
proof  
68134  68 
have "((\<lambda>i. ?di (transpose A) i (inv p i)) \<circ> p) i = ?di A i (p i)" if "i \<in> ?U" for i 
69 
using that permutes_inv_o[OF pU] permutes_in_image[OF pU] 

70 
unfolding transpose_def by (simp add: fun_eq_iff) 

71 
then show "prod ((\<lambda>i. ?di (transpose A) i (inv p i)) \<circ> p) ?U = prod (\<lambda>i. ?di A i (p i)) ?U" 

64272  72 
by (auto intro: prod.cong) 
33175  73 
qed 
64272  74 
finally have "of_int (sign (inv p)) * (prod (\<lambda>i. ?di (transpose A) i (inv p i)) ?U) = 
75 
of_int (sign p) * (prod (\<lambda>i. ?di A i (p i)) ?U)" 

53854  76 
using sth by simp 
53253  77 
} 
78 
then show ?thesis 

79 
unfolding det_def 

68134  80 
by (subst sum_permutations_inverse) (blast intro: sum.cong elim: ) 
33175  81 
qed 
82 

83 
lemma det_lowerdiagonal: 

34291
4e896680897e
finite annotation on cartesian product is now implicit.
hoelzl
parents:
34289
diff
changeset

84 
fixes A :: "'a::comm_ring_1^('n::{finite,wellorder})^('n::{finite,wellorder})" 
33175  85 
assumes ld: "\<And>i j. i < j \<Longrightarrow> A$i$j = 0" 
64272  86 
shows "det A = prod (\<lambda>i. A$i$i) (UNIV:: 'n set)" 
53253  87 
proof  
33175  88 
let ?U = "UNIV:: 'n set" 
89 
let ?PU = "{p. p permutes ?U}" 

64272  90 
let ?pp = "\<lambda>p. of_int (sign p) * prod (\<lambda>i. A$i$p i) (UNIV :: 'n set)" 
53854  91 
have fU: "finite ?U" 
92 
by simp 

93 
have id0: "{id} \<subseteq> ?PU" 

94 
by (auto simp add: permutes_id) 

68134  95 
have p0: "\<forall>p \<in> ?PU  {id}. ?pp p = 0" 
96 
proof 

53253  97 
fix p 
68134  98 
assume "p \<in> ?PU  {id}" 
99 
then obtain i where i: "p i > i" 

100 
by clarify (meson leI permutes_natset_le) 

101 
from ld[OF i] have "\<exists>i \<in> ?U. A$i$p i = 0" 

53253  102 
by blast 
68134  103 
with prod_zero[OF fU] show "?pp p = 0" 
104 
by force 

105 
qed 

106 
from sum.mono_neutral_cong_left[OF finite_permutations[OF fU] id0 p0] show ?thesis 

33175  107 
unfolding det_def by (simp add: sign_id) 
108 
qed 

109 

110 
lemma det_upperdiagonal: 

34291
4e896680897e
finite annotation on cartesian product is now implicit.
hoelzl
parents:
34289
diff
changeset

111 
fixes A :: "'a::comm_ring_1^'n::{finite,wellorder}^'n::{finite,wellorder}" 
33175  112 
assumes ld: "\<And>i j. i > j \<Longrightarrow> A$i$j = 0" 
64272  113 
shows "det A = prod (\<lambda>i. A$i$i) (UNIV:: 'n set)" 
53253  114 
proof  
33175  115 
let ?U = "UNIV:: 'n set" 
116 
let ?PU = "{p. p permutes ?U}" 

64272  117 
let ?pp = "(\<lambda>p. of_int (sign p) * prod (\<lambda>i. A$i$p i) (UNIV :: 'n set))" 
53854  118 
have fU: "finite ?U" 
119 
by simp 

120 
have id0: "{id} \<subseteq> ?PU" 

121 
by (auto simp add: permutes_id) 

68134  122 
have p0: "\<forall>p \<in> ?PU {id}. ?pp p = 0" 
123 
proof 

53253  124 
fix p 
53854  125 
assume p: "p \<in> ?PU  {id}" 
68134  126 
then obtain i where i: "p i < i" 
127 
by clarify (meson leI permutes_natset_ge) 

128 
from ld[OF i] have "\<exists>i \<in> ?U. A$i$p i = 0" 

53854  129 
by blast 
68134  130 
with prod_zero[OF fU] show "?pp p = 0" 
131 
by force 

132 
qed 

133 
from sum.mono_neutral_cong_left[OF finite_permutations[OF fU] id0 p0] show ?thesis 

33175  134 
unfolding det_def by (simp add: sign_id) 
135 
qed 

136 

137 
lemma det_diagonal: 

34291
4e896680897e
finite annotation on cartesian product is now implicit.
hoelzl
parents:
34289
diff
changeset

138 
fixes A :: "'a::comm_ring_1^'n^'n" 
33175  139 
assumes ld: "\<And>i j. i \<noteq> j \<Longrightarrow> A$i$j = 0" 
64272  140 
shows "det A = prod (\<lambda>i. A$i$i) (UNIV::'n set)" 
53253  141 
proof  
33175  142 
let ?U = "UNIV:: 'n set" 
143 
let ?PU = "{p. p permutes ?U}" 

64272  144 
let ?pp = "\<lambda>p. of_int (sign p) * prod (\<lambda>i. A$i$p i) (UNIV :: 'n set)" 
33175  145 
have fU: "finite ?U" by simp 
146 
from finite_permutations[OF fU] have fPU: "finite ?PU" . 

53854  147 
have id0: "{id} \<subseteq> ?PU" 
148 
by (auto simp add: permutes_id) 

68134  149 
have p0: "\<forall>p \<in> ?PU  {id}. ?pp p = 0" 
150 
proof 

53253  151 
fix p 
152 
assume p: "p \<in> ?PU  {id}" 

53854  153 
then obtain i where i: "p i \<noteq> i" 
68134  154 
by fastforce 
155 
with ld have "\<exists>i \<in> ?U. A$i$p i = 0" 

156 
by (metis UNIV_I) 

157 
with prod_zero [OF fU] show "?pp p = 0" 

158 
by force 

159 
qed 

64267  160 
from sum.mono_neutral_cong_left[OF fPU id0 p0] show ?thesis 
33175  161 
unfolding det_def by (simp add: sign_id) 
162 
qed 

163 

67673
c8caefb20564
lots of new material, ultimately related to measure theory
paulson <lp15@cam.ac.uk>
parents:
67399
diff
changeset

164 
lemma det_I [simp]: "det (mat 1 :: 'a::comm_ring_1^'n^'n) = 1" 
c8caefb20564
lots of new material, ultimately related to measure theory
paulson <lp15@cam.ac.uk>
parents:
67399
diff
changeset

165 
by (simp add: det_diagonal mat_def) 
33175  166 

67673
c8caefb20564
lots of new material, ultimately related to measure theory
paulson <lp15@cam.ac.uk>
parents:
67399
diff
changeset

167 
lemma det_0 [simp]: "det (mat 0 :: 'a::comm_ring_1^'n^'n) = 0" 
67970  168 
by (simp add: det_def prod_zero power_0_left) 
33175  169 

170 
lemma det_permute_rows: 

34291
4e896680897e
finite annotation on cartesian product is now implicit.
hoelzl
parents:
34289
diff
changeset

171 
fixes A :: "'a::comm_ring_1^'n^'n" 
33175  172 
assumes p: "p permutes (UNIV :: 'n::finite set)" 
53854  173 
shows "det (\<chi> i. A$p i :: 'a^'n^'n) = of_int (sign p) * det A" 
68134  174 
proof  
33175  175 
let ?U = "UNIV :: 'n set" 
176 
let ?PU = "{p. p permutes ?U}" 

68134  177 
have *: "(\<Sum>q\<in>?PU. of_int (sign (q \<circ> p)) * (\<Prod>i\<in>?U. A $ p i $ (q \<circ> p) i)) = 
178 
(\<Sum>n\<in>?PU. of_int (sign p) * of_int (sign n) * (\<Prod>i\<in>?U. A $ i $ n i))" 

179 
proof (rule sum.cong) 

180 
fix q 

181 
assume qPU: "q \<in> ?PU" 

182 
have fU: "finite ?U" 

183 
by simp 

184 
from qPU have q: "q permutes ?U" 

185 
by blast 

186 
have "prod (\<lambda>i. A$p i$ (q \<circ> p) i) ?U = prod ((\<lambda>i. A$p i$(q \<circ> p) i) \<circ> inv p) ?U" 

187 
by (simp only: prod.permute[OF permutes_inv[OF p], symmetric]) 

188 
also have "\<dots> = prod (\<lambda>i. A $ (p \<circ> inv p) i $ (q \<circ> (p \<circ> inv p)) i) ?U" 

189 
by (simp only: o_def) 

190 
also have "\<dots> = prod (\<lambda>i. A$i$q i) ?U" 

191 
by (simp only: o_def permutes_inverses[OF p]) 

192 
finally have thp: "prod (\<lambda>i. A$p i$ (q \<circ> p) i) ?U = prod (\<lambda>i. A$i$q i) ?U" 

193 
by blast 

194 
from p q have pp: "permutation p" and qp: "permutation q" 

195 
by (metis fU permutation_permutes)+ 

196 
show "of_int (sign (q \<circ> p)) * prod (\<lambda>i. A$ p i$ (q \<circ> p) i) ?U = 

197 
of_int (sign p) * of_int (sign q) * prod (\<lambda>i. A$i$q i) ?U" 

198 
by (simp only: thp sign_compose[OF qp pp] mult.commute of_int_mult) 

199 
qed auto 

200 
show ?thesis 

201 
apply (simp add: det_def sum_distrib_left mult.assoc[symmetric]) 

202 
apply (subst sum_permutations_compose_right[OF p]) 

203 
apply (rule *) 

204 
done 

205 
qed 

33175  206 

207 
lemma det_permute_columns: 

34291
4e896680897e
finite annotation on cartesian product is now implicit.
hoelzl
parents:
34289
diff
changeset

208 
fixes A :: "'a::comm_ring_1^'n^'n" 
33175  209 
assumes p: "p permutes (UNIV :: 'n set)" 
210 
shows "det(\<chi> i j. A$i$ p j :: 'a^'n^'n) = of_int (sign p) * det A" 

53253  211 
proof  
33175  212 
let ?Ap = "\<chi> i j. A$i$ p j :: 'a^'n^'n" 
35150
082fa4bd403d
Rename transp to transpose in HOLMultivariate_Analysis. (by himmelma)
hoelzl
parents:
35028
diff
changeset

213 
let ?At = "transpose A" 
082fa4bd403d
Rename transp to transpose in HOLMultivariate_Analysis. (by himmelma)
hoelzl
parents:
35028
diff
changeset

214 
have "of_int (sign p) * det A = det (transpose (\<chi> i. transpose A $ p i))" 
082fa4bd403d
Rename transp to transpose in HOLMultivariate_Analysis. (by himmelma)
hoelzl
parents:
35028
diff
changeset

215 
unfolding det_permute_rows[OF p, of ?At] det_transpose .. 
33175  216 
moreover 
35150
082fa4bd403d
Rename transp to transpose in HOLMultivariate_Analysis. (by himmelma)
hoelzl
parents:
35028
diff
changeset

217 
have "?Ap = transpose (\<chi> i. transpose A $ p i)" 
44228
5f974bead436
get Multivariate_Analysis/Determinants.thy compiled and working again
huffman
parents:
41959
diff
changeset

218 
by (simp add: transpose_def vec_eq_iff) 
53854  219 
ultimately show ?thesis 
220 
by simp 

33175  221 
qed 
222 

68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

223 
lemma det_identical_columns: 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

224 
fixes A :: "'a::comm_ring_1^'n^'n" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

225 
assumes jk: "j \<noteq> k" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

226 
and r: "column j A = column k A" 
33175  227 
shows "det A = 0" 
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

228 
proof  
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

229 
let ?U="UNIV::'n set" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

230 
let ?t_jk="Fun.swap j k id" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

231 
let ?PU="{p. p permutes ?U}" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

232 
let ?S1="{p. p\<in>?PU \<and> evenperm p}" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

233 
let ?S2="{(?t_jk \<circ> p) p. p \<in>?S1}" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

234 
let ?f="\<lambda>p. of_int (sign p) * (\<Prod>i\<in>UNIV. A $ i $ p i)" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

235 
let ?g="\<lambda>p. ?t_jk \<circ> p" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

236 
have g_S1: "?S2 = ?g` ?S1" by auto 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

237 
have inj_g: "inj_on ?g ?S1" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

238 
proof (unfold inj_on_def, auto) 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

239 
fix x y assume x: "x permutes ?U" and even_x: "evenperm x" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

240 
and y: "y permutes ?U" and even_y: "evenperm y" and eq: "?t_jk \<circ> x = ?t_jk \<circ> y" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

241 
show "x = y" by (metis (hide_lams, no_types) comp_assoc eq id_comp swap_id_idempotent) 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

242 
qed 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

243 
have tjk_permutes: "?t_jk permutes ?U" unfolding permutes_def swap_id_eq by (auto,metis) 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

244 
have tjk_eq: "\<forall>i l. A $ i $ ?t_jk l = A $ i $ l" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

245 
using r jk 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

246 
unfolding column_def vec_eq_iff swap_id_eq by fastforce 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

247 
have sign_tjk: "sign ?t_jk = 1" using sign_swap_id[of j k] jk by auto 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

248 
{fix x 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

249 
assume x: "x\<in> ?S1" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

250 
have "sign (?t_jk \<circ> x) = sign (?t_jk) * sign x" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

251 
by (metis (lifting) finite_class.finite_UNIV mem_Collect_eq 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

252 
permutation_permutes permutation_swap_id sign_compose x) 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

253 
also have "... =  sign x" using sign_tjk by simp 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

254 
also have "... \<noteq> sign x" unfolding sign_def by simp 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

255 
finally have "sign (?t_jk \<circ> x) \<noteq> sign x" and "(?t_jk \<circ> x) \<in> ?S2" 
68134  256 
using x by force+ 
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

257 
} 
68134  258 
hence disjoint: "?S1 \<inter> ?S2 = {}" 
259 
by (force simp: sign_def) 

68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

260 
have PU_decomposition: "?PU = ?S1 \<union> ?S2" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

261 
proof (auto) 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

262 
fix x 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

263 
assume x: "x permutes ?U" and "\<forall>p. p permutes ?U \<longrightarrow> x = Fun.swap j k id \<circ> p \<longrightarrow> \<not> evenperm p" 
68134  264 
then obtain p where p: "p permutes UNIV" and x_eq: "x = Fun.swap j k id \<circ> p" 
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

265 
and odd_p: "\<not> evenperm p" 
68134  266 
by (metis (mono_tags) id_o o_assoc permutes_compose swap_id_idempotent tjk_permutes) 
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

267 
thus "evenperm x" 
68134  268 
by (meson evenperm_comp evenperm_swap finite_class.finite_UNIV 
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

269 
jk permutation_permutes permutation_swap_id) 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

270 
next 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

271 
fix p assume p: "p permutes ?U" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

272 
show "Fun.swap j k id \<circ> p permutes UNIV" by (metis p permutes_compose tjk_permutes) 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

273 
qed 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

274 
have "sum ?f ?S2 = sum ((\<lambda>p. of_int (sign p) * (\<Prod>i\<in>UNIV. A $ i $ p i)) 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

275 
\<circ> (\<circ>) (Fun.swap j k id)) {p \<in> {p. p permutes UNIV}. evenperm p}" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

276 
unfolding g_S1 by (rule sum.reindex[OF inj_g]) 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

277 
also have "... = sum (\<lambda>p. of_int (sign (?t_jk \<circ> p)) * (\<Prod>i\<in>UNIV. A $ i $ p i)) ?S1" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

278 
unfolding o_def by (rule sum.cong, auto simp add: tjk_eq) 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

279 
also have "... = sum (\<lambda>p.  ?f p) ?S1" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

280 
proof (rule sum.cong, auto) 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

281 
fix x assume x: "x permutes ?U" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

282 
and even_x: "evenperm x" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

283 
hence perm_x: "permutation x" and perm_tjk: "permutation ?t_jk" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

284 
using permutation_permutes[of x] permutation_permutes[of ?t_jk] permutation_swap_id 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

285 
by (metis finite_code)+ 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

286 
have "(sign (?t_jk \<circ> x)) =  (sign x)" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

287 
unfolding sign_compose[OF perm_tjk perm_x] sign_tjk by auto 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

288 
thus "of_int (sign (?t_jk \<circ> x)) * (\<Prod>i\<in>UNIV. A $ i $ x i) 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

289 
=  (of_int (sign x) * (\<Prod>i\<in>UNIV. A $ i $ x i))" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

290 
by auto 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

291 
qed 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

292 
also have "...=  sum ?f ?S1" unfolding sum_negf .. 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

293 
finally have *: "sum ?f ?S2 =  sum ?f ?S1" . 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

294 
have "det A = (\<Sum>p  p permutes UNIV. of_int (sign p) * (\<Prod>i\<in>UNIV. A $ i $ p i))" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

295 
unfolding det_def .. 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

296 
also have "...= sum ?f ?S1 + sum ?f ?S2" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

297 
by (subst PU_decomposition, rule sum.union_disjoint[OF _ _ disjoint], auto) 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

298 
also have "...= sum ?f ?S1  sum ?f ?S1 " unfolding * by auto 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

299 
also have "...= 0" by simp 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

300 
finally show "det A = 0" by simp 
33175  301 
qed 
302 

68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

303 
lemma det_identical_rows: 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

304 
fixes A :: "'a::comm_ring_1^'n^'n" 
68134  305 
assumes ij: "i \<noteq> j" and r: "row i A = row j A" 
33175  306 
shows "det A = 0" 
68134  307 
by (metis column_transpose det_identical_columns det_transpose ij r) 
33175  308 

309 
lemma det_zero_row: 

68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

310 
fixes A :: "'a::{idom, ring_char_0}^'n^'n" and F :: "'b::{field}^'m^'m" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

311 
shows "row i A = 0 \<Longrightarrow> det A = 0" and "row j F = 0 \<Longrightarrow> det F = 0" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

312 
by (force simp add: row_def det_def vec_eq_iff sign_nz intro!: sum.neutral)+ 
33175  313 

314 
lemma det_zero_column: 

68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

315 
fixes A :: "'a::{idom, ring_char_0}^'n^'n" and F :: "'b::{field}^'m^'m" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

316 
shows "column i A = 0 \<Longrightarrow> det A = 0" and "column j F = 0 \<Longrightarrow> det F = 0" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

317 
unfolding atomize_conj atomize_imp 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

318 
by (metis det_transpose det_zero_row row_transpose) 
33175  319 

320 
lemma det_row_add: 

321 
fixes a b c :: "'n::finite \<Rightarrow> _ ^ 'n" 

322 
shows "det((\<chi> i. if i = k then a i + b i else c i)::'a::comm_ring_1^'n^'n) = 

53253  323 
det((\<chi> i. if i = k then a i else c i)::'a::comm_ring_1^'n^'n) + 
324 
det((\<chi> i. if i = k then b i else c i)::'a::comm_ring_1^'n^'n)" 

64267  325 
unfolding det_def vec_lambda_beta sum.distrib[symmetric] 
326 
proof (rule sum.cong) 

33175  327 
let ?U = "UNIV :: 'n set" 
328 
let ?pU = "{p. p permutes ?U}" 

329 
let ?f = "(\<lambda>i. if i = k then a i + b i else c i)::'n \<Rightarrow> 'a::comm_ring_1^'n" 

330 
let ?g = "(\<lambda> i. if i = k then a i else c i)::'n \<Rightarrow> 'a::comm_ring_1^'n" 

331 
let ?h = "(\<lambda> i. if i = k then b i else c i)::'n \<Rightarrow> 'a::comm_ring_1^'n" 

53253  332 
fix p 
333 
assume p: "p \<in> ?pU" 

33175  334 
let ?Uk = "?U  {k}" 
53854  335 
from p have pU: "p permutes ?U" 
336 
by blast 

337 
have kU: "?U = insert k ?Uk" 

338 
by blast 

68134  339 
have eq: "prod (\<lambda>i. ?f i $ p i) ?Uk = prod (\<lambda>i. ?g i $ p i) ?Uk" 
340 
"prod (\<lambda>i. ?f i $ p i) ?Uk = prod (\<lambda>i. ?h i $ p i) ?Uk" 

341 
by auto 

342 
have Uk: "finite ?Uk" "k \<notin> ?Uk" 

53854  343 
by auto 
64272  344 
have "prod (\<lambda>i. ?f i $ p i) ?U = prod (\<lambda>i. ?f i $ p i) (insert k ?Uk)" 
33175  345 
unfolding kU[symmetric] .. 
64272  346 
also have "\<dots> = ?f k $ p k * prod (\<lambda>i. ?f i $ p i) ?Uk" 
68134  347 
by (rule prod.insert) auto 
64272  348 
also have "\<dots> = (a k $ p k * prod (\<lambda>i. ?f i $ p i) ?Uk) + (b k$ p k * prod (\<lambda>i. ?f i $ p i) ?Uk)" 
53253  349 
by (simp add: field_simps) 
64272  350 
also have "\<dots> = (a k $ p k * prod (\<lambda>i. ?g i $ p i) ?Uk) + (b k$ p k * prod (\<lambda>i. ?h i $ p i) ?Uk)" 
68134  351 
by (metis eq) 
64272  352 
also have "\<dots> = prod (\<lambda>i. ?g i $ p i) (insert k ?Uk) + prod (\<lambda>i. ?h i $ p i) (insert k ?Uk)" 
68134  353 
unfolding prod.insert[OF Uk] by simp 
64272  354 
finally have "prod (\<lambda>i. ?f i $ p i) ?U = prod (\<lambda>i. ?g i $ p i) ?U + prod (\<lambda>i. ?h i $ p i) ?U" 
53854  355 
unfolding kU[symmetric] . 
64272  356 
then show "of_int (sign p) * prod (\<lambda>i. ?f i $ p i) ?U = 
357 
of_int (sign p) * prod (\<lambda>i. ?g i $ p i) ?U + of_int (sign p) * prod (\<lambda>i. ?h i $ p i) ?U" 

36350  358 
by (simp add: field_simps) 
68134  359 
qed auto 
33175  360 

361 
lemma det_row_mul: 

362 
fixes a b :: "'n::finite \<Rightarrow> _ ^ 'n" 

363 
shows "det((\<chi> i. if i = k then c *s a i else b i)::'a::comm_ring_1^'n^'n) = 

53253  364 
c * det((\<chi> i. if i = k then a i else b i)::'a::comm_ring_1^'n^'n)" 
64267  365 
unfolding det_def vec_lambda_beta sum_distrib_left 
366 
proof (rule sum.cong) 

33175  367 
let ?U = "UNIV :: 'n set" 
368 
let ?pU = "{p. p permutes ?U}" 

369 
let ?f = "(\<lambda>i. if i = k then c*s a i else b i)::'n \<Rightarrow> 'a::comm_ring_1^'n" 

370 
let ?g = "(\<lambda> i. if i = k then a i else b i)::'n \<Rightarrow> 'a::comm_ring_1^'n" 

53253  371 
fix p 
372 
assume p: "p \<in> ?pU" 

33175  373 
let ?Uk = "?U  {k}" 
53854  374 
from p have pU: "p permutes ?U" 
375 
by blast 

376 
have kU: "?U = insert k ?Uk" 

377 
by blast 

68134  378 
have eq: "prod (\<lambda>i. ?f i $ p i) ?Uk = prod (\<lambda>i. ?g i $ p i) ?Uk" 
379 
by (auto simp: ) 

380 
have Uk: "finite ?Uk" "k \<notin> ?Uk" 

53854  381 
by auto 
64272  382 
have "prod (\<lambda>i. ?f i $ p i) ?U = prod (\<lambda>i. ?f i $ p i) (insert k ?Uk)" 
33175  383 
unfolding kU[symmetric] .. 
64272  384 
also have "\<dots> = ?f k $ p k * prod (\<lambda>i. ?f i $ p i) ?Uk" 
68134  385 
by (rule prod.insert) auto 
64272  386 
also have "\<dots> = (c*s a k) $ p k * prod (\<lambda>i. ?f i $ p i) ?Uk" 
53253  387 
by (simp add: field_simps) 
64272  388 
also have "\<dots> = c* (a k $ p k * prod (\<lambda>i. ?g i $ p i) ?Uk)" 
68134  389 
unfolding eq by (simp add: ac_simps) 
64272  390 
also have "\<dots> = c* (prod (\<lambda>i. ?g i $ p i) (insert k ?Uk))" 
68134  391 
unfolding prod.insert[OF Uk] by simp 
64272  392 
finally have "prod (\<lambda>i. ?f i $ p i) ?U = c* (prod (\<lambda>i. ?g i $ p i) ?U)" 
53253  393 
unfolding kU[symmetric] . 
68134  394 
then show "of_int (sign p) * prod (\<lambda>i. ?f i $ p i) ?U = c * (of_int (sign p) * prod (\<lambda>i. ?g i $ p i) ?U)" 
36350  395 
by (simp add: field_simps) 
68134  396 
qed auto 
33175  397 

398 
lemma det_row_0: 

399 
fixes b :: "'n::finite \<Rightarrow> _ ^ 'n" 

400 
shows "det((\<chi> i. if i = k then 0 else b i)::'a::comm_ring_1^'n^'n) = 0" 

53253  401 
using det_row_mul[of k 0 "\<lambda>i. 1" b] 
402 
apply simp 

403 
apply (simp only: vector_smult_lzero) 

404 
done 

33175  405 

406 
lemma det_row_operation: 

68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

407 
fixes A :: "'a::{comm_ring_1}^'n^'n" 
33175  408 
assumes ij: "i \<noteq> j" 
409 
shows "det (\<chi> k. if k = i then row i A + c *s row j A else row k A) = det A" 

53253  410 
proof  
33175  411 
let ?Z = "(\<chi> k. if k = i then row j A else row k A) :: 'a ^'n^'n" 
412 
have th: "row i ?Z = row j ?Z" by (vector row_def) 

413 
have th2: "((\<chi> k. if k = i then row i A else row k A) :: 'a^'n^'n) = A" 

414 
by (vector row_def) 

415 
show ?thesis 

416 
unfolding det_row_add [of i] det_row_mul[of i] det_identical_rows[OF ij th] th2 

417 
by simp 

418 
qed 

419 

420 
lemma det_row_span: 

68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

421 
fixes A :: "'a::{field}^'n^'n" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

422 
assumes x: "x \<in> vec.span {row j A j. j \<noteq> i}" 
33175  423 
shows "det (\<chi> k. if k = i then row i A + x else row k A) = det A" 
68069
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68050
diff
changeset

424 
using x 
68074  425 
proof (induction rule: vec.span_induct_alt) 
68069
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68050
diff
changeset

426 
case base 
68134  427 
have "(if k = i then row i A + 0 else row k A) = row k A" for k 
428 
by simp 

68069
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68050
diff
changeset

429 
then show ?case 
68134  430 
by (simp add: row_def) 
68069
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68050
diff
changeset

431 
next 
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68050
diff
changeset

432 
case (step c z y) 
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68050
diff
changeset

433 
then obtain j where j: "z = row j A" "i \<noteq> j" 
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68050
diff
changeset

434 
by blast 
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68050
diff
changeset

435 
let ?w = "row i A + y" 
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68050
diff
changeset

436 
have th0: "row i A + (c*s z + y) = ?w + c*s z" 
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68050
diff
changeset

437 
by vector 
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68050
diff
changeset

438 
let ?d = "\<lambda>x. det (\<chi> k. if k = i then x else row k A)" 
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68050
diff
changeset

439 
have thz: "?d z = 0" 
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68050
diff
changeset

440 
apply (rule det_identical_rows[OF j(2)]) 
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68050
diff
changeset

441 
using j 
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68050
diff
changeset

442 
apply (vector row_def) 
33175  443 
done 
68069
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68050
diff
changeset

444 
have "?d (row i A + (c*s z + y)) = ?d (?w + c*s z)" 
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68050
diff
changeset

445 
unfolding th0 .. 
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68050
diff
changeset

446 
then have "?d (row i A + (c*s z + y)) = det A" 
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68050
diff
changeset

447 
unfolding thz step.IH det_row_mul[of i] det_row_add[of i] by simp 
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68050
diff
changeset

448 
then show ?case 
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68050
diff
changeset

449 
unfolding scalar_mult_eq_scaleR . 
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68050
diff
changeset

450 
qed 
33175  451 

67673
c8caefb20564
lots of new material, ultimately related to measure theory
paulson <lp15@cam.ac.uk>
parents:
67399
diff
changeset

452 
lemma matrix_id [simp]: "det (matrix id) = 1" 
c8caefb20564
lots of new material, ultimately related to measure theory
paulson <lp15@cam.ac.uk>
parents:
67399
diff
changeset

453 
by (simp add: matrix_id_mat_1) 
c8caefb20564
lots of new material, ultimately related to measure theory
paulson <lp15@cam.ac.uk>
parents:
67399
diff
changeset

454 

c8caefb20564
lots of new material, ultimately related to measure theory
paulson <lp15@cam.ac.uk>
parents:
67399
diff
changeset

455 
lemma det_matrix_scaleR [simp]: "det (matrix ((( *\<^sub>R) r)) :: real^'n^'n) = r ^ CARD('n::finite)" 
c8caefb20564
lots of new material, ultimately related to measure theory
paulson <lp15@cam.ac.uk>
parents:
67399
diff
changeset

456 
apply (subst det_diagonal) 
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

457 
apply (auto simp: matrix_def mat_def) 
67673
c8caefb20564
lots of new material, ultimately related to measure theory
paulson <lp15@cam.ac.uk>
parents:
67399
diff
changeset

458 
apply (simp add: cart_eq_inner_axis inner_axis_axis) 
c8caefb20564
lots of new material, ultimately related to measure theory
paulson <lp15@cam.ac.uk>
parents:
67399
diff
changeset

459 
done 
c8caefb20564
lots of new material, ultimately related to measure theory
paulson <lp15@cam.ac.uk>
parents:
67399
diff
changeset

460 

60420  461 
text \<open> 
53854  462 
May as well do this, though it's a bit unsatisfactory since it ignores 
463 
exact duplicates by considering the rows/columns as a set. 

60420  464 
\<close> 
33175  465 

466 
lemma det_dependent_rows: 

68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

467 
fixes A:: "'a::{field}^'n^'n" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

468 
assumes d: "vec.dependent (rows A)" 
33175  469 
shows "det A = 0" 
53253  470 
proof  
33175  471 
let ?U = "UNIV :: 'n set" 
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

472 
from d obtain i where i: "row i A \<in> vec.span (rows A  {row i A})" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

473 
unfolding vec.dependent_def rows_def by blast 
68134  474 
show ?thesis 
475 
proof (cases "\<forall>i j. i \<noteq> j \<longrightarrow> row i A \<noteq> row j A") 

476 
case True 

477 
with i have "vec.span (rows A  {row i A}) \<subseteq> vec.span {row j A j. j \<noteq> i}" 

478 
by (auto simp add: rows_def intro!: vec.span_mono) 

479 
then have " row i A \<in> vec.span {row j Aj. j \<noteq> i}" 

480 
by (meson i subsetCE vec.span_neg) 

481 
from det_row_span[OF this] 

33175  482 
have "det A = det (\<chi> k. if k = i then 0 *s 1 else row k A)" 
483 
unfolding right_minus vector_smult_lzero .. 

68134  484 
with det_row_mul[of i 0 "\<lambda>i. 1"] 
485 
show ?thesis by simp 

486 
next 

487 
case False 

488 
then obtain j k where jk: "j \<noteq> k" "row j A = row k A" 

489 
by auto 

490 
from det_identical_rows[OF jk] show ?thesis . 

491 
qed 

33175  492 
qed 
493 

53253  494 
lemma det_dependent_columns: 
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

495 
assumes d: "vec.dependent (columns (A::real^'n^'n))" 
53253  496 
shows "det A = 0" 
497 
by (metis d det_dependent_rows rows_transpose det_transpose) 

33175  498 

68134  499 
text \<open>Multilinearity and the multiplication formula\<close> 
33175  500 

44228
5f974bead436
get Multivariate_Analysis/Determinants.thy compiled and working again
huffman
parents:
41959
diff
changeset

501 
lemma Cart_lambda_cong: "(\<And>x. f x = g x) \<Longrightarrow> (vec_lambda f::'a^'n) = (vec_lambda g :: 'a^'n)" 
68134  502 
by auto 
33175  503 

64267  504 
lemma det_linear_row_sum: 
33175  505 
assumes fS: "finite S" 
64267  506 
shows "det ((\<chi> i. if i = k then sum (a i) S else c i)::'a::comm_ring_1^'n^'n) = 
507 
sum (\<lambda>j. det ((\<chi> i. if i = k then a i j else c i)::'a^'n^'n)) S" 

68134  508 
using fS by (induct rule: finite_induct; simp add: det_row_0 det_row_add cong: if_cong) 
33175  509 

510 
lemma finite_bounded_functions: 

511 
assumes fS: "finite S" 

512 
shows "finite {f. (\<forall>i \<in> {1.. (k::nat)}. f i \<in> S) \<and> (\<forall>i. i \<notin> {1 .. k} \<longrightarrow> f i = i)}" 

53253  513 
proof (induct k) 
33175  514 
case 0 
68134  515 
have *: "{f. \<forall>i. f i = i} = {id}" 
53854  516 
by auto 
517 
show ?case 

68134  518 
by (auto simp add: *) 
33175  519 
next 
520 
case (Suc k) 

521 
let ?f = "\<lambda>(y::nat,g) i. if i = Suc k then y else g i" 

522 
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)})" 

523 
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)}" 

524 
apply (auto simp add: image_iff) 

68134  525 
apply (rename_tac f) 
526 
apply (rule_tac x="f (Suc k)" in bexI) 

527 
apply (rule_tac x = "\<lambda>i. if i = Suc k then i else f i" in exI) 

44457
d366fa5551ef
declare euclidean_simps [simp] at the point they are proved;
huffman
parents:
44260
diff
changeset

528 
apply auto 
33175  529 
done 
530 
with finite_imageI[OF finite_cartesian_product[OF fS Suc.hyps(1)], of ?f] 

53854  531 
show ?case 
532 
by metis 

33175  533 
qed 
534 

535 

64267  536 
lemma det_linear_rows_sum_lemma: 
53854  537 
assumes fS: "finite S" 
538 
and fT: "finite T" 

64267  539 
shows "det ((\<chi> i. if i \<in> T then sum (a i) S else c i):: 'a::comm_ring_1^'n^'n) = 
540 
sum (\<lambda>f. det((\<chi> i. if i \<in> T then a i (f i) else c i)::'a^'n^'n)) 

53253  541 
{f. (\<forall>i \<in> T. f i \<in> S) \<and> (\<forall>i. i \<notin> T \<longrightarrow> f i = i)}" 
542 
using fT 

543 
proof (induct T arbitrary: a c set: finite) 

33175  544 
case empty 
53253  545 
have th0: "\<And>x y. (\<chi> i. if i \<in> {} then x i else y i) = (\<chi> i. y i)" 
546 
by vector 

53854  547 
from empty.prems show ?case 
62408
86f27b264d3d
Conformal_mappings: a big development in complex analysis (+ some lemmas)
paulson <lp15@cam.ac.uk>
parents:
61286
diff
changeset

548 
unfolding th0 by (simp add: eq_id_iff) 
33175  549 
next 
550 
case (insert z T a c) 

551 
let ?F = "\<lambda>T. {f. (\<forall>i \<in> T. f i \<in> S) \<and> (\<forall>i. i \<notin> T \<longrightarrow> f i = i)}" 

552 
let ?h = "\<lambda>(y,g) i. if i = z then y else g i" 

553 
let ?k = "\<lambda>h. (h(z),(\<lambda>i. if i = z then i else h i))" 

554 
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)" 

57129
7edb7550663e
introduce more powerful reindexing rules for big operators
hoelzl
parents:
56545
diff
changeset

555 
let ?c = "\<lambda>j i. if i = z then a i j else c i" 
53253  556 
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)" 
557 
by simp 

33175  558 
have thif2: "\<And>a b c d e. (if a then b else if c then d else e) = 
53253  559 
(if c then (if a then b else d) else (if a then b else e))" 
560 
by simp 

68134  561 
from \<open>z \<notin> T\<close> have nz: "\<And>i. i \<in> T \<Longrightarrow> i \<noteq> z" 
53253  562 
by auto 
64267  563 
have "det (\<chi> i. if i \<in> insert z T then sum (a i) S else c i) = 
564 
det (\<chi> i. if i = z then sum (a i) S else if i \<in> T then sum (a i) S else c i)" 

33175  565 
unfolding insert_iff thif .. 
64267  566 
also have "\<dots> = (\<Sum>j\<in>S. det (\<chi> i. if i \<in> T then sum (a i) S else if i = z then a i j else c i))" 
567 
unfolding det_linear_row_sum[OF fS] 

68134  568 
by (subst thif2) (simp add: nz cong: if_cong) 
33175  569 
finally have tha: 
64267  570 
"det (\<chi> i. if i \<in> insert z T then sum (a i) S else c i) = 
33175  571 
(\<Sum>(j, f)\<in>S \<times> ?F T. det (\<chi> i. if i \<in> T then a i (f i) 
572 
else if i = z then a i j 

573 
else c i))" 

64267  574 
unfolding insert.hyps unfolding sum.cartesian_product by blast 
33175  575 
show ?case unfolding tha 
60420  576 
using \<open>z \<notin> T\<close> 
64267  577 
by (intro sum.reindex_bij_witness[where i="?k" and j="?h"]) 
57129
7edb7550663e
introduce more powerful reindexing rules for big operators
hoelzl
parents:
56545
diff
changeset

578 
(auto intro!: cong[OF refl[of det]] simp: vec_eq_iff) 
33175  579 
qed 
580 

64267  581 
lemma det_linear_rows_sum: 
53854  582 
fixes S :: "'n::finite set" 
583 
assumes fS: "finite S" 

64267  584 
shows "det (\<chi> i. sum (a i) S) = 
585 
sum (\<lambda>f. det (\<chi> i. a i (f i) :: 'a::comm_ring_1 ^ 'n^'n)) {f. \<forall>i. f i \<in> S}" 

53253  586 
proof  
587 
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)" 

588 
by vector 

64267  589 
from det_linear_rows_sum_lemma[OF fS, of "UNIV :: 'n set" a, unfolded th0, OF finite] 
53253  590 
show ?thesis by simp 
33175  591 
qed 
592 

64267  593 
lemma matrix_mul_sum_alt: 
34291
4e896680897e
finite annotation on cartesian product is now implicit.
hoelzl
parents:
34289
diff
changeset

594 
fixes A B :: "'a::comm_ring_1^'n^'n" 
64267  595 
shows "A ** B = (\<chi> i. sum (\<lambda>k. A$i$k *s B $ k) (UNIV :: 'n set))" 
596 
by (vector matrix_matrix_mult_def sum_component) 

33175  597 

598 
lemma det_rows_mul: 

34291
4e896680897e
finite annotation on cartesian product is now implicit.
hoelzl
parents:
34289
diff
changeset

599 
"det((\<chi> i. c i *s a i)::'a::comm_ring_1^'n^'n) = 
64272  600 
prod (\<lambda>i. c i) (UNIV:: 'n set) * det((\<chi> i. a i)::'a^'n^'n)" 
601 
proof (simp add: det_def sum_distrib_left cong add: prod.cong, rule sum.cong) 

33175  602 
let ?U = "UNIV :: 'n set" 
603 
let ?PU = "{p. p permutes ?U}" 

53253  604 
fix p 
605 
assume pU: "p \<in> ?PU" 

33175  606 
let ?s = "of_int (sign p)" 
53253  607 
from pU have p: "p permutes ?U" 
608 
by blast 

64272  609 
have "prod (\<lambda>i. c i * a i $ p i) ?U = prod c ?U * prod (\<lambda>i. a i $ p i) ?U" 
610 
unfolding prod.distrib .. 

33175  611 
then show "?s * (\<Prod>xa\<in>?U. c xa * a xa $ p xa) = 
64272  612 
prod c ?U * (?s* (\<Prod>xa\<in>?U. a xa $ p xa))" 
53854  613 
by (simp add: field_simps) 
57418  614 
qed rule 
33175  615 

616 
lemma det_mul: 

68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

617 
fixes A B :: "'a::comm_ring_1^'n^'n" 
33175  618 
shows "det (A ** B) = det A * det B" 
53253  619 
proof  
33175  620 
let ?U = "UNIV :: 'n set" 
68134  621 
let ?F = "{f. (\<forall>i \<in> ?U. f i \<in> ?U) \<and> (\<forall>i. i \<notin> ?U \<longrightarrow> f i = i)}" 
33175  622 
let ?PU = "{p. p permutes ?U}" 
68134  623 
have "p \<in> ?F" if "p permutes ?U" for p 
53854  624 
by simp 
625 
then have PUF: "?PU \<subseteq> ?F" by blast 

53253  626 
{ 
627 
fix f 

628 
assume fPU: "f \<in> ?F  ?PU" 

53854  629 
have fUU: "f ` ?U \<subseteq> ?U" 
630 
using fPU by auto 

53253  631 
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)" 
632 
unfolding permutes_def by auto 

33175  633 

634 
let ?A = "(\<chi> i. A$i$f i *s B$f i) :: 'a^'n^'n" 

635 
let ?B = "(\<chi> i. B$f i) :: 'a^'n^'n" 

53253  636 
{ 
637 
assume fni: "\<not> inj_on f ?U" 

33175  638 
then obtain i j where ij: "f i = f j" "i \<noteq> j" 
639 
unfolding inj_on_def by blast 

68134  640 
then have "row i ?B = row j ?B" 
53854  641 
by (vector row_def) 
68134  642 
with det_identical_rows[OF ij(2)] 
33175  643 
have "det (\<chi> i. A$i$f i *s B$f i) = 0" 
68134  644 
unfolding det_rows_mul by force 
53253  645 
} 
33175  646 
moreover 
53253  647 
{ 
648 
assume fi: "inj_on f ?U" 

33175  649 
from f fi have fith: "\<And>i j. f i = f j \<Longrightarrow> i = j" 
650 
unfolding inj_on_def by metis 

68134  651 
note fs = fi[unfolded surjective_iff_injective_gen[OF finite finite refl fUU, symmetric]] 
652 
have "\<exists>!x. f x = y" for y 

653 
using fith fs by blast 

53854  654 
with f(3) have "det (\<chi> i. A$i$f i *s B$f i) = 0" 
655 
by blast 

53253  656 
} 
53854  657 
ultimately have "det (\<chi> i. A$i$f i *s B$f i) = 0" 
658 
by blast 

53253  659 
} 
53854  660 
then have zth: "\<forall> f\<in> ?F  ?PU. det (\<chi> i. A$i$f i *s B$f i) = 0" 
53253  661 
by simp 
662 
{ 

663 
fix p 

664 
assume pU: "p \<in> ?PU" 

53854  665 
from pU have p: "p permutes ?U" 
666 
by blast 

33175  667 
let ?s = "\<lambda>p. of_int (sign p)" 
53253  668 
let ?f = "\<lambda>q. ?s p * (\<Prod>i\<in> ?U. A $ i $ p i) * (?s q * (\<Prod>i\<in> ?U. B $ i $ q i))" 
64267  669 
have "(sum (\<lambda>q. ?s q * 
53253  670 
(\<Prod>i\<in> ?U. (\<chi> i. A $ i $ p i *s B $ p i :: 'a^'n^'n) $ i $ q i)) ?PU) = 
64267  671 
(sum (\<lambda>q. ?s p * (\<Prod>i\<in> ?U. A $ i $ p i) * (?s q * (\<Prod>i\<in> ?U. B $ i $ q i))) ?PU)" 
33175  672 
unfolding sum_permutations_compose_right[OF permutes_inv[OF p], of ?f] 
64267  673 
proof (rule sum.cong) 
53253  674 
fix q 
675 
assume qU: "q \<in> ?PU" 

53854  676 
then have q: "q permutes ?U" 
677 
by blast 

33175  678 
from p q have pp: "permutation p" and pq: "permutation q" 
679 
unfolding permutation_permutes by auto 

680 
have th00: "of_int (sign p) * of_int (sign p) = (1::'a)" 

681 
"\<And>a. of_int (sign p) * (of_int (sign p) * a) = a" 

57512
cc97b347b301
reduced name variants for assoc and commute on plus and mult
haftmann
parents:
57418
diff
changeset

682 
unfolding mult.assoc[symmetric] 
53854  683 
unfolding of_int_mult[symmetric] 
33175  684 
by (simp_all add: sign_idempotent) 
53854  685 
have ths: "?s q = ?s p * ?s (q \<circ> inv p)" 
33175  686 
using pp pq permutation_inverse[OF pp] sign_inverse[OF pp] 
68134  687 
by (simp add: th00 ac_simps sign_idempotent sign_compose) 
64272  688 
have th001: "prod (\<lambda>i. B$i$ q (inv p i)) ?U = prod ((\<lambda>i. B$i$ q (inv p i)) \<circ> p) ?U" 
68134  689 
by (rule prod.permute[OF p]) 
64272  690 
have thp: "prod (\<lambda>i. (\<chi> i. A$i$p i *s B$p i :: 'a^'n^'n) $i $ q i) ?U = 
691 
prod (\<lambda>i. A$i$p i) ?U * prod (\<lambda>i. B$i$ q (inv p i)) ?U" 

692 
unfolding th001 prod.distrib[symmetric] o_def permutes_inverses[OF p] 

693 
apply (rule prod.cong[OF refl]) 

53253  694 
using permutes_in_image[OF q] 
695 
apply vector 

696 
done 

64272  697 
show "?s q * prod (\<lambda>i. (((\<chi> i. A$i$p i *s B$p i) :: 'a^'n^'n)$i$q i)) ?U = 
698 
?s p * (prod (\<lambda>i. A$i$p i) ?U) * (?s (q \<circ> inv p) * prod (\<lambda>i. B$i$(q \<circ> inv p) i) ?U)" 

33175  699 
using ths thp pp pq permutation_inverse[OF pp] sign_inverse[OF pp] 
36350  700 
by (simp add: sign_nz th00 field_simps sign_idempotent sign_compose) 
57418  701 
qed rule 
33175  702 
} 
64267  703 
then have th2: "sum (\<lambda>f. det (\<chi> i. A$i$f i *s B$f i)) ?PU = det A * det B" 
704 
unfolding det_def sum_product 

705 
by (rule sum.cong [OF refl]) 

706 
have "det (A**B) = sum (\<lambda>f. det (\<chi> i. A $ i $ f i *s B $ f i)) ?F" 

68134  707 
unfolding matrix_mul_sum_alt det_linear_rows_sum[OF finite] 
53854  708 
by simp 
64267  709 
also have "\<dots> = sum (\<lambda>f. det (\<chi> i. A$i$f i *s B$f i)) ?PU" 
68134  710 
using sum.mono_neutral_cong_left[OF finite PUF zth, symmetric] 
33175  711 
unfolding det_rows_mul by auto 
712 
finally show ?thesis unfolding th2 . 

713 
qed 

714 

68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

715 

68134  716 
subsection \<open>Relation to invertibility\<close> 
33175  717 

718 
lemma invertible_det_nz: 

68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

719 
fixes A::"'a::{field}^'n^'n" 
33175  720 
shows "invertible A \<longleftrightarrow> det A \<noteq> 0" 
68134  721 
proof (cases "invertible A") 
722 
case True 

723 
then obtain B :: "'a^'n^'n" where B: "A ** B = mat 1" 

724 
unfolding invertible_right_inverse by blast 

725 
then have "det (A ** B) = det (mat 1 :: 'a^'n^'n)" 

726 
by simp 

727 
then show ?thesis 

728 
by (metis True det_I det_mul mult_zero_left one_neq_zero) 

729 
next 

730 
case False 

731 
let ?U = "UNIV :: 'n set" 

732 
have fU: "finite ?U" 

733 
by simp 

734 
from False obtain c i where c: "sum (\<lambda>i. c i *s row i A) ?U = 0" and iU: "i \<in> ?U" and ci: "c i \<noteq> 0" 

735 
unfolding invertible_right_inverse matrix_right_invertible_independent_rows 

53854  736 
by blast 
68134  737 
have thr0: " row i A = sum (\<lambda>j. (1/ c i) *s (c j *s row j A)) (?U  {i})" 
738 
unfolding sum_cmul using c ci 

739 
by (auto simp add: sum.remove[OF fU iU] eq_vector_fraction_iff add_eq_0_iff) 

740 
have thr: " row i A \<in> vec.span {row j A j. j \<noteq> i}" 

741 
unfolding thr0 by (auto intro: vec.span_base vec.span_scale vec.span_sum) 

742 
let ?B = "(\<chi> k. if k = i then 0 else row k A) :: 'a^'n^'n" 

743 
have thrb: "row i ?B = 0" using iU by (vector row_def) 

744 
have "det A = 0" 

745 
unfolding det_row_span[OF thr, symmetric] right_minus 

746 
unfolding det_zero_row(2)[OF thrb] .. 

747 
then show ?thesis 

748 
by (simp add: False) 

33175  749 
qed 
750 

68134  751 

68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

752 
lemma det_nz_iff_inj_gen: 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

753 
fixes f :: "'a::field^'n \<Rightarrow> 'a::field^'n" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

754 
assumes "Vector_Spaces.linear ( *s) ( *s) f" 
67990  755 
shows "det (matrix f) \<noteq> 0 \<longleftrightarrow> inj f" 
756 
proof 

757 
assume "det (matrix f) \<noteq> 0" 

758 
then show "inj f" 

759 
using assms invertible_det_nz inj_matrix_vector_mult by force 

760 
next 

761 
assume "inj f" 

762 
show "det (matrix f) \<noteq> 0" 

68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

763 
using vec.linear_injective_left_inverse [OF assms \<open>inj f\<close>] 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

764 
by (metis assms invertible_det_nz invertible_left_inverse matrix_compose_gen matrix_id_mat_1) 
67990  765 
qed 
766 

68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

767 
lemma det_nz_iff_inj: 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

768 
fixes f :: "real^'n \<Rightarrow> real^'n" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

769 
assumes "linear f" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

770 
shows "det (matrix f) \<noteq> 0 \<longleftrightarrow> inj f" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

771 
using det_nz_iff_inj_gen[of f] assms 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

772 
unfolding linear_matrix_vector_mul_eq . 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

773 

67990  774 
lemma det_eq_0_rank: 
775 
fixes A :: "real^'n^'n" 

776 
shows "det A = 0 \<longleftrightarrow> rank A < CARD('n)" 

777 
using invertible_det_nz [of A] 

778 
by (auto simp: matrix_left_invertible_injective invertible_left_inverse less_rank_noninjective) 

779 

67981
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

780 
subsubsection\<open>Invertibility of matrices and corresponding linear functions\<close> 
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

781 

68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

782 
lemma matrix_left_invertible_gen: 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

783 
fixes f :: "'a::field^'m \<Rightarrow> 'a::field^'n" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

784 
assumes "Vector_Spaces.linear ( *s) ( *s) f" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

785 
shows "((\<exists>B. B ** matrix f = mat 1) \<longleftrightarrow> (\<exists>g. Vector_Spaces.linear ( *s) ( *s) g \<and> g \<circ> f = id))" 
67981
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

786 
proof safe 
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

787 
fix B 
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

788 
assume 1: "B ** matrix f = mat 1" 
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

789 
show "\<exists>g. Vector_Spaces.linear ( *s) ( *s) g \<and> g \<circ> f = id" 
67981
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

790 
proof (intro exI conjI) 
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

791 
show "Vector_Spaces.linear ( *s) ( *s) (\<lambda>y. B *v y)" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

792 
by (simp add:) 
67981
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

793 
show "(( *v) B) \<circ> f = id" 
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

794 
unfolding o_def 
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

795 
by (metis assms 1 eq_id_iff matrix_vector_mul(1) matrix_vector_mul_assoc matrix_vector_mul_lid) 
67981
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

796 
qed 
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

797 
next 
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

798 
fix g 
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

799 
assume "Vector_Spaces.linear ( *s) ( *s) g" "g \<circ> f = id" 
67981
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

800 
then have "matrix g ** matrix f = mat 1" 
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

801 
by (metis assms matrix_compose_gen matrix_id_mat_1) 
67981
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

802 
then show "\<exists>B. B ** matrix f = mat 1" .. 
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

803 
qed 
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

804 

68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

805 
lemma matrix_left_invertible: 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

806 
"linear f \<Longrightarrow> ((\<exists>B. B ** matrix f = mat 1) \<longleftrightarrow> (\<exists>g. linear g \<and> g \<circ> f = id))" for f::"real^'m \<Rightarrow> real^'n" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

807 
using matrix_left_invertible_gen[of f] 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

808 
by (auto simp: linear_matrix_vector_mul_eq) 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

809 

493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

810 
lemma matrix_right_invertible_gen: 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

811 
fixes f :: "'a::field^'m \<Rightarrow> 'a^'n" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

812 
assumes "Vector_Spaces.linear ( *s) ( *s) f" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

813 
shows "((\<exists>B. matrix f ** B = mat 1) \<longleftrightarrow> (\<exists>g. Vector_Spaces.linear ( *s) ( *s) g \<and> f \<circ> g = id))" 
67981
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

814 
proof safe 
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

815 
fix B 
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

816 
assume 1: "matrix f ** B = mat 1" 
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

817 
show "\<exists>g. Vector_Spaces.linear ( *s) ( *s) g \<and> f \<circ> g = id" 
67981
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

818 
proof (intro exI conjI) 
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

819 
show "Vector_Spaces.linear ( *s) ( *s) (( *v) B)" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

820 
by (simp add: ) 
67981
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

821 
show "f \<circ> ( *v) B = id" 
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

822 
using 1 assms comp_apply eq_id_iff vec.linear_id matrix_id_mat_1 matrix_vector_mul_assoc matrix_works 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

823 
by (metis (no_types, hide_lams)) 
67981
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

824 
qed 
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

825 
next 
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

826 
fix g 
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

827 
assume "Vector_Spaces.linear ( *s) ( *s) g" and "f \<circ> g = id" 
67981
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

828 
then have "matrix f ** matrix g = mat 1" 
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

829 
by (metis assms matrix_compose_gen matrix_id_mat_1) 
67981
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

830 
then show "\<exists>B. matrix f ** B = mat 1" .. 
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

831 
qed 
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

832 

68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

833 
lemma matrix_right_invertible: 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

834 
"linear f \<Longrightarrow> ((\<exists>B. matrix f ** B = mat 1) \<longleftrightarrow> (\<exists>g. linear g \<and> f \<circ> g = id))" for f::"real^'m \<Rightarrow> real^'n" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

835 
using matrix_right_invertible_gen[of f] 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

836 
by (auto simp: linear_matrix_vector_mul_eq) 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

837 

493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

838 
lemma matrix_invertible_gen: 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

839 
fixes f :: "'a::field^'m \<Rightarrow> 'a::field^'n" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

840 
assumes "Vector_Spaces.linear ( *s) ( *s) f" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

841 
shows "invertible (matrix f) \<longleftrightarrow> (\<exists>g. Vector_Spaces.linear ( *s) ( *s) g \<and> f \<circ> g = id \<and> g \<circ> f = id)" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

842 
(is "?lhs = ?rhs") 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

843 
proof 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

844 
assume ?lhs then show ?rhs 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

845 
by (metis assms invertible_def left_right_inverse_eq matrix_left_invertible_gen matrix_right_invertible_gen) 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

846 
next 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

847 
assume ?rhs then show ?lhs 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

848 
by (metis assms invertible_def matrix_compose_gen matrix_id_mat_1) 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

849 
qed 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

850 

67981
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

851 
lemma matrix_invertible: 
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

852 
"linear f \<Longrightarrow> invertible (matrix f) \<longleftrightarrow> (\<exists>g. linear g \<and> f \<circ> g = id \<and> g \<circ> f = id)" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

853 
for f::"real^'m \<Rightarrow> real^'n" 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

854 
using matrix_invertible_gen[of f] 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

855 
by (auto simp: linear_matrix_vector_mul_eq) 
67981
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

856 

349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

857 
lemma invertible_eq_bij: 
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

858 
fixes m :: "'a::field^'m^'n" 
67981
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

859 
shows "invertible m \<longleftrightarrow> bij (( *v) m)" 
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

860 
using matrix_invertible_gen[OF matrix_vector_mul_linear_gen, of m, simplified matrix_of_matrix_vector_mul] 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

861 
by (metis bij_betw_def left_right_inverse_eq matrix_vector_mul_linear_gen o_bij 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

862 
vec.linear_injective_left_inverse vec.linear_surjective_right_inverse) 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

863 

67981
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

864 

68134  865 
subsection \<open>Cramer's rule\<close> 
33175  866 

35150
082fa4bd403d
Rename transp to transpose in HOLMultivariate_Analysis. (by himmelma)
hoelzl
parents:
35028
diff
changeset

867 
lemma cramer_lemma_transpose: 
53854  868 
fixes A:: "real^'n^'n" 
869 
and x :: "real^'n" 

64267  870 
shows "det ((\<chi> i. if i = k then sum (\<lambda>i. x$i *s row i A) (UNIV::'n set) 
53854  871 
else row i A)::real^'n^'n) = x$k * det A" 
33175  872 
(is "?lhs = ?rhs") 
53253  873 
proof  
33175  874 
let ?U = "UNIV :: 'n set" 
875 
let ?Uk = "?U  {k}" 

53854  876 
have U: "?U = insert k ?Uk" 
877 
by blast 

878 
have kUk: "k \<notin> ?Uk" 

879 
by simp 

33175  880 
have th00: "\<And>k s. x$k *s row k A + s = (x$k  1) *s row k A + row k A + s" 
36350  881 
by (vector field_simps) 
53854  882 
have th001: "\<And>f k . (\<lambda>x. if x = k then f k else f x) = f" 
883 
by auto 

33175  884 
have "(\<chi> i. row i A) = A" by (vector row_def) 
53253  885 
then have thd1: "det (\<chi> i. row i A) = det A" 
886 
by simp 

33175  887 
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" 
68134  888 
by (force intro: det_row_span vec.span_sum vec.span_scale vec.span_base) 
33175  889 
show "?lhs = x$k * det A" 
890 
apply (subst U) 

68134  891 
unfolding sum.insert[OF finite kUk] 
33175  892 
apply (subst th00) 
57512
cc97b347b301
reduced name variants for assoc and commute on plus and mult
haftmann
parents:
57418
diff
changeset

893 
unfolding add.assoc 
33175  894 
apply (subst det_row_add) 
895 
unfolding thd0 

896 
unfolding det_row_mul 

897 
unfolding th001[of k "\<lambda>i. row i A"] 

53253  898 
unfolding thd1 
899 
apply (simp add: field_simps) 

900 
done 

33175  901 
qed 
902 

903 
lemma cramer_lemma: 

36593
fb69c8cd27bd
define linear algebra concepts using scaleR instead of (op *s); generalized many lemmas, though a few theorems that used to work on type int^'n are a bit less general
huffman
parents:
36585
diff
changeset

904 
fixes A :: "real^'n^'n" 
fb69c8cd27bd
define linear algebra concepts using scaleR instead of (op *s); generalized many lemmas, though a few theorems that used to work on type int^'n are a bit less general
huffman
parents:
36585
diff
changeset

905 
shows "det((\<chi> i j. if j = k then (A *v x)$i else A$i$j):: real^'n^'n) = x$k * det A" 
53253  906 
proof  
33175  907 
let ?U = "UNIV :: 'n set" 
64267  908 
have *: "\<And>c. sum (\<lambda>i. c i *s row i (transpose A)) ?U = sum (\<lambda>i. c i *s column i A) ?U" 
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

909 
by (auto intro: sum.cong) 
53854  910 
show ?thesis 
67673
c8caefb20564
lots of new material, ultimately related to measure theory
paulson <lp15@cam.ac.uk>
parents:
67399
diff
changeset

911 
unfolding matrix_mult_sum 
53253  912 
unfolding cramer_lemma_transpose[of k x "transpose A", unfolded det_transpose, symmetric] 
913 
unfolding *[of "\<lambda>i. x$i"] 

914 
apply (subst det_transpose[symmetric]) 

915 
apply (rule cong[OF refl[of det]]) 

916 
apply (vector transpose_def column_def row_def) 

917 
done 

33175  918 
qed 
919 

920 
lemma cramer: 

34291
4e896680897e
finite annotation on cartesian product is now implicit.
hoelzl
parents:
34289
diff
changeset

921 
fixes A ::"real^'n^'n" 
33175  922 
assumes d0: "det A \<noteq> 0" 
36362
06475a1547cb
fix lots of looping simp calls and other warnings
huffman
parents:
35542
diff
changeset

923 
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)" 
53253  924 
proof  
33175  925 
from d0 obtain B where B: "A ** B = mat 1" "B ** A = mat 1" 
53854  926 
unfolding invertible_det_nz[symmetric] invertible_def 
927 
by blast 

928 
have "(A ** B) *v b = b" 

68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

929 
by (simp add: B) 
53854  930 
then have "A *v (B *v b) = b" 
931 
by (simp add: matrix_vector_mul_assoc) 

932 
then have xe: "\<exists>x. A *v x = b" 

933 
by blast 

53253  934 
{ 
935 
fix x 

936 
assume x: "A *v x = b" 

937 
have "x = (\<chi> k. det(\<chi> i j. if j=k then b$i else A$i$j) / det A)" 

938 
unfolding x[symmetric] 

939 
using d0 by (simp add: vec_eq_iff cramer_lemma field_simps) 

940 
} 

53854  941 
with xe show ?thesis 
942 
by auto 

33175  943 
qed 
944 

67968  945 
subsection \<open>Orthogonality of a transformation and matrix\<close> 
33175  946 

947 
definition "orthogonal_transformation f \<longleftrightarrow> linear f \<and> (\<forall>v w. f v \<bullet> f w = v \<bullet> w)" 

948 

67981
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

949 
definition "orthogonal_matrix (Q::'a::semiring_1^'n^'n) \<longleftrightarrow> 
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

950 
transpose Q ** Q = mat 1 \<and> Q ** transpose Q = mat 1" 
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

951 

53253  952 
lemma orthogonal_transformation: 
67733
346cb74e79f6
generalized lemmas about orthogonal transformation
immler
parents:
67683
diff
changeset

953 
"orthogonal_transformation f \<longleftrightarrow> linear f \<and> (\<forall>v. norm (f v) = norm v)" 
33175  954 
unfolding orthogonal_transformation_def 
955 
apply auto 

956 
apply (erule_tac x=v in allE)+ 

35542  957 
apply (simp add: norm_eq_sqrt_inner) 
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

958 
apply (simp add: dot_norm linear_add[symmetric]) 
53253  959 
done 
33175  960 

67683
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

961 
lemma orthogonal_transformation_id [simp]: "orthogonal_transformation (\<lambda>x. x)" 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

962 
by (simp add: linear_iff orthogonal_transformation_def) 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

963 

817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

964 
lemma orthogonal_orthogonal_transformation: 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

965 
"orthogonal_transformation f \<Longrightarrow> orthogonal (f x) (f y) \<longleftrightarrow> orthogonal x y" 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

966 
by (simp add: orthogonal_def orthogonal_transformation_def) 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

967 

817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

968 
lemma orthogonal_transformation_compose: 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

969 
"\<lbrakk>orthogonal_transformation f; orthogonal_transformation g\<rbrakk> \<Longrightarrow> orthogonal_transformation(f \<circ> g)" 
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

970 
by (auto simp add: orthogonal_transformation_def linear_compose) 
67683
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

971 

817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

972 
lemma orthogonal_transformation_neg: 
67733
346cb74e79f6
generalized lemmas about orthogonal transformation
immler
parents:
67683
diff
changeset

973 
"orthogonal_transformation(\<lambda>x. (f x)) \<longleftrightarrow> orthogonal_transformation f" 
67683
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

974 
by (auto simp: orthogonal_transformation_def dest: linear_compose_neg) 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

975 

67981
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

976 
lemma orthogonal_transformation_scaleR: "orthogonal_transformation f \<Longrightarrow> f (c *\<^sub>R v) = c *\<^sub>R f v" 
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

977 
by (simp add: linear_iff orthogonal_transformation_def) 
349c639e593c
more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67971
diff
changeset

978 

67683
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

979 
lemma orthogonal_transformation_linear: 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

980 
"orthogonal_transformation f \<Longrightarrow> linear f" 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

981 
by (simp add: orthogonal_transformation_def) 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

982 

817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

983 
lemma orthogonal_transformation_inj: 
67733
346cb74e79f6
generalized lemmas about orthogonal transformation
immler
parents:
67683
diff
changeset

984 
"orthogonal_transformation f \<Longrightarrow> inj f" 
346cb74e79f6
generalized lemmas about orthogonal transformation
immler
parents:
67683
diff
changeset

985 
unfolding orthogonal_transformation_def inj_on_def 
346cb74e79f6
generalized lemmas about orthogonal transformation
immler
parents:
67683
diff
changeset

986 
by (metis vector_eq) 
67683
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

987 

817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

988 
lemma orthogonal_transformation_surj: 
67733
346cb74e79f6
generalized lemmas about orthogonal transformation
immler
parents:
67683
diff
changeset

989 
"orthogonal_transformation f \<Longrightarrow> surj f" 
346cb74e79f6
generalized lemmas about orthogonal transformation
immler
parents:
67683
diff
changeset

990 
for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space" 
67683
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

991 
by (simp add: linear_injective_imp_surjective orthogonal_transformation_inj orthogonal_transformation_linear) 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

992 

817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

993 
lemma orthogonal_transformation_bij: 
67733
346cb74e79f6
generalized lemmas about orthogonal transformation
immler
parents:
67683
diff
changeset

994 
"orthogonal_transformation f \<Longrightarrow> bij f" 
346cb74e79f6
generalized lemmas about orthogonal transformation
immler
parents:
67683
diff
changeset

995 
for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space" 
67683
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

996 
by (simp add: bij_def orthogonal_transformation_inj orthogonal_transformation_surj) 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

997 

817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

998 
lemma orthogonal_transformation_inv: 
67733
346cb74e79f6
generalized lemmas about orthogonal transformation
immler
parents:
67683
diff
changeset

999 
"orthogonal_transformation f \<Longrightarrow> orthogonal_transformation (inv f)" 
346cb74e79f6
generalized lemmas about orthogonal transformation
immler
parents:
67683
diff
changeset

1000 
for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space" 
67683
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1001 
by (metis (no_types, hide_lams) bijection.inv_right bijection_def inj_linear_imp_inv_linear orthogonal_transformation orthogonal_transformation_bij orthogonal_transformation_inj) 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1002 

817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1003 
lemma orthogonal_transformation_norm: 
67733
346cb74e79f6
generalized lemmas about orthogonal transformation
immler
parents:
67683
diff
changeset

1004 
"orthogonal_transformation f \<Longrightarrow> norm (f x) = norm x" 
67683
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1005 
by (metis orthogonal_transformation) 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1006 

53253  1007 
lemma orthogonal_matrix: "orthogonal_matrix (Q:: real ^'n^'n) \<longleftrightarrow> transpose Q ** Q = mat 1" 
33175  1008 
by (metis matrix_left_right_inverse orthogonal_matrix_def) 
1009 

34291
4e896680897e
finite annotation on cartesian product is now implicit.
hoelzl
parents:
34289
diff
changeset

1010 
lemma orthogonal_matrix_id: "orthogonal_matrix (mat 1 :: _^'n^'n)" 
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

1011 
by (simp add: orthogonal_matrix_def) 
33175  1012 

1013 
lemma orthogonal_matrix_mul: 

34291
4e896680897e
finite annotation on cartesian product is now implicit.
hoelzl
parents:
34289
diff
changeset

1014 
fixes A :: "real ^'n^'n" 
33175  1015 
assumes oA : "orthogonal_matrix A" 
53253  1016 
and oB: "orthogonal_matrix B" 
33175  1017 
shows "orthogonal_matrix(A ** B)" 
1018 
using oA oB 

35150
082fa4bd403d
Rename transp to transpose in HOLMultivariate_Analysis. (by himmelma)
hoelzl
parents:
35028
diff
changeset

1019 
unfolding orthogonal_matrix matrix_transpose_mul 
33175  1020 
apply (subst matrix_mul_assoc) 
1021 
apply (subst matrix_mul_assoc[symmetric]) 

68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

1022 
apply (simp add: ) 
53253  1023 
done 
33175  1024 

1025 
lemma orthogonal_transformation_matrix: 

34291
4e896680897e
finite annotation on cartesian product is now implicit.
hoelzl
parents:
34289
diff
changeset

1026 
fixes f:: "real^'n \<Rightarrow> real^'n" 
33175  1027 
shows "orthogonal_transformation f \<longleftrightarrow> linear f \<and> orthogonal_matrix(matrix f)" 
1028 
(is "?lhs \<longleftrightarrow> ?rhs") 

53253  1029 
proof  
33175  1030 
let ?mf = "matrix f" 
1031 
let ?ot = "orthogonal_transformation f" 

1032 
let ?U = "UNIV :: 'n set" 

1033 
have fU: "finite ?U" by simp 

1034 
let ?m1 = "mat 1 :: real ^'n^'n" 

53253  1035 
{ 
1036 
assume ot: ?ot 

68134  1037 
from ot have lf: "Vector_Spaces.linear ( *s) ( *s) f" and fd: "\<And>v w. f v \<bullet> f w = v \<bullet> w" 
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

1038 
unfolding orthogonal_transformation_def orthogonal_matrix linear_def scalar_mult_eq_scaleR 
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

1039 
by blast+ 
53253  1040 
{ 
1041 
fix i j 

35150
082fa4bd403d
Rename transp to transpose in HOLMultivariate_Analysis. (by himmelma)
hoelzl
parents:
35028
diff
changeset

1042 
let ?A = "transpose ?mf ** ?mf" 
33175  1043 
have th0: "\<And>b (x::'a::comm_ring_1). (if b then 1 else 0)*x = (if b then x else 0)" 
1044 
"\<And>b (x::'a::comm_ring_1). x*(if b then 1 else 0) = (if b then x else 0)" 

1045 
by simp_all 

68134  1046 
from fd[of "axis i 1" "axis j 1", 
63170  1047 
simplified matrix_works[OF lf, symmetric] dot_matrix_vector_mul] 
33175  1048 
have "?A$i$j = ?m1 $ i $ j" 
50526
899c9c4e4a4c
Remove the indexed basis from the definition of euclidean spaces and only use the set of Basis vectors
hoelzl
parents:
47108
diff
changeset

1049 
by (simp add: inner_vec_def matrix_matrix_mult_def columnvector_def rowvector_def 
64267  1050 
th0 sum.delta[OF fU] mat_def axis_def) 
53253  1051 
} 
53854  1052 
then have "orthogonal_matrix ?mf" 
1053 
unfolding orthogonal_matrix 

53253  1054 
by vector 
53854  1055 
with lf have ?rhs 
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

1056 
unfolding linear_def scalar_mult_eq_scaleR 
53854  1057 
by blast 
53253  1058 
} 
33175  1059 
moreover 
53253  1060 
{ 
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

1061 
assume lf: "Vector_Spaces.linear ( *s) ( *s) f" and om: "orthogonal_matrix ?mf" 
33175  1062 
from lf om have ?lhs 
63170  1063 
apply (simp only: orthogonal_matrix_def norm_eq orthogonal_transformation) 
1064 
apply (simp only: matrix_works[OF lf, symmetric]) 

33175  1065 
apply (subst dot_matrix_vector_mul) 
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

1066 
apply (simp add: dot_matrix_product linear_def scalar_mult_eq_scaleR) 
53253  1067 
done 
1068 
} 

53854  1069 
ultimately show ?thesis 
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

1070 
by (auto simp: linear_def scalar_mult_eq_scaleR) 
33175  1071 
qed 
1072 

1073 
lemma det_orthogonal_matrix: 

35028
108662d50512
more consistent naming of type classes involving orderings (and lattices)  c.f. NEWS
haftmann
parents:
34291
diff
changeset

1074 
fixes Q:: "'a::linordered_idom^'n^'n" 
33175  1075 
assumes oQ: "orthogonal_matrix Q" 
1076 
shows "det Q = 1 \<or> det Q =  1" 

53253  1077 
proof  
33175  1078 
have th: "\<And>x::'a. x = 1 \<or> x =  1 \<longleftrightarrow> x*x = 1" (is "\<And>x::'a. ?ths x") 
53253  1079 
proof  
33175  1080 
fix x:: 'a 
53854  1081 
have th0: "x * x  1 = (x  1) * (x + 1)" 
53253  1082 
by (simp add: field_simps) 
33175  1083 
have th1: "\<And>(x::'a) y. x =  y \<longleftrightarrow> x + y = 0" 
53253  1084 
apply (subst eq_iff_diff_eq_0) 
1085 
apply simp 

1086 
done 

53854  1087 
have "x * x = 1 \<longleftrightarrow> x * x  1 = 0" 
1088 
by simp 

1089 
also have "\<dots> \<longleftrightarrow> x = 1 \<or> x =  1" 

1090 
unfolding th0 th1 by simp 

33175  1091 
finally show "?ths x" .. 
1092 
qed 

53253  1093 
from oQ have "Q ** transpose Q = mat 1" 
1094 
by (metis orthogonal_matrix_def) 

1095 
then have "det (Q ** transpose Q) = det (mat 1:: 'a^'n^'n)" 

1096 
by simp 

1097 
then have "det Q * det Q = 1" 

68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOLAnalysis accordingly
immler
parents:
67990
diff
changeset

1098 
by (simp add: det_mul) 
33175  1099 
then show ?thesis unfolding th . 
1100 
qed 

1101 

67683
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1102 
lemma orthogonal_transformation_det [simp]: 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1103 
fixes f :: "real^'n \<Rightarrow> real^'n" 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1104 
shows "orthogonal_transformation f \<Longrightarrow> \<bar>det (matrix f)\<bar> = 1" 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1105 
using det_orthogonal_matrix orthogonal_transformation_matrix by fastforce 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1106 

817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1107 

67968  1108 
subsection \<open>Linearity of scaling, and hence isometry, that preserves origin\<close> 
53854  1109 

33175  1110 
lemma scaling_linear: 
67733
346cb74e79f6
generalized lemmas about orthogonal transformation
immler
parents:
67683
diff
changeset

1111 
fixes f :: "'a::real_inner \<Rightarrow> 'a::real_inner" 
53253  1112 
assumes f0: "f 0 = 0" 
1113 
and fd: "\<forall>x y. dist (f x) (f y) = c * dist x y" 

33175  1114 
shows "linear f" 
53253  1115 
proof  
1116 
{ 

1117 
fix v w 

68134  1118 
have "norm (f x) = c * norm x" for x 
1119 
by (metis dist_0_norm f0 fd) 

1120 
then have "f v \<bullet> f w = c\<^sup>2 * (v \<bullet> w)" 

33175  1121 
unfolding dot_norm_neg dist_norm[symmetric] 
68134  1122 
by (simp add: fd power2_eq_square field_simps) 
1123 
} 

1124 
then show ?thesis 

67733
346cb74e79f6
generalized lemmas about orthogonal transformation
immler
parents:
67683
diff
changeset

1125 
unfolding linear_iff vector_eq[where 'a="'a"] scalar_mult_eq_scaleR 
68134  1126 
by (simp add: inner_add field_simps) 
33175  1127 
qed 
1128 

1129 
lemma isometry_linear: 

67733
346cb74e79f6
generalized lemmas about orthogonal transformation
immler
parents:
67683
diff
changeset

1130 
"f (0::'a::real_inner) = (0::'a) \<Longrightarrow> \<forall>x y. dist(f x) (f y) = dist x y \<Longrightarrow> linear f" 
53253  1131 
by (rule scaling_linear[where c=1]) simp_all 
33175  1132 

68134  1133 
text \<open>Hence another formulation of orthogonal transformation\<close> 
33175  1134 

1135 
lemma orthogonal_transformation_isometry: 

67733
346cb74e79f6
generalized lemmas about orthogonal transformation
immler
parents:
67683
diff
changeset

1136 
"orthogonal_transformation f \<longleftrightarrow> f(0::'a::real_inner) = (0::'a) \<and> (\<forall>x y. dist(f x) (f y) = dist x y)" 
33175  1137 
unfolding orthogonal_transformation 
67683
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1138 
apply (auto simp: linear_0 isometry_linear) 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1139 
apply (metis (no_types, hide_lams) dist_norm linear_diff) 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1140 
by (metis dist_0_norm) 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1141 

817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1142 

817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1143 
lemma image_orthogonal_transformation_ball: 
67733
346cb74e79f6
generalized lemmas about orthogonal transformation
immler
parents:
67683
diff
changeset

1144 
fixes f :: "'a::euclidean_space \<Rightarrow> 'a" 
67683
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1145 
assumes "orthogonal_transformation f" 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1146 
shows "f ` ball x r = ball (f x) r" 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1147 
proof (intro equalityI subsetI) 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1148 
fix y assume "y \<in> f ` ball x r" 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1149 
with assms show "y \<in> ball (f x) r" 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1150 
by (auto simp: orthogonal_transformation_isometry) 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1151 
next 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1152 
fix y assume y: "y \<in> ball (f x) r" 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1153 
then obtain z where z: "y = f z" 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1154 
using assms orthogonal_transformation_surj by blast 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1155 
with y assms show "y \<in> f ` ball x r" 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1156 
by (auto simp: orthogonal_transformation_isometry) 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1157 
qed 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1158 

817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1159 
lemma image_orthogonal_transformation_cball: 
67733
346cb74e79f6
generalized lemmas about orthogonal transformation
immler
parents:
67683
diff
changeset

1160 
fixes f :: "'a::euclidean_space \<Rightarrow> 'a" 
67683
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1161 
assumes "orthogonal_transformation f" 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1162 
shows "f ` cball x r = cball (f x) r" 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1163 
proof (intro equalityI subsetI) 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1164 
fix y assume "y \<in> f ` cball x r" 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1165 
with assms show "y \<in> cball (f x) r" 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1166 
by (auto simp: orthogonal_transformation_isometry) 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1167 
next 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1168 
fix y assume y: "y \<in> cball (f x) r" 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1169 
then obtain z where z: "y = f z" 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1170 
using assms orthogonal_transformation_surj by blast 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1171 
with y assms show "y \<in> f ` cball x r" 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1172 
by (auto simp: orthogonal_transformation_isometry) 
817944aeac3f
Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents:
67673
diff
changeset

1173 
qed 