Reorg, in particular Determinants as well as some linear algebra from Starlike and Change_Of_Vars
--- a/src/HOL/Analysis/Cartesian_Space.thy Wed Jan 16 16:50:35 2019 -0500
+++ b/src/HOL/Analysis/Cartesian_Space.thy Wed Jan 16 18:14:02 2019 -0500
@@ -930,4 +930,492 @@
lemma%unimportant const_vector_cart:"((\<chi> i. d)::real^'n) = (\<Sum>i\<in>Basis. d *\<^sub>R i)"
by (rule vector_cart)
+subsection%unimportant \<open>Explicit formulas for low dimensions\<close>
+
+lemma%unimportant prod_neutral_const: "prod f {(1::nat)..1} = f 1"
+ by simp
+
+lemma%unimportant prod_2: "prod f {(1::nat)..2} = f 1 * f 2"
+ by (simp add: eval_nat_numeral atLeastAtMostSuc_conv mult.commute)
+
+lemma%unimportant prod_3: "prod f {(1::nat)..3} = f 1 * f 2 * f 3"
+ by (simp add: eval_nat_numeral atLeastAtMostSuc_conv mult.commute)
+
+
+subsection%important \<open>Orthogonality of a matrix\<close>
+
+definition%important "orthogonal_matrix (Q::'a::semiring_1^'n^'n) \<longleftrightarrow>
+ transpose Q ** Q = mat 1 \<and> Q ** transpose Q = mat 1"
+
+lemma%unimportant orthogonal_matrix: "orthogonal_matrix (Q:: real ^'n^'n) \<longleftrightarrow> transpose Q ** Q = mat 1"
+ by (metis matrix_left_right_inverse orthogonal_matrix_def)
+
+lemma%unimportant orthogonal_matrix_id: "orthogonal_matrix (mat 1 :: _^'n^'n)"
+ by (simp add: orthogonal_matrix_def)
+
+lemma%unimportant orthogonal_matrix_mul:
+ fixes A :: "real ^'n^'n"
+ assumes "orthogonal_matrix A" "orthogonal_matrix B"
+ shows "orthogonal_matrix(A ** B)"
+ using assms
+ by (simp add: orthogonal_matrix matrix_transpose_mul matrix_left_right_inverse matrix_mul_assoc)
+
+lemma%important orthogonal_transformation_matrix:
+ fixes f:: "real^'n \<Rightarrow> real^'n"
+ shows "orthogonal_transformation f \<longleftrightarrow> linear f \<and> orthogonal_matrix(matrix f)"
+ (is "?lhs \<longleftrightarrow> ?rhs")
+proof%unimportant -
+ let ?mf = "matrix f"
+ let ?ot = "orthogonal_transformation f"
+ let ?U = "UNIV :: 'n set"
+ have fU: "finite ?U" by simp
+ let ?m1 = "mat 1 :: real ^'n^'n"
+ {
+ assume ot: ?ot
+ from ot have lf: "Vector_Spaces.linear (*s) (*s) f" and fd: "\<And>v w. f v \<bullet> f w = v \<bullet> w"
+ unfolding orthogonal_transformation_def orthogonal_matrix linear_def scalar_mult_eq_scaleR
+ by blast+
+ {
+ fix i j
+ let ?A = "transpose ?mf ** ?mf"
+ have th0: "\<And>b (x::'a::comm_ring_1). (if b then 1 else 0)*x = (if b then x else 0)"
+ "\<And>b (x::'a::comm_ring_1). x*(if b then 1 else 0) = (if b then x else 0)"
+ by simp_all
+ from fd[of "axis i 1" "axis j 1",
+ simplified matrix_works[OF lf, symmetric] dot_matrix_vector_mul]
+ have "?A$i$j = ?m1 $ i $ j"
+ by (simp add: inner_vec_def matrix_matrix_mult_def columnvector_def rowvector_def
+ th0 sum.delta[OF fU] mat_def axis_def)
+ }
+ then have "orthogonal_matrix ?mf"
+ unfolding orthogonal_matrix
+ by vector
+ with lf have ?rhs
+ unfolding linear_def scalar_mult_eq_scaleR
+ by blast
+ }
+ moreover
+ {
+ assume lf: "Vector_Spaces.linear (*s) (*s) f" and om: "orthogonal_matrix ?mf"
+ from lf om have ?lhs
+ unfolding orthogonal_matrix_def norm_eq orthogonal_transformation
+ apply (simp only: matrix_works[OF lf, symmetric] dot_matrix_vector_mul)
+ apply (simp add: dot_matrix_product linear_def scalar_mult_eq_scaleR)
+ done
+ }
+ ultimately show ?thesis
+ by (auto simp: linear_def scalar_mult_eq_scaleR)
+qed
+
+
+subsection%important \<open> We can find an orthogonal matrix taking any unit vector to any other\<close>
+
+lemma%unimportant orthogonal_matrix_transpose [simp]:
+ "orthogonal_matrix(transpose A) \<longleftrightarrow> orthogonal_matrix A"
+ by (auto simp: orthogonal_matrix_def)
+
+lemma%unimportant orthogonal_matrix_orthonormal_columns:
+ fixes A :: "real^'n^'n"
+ shows "orthogonal_matrix A \<longleftrightarrow>
+ (\<forall>i. norm(column i A) = 1) \<and>
+ (\<forall>i j. i \<noteq> j \<longrightarrow> orthogonal (column i A) (column j A))"
+ by (auto simp: orthogonal_matrix matrix_mult_transpose_dot_column vec_eq_iff mat_def norm_eq_1 orthogonal_def)
+
+lemma%unimportant orthogonal_matrix_orthonormal_rows:
+ fixes A :: "real^'n^'n"
+ shows "orthogonal_matrix A \<longleftrightarrow>
+ (\<forall>i. norm(row i A) = 1) \<and>
+ (\<forall>i j. i \<noteq> j \<longrightarrow> orthogonal (row i A) (row j A))"
+ using orthogonal_matrix_orthonormal_columns [of "transpose A"] by simp
+
+lemma%important orthogonal_matrix_exists_basis:
+ fixes a :: "real^'n"
+ assumes "norm a = 1"
+ obtains A where "orthogonal_matrix A" "A *v (axis k 1) = a"
+proof%unimportant -
+ obtain S where "a \<in> S" "pairwise orthogonal S" and noS: "\<And>x. x \<in> S \<Longrightarrow> norm x = 1"
+ and "independent S" "card S = CARD('n)" "span S = UNIV"
+ using vector_in_orthonormal_basis assms by force
+ then obtain f0 where "bij_betw f0 (UNIV::'n set) S"
+ by (metis finite_class.finite_UNIV finite_same_card_bij finiteI_independent)
+ then obtain f where f: "bij_betw f (UNIV::'n set) S" and a: "a = f k"
+ using bij_swap_iff [of k "inv f0 a" f0]
+ by (metis UNIV_I \<open>a \<in> S\<close> bij_betw_inv_into_right bij_betw_swap_iff swap_apply(1))
+ show thesis
+ proof
+ have [simp]: "\<And>i. norm (f i) = 1"
+ using bij_betwE [OF \<open>bij_betw f UNIV S\<close>] by (blast intro: noS)
+ have [simp]: "\<And>i j. i \<noteq> j \<Longrightarrow> orthogonal (f i) (f j)"
+ using \<open>pairwise orthogonal S\<close> \<open>bij_betw f UNIV S\<close>
+ by (auto simp: pairwise_def bij_betw_def inj_on_def)
+ show "orthogonal_matrix (\<chi> i j. f j $ i)"
+ by (simp add: orthogonal_matrix_orthonormal_columns column_def)
+ show "(\<chi> i j. f j $ i) *v axis k 1 = a"
+ by (simp add: matrix_vector_mult_def axis_def a if_distrib cong: if_cong)
+ qed
+qed
+
+lemma%unimportant orthogonal_transformation_exists_1:
+ fixes a b :: "real^'n"
+ assumes "norm a = 1" "norm b = 1"
+ obtains f where "orthogonal_transformation f" "f a = b"
+proof%unimportant -
+ obtain k::'n where True
+ by simp
+ obtain A B where AB: "orthogonal_matrix A" "orthogonal_matrix B" and eq: "A *v (axis k 1) = a" "B *v (axis k 1) = b"
+ using orthogonal_matrix_exists_basis assms by metis
+ let ?f = "\<lambda>x. (B ** transpose A) *v x"
+ show thesis
+ proof
+ show "orthogonal_transformation ?f"
+ by (subst orthogonal_transformation_matrix)
+ (auto simp: AB orthogonal_matrix_mul)
+ next
+ show "?f a = b"
+ using \<open>orthogonal_matrix A\<close> unfolding orthogonal_matrix_def
+ by (metis eq matrix_mul_rid matrix_vector_mul_assoc)
+ qed
+qed
+
+lemma%important orthogonal_transformation_exists:
+ fixes a b :: "real^'n"
+ assumes "norm a = norm b"
+ obtains f where "orthogonal_transformation f" "f a = b"
+proof%unimportant (cases "a = 0 \<or> b = 0")
+ case True
+ with assms show ?thesis
+ using that by force
+next
+ case False
+ then obtain f where f: "orthogonal_transformation f" and eq: "f (a /\<^sub>R norm a) = (b /\<^sub>R norm b)"
+ by (auto intro: orthogonal_transformation_exists_1 [of "a /\<^sub>R norm a" "b /\<^sub>R norm b"])
+ show ?thesis
+ proof
+ interpret linear f
+ using f by (simp add: orthogonal_transformation_linear)
+ have "f a /\<^sub>R norm a = f (a /\<^sub>R norm a)"
+ by (simp add: scale)
+ also have "\<dots> = b /\<^sub>R norm a"
+ by (simp add: eq assms [symmetric])
+ finally show "f a = b"
+ using False by auto
+ qed (use f in auto)
+qed
+
+
+subsection%important \<open>Linearity of scaling, and hence isometry, that preserves origin\<close>
+
+lemma%important scaling_linear:
+ fixes f :: "'a::real_inner \<Rightarrow> 'a::real_inner"
+ assumes f0: "f 0 = 0"
+ and fd: "\<forall>x y. dist (f x) (f y) = c * dist x y"
+ shows "linear f"
+proof%unimportant -
+ {
+ fix v w
+ have "norm (f x) = c * norm x" for x
+ by (metis dist_0_norm f0 fd)
+ then have "f v \<bullet> f w = c\<^sup>2 * (v \<bullet> w)"
+ unfolding dot_norm_neg dist_norm[symmetric]
+ by (simp add: fd power2_eq_square field_simps)
+ }
+ then show ?thesis
+ unfolding linear_iff vector_eq[where 'a="'a"] scalar_mult_eq_scaleR
+ by (simp add: inner_add field_simps)
+qed
+
+lemma%unimportant isometry_linear:
+ "f (0::'a::real_inner) = (0::'a) \<Longrightarrow> \<forall>x y. dist(f x) (f y) = dist x y \<Longrightarrow> linear f"
+ by (rule scaling_linear[where c=1]) simp_all
+
+text \<open>Hence another formulation of orthogonal transformation\<close>
+
+lemma%important orthogonal_transformation_isometry:
+ "orthogonal_transformation f \<longleftrightarrow> f(0::'a::real_inner) = (0::'a) \<and> (\<forall>x y. dist(f x) (f y) = dist x y)"
+ unfolding orthogonal_transformation
+ apply (auto simp: linear_0 isometry_linear)
+ apply (metis (no_types, hide_lams) dist_norm linear_diff)
+ by (metis dist_0_norm)
+
+
+subsection%important \<open>Can extend an isometry from unit sphere\<close>
+
+lemma%important isometry_sphere_extend:
+ fixes f:: "'a::real_inner \<Rightarrow> 'a"
+ assumes f1: "\<And>x. norm x = 1 \<Longrightarrow> norm (f x) = 1"
+ and fd1: "\<And>x y. \<lbrakk>norm x = 1; norm y = 1\<rbrakk> \<Longrightarrow> dist (f x) (f y) = dist x y"
+ shows "\<exists>g. orthogonal_transformation g \<and> (\<forall>x. norm x = 1 \<longrightarrow> g x = f x)"
+proof%unimportant -
+ {
+ fix x y x' y' u v u' v' :: "'a"
+ assume H: "x = norm x *\<^sub>R u" "y = norm y *\<^sub>R v"
+ "x' = norm x *\<^sub>R u'" "y' = norm y *\<^sub>R v'"
+ and J: "norm u = 1" "norm u' = 1" "norm v = 1" "norm v' = 1" "norm(u' - v') = norm(u - v)"
+ then have *: "u \<bullet> v = u' \<bullet> v' + v' \<bullet> u' - v \<bullet> u "
+ by (simp add: norm_eq norm_eq_1 inner_add inner_diff)
+ have "norm (norm x *\<^sub>R u' - norm y *\<^sub>R v') = norm (norm x *\<^sub>R u - norm y *\<^sub>R v)"
+ using J by (simp add: norm_eq norm_eq_1 inner_diff * field_simps)
+ then have "norm(x' - y') = norm(x - y)"
+ using H by metis
+ }
+ note norm_eq = this
+ let ?g = "\<lambda>x. if x = 0 then 0 else norm x *\<^sub>R f (x /\<^sub>R norm x)"
+ have thfg: "?g x = f x" if "norm x = 1" for x
+ using that by auto
+ have thd: "dist (?g x) (?g y) = dist x y" for x y
+ proof (cases "x=0 \<or> y=0")
+ case False
+ show "dist (?g x) (?g y) = dist x y"
+ unfolding dist_norm
+ proof (rule norm_eq)
+ show "x = norm x *\<^sub>R (x /\<^sub>R norm x)" "y = norm y *\<^sub>R (y /\<^sub>R norm y)"
+ "norm (f (x /\<^sub>R norm x)) = 1" "norm (f (y /\<^sub>R norm y)) = 1"
+ using False f1 by auto
+ qed (use False in \<open>auto simp: field_simps intro: f1 fd1[unfolded dist_norm]\<close>)
+ qed (auto simp: f1)
+ show ?thesis
+ unfolding orthogonal_transformation_isometry
+ by (rule exI[where x= ?g]) (metis thfg thd)
+qed
+
+subsection%important\<open>Induction on matrix row operations\<close>
+
+lemma%unimportant induct_matrix_row_operations:
+ fixes P :: "real^'n^'n \<Rightarrow> bool"
+ assumes zero_row: "\<And>A i. row i A = 0 \<Longrightarrow> P A"
+ and diagonal: "\<And>A. (\<And>i j. i \<noteq> j \<Longrightarrow> A$i$j = 0) \<Longrightarrow> P A"
+ and swap_cols: "\<And>A m n. \<lbrakk>P A; m \<noteq> n\<rbrakk> \<Longrightarrow> P(\<chi> i j. A $ i $ Fun.swap m n id j)"
+ and row_op: "\<And>A m n c. \<lbrakk>P A; m \<noteq> n\<rbrakk>
+ \<Longrightarrow> P(\<chi> i. if i = m then row m A + c *\<^sub>R row n A else row i A)"
+ shows "P A"
+proof -
+ have "P A" if "(\<And>i j. \<lbrakk>j \<in> -K; i \<noteq> j\<rbrakk> \<Longrightarrow> A$i$j = 0)" for A K
+ proof -
+ have "finite K"
+ by simp
+ then show ?thesis using that
+ proof (induction arbitrary: A rule: finite_induct)
+ case empty
+ with diagonal show ?case
+ by simp
+ next
+ case (insert k K)
+ note insertK = insert
+ have "P A" if kk: "A$k$k \<noteq> 0"
+ and 0: "\<And>i j. \<lbrakk>j \<in> - insert k K; i \<noteq> j\<rbrakk> \<Longrightarrow> A$i$j = 0"
+ "\<And>i. \<lbrakk>i \<in> -L; i \<noteq> k\<rbrakk> \<Longrightarrow> A$i$k = 0" for A L
+ proof -
+ have "finite L"
+ by simp
+ then show ?thesis using 0 kk
+ proof (induction arbitrary: A rule: finite_induct)
+ case (empty B)
+ show ?case
+ proof (rule insertK)
+ fix i j
+ assume "i \<in> - K" "j \<noteq> i"
+ show "B $ j $ i = 0"
+ using \<open>j \<noteq> i\<close> \<open>i \<in> - K\<close> empty
+ by (metis ComplD ComplI Compl_eq_Diff_UNIV Diff_empty UNIV_I insert_iff)
+ qed
+ next
+ case (insert l L B)
+ show ?case
+ proof (cases "k = l")
+ case True
+ with insert show ?thesis
+ by auto
+ next
+ case False
+ let ?C = "\<chi> i. if i = l then row l B - (B $ l $ k / B $ k $ k) *\<^sub>R row k B else row i B"
+ have 1: "\<lbrakk>j \<in> - insert k K; i \<noteq> j\<rbrakk> \<Longrightarrow> ?C $ i $ j = 0" for j i
+ by (auto simp: insert.prems(1) row_def)
+ have 2: "?C $ i $ k = 0"
+ if "i \<in> - L" "i \<noteq> k" for i
+ proof (cases "i=l")
+ case True
+ with that insert.prems show ?thesis
+ by (simp add: row_def)
+ next
+ case False
+ with that show ?thesis
+ by (simp add: insert.prems(2) row_def)
+ qed
+ have 3: "?C $ k $ k \<noteq> 0"
+ by (auto simp: insert.prems row_def \<open>k \<noteq> l\<close>)
+ have PC: "P ?C"
+ using insert.IH [OF 1 2 3] by auto
+ have eqB: "(\<chi> i. if i = l then row l ?C + (B $ l $ k / B $ k $ k) *\<^sub>R row k ?C else row i ?C) = B"
+ using \<open>k \<noteq> l\<close> by (simp add: vec_eq_iff row_def)
+ show ?thesis
+ using row_op [OF PC, of l k, where c = "B$l$k / B$k$k"] eqB \<open>k \<noteq> l\<close>
+ by (simp add: cong: if_cong)
+ qed
+ qed
+ qed
+ then have nonzero_hyp: "P A"
+ if kk: "A$k$k \<noteq> 0" and zeroes: "\<And>i j. j \<in> - insert k K \<and> i\<noteq>j \<Longrightarrow> A$i$j = 0" for A
+ by (auto simp: intro!: kk zeroes)
+ show ?case
+ proof (cases "row k A = 0")
+ case True
+ with zero_row show ?thesis by auto
+ next
+ case False
+ then obtain l where l: "A$k$l \<noteq> 0"
+ by (auto simp: row_def zero_vec_def vec_eq_iff)
+ show ?thesis
+ proof (cases "k = l")
+ case True
+ with l nonzero_hyp insert.prems show ?thesis
+ by blast
+ next
+ case False
+ have *: "A $ i $ Fun.swap k l id j = 0" if "j \<noteq> k" "j \<notin> K" "i \<noteq> j" for i j
+ using False l insert.prems that
+ by (auto simp: swap_def insert split: if_split_asm)
+ have "P (\<chi> i j. (\<chi> i j. A $ i $ Fun.swap k l id j) $ i $ Fun.swap k l id j)"
+ by (rule swap_cols [OF nonzero_hyp False]) (auto simp: l *)
+ moreover
+ have "(\<chi> i j. (\<chi> i j. A $ i $ Fun.swap k l id j) $ i $ Fun.swap k l id j) = A"
+ by (vector Fun.swap_def)
+ ultimately show ?thesis
+ by simp
+ qed
+ qed
+ qed
+ qed
+ then show ?thesis
+ by blast
+qed
+
+lemma%unimportant induct_matrix_elementary:
+ fixes P :: "real^'n^'n \<Rightarrow> bool"
+ assumes mult: "\<And>A B. \<lbrakk>P A; P B\<rbrakk> \<Longrightarrow> P(A ** B)"
+ and zero_row: "\<And>A i. row i A = 0 \<Longrightarrow> P A"
+ and diagonal: "\<And>A. (\<And>i j. i \<noteq> j \<Longrightarrow> A$i$j = 0) \<Longrightarrow> P A"
+ and swap1: "\<And>m n. m \<noteq> n \<Longrightarrow> P(\<chi> i j. mat 1 $ i $ Fun.swap m n id j)"
+ and idplus: "\<And>m n c. m \<noteq> n \<Longrightarrow> P(\<chi> i j. if i = m \<and> j = n then c else of_bool (i = j))"
+ shows "P A"
+proof -
+ have swap: "P (\<chi> i j. A $ i $ Fun.swap m n id j)" (is "P ?C")
+ if "P A" "m \<noteq> n" for A m n
+ proof -
+ have "A ** (\<chi> i j. mat 1 $ i $ Fun.swap m n id j) = ?C"
+ by (simp add: matrix_matrix_mult_def mat_def vec_eq_iff if_distrib sum.delta_remove)
+ then show ?thesis
+ using mult swap1 that by metis
+ qed
+ have row: "P (\<chi> i. if i = m then row m A + c *\<^sub>R row n A else row i A)" (is "P ?C")
+ if "P A" "m \<noteq> n" for A m n c
+ proof -
+ let ?B = "\<chi> i j. if i = m \<and> j = n then c else of_bool (i = j)"
+ have "?B ** A = ?C"
+ using \<open>m \<noteq> n\<close> unfolding matrix_matrix_mult_def row_def of_bool_def
+ by (auto simp: vec_eq_iff if_distrib [of "\<lambda>x. x * y" for y] sum.remove cong: if_cong)
+ then show ?thesis
+ by (rule subst) (auto simp: that mult idplus)
+ qed
+ show ?thesis
+ by (rule induct_matrix_row_operations [OF zero_row diagonal swap row])
+qed
+
+lemma%unimportant induct_matrix_elementary_alt:
+ fixes P :: "real^'n^'n \<Rightarrow> bool"
+ assumes mult: "\<And>A B. \<lbrakk>P A; P B\<rbrakk> \<Longrightarrow> P(A ** B)"
+ and zero_row: "\<And>A i. row i A = 0 \<Longrightarrow> P A"
+ and diagonal: "\<And>A. (\<And>i j. i \<noteq> j \<Longrightarrow> A$i$j = 0) \<Longrightarrow> P A"
+ and swap1: "\<And>m n. m \<noteq> n \<Longrightarrow> P(\<chi> i j. mat 1 $ i $ Fun.swap m n id j)"
+ and idplus: "\<And>m n. m \<noteq> n \<Longrightarrow> P(\<chi> i j. of_bool (i = m \<and> j = n \<or> i = j))"
+ shows "P A"
+proof -
+ have *: "P (\<chi> i j. if i = m \<and> j = n then c else of_bool (i = j))"
+ if "m \<noteq> n" for m n c
+ proof (cases "c = 0")
+ case True
+ with diagonal show ?thesis by auto
+ next
+ case False
+ then have eq: "(\<chi> i j. if i = m \<and> j = n then c else of_bool (i = j)) =
+ (\<chi> i j. if i = j then (if j = n then inverse c else 1) else 0) **
+ (\<chi> i j. of_bool (i = m \<and> j = n \<or> i = j)) **
+ (\<chi> i j. if i = j then if j = n then c else 1 else 0)"
+ using \<open>m \<noteq> n\<close>
+ apply (simp add: matrix_matrix_mult_def vec_eq_iff of_bool_def if_distrib [of "\<lambda>x. y * x" for y] cong: if_cong)
+ apply (simp add: if_if_eq_conj sum.neutral conj_commute cong: conj_cong)
+ done
+ show ?thesis
+ apply (subst eq)
+ apply (intro mult idplus that)
+ apply (auto intro: diagonal)
+ done
+ qed
+ show ?thesis
+ by (rule induct_matrix_elementary) (auto intro: assms *)
+qed
+
+lemma%unimportant matrix_vector_mult_matrix_matrix_mult_compose:
+ "(*v) (A ** B) = (*v) A \<circ> (*v) B"
+ by (auto simp: matrix_vector_mul_assoc)
+
+lemma%unimportant induct_linear_elementary:
+ fixes f :: "real^'n \<Rightarrow> real^'n"
+ assumes "linear f"
+ and comp: "\<And>f g. \<lbrakk>linear f; linear g; P f; P g\<rbrakk> \<Longrightarrow> P(f \<circ> g)"
+ and zeroes: "\<And>f i. \<lbrakk>linear f; \<And>x. (f x) $ i = 0\<rbrakk> \<Longrightarrow> P f"
+ and const: "\<And>c. P(\<lambda>x. \<chi> i. c i * x$i)"
+ and swap: "\<And>m n::'n. m \<noteq> n \<Longrightarrow> P(\<lambda>x. \<chi> i. x $ Fun.swap m n id i)"
+ and idplus: "\<And>m n::'n. m \<noteq> n \<Longrightarrow> P(\<lambda>x. \<chi> i. if i = m then x$m + x$n else x$i)"
+ shows "P f"
+proof -
+ have "P ((*v) A)" for A
+ proof (rule induct_matrix_elementary_alt)
+ fix A B
+ assume "P ((*v) A)" and "P ((*v) B)"
+ then show "P ((*v) (A ** B))"
+ by (auto simp add: matrix_vector_mult_matrix_matrix_mult_compose matrix_vector_mul_linear
+ intro!: comp)
+ next
+ fix A :: "real^'n^'n" and i
+ assume "row i A = 0"
+ show "P ((*v) A)"
+ using matrix_vector_mul_linear
+ by (rule zeroes[where i=i])
+ (metis \<open>row i A = 0\<close> inner_zero_left matrix_vector_mul_component row_def vec_lambda_eta)
+ next
+ fix A :: "real^'n^'n"
+ assume 0: "\<And>i j. i \<noteq> j \<Longrightarrow> A $ i $ j = 0"
+ have "A $ i $ i * x $ i = (\<Sum>j\<in>UNIV. A $ i $ j * x $ j)" for x and i :: "'n"
+ by (simp add: 0 comm_monoid_add_class.sum.remove [where x=i])
+ then have "(\<lambda>x. \<chi> i. A $ i $ i * x $ i) = ((*v) A)"
+ by (auto simp: 0 matrix_vector_mult_def)
+ then show "P ((*v) A)"
+ using const [of "\<lambda>i. A $ i $ i"] by simp
+ next
+ fix m n :: "'n"
+ assume "m \<noteq> n"
+ have eq: "(\<Sum>j\<in>UNIV. if i = Fun.swap m n id j then x $ j else 0) =
+ (\<Sum>j\<in>UNIV. if j = Fun.swap m n id i then x $ j else 0)"
+ for i and x :: "real^'n"
+ unfolding swap_def by (rule sum.cong) auto
+ have "(\<lambda>x::real^'n. \<chi> i. x $ Fun.swap m n id i) = ((*v) (\<chi> i j. if i = Fun.swap m n id j then 1 else 0))"
+ by (auto simp: mat_def matrix_vector_mult_def eq if_distrib [of "\<lambda>x. x * y" for y] cong: if_cong)
+ with swap [OF \<open>m \<noteq> n\<close>] show "P ((*v) (\<chi> i j. mat 1 $ i $ Fun.swap m n id j))"
+ by (simp add: mat_def matrix_vector_mult_def)
+ next
+ fix m n :: "'n"
+ assume "m \<noteq> n"
+ then have "x $ m + x $ n = (\<Sum>j\<in>UNIV. of_bool (j = n \<or> m = j) * x $ j)" for x :: "real^'n"
+ by (auto simp: of_bool_def if_distrib [of "\<lambda>x. x * y" for y] sum.remove cong: if_cong)
+ then have "(\<lambda>x::real^'n. \<chi> i. if i = m then x $ m + x $ n else x $ i) =
+ ((*v) (\<chi> i j. of_bool (i = m \<and> j = n \<or> i = j)))"
+ unfolding matrix_vector_mult_def of_bool_def
+ by (auto simp: vec_eq_iff if_distrib [of "\<lambda>x. x * y" for y] cong: if_cong)
+ then show "P ((*v) (\<chi> i j. of_bool (i = m \<and> j = n \<or> i = j)))"
+ using idplus [OF \<open>m \<noteq> n\<close>] by simp
+ qed
+ then show ?thesis
+ by (metis \<open>linear f\<close> matrix_vector_mul)
+qed
+
end
\ No newline at end of file
--- a/src/HOL/Analysis/Change_Of_Vars.thy Wed Jan 16 16:50:35 2019 -0500
+++ b/src/HOL/Analysis/Change_Of_Vars.thy Wed Jan 16 18:14:02 2019 -0500
@@ -9,246 +9,42 @@
begin
-subsection%important\<open>Induction on matrix row operations\<close>
+subsection%unimportant \<open>Orthogonal Transformation of Balls\<close>
-lemma%unimportant induct_matrix_row_operations:
- fixes P :: "real^'n^'n \<Rightarrow> bool"
- assumes zero_row: "\<And>A i. row i A = 0 \<Longrightarrow> P A"
- and diagonal: "\<And>A. (\<And>i j. i \<noteq> j \<Longrightarrow> A$i$j = 0) \<Longrightarrow> P A"
- and swap_cols: "\<And>A m n. \<lbrakk>P A; m \<noteq> n\<rbrakk> \<Longrightarrow> P(\<chi> i j. A $ i $ Fun.swap m n id j)"
- and row_op: "\<And>A m n c. \<lbrakk>P A; m \<noteq> n\<rbrakk>
- \<Longrightarrow> P(\<chi> i. if i = m then row m A + c *\<^sub>R row n A else row i A)"
- shows "P A"
-proof -
- have "P A" if "(\<And>i j. \<lbrakk>j \<in> -K; i \<noteq> j\<rbrakk> \<Longrightarrow> A$i$j = 0)" for A K
- proof -
- have "finite K"
- by simp
- then show ?thesis using that
- proof (induction arbitrary: A rule: finite_induct)
- case empty
- with diagonal show ?case
- by simp
- next
- case (insert k K)
- note insertK = insert
- have "P A" if kk: "A$k$k \<noteq> 0"
- and 0: "\<And>i j. \<lbrakk>j \<in> - insert k K; i \<noteq> j\<rbrakk> \<Longrightarrow> A$i$j = 0"
- "\<And>i. \<lbrakk>i \<in> -L; i \<noteq> k\<rbrakk> \<Longrightarrow> A$i$k = 0" for A L
- proof -
- have "finite L"
- by simp
- then show ?thesis using 0 kk
- proof (induction arbitrary: A rule: finite_induct)
- case (empty B)
- show ?case
- proof (rule insertK)
- fix i j
- assume "i \<in> - K" "j \<noteq> i"
- show "B $ j $ i = 0"
- using \<open>j \<noteq> i\<close> \<open>i \<in> - K\<close> empty
- by (metis ComplD ComplI Compl_eq_Diff_UNIV Diff_empty UNIV_I insert_iff)
- qed
- next
- case (insert l L B)
- show ?case
- proof (cases "k = l")
- case True
- with insert show ?thesis
- by auto
- next
- case False
- let ?C = "\<chi> i. if i = l then row l B - (B $ l $ k / B $ k $ k) *\<^sub>R row k B else row i B"
- have 1: "\<lbrakk>j \<in> - insert k K; i \<noteq> j\<rbrakk> \<Longrightarrow> ?C $ i $ j = 0" for j i
- by (auto simp: insert.prems(1) row_def)
- have 2: "?C $ i $ k = 0"
- if "i \<in> - L" "i \<noteq> k" for i
- proof (cases "i=l")
- case True
- with that insert.prems show ?thesis
- by (simp add: row_def)
- next
- case False
- with that show ?thesis
- by (simp add: insert.prems(2) row_def)
- qed
- have 3: "?C $ k $ k \<noteq> 0"
- by (auto simp: insert.prems row_def \<open>k \<noteq> l\<close>)
- have PC: "P ?C"
- using insert.IH [OF 1 2 3] by auto
- have eqB: "(\<chi> i. if i = l then row l ?C + (B $ l $ k / B $ k $ k) *\<^sub>R row k ?C else row i ?C) = B"
- using \<open>k \<noteq> l\<close> by (simp add: vec_eq_iff row_def)
- show ?thesis
- using row_op [OF PC, of l k, where c = "B$l$k / B$k$k"] eqB \<open>k \<noteq> l\<close>
- by (simp add: cong: if_cong)
- qed
- qed
- qed
- then have nonzero_hyp: "P A"
- if kk: "A$k$k \<noteq> 0" and zeroes: "\<And>i j. j \<in> - insert k K \<and> i\<noteq>j \<Longrightarrow> A$i$j = 0" for A
- by (auto simp: intro!: kk zeroes)
- show ?case
- proof (cases "row k A = 0")
- case True
- with zero_row show ?thesis by auto
- next
- case False
- then obtain l where l: "A$k$l \<noteq> 0"
- by (auto simp: row_def zero_vec_def vec_eq_iff)
- show ?thesis
- proof (cases "k = l")
- case True
- with l nonzero_hyp insert.prems show ?thesis
- by blast
- next
- case False
- have *: "A $ i $ Fun.swap k l id j = 0" if "j \<noteq> k" "j \<notin> K" "i \<noteq> j" for i j
- using False l insert.prems that
- by (auto simp: swap_def insert split: if_split_asm)
- have "P (\<chi> i j. (\<chi> i j. A $ i $ Fun.swap k l id j) $ i $ Fun.swap k l id j)"
- by (rule swap_cols [OF nonzero_hyp False]) (auto simp: l *)
- moreover
- have "(\<chi> i j. (\<chi> i j. A $ i $ Fun.swap k l id j) $ i $ Fun.swap k l id j) = A"
- by (metis (no_types, lifting) id_apply o_apply swap_id_idempotent vec_lambda_unique vec_lambda_unique)
- ultimately show ?thesis
- by simp
- qed
- qed
- qed
- qed
- then show ?thesis
- by blast
+lemma%unimportant image_orthogonal_transformation_ball:
+ fixes f :: "'a::euclidean_space \<Rightarrow> 'a"
+ assumes "orthogonal_transformation f"
+ shows "f ` ball x r = ball (f x) r"
+proof (intro equalityI subsetI)
+ fix y assume "y \<in> f ` ball x r"
+ with assms show "y \<in> ball (f x) r"
+ by (auto simp: orthogonal_transformation_isometry)
+next
+ fix y assume y: "y \<in> ball (f x) r"
+ then obtain z where z: "y = f z"
+ using assms orthogonal_transformation_surj by blast
+ with y assms show "y \<in> f ` ball x r"
+ by (auto simp: orthogonal_transformation_isometry)
qed
-lemma%unimportant induct_matrix_elementary:
- fixes P :: "real^'n^'n \<Rightarrow> bool"
- assumes mult: "\<And>A B. \<lbrakk>P A; P B\<rbrakk> \<Longrightarrow> P(A ** B)"
- and zero_row: "\<And>A i. row i A = 0 \<Longrightarrow> P A"
- and diagonal: "\<And>A. (\<And>i j. i \<noteq> j \<Longrightarrow> A$i$j = 0) \<Longrightarrow> P A"
- and swap1: "\<And>m n. m \<noteq> n \<Longrightarrow> P(\<chi> i j. mat 1 $ i $ Fun.swap m n id j)"
- and idplus: "\<And>m n c. m \<noteq> n \<Longrightarrow> P(\<chi> i j. if i = m \<and> j = n then c else of_bool (i = j))"
- shows "P A"
-proof -
- have swap: "P (\<chi> i j. A $ i $ Fun.swap m n id j)" (is "P ?C")
- if "P A" "m \<noteq> n" for A m n
- proof -
- have "A ** (\<chi> i j. mat 1 $ i $ Fun.swap m n id j) = ?C"
- by (simp add: matrix_matrix_mult_def mat_def vec_eq_iff if_distrib sum.delta_remove)
- then show ?thesis
- using mult swap1 that by metis
- qed
- have row: "P (\<chi> i. if i = m then row m A + c *\<^sub>R row n A else row i A)" (is "P ?C")
- if "P A" "m \<noteq> n" for A m n c
- proof -
- let ?B = "\<chi> i j. if i = m \<and> j = n then c else of_bool (i = j)"
- have "?B ** A = ?C"
- using \<open>m \<noteq> n\<close> unfolding matrix_matrix_mult_def row_def of_bool_def
- by (auto simp: vec_eq_iff if_distrib [of "\<lambda>x. x * y" for y] sum.remove cong: if_cong)
- then show ?thesis
- by (rule subst) (auto simp: that mult idplus)
- qed
- show ?thesis
- by (rule induct_matrix_row_operations [OF zero_row diagonal swap row])
-qed
-
-lemma%unimportant induct_matrix_elementary_alt:
- fixes P :: "real^'n^'n \<Rightarrow> bool"
- assumes mult: "\<And>A B. \<lbrakk>P A; P B\<rbrakk> \<Longrightarrow> P(A ** B)"
- and zero_row: "\<And>A i. row i A = 0 \<Longrightarrow> P A"
- and diagonal: "\<And>A. (\<And>i j. i \<noteq> j \<Longrightarrow> A$i$j = 0) \<Longrightarrow> P A"
- and swap1: "\<And>m n. m \<noteq> n \<Longrightarrow> P(\<chi> i j. mat 1 $ i $ Fun.swap m n id j)"
- and idplus: "\<And>m n. m \<noteq> n \<Longrightarrow> P(\<chi> i j. of_bool (i = m \<and> j = n \<or> i = j))"
- shows "P A"
-proof -
- have *: "P (\<chi> i j. if i = m \<and> j = n then c else of_bool (i = j))"
- if "m \<noteq> n" for m n c
- proof (cases "c = 0")
- case True
- with diagonal show ?thesis by auto
- next
- case False
- then have eq: "(\<chi> i j. if i = m \<and> j = n then c else of_bool (i = j)) =
- (\<chi> i j. if i = j then (if j = n then inverse c else 1) else 0) **
- (\<chi> i j. of_bool (i = m \<and> j = n \<or> i = j)) **
- (\<chi> i j. if i = j then if j = n then c else 1 else 0)"
- using \<open>m \<noteq> n\<close>
- apply (simp add: matrix_matrix_mult_def vec_eq_iff of_bool_def if_distrib [of "\<lambda>x. y * x" for y] cong: if_cong)
- apply (simp add: if_if_eq_conj sum.neutral conj_commute cong: conj_cong)
- done
- show ?thesis
- apply (subst eq)
- apply (intro mult idplus that)
- apply (auto intro: diagonal)
- done
- qed
- show ?thesis
- by (rule induct_matrix_elementary) (auto intro: assms *)
+lemma%unimportant image_orthogonal_transformation_cball:
+ fixes f :: "'a::euclidean_space \<Rightarrow> 'a"
+ assumes "orthogonal_transformation f"
+ shows "f ` cball x r = cball (f x) r"
+proof (intro equalityI subsetI)
+ fix y assume "y \<in> f ` cball x r"
+ with assms show "y \<in> cball (f x) r"
+ by (auto simp: orthogonal_transformation_isometry)
+next
+ fix y assume y: "y \<in> cball (f x) r"
+ then obtain z where z: "y = f z"
+ using assms orthogonal_transformation_surj by blast
+ with y assms show "y \<in> f ` cball x r"
+ by (auto simp: orthogonal_transformation_isometry)
qed
-lemma%unimportant matrix_vector_mult_matrix_matrix_mult_compose:
- "(*v) (A ** B) = (*v) A \<circ> (*v) B"
- by (auto simp: matrix_vector_mul_assoc)
-lemma%unimportant induct_linear_elementary:
- fixes f :: "real^'n \<Rightarrow> real^'n"
- assumes "linear f"
- and comp: "\<And>f g. \<lbrakk>linear f; linear g; P f; P g\<rbrakk> \<Longrightarrow> P(f \<circ> g)"
- and zeroes: "\<And>f i. \<lbrakk>linear f; \<And>x. (f x) $ i = 0\<rbrakk> \<Longrightarrow> P f"
- and const: "\<And>c. P(\<lambda>x. \<chi> i. c i * x$i)"
- and swap: "\<And>m n::'n. m \<noteq> n \<Longrightarrow> P(\<lambda>x. \<chi> i. x $ Fun.swap m n id i)"
- and idplus: "\<And>m n::'n. m \<noteq> n \<Longrightarrow> P(\<lambda>x. \<chi> i. if i = m then x$m + x$n else x$i)"
- shows "P f"
-proof -
- have "P ((*v) A)" for A
- proof (rule induct_matrix_elementary_alt)
- fix A B
- assume "P ((*v) A)" and "P ((*v) B)"
- then show "P ((*v) (A ** B))"
- by (auto simp add: matrix_vector_mult_matrix_matrix_mult_compose matrix_vector_mul_linear
- intro!: comp)
- next
- fix A :: "real^'n^'n" and i
- assume "row i A = 0"
- show "P ((*v) A)"
- using matrix_vector_mul_linear
- by (rule zeroes[where i=i])
- (metis \<open>row i A = 0\<close> inner_zero_left matrix_vector_mul_component row_def vec_lambda_eta)
- next
- fix A :: "real^'n^'n"
- assume 0: "\<And>i j. i \<noteq> j \<Longrightarrow> A $ i $ j = 0"
- have "A $ i $ i * x $ i = (\<Sum>j\<in>UNIV. A $ i $ j * x $ j)" for x and i :: "'n"
- by (simp add: 0 comm_monoid_add_class.sum.remove [where x=i])
- then have "(\<lambda>x. \<chi> i. A $ i $ i * x $ i) = ((*v) A)"
- by (auto simp: 0 matrix_vector_mult_def)
- then show "P ((*v) A)"
- using const [of "\<lambda>i. A $ i $ i"] by simp
- next
- fix m n :: "'n"
- assume "m \<noteq> n"
- have eq: "(\<Sum>j\<in>UNIV. if i = Fun.swap m n id j then x $ j else 0) =
- (\<Sum>j\<in>UNIV. if j = Fun.swap m n id i then x $ j else 0)"
- for i and x :: "real^'n"
- unfolding swap_def by (rule sum.cong) auto
- have "(\<lambda>x::real^'n. \<chi> i. x $ Fun.swap m n id i) = ((*v) (\<chi> i j. if i = Fun.swap m n id j then 1 else 0))"
- by (auto simp: mat_def matrix_vector_mult_def eq if_distrib [of "\<lambda>x. x * y" for y] cong: if_cong)
- with swap [OF \<open>m \<noteq> n\<close>] show "P ((*v) (\<chi> i j. mat 1 $ i $ Fun.swap m n id j))"
- by (simp add: mat_def matrix_vector_mult_def)
- next
- fix m n :: "'n"
- assume "m \<noteq> n"
- then have "x $ m + x $ n = (\<Sum>j\<in>UNIV. of_bool (j = n \<or> m = j) * x $ j)" for x :: "real^'n"
- by (auto simp: of_bool_def if_distrib [of "\<lambda>x. x * y" for y] sum.remove cong: if_cong)
- then have "(\<lambda>x::real^'n. \<chi> i. if i = m then x $ m + x $ n else x $ i) =
- ((*v) (\<chi> i j. of_bool (i = m \<and> j = n \<or> i = j)))"
- unfolding matrix_vector_mult_def of_bool_def
- by (auto simp: vec_eq_iff if_distrib [of "\<lambda>x. x * y" for y] cong: if_cong)
- then show "P ((*v) (\<chi> i j. of_bool (i = m \<and> j = n \<or> i = j)))"
- using idplus [OF \<open>m \<noteq> n\<close>] by simp
- qed
- then show ?thesis
- by (metis \<open>linear f\<close> matrix_vector_mul)
-qed
-
+subsection \<open>Measurable Shear and Stretch\<close>
proposition%important
fixes a :: "real^'n"
--- a/src/HOL/Analysis/Convex.thy Wed Jan 16 16:50:35 2019 -0500
+++ b/src/HOL/Analysis/Convex.thy Wed Jan 16 18:14:02 2019 -0500
@@ -14,79 +14,6 @@
"HOL-Library.Set_Algebras"
begin
-lemma substdbasis_expansion_unique:
- assumes d: "d \<subseteq> Basis"
- shows "(\<Sum>i\<in>d. f i *\<^sub>R i) = (x::'a::euclidean_space) \<longleftrightarrow>
- (\<forall>i\<in>Basis. (i \<in> d \<longrightarrow> f i = x \<bullet> i) \<and> (i \<notin> d \<longrightarrow> x \<bullet> i = 0))"
-proof -
- have *: "\<And>x a b P. x * (if P then a else b) = (if P then x * a else x * b)"
- by auto
- have **: "finite d"
- by (auto intro: finite_subset[OF assms])
- 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)"
- using d
- by (auto intro!: sum.cong simp: inner_Basis inner_sum_left)
- show ?thesis
- unfolding euclidean_eq_iff[where 'a='a] by (auto simp: sum.delta[OF **] ***)
-qed
-
-lemma independent_substdbasis: "d \<subseteq> Basis \<Longrightarrow> independent d"
- by (rule independent_mono[OF independent_Basis])
-
-lemma sum_not_0: "sum f A \<noteq> 0 \<Longrightarrow> \<exists>a \<in> A. f a \<noteq> 0"
- by (rule ccontr) auto
-
-lemma subset_translation_eq [simp]:
- fixes a :: "'a::real_vector" shows "(+) a ` s \<subseteq> (+) a ` t \<longleftrightarrow> s \<subseteq> t"
- by auto
-
-lemma translate_inj_on:
- fixes A :: "'a::ab_group_add set"
- shows "inj_on (\<lambda>x. a + x) A"
- unfolding inj_on_def by auto
-
-lemma translation_assoc:
- fixes a b :: "'a::ab_group_add"
- shows "(\<lambda>x. b + x) ` ((\<lambda>x. a + x) ` S) = (\<lambda>x. (a + b) + x) ` S"
- by auto
-
-lemma translation_invert:
- fixes a :: "'a::ab_group_add"
- assumes "(\<lambda>x. a + x) ` A = (\<lambda>x. a + x) ` B"
- shows "A = B"
-proof -
- have "(\<lambda>x. -a + x) ` ((\<lambda>x. a + x) ` A) = (\<lambda>x. - a + x) ` ((\<lambda>x. a + x) ` B)"
- using assms by auto
- then show ?thesis
- using translation_assoc[of "-a" a A] translation_assoc[of "-a" a B] by auto
-qed
-
-lemma translation_galois:
- fixes a :: "'a::ab_group_add"
- shows "T = ((\<lambda>x. a + x) ` S) \<longleftrightarrow> S = ((\<lambda>x. (- a) + x) ` T)"
- using translation_assoc[of "-a" a S]
- apply auto
- using translation_assoc[of a "-a" T]
- apply auto
- done
-
-lemma translation_inverse_subset:
- assumes "((\<lambda>x. - a + x) ` V) \<le> (S :: 'n::ab_group_add set)"
- shows "V \<le> ((\<lambda>x. a + x) ` S)"
-proof -
- {
- fix x
- assume "x \<in> V"
- then have "x-a \<in> S" using assms by auto
- then have "x \<in> {a + v |v. v \<in> S}"
- apply auto
- apply (rule exI[of _ "x-a"], simp)
- done
- then have "x \<in> ((\<lambda>x. a+x) ` S)" by auto
- }
- then show ?thesis by auto
-qed
-
subsection \<open>Convexity\<close>
definition%important convex :: "'a::real_vector set \<Rightarrow> bool"
--- a/src/HOL/Analysis/Cross3.thy Wed Jan 16 16:50:35 2019 -0500
+++ b/src/HOL/Analysis/Cross3.thy Wed Jan 16 18:14:02 2019 -0500
@@ -7,7 +7,7 @@
section\<open>Vector Cross Products in 3 Dimensions\<close>
theory "Cross3"
- imports Determinants
+ imports Determinants Cartesian_Euclidean_Space
begin
context includes no_Set_Product_syntax
--- a/src/HOL/Analysis/Determinants.thy Wed Jan 16 16:50:35 2019 -0500
+++ b/src/HOL/Analysis/Determinants.thy Wed Jan 16 18:14:02 2019 -0500
@@ -6,7 +6,7 @@
theory Determinants
imports
- Cartesian_Euclidean_Space
+ Cartesian_Space
"HOL-Library.Permutations"
begin
@@ -941,372 +941,6 @@
by auto
qed
-subsection%important \<open>Orthogonality of a transformation and matrix\<close>
-
-definition%important "orthogonal_transformation f \<longleftrightarrow> linear f \<and> (\<forall>v w. f v \<bullet> f w = v \<bullet> w)"
-
-definition%important "orthogonal_matrix (Q::'a::semiring_1^'n^'n) \<longleftrightarrow>
- transpose Q ** Q = mat 1 \<and> Q ** transpose Q = mat 1"
-
-lemma%unimportant orthogonal_transformation:
- "orthogonal_transformation f \<longleftrightarrow> linear f \<and> (\<forall>v. norm (f v) = norm v)"
- unfolding orthogonal_transformation_def
- apply auto
- apply (erule_tac x=v in allE)+
- apply (simp add: norm_eq_sqrt_inner)
- apply (simp add: dot_norm linear_add[symmetric])
- done
-
-lemma%unimportant orthogonal_transformation_id [simp]: "orthogonal_transformation (\<lambda>x. x)"
- by (simp add: linear_iff orthogonal_transformation_def)
-
-lemma%unimportant orthogonal_orthogonal_transformation:
- "orthogonal_transformation f \<Longrightarrow> orthogonal (f x) (f y) \<longleftrightarrow> orthogonal x y"
- by (simp add: orthogonal_def orthogonal_transformation_def)
-
-lemma%unimportant orthogonal_transformation_compose:
- "\<lbrakk>orthogonal_transformation f; orthogonal_transformation g\<rbrakk> \<Longrightarrow> orthogonal_transformation(f \<circ> g)"
- by (auto simp: orthogonal_transformation_def linear_compose)
-
-lemma%unimportant orthogonal_transformation_neg:
- "orthogonal_transformation(\<lambda>x. -(f x)) \<longleftrightarrow> orthogonal_transformation f"
- by (auto simp: orthogonal_transformation_def dest: linear_compose_neg)
-
-lemma%unimportant orthogonal_transformation_scaleR: "orthogonal_transformation f \<Longrightarrow> f (c *\<^sub>R v) = c *\<^sub>R f v"
- by (simp add: linear_iff orthogonal_transformation_def)
-
-lemma%unimportant orthogonal_transformation_linear:
- "orthogonal_transformation f \<Longrightarrow> linear f"
- by (simp add: orthogonal_transformation_def)
-
-lemma%unimportant orthogonal_transformation_inj:
- "orthogonal_transformation f \<Longrightarrow> inj f"
- unfolding orthogonal_transformation_def inj_on_def
- by (metis vector_eq)
-
-lemma%unimportant orthogonal_transformation_surj:
- "orthogonal_transformation f \<Longrightarrow> surj f"
- for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space"
- by (simp add: linear_injective_imp_surjective orthogonal_transformation_inj orthogonal_transformation_linear)
-
-lemma%unimportant orthogonal_transformation_bij:
- "orthogonal_transformation f \<Longrightarrow> bij f"
- for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space"
- by (simp add: bij_def orthogonal_transformation_inj orthogonal_transformation_surj)
-
-lemma%unimportant orthogonal_transformation_inv:
- "orthogonal_transformation f \<Longrightarrow> orthogonal_transformation (inv f)"
- for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space"
- by (metis (no_types, hide_lams) bijection.inv_right bijection_def inj_linear_imp_inv_linear orthogonal_transformation orthogonal_transformation_bij orthogonal_transformation_inj)
-
-lemma%unimportant orthogonal_transformation_norm:
- "orthogonal_transformation f \<Longrightarrow> norm (f x) = norm x"
- by (metis orthogonal_transformation)
-
-lemma%unimportant orthogonal_matrix: "orthogonal_matrix (Q:: real ^'n^'n) \<longleftrightarrow> transpose Q ** Q = mat 1"
- by (metis matrix_left_right_inverse orthogonal_matrix_def)
-
-lemma%unimportant orthogonal_matrix_id: "orthogonal_matrix (mat 1 :: _^'n^'n)"
- by (simp add: orthogonal_matrix_def)
-
-lemma%unimportant orthogonal_matrix_mul:
- fixes A :: "real ^'n^'n"
- assumes "orthogonal_matrix A" "orthogonal_matrix B"
- shows "orthogonal_matrix(A ** B)"
- using assms
- by (simp add: orthogonal_matrix matrix_transpose_mul matrix_left_right_inverse matrix_mul_assoc)
-
-lemma%important orthogonal_transformation_matrix:
- fixes f:: "real^'n \<Rightarrow> real^'n"
- shows "orthogonal_transformation f \<longleftrightarrow> linear f \<and> orthogonal_matrix(matrix f)"
- (is "?lhs \<longleftrightarrow> ?rhs")
-proof%unimportant -
- let ?mf = "matrix f"
- let ?ot = "orthogonal_transformation f"
- let ?U = "UNIV :: 'n set"
- have fU: "finite ?U" by simp
- let ?m1 = "mat 1 :: real ^'n^'n"
- {
- assume ot: ?ot
- from ot have lf: "Vector_Spaces.linear (*s) (*s) f" and fd: "\<And>v w. f v \<bullet> f w = v \<bullet> w"
- unfolding orthogonal_transformation_def orthogonal_matrix linear_def scalar_mult_eq_scaleR
- by blast+
- {
- fix i j
- let ?A = "transpose ?mf ** ?mf"
- have th0: "\<And>b (x::'a::comm_ring_1). (if b then 1 else 0)*x = (if b then x else 0)"
- "\<And>b (x::'a::comm_ring_1). x*(if b then 1 else 0) = (if b then x else 0)"
- by simp_all
- from fd[of "axis i 1" "axis j 1",
- simplified matrix_works[OF lf, symmetric] dot_matrix_vector_mul]
- have "?A$i$j = ?m1 $ i $ j"
- by (simp add: inner_vec_def matrix_matrix_mult_def columnvector_def rowvector_def
- th0 sum.delta[OF fU] mat_def axis_def)
- }
- then have "orthogonal_matrix ?mf"
- unfolding orthogonal_matrix
- by vector
- with lf have ?rhs
- unfolding linear_def scalar_mult_eq_scaleR
- by blast
- }
- moreover
- {
- assume lf: "Vector_Spaces.linear (*s) (*s) f" and om: "orthogonal_matrix ?mf"
- from lf om have ?lhs
- unfolding orthogonal_matrix_def norm_eq orthogonal_transformation
- apply (simp only: matrix_works[OF lf, symmetric] dot_matrix_vector_mul)
- apply (simp add: dot_matrix_product linear_def scalar_mult_eq_scaleR)
- done
- }
- ultimately show ?thesis
- by (auto simp: linear_def scalar_mult_eq_scaleR)
-qed
-
-lemma%important det_orthogonal_matrix:
- fixes Q:: "'a::linordered_idom^'n^'n"
- assumes oQ: "orthogonal_matrix Q"
- shows "det Q = 1 \<or> det Q = - 1"
-proof%unimportant -
- have "Q ** transpose Q = mat 1"
- by (metis oQ orthogonal_matrix_def)
- then have "det (Q ** transpose Q) = det (mat 1:: 'a^'n^'n)"
- by simp
- then have "det Q * det Q = 1"
- by (simp add: det_mul)
- then show ?thesis
- by (simp add: square_eq_1_iff)
-qed
-
-lemma%important orthogonal_transformation_det [simp]:
- fixes f :: "real^'n \<Rightarrow> real^'n"
- shows "orthogonal_transformation f \<Longrightarrow> \<bar>det (matrix f)\<bar> = 1"
- using%unimportant det_orthogonal_matrix orthogonal_transformation_matrix by fastforce
-
-
-subsection%important \<open>Linearity of scaling, and hence isometry, that preserves origin\<close>
-
-lemma%important scaling_linear:
- fixes f :: "'a::real_inner \<Rightarrow> 'a::real_inner"
- assumes f0: "f 0 = 0"
- and fd: "\<forall>x y. dist (f x) (f y) = c * dist x y"
- shows "linear f"
-proof%unimportant -
- {
- fix v w
- have "norm (f x) = c * norm x" for x
- by (metis dist_0_norm f0 fd)
- then have "f v \<bullet> f w = c\<^sup>2 * (v \<bullet> w)"
- unfolding dot_norm_neg dist_norm[symmetric]
- by (simp add: fd power2_eq_square field_simps)
- }
- then show ?thesis
- unfolding linear_iff vector_eq[where 'a="'a"] scalar_mult_eq_scaleR
- by (simp add: inner_add field_simps)
-qed
-
-lemma%unimportant isometry_linear:
- "f (0::'a::real_inner) = (0::'a) \<Longrightarrow> \<forall>x y. dist(f x) (f y) = dist x y \<Longrightarrow> linear f"
- by (rule scaling_linear[where c=1]) simp_all
-
-text \<open>Hence another formulation of orthogonal transformation\<close>
-
-lemma%important orthogonal_transformation_isometry:
- "orthogonal_transformation f \<longleftrightarrow> f(0::'a::real_inner) = (0::'a) \<and> (\<forall>x y. dist(f x) (f y) = dist x y)"
- unfolding orthogonal_transformation
- apply (auto simp: linear_0 isometry_linear)
- apply (metis (no_types, hide_lams) dist_norm linear_diff)
- by (metis dist_0_norm)
-
-
-lemma%unimportant image_orthogonal_transformation_ball:
- fixes f :: "'a::euclidean_space \<Rightarrow> 'a"
- assumes "orthogonal_transformation f"
- shows "f ` ball x r = ball (f x) r"
-proof (intro equalityI subsetI)
- fix y assume "y \<in> f ` ball x r"
- with assms show "y \<in> ball (f x) r"
- by (auto simp: orthogonal_transformation_isometry)
-next
- fix y assume y: "y \<in> ball (f x) r"
- then obtain z where z: "y = f z"
- using assms orthogonal_transformation_surj by blast
- with y assms show "y \<in> f ` ball x r"
- by (auto simp: orthogonal_transformation_isometry)
-qed
-
-lemma%unimportant image_orthogonal_transformation_cball:
- fixes f :: "'a::euclidean_space \<Rightarrow> 'a"
- assumes "orthogonal_transformation f"
- shows "f ` cball x r = cball (f x) r"
-proof (intro equalityI subsetI)
- fix y assume "y \<in> f ` cball x r"
- with assms show "y \<in> cball (f x) r"
- by (auto simp: orthogonal_transformation_isometry)
-next
- fix y assume y: "y \<in> cball (f x) r"
- then obtain z where z: "y = f z"
- using assms orthogonal_transformation_surj by blast
- with y assms show "y \<in> f ` cball x r"
- by (auto simp: orthogonal_transformation_isometry)
-qed
-
-subsection%important \<open> We can find an orthogonal matrix taking any unit vector to any other\<close>
-
-lemma%unimportant orthogonal_matrix_transpose [simp]:
- "orthogonal_matrix(transpose A) \<longleftrightarrow> orthogonal_matrix A"
- by (auto simp: orthogonal_matrix_def)
-
-lemma%unimportant orthogonal_matrix_orthonormal_columns:
- fixes A :: "real^'n^'n"
- shows "orthogonal_matrix A \<longleftrightarrow>
- (\<forall>i. norm(column i A) = 1) \<and>
- (\<forall>i j. i \<noteq> j \<longrightarrow> orthogonal (column i A) (column j A))"
- by (auto simp: orthogonal_matrix matrix_mult_transpose_dot_column vec_eq_iff mat_def norm_eq_1 orthogonal_def)
-
-lemma%unimportant orthogonal_matrix_orthonormal_rows:
- fixes A :: "real^'n^'n"
- shows "orthogonal_matrix A \<longleftrightarrow>
- (\<forall>i. norm(row i A) = 1) \<and>
- (\<forall>i j. i \<noteq> j \<longrightarrow> orthogonal (row i A) (row j A))"
- using orthogonal_matrix_orthonormal_columns [of "transpose A"] by simp
-
-lemma%important orthogonal_matrix_exists_basis:
- fixes a :: "real^'n"
- assumes "norm a = 1"
- obtains A where "orthogonal_matrix A" "A *v (axis k 1) = a"
-proof%unimportant -
- obtain S where "a \<in> S" "pairwise orthogonal S" and noS: "\<And>x. x \<in> S \<Longrightarrow> norm x = 1"
- and "independent S" "card S = CARD('n)" "span S = UNIV"
- using vector_in_orthonormal_basis assms by force
- then obtain f0 where "bij_betw f0 (UNIV::'n set) S"
- by (metis finite_class.finite_UNIV finite_same_card_bij finiteI_independent)
- then obtain f where f: "bij_betw f (UNIV::'n set) S" and a: "a = f k"
- using bij_swap_iff [of k "inv f0 a" f0]
- by (metis UNIV_I \<open>a \<in> S\<close> bij_betw_inv_into_right bij_betw_swap_iff swap_apply1)
- show thesis
- proof
- have [simp]: "\<And>i. norm (f i) = 1"
- using bij_betwE [OF \<open>bij_betw f UNIV S\<close>] by (blast intro: noS)
- have [simp]: "\<And>i j. i \<noteq> j \<Longrightarrow> orthogonal (f i) (f j)"
- using \<open>pairwise orthogonal S\<close> \<open>bij_betw f UNIV S\<close>
- by (auto simp: pairwise_def bij_betw_def inj_on_def)
- show "orthogonal_matrix (\<chi> i j. f j $ i)"
- by (simp add: orthogonal_matrix_orthonormal_columns column_def)
- show "(\<chi> i j. f j $ i) *v axis k 1 = a"
- by (simp add: matrix_vector_mult_def axis_def a if_distrib cong: if_cong)
- qed
-qed
-
-lemma%unimportant orthogonal_transformation_exists_1:
- fixes a b :: "real^'n"
- assumes "norm a = 1" "norm b = 1"
- obtains f where "orthogonal_transformation f" "f a = b"
-proof%unimportant -
- obtain k::'n where True
- by simp
- obtain A B where AB: "orthogonal_matrix A" "orthogonal_matrix B" and eq: "A *v (axis k 1) = a" "B *v (axis k 1) = b"
- using orthogonal_matrix_exists_basis assms by metis
- let ?f = "\<lambda>x. (B ** transpose A) *v x"
- show thesis
- proof
- show "orthogonal_transformation ?f"
- by (subst orthogonal_transformation_matrix)
- (auto simp: AB orthogonal_matrix_mul)
- next
- show "?f a = b"
- using \<open>orthogonal_matrix A\<close> unfolding orthogonal_matrix_def
- by (metis eq matrix_mul_rid matrix_vector_mul_assoc)
- qed
-qed
-
-lemma%important orthogonal_transformation_exists:
- fixes a b :: "real^'n"
- assumes "norm a = norm b"
- obtains f where "orthogonal_transformation f" "f a = b"
-proof%unimportant (cases "a = 0 \<or> b = 0")
- case True
- with assms show ?thesis
- using that by force
-next
- case False
- then obtain f where f: "orthogonal_transformation f" and eq: "f (a /\<^sub>R norm a) = (b /\<^sub>R norm b)"
- by (auto intro: orthogonal_transformation_exists_1 [of "a /\<^sub>R norm a" "b /\<^sub>R norm b"])
- show ?thesis
- proof
- interpret linear f
- using f by (simp add: orthogonal_transformation_linear)
- have "f a /\<^sub>R norm a = f (a /\<^sub>R norm a)"
- by (simp add: scale)
- also have "\<dots> = b /\<^sub>R norm a"
- by (simp add: eq assms [symmetric])
- finally show "f a = b"
- using False by auto
- qed (use f in auto)
-qed
-
-
-subsection%important \<open>Can extend an isometry from unit sphere\<close>
-
-lemma%important isometry_sphere_extend:
- fixes f:: "'a::real_inner \<Rightarrow> 'a"
- assumes f1: "\<And>x. norm x = 1 \<Longrightarrow> norm (f x) = 1"
- and fd1: "\<And>x y. \<lbrakk>norm x = 1; norm y = 1\<rbrakk> \<Longrightarrow> dist (f x) (f y) = dist x y"
- shows "\<exists>g. orthogonal_transformation g \<and> (\<forall>x. norm x = 1 \<longrightarrow> g x = f x)"
-proof%unimportant -
- {
- fix x y x' y' u v u' v' :: "'a"
- assume H: "x = norm x *\<^sub>R u" "y = norm y *\<^sub>R v"
- "x' = norm x *\<^sub>R u'" "y' = norm y *\<^sub>R v'"
- and J: "norm u = 1" "norm u' = 1" "norm v = 1" "norm v' = 1" "norm(u' - v') = norm(u - v)"
- then have *: "u \<bullet> v = u' \<bullet> v' + v' \<bullet> u' - v \<bullet> u "
- by (simp add: norm_eq norm_eq_1 inner_add inner_diff)
- have "norm (norm x *\<^sub>R u' - norm y *\<^sub>R v') = norm (norm x *\<^sub>R u - norm y *\<^sub>R v)"
- using J by (simp add: norm_eq norm_eq_1 inner_diff * field_simps)
- then have "norm(x' - y') = norm(x - y)"
- using H by metis
- }
- note norm_eq = this
- let ?g = "\<lambda>x. if x = 0 then 0 else norm x *\<^sub>R f (x /\<^sub>R norm x)"
- have thfg: "?g x = f x" if "norm x = 1" for x
- using that by auto
- have thd: "dist (?g x) (?g y) = dist x y" for x y
- proof (cases "x=0 \<or> y=0")
- case False
- show "dist (?g x) (?g y) = dist x y"
- unfolding dist_norm
- proof (rule norm_eq)
- show "x = norm x *\<^sub>R (x /\<^sub>R norm x)" "y = norm y *\<^sub>R (y /\<^sub>R norm y)"
- "norm (f (x /\<^sub>R norm x)) = 1" "norm (f (y /\<^sub>R norm y)) = 1"
- using False f1 by auto
- qed (use False in \<open>auto simp: field_simps intro: f1 fd1[unfolded dist_norm]\<close>)
- qed (auto simp: f1)
- show ?thesis
- unfolding orthogonal_transformation_isometry
- by (rule exI[where x= ?g]) (metis thfg thd)
-qed
-
-subsection%important \<open>Rotation, reflection, rotoinversion\<close>
-
-definition%important "rotation_matrix Q \<longleftrightarrow> orthogonal_matrix Q \<and> det Q = 1"
-definition%important "rotoinversion_matrix Q \<longleftrightarrow> orthogonal_matrix Q \<and> det Q = - 1"
-
-lemma%important orthogonal_rotation_or_rotoinversion:
- fixes Q :: "'a::linordered_idom^'n^'n"
- shows " orthogonal_matrix Q \<longleftrightarrow> rotation_matrix Q \<or> rotoinversion_matrix Q"
- by%unimportant (metis rotoinversion_matrix_def rotation_matrix_def det_orthogonal_matrix)
-
-text \<open>Explicit formulas for low dimensions\<close>
-
-lemma%unimportant prod_neutral_const: "prod f {(1::nat)..1} = f 1"
- by simp
-
-lemma%unimportant prod_2: "prod f {(1::nat)..2} = f 1 * f 2"
- by (simp add: eval_nat_numeral atLeastAtMostSuc_conv mult.commute)
-
-lemma%unimportant prod_3: "prod f {(1::nat)..3} = f 1 * f 2 * f 3"
- by (simp add: eval_nat_numeral atLeastAtMostSuc_conv mult.commute)
-
lemma%unimportant det_1: "det (A::'a::comm_ring_1^1^1) = A$1$1"
by (simp add: det_def sign_id)
@@ -1342,6 +976,36 @@
by (simp add: sign_swap_id permutation_swap_id sign_compose sign_id swap_id_eq)
qed
+lemma%important det_orthogonal_matrix:
+ fixes Q:: "'a::linordered_idom^'n^'n"
+ assumes oQ: "orthogonal_matrix Q"
+ shows "det Q = 1 \<or> det Q = - 1"
+proof%unimportant -
+ have "Q ** transpose Q = mat 1"
+ by (metis oQ orthogonal_matrix_def)
+ then have "det (Q ** transpose Q) = det (mat 1:: 'a^'n^'n)"
+ by simp
+ then have "det Q * det Q = 1"
+ by (simp add: det_mul)
+ then show ?thesis
+ by (simp add: square_eq_1_iff)
+qed
+
+lemma%important orthogonal_transformation_det [simp]:
+ fixes f :: "real^'n \<Rightarrow> real^'n"
+ shows "orthogonal_transformation f \<Longrightarrow> \<bar>det (matrix f)\<bar> = 1"
+ using%unimportant det_orthogonal_matrix orthogonal_transformation_matrix by fastforce
+
+subsection%important \<open>Rotation, reflection, rotoinversion\<close>
+
+definition%important "rotation_matrix Q \<longleftrightarrow> orthogonal_matrix Q \<and> det Q = 1"
+definition%important "rotoinversion_matrix Q \<longleftrightarrow> orthogonal_matrix Q \<and> det Q = - 1"
+
+lemma%important orthogonal_rotation_or_rotoinversion:
+ fixes Q :: "'a::linordered_idom^'n^'n"
+ shows " orthogonal_matrix Q \<longleftrightarrow> rotation_matrix Q \<or> rotoinversion_matrix Q"
+ by%unimportant (metis rotoinversion_matrix_def rotation_matrix_def det_orthogonal_matrix)
+
text\<open> Slightly stronger results giving rotation, but only in two or more dimensions\<close>
lemma%unimportant rotation_matrix_exists_basis:
@@ -1360,8 +1024,10 @@
then show ?thesis
using \<open>A *v axis k 1 = a\<close> that by auto
next
- obtain j where "j \<noteq> k"
- by (metis (full_types) 2 card_2_exists ex_card)
+ from ex_card[OF 2] obtain h i::'n where "h \<noteq> i"
+ by (auto simp add: eval_nat_numeral card_Suc_eq)
+ then obtain j where "j \<noteq> k"
+ by (metis (full_types))
let ?TA = "transpose A"
let ?A = "\<chi> i. if i = j then - 1 *\<^sub>R (?TA $ i) else ?TA $i"
assume "rotoinversion_matrix A"
--- a/src/HOL/Analysis/Linear_Algebra.thy Wed Jan 16 16:50:35 2019 -0500
+++ b/src/HOL/Analysis/Linear_Algebra.thy Wed Jan 16 18:14:02 2019 -0500
@@ -30,6 +30,79 @@
lemma finite_Atleast_Atmost_nat[simp]: "finite {f x |x. x \<in> (UNIV::'a::finite set)}"
using finite finite_image_set by blast
+lemma substdbasis_expansion_unique:
+ includes inner_syntax
+ assumes d: "d \<subseteq> Basis"
+ shows "(\<Sum>i\<in>d. f i *\<^sub>R i) = (x::'a::euclidean_space) \<longleftrightarrow>
+ (\<forall>i\<in>Basis. (i \<in> d \<longrightarrow> f i = x \<bullet> i) \<and> (i \<notin> d \<longrightarrow> x \<bullet> i = 0))"
+proof -
+ have *: "\<And>x a b P. x * (if P then a else b) = (if P then x * a else x * b)"
+ by auto
+ have **: "finite d"
+ by (auto intro: finite_subset[OF assms])
+ 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)"
+ using d
+ by (auto intro!: sum.cong simp: inner_Basis inner_sum_left)
+ show ?thesis
+ unfolding euclidean_eq_iff[where 'a='a] by (auto simp: sum.delta[OF **] ***)
+qed
+
+lemma independent_substdbasis: "d \<subseteq> Basis \<Longrightarrow> independent d"
+ by (rule independent_mono[OF independent_Basis])
+
+lemma sum_not_0: "sum f A \<noteq> 0 \<Longrightarrow> \<exists>a \<in> A. f a \<noteq> 0"
+ by (rule ccontr) auto
+
+lemma subset_translation_eq [simp]:
+ fixes a :: "'a::real_vector" shows "(+) a ` s \<subseteq> (+) a ` t \<longleftrightarrow> s \<subseteq> t"
+ by auto
+
+lemma translate_inj_on:
+ fixes A :: "'a::ab_group_add set"
+ shows "inj_on (\<lambda>x. a + x) A"
+ unfolding inj_on_def by auto
+
+lemma translation_assoc:
+ fixes a b :: "'a::ab_group_add"
+ shows "(\<lambda>x. b + x) ` ((\<lambda>x. a + x) ` S) = (\<lambda>x. (a + b) + x) ` S"
+ by auto
+
+lemma translation_invert:
+ fixes a :: "'a::ab_group_add"
+ assumes "(\<lambda>x. a + x) ` A = (\<lambda>x. a + x) ` B"
+ shows "A = B"
+proof -
+ have "(\<lambda>x. -a + x) ` ((\<lambda>x. a + x) ` A) = (\<lambda>x. - a + x) ` ((\<lambda>x. a + x) ` B)"
+ using assms by auto
+ then show ?thesis
+ using translation_assoc[of "-a" a A] translation_assoc[of "-a" a B] by auto
+qed
+
+lemma translation_galois:
+ fixes a :: "'a::ab_group_add"
+ shows "T = ((\<lambda>x. a + x) ` S) \<longleftrightarrow> S = ((\<lambda>x. (- a) + x) ` T)"
+ using translation_assoc[of "-a" a S]
+ apply auto
+ using translation_assoc[of a "-a" T]
+ apply auto
+ done
+
+lemma translation_inverse_subset:
+ assumes "((\<lambda>x. - a + x) ` V) \<le> (S :: 'n::ab_group_add set)"
+ shows "V \<le> ((\<lambda>x. a + x) ` S)"
+proof -
+ {
+ fix x
+ assume "x \<in> V"
+ then have "x-a \<in> S" using assms by auto
+ then have "x \<in> {a + v |v. v \<in> S}"
+ apply auto
+ apply (rule exI[of _ "x-a"], simp)
+ done
+ then have "x \<in> ((\<lambda>x. a+x) ` S)" by auto
+ }
+ then show ?thesis by auto
+qed
subsection%unimportant \<open>More interesting properties of the norm\<close>
@@ -224,6 +297,66 @@
qed
+subsection%important \<open>Orthogonality of a transformation\<close>
+
+definition%important "orthogonal_transformation f \<longleftrightarrow> linear f \<and> (\<forall>v w. f v \<bullet> f w = v \<bullet> w)"
+
+lemma%unimportant orthogonal_transformation:
+ "orthogonal_transformation f \<longleftrightarrow> linear f \<and> (\<forall>v. norm (f v) = norm v)"
+ unfolding orthogonal_transformation_def
+ apply auto
+ apply (erule_tac x=v in allE)+
+ apply (simp add: norm_eq_sqrt_inner)
+ apply (simp add: dot_norm linear_add[symmetric])
+ done
+
+lemma%unimportant orthogonal_transformation_id [simp]: "orthogonal_transformation (\<lambda>x. x)"
+ by (simp add: linear_iff orthogonal_transformation_def)
+
+lemma%unimportant orthogonal_orthogonal_transformation:
+ "orthogonal_transformation f \<Longrightarrow> orthogonal (f x) (f y) \<longleftrightarrow> orthogonal x y"
+ by (simp add: orthogonal_def orthogonal_transformation_def)
+
+lemma%unimportant orthogonal_transformation_compose:
+ "\<lbrakk>orthogonal_transformation f; orthogonal_transformation g\<rbrakk> \<Longrightarrow> orthogonal_transformation(f \<circ> g)"
+ by (auto simp: orthogonal_transformation_def linear_compose)
+
+lemma%unimportant orthogonal_transformation_neg:
+ "orthogonal_transformation(\<lambda>x. -(f x)) \<longleftrightarrow> orthogonal_transformation f"
+ by (auto simp: orthogonal_transformation_def dest: linear_compose_neg)
+
+lemma%unimportant orthogonal_transformation_scaleR: "orthogonal_transformation f \<Longrightarrow> f (c *\<^sub>R v) = c *\<^sub>R f v"
+ by (simp add: linear_iff orthogonal_transformation_def)
+
+lemma%unimportant orthogonal_transformation_linear:
+ "orthogonal_transformation f \<Longrightarrow> linear f"
+ by (simp add: orthogonal_transformation_def)
+
+lemma%unimportant orthogonal_transformation_inj:
+ "orthogonal_transformation f \<Longrightarrow> inj f"
+ unfolding orthogonal_transformation_def inj_on_def
+ by (metis vector_eq)
+
+lemma%unimportant orthogonal_transformation_surj:
+ "orthogonal_transformation f \<Longrightarrow> surj f"
+ for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space"
+ by (simp add: linear_injective_imp_surjective orthogonal_transformation_inj orthogonal_transformation_linear)
+
+lemma%unimportant orthogonal_transformation_bij:
+ "orthogonal_transformation f \<Longrightarrow> bij f"
+ for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space"
+ by (simp add: bij_def orthogonal_transformation_inj orthogonal_transformation_surj)
+
+lemma%unimportant orthogonal_transformation_inv:
+ "orthogonal_transformation f \<Longrightarrow> orthogonal_transformation (inv f)"
+ for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space"
+ by (metis (no_types, hide_lams) bijection.inv_right bijection_def inj_linear_imp_inv_linear orthogonal_transformation orthogonal_transformation_bij orthogonal_transformation_inj)
+
+lemma%unimportant orthogonal_transformation_norm:
+ "orthogonal_transformation f \<Longrightarrow> norm (f x) = norm x"
+ by (metis orthogonal_transformation)
+
+
subsection \<open>Bilinear functions\<close>
definition%important
@@ -1210,4 +1343,540 @@
qed
qed
+
+subsection\<open>Properties of special hyperplanes\<close>
+
+lemma subspace_hyperplane: "subspace {x. a \<bullet> x = 0}"
+ by (simp add: subspace_def inner_right_distrib)
+
+lemma subspace_hyperplane2: "subspace {x. x \<bullet> a = 0}"
+ by (simp add: inner_commute inner_right_distrib subspace_def)
+
+lemma special_hyperplane_span:
+ fixes S :: "'n::euclidean_space set"
+ assumes "k \<in> Basis"
+ shows "{x. k \<bullet> x = 0} = span (Basis - {k})"
+proof -
+ have *: "x \<in> span (Basis - {k})" if "k \<bullet> x = 0" for x
+ proof -
+ have "x = (\<Sum>b\<in>Basis. (x \<bullet> b) *\<^sub>R b)"
+ by (simp add: euclidean_representation)
+ also have "... = (\<Sum>b \<in> Basis - {k}. (x \<bullet> b) *\<^sub>R b)"
+ by (auto simp: sum.remove [of _ k] inner_commute assms that)
+ finally have "x = (\<Sum>b\<in>Basis - {k}. (x \<bullet> b) *\<^sub>R b)" .
+ then show ?thesis
+ by (simp add: span_finite)
+ qed
+ show ?thesis
+ apply (rule span_subspace [symmetric])
+ using assms
+ apply (auto simp: inner_not_same_Basis intro: * subspace_hyperplane)
+ done
+qed
+
+lemma dim_special_hyperplane:
+ fixes k :: "'n::euclidean_space"
+ shows "k \<in> Basis \<Longrightarrow> dim {x. k \<bullet> x = 0} = DIM('n) - 1"
+apply (simp add: special_hyperplane_span)
+apply (rule dim_unique [OF subset_refl])
+apply (auto simp: independent_substdbasis)
+apply (metis member_remove remove_def span_base)
+done
+
+proposition dim_hyperplane:
+ fixes a :: "'a::euclidean_space"
+ assumes "a \<noteq> 0"
+ shows "dim {x. a \<bullet> x = 0} = DIM('a) - 1"
+proof -
+ have span0: "span {x. a \<bullet> x = 0} = {x. a \<bullet> x = 0}"
+ by (rule span_unique) (auto simp: subspace_hyperplane)
+ then obtain B where "independent B"
+ and Bsub: "B \<subseteq> {x. a \<bullet> x = 0}"
+ and subspB: "{x. a \<bullet> x = 0} \<subseteq> span B"
+ and card0: "(card B = dim {x. a \<bullet> x = 0})"
+ and ortho: "pairwise orthogonal B"
+ using orthogonal_basis_exists by metis
+ with assms have "a \<notin> span B"
+ by (metis (mono_tags, lifting) span_eq inner_eq_zero_iff mem_Collect_eq span0)
+ then have ind: "independent (insert a B)"
+ by (simp add: \<open>independent B\<close> independent_insert)
+ have "finite B"
+ using \<open>independent B\<close> independent_bound by blast
+ have "UNIV \<subseteq> span (insert a B)"
+ proof fix y::'a
+ obtain r z where z: "y = r *\<^sub>R a + z" "a \<bullet> z = 0"
+ apply (rule_tac r="(a \<bullet> y) / (a \<bullet> a)" and z = "y - ((a \<bullet> y) / (a \<bullet> a)) *\<^sub>R a" in that)
+ using assms
+ by (auto simp: algebra_simps)
+ show "y \<in> span (insert a B)"
+ by (metis (mono_tags, lifting) z Bsub span_eq_iff
+ add_diff_cancel_left' mem_Collect_eq span0 span_breakdown_eq span_subspace subspB)
+ qed
+ then have dima: "DIM('a) = dim(insert a B)"
+ by (metis independent_Basis span_Basis dim_eq_card top.extremum_uniqueI)
+ then show ?thesis
+ by (metis (mono_tags, lifting) Bsub Diff_insert_absorb \<open>a \<notin> span B\<close> ind card0
+ card_Diff_singleton dim_span indep_card_eq_dim_span insertI1 subsetCE
+ subspB)
+qed
+
+lemma lowdim_eq_hyperplane:
+ fixes S :: "'a::euclidean_space set"
+ assumes "dim S = DIM('a) - 1"
+ obtains a where "a \<noteq> 0" and "span S = {x. a \<bullet> x = 0}"
+proof -
+ have dimS: "dim S < DIM('a)"
+ by (simp add: assms)
+ then obtain b where b: "b \<noteq> 0" "span S \<subseteq> {a. b \<bullet> a = 0}"
+ using lowdim_subset_hyperplane [of S] by fastforce
+ show ?thesis
+ apply (rule that[OF b(1)])
+ apply (rule subspace_dim_equal)
+ by (auto simp: assms b dim_hyperplane dim_span subspace_hyperplane
+ subspace_span)
+qed
+
+lemma dim_eq_hyperplane:
+ fixes S :: "'n::euclidean_space set"
+ shows "dim S = DIM('n) - 1 \<longleftrightarrow> (\<exists>a. a \<noteq> 0 \<and> span S = {x. a \<bullet> x = 0})"
+by (metis One_nat_def dim_hyperplane dim_span lowdim_eq_hyperplane)
+
+
+subsection\<open> Orthogonal bases, Gram-Schmidt process, and related theorems\<close>
+
+lemma pairwise_orthogonal_independent:
+ assumes "pairwise orthogonal S" and "0 \<notin> S"
+ shows "independent S"
+proof -
+ have 0: "\<And>x y. \<lbrakk>x \<noteq> y; x \<in> S; y \<in> S\<rbrakk> \<Longrightarrow> x \<bullet> y = 0"
+ using assms by (simp add: pairwise_def orthogonal_def)
+ have "False" if "a \<in> S" and a: "a \<in> span (S - {a})" for a
+ proof -
+ obtain T U where "T \<subseteq> S - {a}" "a = (\<Sum>v\<in>T. U v *\<^sub>R v)"
+ using a by (force simp: span_explicit)
+ then have "a \<bullet> a = a \<bullet> (\<Sum>v\<in>T. U v *\<^sub>R v)"
+ by simp
+ also have "... = 0"
+ apply (simp add: inner_sum_right)
+ apply (rule comm_monoid_add_class.sum.neutral)
+ by (metis "0" DiffE \<open>T \<subseteq> S - {a}\<close> mult_not_zero singletonI subsetCE \<open>a \<in> S\<close>)
+ finally show ?thesis
+ using \<open>0 \<notin> S\<close> \<open>a \<in> S\<close> by auto
+ qed
+ then show ?thesis
+ by (force simp: dependent_def)
+qed
+
+lemma pairwise_orthogonal_imp_finite:
+ fixes S :: "'a::euclidean_space set"
+ assumes "pairwise orthogonal S"
+ shows "finite S"
+proof -
+ have "independent (S - {0})"
+ apply (rule pairwise_orthogonal_independent)
+ apply (metis Diff_iff assms pairwise_def)
+ by blast
+ then show ?thesis
+ by (meson independent_imp_finite infinite_remove)
+qed
+
+lemma subspace_orthogonal_to_vector: "subspace {y. orthogonal x y}"
+ by (simp add: subspace_def orthogonal_clauses)
+
+lemma subspace_orthogonal_to_vectors: "subspace {y. \<forall>x \<in> S. orthogonal x y}"
+ by (simp add: subspace_def orthogonal_clauses)
+
+lemma orthogonal_to_span:
+ assumes a: "a \<in> span S" and x: "\<And>y. y \<in> S \<Longrightarrow> orthogonal x y"
+ shows "orthogonal x a"
+ by (metis a orthogonal_clauses(1,2,4)
+ span_induct_alt x)
+
+proposition Gram_Schmidt_step:
+ fixes S :: "'a::euclidean_space set"
+ assumes S: "pairwise orthogonal S" and x: "x \<in> span S"
+ shows "orthogonal x (a - (\<Sum>b\<in>S. (b \<bullet> a / (b \<bullet> b)) *\<^sub>R b))"
+proof -
+ have "finite S"
+ by (simp add: S pairwise_orthogonal_imp_finite)
+ have "orthogonal (a - (\<Sum>b\<in>S. (b \<bullet> a / (b \<bullet> b)) *\<^sub>R b)) x"
+ if "x \<in> S" for x
+ proof -
+ have "a \<bullet> x = (\<Sum>y\<in>S. if y = x then y \<bullet> a else 0)"
+ by (simp add: \<open>finite S\<close> inner_commute sum.delta that)
+ also have "... = (\<Sum>b\<in>S. b \<bullet> a * (b \<bullet> x) / (b \<bullet> b))"
+ apply (rule sum.cong [OF refl], simp)
+ by (meson S orthogonal_def pairwise_def that)
+ finally show ?thesis
+ by (simp add: orthogonal_def algebra_simps inner_sum_left)
+ qed
+ then show ?thesis
+ using orthogonal_to_span orthogonal_commute x by blast
+qed
+
+
+lemma orthogonal_extension_aux:
+ fixes S :: "'a::euclidean_space set"
+ assumes "finite T" "finite S" "pairwise orthogonal S"
+ shows "\<exists>U. pairwise orthogonal (S \<union> U) \<and> span (S \<union> U) = span (S \<union> T)"
+using assms
+proof (induction arbitrary: S)
+ case empty then show ?case
+ by simp (metis sup_bot_right)
+next
+ case (insert a T)
+ have 0: "\<And>x y. \<lbrakk>x \<noteq> y; x \<in> S; y \<in> S\<rbrakk> \<Longrightarrow> x \<bullet> y = 0"
+ using insert by (simp add: pairwise_def orthogonal_def)
+ define a' where "a' = a - (\<Sum>b\<in>S. (b \<bullet> a / (b \<bullet> b)) *\<^sub>R b)"
+ obtain U where orthU: "pairwise orthogonal (S \<union> insert a' U)"
+ and spanU: "span (insert a' S \<union> U) = span (insert a' S \<union> T)"
+ by (rule exE [OF insert.IH [of "insert a' S"]])
+ (auto simp: Gram_Schmidt_step a'_def insert.prems orthogonal_commute
+ pairwise_orthogonal_insert span_clauses)
+ have orthS: "\<And>x. x \<in> S \<Longrightarrow> a' \<bullet> x = 0"
+ apply (simp add: a'_def)
+ using Gram_Schmidt_step [OF \<open>pairwise orthogonal S\<close>]
+ apply (force simp: orthogonal_def inner_commute span_superset [THEN subsetD])
+ done
+ have "span (S \<union> insert a' U) = span (insert a' (S \<union> T))"
+ using spanU by simp
+ also have "... = span (insert a (S \<union> T))"
+ apply (rule eq_span_insert_eq)
+ apply (simp add: a'_def span_neg span_sum span_base span_mul)
+ done
+ also have "... = span (S \<union> insert a T)"
+ by simp
+ finally show ?case
+ by (rule_tac x="insert a' U" in exI) (use orthU in auto)
+qed
+
+
+proposition orthogonal_extension:
+ fixes S :: "'a::euclidean_space set"
+ assumes S: "pairwise orthogonal S"
+ obtains U where "pairwise orthogonal (S \<union> U)" "span (S \<union> U) = span (S \<union> T)"
+proof -
+ obtain B where "finite B" "span B = span T"
+ using basis_subspace_exists [of "span T"] subspace_span by metis
+ with orthogonal_extension_aux [of B S]
+ obtain U where "pairwise orthogonal (S \<union> U)" "span (S \<union> U) = span (S \<union> B)"
+ using assms pairwise_orthogonal_imp_finite by auto
+ with \<open>span B = span T\<close> show ?thesis
+ by (rule_tac U=U in that) (auto simp: span_Un)
+qed
+
+corollary%unimportant orthogonal_extension_strong:
+ fixes S :: "'a::euclidean_space set"
+ assumes S: "pairwise orthogonal S"
+ obtains U where "U \<inter> (insert 0 S) = {}" "pairwise orthogonal (S \<union> U)"
+ "span (S \<union> U) = span (S \<union> T)"
+proof -
+ obtain U where "pairwise orthogonal (S \<union> U)" "span (S \<union> U) = span (S \<union> T)"
+ using orthogonal_extension assms by blast
+ then show ?thesis
+ apply (rule_tac U = "U - (insert 0 S)" in that)
+ apply blast
+ apply (force simp: pairwise_def)
+ apply (metis Un_Diff_cancel Un_insert_left span_redundant span_zero)
+ done
+qed
+
+subsection\<open>Decomposing a vector into parts in orthogonal subspaces\<close>
+
+text\<open>existence of orthonormal basis for a subspace.\<close>
+
+lemma orthogonal_spanningset_subspace:
+ fixes S :: "'a :: euclidean_space set"
+ assumes "subspace S"
+ obtains B where "B \<subseteq> S" "pairwise orthogonal B" "span B = S"
+proof -
+ obtain B where "B \<subseteq> S" "independent B" "S \<subseteq> span B" "card B = dim S"
+ using basis_exists by blast
+ with orthogonal_extension [of "{}" B]
+ show ?thesis
+ by (metis Un_empty_left assms pairwise_empty span_superset span_subspace that)
+qed
+
+lemma orthogonal_basis_subspace:
+ fixes S :: "'a :: euclidean_space set"
+ assumes "subspace S"
+ obtains B where "0 \<notin> B" "B \<subseteq> S" "pairwise orthogonal B" "independent B"
+ "card B = dim S" "span B = S"
+proof -
+ obtain B where "B \<subseteq> S" "pairwise orthogonal B" "span B = S"
+ using assms orthogonal_spanningset_subspace by blast
+ then show ?thesis
+ apply (rule_tac B = "B - {0}" in that)
+ apply (auto simp: indep_card_eq_dim_span pairwise_subset pairwise_orthogonal_independent elim: pairwise_subset)
+ done
+qed
+
+proposition orthonormal_basis_subspace:
+ fixes S :: "'a :: euclidean_space set"
+ assumes "subspace S"
+ obtains B where "B \<subseteq> S" "pairwise orthogonal B"
+ and "\<And>x. x \<in> B \<Longrightarrow> norm x = 1"
+ and "independent B" "card B = dim S" "span B = S"
+proof -
+ obtain B where "0 \<notin> B" "B \<subseteq> S"
+ and orth: "pairwise orthogonal B"
+ and "independent B" "card B = dim S" "span B = S"
+ by (blast intro: orthogonal_basis_subspace [OF assms])
+ have 1: "(\<lambda>x. x /\<^sub>R norm x) ` B \<subseteq> S"
+ using \<open>span B = S\<close> span_superset span_mul by fastforce
+ have 2: "pairwise orthogonal ((\<lambda>x. x /\<^sub>R norm x) ` B)"
+ using orth by (force simp: pairwise_def orthogonal_clauses)
+ have 3: "\<And>x. x \<in> (\<lambda>x. x /\<^sub>R norm x) ` B \<Longrightarrow> norm x = 1"
+ by (metis (no_types, lifting) \<open>0 \<notin> B\<close> image_iff norm_sgn sgn_div_norm)
+ have 4: "independent ((\<lambda>x. x /\<^sub>R norm x) ` B)"
+ by (metis "2" "3" norm_zero pairwise_orthogonal_independent zero_neq_one)
+ have "inj_on (\<lambda>x. x /\<^sub>R norm x) B"
+ proof
+ fix x y
+ assume "x \<in> B" "y \<in> B" "x /\<^sub>R norm x = y /\<^sub>R norm y"
+ moreover have "\<And>i. i \<in> B \<Longrightarrow> norm (i /\<^sub>R norm i) = 1"
+ using 3 by blast
+ ultimately show "x = y"
+ by (metis norm_eq_1 orth orthogonal_clauses(7) orthogonal_commute orthogonal_def pairwise_def zero_neq_one)
+ qed
+ then have 5: "card ((\<lambda>x. x /\<^sub>R norm x) ` B) = dim S"
+ by (metis \<open>card B = dim S\<close> card_image)
+ have 6: "span ((\<lambda>x. x /\<^sub>R norm x) ` B) = S"
+ by (metis "1" "4" "5" assms card_eq_dim independent_imp_finite span_subspace)
+ show ?thesis
+ by (rule that [OF 1 2 3 4 5 6])
+qed
+
+
+proposition%unimportant orthogonal_to_subspace_exists_gen:
+ fixes S :: "'a :: euclidean_space set"
+ assumes "span S \<subset> span T"
+ obtains x where "x \<noteq> 0" "x \<in> span T" "\<And>y. y \<in> span S \<Longrightarrow> orthogonal x y"
+proof -
+ obtain B where "B \<subseteq> span S" and orthB: "pairwise orthogonal B"
+ and "\<And>x. x \<in> B \<Longrightarrow> norm x = 1"
+ and "independent B" "card B = dim S" "span B = span S"
+ by (rule orthonormal_basis_subspace [of "span S", OF subspace_span])
+ (auto simp: dim_span)
+ with assms obtain u where spanBT: "span B \<subseteq> span T" and "u \<notin> span B" "u \<in> span T"
+ by auto
+ obtain C where orthBC: "pairwise orthogonal (B \<union> C)" and spanBC: "span (B \<union> C) = span (B \<union> {u})"
+ by (blast intro: orthogonal_extension [OF orthB])
+ show thesis
+ proof (cases "C \<subseteq> insert 0 B")
+ case True
+ then have "C \<subseteq> span B"
+ using span_eq
+ by (metis span_insert_0 subset_trans)
+ moreover have "u \<in> span (B \<union> C)"
+ using \<open>span (B \<union> C) = span (B \<union> {u})\<close> span_superset by force
+ ultimately show ?thesis
+ using True \<open>u \<notin> span B\<close>
+ by (metis Un_insert_left span_insert_0 sup.orderE)
+ next
+ case False
+ then obtain x where "x \<in> C" "x \<noteq> 0" "x \<notin> B"
+ by blast
+ then have "x \<in> span T"
+ by (metis (no_types, lifting) Un_insert_right Un_upper2 \<open>u \<in> span T\<close> spanBT spanBC
+ \<open>u \<in> span T\<close> insert_subset span_superset span_mono
+ span_span subsetCE subset_trans sup_bot.comm_neutral)
+ moreover have "orthogonal x y" if "y \<in> span B" for y
+ using that
+ proof (rule span_induct)
+ show "subspace {a. orthogonal x a}"
+ by (simp add: subspace_orthogonal_to_vector)
+ show "\<And>b. b \<in> B \<Longrightarrow> orthogonal x b"
+ by (metis Un_iff \<open>x \<in> C\<close> \<open>x \<notin> B\<close> orthBC pairwise_def)
+ qed
+ ultimately show ?thesis
+ using \<open>x \<noteq> 0\<close> that \<open>span B = span S\<close> by auto
+ qed
+qed
+
+corollary%unimportant orthogonal_to_subspace_exists:
+ fixes S :: "'a :: euclidean_space set"
+ assumes "dim S < DIM('a)"
+ obtains x where "x \<noteq> 0" "\<And>y. y \<in> span S \<Longrightarrow> orthogonal x y"
+proof -
+have "span S \<subset> UNIV"
+ by (metis (mono_tags) UNIV_I assms inner_eq_zero_iff less_le lowdim_subset_hyperplane
+ mem_Collect_eq top.extremum_strict top.not_eq_extremum)
+ with orthogonal_to_subspace_exists_gen [of S UNIV] that show ?thesis
+ by (auto simp: span_UNIV)
+qed
+
+corollary%unimportant orthogonal_to_vector_exists:
+ fixes x :: "'a :: euclidean_space"
+ assumes "2 \<le> DIM('a)"
+ obtains y where "y \<noteq> 0" "orthogonal x y"
+proof -
+ have "dim {x} < DIM('a)"
+ using assms by auto
+ then show thesis
+ by (rule orthogonal_to_subspace_exists) (simp add: orthogonal_commute span_base that)
+qed
+
+proposition%unimportant orthogonal_subspace_decomp_exists:
+ fixes S :: "'a :: euclidean_space set"
+ obtains y z
+ where "y \<in> span S"
+ and "\<And>w. w \<in> span S \<Longrightarrow> orthogonal z w"
+ and "x = y + z"
+proof -
+ obtain T where "0 \<notin> T" "T \<subseteq> span S" "pairwise orthogonal T" "independent T"
+ "card T = dim (span S)" "span T = span S"
+ using orthogonal_basis_subspace subspace_span by blast
+ let ?a = "\<Sum>b\<in>T. (b \<bullet> x / (b \<bullet> b)) *\<^sub>R b"
+ have orth: "orthogonal (x - ?a) w" if "w \<in> span S" for w
+ by (simp add: Gram_Schmidt_step \<open>pairwise orthogonal T\<close> \<open>span T = span S\<close>
+ orthogonal_commute that)
+ show ?thesis
+ apply (rule_tac y = "?a" and z = "x - ?a" in that)
+ apply (meson \<open>T \<subseteq> span S\<close> span_scale span_sum subsetCE)
+ apply (fact orth, simp)
+ done
+qed
+
+lemma orthogonal_subspace_decomp_unique:
+ fixes S :: "'a :: euclidean_space set"
+ assumes "x + y = x' + y'"
+ and ST: "x \<in> span S" "x' \<in> span S" "y \<in> span T" "y' \<in> span T"
+ and orth: "\<And>a b. \<lbrakk>a \<in> S; b \<in> T\<rbrakk> \<Longrightarrow> orthogonal a b"
+ shows "x = x' \<and> y = y'"
+proof -
+ have "x + y - y' = x'"
+ by (simp add: assms)
+ moreover have "\<And>a b. \<lbrakk>a \<in> span S; b \<in> span T\<rbrakk> \<Longrightarrow> orthogonal a b"
+ by (meson orth orthogonal_commute orthogonal_to_span)
+ ultimately have "0 = x' - x"
+ by (metis (full_types) add_diff_cancel_left' ST diff_right_commute orthogonal_clauses(10) orthogonal_clauses(5) orthogonal_self)
+ with assms show ?thesis by auto
+qed
+
+lemma vector_in_orthogonal_spanningset:
+ fixes a :: "'a::euclidean_space"
+ obtains S where "a \<in> S" "pairwise orthogonal S" "span S = UNIV"
+ by (metis UNIV_I Un_iff empty_iff insert_subset orthogonal_extension pairwise_def
+ pairwise_orthogonal_insert span_UNIV subsetI subset_antisym)
+
+lemma vector_in_orthogonal_basis:
+ fixes a :: "'a::euclidean_space"
+ assumes "a \<noteq> 0"
+ obtains S where "a \<in> S" "0 \<notin> S" "pairwise orthogonal S" "independent S" "finite S"
+ "span S = UNIV" "card S = DIM('a)"
+proof -
+ obtain S where S: "a \<in> S" "pairwise orthogonal S" "span S = UNIV"
+ using vector_in_orthogonal_spanningset .
+ show thesis
+ proof
+ show "pairwise orthogonal (S - {0})"
+ using pairwise_mono S(2) by blast
+ show "independent (S - {0})"
+ by (simp add: \<open>pairwise orthogonal (S - {0})\<close> pairwise_orthogonal_independent)
+ show "finite (S - {0})"
+ using \<open>independent (S - {0})\<close> independent_imp_finite by blast
+ show "card (S - {0}) = DIM('a)"
+ using span_delete_0 [of S] S
+ by (simp add: \<open>independent (S - {0})\<close> indep_card_eq_dim_span dim_UNIV)
+ qed (use S \<open>a \<noteq> 0\<close> in auto)
+qed
+
+lemma vector_in_orthonormal_basis:
+ fixes a :: "'a::euclidean_space"
+ assumes "norm a = 1"
+ obtains S where "a \<in> S" "pairwise orthogonal S" "\<And>x. x \<in> S \<Longrightarrow> norm x = 1"
+ "independent S" "card S = DIM('a)" "span S = UNIV"
+proof -
+ have "a \<noteq> 0"
+ using assms by auto
+ then obtain S where "a \<in> S" "0 \<notin> S" "finite S"
+ and S: "pairwise orthogonal S" "independent S" "span S = UNIV" "card S = DIM('a)"
+ by (metis vector_in_orthogonal_basis)
+ let ?S = "(\<lambda>x. x /\<^sub>R norm x) ` S"
+ show thesis
+ proof
+ show "a \<in> ?S"
+ using \<open>a \<in> S\<close> assms image_iff by fastforce
+ next
+ show "pairwise orthogonal ?S"
+ using \<open>pairwise orthogonal S\<close> by (auto simp: pairwise_def orthogonal_def)
+ show "\<And>x. x \<in> (\<lambda>x. x /\<^sub>R norm x) ` S \<Longrightarrow> norm x = 1"
+ using \<open>0 \<notin> S\<close> by (auto simp: divide_simps)
+ then show "independent ?S"
+ by (metis \<open>pairwise orthogonal ((\<lambda>x. x /\<^sub>R norm x) ` S)\<close> norm_zero pairwise_orthogonal_independent zero_neq_one)
+ have "inj_on (\<lambda>x. x /\<^sub>R norm x) S"
+ unfolding inj_on_def
+ by (metis (full_types) S(1) \<open>0 \<notin> S\<close> inverse_nonzero_iff_nonzero norm_eq_zero orthogonal_scaleR orthogonal_self pairwise_def)
+ then show "card ?S = DIM('a)"
+ by (simp add: card_image S)
+ show "span ?S = UNIV"
+ by (metis (no_types) \<open>0 \<notin> S\<close> \<open>finite S\<close> \<open>span S = UNIV\<close>
+ field_class.field_inverse_zero inverse_inverse_eq less_irrefl span_image_scale
+ zero_less_norm_iff)
+ qed
+qed
+
+proposition dim_orthogonal_sum:
+ fixes A :: "'a::euclidean_space set"
+ assumes "\<And>x y. \<lbrakk>x \<in> A; y \<in> B\<rbrakk> \<Longrightarrow> x \<bullet> y = 0"
+ shows "dim(A \<union> B) = dim A + dim B"
+proof -
+ have 1: "\<And>x y. \<lbrakk>x \<in> span A; y \<in> B\<rbrakk> \<Longrightarrow> x \<bullet> y = 0"
+ by (erule span_induct [OF _ subspace_hyperplane2]; simp add: assms)
+ have "\<And>x y. \<lbrakk>x \<in> span A; y \<in> span B\<rbrakk> \<Longrightarrow> x \<bullet> y = 0"
+ using 1 by (simp add: span_induct [OF _ subspace_hyperplane])
+ then have 0: "\<And>x y. \<lbrakk>x \<in> span A; y \<in> span B\<rbrakk> \<Longrightarrow> x \<bullet> y = 0"
+ by simp
+ have "dim(A \<union> B) = dim (span (A \<union> B))"
+ by (simp add: dim_span)
+ also have "span (A \<union> B) = ((\<lambda>(a, b). a + b) ` (span A \<times> span B))"
+ by (auto simp add: span_Un image_def)
+ also have "dim \<dots> = dim {x + y |x y. x \<in> span A \<and> y \<in> span B}"
+ by (auto intro!: arg_cong [where f=dim])
+ also have "... = dim {x + y |x y. x \<in> span A \<and> y \<in> span B} + dim(span A \<inter> span B)"
+ by (auto simp: dest: 0)
+ also have "... = dim (span A) + dim (span B)"
+ by (rule dim_sums_Int) (auto simp: subspace_span)
+ also have "... = dim A + dim B"
+ by (simp add: dim_span)
+ finally show ?thesis .
+qed
+
+lemma dim_subspace_orthogonal_to_vectors:
+ fixes A :: "'a::euclidean_space set"
+ assumes "subspace A" "subspace B" "A \<subseteq> B"
+ shows "dim {y \<in> B. \<forall>x \<in> A. orthogonal x y} + dim A = dim B"
+proof -
+ have "dim (span ({y \<in> B. \<forall>x\<in>A. orthogonal x y} \<union> A)) = dim (span B)"
+ proof (rule arg_cong [where f=dim, OF subset_antisym])
+ show "span ({y \<in> B. \<forall>x\<in>A. orthogonal x y} \<union> A) \<subseteq> span B"
+ by (simp add: \<open>A \<subseteq> B\<close> Collect_restrict span_mono)
+ next
+ have *: "x \<in> span ({y \<in> B. \<forall>x\<in>A. orthogonal x y} \<union> A)"
+ if "x \<in> B" for x
+ proof -
+ obtain y z where "x = y + z" "y \<in> span A" and orth: "\<And>w. w \<in> span A \<Longrightarrow> orthogonal z w"
+ using orthogonal_subspace_decomp_exists [of A x] that by auto
+ have "y \<in> span B"
+ using \<open>y \<in> span A\<close> assms(3) span_mono by blast
+ then have "z \<in> {a \<in> B. \<forall>x. x \<in> A \<longrightarrow> orthogonal x a}"
+ apply simp
+ using \<open>x = y + z\<close> assms(1) assms(2) orth orthogonal_commute span_add_eq
+ span_eq_iff that by blast
+ then have z: "z \<in> span {y \<in> B. \<forall>x\<in>A. orthogonal x y}"
+ by (meson span_superset subset_iff)
+ then show ?thesis
+ apply (auto simp: span_Un image_def \<open>x = y + z\<close> \<open>y \<in> span A\<close>)
+ using \<open>y \<in> span A\<close> add.commute by blast
+ qed
+ show "span B \<subseteq> span ({y \<in> B. \<forall>x\<in>A. orthogonal x y} \<union> A)"
+ by (rule span_minimal)
+ (auto intro: * span_minimal simp: subspace_span)
+ qed
+ then show ?thesis
+ by (metis (no_types, lifting) dim_orthogonal_sum dim_span mem_Collect_eq
+ orthogonal_commute orthogonal_def)
+qed
+
end
--- a/src/HOL/Analysis/Starlike.thy Wed Jan 16 16:50:35 2019 -0500
+++ b/src/HOL/Analysis/Starlike.thy Wed Jan 16 18:14:02 2019 -0500
@@ -5469,103 +5469,6 @@
(if a = 0 \<and> r > 0 then -1 else DIM('a))"
using aff_dim_halfspace_le [of "-a" "-r"] by simp
-subsection\<open>Properties of special hyperplanes\<close>
-
-lemma subspace_hyperplane: "subspace {x. a \<bullet> x = 0}"
- by (simp add: subspace_def inner_right_distrib)
-
-lemma subspace_hyperplane2: "subspace {x. x \<bullet> a = 0}"
- by (simp add: inner_commute inner_right_distrib subspace_def)
-
-lemma special_hyperplane_span:
- fixes S :: "'n::euclidean_space set"
- assumes "k \<in> Basis"
- shows "{x. k \<bullet> x = 0} = span (Basis - {k})"
-proof -
- have *: "x \<in> span (Basis - {k})" if "k \<bullet> x = 0" for x
- proof -
- have "x = (\<Sum>b\<in>Basis. (x \<bullet> b) *\<^sub>R b)"
- by (simp add: euclidean_representation)
- also have "... = (\<Sum>b \<in> Basis - {k}. (x \<bullet> b) *\<^sub>R b)"
- by (auto simp: sum.remove [of _ k] inner_commute assms that)
- finally have "x = (\<Sum>b\<in>Basis - {k}. (x \<bullet> b) *\<^sub>R b)" .
- then show ?thesis
- by (simp add: span_finite)
- qed
- show ?thesis
- apply (rule span_subspace [symmetric])
- using assms
- apply (auto simp: inner_not_same_Basis intro: * subspace_hyperplane)
- done
-qed
-
-lemma dim_special_hyperplane:
- fixes k :: "'n::euclidean_space"
- shows "k \<in> Basis \<Longrightarrow> dim {x. k \<bullet> x = 0} = DIM('n) - 1"
-apply (simp add: special_hyperplane_span)
-apply (rule dim_unique [OF subset_refl])
-apply (auto simp: independent_substdbasis)
-apply (metis member_remove remove_def span_base)
-done
-
-proposition dim_hyperplane:
- fixes a :: "'a::euclidean_space"
- assumes "a \<noteq> 0"
- shows "dim {x. a \<bullet> x = 0} = DIM('a) - 1"
-proof -
- have span0: "span {x. a \<bullet> x = 0} = {x. a \<bullet> x = 0}"
- by (rule span_unique) (auto simp: subspace_hyperplane)
- then obtain B where "independent B"
- and Bsub: "B \<subseteq> {x. a \<bullet> x = 0}"
- and subspB: "{x. a \<bullet> x = 0} \<subseteq> span B"
- and card0: "(card B = dim {x. a \<bullet> x = 0})"
- and ortho: "pairwise orthogonal B"
- using orthogonal_basis_exists by metis
- with assms have "a \<notin> span B"
- by (metis (mono_tags, lifting) span_eq inner_eq_zero_iff mem_Collect_eq span0)
- then have ind: "independent (insert a B)"
- by (simp add: \<open>independent B\<close> independent_insert)
- have "finite B"
- using \<open>independent B\<close> independent_bound by blast
- have "UNIV \<subseteq> span (insert a B)"
- proof fix y::'a
- obtain r z where z: "y = r *\<^sub>R a + z" "a \<bullet> z = 0"
- apply (rule_tac r="(a \<bullet> y) / (a \<bullet> a)" and z = "y - ((a \<bullet> y) / (a \<bullet> a)) *\<^sub>R a" in that)
- using assms
- by (auto simp: algebra_simps)
- show "y \<in> span (insert a B)"
- by (metis (mono_tags, lifting) z Bsub span_eq_iff
- add_diff_cancel_left' mem_Collect_eq span0 span_breakdown_eq span_subspace subspB)
- qed
- then have dima: "DIM('a) = dim(insert a B)"
- by (metis independent_Basis span_Basis dim_eq_card top.extremum_uniqueI)
- then show ?thesis
- by (metis (mono_tags, lifting) Bsub Diff_insert_absorb \<open>a \<notin> span B\<close> ind card0
- card_Diff_singleton dim_span indep_card_eq_dim_span insertI1 subsetCE
- subspB)
-qed
-
-lemma lowdim_eq_hyperplane:
- fixes S :: "'a::euclidean_space set"
- assumes "dim S = DIM('a) - 1"
- obtains a where "a \<noteq> 0" and "span S = {x. a \<bullet> x = 0}"
-proof -
- have dimS: "dim S < DIM('a)"
- by (simp add: assms)
- then obtain b where b: "b \<noteq> 0" "span S \<subseteq> {a. b \<bullet> a = 0}"
- using lowdim_subset_hyperplane [of S] by fastforce
- show ?thesis
- apply (rule that[OF b(1)])
- apply (rule subspace_dim_equal)
- by (auto simp: assms b dim_hyperplane dim_span subspace_hyperplane
- subspace_span)
-qed
-
-lemma dim_eq_hyperplane:
- fixes S :: "'n::euclidean_space set"
- shows "dim S = DIM('n) - 1 \<longleftrightarrow> (\<exists>a. a \<noteq> 0 \<and> span S = {x. a \<bullet> x = 0})"
-by (metis One_nat_def dim_hyperplane dim_span lowdim_eq_hyperplane)
-
proposition aff_dim_eq_hyperplane:
fixes S :: "'a::euclidean_space set"
shows "aff_dim S = DIM('a) - 1 \<longleftrightarrow> (\<exists>a b. a \<noteq> 0 \<and> affine hull S = {x. a \<bullet> x = b})"
@@ -6436,444 +6339,6 @@
shows "aff_dim S < DIM('a) \<longleftrightarrow> (affine hull S \<noteq> UNIV)"
by (metis (no_types) aff_dim_affine_hull aff_dim_le_DIM aff_dim_UNIV affine_hull_UNIV less_le)
-
-subsection\<open> Orthogonal bases, Gram-Schmidt process, and related theorems\<close>
-
-lemma pairwise_orthogonal_independent:
- assumes "pairwise orthogonal S" and "0 \<notin> S"
- shows "independent S"
-proof -
- have 0: "\<And>x y. \<lbrakk>x \<noteq> y; x \<in> S; y \<in> S\<rbrakk> \<Longrightarrow> x \<bullet> y = 0"
- using assms by (simp add: pairwise_def orthogonal_def)
- have "False" if "a \<in> S" and a: "a \<in> span (S - {a})" for a
- proof -
- obtain T U where "T \<subseteq> S - {a}" "a = (\<Sum>v\<in>T. U v *\<^sub>R v)"
- using a by (force simp: span_explicit)
- then have "a \<bullet> a = a \<bullet> (\<Sum>v\<in>T. U v *\<^sub>R v)"
- by simp
- also have "... = 0"
- apply (simp add: inner_sum_right)
- apply (rule comm_monoid_add_class.sum.neutral)
- by (metis "0" DiffE \<open>T \<subseteq> S - {a}\<close> mult_not_zero singletonI subsetCE \<open>a \<in> S\<close>)
- finally show ?thesis
- using \<open>0 \<notin> S\<close> \<open>a \<in> S\<close> by auto
- qed
- then show ?thesis
- by (force simp: dependent_def)
-qed
-
-lemma pairwise_orthogonal_imp_finite:
- fixes S :: "'a::euclidean_space set"
- assumes "pairwise orthogonal S"
- shows "finite S"
-proof -
- have "independent (S - {0})"
- apply (rule pairwise_orthogonal_independent)
- apply (metis Diff_iff assms pairwise_def)
- by blast
- then show ?thesis
- by (meson independent_imp_finite infinite_remove)
-qed
-
-lemma subspace_orthogonal_to_vector: "subspace {y. orthogonal x y}"
- by (simp add: subspace_def orthogonal_clauses)
-
-lemma subspace_orthogonal_to_vectors: "subspace {y. \<forall>x \<in> S. orthogonal x y}"
- by (simp add: subspace_def orthogonal_clauses)
-
-lemma orthogonal_to_span:
- assumes a: "a \<in> span S" and x: "\<And>y. y \<in> S \<Longrightarrow> orthogonal x y"
- shows "orthogonal x a"
- by (metis a orthogonal_clauses(1,2,4)
- span_induct_alt x)
-
-proposition Gram_Schmidt_step:
- fixes S :: "'a::euclidean_space set"
- assumes S: "pairwise orthogonal S" and x: "x \<in> span S"
- shows "orthogonal x (a - (\<Sum>b\<in>S. (b \<bullet> a / (b \<bullet> b)) *\<^sub>R b))"
-proof -
- have "finite S"
- by (simp add: S pairwise_orthogonal_imp_finite)
- have "orthogonal (a - (\<Sum>b\<in>S. (b \<bullet> a / (b \<bullet> b)) *\<^sub>R b)) x"
- if "x \<in> S" for x
- proof -
- have "a \<bullet> x = (\<Sum>y\<in>S. if y = x then y \<bullet> a else 0)"
- by (simp add: \<open>finite S\<close> inner_commute sum.delta that)
- also have "... = (\<Sum>b\<in>S. b \<bullet> a * (b \<bullet> x) / (b \<bullet> b))"
- apply (rule sum.cong [OF refl], simp)
- by (meson S orthogonal_def pairwise_def that)
- finally show ?thesis
- by (simp add: orthogonal_def algebra_simps inner_sum_left)
- qed
- then show ?thesis
- using orthogonal_to_span orthogonal_commute x by blast
-qed
-
-
-lemma orthogonal_extension_aux:
- fixes S :: "'a::euclidean_space set"
- assumes "finite T" "finite S" "pairwise orthogonal S"
- shows "\<exists>U. pairwise orthogonal (S \<union> U) \<and> span (S \<union> U) = span (S \<union> T)"
-using assms
-proof (induction arbitrary: S)
- case empty then show ?case
- by simp (metis sup_bot_right)
-next
- case (insert a T)
- have 0: "\<And>x y. \<lbrakk>x \<noteq> y; x \<in> S; y \<in> S\<rbrakk> \<Longrightarrow> x \<bullet> y = 0"
- using insert by (simp add: pairwise_def orthogonal_def)
- define a' where "a' = a - (\<Sum>b\<in>S. (b \<bullet> a / (b \<bullet> b)) *\<^sub>R b)"
- obtain U where orthU: "pairwise orthogonal (S \<union> insert a' U)"
- and spanU: "span (insert a' S \<union> U) = span (insert a' S \<union> T)"
- by (rule exE [OF insert.IH [of "insert a' S"]])
- (auto simp: Gram_Schmidt_step a'_def insert.prems orthogonal_commute
- pairwise_orthogonal_insert span_clauses)
- have orthS: "\<And>x. x \<in> S \<Longrightarrow> a' \<bullet> x = 0"
- apply (simp add: a'_def)
- using Gram_Schmidt_step [OF \<open>pairwise orthogonal S\<close>]
- apply (force simp: orthogonal_def inner_commute span_superset [THEN subsetD])
- done
- have "span (S \<union> insert a' U) = span (insert a' (S \<union> T))"
- using spanU by simp
- also have "... = span (insert a (S \<union> T))"
- apply (rule eq_span_insert_eq)
- apply (simp add: a'_def span_neg span_sum span_base span_mul)
- done
- also have "... = span (S \<union> insert a T)"
- by simp
- finally show ?case
- by (rule_tac x="insert a' U" in exI) (use orthU in auto)
-qed
-
-
-proposition orthogonal_extension:
- fixes S :: "'a::euclidean_space set"
- assumes S: "pairwise orthogonal S"
- obtains U where "pairwise orthogonal (S \<union> U)" "span (S \<union> U) = span (S \<union> T)"
-proof -
- obtain B where "finite B" "span B = span T"
- using basis_subspace_exists [of "span T"] subspace_span by metis
- with orthogonal_extension_aux [of B S]
- obtain U where "pairwise orthogonal (S \<union> U)" "span (S \<union> U) = span (S \<union> B)"
- using assms pairwise_orthogonal_imp_finite by auto
- with \<open>span B = span T\<close> show ?thesis
- by (rule_tac U=U in that) (auto simp: span_Un)
-qed
-
-corollary%unimportant orthogonal_extension_strong:
- fixes S :: "'a::euclidean_space set"
- assumes S: "pairwise orthogonal S"
- obtains U where "U \<inter> (insert 0 S) = {}" "pairwise orthogonal (S \<union> U)"
- "span (S \<union> U) = span (S \<union> T)"
-proof -
- obtain U where "pairwise orthogonal (S \<union> U)" "span (S \<union> U) = span (S \<union> T)"
- using orthogonal_extension assms by blast
- then show ?thesis
- apply (rule_tac U = "U - (insert 0 S)" in that)
- apply blast
- apply (force simp: pairwise_def)
- apply (metis Un_Diff_cancel Un_insert_left span_redundant span_zero)
- done
-qed
-
-subsection\<open>Decomposing a vector into parts in orthogonal subspaces\<close>
-
-text\<open>existence of orthonormal basis for a subspace.\<close>
-
-lemma orthogonal_spanningset_subspace:
- fixes S :: "'a :: euclidean_space set"
- assumes "subspace S"
- obtains B where "B \<subseteq> S" "pairwise orthogonal B" "span B = S"
-proof -
- obtain B where "B \<subseteq> S" "independent B" "S \<subseteq> span B" "card B = dim S"
- using basis_exists by blast
- with orthogonal_extension [of "{}" B]
- show ?thesis
- by (metis Un_empty_left assms pairwise_empty span_superset span_subspace that)
-qed
-
-lemma orthogonal_basis_subspace:
- fixes S :: "'a :: euclidean_space set"
- assumes "subspace S"
- obtains B where "0 \<notin> B" "B \<subseteq> S" "pairwise orthogonal B" "independent B"
- "card B = dim S" "span B = S"
-proof -
- obtain B where "B \<subseteq> S" "pairwise orthogonal B" "span B = S"
- using assms orthogonal_spanningset_subspace by blast
- then show ?thesis
- apply (rule_tac B = "B - {0}" in that)
- apply (auto simp: indep_card_eq_dim_span pairwise_subset pairwise_orthogonal_independent elim: pairwise_subset)
- done
-qed
-
-proposition orthonormal_basis_subspace:
- fixes S :: "'a :: euclidean_space set"
- assumes "subspace S"
- obtains B where "B \<subseteq> S" "pairwise orthogonal B"
- and "\<And>x. x \<in> B \<Longrightarrow> norm x = 1"
- and "independent B" "card B = dim S" "span B = S"
-proof -
- obtain B where "0 \<notin> B" "B \<subseteq> S"
- and orth: "pairwise orthogonal B"
- and "independent B" "card B = dim S" "span B = S"
- by (blast intro: orthogonal_basis_subspace [OF assms])
- have 1: "(\<lambda>x. x /\<^sub>R norm x) ` B \<subseteq> S"
- using \<open>span B = S\<close> span_superset span_mul by fastforce
- have 2: "pairwise orthogonal ((\<lambda>x. x /\<^sub>R norm x) ` B)"
- using orth by (force simp: pairwise_def orthogonal_clauses)
- have 3: "\<And>x. x \<in> (\<lambda>x. x /\<^sub>R norm x) ` B \<Longrightarrow> norm x = 1"
- by (metis (no_types, lifting) \<open>0 \<notin> B\<close> image_iff norm_sgn sgn_div_norm)
- have 4: "independent ((\<lambda>x. x /\<^sub>R norm x) ` B)"
- by (metis "2" "3" norm_zero pairwise_orthogonal_independent zero_neq_one)
- have "inj_on (\<lambda>x. x /\<^sub>R norm x) B"
- proof
- fix x y
- assume "x \<in> B" "y \<in> B" "x /\<^sub>R norm x = y /\<^sub>R norm y"
- moreover have "\<And>i. i \<in> B \<Longrightarrow> norm (i /\<^sub>R norm i) = 1"
- using 3 by blast
- ultimately show "x = y"
- by (metis norm_eq_1 orth orthogonal_clauses(7) orthogonal_commute orthogonal_def pairwise_def zero_neq_one)
- qed
- then have 5: "card ((\<lambda>x. x /\<^sub>R norm x) ` B) = dim S"
- by (metis \<open>card B = dim S\<close> card_image)
- have 6: "span ((\<lambda>x. x /\<^sub>R norm x) ` B) = S"
- by (metis "1" "4" "5" assms card_eq_dim independent_finite span_subspace)
- show ?thesis
- by (rule that [OF 1 2 3 4 5 6])
-qed
-
-
-proposition%unimportant orthogonal_to_subspace_exists_gen:
- fixes S :: "'a :: euclidean_space set"
- assumes "span S \<subset> span T"
- obtains x where "x \<noteq> 0" "x \<in> span T" "\<And>y. y \<in> span S \<Longrightarrow> orthogonal x y"
-proof -
- obtain B where "B \<subseteq> span S" and orthB: "pairwise orthogonal B"
- and "\<And>x. x \<in> B \<Longrightarrow> norm x = 1"
- and "independent B" "card B = dim S" "span B = span S"
- by (rule orthonormal_basis_subspace [of "span S", OF subspace_span])
- (auto simp: dim_span)
- with assms obtain u where spanBT: "span B \<subseteq> span T" and "u \<notin> span B" "u \<in> span T"
- by auto
- obtain C where orthBC: "pairwise orthogonal (B \<union> C)" and spanBC: "span (B \<union> C) = span (B \<union> {u})"
- by (blast intro: orthogonal_extension [OF orthB])
- show thesis
- proof (cases "C \<subseteq> insert 0 B")
- case True
- then have "C \<subseteq> span B"
- using span_eq
- by (metis span_insert_0 subset_trans)
- moreover have "u \<in> span (B \<union> C)"
- using \<open>span (B \<union> C) = span (B \<union> {u})\<close> span_superset by force
- ultimately show ?thesis
- using True \<open>u \<notin> span B\<close>
- by (metis Un_insert_left span_insert_0 sup.orderE)
- next
- case False
- then obtain x where "x \<in> C" "x \<noteq> 0" "x \<notin> B"
- by blast
- then have "x \<in> span T"
- by (metis (no_types, lifting) Un_insert_right Un_upper2 \<open>u \<in> span T\<close> spanBT spanBC
- \<open>u \<in> span T\<close> insert_subset span_superset span_mono
- span_span subsetCE subset_trans sup_bot.comm_neutral)
- moreover have "orthogonal x y" if "y \<in> span B" for y
- using that
- proof (rule span_induct)
- show "subspace {a. orthogonal x a}"
- by (simp add: subspace_orthogonal_to_vector)
- show "\<And>b. b \<in> B \<Longrightarrow> orthogonal x b"
- by (metis Un_iff \<open>x \<in> C\<close> \<open>x \<notin> B\<close> orthBC pairwise_def)
- qed
- ultimately show ?thesis
- using \<open>x \<noteq> 0\<close> that \<open>span B = span S\<close> by auto
- qed
-qed
-
-corollary%unimportant orthogonal_to_subspace_exists:
- fixes S :: "'a :: euclidean_space set"
- assumes "dim S < DIM('a)"
- obtains x where "x \<noteq> 0" "\<And>y. y \<in> span S \<Longrightarrow> orthogonal x y"
-proof -
-have "span S \<subset> UNIV"
- by (metis (mono_tags) UNIV_I assms inner_eq_zero_iff less_le lowdim_subset_hyperplane
- mem_Collect_eq top.extremum_strict top.not_eq_extremum)
- with orthogonal_to_subspace_exists_gen [of S UNIV] that show ?thesis
- by (auto simp: span_UNIV)
-qed
-
-corollary%unimportant orthogonal_to_vector_exists:
- fixes x :: "'a :: euclidean_space"
- assumes "2 \<le> DIM('a)"
- obtains y where "y \<noteq> 0" "orthogonal x y"
-proof -
- have "dim {x} < DIM('a)"
- using assms by auto
- then show thesis
- by (rule orthogonal_to_subspace_exists) (simp add: orthogonal_commute span_base that)
-qed
-
-proposition%unimportant orthogonal_subspace_decomp_exists:
- fixes S :: "'a :: euclidean_space set"
- obtains y z
- where "y \<in> span S"
- and "\<And>w. w \<in> span S \<Longrightarrow> orthogonal z w"
- and "x = y + z"
-proof -
- obtain T where "0 \<notin> T" "T \<subseteq> span S" "pairwise orthogonal T" "independent T"
- "card T = dim (span S)" "span T = span S"
- using orthogonal_basis_subspace subspace_span by blast
- let ?a = "\<Sum>b\<in>T. (b \<bullet> x / (b \<bullet> b)) *\<^sub>R b"
- have orth: "orthogonal (x - ?a) w" if "w \<in> span S" for w
- by (simp add: Gram_Schmidt_step \<open>pairwise orthogonal T\<close> \<open>span T = span S\<close>
- orthogonal_commute that)
- show ?thesis
- apply (rule_tac y = "?a" and z = "x - ?a" in that)
- apply (meson \<open>T \<subseteq> span S\<close> span_scale span_sum subsetCE)
- apply (fact orth, simp)
- done
-qed
-
-lemma orthogonal_subspace_decomp_unique:
- fixes S :: "'a :: euclidean_space set"
- assumes "x + y = x' + y'"
- and ST: "x \<in> span S" "x' \<in> span S" "y \<in> span T" "y' \<in> span T"
- and orth: "\<And>a b. \<lbrakk>a \<in> S; b \<in> T\<rbrakk> \<Longrightarrow> orthogonal a b"
- shows "x = x' \<and> y = y'"
-proof -
- have "x + y - y' = x'"
- by (simp add: assms)
- moreover have "\<And>a b. \<lbrakk>a \<in> span S; b \<in> span T\<rbrakk> \<Longrightarrow> orthogonal a b"
- by (meson orth orthogonal_commute orthogonal_to_span)
- ultimately have "0 = x' - x"
- by (metis (full_types) add_diff_cancel_left' ST diff_right_commute orthogonal_clauses(10) orthogonal_clauses(5) orthogonal_self)
- with assms show ?thesis by auto
-qed
-
-lemma vector_in_orthogonal_spanningset:
- fixes a :: "'a::euclidean_space"
- obtains S where "a \<in> S" "pairwise orthogonal S" "span S = UNIV"
- by (metis UNIV_I Un_iff empty_iff insert_subset orthogonal_extension pairwise_def
- pairwise_orthogonal_insert span_UNIV subsetI subset_antisym)
-
-lemma vector_in_orthogonal_basis:
- fixes a :: "'a::euclidean_space"
- assumes "a \<noteq> 0"
- obtains S where "a \<in> S" "0 \<notin> S" "pairwise orthogonal S" "independent S" "finite S"
- "span S = UNIV" "card S = DIM('a)"
-proof -
- obtain S where S: "a \<in> S" "pairwise orthogonal S" "span S = UNIV"
- using vector_in_orthogonal_spanningset .
- show thesis
- proof
- show "pairwise orthogonal (S - {0})"
- using pairwise_mono S(2) by blast
- show "independent (S - {0})"
- by (simp add: \<open>pairwise orthogonal (S - {0})\<close> pairwise_orthogonal_independent)
- show "finite (S - {0})"
- using \<open>independent (S - {0})\<close> independent_finite by blast
- show "card (S - {0}) = DIM('a)"
- using span_delete_0 [of S] S
- by (simp add: \<open>independent (S - {0})\<close> indep_card_eq_dim_span dim_UNIV)
- qed (use S \<open>a \<noteq> 0\<close> in auto)
-qed
-
-lemma vector_in_orthonormal_basis:
- fixes a :: "'a::euclidean_space"
- assumes "norm a = 1"
- obtains S where "a \<in> S" "pairwise orthogonal S" "\<And>x. x \<in> S \<Longrightarrow> norm x = 1"
- "independent S" "card S = DIM('a)" "span S = UNIV"
-proof -
- have "a \<noteq> 0"
- using assms by auto
- then obtain S where "a \<in> S" "0 \<notin> S" "finite S"
- and S: "pairwise orthogonal S" "independent S" "span S = UNIV" "card S = DIM('a)"
- by (metis vector_in_orthogonal_basis)
- let ?S = "(\<lambda>x. x /\<^sub>R norm x) ` S"
- show thesis
- proof
- show "a \<in> ?S"
- using \<open>a \<in> S\<close> assms image_iff by fastforce
- next
- show "pairwise orthogonal ?S"
- using \<open>pairwise orthogonal S\<close> by (auto simp: pairwise_def orthogonal_def)
- show "\<And>x. x \<in> (\<lambda>x. x /\<^sub>R norm x) ` S \<Longrightarrow> norm x = 1"
- using \<open>0 \<notin> S\<close> by (auto simp: divide_simps)
- then show "independent ?S"
- by (metis \<open>pairwise orthogonal ((\<lambda>x. x /\<^sub>R norm x) ` S)\<close> norm_zero pairwise_orthogonal_independent zero_neq_one)
- have "inj_on (\<lambda>x. x /\<^sub>R norm x) S"
- unfolding inj_on_def
- by (metis (full_types) S(1) \<open>0 \<notin> S\<close> inverse_nonzero_iff_nonzero norm_eq_zero orthogonal_scaleR orthogonal_self pairwise_def)
- then show "card ?S = DIM('a)"
- by (simp add: card_image S)
- show "span ?S = UNIV"
- by (metis (no_types) \<open>0 \<notin> S\<close> \<open>finite S\<close> \<open>span S = UNIV\<close>
- field_class.field_inverse_zero inverse_inverse_eq less_irrefl span_image_scale
- zero_less_norm_iff)
- qed
-qed
-
-proposition dim_orthogonal_sum:
- fixes A :: "'a::euclidean_space set"
- assumes "\<And>x y. \<lbrakk>x \<in> A; y \<in> B\<rbrakk> \<Longrightarrow> x \<bullet> y = 0"
- shows "dim(A \<union> B) = dim A + dim B"
-proof -
- have 1: "\<And>x y. \<lbrakk>x \<in> span A; y \<in> B\<rbrakk> \<Longrightarrow> x \<bullet> y = 0"
- by (erule span_induct [OF _ subspace_hyperplane2]; simp add: assms)
- have "\<And>x y. \<lbrakk>x \<in> span A; y \<in> span B\<rbrakk> \<Longrightarrow> x \<bullet> y = 0"
- using 1 by (simp add: span_induct [OF _ subspace_hyperplane])
- then have 0: "\<And>x y. \<lbrakk>x \<in> span A; y \<in> span B\<rbrakk> \<Longrightarrow> x \<bullet> y = 0"
- by simp
- have "dim(A \<union> B) = dim (span (A \<union> B))"
- by (simp add: dim_span)
- also have "span (A \<union> B) = ((\<lambda>(a, b). a + b) ` (span A \<times> span B))"
- by (auto simp add: span_Un image_def)
- also have "dim \<dots> = dim {x + y |x y. x \<in> span A \<and> y \<in> span B}"
- by (auto intro!: arg_cong [where f=dim])
- also have "... = dim {x + y |x y. x \<in> span A \<and> y \<in> span B} + dim(span A \<inter> span B)"
- by (auto simp: dest: 0)
- also have "... = dim (span A) + dim (span B)"
- by (rule dim_sums_Int) (auto simp: subspace_span)
- also have "... = dim A + dim B"
- by (simp add: dim_span)
- finally show ?thesis .
-qed
-
-lemma dim_subspace_orthogonal_to_vectors:
- fixes A :: "'a::euclidean_space set"
- assumes "subspace A" "subspace B" "A \<subseteq> B"
- shows "dim {y \<in> B. \<forall>x \<in> A. orthogonal x y} + dim A = dim B"
-proof -
- have "dim (span ({y \<in> B. \<forall>x\<in>A. orthogonal x y} \<union> A)) = dim (span B)"
- proof (rule arg_cong [where f=dim, OF subset_antisym])
- show "span ({y \<in> B. \<forall>x\<in>A. orthogonal x y} \<union> A) \<subseteq> span B"
- by (simp add: \<open>A \<subseteq> B\<close> Collect_restrict span_mono)
- next
- have *: "x \<in> span ({y \<in> B. \<forall>x\<in>A. orthogonal x y} \<union> A)"
- if "x \<in> B" for x
- proof -
- obtain y z where "x = y + z" "y \<in> span A" and orth: "\<And>w. w \<in> span A \<Longrightarrow> orthogonal z w"
- using orthogonal_subspace_decomp_exists [of A x] that by auto
- have "y \<in> span B"
- using \<open>y \<in> span A\<close> assms(3) span_mono by blast
- then have "z \<in> {a \<in> B. \<forall>x. x \<in> A \<longrightarrow> orthogonal x a}"
- apply simp
- using \<open>x = y + z\<close> assms(1) assms(2) orth orthogonal_commute span_add_eq
- span_eq_iff that by blast
- then have z: "z \<in> span {y \<in> B. \<forall>x\<in>A. orthogonal x y}"
- by (meson span_superset subset_iff)
- then show ?thesis
- apply (auto simp: span_Un image_def \<open>x = y + z\<close> \<open>y \<in> span A\<close>)
- using \<open>y \<in> span A\<close> add.commute by blast
- qed
- show "span B \<subseteq> span ({y \<in> B. \<forall>x\<in>A. orthogonal x y} \<union> A)"
- by (rule span_minimal)
- (auto intro: * span_minimal simp: subspace_span)
- qed
- then show ?thesis
- by (metis (no_types, lifting) dim_orthogonal_sum dim_span mem_Collect_eq
- orthogonal_commute orthogonal_def)
-qed
-
lemma aff_dim_openin:
fixes S :: "'a::euclidean_space set"
assumes ope: "openin (subtopology euclidean T) S" and "affine T" "S \<noteq> {}"