author | immler |
Wed, 16 Jan 2019 18:14:02 -0500 | |
changeset 69675 | 880ab0f27ddf |
parent 69674 | fc252acb7100 |
child 69683 | 8b3458ca0762 |
permissions | -rw-r--r-- |
63627 | 1 |
(* Title: HOL/Analysis/Linear_Algebra.thy |
44133 | 2 |
Author: Amine Chaieb, University of Cambridge |
3 |
*) |
|
4 |
||
69517 | 5 |
section \<open>Elementary Linear Algebra on Euclidean Spaces\<close> |
44133 | 6 |
|
7 |
theory Linear_Algebra |
|
8 |
imports |
|
9 |
Euclidean_Space |
|
66453
cc19f7ca2ed6
session-qualified theory imports: isabelle imports -U -i -d '~~/src/Benchmarks' -a;
wenzelm
parents:
66447
diff
changeset
|
10 |
"HOL-Library.Infinite_Set" |
44133 | 11 |
begin |
12 |
||
63886
685fb01256af
move Henstock-Kurzweil integration after Lebesgue_Measure; replace content by abbreviation measure lborel
hoelzl
parents:
63881
diff
changeset
|
13 |
lemma linear_simps: |
685fb01256af
move Henstock-Kurzweil integration after Lebesgue_Measure; replace content by abbreviation measure lborel
hoelzl
parents:
63881
diff
changeset
|
14 |
assumes "bounded_linear f" |
685fb01256af
move Henstock-Kurzweil integration after Lebesgue_Measure; replace content by abbreviation measure lborel
hoelzl
parents:
63881
diff
changeset
|
15 |
shows |
685fb01256af
move Henstock-Kurzweil integration after Lebesgue_Measure; replace content by abbreviation measure lborel
hoelzl
parents:
63881
diff
changeset
|
16 |
"f (a + b) = f a + f b" |
685fb01256af
move Henstock-Kurzweil integration after Lebesgue_Measure; replace content by abbreviation measure lborel
hoelzl
parents:
63881
diff
changeset
|
17 |
"f (a - b) = f a - f b" |
685fb01256af
move Henstock-Kurzweil integration after Lebesgue_Measure; replace content by abbreviation measure lborel
hoelzl
parents:
63881
diff
changeset
|
18 |
"f 0 = 0" |
685fb01256af
move Henstock-Kurzweil integration after Lebesgue_Measure; replace content by abbreviation measure lborel
hoelzl
parents:
63881
diff
changeset
|
19 |
"f (- a) = - f a" |
685fb01256af
move Henstock-Kurzweil integration after Lebesgue_Measure; replace content by abbreviation measure lborel
hoelzl
parents:
63881
diff
changeset
|
20 |
"f (s *\<^sub>R v) = s *\<^sub>R (f v)" |
685fb01256af
move Henstock-Kurzweil integration after Lebesgue_Measure; replace content by abbreviation measure lborel
hoelzl
parents:
63881
diff
changeset
|
21 |
proof - |
685fb01256af
move Henstock-Kurzweil integration after Lebesgue_Measure; replace content by abbreviation measure lborel
hoelzl
parents:
63881
diff
changeset
|
22 |
interpret f: bounded_linear f by fact |
685fb01256af
move Henstock-Kurzweil integration after Lebesgue_Measure; replace content by abbreviation measure lborel
hoelzl
parents:
63881
diff
changeset
|
23 |
show "f (a + b) = f a + f b" by (rule f.add) |
685fb01256af
move Henstock-Kurzweil integration after Lebesgue_Measure; replace content by abbreviation measure lborel
hoelzl
parents:
63881
diff
changeset
|
24 |
show "f (a - b) = f a - f b" by (rule f.diff) |
685fb01256af
move Henstock-Kurzweil integration after Lebesgue_Measure; replace content by abbreviation measure lborel
hoelzl
parents:
63881
diff
changeset
|
25 |
show "f 0 = 0" by (rule f.zero) |
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
26 |
show "f (- a) = - f a" by (rule f.neg) |
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
27 |
show "f (s *\<^sub>R v) = s *\<^sub>R (f v)" by (rule f.scale) |
44133 | 28 |
qed |
29 |
||
68069
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68062
diff
changeset
|
30 |
lemma finite_Atleast_Atmost_nat[simp]: "finite {f x |x. x \<in> (UNIV::'a::finite set)}" |
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68062
diff
changeset
|
31 |
using finite finite_image_set by blast |
44133 | 32 |
|
69675
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
33 |
lemma substdbasis_expansion_unique: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
34 |
includes inner_syntax |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
35 |
assumes d: "d \<subseteq> Basis" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
36 |
shows "(\<Sum>i\<in>d. f i *\<^sub>R i) = (x::'a::euclidean_space) \<longleftrightarrow> |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
37 |
(\<forall>i\<in>Basis. (i \<in> d \<longrightarrow> f i = x \<bullet> i) \<and> (i \<notin> d \<longrightarrow> x \<bullet> i = 0))" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
38 |
proof - |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
39 |
have *: "\<And>x a b P. x * (if P then a else b) = (if P then x * a else x * b)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
40 |
by auto |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
41 |
have **: "finite d" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
42 |
by (auto intro: finite_subset[OF assms]) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
43 |
have ***: "\<And>i. i \<in> Basis \<Longrightarrow> (\<Sum>i\<in>d. f i *\<^sub>R i) \<bullet> i = (\<Sum>x\<in>d. if x = i then f x else 0)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
44 |
using d |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
45 |
by (auto intro!: sum.cong simp: inner_Basis inner_sum_left) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
46 |
show ?thesis |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
47 |
unfolding euclidean_eq_iff[where 'a='a] by (auto simp: sum.delta[OF **] ***) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
48 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
49 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
50 |
lemma independent_substdbasis: "d \<subseteq> Basis \<Longrightarrow> independent d" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
51 |
by (rule independent_mono[OF independent_Basis]) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
52 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
53 |
lemma sum_not_0: "sum f A \<noteq> 0 \<Longrightarrow> \<exists>a \<in> A. f a \<noteq> 0" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
54 |
by (rule ccontr) auto |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
55 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
56 |
lemma subset_translation_eq [simp]: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
57 |
fixes a :: "'a::real_vector" shows "(+) a ` s \<subseteq> (+) a ` t \<longleftrightarrow> s \<subseteq> t" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
58 |
by auto |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
59 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
60 |
lemma translate_inj_on: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
61 |
fixes A :: "'a::ab_group_add set" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
62 |
shows "inj_on (\<lambda>x. a + x) A" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
63 |
unfolding inj_on_def by auto |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
64 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
65 |
lemma translation_assoc: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
66 |
fixes a b :: "'a::ab_group_add" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
67 |
shows "(\<lambda>x. b + x) ` ((\<lambda>x. a + x) ` S) = (\<lambda>x. (a + b) + x) ` S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
68 |
by auto |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
69 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
70 |
lemma translation_invert: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
71 |
fixes a :: "'a::ab_group_add" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
72 |
assumes "(\<lambda>x. a + x) ` A = (\<lambda>x. a + x) ` B" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
73 |
shows "A = B" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
74 |
proof - |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
75 |
have "(\<lambda>x. -a + x) ` ((\<lambda>x. a + x) ` A) = (\<lambda>x. - a + x) ` ((\<lambda>x. a + x) ` B)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
76 |
using assms by auto |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
77 |
then show ?thesis |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
78 |
using translation_assoc[of "-a" a A] translation_assoc[of "-a" a B] by auto |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
79 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
80 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
81 |
lemma translation_galois: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
82 |
fixes a :: "'a::ab_group_add" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
83 |
shows "T = ((\<lambda>x. a + x) ` S) \<longleftrightarrow> S = ((\<lambda>x. (- a) + x) ` T)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
84 |
using translation_assoc[of "-a" a S] |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
85 |
apply auto |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
86 |
using translation_assoc[of a "-a" T] |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
87 |
apply auto |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
88 |
done |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
89 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
90 |
lemma translation_inverse_subset: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
91 |
assumes "((\<lambda>x. - a + x) ` V) \<le> (S :: 'n::ab_group_add set)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
92 |
shows "V \<le> ((\<lambda>x. a + x) ` S)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
93 |
proof - |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
94 |
{ |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
95 |
fix x |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
96 |
assume "x \<in> V" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
97 |
then have "x-a \<in> S" using assms by auto |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
98 |
then have "x \<in> {a + v |v. v \<in> S}" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
99 |
apply auto |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
100 |
apply (rule exI[of _ "x-a"], simp) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
101 |
done |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
102 |
then have "x \<in> ((\<lambda>x. a+x) ` S)" by auto |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
103 |
} |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
104 |
then show ?thesis by auto |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
105 |
qed |
53406 | 106 |
|
68901 | 107 |
subsection%unimportant \<open>More interesting properties of the norm\<close> |
63050 | 108 |
|
69674 | 109 |
unbundle inner_syntax |
63050 | 110 |
|
69597 | 111 |
text\<open>Equality of vectors in terms of \<^term>\<open>(\<bullet>)\<close> products.\<close> |
63050 | 112 |
|
113 |
lemma linear_componentwise: |
|
114 |
fixes f:: "'a::euclidean_space \<Rightarrow> 'b::real_inner" |
|
115 |
assumes lf: "linear f" |
|
116 |
shows "(f x) \<bullet> j = (\<Sum>i\<in>Basis. (x\<bullet>i) * (f i\<bullet>j))" (is "?lhs = ?rhs") |
|
117 |
proof - |
|
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
118 |
interpret linear f by fact |
63050 | 119 |
have "?rhs = (\<Sum>i\<in>Basis. (x\<bullet>i) *\<^sub>R (f i))\<bullet>j" |
64267 | 120 |
by (simp add: inner_sum_left) |
63050 | 121 |
then show ?thesis |
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
122 |
by (simp add: euclidean_representation sum[symmetric] scale[symmetric]) |
63050 | 123 |
qed |
124 |
||
125 |
lemma vector_eq: "x = y \<longleftrightarrow> x \<bullet> x = x \<bullet> y \<and> y \<bullet> y = x \<bullet> x" |
|
126 |
(is "?lhs \<longleftrightarrow> ?rhs") |
|
127 |
proof |
|
128 |
assume ?lhs |
|
129 |
then show ?rhs by simp |
|
130 |
next |
|
131 |
assume ?rhs |
|
132 |
then have "x \<bullet> x - x \<bullet> y = 0 \<and> x \<bullet> y - y \<bullet> y = 0" |
|
133 |
by simp |
|
134 |
then have "x \<bullet> (x - y) = 0 \<and> y \<bullet> (x - y) = 0" |
|
135 |
by (simp add: inner_diff inner_commute) |
|
136 |
then have "(x - y) \<bullet> (x - y) = 0" |
|
137 |
by (simp add: field_simps inner_diff inner_commute) |
|
138 |
then show "x = y" by simp |
|
139 |
qed |
|
140 |
||
141 |
lemma norm_triangle_half_r: |
|
142 |
"norm (y - x1) < e / 2 \<Longrightarrow> norm (y - x2) < e / 2 \<Longrightarrow> norm (x1 - x2) < e" |
|
143 |
using dist_triangle_half_r unfolding dist_norm[symmetric] by auto |
|
144 |
||
145 |
lemma norm_triangle_half_l: |
|
146 |
assumes "norm (x - y) < e / 2" |
|
147 |
and "norm (x' - y) < e / 2" |
|
148 |
shows "norm (x - x') < e" |
|
149 |
using dist_triangle_half_l[OF assms[unfolded dist_norm[symmetric]]] |
|
150 |
unfolding dist_norm[symmetric] . |
|
151 |
||
66420 | 152 |
lemma abs_triangle_half_r: |
153 |
fixes y :: "'a::linordered_field" |
|
154 |
shows "abs (y - x1) < e / 2 \<Longrightarrow> abs (y - x2) < e / 2 \<Longrightarrow> abs (x1 - x2) < e" |
|
155 |
by linarith |
|
156 |
||
157 |
lemma abs_triangle_half_l: |
|
158 |
fixes y :: "'a::linordered_field" |
|
159 |
assumes "abs (x - y) < e / 2" |
|
160 |
and "abs (x' - y) < e / 2" |
|
161 |
shows "abs (x - x') < e" |
|
162 |
using assms by linarith |
|
163 |
||
64267 | 164 |
lemma sum_clauses: |
165 |
shows "sum f {} = 0" |
|
166 |
and "finite S \<Longrightarrow> sum f (insert x S) = (if x \<in> S then sum f S else f x + sum f S)" |
|
63050 | 167 |
by (auto simp add: insert_absorb) |
168 |
||
169 |
lemma vector_eq_ldot: "(\<forall>x. x \<bullet> y = x \<bullet> z) \<longleftrightarrow> y = z" |
|
170 |
proof |
|
171 |
assume "\<forall>x. x \<bullet> y = x \<bullet> z" |
|
172 |
then have "\<forall>x. x \<bullet> (y - z) = 0" |
|
173 |
by (simp add: inner_diff) |
|
174 |
then have "(y - z) \<bullet> (y - z) = 0" .. |
|
175 |
then show "y = z" by simp |
|
176 |
qed simp |
|
177 |
||
178 |
lemma vector_eq_rdot: "(\<forall>z. x \<bullet> z = y \<bullet> z) \<longleftrightarrow> x = y" |
|
179 |
proof |
|
180 |
assume "\<forall>z. x \<bullet> z = y \<bullet> z" |
|
181 |
then have "\<forall>z. (x - y) \<bullet> z = 0" |
|
182 |
by (simp add: inner_diff) |
|
183 |
then have "(x - y) \<bullet> (x - y) = 0" .. |
|
184 |
then show "x = y" by simp |
|
185 |
qed simp |
|
186 |
||
69619
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
187 |
subsection \<open>Substandard Basis\<close> |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
188 |
|
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
189 |
lemma ex_card: |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
190 |
assumes "n \<le> card A" |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
191 |
shows "\<exists>S\<subseteq>A. card S = n" |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
192 |
proof (cases "finite A") |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
193 |
case True |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
194 |
from ex_bij_betw_nat_finite[OF this] obtain f where f: "bij_betw f {0..<card A} A" .. |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
195 |
moreover from f \<open>n \<le> card A\<close> have "{..< n} \<subseteq> {..< card A}" "inj_on f {..< n}" |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
196 |
by (auto simp: bij_betw_def intro: subset_inj_on) |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
197 |
ultimately have "f ` {..< n} \<subseteq> A" "card (f ` {..< n}) = n" |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
198 |
by (auto simp: bij_betw_def card_image) |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
199 |
then show ?thesis by blast |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
200 |
next |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
201 |
case False |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
202 |
with \<open>n \<le> card A\<close> show ?thesis by force |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
203 |
qed |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
204 |
|
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
205 |
lemma subspace_substandard: "subspace {x::'a::euclidean_space. (\<forall>i\<in>Basis. P i \<longrightarrow> x\<bullet>i = 0)}" |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
206 |
by (auto simp: subspace_def inner_add_left) |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
207 |
|
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
208 |
lemma dim_substandard: |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
209 |
assumes d: "d \<subseteq> Basis" |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
210 |
shows "dim {x::'a::euclidean_space. \<forall>i\<in>Basis. i \<notin> d \<longrightarrow> x\<bullet>i = 0} = card d" (is "dim ?A = _") |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
211 |
proof (rule dim_unique) |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
212 |
from d show "d \<subseteq> ?A" |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
213 |
by (auto simp: inner_Basis) |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
214 |
from d show "independent d" |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
215 |
by (rule independent_mono [OF independent_Basis]) |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
216 |
have "x \<in> span d" if "\<forall>i\<in>Basis. i \<notin> d \<longrightarrow> x \<bullet> i = 0" for x |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
217 |
proof - |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
218 |
have "finite d" |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
219 |
by (rule finite_subset [OF d finite_Basis]) |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
220 |
then have "(\<Sum>i\<in>d. (x \<bullet> i) *\<^sub>R i) \<in> span d" |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
221 |
by (simp add: span_sum span_clauses) |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
222 |
also have "(\<Sum>i\<in>d. (x \<bullet> i) *\<^sub>R i) = (\<Sum>i\<in>Basis. (x \<bullet> i) *\<^sub>R i)" |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
223 |
by (rule sum.mono_neutral_cong_left [OF finite_Basis d]) (auto simp: that) |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
224 |
finally show "x \<in> span d" |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
225 |
by (simp only: euclidean_representation) |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
226 |
qed |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
227 |
then show "?A \<subseteq> span d" by auto |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
228 |
qed simp |
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
229 |
|
63050 | 230 |
|
68901 | 231 |
subsection \<open>Orthogonality\<close> |
63050 | 232 |
|
67962 | 233 |
definition%important (in real_inner) "orthogonal x y \<longleftrightarrow> x \<bullet> y = 0" |
234 |
||
63050 | 235 |
context real_inner |
236 |
begin |
|
237 |
||
63072 | 238 |
lemma orthogonal_self: "orthogonal x x \<longleftrightarrow> x = 0" |
239 |
by (simp add: orthogonal_def) |
|
240 |
||
63050 | 241 |
lemma orthogonal_clauses: |
242 |
"orthogonal a 0" |
|
243 |
"orthogonal a x \<Longrightarrow> orthogonal a (c *\<^sub>R x)" |
|
244 |
"orthogonal a x \<Longrightarrow> orthogonal a (- x)" |
|
245 |
"orthogonal a x \<Longrightarrow> orthogonal a y \<Longrightarrow> orthogonal a (x + y)" |
|
246 |
"orthogonal a x \<Longrightarrow> orthogonal a y \<Longrightarrow> orthogonal a (x - y)" |
|
247 |
"orthogonal 0 a" |
|
248 |
"orthogonal x a \<Longrightarrow> orthogonal (c *\<^sub>R x) a" |
|
249 |
"orthogonal x a \<Longrightarrow> orthogonal (- x) a" |
|
250 |
"orthogonal x a \<Longrightarrow> orthogonal y a \<Longrightarrow> orthogonal (x + y) a" |
|
251 |
"orthogonal x a \<Longrightarrow> orthogonal y a \<Longrightarrow> orthogonal (x - y) a" |
|
252 |
unfolding orthogonal_def inner_add inner_diff by auto |
|
253 |
||
254 |
end |
|
255 |
||
256 |
lemma orthogonal_commute: "orthogonal x y \<longleftrightarrow> orthogonal y x" |
|
257 |
by (simp add: orthogonal_def inner_commute) |
|
258 |
||
63114
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
259 |
lemma orthogonal_scaleR [simp]: "c \<noteq> 0 \<Longrightarrow> orthogonal (c *\<^sub>R x) = orthogonal x" |
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
260 |
by (rule ext) (simp add: orthogonal_def) |
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
261 |
|
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
262 |
lemma pairwise_ortho_scaleR: |
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
263 |
"pairwise (\<lambda>i j. orthogonal (f i) (g j)) B |
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
264 |
\<Longrightarrow> pairwise (\<lambda>i j. orthogonal (a i *\<^sub>R f i) (a j *\<^sub>R g j)) B" |
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
265 |
by (auto simp: pairwise_def orthogonal_clauses) |
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
266 |
|
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
267 |
lemma orthogonal_rvsum: |
64267 | 268 |
"\<lbrakk>finite s; \<And>y. y \<in> s \<Longrightarrow> orthogonal x (f y)\<rbrakk> \<Longrightarrow> orthogonal x (sum f s)" |
63114
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
269 |
by (induction s rule: finite_induct) (auto simp: orthogonal_clauses) |
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
270 |
|
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
271 |
lemma orthogonal_lvsum: |
64267 | 272 |
"\<lbrakk>finite s; \<And>x. x \<in> s \<Longrightarrow> orthogonal (f x) y\<rbrakk> \<Longrightarrow> orthogonal (sum f s) y" |
63114
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
273 |
by (induction s rule: finite_induct) (auto simp: orthogonal_clauses) |
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
274 |
|
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
275 |
lemma norm_add_Pythagorean: |
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
276 |
assumes "orthogonal a b" |
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
277 |
shows "norm(a + b) ^ 2 = norm a ^ 2 + norm b ^ 2" |
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
278 |
proof - |
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
279 |
from assms have "(a - (0 - b)) \<bullet> (a - (0 - b)) = a \<bullet> a - (0 - b \<bullet> b)" |
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
280 |
by (simp add: algebra_simps orthogonal_def inner_commute) |
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
281 |
then show ?thesis |
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
282 |
by (simp add: power2_norm_eq_inner) |
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
283 |
qed |
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
284 |
|
64267 | 285 |
lemma norm_sum_Pythagorean: |
63114
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
286 |
assumes "finite I" "pairwise (\<lambda>i j. orthogonal (f i) (f j)) I" |
64267 | 287 |
shows "(norm (sum f I))\<^sup>2 = (\<Sum>i\<in>I. (norm (f i))\<^sup>2)" |
63114
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
288 |
using assms |
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
289 |
proof (induction I rule: finite_induct) |
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
290 |
case empty then show ?case by simp |
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
291 |
next |
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
292 |
case (insert x I) |
64267 | 293 |
then have "orthogonal (f x) (sum f I)" |
63114
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
294 |
by (metis pairwise_insert orthogonal_rvsum) |
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
295 |
with insert show ?case |
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
296 |
by (simp add: pairwise_insert norm_add_Pythagorean) |
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
297 |
qed |
27afe7af7379
Lots of new material for multivariate analysis
paulson <lp15@cam.ac.uk>
parents:
63075
diff
changeset
|
298 |
|
63050 | 299 |
|
69675
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
300 |
subsection%important \<open>Orthogonality of a transformation\<close> |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
301 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
302 |
definition%important "orthogonal_transformation f \<longleftrightarrow> linear f \<and> (\<forall>v w. f v \<bullet> f w = v \<bullet> w)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
303 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
304 |
lemma%unimportant orthogonal_transformation: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
305 |
"orthogonal_transformation f \<longleftrightarrow> linear f \<and> (\<forall>v. norm (f v) = norm v)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
306 |
unfolding orthogonal_transformation_def |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
307 |
apply auto |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
308 |
apply (erule_tac x=v in allE)+ |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
309 |
apply (simp add: norm_eq_sqrt_inner) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
310 |
apply (simp add: dot_norm linear_add[symmetric]) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
311 |
done |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
312 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
313 |
lemma%unimportant orthogonal_transformation_id [simp]: "orthogonal_transformation (\<lambda>x. x)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
314 |
by (simp add: linear_iff orthogonal_transformation_def) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
315 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
316 |
lemma%unimportant orthogonal_orthogonal_transformation: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
317 |
"orthogonal_transformation f \<Longrightarrow> orthogonal (f x) (f y) \<longleftrightarrow> orthogonal x y" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
318 |
by (simp add: orthogonal_def orthogonal_transformation_def) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
319 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
320 |
lemma%unimportant orthogonal_transformation_compose: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
321 |
"\<lbrakk>orthogonal_transformation f; orthogonal_transformation g\<rbrakk> \<Longrightarrow> orthogonal_transformation(f \<circ> g)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
322 |
by (auto simp: orthogonal_transformation_def linear_compose) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
323 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
324 |
lemma%unimportant orthogonal_transformation_neg: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
325 |
"orthogonal_transformation(\<lambda>x. -(f x)) \<longleftrightarrow> orthogonal_transformation f" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
326 |
by (auto simp: orthogonal_transformation_def dest: linear_compose_neg) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
327 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
328 |
lemma%unimportant orthogonal_transformation_scaleR: "orthogonal_transformation f \<Longrightarrow> f (c *\<^sub>R v) = c *\<^sub>R f v" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
329 |
by (simp add: linear_iff orthogonal_transformation_def) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
330 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
331 |
lemma%unimportant orthogonal_transformation_linear: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
332 |
"orthogonal_transformation f \<Longrightarrow> linear f" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
333 |
by (simp add: orthogonal_transformation_def) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
334 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
335 |
lemma%unimportant orthogonal_transformation_inj: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
336 |
"orthogonal_transformation f \<Longrightarrow> inj f" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
337 |
unfolding orthogonal_transformation_def inj_on_def |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
338 |
by (metis vector_eq) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
339 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
340 |
lemma%unimportant orthogonal_transformation_surj: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
341 |
"orthogonal_transformation f \<Longrightarrow> surj f" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
342 |
for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
343 |
by (simp add: linear_injective_imp_surjective orthogonal_transformation_inj orthogonal_transformation_linear) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
344 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
345 |
lemma%unimportant orthogonal_transformation_bij: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
346 |
"orthogonal_transformation f \<Longrightarrow> bij f" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
347 |
for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
348 |
by (simp add: bij_def orthogonal_transformation_inj orthogonal_transformation_surj) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
349 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
350 |
lemma%unimportant orthogonal_transformation_inv: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
351 |
"orthogonal_transformation f \<Longrightarrow> orthogonal_transformation (inv f)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
352 |
for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
353 |
by (metis (no_types, hide_lams) bijection.inv_right bijection_def inj_linear_imp_inv_linear orthogonal_transformation orthogonal_transformation_bij orthogonal_transformation_inj) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
354 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
355 |
lemma%unimportant orthogonal_transformation_norm: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
356 |
"orthogonal_transformation f \<Longrightarrow> norm (f x) = norm x" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
357 |
by (metis orthogonal_transformation) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
358 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
359 |
|
68901 | 360 |
subsection \<open>Bilinear functions\<close> |
63050 | 361 |
|
69600 | 362 |
definition%important |
363 |
bilinear :: "('a::real_vector \<Rightarrow> 'b::real_vector \<Rightarrow> 'c::real_vector) \<Rightarrow> bool" where |
|
364 |
"bilinear f \<longleftrightarrow> (\<forall>x. linear (\<lambda>y. f x y)) \<and> (\<forall>y. linear (\<lambda>x. f x y))" |
|
63050 | 365 |
|
366 |
lemma bilinear_ladd: "bilinear h \<Longrightarrow> h (x + y) z = h x z + h y z" |
|
367 |
by (simp add: bilinear_def linear_iff) |
|
368 |
||
369 |
lemma bilinear_radd: "bilinear h \<Longrightarrow> h x (y + z) = h x y + h x z" |
|
370 |
by (simp add: bilinear_def linear_iff) |
|
371 |
||
372 |
lemma bilinear_lmul: "bilinear h \<Longrightarrow> h (c *\<^sub>R x) y = c *\<^sub>R h x y" |
|
373 |
by (simp add: bilinear_def linear_iff) |
|
374 |
||
375 |
lemma bilinear_rmul: "bilinear h \<Longrightarrow> h x (c *\<^sub>R y) = c *\<^sub>R h x y" |
|
376 |
by (simp add: bilinear_def linear_iff) |
|
377 |
||
378 |
lemma bilinear_lneg: "bilinear h \<Longrightarrow> h (- x) y = - h x y" |
|
379 |
by (drule bilinear_lmul [of _ "- 1"]) simp |
|
380 |
||
381 |
lemma bilinear_rneg: "bilinear h \<Longrightarrow> h x (- y) = - h x y" |
|
382 |
by (drule bilinear_rmul [of _ _ "- 1"]) simp |
|
383 |
||
384 |
lemma (in ab_group_add) eq_add_iff: "x = x + y \<longleftrightarrow> y = 0" |
|
385 |
using add_left_imp_eq[of x y 0] by auto |
|
386 |
||
387 |
lemma bilinear_lzero: |
|
388 |
assumes "bilinear h" |
|
389 |
shows "h 0 x = 0" |
|
390 |
using bilinear_ladd [OF assms, of 0 0 x] by (simp add: eq_add_iff field_simps) |
|
391 |
||
392 |
lemma bilinear_rzero: |
|
393 |
assumes "bilinear h" |
|
394 |
shows "h x 0 = 0" |
|
395 |
using bilinear_radd [OF assms, of x 0 0 ] by (simp add: eq_add_iff field_simps) |
|
396 |
||
397 |
lemma bilinear_lsub: "bilinear h \<Longrightarrow> h (x - y) z = h x z - h y z" |
|
398 |
using bilinear_ladd [of h x "- y"] by (simp add: bilinear_lneg) |
|
399 |
||
400 |
lemma bilinear_rsub: "bilinear h \<Longrightarrow> h z (x - y) = h z x - h z y" |
|
401 |
using bilinear_radd [of h _ x "- y"] by (simp add: bilinear_rneg) |
|
402 |
||
64267 | 403 |
lemma bilinear_sum: |
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
404 |
assumes "bilinear h" |
64267 | 405 |
shows "h (sum f S) (sum g T) = sum (\<lambda>(i,j). h (f i) (g j)) (S \<times> T) " |
63050 | 406 |
proof - |
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
407 |
interpret l: linear "\<lambda>x. h x y" for y using assms by (simp add: bilinear_def) |
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
408 |
interpret r: linear "\<lambda>y. h x y" for x using assms by (simp add: bilinear_def) |
64267 | 409 |
have "h (sum f S) (sum g T) = sum (\<lambda>x. h (f x) (sum g T)) S" |
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
410 |
by (simp add: l.sum) |
64267 | 411 |
also have "\<dots> = sum (\<lambda>x. sum (\<lambda>y. h (f x) (g y)) T) S" |
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
412 |
by (rule sum.cong) (simp_all add: r.sum) |
63050 | 413 |
finally show ?thesis |
64267 | 414 |
unfolding sum.cartesian_product . |
63050 | 415 |
qed |
416 |
||
417 |
||
68901 | 418 |
subsection \<open>Adjoints\<close> |
63050 | 419 |
|
69600 | 420 |
definition%important adjoint :: "(('a::real_inner) \<Rightarrow> ('b::real_inner)) \<Rightarrow> 'b \<Rightarrow> 'a" where |
421 |
"adjoint f = (SOME f'. \<forall>x y. f x \<bullet> y = x \<bullet> f' y)" |
|
63050 | 422 |
|
423 |
lemma adjoint_unique: |
|
424 |
assumes "\<forall>x y. inner (f x) y = inner x (g y)" |
|
425 |
shows "adjoint f = g" |
|
426 |
unfolding adjoint_def |
|
427 |
proof (rule some_equality) |
|
428 |
show "\<forall>x y. inner (f x) y = inner x (g y)" |
|
429 |
by (rule assms) |
|
430 |
next |
|
431 |
fix h |
|
432 |
assume "\<forall>x y. inner (f x) y = inner x (h y)" |
|
433 |
then have "\<forall>x y. inner x (g y) = inner x (h y)" |
|
434 |
using assms by simp |
|
435 |
then have "\<forall>x y. inner x (g y - h y) = 0" |
|
436 |
by (simp add: inner_diff_right) |
|
437 |
then have "\<forall>y. inner (g y - h y) (g y - h y) = 0" |
|
438 |
by simp |
|
439 |
then have "\<forall>y. h y = g y" |
|
440 |
by simp |
|
441 |
then show "h = g" by (simp add: ext) |
|
442 |
qed |
|
443 |
||
444 |
text \<open>TODO: The following lemmas about adjoints should hold for any |
|
63680 | 445 |
Hilbert space (i.e. complete inner product space). |
68224 | 446 |
(see \<^url>\<open>https://en.wikipedia.org/wiki/Hermitian_adjoint\<close>) |
63050 | 447 |
\<close> |
448 |
||
449 |
lemma adjoint_works: |
|
450 |
fixes f :: "'n::euclidean_space \<Rightarrow> 'm::euclidean_space" |
|
451 |
assumes lf: "linear f" |
|
452 |
shows "x \<bullet> adjoint f y = f x \<bullet> y" |
|
453 |
proof - |
|
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
454 |
interpret linear f by fact |
63050 | 455 |
have "\<forall>y. \<exists>w. \<forall>x. f x \<bullet> y = x \<bullet> w" |
456 |
proof (intro allI exI) |
|
457 |
fix y :: "'m" and x |
|
458 |
let ?w = "(\<Sum>i\<in>Basis. (f i \<bullet> y) *\<^sub>R i) :: 'n" |
|
459 |
have "f x \<bullet> y = f (\<Sum>i\<in>Basis. (x \<bullet> i) *\<^sub>R i) \<bullet> y" |
|
460 |
by (simp add: euclidean_representation) |
|
461 |
also have "\<dots> = (\<Sum>i\<in>Basis. (x \<bullet> i) *\<^sub>R f i) \<bullet> y" |
|
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
462 |
by (simp add: sum scale) |
63050 | 463 |
finally show "f x \<bullet> y = x \<bullet> ?w" |
64267 | 464 |
by (simp add: inner_sum_left inner_sum_right mult.commute) |
63050 | 465 |
qed |
466 |
then show ?thesis |
|
467 |
unfolding adjoint_def choice_iff |
|
468 |
by (intro someI2_ex[where Q="\<lambda>f'. x \<bullet> f' y = f x \<bullet> y"]) auto |
|
469 |
qed |
|
470 |
||
471 |
lemma adjoint_clauses: |
|
472 |
fixes f :: "'n::euclidean_space \<Rightarrow> 'm::euclidean_space" |
|
473 |
assumes lf: "linear f" |
|
474 |
shows "x \<bullet> adjoint f y = f x \<bullet> y" |
|
475 |
and "adjoint f y \<bullet> x = y \<bullet> f x" |
|
476 |
by (simp_all add: adjoint_works[OF lf] inner_commute) |
|
477 |
||
478 |
lemma adjoint_linear: |
|
479 |
fixes f :: "'n::euclidean_space \<Rightarrow> 'm::euclidean_space" |
|
480 |
assumes lf: "linear f" |
|
481 |
shows "linear (adjoint f)" |
|
482 |
by (simp add: lf linear_iff euclidean_eq_iff[where 'a='n] euclidean_eq_iff[where 'a='m] |
|
483 |
adjoint_clauses[OF lf] inner_distrib) |
|
484 |
||
485 |
lemma adjoint_adjoint: |
|
486 |
fixes f :: "'n::euclidean_space \<Rightarrow> 'm::euclidean_space" |
|
487 |
assumes lf: "linear f" |
|
488 |
shows "adjoint (adjoint f) = f" |
|
489 |
by (rule adjoint_unique, simp add: adjoint_clauses [OF lf]) |
|
490 |
||
491 |
||
492 |
subsection \<open>Archimedean properties and useful consequences\<close> |
|
493 |
||
494 |
text\<open>Bernoulli's inequality\<close> |
|
68607
67bb59e49834
make theorem, corollary, and proposition %important for HOL-Analysis manual
immler
parents:
68224
diff
changeset
|
495 |
proposition Bernoulli_inequality: |
63050 | 496 |
fixes x :: real |
497 |
assumes "-1 \<le> x" |
|
498 |
shows "1 + n * x \<le> (1 + x) ^ n" |
|
68607
67bb59e49834
make theorem, corollary, and proposition %important for HOL-Analysis manual
immler
parents:
68224
diff
changeset
|
499 |
proof (induct n) |
63050 | 500 |
case 0 |
501 |
then show ?case by simp |
|
502 |
next |
|
503 |
case (Suc n) |
|
504 |
have "1 + Suc n * x \<le> 1 + (Suc n)*x + n * x^2" |
|
505 |
by (simp add: algebra_simps) |
|
506 |
also have "... = (1 + x) * (1 + n*x)" |
|
507 |
by (auto simp: power2_eq_square algebra_simps of_nat_Suc) |
|
508 |
also have "... \<le> (1 + x) ^ Suc n" |
|
509 |
using Suc.hyps assms mult_left_mono by fastforce |
|
510 |
finally show ?case . |
|
511 |
qed |
|
512 |
||
513 |
corollary Bernoulli_inequality_even: |
|
514 |
fixes x :: real |
|
515 |
assumes "even n" |
|
516 |
shows "1 + n * x \<le> (1 + x) ^ n" |
|
517 |
proof (cases "-1 \<le> x \<or> n=0") |
|
518 |
case True |
|
519 |
then show ?thesis |
|
520 |
by (auto simp: Bernoulli_inequality) |
|
521 |
next |
|
522 |
case False |
|
523 |
then have "real n \<ge> 1" |
|
524 |
by simp |
|
525 |
with False have "n * x \<le> -1" |
|
526 |
by (metis linear minus_zero mult.commute mult.left_neutral mult_left_mono_neg neg_le_iff_le order_trans zero_le_one) |
|
527 |
then have "1 + n * x \<le> 0" |
|
528 |
by auto |
|
529 |
also have "... \<le> (1 + x) ^ n" |
|
530 |
using assms |
|
531 |
using zero_le_even_power by blast |
|
532 |
finally show ?thesis . |
|
533 |
qed |
|
534 |
||
535 |
corollary real_arch_pow: |
|
536 |
fixes x :: real |
|
537 |
assumes x: "1 < x" |
|
538 |
shows "\<exists>n. y < x^n" |
|
539 |
proof - |
|
540 |
from x have x0: "x - 1 > 0" |
|
541 |
by arith |
|
542 |
from reals_Archimedean3[OF x0, rule_format, of y] |
|
543 |
obtain n :: nat where n: "y < real n * (x - 1)" by metis |
|
544 |
from x0 have x00: "x- 1 \<ge> -1" by arith |
|
545 |
from Bernoulli_inequality[OF x00, of n] n |
|
546 |
have "y < x^n" by auto |
|
547 |
then show ?thesis by metis |
|
548 |
qed |
|
549 |
||
550 |
corollary real_arch_pow_inv: |
|
551 |
fixes x y :: real |
|
552 |
assumes y: "y > 0" |
|
553 |
and x1: "x < 1" |
|
554 |
shows "\<exists>n. x^n < y" |
|
555 |
proof (cases "x > 0") |
|
556 |
case True |
|
557 |
with x1 have ix: "1 < 1/x" by (simp add: field_simps) |
|
558 |
from real_arch_pow[OF ix, of "1/y"] |
|
559 |
obtain n where n: "1/y < (1/x)^n" by blast |
|
560 |
then show ?thesis using y \<open>x > 0\<close> |
|
561 |
by (auto simp add: field_simps) |
|
562 |
next |
|
563 |
case False |
|
564 |
with y x1 show ?thesis |
|
68069
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68062
diff
changeset
|
565 |
by (metis less_le_trans not_less power_one_right) |
63050 | 566 |
qed |
567 |
||
568 |
lemma forall_pos_mono: |
|
569 |
"(\<And>d e::real. d < e \<Longrightarrow> P d \<Longrightarrow> P e) \<Longrightarrow> |
|
570 |
(\<And>n::nat. n \<noteq> 0 \<Longrightarrow> P (inverse (real n))) \<Longrightarrow> (\<And>e. 0 < e \<Longrightarrow> P e)" |
|
571 |
by (metis real_arch_inverse) |
|
572 |
||
573 |
lemma forall_pos_mono_1: |
|
574 |
"(\<And>d e::real. d < e \<Longrightarrow> P d \<Longrightarrow> P e) \<Longrightarrow> |
|
575 |
(\<And>n. P (inverse (real (Suc n)))) \<Longrightarrow> 0 < e \<Longrightarrow> P e" |
|
576 |
apply (rule forall_pos_mono) |
|
577 |
apply auto |
|
578 |
apply (metis Suc_pred of_nat_Suc) |
|
579 |
done |
|
580 |
||
581 |
||
67962 | 582 |
subsection%unimportant \<open>Euclidean Spaces as Typeclass\<close> |
44133 | 583 |
|
50526
899c9c4e4a4c
Remove the indexed basis from the definition of euclidean spaces and only use the set of Basis vectors
hoelzl
parents:
50105
diff
changeset
|
584 |
lemma independent_Basis: "independent Basis" |
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
585 |
by (rule independent_Basis) |
50526
899c9c4e4a4c
Remove the indexed basis from the definition of euclidean spaces and only use the set of Basis vectors
hoelzl
parents:
50105
diff
changeset
|
586 |
|
53939 | 587 |
lemma span_Basis [simp]: "span Basis = UNIV" |
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
588 |
by (rule span_Basis) |
44133 | 589 |
|
50526
899c9c4e4a4c
Remove the indexed basis from the definition of euclidean spaces and only use the set of Basis vectors
hoelzl
parents:
50105
diff
changeset
|
590 |
lemma in_span_Basis: "x \<in> span Basis" |
899c9c4e4a4c
Remove the indexed basis from the definition of euclidean spaces and only use the set of Basis vectors
hoelzl
parents:
50105
diff
changeset
|
591 |
unfolding span_Basis .. |
899c9c4e4a4c
Remove the indexed basis from the definition of euclidean spaces and only use the set of Basis vectors
hoelzl
parents:
50105
diff
changeset
|
592 |
|
53406 | 593 |
|
67962 | 594 |
subsection%unimportant \<open>Linearity and Bilinearity continued\<close> |
44133 | 595 |
|
596 |
lemma linear_bounded: |
|
56444 | 597 |
fixes f :: "'a::euclidean_space \<Rightarrow> 'b::real_normed_vector" |
44133 | 598 |
assumes lf: "linear f" |
599 |
shows "\<exists>B. \<forall>x. norm (f x) \<le> B * norm x" |
|
53939 | 600 |
proof |
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
601 |
interpret linear f by fact |
50526
899c9c4e4a4c
Remove the indexed basis from the definition of euclidean spaces and only use the set of Basis vectors
hoelzl
parents:
50105
diff
changeset
|
602 |
let ?B = "\<Sum>b\<in>Basis. norm (f b)" |
53939 | 603 |
show "\<forall>x. norm (f x) \<le> ?B * norm x" |
604 |
proof |
|
53406 | 605 |
fix x :: 'a |
50526
899c9c4e4a4c
Remove the indexed basis from the definition of euclidean spaces and only use the set of Basis vectors
hoelzl
parents:
50105
diff
changeset
|
606 |
let ?g = "\<lambda>b. (x \<bullet> b) *\<^sub>R f b" |
899c9c4e4a4c
Remove the indexed basis from the definition of euclidean spaces and only use the set of Basis vectors
hoelzl
parents:
50105
diff
changeset
|
607 |
have "norm (f x) = norm (f (\<Sum>b\<in>Basis. (x \<bullet> b) *\<^sub>R b))" |
899c9c4e4a4c
Remove the indexed basis from the definition of euclidean spaces and only use the set of Basis vectors
hoelzl
parents:
50105
diff
changeset
|
608 |
unfolding euclidean_representation .. |
64267 | 609 |
also have "\<dots> = norm (sum ?g Basis)" |
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
610 |
by (simp add: sum scale) |
64267 | 611 |
finally have th0: "norm (f x) = norm (sum ?g Basis)" . |
64773
223b2ebdda79
Many new theorems, and more tidying
paulson <lp15@cam.ac.uk>
parents:
64267
diff
changeset
|
612 |
have th: "norm (?g i) \<le> norm (f i) * norm x" if "i \<in> Basis" for i |
223b2ebdda79
Many new theorems, and more tidying
paulson <lp15@cam.ac.uk>
parents:
64267
diff
changeset
|
613 |
proof - |
223b2ebdda79
Many new theorems, and more tidying
paulson <lp15@cam.ac.uk>
parents:
64267
diff
changeset
|
614 |
from Basis_le_norm[OF that, of x] |
53939 | 615 |
show "norm (?g i) \<le> norm (f i) * norm x" |
68069
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68062
diff
changeset
|
616 |
unfolding norm_scaleR by (metis mult.commute mult_left_mono norm_ge_zero) |
53939 | 617 |
qed |
64267 | 618 |
from sum_norm_le[of _ ?g, OF th] |
53939 | 619 |
show "norm (f x) \<le> ?B * norm x" |
64267 | 620 |
unfolding th0 sum_distrib_right by metis |
53939 | 621 |
qed |
44133 | 622 |
qed |
623 |
||
624 |
lemma linear_conv_bounded_linear: |
|
625 |
fixes f :: "'a::euclidean_space \<Rightarrow> 'b::real_normed_vector" |
|
626 |
shows "linear f \<longleftrightarrow> bounded_linear f" |
|
627 |
proof |
|
628 |
assume "linear f" |
|
53939 | 629 |
then interpret f: linear f . |
44133 | 630 |
show "bounded_linear f" |
631 |
proof |
|
632 |
have "\<exists>B. \<forall>x. norm (f x) \<le> B * norm x" |
|
60420 | 633 |
using \<open>linear f\<close> by (rule linear_bounded) |
49522 | 634 |
then show "\<exists>K. \<forall>x. norm (f x) \<le> norm x * K" |
57512
cc97b347b301
reduced name variants for assoc and commute on plus and mult
haftmann
parents:
57418
diff
changeset
|
635 |
by (simp add: mult.commute) |
44133 | 636 |
qed |
637 |
next |
|
638 |
assume "bounded_linear f" |
|
639 |
then interpret f: bounded_linear f . |
|
53939 | 640 |
show "linear f" .. |
641 |
qed |
|
642 |
||
61518
ff12606337e9
new lemmas about topology, etc., for Cauchy integral formula
paulson
parents:
61306
diff
changeset
|
643 |
lemmas linear_linear = linear_conv_bounded_linear[symmetric] |
ff12606337e9
new lemmas about topology, etc., for Cauchy integral formula
paulson
parents:
61306
diff
changeset
|
644 |
|
53939 | 645 |
lemma linear_bounded_pos: |
56444 | 646 |
fixes f :: "'a::euclidean_space \<Rightarrow> 'b::real_normed_vector" |
53939 | 647 |
assumes lf: "linear f" |
67982
7643b005b29a
various new results on measures, integrals, etc., and some simplified proofs
paulson <lp15@cam.ac.uk>
parents:
67962
diff
changeset
|
648 |
obtains B where "B > 0" "\<And>x. norm (f x) \<le> B * norm x" |
53939 | 649 |
proof - |
650 |
have "\<exists>B > 0. \<forall>x. norm (f x) \<le> norm x * B" |
|
651 |
using lf unfolding linear_conv_bounded_linear |
|
652 |
by (rule bounded_linear.pos_bounded) |
|
67982
7643b005b29a
various new results on measures, integrals, etc., and some simplified proofs
paulson <lp15@cam.ac.uk>
parents:
67962
diff
changeset
|
653 |
with that show ?thesis |
7643b005b29a
various new results on measures, integrals, etc., and some simplified proofs
paulson <lp15@cam.ac.uk>
parents:
67962
diff
changeset
|
654 |
by (auto simp: mult.commute) |
44133 | 655 |
qed |
656 |
||
67982
7643b005b29a
various new results on measures, integrals, etc., and some simplified proofs
paulson <lp15@cam.ac.uk>
parents:
67962
diff
changeset
|
657 |
lemma linear_invertible_bounded_below_pos: |
7643b005b29a
various new results on measures, integrals, etc., and some simplified proofs
paulson <lp15@cam.ac.uk>
parents:
67962
diff
changeset
|
658 |
fixes f :: "'a::real_normed_vector \<Rightarrow> 'b::euclidean_space" |
7643b005b29a
various new results on measures, integrals, etc., and some simplified proofs
paulson <lp15@cam.ac.uk>
parents:
67962
diff
changeset
|
659 |
assumes "linear f" "linear g" "g \<circ> f = id" |
7643b005b29a
various new results on measures, integrals, etc., and some simplified proofs
paulson <lp15@cam.ac.uk>
parents:
67962
diff
changeset
|
660 |
obtains B where "B > 0" "\<And>x. B * norm x \<le> norm(f x)" |
7643b005b29a
various new results on measures, integrals, etc., and some simplified proofs
paulson <lp15@cam.ac.uk>
parents:
67962
diff
changeset
|
661 |
proof - |
7643b005b29a
various new results on measures, integrals, etc., and some simplified proofs
paulson <lp15@cam.ac.uk>
parents:
67962
diff
changeset
|
662 |
obtain B where "B > 0" and B: "\<And>x. norm (g x) \<le> B * norm x" |
7643b005b29a
various new results on measures, integrals, etc., and some simplified proofs
paulson <lp15@cam.ac.uk>
parents:
67962
diff
changeset
|
663 |
using linear_bounded_pos [OF \<open>linear g\<close>] by blast |
7643b005b29a
various new results on measures, integrals, etc., and some simplified proofs
paulson <lp15@cam.ac.uk>
parents:
67962
diff
changeset
|
664 |
show thesis |
7643b005b29a
various new results on measures, integrals, etc., and some simplified proofs
paulson <lp15@cam.ac.uk>
parents:
67962
diff
changeset
|
665 |
proof |
7643b005b29a
various new results on measures, integrals, etc., and some simplified proofs
paulson <lp15@cam.ac.uk>
parents:
67962
diff
changeset
|
666 |
show "0 < 1/B" |
7643b005b29a
various new results on measures, integrals, etc., and some simplified proofs
paulson <lp15@cam.ac.uk>
parents:
67962
diff
changeset
|
667 |
by (simp add: \<open>B > 0\<close>) |
7643b005b29a
various new results on measures, integrals, etc., and some simplified proofs
paulson <lp15@cam.ac.uk>
parents:
67962
diff
changeset
|
668 |
show "1/B * norm x \<le> norm (f x)" for x |
7643b005b29a
various new results on measures, integrals, etc., and some simplified proofs
paulson <lp15@cam.ac.uk>
parents:
67962
diff
changeset
|
669 |
proof - |
7643b005b29a
various new results on measures, integrals, etc., and some simplified proofs
paulson <lp15@cam.ac.uk>
parents:
67962
diff
changeset
|
670 |
have "1/B * norm x = 1/B * norm (g (f x))" |
7643b005b29a
various new results on measures, integrals, etc., and some simplified proofs
paulson <lp15@cam.ac.uk>
parents:
67962
diff
changeset
|
671 |
using assms by (simp add: pointfree_idE) |
7643b005b29a
various new results on measures, integrals, etc., and some simplified proofs
paulson <lp15@cam.ac.uk>
parents:
67962
diff
changeset
|
672 |
also have "\<dots> \<le> norm (f x)" |
7643b005b29a
various new results on measures, integrals, etc., and some simplified proofs
paulson <lp15@cam.ac.uk>
parents:
67962
diff
changeset
|
673 |
using B [of "f x"] by (simp add: \<open>B > 0\<close> mult.commute pos_divide_le_eq) |
7643b005b29a
various new results on measures, integrals, etc., and some simplified proofs
paulson <lp15@cam.ac.uk>
parents:
67962
diff
changeset
|
674 |
finally show ?thesis . |
7643b005b29a
various new results on measures, integrals, etc., and some simplified proofs
paulson <lp15@cam.ac.uk>
parents:
67962
diff
changeset
|
675 |
qed |
7643b005b29a
various new results on measures, integrals, etc., and some simplified proofs
paulson <lp15@cam.ac.uk>
parents:
67962
diff
changeset
|
676 |
qed |
7643b005b29a
various new results on measures, integrals, etc., and some simplified proofs
paulson <lp15@cam.ac.uk>
parents:
67962
diff
changeset
|
677 |
qed |
7643b005b29a
various new results on measures, integrals, etc., and some simplified proofs
paulson <lp15@cam.ac.uk>
parents:
67962
diff
changeset
|
678 |
|
7643b005b29a
various new results on measures, integrals, etc., and some simplified proofs
paulson <lp15@cam.ac.uk>
parents:
67962
diff
changeset
|
679 |
lemma linear_inj_bounded_below_pos: |
7643b005b29a
various new results on measures, integrals, etc., and some simplified proofs
paulson <lp15@cam.ac.uk>
parents:
67962
diff
changeset
|
680 |
fixes f :: "'a::real_normed_vector \<Rightarrow> 'b::euclidean_space" |
7643b005b29a
various new results on measures, integrals, etc., and some simplified proofs
paulson <lp15@cam.ac.uk>
parents:
67962
diff
changeset
|
681 |
assumes "linear f" "inj f" |
7643b005b29a
various new results on measures, integrals, etc., and some simplified proofs
paulson <lp15@cam.ac.uk>
parents:
67962
diff
changeset
|
682 |
obtains B where "B > 0" "\<And>x. B * norm x \<le> norm(f x)" |
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
683 |
using linear_injective_left_inverse [OF assms] |
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
684 |
linear_invertible_bounded_below_pos assms by blast |
67982
7643b005b29a
various new results on measures, integrals, etc., and some simplified proofs
paulson <lp15@cam.ac.uk>
parents:
67962
diff
changeset
|
685 |
|
49522 | 686 |
lemma bounded_linearI': |
56444 | 687 |
fixes f ::"'a::euclidean_space \<Rightarrow> 'b::real_normed_vector" |
53406 | 688 |
assumes "\<And>x y. f (x + y) = f x + f y" |
689 |
and "\<And>c x. f (c *\<^sub>R x) = c *\<^sub>R f x" |
|
49522 | 690 |
shows "bounded_linear f" |
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
691 |
using assms linearI linear_conv_bounded_linear by blast |
44133 | 692 |
|
693 |
lemma bilinear_bounded: |
|
56444 | 694 |
fixes h :: "'m::euclidean_space \<Rightarrow> 'n::euclidean_space \<Rightarrow> 'k::real_normed_vector" |
44133 | 695 |
assumes bh: "bilinear h" |
696 |
shows "\<exists>B. \<forall>x y. norm (h x y) \<le> B * norm x * norm y" |
|
50526
899c9c4e4a4c
Remove the indexed basis from the definition of euclidean spaces and only use the set of Basis vectors
hoelzl
parents:
50105
diff
changeset
|
697 |
proof (clarify intro!: exI[of _ "\<Sum>i\<in>Basis. \<Sum>j\<in>Basis. norm (h i j)"]) |
53406 | 698 |
fix x :: 'm |
699 |
fix y :: 'n |
|
64267 | 700 |
have "norm (h x y) = norm (h (sum (\<lambda>i. (x \<bullet> i) *\<^sub>R i) Basis) (sum (\<lambda>i. (y \<bullet> i) *\<^sub>R i) Basis))" |
68069
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68062
diff
changeset
|
701 |
by (simp add: euclidean_representation) |
64267 | 702 |
also have "\<dots> = norm (sum (\<lambda> (i,j). h ((x \<bullet> i) *\<^sub>R i) ((y \<bullet> j) *\<^sub>R j)) (Basis \<times> Basis))" |
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
703 |
unfolding bilinear_sum[OF bh] .. |
50526
899c9c4e4a4c
Remove the indexed basis from the definition of euclidean spaces and only use the set of Basis vectors
hoelzl
parents:
50105
diff
changeset
|
704 |
finally have th: "norm (h x y) = \<dots>" . |
68069
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68062
diff
changeset
|
705 |
have "\<And>i j. \<lbrakk>i \<in> Basis; j \<in> Basis\<rbrakk> |
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68062
diff
changeset
|
706 |
\<Longrightarrow> \<bar>x \<bullet> i\<bar> * (\<bar>y \<bullet> j\<bar> * norm (h i j)) \<le> norm x * (norm y * norm (h i j))" |
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68062
diff
changeset
|
707 |
by (auto simp add: zero_le_mult_iff Basis_le_norm mult_mono) |
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68062
diff
changeset
|
708 |
then show "norm (h x y) \<le> (\<Sum>i\<in>Basis. \<Sum>j\<in>Basis. norm (h i j)) * norm x * norm y" |
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68062
diff
changeset
|
709 |
unfolding sum_distrib_right th sum.cartesian_product |
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68062
diff
changeset
|
710 |
by (clarsimp simp add: bilinear_rmul[OF bh] bilinear_lmul[OF bh] |
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68062
diff
changeset
|
711 |
field_simps simp del: scaleR_scaleR intro!: sum_norm_le) |
44133 | 712 |
qed |
713 |
||
714 |
lemma bilinear_conv_bounded_bilinear: |
|
715 |
fixes h :: "'a::euclidean_space \<Rightarrow> 'b::euclidean_space \<Rightarrow> 'c::real_normed_vector" |
|
716 |
shows "bilinear h \<longleftrightarrow> bounded_bilinear h" |
|
717 |
proof |
|
718 |
assume "bilinear h" |
|
719 |
show "bounded_bilinear h" |
|
720 |
proof |
|
53406 | 721 |
fix x y z |
722 |
show "h (x + y) z = h x z + h y z" |
|
60420 | 723 |
using \<open>bilinear h\<close> unfolding bilinear_def linear_iff by simp |
44133 | 724 |
next |
53406 | 725 |
fix x y z |
726 |
show "h x (y + z) = h x y + h x z" |
|
60420 | 727 |
using \<open>bilinear h\<close> unfolding bilinear_def linear_iff by simp |
44133 | 728 |
next |
68069
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68062
diff
changeset
|
729 |
show "h (scaleR r x) y = scaleR r (h x y)" "h x (scaleR r y) = scaleR r (h x y)" for r x y |
60420 | 730 |
using \<open>bilinear h\<close> unfolding bilinear_def linear_iff |
68069
36209dfb981e
tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents:
68062
diff
changeset
|
731 |
by simp_all |
44133 | 732 |
next |
733 |
have "\<exists>B. \<forall>x y. norm (h x y) \<le> B * norm x * norm y" |
|
60420 | 734 |
using \<open>bilinear h\<close> by (rule bilinear_bounded) |
49522 | 735 |
then show "\<exists>K. \<forall>x y. norm (h x y) \<le> norm x * norm y * K" |
57514
bdc2c6b40bf2
prefer ac_simps collections over separate name bindings for add and mult
haftmann
parents:
57512
diff
changeset
|
736 |
by (simp add: ac_simps) |
44133 | 737 |
qed |
738 |
next |
|
739 |
assume "bounded_bilinear h" |
|
740 |
then interpret h: bounded_bilinear h . |
|
741 |
show "bilinear h" |
|
742 |
unfolding bilinear_def linear_conv_bounded_linear |
|
49522 | 743 |
using h.bounded_linear_left h.bounded_linear_right by simp |
44133 | 744 |
qed |
745 |
||
53939 | 746 |
lemma bilinear_bounded_pos: |
56444 | 747 |
fixes h :: "'a::euclidean_space \<Rightarrow> 'b::euclidean_space \<Rightarrow> 'c::real_normed_vector" |
53939 | 748 |
assumes bh: "bilinear h" |
749 |
shows "\<exists>B > 0. \<forall>x y. norm (h x y) \<le> B * norm x * norm y" |
|
750 |
proof - |
|
751 |
have "\<exists>B > 0. \<forall>x y. norm (h x y) \<le> norm x * norm y * B" |
|
752 |
using bh [unfolded bilinear_conv_bounded_bilinear] |
|
753 |
by (rule bounded_bilinear.pos_bounded) |
|
754 |
then show ?thesis |
|
57514
bdc2c6b40bf2
prefer ac_simps collections over separate name bindings for add and mult
haftmann
parents:
57512
diff
changeset
|
755 |
by (simp only: ac_simps) |
53939 | 756 |
qed |
757 |
||
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
758 |
lemma bounded_linear_imp_has_derivative: "bounded_linear f \<Longrightarrow> (f has_derivative f) net" |
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
759 |
by (auto simp add: has_derivative_def linear_diff linear_linear linear_def |
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
760 |
dest: bounded_linear.linear) |
63469
b6900858dcb9
lots of new theorems about differentiable_on, retracts, ANRs, etc.
paulson <lp15@cam.ac.uk>
parents:
63170
diff
changeset
|
761 |
|
b6900858dcb9
lots of new theorems about differentiable_on, retracts, ANRs, etc.
paulson <lp15@cam.ac.uk>
parents:
63170
diff
changeset
|
762 |
lemma linear_imp_has_derivative: |
b6900858dcb9
lots of new theorems about differentiable_on, retracts, ANRs, etc.
paulson <lp15@cam.ac.uk>
parents:
63170
diff
changeset
|
763 |
fixes f :: "'a::euclidean_space \<Rightarrow> 'b::real_normed_vector" |
b6900858dcb9
lots of new theorems about differentiable_on, retracts, ANRs, etc.
paulson <lp15@cam.ac.uk>
parents:
63170
diff
changeset
|
764 |
shows "linear f \<Longrightarrow> (f has_derivative f) net" |
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
765 |
by (simp add: bounded_linear_imp_has_derivative linear_conv_bounded_linear) |
63469
b6900858dcb9
lots of new theorems about differentiable_on, retracts, ANRs, etc.
paulson <lp15@cam.ac.uk>
parents:
63170
diff
changeset
|
766 |
|
b6900858dcb9
lots of new theorems about differentiable_on, retracts, ANRs, etc.
paulson <lp15@cam.ac.uk>
parents:
63170
diff
changeset
|
767 |
lemma bounded_linear_imp_differentiable: "bounded_linear f \<Longrightarrow> f differentiable net" |
b6900858dcb9
lots of new theorems about differentiable_on, retracts, ANRs, etc.
paulson <lp15@cam.ac.uk>
parents:
63170
diff
changeset
|
768 |
using bounded_linear_imp_has_derivative differentiable_def by blast |
b6900858dcb9
lots of new theorems about differentiable_on, retracts, ANRs, etc.
paulson <lp15@cam.ac.uk>
parents:
63170
diff
changeset
|
769 |
|
b6900858dcb9
lots of new theorems about differentiable_on, retracts, ANRs, etc.
paulson <lp15@cam.ac.uk>
parents:
63170
diff
changeset
|
770 |
lemma linear_imp_differentiable: |
b6900858dcb9
lots of new theorems about differentiable_on, retracts, ANRs, etc.
paulson <lp15@cam.ac.uk>
parents:
63170
diff
changeset
|
771 |
fixes f :: "'a::euclidean_space \<Rightarrow> 'b::real_normed_vector" |
b6900858dcb9
lots of new theorems about differentiable_on, retracts, ANRs, etc.
paulson <lp15@cam.ac.uk>
parents:
63170
diff
changeset
|
772 |
shows "linear f \<Longrightarrow> f differentiable net" |
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
773 |
by (metis linear_imp_has_derivative differentiable_def) |
63469
b6900858dcb9
lots of new theorems about differentiable_on, retracts, ANRs, etc.
paulson <lp15@cam.ac.uk>
parents:
63170
diff
changeset
|
774 |
|
49522 | 775 |
|
68901 | 776 |
subsection%unimportant \<open>We continue\<close> |
44133 | 777 |
|
778 |
lemma independent_bound: |
|
53716 | 779 |
fixes S :: "'a::euclidean_space set" |
780 |
shows "independent S \<Longrightarrow> finite S \<and> card S \<le> DIM('a)" |
|
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
781 |
by (metis dim_subset_UNIV finiteI_independent dim_span_eq_card_independent) |
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
782 |
|
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
783 |
lemmas independent_imp_finite = finiteI_independent |
44133 | 784 |
|
61609
77b453bd616f
Coercion "real" now has type nat => real only and is no longer overloaded. Type class "real_of" is gone. Many duplicate theorems removed.
paulson <lp15@cam.ac.uk>
parents:
61520
diff
changeset
|
785 |
corollary |
60303 | 786 |
fixes S :: "'a::euclidean_space set" |
787 |
assumes "independent S" |
|
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
788 |
shows independent_card_le:"card S \<le> DIM('a)" |
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
789 |
using assms independent_bound by auto |
63075
60a42a4166af
lemmas about dimension, hyperplanes, span, etc.
paulson <lp15@cam.ac.uk>
parents:
63072
diff
changeset
|
790 |
|
49663 | 791 |
lemma dependent_biggerset: |
56444 | 792 |
fixes S :: "'a::euclidean_space set" |
793 |
shows "(finite S \<Longrightarrow> card S > DIM('a)) \<Longrightarrow> dependent S" |
|
44133 | 794 |
by (metis independent_bound not_less) |
795 |
||
60420 | 796 |
text \<open>Picking an orthogonal replacement for a spanning set.\<close> |
44133 | 797 |
|
53406 | 798 |
lemma vector_sub_project_orthogonal: |
799 |
fixes b x :: "'a::euclidean_space" |
|
800 |
shows "b \<bullet> (x - ((b \<bullet> x) / (b \<bullet> b)) *\<^sub>R b) = 0" |
|
44133 | 801 |
unfolding inner_simps by auto |
802 |
||
44528 | 803 |
lemma pairwise_orthogonal_insert: |
804 |
assumes "pairwise orthogonal S" |
|
49522 | 805 |
and "\<And>y. y \<in> S \<Longrightarrow> orthogonal x y" |
44528 | 806 |
shows "pairwise orthogonal (insert x S)" |
807 |
using assms unfolding pairwise_def |
|
808 |
by (auto simp add: orthogonal_commute) |
|
809 |
||
44133 | 810 |
lemma basis_orthogonal: |
53406 | 811 |
fixes B :: "'a::real_inner set" |
44133 | 812 |
assumes fB: "finite B" |
813 |
shows "\<exists>C. finite C \<and> card C \<le> card B \<and> span C = span B \<and> pairwise orthogonal C" |
|
814 |
(is " \<exists>C. ?P B C") |
|
49522 | 815 |
using fB |
816 |
proof (induct rule: finite_induct) |
|
817 |
case empty |
|
53406 | 818 |
then show ?case |
819 |
apply (rule exI[where x="{}"]) |
|
820 |
apply (auto simp add: pairwise_def) |
|
821 |
done |
|
44133 | 822 |
next |
49522 | 823 |
case (insert a B) |
60420 | 824 |
note fB = \<open>finite B\<close> and aB = \<open>a \<notin> B\<close> |
825 |
from \<open>\<exists>C. finite C \<and> card C \<le> card B \<and> span C = span B \<and> pairwise orthogonal C\<close> |
|
44133 | 826 |
obtain C where C: "finite C" "card C \<le> card B" |
827 |
"span C = span B" "pairwise orthogonal C" by blast |
|
64267 | 828 |
let ?a = "a - sum (\<lambda>x. (x \<bullet> a / (x \<bullet> x)) *\<^sub>R x) C" |
44133 | 829 |
let ?C = "insert ?a C" |
53406 | 830 |
from C(1) have fC: "finite ?C" |
831 |
by simp |
|
49522 | 832 |
from fB aB C(1,2) have cC: "card ?C \<le> card (insert a B)" |
833 |
by (simp add: card_insert_if) |
|
53406 | 834 |
{ |
835 |
fix x k |
|
49522 | 836 |
have th0: "\<And>(a::'a) b c. a - (b - c) = c + (a - b)" |
837 |
by (simp add: field_simps) |
|
44133 | 838 |
have "x - k *\<^sub>R (a - (\<Sum>x\<in>C. (x \<bullet> a / (x \<bullet> x)) *\<^sub>R x)) \<in> span C \<longleftrightarrow> x - k *\<^sub>R a \<in> span C" |
839 |
apply (simp only: scaleR_right_diff_distrib th0) |
|
840 |
apply (rule span_add_eq) |
|
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
841 |
apply (rule span_scale) |
64267 | 842 |
apply (rule span_sum) |
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
843 |
apply (rule span_scale) |
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
844 |
apply (rule span_base) |
49522 | 845 |
apply assumption |
53406 | 846 |
done |
847 |
} |
|
44133 | 848 |
then have SC: "span ?C = span (insert a B)" |
849 |
unfolding set_eq_iff span_breakdown_eq C(3)[symmetric] by auto |
|
53406 | 850 |
{ |
851 |
fix y |
|
852 |
assume yC: "y \<in> C" |
|
853 |
then have Cy: "C = insert y (C - {y})" |
|
854 |
by blast |
|
855 |
have fth: "finite (C - {y})" |
|
856 |
using C by simp |
|
44528 | 857 |
have "orthogonal ?a y" |
858 |
unfolding orthogonal_def |
|
64267 | 859 |
unfolding inner_diff inner_sum_left right_minus_eq |
860 |
unfolding sum.remove [OF \<open>finite C\<close> \<open>y \<in> C\<close>] |
|
44528 | 861 |
apply (clarsimp simp add: inner_commute[of y a]) |
64267 | 862 |
apply (rule sum.neutral) |
44528 | 863 |
apply clarsimp |
864 |
apply (rule C(4)[unfolded pairwise_def orthogonal_def, rule_format]) |
|
60420 | 865 |
using \<open>y \<in> C\<close> by auto |
53406 | 866 |
} |
60420 | 867 |
with \<open>pairwise orthogonal C\<close> have CPO: "pairwise orthogonal ?C" |
44528 | 868 |
by (rule pairwise_orthogonal_insert) |
53406 | 869 |
from fC cC SC CPO have "?P (insert a B) ?C" |
870 |
by blast |
|
44133 | 871 |
then show ?case by blast |
872 |
qed |
|
873 |
||
874 |
lemma orthogonal_basis_exists: |
|
875 |
fixes V :: "('a::euclidean_space) set" |
|
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
876 |
shows "\<exists>B. independent B \<and> B \<subseteq> span V \<and> V \<subseteq> span B \<and> |
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
877 |
(card B = dim V) \<and> pairwise orthogonal B" |
49663 | 878 |
proof - |
49522 | 879 |
from basis_exists[of V] obtain B where |
53406 | 880 |
B: "B \<subseteq> V" "independent B" "V \<subseteq> span B" "card B = dim V" |
68073
fad29d2a17a5
merged; resolved conflicts manually (esp. lemmas that have been moved from Linear_Algebra and Cartesian_Euclidean_Space)
immler
diff
changeset
|
881 |
by force |
53406 | 882 |
from B have fB: "finite B" "card B = dim V" |
883 |
using independent_bound by auto |
|
44133 | 884 |
from basis_orthogonal[OF fB(1)] obtain C where |
53406 | 885 |
C: "finite C" "card C \<le> card B" "span C = span B" "pairwise orthogonal C" |
886 |
by blast |
|
887 |
from C B have CSV: "C \<subseteq> span V" |
|
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
888 |
by (metis span_superset span_mono subset_trans) |
53406 | 889 |
from span_mono[OF B(3)] C have SVC: "span V \<subseteq> span C" |
890 |
by (simp add: span_span) |
|
44133 | 891 |
from card_le_dim_spanning[OF CSV SVC C(1)] C(2,3) fB |
53406 | 892 |
have iC: "independent C" |
44133 | 893 |
by (simp add: dim_span) |
53406 | 894 |
from C fB have "card C \<le> dim V" |
895 |
by simp |
|
896 |
moreover have "dim V \<le> card C" |
|
897 |
using span_card_ge_dim[OF CSV SVC C(1)] |
|
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
898 |
by simp |
53406 | 899 |
ultimately have CdV: "card C = dim V" |
900 |
using C(1) by simp |
|
901 |
from C B CSV CdV iC show ?thesis |
|
902 |
by auto |
|
44133 | 903 |
qed |
904 |
||
60420 | 905 |
text \<open>Low-dimensional subset is in a hyperplane (weak orthogonal complement).\<close> |
44133 | 906 |
|
49522 | 907 |
lemma span_not_univ_orthogonal: |
53406 | 908 |
fixes S :: "'a::euclidean_space set" |
44133 | 909 |
assumes sU: "span S \<noteq> UNIV" |
56444 | 910 |
shows "\<exists>a::'a. a \<noteq> 0 \<and> (\<forall>x \<in> span S. a \<bullet> x = 0)" |
49522 | 911 |
proof - |
53406 | 912 |
from sU obtain a where a: "a \<notin> span S" |
913 |
by blast |
|
44133 | 914 |
from orthogonal_basis_exists obtain B where |
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
915 |
B: "independent B" "B \<subseteq> span S" "S \<subseteq> span B" |
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
916 |
"card B = dim S" "pairwise orthogonal B" |
44133 | 917 |
by blast |
53406 | 918 |
from B have fB: "finite B" "card B = dim S" |
919 |
using independent_bound by auto |
|
44133 | 920 |
from span_mono[OF B(2)] span_mono[OF B(3)] |
53406 | 921 |
have sSB: "span S = span B" |
922 |
by (simp add: span_span) |
|
64267 | 923 |
let ?a = "a - sum (\<lambda>b. (a \<bullet> b / (b \<bullet> b)) *\<^sub>R b) B" |
924 |
have "sum (\<lambda>b. (a \<bullet> b / (b \<bullet> b)) *\<^sub>R b) B \<in> span S" |
|
44133 | 925 |
unfolding sSB |
64267 | 926 |
apply (rule span_sum) |
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
927 |
apply (rule span_scale) |
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
928 |
apply (rule span_base) |
49522 | 929 |
apply assumption |
930 |
done |
|
53406 | 931 |
with a have a0:"?a \<noteq> 0" |
932 |
by auto |
|
68058 | 933 |
have "?a \<bullet> x = 0" if "x\<in>span B" for x |
934 |
proof (rule span_induct [OF that]) |
|
49522 | 935 |
show "subspace {x. ?a \<bullet> x = 0}" |
936 |
by (auto simp add: subspace_def inner_add) |
|
937 |
next |
|
53406 | 938 |
{ |
939 |
fix x |
|
940 |
assume x: "x \<in> B" |
|
941 |
from x have B': "B = insert x (B - {x})" |
|
942 |
by blast |
|
943 |
have fth: "finite (B - {x})" |
|
944 |
using fB by simp |
|
44133 | 945 |
have "?a \<bullet> x = 0" |
53406 | 946 |
apply (subst B') |
947 |
using fB fth |
|
64267 | 948 |
unfolding sum_clauses(2)[OF fth] |
44133 | 949 |
apply simp unfolding inner_simps |
64267 | 950 |
apply (clarsimp simp add: inner_add inner_sum_left) |
951 |
apply (rule sum.neutral, rule ballI) |
|
63170 | 952 |
apply (simp only: inner_commute) |
49711 | 953 |
apply (auto simp add: x field_simps |
954 |
intro: B(5)[unfolded pairwise_def orthogonal_def, rule_format]) |
|
53406 | 955 |
done |
956 |
} |
|
68058 | 957 |
then show "?a \<bullet> x = 0" if "x \<in> B" for x |
958 |
using that by blast |
|
959 |
qed |
|
53406 | 960 |
with a0 show ?thesis |
961 |
unfolding sSB by (auto intro: exI[where x="?a"]) |
|
44133 | 962 |
qed |
963 |
||
964 |
lemma span_not_univ_subset_hyperplane: |
|
53406 | 965 |
fixes S :: "'a::euclidean_space set" |
966 |
assumes SU: "span S \<noteq> UNIV" |
|
44133 | 967 |
shows "\<exists> a. a \<noteq>0 \<and> span S \<subseteq> {x. a \<bullet> x = 0}" |
968 |
using span_not_univ_orthogonal[OF SU] by auto |
|
969 |
||
49663 | 970 |
lemma lowdim_subset_hyperplane: |
53406 | 971 |
fixes S :: "'a::euclidean_space set" |
44133 | 972 |
assumes d: "dim S < DIM('a)" |
56444 | 973 |
shows "\<exists>a::'a. a \<noteq> 0 \<and> span S \<subseteq> {x. a \<bullet> x = 0}" |
49522 | 974 |
proof - |
53406 | 975 |
{ |
976 |
assume "span S = UNIV" |
|
977 |
then have "dim (span S) = dim (UNIV :: ('a) set)" |
|
978 |
by simp |
|
979 |
then have "dim S = DIM('a)" |
|
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
980 |
by (metis Euclidean_Space.dim_UNIV dim_span) |
53406 | 981 |
with d have False by arith |
982 |
} |
|
983 |
then have th: "span S \<noteq> UNIV" |
|
984 |
by blast |
|
44133 | 985 |
from span_not_univ_subset_hyperplane[OF th] show ?thesis . |
986 |
qed |
|
987 |
||
988 |
lemma linear_eq_stdbasis: |
|
56444 | 989 |
fixes f :: "'a::euclidean_space \<Rightarrow> _" |
990 |
assumes lf: "linear f" |
|
49663 | 991 |
and lg: "linear g" |
68058 | 992 |
and fg: "\<And>b. b \<in> Basis \<Longrightarrow> f b = g b" |
44133 | 993 |
shows "f = g" |
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
994 |
using linear_eq_on_span[OF lf lg, of Basis] fg |
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
995 |
by auto |
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
996 |
|
44133 | 997 |
|
60420 | 998 |
text \<open>Similar results for bilinear functions.\<close> |
44133 | 999 |
|
1000 |
lemma bilinear_eq: |
|
1001 |
assumes bf: "bilinear f" |
|
49522 | 1002 |
and bg: "bilinear g" |
53406 | 1003 |
and SB: "S \<subseteq> span B" |
1004 |
and TC: "T \<subseteq> span C" |
|
68058 | 1005 |
and "x\<in>S" "y\<in>T" |
1006 |
and fg: "\<And>x y. \<lbrakk>x \<in> B; y\<in> C\<rbrakk> \<Longrightarrow> f x y = g x y" |
|
1007 |
shows "f x y = g x y" |
|
49663 | 1008 |
proof - |
44170
510ac30f44c0
make Multivariate_Analysis work with separate set type
huffman
parents:
44166
diff
changeset
|
1009 |
let ?P = "{x. \<forall>y\<in> span C. f x y = g x y}" |
44133 | 1010 |
from bf bg have sp: "subspace ?P" |
53600
8fda7ad57466
make 'linear' into a sublocale of 'bounded_linear';
huffman
parents:
53596
diff
changeset
|
1011 |
unfolding bilinear_def linear_iff subspace_def bf bg |
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
1012 |
by (auto simp add: span_zero bilinear_lzero[OF bf] bilinear_lzero[OF bg] |
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
1013 |
span_add Ball_def |
49663 | 1014 |
intro: bilinear_ladd[OF bf]) |
68058 | 1015 |
have sfg: "\<And>x. x \<in> B \<Longrightarrow> subspace {a. f x a = g x a}" |
44133 | 1016 |
apply (auto simp add: subspace_def) |
53600
8fda7ad57466
make 'linear' into a sublocale of 'bounded_linear';
huffman
parents:
53596
diff
changeset
|
1017 |
using bf bg unfolding bilinear_def linear_iff |
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
1018 |
apply (auto simp add: span_zero bilinear_rzero[OF bf] bilinear_rzero[OF bg] |
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
1019 |
span_add Ball_def |
49663 | 1020 |
intro: bilinear_ladd[OF bf]) |
49522 | 1021 |
done |
68058 | 1022 |
have "\<forall>y\<in> span C. f x y = g x y" if "x \<in> span B" for x |
1023 |
apply (rule span_induct [OF that sp]) |
|
68062 | 1024 |
using fg sfg span_induct by blast |
53406 | 1025 |
then show ?thesis |
68058 | 1026 |
using SB TC assms by auto |
44133 | 1027 |
qed |
1028 |
||
49522 | 1029 |
lemma bilinear_eq_stdbasis: |
53406 | 1030 |
fixes f :: "'a::euclidean_space \<Rightarrow> 'b::euclidean_space \<Rightarrow> _" |
44133 | 1031 |
assumes bf: "bilinear f" |
49522 | 1032 |
and bg: "bilinear g" |
68058 | 1033 |
and fg: "\<And>i j. i \<in> Basis \<Longrightarrow> j \<in> Basis \<Longrightarrow> f i j = g i j" |
44133 | 1034 |
shows "f = g" |
68074 | 1035 |
using bilinear_eq[OF bf bg equalityD2[OF span_Basis] equalityD2[OF span_Basis]] fg by blast |
49522 | 1036 |
|
69619
3f7d8e05e0f2
split off Convex.thy: material that does not require Topology_Euclidean_Space
immler
parents:
69600
diff
changeset
|
1037 |
|
60420 | 1038 |
subsection \<open>Infinity norm\<close> |
44133 | 1039 |
|
67962 | 1040 |
definition%important "infnorm (x::'a::euclidean_space) = Sup {\<bar>x \<bullet> b\<bar> |b. b \<in> Basis}" |
44133 | 1041 |
|
1042 |
lemma infnorm_set_image: |
|
53716 | 1043 |
fixes x :: "'a::euclidean_space" |
56444 | 1044 |
shows "{\<bar>x \<bullet> i\<bar> |i. i \<in> Basis} = (\<lambda>i. \<bar>x \<bullet> i\<bar>) ` Basis" |
50526
899c9c4e4a4c
Remove the indexed basis from the definition of euclidean spaces and only use the set of Basis vectors
hoelzl
parents:
50105
diff
changeset
|
1045 |
by blast |
44133 | 1046 |
|
53716 | 1047 |
lemma infnorm_Max: |
1048 |
fixes x :: "'a::euclidean_space" |
|
56444 | 1049 |
shows "infnorm x = Max ((\<lambda>i. \<bar>x \<bullet> i\<bar>) ` Basis)" |
62343
24106dc44def
prefer abbreviations for compound operators INFIMUM and SUPREMUM
haftmann
parents:
61973
diff
changeset
|
1050 |
by (simp add: infnorm_def infnorm_set_image cSup_eq_Max) |
51475
ebf9d4fd00ba
introduct the conditional_complete_lattice type class; generalize theorems about real Sup and Inf to it
hoelzl
parents:
50526
diff
changeset
|
1051 |
|
44133 | 1052 |
lemma infnorm_set_lemma: |
53716 | 1053 |
fixes x :: "'a::euclidean_space" |
56444 | 1054 |
shows "finite {\<bar>x \<bullet> i\<bar> |i. i \<in> Basis}" |
1055 |
and "{\<bar>x \<bullet> i\<bar> |i. i \<in> Basis} \<noteq> {}" |
|
44133 | 1056 |
unfolding infnorm_set_image |
1057 |
by auto |
|
1058 |
||
53406 | 1059 |
lemma infnorm_pos_le: |
1060 |
fixes x :: "'a::euclidean_space" |
|
1061 |
shows "0 \<le> infnorm x" |
|
51475
ebf9d4fd00ba
introduct the conditional_complete_lattice type class; generalize theorems about real Sup and Inf to it
hoelzl
parents:
50526
diff
changeset
|
1062 |
by (simp add: infnorm_Max Max_ge_iff ex_in_conv) |
44133 | 1063 |
|
53406 | 1064 |
lemma infnorm_triangle: |
1065 |
fixes x :: "'a::euclidean_space" |
|
1066 |
shows "infnorm (x + y) \<le> infnorm x + infnorm y" |
|
49522 | 1067 |
proof - |
51475
ebf9d4fd00ba
introduct the conditional_complete_lattice type class; generalize theorems about real Sup and Inf to it
hoelzl
parents:
50526
diff
changeset
|
1068 |
have *: "\<And>a b c d :: real. \<bar>a\<bar> \<le> c \<Longrightarrow> \<bar>b\<bar> \<le> d \<Longrightarrow> \<bar>a + b\<bar> \<le> c + d" |
ebf9d4fd00ba
introduct the conditional_complete_lattice type class; generalize theorems about real Sup and Inf to it
hoelzl
parents:
50526
diff
changeset
|
1069 |
by simp |
44133 | 1070 |
show ?thesis |
51475
ebf9d4fd00ba
introduct the conditional_complete_lattice type class; generalize theorems about real Sup and Inf to it
hoelzl
parents:
50526
diff
changeset
|
1071 |
by (auto simp: infnorm_Max inner_add_left intro!: *) |
44133 | 1072 |
qed |
1073 |
||
53406 | 1074 |
lemma infnorm_eq_0: |
1075 |
fixes x :: "'a::euclidean_space" |
|
1076 |
shows "infnorm x = 0 \<longleftrightarrow> x = 0" |
|
49522 | 1077 |
proof - |
51475
ebf9d4fd00ba
introduct the conditional_complete_lattice type class; generalize theorems about real Sup and Inf to it
hoelzl
parents:
50526
diff
changeset
|
1078 |
have "infnorm x \<le> 0 \<longleftrightarrow> x = 0" |
ebf9d4fd00ba
introduct the conditional_complete_lattice type class; generalize theorems about real Sup and Inf to it
hoelzl
parents:
50526
diff
changeset
|
1079 |
unfolding infnorm_Max by (simp add: euclidean_all_zero_iff) |
ebf9d4fd00ba
introduct the conditional_complete_lattice type class; generalize theorems about real Sup and Inf to it
hoelzl
parents:
50526
diff
changeset
|
1080 |
then show ?thesis |
ebf9d4fd00ba
introduct the conditional_complete_lattice type class; generalize theorems about real Sup and Inf to it
hoelzl
parents:
50526
diff
changeset
|
1081 |
using infnorm_pos_le[of x] by simp |
44133 | 1082 |
qed |
1083 |
||
1084 |
lemma infnorm_0: "infnorm 0 = 0" |
|
1085 |
by (simp add: infnorm_eq_0) |
|
1086 |
||
1087 |
lemma infnorm_neg: "infnorm (- x) = infnorm x" |
|
68062 | 1088 |
unfolding infnorm_def by simp |
44133 | 1089 |
|
1090 |
lemma infnorm_sub: "infnorm (x - y) = infnorm (y - x)" |
|
68062 | 1091 |
by (metis infnorm_neg minus_diff_eq) |
1092 |
||
1093 |
lemma absdiff_infnorm: "\<bar>infnorm x - infnorm y\<bar> \<le> infnorm (x - y)" |
|
49522 | 1094 |
proof - |
68062 | 1095 |
have *: "\<And>(nx::real) n ny. nx \<le> n + ny \<Longrightarrow> ny \<le> n + nx \<Longrightarrow> \<bar>nx - ny\<bar> \<le> n" |
44133 | 1096 |
by arith |
68062 | 1097 |
show ?thesis |
1098 |
proof (rule *) |
|
1099 |
from infnorm_triangle[of "x - y" " y"] infnorm_triangle[of "x - y" "-x"] |
|
1100 |
show "infnorm x \<le> infnorm (x - y) + infnorm y" "infnorm y \<le> infnorm (x - y) + infnorm x" |
|
1101 |
by (simp_all add: field_simps infnorm_neg) |
|
1102 |
qed |
|
44133 | 1103 |
qed |
1104 |
||
53406 | 1105 |
lemma real_abs_infnorm: "\<bar>infnorm x\<bar> = infnorm x" |
44133 | 1106 |
using infnorm_pos_le[of x] by arith |
1107 |
||
50526
899c9c4e4a4c
Remove the indexed basis from the definition of euclidean spaces and only use the set of Basis vectors
hoelzl
parents:
50105
diff
changeset
|
1108 |
lemma Basis_le_infnorm: |
53406 | 1109 |
fixes x :: "'a::euclidean_space" |
1110 |
shows "b \<in> Basis \<Longrightarrow> \<bar>x \<bullet> b\<bar> \<le> infnorm x" |
|
51475
ebf9d4fd00ba
introduct the conditional_complete_lattice type class; generalize theorems about real Sup and Inf to it
hoelzl
parents:
50526
diff
changeset
|
1111 |
by (simp add: infnorm_Max) |
44133 | 1112 |
|
56444 | 1113 |
lemma infnorm_mul: "infnorm (a *\<^sub>R x) = \<bar>a\<bar> * infnorm x" |
51475
ebf9d4fd00ba
introduct the conditional_complete_lattice type class; generalize theorems about real Sup and Inf to it
hoelzl
parents:
50526
diff
changeset
|
1114 |
unfolding infnorm_Max |
ebf9d4fd00ba
introduct the conditional_complete_lattice type class; generalize theorems about real Sup and Inf to it
hoelzl
parents:
50526
diff
changeset
|
1115 |
proof (safe intro!: Max_eqI) |
ebf9d4fd00ba
introduct the conditional_complete_lattice type class; generalize theorems about real Sup and Inf to it
hoelzl
parents:
50526
diff
changeset
|
1116 |
let ?B = "(\<lambda>i. \<bar>x \<bullet> i\<bar>) ` Basis" |
68062 | 1117 |
{ fix b :: 'a |
53406 | 1118 |
assume "b \<in> Basis" |
1119 |
then show "\<bar>a *\<^sub>R x \<bullet> b\<bar> \<le> \<bar>a\<bar> * Max ?B" |
|
1120 |
by (simp add: abs_mult mult_left_mono) |
|
1121 |
next |
|
1122 |
from Max_in[of ?B] obtain b where "b \<in> Basis" "Max ?B = \<bar>x \<bullet> b\<bar>" |
|
1123 |
by (auto simp del: Max_in) |
|
1124 |
then show "\<bar>a\<bar> * Max ((\<lambda>i. \<bar>x \<bullet> i\<bar>) ` Basis) \<in> (\<lambda>i. \<bar>a *\<^sub>R x \<bullet> i\<bar>) ` Basis" |
|
1125 |
by (intro image_eqI[where x=b]) (auto simp: abs_mult) |
|
1126 |
} |
|
51475
ebf9d4fd00ba
introduct the conditional_complete_lattice type class; generalize theorems about real Sup and Inf to it
hoelzl
parents:
50526
diff
changeset
|
1127 |
qed simp |
ebf9d4fd00ba
introduct the conditional_complete_lattice type class; generalize theorems about real Sup and Inf to it
hoelzl
parents:
50526
diff
changeset
|
1128 |
|
53406 | 1129 |
lemma infnorm_mul_lemma: "infnorm (a *\<^sub>R x) \<le> \<bar>a\<bar> * infnorm x" |
51475
ebf9d4fd00ba
introduct the conditional_complete_lattice type class; generalize theorems about real Sup and Inf to it
hoelzl
parents:
50526
diff
changeset
|
1130 |
unfolding infnorm_mul .. |
44133 | 1131 |
|
1132 |
lemma infnorm_pos_lt: "infnorm x > 0 \<longleftrightarrow> x \<noteq> 0" |
|
1133 |
using infnorm_pos_le[of x] infnorm_eq_0[of x] by arith |
|
1134 |
||
60420 | 1135 |
text \<open>Prove that it differs only up to a bound from Euclidean norm.\<close> |
44133 | 1136 |
|
1137 |
lemma infnorm_le_norm: "infnorm x \<le> norm x" |
|
51475
ebf9d4fd00ba
introduct the conditional_complete_lattice type class; generalize theorems about real Sup and Inf to it
hoelzl
parents:
50526
diff
changeset
|
1138 |
by (simp add: Basis_le_norm infnorm_Max) |
50526
899c9c4e4a4c
Remove the indexed basis from the definition of euclidean spaces and only use the set of Basis vectors
hoelzl
parents:
50105
diff
changeset
|
1139 |
|
53716 | 1140 |
lemma norm_le_infnorm: |
1141 |
fixes x :: "'a::euclidean_space" |
|
1142 |
shows "norm x \<le> sqrt DIM('a) * infnorm x" |
|
68062 | 1143 |
unfolding norm_eq_sqrt_inner id_def |
1144 |
proof (rule real_le_lsqrt[OF inner_ge_zero]) |
|
1145 |
show "sqrt DIM('a) * infnorm x \<ge> 0" |
|
44133 | 1146 |
by (simp add: zero_le_mult_iff infnorm_pos_le) |
68062 | 1147 |
have "x \<bullet> x \<le> (\<Sum>b\<in>Basis. x \<bullet> b * (x \<bullet> b))" |
1148 |
by (metis euclidean_inner order_refl) |
|
1149 |
also have "... \<le> DIM('a) * \<bar>infnorm x\<bar>\<^sup>2" |
|
1150 |
by (rule sum_bounded_above) (metis Basis_le_infnorm abs_le_square_iff power2_eq_square real_abs_infnorm) |
|
1151 |
also have "... \<le> (sqrt DIM('a) * infnorm x)\<^sup>2" |
|
1152 |
by (simp add: power_mult_distrib) |
|
1153 |
finally show "x \<bullet> x \<le> (sqrt DIM('a) * infnorm x)\<^sup>2" . |
|
44133 | 1154 |
qed |
1155 |
||
44646 | 1156 |
lemma tendsto_infnorm [tendsto_intros]: |
61973 | 1157 |
assumes "(f \<longlongrightarrow> a) F" |
1158 |
shows "((\<lambda>x. infnorm (f x)) \<longlongrightarrow> infnorm a) F" |
|
44646 | 1159 |
proof (rule tendsto_compose [OF LIM_I assms]) |
53406 | 1160 |
fix r :: real |
1161 |
assume "r > 0" |
|
49522 | 1162 |
then show "\<exists>s>0. \<forall>x. x \<noteq> a \<and> norm (x - a) < s \<longrightarrow> norm (infnorm x - infnorm a) < r" |
68062 | 1163 |
by (metis real_norm_def le_less_trans absdiff_infnorm infnorm_le_norm) |
44646 | 1164 |
qed |
1165 |
||
60420 | 1166 |
text \<open>Equality in Cauchy-Schwarz and triangle inequalities.\<close> |
44133 | 1167 |
|
53406 | 1168 |
lemma norm_cauchy_schwarz_eq: "x \<bullet> y = norm x * norm y \<longleftrightarrow> norm x *\<^sub>R y = norm y *\<^sub>R x" |
1169 |
(is "?lhs \<longleftrightarrow> ?rhs") |
|
68062 | 1170 |
proof (cases "x=0") |
1171 |
case True |
|
1172 |
then show ?thesis |
|
1173 |
by auto |
|
1174 |
next |
|
1175 |
case False |
|
1176 |
from inner_eq_zero_iff[of "norm y *\<^sub>R x - norm x *\<^sub>R y"] |
|
1177 |
have "?rhs \<longleftrightarrow> |
|
49522 | 1178 |
(norm y * (norm y * norm x * norm x - norm x * (x \<bullet> y)) - |
1179 |
norm x * (norm y * (y \<bullet> x) - norm x * norm y * norm y) = 0)" |
|
68062 | 1180 |
using False unfolding inner_simps |
1181 |
by (auto simp add: power2_norm_eq_inner[symmetric] power2_eq_square inner_commute field_simps) |
|
1182 |
also have "\<dots> \<longleftrightarrow> (2 * norm x * norm y * (norm x * norm y - x \<bullet> y) = 0)" |
|
1183 |
using False by (simp add: field_simps inner_commute) |
|
1184 |
also have "\<dots> \<longleftrightarrow> ?lhs" |
|
1185 |
using False by auto |
|
1186 |
finally show ?thesis by metis |
|
44133 | 1187 |
qed |
1188 |
||
1189 |
lemma norm_cauchy_schwarz_abs_eq: |
|
56444 | 1190 |
"\<bar>x \<bullet> y\<bar> = norm x * norm y \<longleftrightarrow> |
53716 | 1191 |
norm x *\<^sub>R y = norm y *\<^sub>R x \<or> norm x *\<^sub>R y = - norm y *\<^sub>R x" |
53406 | 1192 |
(is "?lhs \<longleftrightarrow> ?rhs") |
49522 | 1193 |
proof - |
56444 | 1194 |
have th: "\<And>(x::real) a. a \<ge> 0 \<Longrightarrow> \<bar>x\<bar> = a \<longleftrightarrow> x = a \<or> x = - a" |
53406 | 1195 |
by arith |
44133 | 1196 |
have "?rhs \<longleftrightarrow> norm x *\<^sub>R y = norm y *\<^sub>R x \<or> norm (- x) *\<^sub>R y = norm y *\<^sub>R (- x)" |
1197 |
by simp |
|
68062 | 1198 |
also have "\<dots> \<longleftrightarrow> (x \<bullet> y = norm x * norm y \<or> (- x) \<bullet> y = norm x * norm y)" |
44133 | 1199 |
unfolding norm_cauchy_schwarz_eq[symmetric] |
1200 |
unfolding norm_minus_cancel norm_scaleR .. |
|
1201 |
also have "\<dots> \<longleftrightarrow> ?lhs" |
|
53406 | 1202 |
unfolding th[OF mult_nonneg_nonneg, OF norm_ge_zero[of x] norm_ge_zero[of y]] inner_simps |
1203 |
by auto |
|
44133 | 1204 |
finally show ?thesis .. |
1205 |
qed |
|
1206 |
||
1207 |
lemma norm_triangle_eq: |
|
1208 |
fixes x y :: "'a::real_inner" |
|
53406 | 1209 |
shows "norm (x + y) = norm x + norm y \<longleftrightarrow> norm x *\<^sub>R y = norm y *\<^sub>R x" |
68062 | 1210 |
proof (cases "x = 0 \<or> y = 0") |
1211 |
case True |
|
1212 |
then show ?thesis |
|
1213 |
by force |
|
1214 |
next |
|
1215 |
case False |
|
1216 |
then have n: "norm x > 0" "norm y > 0" |
|
1217 |
by auto |
|
1218 |
have "norm (x + y) = norm x + norm y \<longleftrightarrow> (norm (x + y))\<^sup>2 = (norm x + norm y)\<^sup>2" |
|
1219 |
by simp |
|
1220 |
also have "\<dots> \<longleftrightarrow> norm x *\<^sub>R y = norm y *\<^sub>R x" |
|
1221 |
unfolding norm_cauchy_schwarz_eq[symmetric] |
|
1222 |
unfolding power2_norm_eq_inner inner_simps |
|
1223 |
by (simp add: power2_norm_eq_inner[symmetric] power2_eq_square inner_commute field_simps) |
|
1224 |
finally show ?thesis . |
|
44133 | 1225 |
qed |
1226 |
||
49522 | 1227 |
|
60420 | 1228 |
subsection \<open>Collinearity\<close> |
44133 | 1229 |
|
67962 | 1230 |
definition%important collinear :: "'a::real_vector set \<Rightarrow> bool" |
49522 | 1231 |
where "collinear S \<longleftrightarrow> (\<exists>u. \<forall>x \<in> S. \<forall> y \<in> S. \<exists>c. x - y = c *\<^sub>R u)" |
44133 | 1232 |
|
66287
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1233 |
lemma collinear_alt: |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1234 |
"collinear S \<longleftrightarrow> (\<exists>u v. \<forall>x \<in> S. \<exists>c. x = u + c *\<^sub>R v)" (is "?lhs = ?rhs") |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1235 |
proof |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1236 |
assume ?lhs |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1237 |
then show ?rhs |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1238 |
unfolding collinear_def by (metis Groups.add_ac(2) diff_add_cancel) |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1239 |
next |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1240 |
assume ?rhs |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1241 |
then obtain u v where *: "\<And>x. x \<in> S \<Longrightarrow> \<exists>c. x = u + c *\<^sub>R v" |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1242 |
by (auto simp: ) |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1243 |
have "\<exists>c. x - y = c *\<^sub>R v" if "x \<in> S" "y \<in> S" for x y |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1244 |
by (metis *[OF \<open>x \<in> S\<close>] *[OF \<open>y \<in> S\<close>] scaleR_left.diff add_diff_cancel_left) |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1245 |
then show ?lhs |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1246 |
using collinear_def by blast |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1247 |
qed |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1248 |
|
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1249 |
lemma collinear: |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1250 |
fixes S :: "'a::{perfect_space,real_vector} set" |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1251 |
shows "collinear S \<longleftrightarrow> (\<exists>u. u \<noteq> 0 \<and> (\<forall>x \<in> S. \<forall> y \<in> S. \<exists>c. x - y = c *\<^sub>R u))" |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1252 |
proof - |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1253 |
have "\<exists>v. v \<noteq> 0 \<and> (\<forall>x\<in>S. \<forall>y\<in>S. \<exists>c. x - y = c *\<^sub>R v)" |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1254 |
if "\<forall>x\<in>S. \<forall>y\<in>S. \<exists>c. x - y = c *\<^sub>R u" "u=0" for u |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1255 |
proof - |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1256 |
have "\<forall>x\<in>S. \<forall>y\<in>S. x = y" |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1257 |
using that by auto |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1258 |
moreover |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1259 |
obtain v::'a where "v \<noteq> 0" |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1260 |
using UNIV_not_singleton [of 0] by auto |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1261 |
ultimately have "\<forall>x\<in>S. \<forall>y\<in>S. \<exists>c. x - y = c *\<^sub>R v" |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1262 |
by auto |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1263 |
then show ?thesis |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1264 |
using \<open>v \<noteq> 0\<close> by blast |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1265 |
qed |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1266 |
then show ?thesis |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1267 |
apply (clarsimp simp: collinear_def) |
68072
493b818e8e10
added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents:
67982
diff
changeset
|
1268 |
by (metis scaleR_zero_right vector_fraction_eq_iff) |
66287
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1269 |
qed |
005a30862ed0
new material: Colinearity, convex sets, polytopes
paulson <lp15@cam.ac.uk>
parents:
65680
diff
changeset
|
1270 |
|
63881
b746b19197bd
lots of new results about topology, affine dimension etc
paulson <lp15@cam.ac.uk>
parents:
63680
diff
changeset
|
1271 |
lemma collinear_subset: "\<lbrakk>collinear T; S \<subseteq> T\<rbrakk> \<Longrightarrow> collinear S" |
b746b19197bd
lots of new results about topology, affine dimension etc
paulson <lp15@cam.ac.uk>
parents:
63680
diff
changeset
|
1272 |
by (meson collinear_def subsetCE) |
b746b19197bd
lots of new results about topology, affine dimension etc
paulson <lp15@cam.ac.uk>
parents:
63680
diff
changeset
|
1273 |
|
60762 | 1274 |
lemma collinear_empty [iff]: "collinear {}" |
53406 | 1275 |
by (simp add: collinear_def) |
44133 | 1276 |
|
60762 | 1277 |
lemma collinear_sing [iff]: "collinear {x}" |
44133 | 1278 |
by (simp add: collinear_def) |
1279 |
||
60762 | 1280 |
lemma collinear_2 [iff]: "collinear {x, y}" |
44133 | 1281 |
apply (simp add: collinear_def) |
1282 |
apply (rule exI[where x="x - y"]) |
|
68062 | 1283 |
by (metis minus_diff_eq scaleR_left.minus scaleR_one) |
44133 | 1284 |
|
56444 | 1285 |
lemma collinear_lemma: "collinear {0, x, y} \<longleftrightarrow> x = 0 \<or> y = 0 \<or> (\<exists>c. y = c *\<^sub>R x)" |
53406 | 1286 |
(is "?lhs \<longleftrightarrow> ?rhs") |
68062 | 1287 |
proof (cases "x = 0 \<or> y = 0") |
1288 |
case True |
|
1289 |
then show ?thesis |
|
1290 |
by (auto simp: insert_commute) |
|
1291 |
next |
|
1292 |
case False |
|
1293 |
show ?thesis |
|
1294 |
proof |
|
1295 |
assume h: "?lhs" |
|
1296 |
then obtain u where u: "\<forall> x\<in> {0,x,y}. \<forall>y\<in> {0,x,y}. \<exists>c. x - y = c *\<^sub>R u" |
|
1297 |
unfolding collinear_def by blast |
|
1298 |
from u[rule_format, of x 0] u[rule_format, of y 0] |
|
1299 |
obtain cx and cy where |
|
1300 |
cx: "x = cx *\<^sub>R u" and cy: "y = cy *\<^sub>R u" |
|
1301 |
by auto |
|
1302 |
from cx cy False have cx0: "cx \<noteq> 0" and cy0: "cy \<noteq> 0" by auto |
|
1303 |
let ?d = "cy / cx" |
|
1304 |
from cx cy cx0 have "y = ?d *\<^sub>R x" |
|
1305 |
by simp |
|
1306 |
then show ?rhs using False by blast |
|
1307 |
next |
|
1308 |
assume h: "?rhs" |
|
1309 |
then obtain c where c: "y = c *\<^sub>R x" |
|
1310 |
using False by blast |
|
1311 |
show ?lhs |
|
1312 |
unfolding collinear_def c |
|
1313 |
apply (rule exI[where x=x]) |
|
1314 |
apply auto |
|
1315 |
apply (rule exI[where x="- 1"], simp) |
|
1316 |
apply (rule exI[where x= "-c"], simp) |
|
44133 | 1317 |
apply (rule exI[where x=1], simp) |
68062 | 1318 |
apply (rule exI[where x="1 - c"], simp add: scaleR_left_diff_distrib) |
1319 |
apply (rule exI[where x="c - 1"], simp add: scaleR_left_diff_distrib) |
|
1320 |
done |
|
1321 |
qed |
|
44133 | 1322 |
qed |
1323 |
||
56444 | 1324 |
lemma norm_cauchy_schwarz_equal: "\<bar>x \<bullet> y\<bar> = norm x * norm y \<longleftrightarrow> collinear {0, x, y}" |
68062 | 1325 |
proof (cases "x=0") |
1326 |
case True |
|
1327 |
then show ?thesis |
|
1328 |
by (auto simp: insert_commute) |
|
1329 |
next |
|
1330 |
case False |
|
1331 |
then have nnz: "norm x \<noteq> 0" |
|
1332 |
by auto |
|
1333 |
show ?thesis |
|
1334 |
proof |
|
1335 |
assume "\<bar>x \<bullet> y\<bar> = norm x * norm y" |
|
1336 |
then show "collinear {0, x, y}" |
|
1337 |
unfolding norm_cauchy_schwarz_abs_eq collinear_lemma |
|
1338 |
by (meson eq_vector_fraction_iff nnz) |
|
1339 |
next |
|
1340 |
assume "collinear {0, x, y}" |
|
1341 |
with False show "\<bar>x \<bullet> y\<bar> = norm x * norm y" |
|
1342 |
unfolding norm_cauchy_schwarz_abs_eq collinear_lemma by (auto simp: abs_if) |
|
1343 |
qed |
|
1344 |
qed |
|
49522 | 1345 |
|
69675
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1346 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1347 |
subsection\<open>Properties of special hyperplanes\<close> |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1348 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1349 |
lemma subspace_hyperplane: "subspace {x. a \<bullet> x = 0}" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1350 |
by (simp add: subspace_def inner_right_distrib) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1351 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1352 |
lemma subspace_hyperplane2: "subspace {x. x \<bullet> a = 0}" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1353 |
by (simp add: inner_commute inner_right_distrib subspace_def) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1354 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1355 |
lemma special_hyperplane_span: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1356 |
fixes S :: "'n::euclidean_space set" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1357 |
assumes "k \<in> Basis" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1358 |
shows "{x. k \<bullet> x = 0} = span (Basis - {k})" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1359 |
proof - |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1360 |
have *: "x \<in> span (Basis - {k})" if "k \<bullet> x = 0" for x |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1361 |
proof - |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1362 |
have "x = (\<Sum>b\<in>Basis. (x \<bullet> b) *\<^sub>R b)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1363 |
by (simp add: euclidean_representation) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1364 |
also have "... = (\<Sum>b \<in> Basis - {k}. (x \<bullet> b) *\<^sub>R b)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1365 |
by (auto simp: sum.remove [of _ k] inner_commute assms that) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1366 |
finally have "x = (\<Sum>b\<in>Basis - {k}. (x \<bullet> b) *\<^sub>R b)" . |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1367 |
then show ?thesis |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1368 |
by (simp add: span_finite) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1369 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1370 |
show ?thesis |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1371 |
apply (rule span_subspace [symmetric]) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1372 |
using assms |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1373 |
apply (auto simp: inner_not_same_Basis intro: * subspace_hyperplane) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1374 |
done |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1375 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1376 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1377 |
lemma dim_special_hyperplane: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1378 |
fixes k :: "'n::euclidean_space" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1379 |
shows "k \<in> Basis \<Longrightarrow> dim {x. k \<bullet> x = 0} = DIM('n) - 1" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1380 |
apply (simp add: special_hyperplane_span) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1381 |
apply (rule dim_unique [OF subset_refl]) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1382 |
apply (auto simp: independent_substdbasis) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1383 |
apply (metis member_remove remove_def span_base) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1384 |
done |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1385 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1386 |
proposition dim_hyperplane: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1387 |
fixes a :: "'a::euclidean_space" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1388 |
assumes "a \<noteq> 0" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1389 |
shows "dim {x. a \<bullet> x = 0} = DIM('a) - 1" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1390 |
proof - |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1391 |
have span0: "span {x. a \<bullet> x = 0} = {x. a \<bullet> x = 0}" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1392 |
by (rule span_unique) (auto simp: subspace_hyperplane) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1393 |
then obtain B where "independent B" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1394 |
and Bsub: "B \<subseteq> {x. a \<bullet> x = 0}" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1395 |
and subspB: "{x. a \<bullet> x = 0} \<subseteq> span B" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1396 |
and card0: "(card B = dim {x. a \<bullet> x = 0})" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1397 |
and ortho: "pairwise orthogonal B" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1398 |
using orthogonal_basis_exists by metis |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1399 |
with assms have "a \<notin> span B" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1400 |
by (metis (mono_tags, lifting) span_eq inner_eq_zero_iff mem_Collect_eq span0) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1401 |
then have ind: "independent (insert a B)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1402 |
by (simp add: \<open>independent B\<close> independent_insert) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1403 |
have "finite B" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1404 |
using \<open>independent B\<close> independent_bound by blast |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1405 |
have "UNIV \<subseteq> span (insert a B)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1406 |
proof fix y::'a |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1407 |
obtain r z where z: "y = r *\<^sub>R a + z" "a \<bullet> z = 0" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1408 |
apply (rule_tac r="(a \<bullet> y) / (a \<bullet> a)" and z = "y - ((a \<bullet> y) / (a \<bullet> a)) *\<^sub>R a" in that) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1409 |
using assms |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1410 |
by (auto simp: algebra_simps) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1411 |
show "y \<in> span (insert a B)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1412 |
by (metis (mono_tags, lifting) z Bsub span_eq_iff |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1413 |
add_diff_cancel_left' mem_Collect_eq span0 span_breakdown_eq span_subspace subspB) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1414 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1415 |
then have dima: "DIM('a) = dim(insert a B)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1416 |
by (metis independent_Basis span_Basis dim_eq_card top.extremum_uniqueI) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1417 |
then show ?thesis |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1418 |
by (metis (mono_tags, lifting) Bsub Diff_insert_absorb \<open>a \<notin> span B\<close> ind card0 |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1419 |
card_Diff_singleton dim_span indep_card_eq_dim_span insertI1 subsetCE |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1420 |
subspB) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1421 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1422 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1423 |
lemma lowdim_eq_hyperplane: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1424 |
fixes S :: "'a::euclidean_space set" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1425 |
assumes "dim S = DIM('a) - 1" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1426 |
obtains a where "a \<noteq> 0" and "span S = {x. a \<bullet> x = 0}" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1427 |
proof - |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1428 |
have dimS: "dim S < DIM('a)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1429 |
by (simp add: assms) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1430 |
then obtain b where b: "b \<noteq> 0" "span S \<subseteq> {a. b \<bullet> a = 0}" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1431 |
using lowdim_subset_hyperplane [of S] by fastforce |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1432 |
show ?thesis |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1433 |
apply (rule that[OF b(1)]) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1434 |
apply (rule subspace_dim_equal) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1435 |
by (auto simp: assms b dim_hyperplane dim_span subspace_hyperplane |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1436 |
subspace_span) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1437 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1438 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1439 |
lemma dim_eq_hyperplane: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1440 |
fixes S :: "'n::euclidean_space set" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1441 |
shows "dim S = DIM('n) - 1 \<longleftrightarrow> (\<exists>a. a \<noteq> 0 \<and> span S = {x. a \<bullet> x = 0})" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1442 |
by (metis One_nat_def dim_hyperplane dim_span lowdim_eq_hyperplane) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1443 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1444 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1445 |
subsection\<open> Orthogonal bases, Gram-Schmidt process, and related theorems\<close> |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1446 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1447 |
lemma pairwise_orthogonal_independent: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1448 |
assumes "pairwise orthogonal S" and "0 \<notin> S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1449 |
shows "independent S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1450 |
proof - |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1451 |
have 0: "\<And>x y. \<lbrakk>x \<noteq> y; x \<in> S; y \<in> S\<rbrakk> \<Longrightarrow> x \<bullet> y = 0" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1452 |
using assms by (simp add: pairwise_def orthogonal_def) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1453 |
have "False" if "a \<in> S" and a: "a \<in> span (S - {a})" for a |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1454 |
proof - |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1455 |
obtain T U where "T \<subseteq> S - {a}" "a = (\<Sum>v\<in>T. U v *\<^sub>R v)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1456 |
using a by (force simp: span_explicit) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1457 |
then have "a \<bullet> a = a \<bullet> (\<Sum>v\<in>T. U v *\<^sub>R v)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1458 |
by simp |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1459 |
also have "... = 0" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1460 |
apply (simp add: inner_sum_right) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1461 |
apply (rule comm_monoid_add_class.sum.neutral) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1462 |
by (metis "0" DiffE \<open>T \<subseteq> S - {a}\<close> mult_not_zero singletonI subsetCE \<open>a \<in> S\<close>) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1463 |
finally show ?thesis |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1464 |
using \<open>0 \<notin> S\<close> \<open>a \<in> S\<close> by auto |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1465 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1466 |
then show ?thesis |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1467 |
by (force simp: dependent_def) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1468 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1469 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1470 |
lemma pairwise_orthogonal_imp_finite: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1471 |
fixes S :: "'a::euclidean_space set" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1472 |
assumes "pairwise orthogonal S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1473 |
shows "finite S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1474 |
proof - |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1475 |
have "independent (S - {0})" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1476 |
apply (rule pairwise_orthogonal_independent) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1477 |
apply (metis Diff_iff assms pairwise_def) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1478 |
by blast |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1479 |
then show ?thesis |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1480 |
by (meson independent_imp_finite infinite_remove) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1481 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1482 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1483 |
lemma subspace_orthogonal_to_vector: "subspace {y. orthogonal x y}" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1484 |
by (simp add: subspace_def orthogonal_clauses) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1485 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1486 |
lemma subspace_orthogonal_to_vectors: "subspace {y. \<forall>x \<in> S. orthogonal x y}" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1487 |
by (simp add: subspace_def orthogonal_clauses) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1488 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1489 |
lemma orthogonal_to_span: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1490 |
assumes a: "a \<in> span S" and x: "\<And>y. y \<in> S \<Longrightarrow> orthogonal x y" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1491 |
shows "orthogonal x a" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1492 |
by (metis a orthogonal_clauses(1,2,4) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1493 |
span_induct_alt x) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1494 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1495 |
proposition Gram_Schmidt_step: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1496 |
fixes S :: "'a::euclidean_space set" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1497 |
assumes S: "pairwise orthogonal S" and x: "x \<in> span S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1498 |
shows "orthogonal x (a - (\<Sum>b\<in>S. (b \<bullet> a / (b \<bullet> b)) *\<^sub>R b))" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1499 |
proof - |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1500 |
have "finite S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1501 |
by (simp add: S pairwise_orthogonal_imp_finite) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1502 |
have "orthogonal (a - (\<Sum>b\<in>S. (b \<bullet> a / (b \<bullet> b)) *\<^sub>R b)) x" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1503 |
if "x \<in> S" for x |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1504 |
proof - |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1505 |
have "a \<bullet> x = (\<Sum>y\<in>S. if y = x then y \<bullet> a else 0)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1506 |
by (simp add: \<open>finite S\<close> inner_commute sum.delta that) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1507 |
also have "... = (\<Sum>b\<in>S. b \<bullet> a * (b \<bullet> x) / (b \<bullet> b))" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1508 |
apply (rule sum.cong [OF refl], simp) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1509 |
by (meson S orthogonal_def pairwise_def that) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1510 |
finally show ?thesis |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1511 |
by (simp add: orthogonal_def algebra_simps inner_sum_left) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1512 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1513 |
then show ?thesis |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1514 |
using orthogonal_to_span orthogonal_commute x by blast |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1515 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1516 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1517 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1518 |
lemma orthogonal_extension_aux: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1519 |
fixes S :: "'a::euclidean_space set" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1520 |
assumes "finite T" "finite S" "pairwise orthogonal S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1521 |
shows "\<exists>U. pairwise orthogonal (S \<union> U) \<and> span (S \<union> U) = span (S \<union> T)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1522 |
using assms |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1523 |
proof (induction arbitrary: S) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1524 |
case empty then show ?case |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1525 |
by simp (metis sup_bot_right) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1526 |
next |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1527 |
case (insert a T) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1528 |
have 0: "\<And>x y. \<lbrakk>x \<noteq> y; x \<in> S; y \<in> S\<rbrakk> \<Longrightarrow> x \<bullet> y = 0" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1529 |
using insert by (simp add: pairwise_def orthogonal_def) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1530 |
define a' where "a' = a - (\<Sum>b\<in>S. (b \<bullet> a / (b \<bullet> b)) *\<^sub>R b)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1531 |
obtain U where orthU: "pairwise orthogonal (S \<union> insert a' U)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1532 |
and spanU: "span (insert a' S \<union> U) = span (insert a' S \<union> T)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1533 |
by (rule exE [OF insert.IH [of "insert a' S"]]) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1534 |
(auto simp: Gram_Schmidt_step a'_def insert.prems orthogonal_commute |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1535 |
pairwise_orthogonal_insert span_clauses) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1536 |
have orthS: "\<And>x. x \<in> S \<Longrightarrow> a' \<bullet> x = 0" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1537 |
apply (simp add: a'_def) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1538 |
using Gram_Schmidt_step [OF \<open>pairwise orthogonal S\<close>] |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1539 |
apply (force simp: orthogonal_def inner_commute span_superset [THEN subsetD]) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1540 |
done |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1541 |
have "span (S \<union> insert a' U) = span (insert a' (S \<union> T))" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1542 |
using spanU by simp |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1543 |
also have "... = span (insert a (S \<union> T))" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1544 |
apply (rule eq_span_insert_eq) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1545 |
apply (simp add: a'_def span_neg span_sum span_base span_mul) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1546 |
done |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1547 |
also have "... = span (S \<union> insert a T)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1548 |
by simp |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1549 |
finally show ?case |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1550 |
by (rule_tac x="insert a' U" in exI) (use orthU in auto) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1551 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1552 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1553 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1554 |
proposition orthogonal_extension: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1555 |
fixes S :: "'a::euclidean_space set" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1556 |
assumes S: "pairwise orthogonal S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1557 |
obtains U where "pairwise orthogonal (S \<union> U)" "span (S \<union> U) = span (S \<union> T)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1558 |
proof - |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1559 |
obtain B where "finite B" "span B = span T" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1560 |
using basis_subspace_exists [of "span T"] subspace_span by metis |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1561 |
with orthogonal_extension_aux [of B S] |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1562 |
obtain U where "pairwise orthogonal (S \<union> U)" "span (S \<union> U) = span (S \<union> B)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1563 |
using assms pairwise_orthogonal_imp_finite by auto |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1564 |
with \<open>span B = span T\<close> show ?thesis |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1565 |
by (rule_tac U=U in that) (auto simp: span_Un) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1566 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1567 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1568 |
corollary%unimportant orthogonal_extension_strong: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1569 |
fixes S :: "'a::euclidean_space set" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1570 |
assumes S: "pairwise orthogonal S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1571 |
obtains U where "U \<inter> (insert 0 S) = {}" "pairwise orthogonal (S \<union> U)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1572 |
"span (S \<union> U) = span (S \<union> T)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1573 |
proof - |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1574 |
obtain U where "pairwise orthogonal (S \<union> U)" "span (S \<union> U) = span (S \<union> T)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1575 |
using orthogonal_extension assms by blast |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1576 |
then show ?thesis |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1577 |
apply (rule_tac U = "U - (insert 0 S)" in that) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1578 |
apply blast |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1579 |
apply (force simp: pairwise_def) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1580 |
apply (metis Un_Diff_cancel Un_insert_left span_redundant span_zero) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1581 |
done |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1582 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1583 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1584 |
subsection\<open>Decomposing a vector into parts in orthogonal subspaces\<close> |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1585 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1586 |
text\<open>existence of orthonormal basis for a subspace.\<close> |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1587 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1588 |
lemma orthogonal_spanningset_subspace: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1589 |
fixes S :: "'a :: euclidean_space set" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1590 |
assumes "subspace S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1591 |
obtains B where "B \<subseteq> S" "pairwise orthogonal B" "span B = S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1592 |
proof - |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1593 |
obtain B where "B \<subseteq> S" "independent B" "S \<subseteq> span B" "card B = dim S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1594 |
using basis_exists by blast |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1595 |
with orthogonal_extension [of "{}" B] |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1596 |
show ?thesis |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1597 |
by (metis Un_empty_left assms pairwise_empty span_superset span_subspace that) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1598 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1599 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1600 |
lemma orthogonal_basis_subspace: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1601 |
fixes S :: "'a :: euclidean_space set" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1602 |
assumes "subspace S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1603 |
obtains B where "0 \<notin> B" "B \<subseteq> S" "pairwise orthogonal B" "independent B" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1604 |
"card B = dim S" "span B = S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1605 |
proof - |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1606 |
obtain B where "B \<subseteq> S" "pairwise orthogonal B" "span B = S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1607 |
using assms orthogonal_spanningset_subspace by blast |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1608 |
then show ?thesis |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1609 |
apply (rule_tac B = "B - {0}" in that) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1610 |
apply (auto simp: indep_card_eq_dim_span pairwise_subset pairwise_orthogonal_independent elim: pairwise_subset) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1611 |
done |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1612 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1613 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1614 |
proposition orthonormal_basis_subspace: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1615 |
fixes S :: "'a :: euclidean_space set" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1616 |
assumes "subspace S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1617 |
obtains B where "B \<subseteq> S" "pairwise orthogonal B" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1618 |
and "\<And>x. x \<in> B \<Longrightarrow> norm x = 1" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1619 |
and "independent B" "card B = dim S" "span B = S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1620 |
proof - |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1621 |
obtain B where "0 \<notin> B" "B \<subseteq> S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1622 |
and orth: "pairwise orthogonal B" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1623 |
and "independent B" "card B = dim S" "span B = S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1624 |
by (blast intro: orthogonal_basis_subspace [OF assms]) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1625 |
have 1: "(\<lambda>x. x /\<^sub>R norm x) ` B \<subseteq> S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1626 |
using \<open>span B = S\<close> span_superset span_mul by fastforce |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1627 |
have 2: "pairwise orthogonal ((\<lambda>x. x /\<^sub>R norm x) ` B)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1628 |
using orth by (force simp: pairwise_def orthogonal_clauses) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1629 |
have 3: "\<And>x. x \<in> (\<lambda>x. x /\<^sub>R norm x) ` B \<Longrightarrow> norm x = 1" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1630 |
by (metis (no_types, lifting) \<open>0 \<notin> B\<close> image_iff norm_sgn sgn_div_norm) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1631 |
have 4: "independent ((\<lambda>x. x /\<^sub>R norm x) ` B)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1632 |
by (metis "2" "3" norm_zero pairwise_orthogonal_independent zero_neq_one) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1633 |
have "inj_on (\<lambda>x. x /\<^sub>R norm x) B" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1634 |
proof |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1635 |
fix x y |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1636 |
assume "x \<in> B" "y \<in> B" "x /\<^sub>R norm x = y /\<^sub>R norm y" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1637 |
moreover have "\<And>i. i \<in> B \<Longrightarrow> norm (i /\<^sub>R norm i) = 1" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1638 |
using 3 by blast |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1639 |
ultimately show "x = y" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1640 |
by (metis norm_eq_1 orth orthogonal_clauses(7) orthogonal_commute orthogonal_def pairwise_def zero_neq_one) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1641 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1642 |
then have 5: "card ((\<lambda>x. x /\<^sub>R norm x) ` B) = dim S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1643 |
by (metis \<open>card B = dim S\<close> card_image) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1644 |
have 6: "span ((\<lambda>x. x /\<^sub>R norm x) ` B) = S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1645 |
by (metis "1" "4" "5" assms card_eq_dim independent_imp_finite span_subspace) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1646 |
show ?thesis |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1647 |
by (rule that [OF 1 2 3 4 5 6]) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1648 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1649 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1650 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1651 |
proposition%unimportant orthogonal_to_subspace_exists_gen: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1652 |
fixes S :: "'a :: euclidean_space set" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1653 |
assumes "span S \<subset> span T" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1654 |
obtains x where "x \<noteq> 0" "x \<in> span T" "\<And>y. y \<in> span S \<Longrightarrow> orthogonal x y" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1655 |
proof - |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1656 |
obtain B where "B \<subseteq> span S" and orthB: "pairwise orthogonal B" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1657 |
and "\<And>x. x \<in> B \<Longrightarrow> norm x = 1" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1658 |
and "independent B" "card B = dim S" "span B = span S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1659 |
by (rule orthonormal_basis_subspace [of "span S", OF subspace_span]) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1660 |
(auto simp: dim_span) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1661 |
with assms obtain u where spanBT: "span B \<subseteq> span T" and "u \<notin> span B" "u \<in> span T" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1662 |
by auto |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1663 |
obtain C where orthBC: "pairwise orthogonal (B \<union> C)" and spanBC: "span (B \<union> C) = span (B \<union> {u})" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1664 |
by (blast intro: orthogonal_extension [OF orthB]) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1665 |
show thesis |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1666 |
proof (cases "C \<subseteq> insert 0 B") |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1667 |
case True |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1668 |
then have "C \<subseteq> span B" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1669 |
using span_eq |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1670 |
by (metis span_insert_0 subset_trans) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1671 |
moreover have "u \<in> span (B \<union> C)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1672 |
using \<open>span (B \<union> C) = span (B \<union> {u})\<close> span_superset by force |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1673 |
ultimately show ?thesis |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1674 |
using True \<open>u \<notin> span B\<close> |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1675 |
by (metis Un_insert_left span_insert_0 sup.orderE) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1676 |
next |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1677 |
case False |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1678 |
then obtain x where "x \<in> C" "x \<noteq> 0" "x \<notin> B" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1679 |
by blast |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1680 |
then have "x \<in> span T" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1681 |
by (metis (no_types, lifting) Un_insert_right Un_upper2 \<open>u \<in> span T\<close> spanBT spanBC |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1682 |
\<open>u \<in> span T\<close> insert_subset span_superset span_mono |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1683 |
span_span subsetCE subset_trans sup_bot.comm_neutral) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1684 |
moreover have "orthogonal x y" if "y \<in> span B" for y |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1685 |
using that |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1686 |
proof (rule span_induct) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1687 |
show "subspace {a. orthogonal x a}" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1688 |
by (simp add: subspace_orthogonal_to_vector) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1689 |
show "\<And>b. b \<in> B \<Longrightarrow> orthogonal x b" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1690 |
by (metis Un_iff \<open>x \<in> C\<close> \<open>x \<notin> B\<close> orthBC pairwise_def) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1691 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1692 |
ultimately show ?thesis |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1693 |
using \<open>x \<noteq> 0\<close> that \<open>span B = span S\<close> by auto |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1694 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1695 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1696 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1697 |
corollary%unimportant orthogonal_to_subspace_exists: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1698 |
fixes S :: "'a :: euclidean_space set" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1699 |
assumes "dim S < DIM('a)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1700 |
obtains x where "x \<noteq> 0" "\<And>y. y \<in> span S \<Longrightarrow> orthogonal x y" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1701 |
proof - |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1702 |
have "span S \<subset> UNIV" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1703 |
by (metis (mono_tags) UNIV_I assms inner_eq_zero_iff less_le lowdim_subset_hyperplane |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1704 |
mem_Collect_eq top.extremum_strict top.not_eq_extremum) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1705 |
with orthogonal_to_subspace_exists_gen [of S UNIV] that show ?thesis |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1706 |
by (auto simp: span_UNIV) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1707 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1708 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1709 |
corollary%unimportant orthogonal_to_vector_exists: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1710 |
fixes x :: "'a :: euclidean_space" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1711 |
assumes "2 \<le> DIM('a)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1712 |
obtains y where "y \<noteq> 0" "orthogonal x y" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1713 |
proof - |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1714 |
have "dim {x} < DIM('a)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1715 |
using assms by auto |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1716 |
then show thesis |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1717 |
by (rule orthogonal_to_subspace_exists) (simp add: orthogonal_commute span_base that) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1718 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1719 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1720 |
proposition%unimportant orthogonal_subspace_decomp_exists: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1721 |
fixes S :: "'a :: euclidean_space set" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1722 |
obtains y z |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1723 |
where "y \<in> span S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1724 |
and "\<And>w. w \<in> span S \<Longrightarrow> orthogonal z w" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1725 |
and "x = y + z" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1726 |
proof - |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1727 |
obtain T where "0 \<notin> T" "T \<subseteq> span S" "pairwise orthogonal T" "independent T" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1728 |
"card T = dim (span S)" "span T = span S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1729 |
using orthogonal_basis_subspace subspace_span by blast |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1730 |
let ?a = "\<Sum>b\<in>T. (b \<bullet> x / (b \<bullet> b)) *\<^sub>R b" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1731 |
have orth: "orthogonal (x - ?a) w" if "w \<in> span S" for w |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1732 |
by (simp add: Gram_Schmidt_step \<open>pairwise orthogonal T\<close> \<open>span T = span S\<close> |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1733 |
orthogonal_commute that) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1734 |
show ?thesis |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1735 |
apply (rule_tac y = "?a" and z = "x - ?a" in that) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1736 |
apply (meson \<open>T \<subseteq> span S\<close> span_scale span_sum subsetCE) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1737 |
apply (fact orth, simp) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1738 |
done |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1739 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1740 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1741 |
lemma orthogonal_subspace_decomp_unique: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1742 |
fixes S :: "'a :: euclidean_space set" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1743 |
assumes "x + y = x' + y'" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1744 |
and ST: "x \<in> span S" "x' \<in> span S" "y \<in> span T" "y' \<in> span T" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1745 |
and orth: "\<And>a b. \<lbrakk>a \<in> S; b \<in> T\<rbrakk> \<Longrightarrow> orthogonal a b" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1746 |
shows "x = x' \<and> y = y'" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1747 |
proof - |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1748 |
have "x + y - y' = x'" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1749 |
by (simp add: assms) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1750 |
moreover have "\<And>a b. \<lbrakk>a \<in> span S; b \<in> span T\<rbrakk> \<Longrightarrow> orthogonal a b" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1751 |
by (meson orth orthogonal_commute orthogonal_to_span) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1752 |
ultimately have "0 = x' - x" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1753 |
by (metis (full_types) add_diff_cancel_left' ST diff_right_commute orthogonal_clauses(10) orthogonal_clauses(5) orthogonal_self) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1754 |
with assms show ?thesis by auto |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1755 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1756 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1757 |
lemma vector_in_orthogonal_spanningset: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1758 |
fixes a :: "'a::euclidean_space" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1759 |
obtains S where "a \<in> S" "pairwise orthogonal S" "span S = UNIV" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1760 |
by (metis UNIV_I Un_iff empty_iff insert_subset orthogonal_extension pairwise_def |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1761 |
pairwise_orthogonal_insert span_UNIV subsetI subset_antisym) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1762 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1763 |
lemma vector_in_orthogonal_basis: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1764 |
fixes a :: "'a::euclidean_space" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1765 |
assumes "a \<noteq> 0" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1766 |
obtains S where "a \<in> S" "0 \<notin> S" "pairwise orthogonal S" "independent S" "finite S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1767 |
"span S = UNIV" "card S = DIM('a)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1768 |
proof - |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1769 |
obtain S where S: "a \<in> S" "pairwise orthogonal S" "span S = UNIV" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1770 |
using vector_in_orthogonal_spanningset . |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1771 |
show thesis |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1772 |
proof |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1773 |
show "pairwise orthogonal (S - {0})" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1774 |
using pairwise_mono S(2) by blast |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1775 |
show "independent (S - {0})" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1776 |
by (simp add: \<open>pairwise orthogonal (S - {0})\<close> pairwise_orthogonal_independent) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1777 |
show "finite (S - {0})" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1778 |
using \<open>independent (S - {0})\<close> independent_imp_finite by blast |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1779 |
show "card (S - {0}) = DIM('a)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1780 |
using span_delete_0 [of S] S |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1781 |
by (simp add: \<open>independent (S - {0})\<close> indep_card_eq_dim_span dim_UNIV) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1782 |
qed (use S \<open>a \<noteq> 0\<close> in auto) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1783 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1784 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1785 |
lemma vector_in_orthonormal_basis: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1786 |
fixes a :: "'a::euclidean_space" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1787 |
assumes "norm a = 1" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1788 |
obtains S where "a \<in> S" "pairwise orthogonal S" "\<And>x. x \<in> S \<Longrightarrow> norm x = 1" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1789 |
"independent S" "card S = DIM('a)" "span S = UNIV" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1790 |
proof - |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1791 |
have "a \<noteq> 0" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1792 |
using assms by auto |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1793 |
then obtain S where "a \<in> S" "0 \<notin> S" "finite S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1794 |
and S: "pairwise orthogonal S" "independent S" "span S = UNIV" "card S = DIM('a)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1795 |
by (metis vector_in_orthogonal_basis) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1796 |
let ?S = "(\<lambda>x. x /\<^sub>R norm x) ` S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1797 |
show thesis |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1798 |
proof |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1799 |
show "a \<in> ?S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1800 |
using \<open>a \<in> S\<close> assms image_iff by fastforce |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1801 |
next |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1802 |
show "pairwise orthogonal ?S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1803 |
using \<open>pairwise orthogonal S\<close> by (auto simp: pairwise_def orthogonal_def) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1804 |
show "\<And>x. x \<in> (\<lambda>x. x /\<^sub>R norm x) ` S \<Longrightarrow> norm x = 1" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1805 |
using \<open>0 \<notin> S\<close> by (auto simp: divide_simps) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1806 |
then show "independent ?S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1807 |
by (metis \<open>pairwise orthogonal ((\<lambda>x. x /\<^sub>R norm x) ` S)\<close> norm_zero pairwise_orthogonal_independent zero_neq_one) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1808 |
have "inj_on (\<lambda>x. x /\<^sub>R norm x) S" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1809 |
unfolding inj_on_def |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1810 |
by (metis (full_types) S(1) \<open>0 \<notin> S\<close> inverse_nonzero_iff_nonzero norm_eq_zero orthogonal_scaleR orthogonal_self pairwise_def) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1811 |
then show "card ?S = DIM('a)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1812 |
by (simp add: card_image S) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1813 |
show "span ?S = UNIV" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1814 |
by (metis (no_types) \<open>0 \<notin> S\<close> \<open>finite S\<close> \<open>span S = UNIV\<close> |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1815 |
field_class.field_inverse_zero inverse_inverse_eq less_irrefl span_image_scale |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1816 |
zero_less_norm_iff) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1817 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1818 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1819 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1820 |
proposition dim_orthogonal_sum: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1821 |
fixes A :: "'a::euclidean_space set" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1822 |
assumes "\<And>x y. \<lbrakk>x \<in> A; y \<in> B\<rbrakk> \<Longrightarrow> x \<bullet> y = 0" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1823 |
shows "dim(A \<union> B) = dim A + dim B" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1824 |
proof - |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1825 |
have 1: "\<And>x y. \<lbrakk>x \<in> span A; y \<in> B\<rbrakk> \<Longrightarrow> x \<bullet> y = 0" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1826 |
by (erule span_induct [OF _ subspace_hyperplane2]; simp add: assms) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1827 |
have "\<And>x y. \<lbrakk>x \<in> span A; y \<in> span B\<rbrakk> \<Longrightarrow> x \<bullet> y = 0" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1828 |
using 1 by (simp add: span_induct [OF _ subspace_hyperplane]) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1829 |
then have 0: "\<And>x y. \<lbrakk>x \<in> span A; y \<in> span B\<rbrakk> \<Longrightarrow> x \<bullet> y = 0" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1830 |
by simp |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1831 |
have "dim(A \<union> B) = dim (span (A \<union> B))" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1832 |
by (simp add: dim_span) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1833 |
also have "span (A \<union> B) = ((\<lambda>(a, b). a + b) ` (span A \<times> span B))" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1834 |
by (auto simp add: span_Un image_def) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1835 |
also have "dim \<dots> = dim {x + y |x y. x \<in> span A \<and> y \<in> span B}" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1836 |
by (auto intro!: arg_cong [where f=dim]) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1837 |
also have "... = dim {x + y |x y. x \<in> span A \<and> y \<in> span B} + dim(span A \<inter> span B)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1838 |
by (auto simp: dest: 0) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1839 |
also have "... = dim (span A) + dim (span B)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1840 |
by (rule dim_sums_Int) (auto simp: subspace_span) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1841 |
also have "... = dim A + dim B" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1842 |
by (simp add: dim_span) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1843 |
finally show ?thesis . |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1844 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1845 |
|
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1846 |
lemma dim_subspace_orthogonal_to_vectors: |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1847 |
fixes A :: "'a::euclidean_space set" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1848 |
assumes "subspace A" "subspace B" "A \<subseteq> B" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1849 |
shows "dim {y \<in> B. \<forall>x \<in> A. orthogonal x y} + dim A = dim B" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1850 |
proof - |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1851 |
have "dim (span ({y \<in> B. \<forall>x\<in>A. orthogonal x y} \<union> A)) = dim (span B)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1852 |
proof (rule arg_cong [where f=dim, OF subset_antisym]) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1853 |
show "span ({y \<in> B. \<forall>x\<in>A. orthogonal x y} \<union> A) \<subseteq> span B" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1854 |
by (simp add: \<open>A \<subseteq> B\<close> Collect_restrict span_mono) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1855 |
next |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1856 |
have *: "x \<in> span ({y \<in> B. \<forall>x\<in>A. orthogonal x y} \<union> A)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1857 |
if "x \<in> B" for x |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1858 |
proof - |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1859 |
obtain y z where "x = y + z" "y \<in> span A" and orth: "\<And>w. w \<in> span A \<Longrightarrow> orthogonal z w" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1860 |
using orthogonal_subspace_decomp_exists [of A x] that by auto |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1861 |
have "y \<in> span B" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1862 |
using \<open>y \<in> span A\<close> assms(3) span_mono by blast |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1863 |
then have "z \<in> {a \<in> B. \<forall>x. x \<in> A \<longrightarrow> orthogonal x a}" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1864 |
apply simp |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1865 |
using \<open>x = y + z\<close> assms(1) assms(2) orth orthogonal_commute span_add_eq |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1866 |
span_eq_iff that by blast |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1867 |
then have z: "z \<in> span {y \<in> B. \<forall>x\<in>A. orthogonal x y}" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1868 |
by (meson span_superset subset_iff) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1869 |
then show ?thesis |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1870 |
apply (auto simp: span_Un image_def \<open>x = y + z\<close> \<open>y \<in> span A\<close>) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1871 |
using \<open>y \<in> span A\<close> add.commute by blast |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1872 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1873 |
show "span B \<subseteq> span ({y \<in> B. \<forall>x\<in>A. orthogonal x y} \<union> A)" |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1874 |
by (rule span_minimal) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1875 |
(auto intro: * span_minimal simp: subspace_span) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1876 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1877 |
then show ?thesis |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1878 |
by (metis (no_types, lifting) dim_orthogonal_sum dim_span mem_Collect_eq |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1879 |
orthogonal_commute orthogonal_def) |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1880 |
qed |
880ab0f27ddf
Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
immler
parents:
69674
diff
changeset
|
1881 |
|
54776
db890d9fc5c2
ordered_euclidean_space compatible with more standard pointwise ordering on products; conditionally complete lattice with product order
immler
parents:
54703
diff
changeset
|
1882 |
end |