804 by (metis span_superset span_mono subset_trans) |
804 by (metis span_superset span_mono subset_trans) |
805 from span_mono[OF B(3)] C have SVC: "span V \<subseteq> span C" |
805 from span_mono[OF B(3)] C have SVC: "span V \<subseteq> span C" |
806 by (simp add: span_span) |
806 by (simp add: span_span) |
807 from card_le_dim_spanning[OF CSV SVC C(1)] C(2,3) fB |
807 from card_le_dim_spanning[OF CSV SVC C(1)] C(2,3) fB |
808 have iC: "independent C" |
808 have iC: "independent C" |
809 by (simp add: dim_span) |
809 by (simp) |
810 from C fB have "card C \<le> dim V" |
810 from C fB have "card C \<le> dim V" |
811 by simp |
811 by simp |
812 moreover have "dim V \<le> card C" |
812 moreover have "dim V \<le> card C" |
813 using span_card_ge_dim[OF CSV SVC C(1)] |
813 using span_card_ge_dim[OF CSV SVC C(1)] |
814 by simp |
814 by simp |
1346 then obtain b where b: "b \<noteq> 0" "span S \<subseteq> {a. b \<bullet> a = 0}" |
1346 then obtain b where b: "b \<noteq> 0" "span S \<subseteq> {a. b \<bullet> a = 0}" |
1347 using lowdim_subset_hyperplane [of S] by fastforce |
1347 using lowdim_subset_hyperplane [of S] by fastforce |
1348 show ?thesis |
1348 show ?thesis |
1349 apply (rule that[OF b(1)]) |
1349 apply (rule that[OF b(1)]) |
1350 apply (rule subspace_dim_equal) |
1350 apply (rule subspace_dim_equal) |
1351 by (auto simp: assms b dim_hyperplane dim_span subspace_hyperplane |
1351 by (auto simp: assms b dim_hyperplane subspace_hyperplane) |
1352 subspace_span) |
|
1353 qed |
1352 qed |
1354 |
1353 |
1355 lemma dim_eq_hyperplane: |
1354 lemma dim_eq_hyperplane: |
1356 fixes S :: "'n::euclidean_space set" |
1355 fixes S :: "'n::euclidean_space set" |
1357 shows "dim S = DIM('n) - 1 \<longleftrightarrow> (\<exists>a. a \<noteq> 0 \<and> span S = {x. a \<bullet> x = 0})" |
1356 shows "dim S = DIM('n) - 1 \<longleftrightarrow> (\<exists>a. a \<noteq> 0 \<and> span S = {x. a \<bullet> x = 0})" |
1358 by (metis One_nat_def dim_hyperplane dim_span lowdim_eq_hyperplane) |
1357 by (metis One_nat_def dim_hyperplane dim_span lowdim_eq_hyperplane) |
1359 |
1358 |
1360 |
1359 |
1361 subsection\<open> Orthogonal bases, Gram-Schmidt process, and related theorems\<close> |
1360 subsection\<open> Orthogonal bases and Gram-Schmidt process\<close> |
1362 |
1361 |
1363 lemma pairwise_orthogonal_independent: |
1362 lemma pairwise_orthogonal_independent: |
1364 assumes "pairwise orthogonal S" and "0 \<notin> S" |
1363 assumes "pairwise orthogonal S" and "0 \<notin> S" |
1365 shows "independent S" |
1364 shows "independent S" |
1366 proof - |
1365 proof - |
1417 by (simp add: S pairwise_orthogonal_imp_finite) |
1416 by (simp add: S pairwise_orthogonal_imp_finite) |
1418 have "orthogonal (a - (\<Sum>b\<in>S. (b \<bullet> a / (b \<bullet> b)) *\<^sub>R b)) x" |
1417 have "orthogonal (a - (\<Sum>b\<in>S. (b \<bullet> a / (b \<bullet> b)) *\<^sub>R b)) x" |
1419 if "x \<in> S" for x |
1418 if "x \<in> S" for x |
1420 proof - |
1419 proof - |
1421 have "a \<bullet> x = (\<Sum>y\<in>S. if y = x then y \<bullet> a else 0)" |
1420 have "a \<bullet> x = (\<Sum>y\<in>S. if y = x then y \<bullet> a else 0)" |
1422 by (simp add: \<open>finite S\<close> inner_commute sum.delta that) |
1421 by (simp add: \<open>finite S\<close> inner_commute that) |
1423 also have "... = (\<Sum>b\<in>S. b \<bullet> a * (b \<bullet> x) / (b \<bullet> b))" |
1422 also have "... = (\<Sum>b\<in>S. b \<bullet> a * (b \<bullet> x) / (b \<bullet> b))" |
1424 apply (rule sum.cong [OF refl], simp) |
1423 apply (rule sum.cong [OF refl], simp) |
1425 by (meson S orthogonal_def pairwise_def that) |
1424 by (meson S orthogonal_def pairwise_def that) |
1426 finally show ?thesis |
1425 finally show ?thesis |
1427 by (simp add: orthogonal_def algebra_simps inner_sum_left) |
1426 by (simp add: orthogonal_def algebra_simps inner_sum_left) |
1570 obtains x where "x \<noteq> 0" "x \<in> span T" "\<And>y. y \<in> span S \<Longrightarrow> orthogonal x y" |
1569 obtains x where "x \<noteq> 0" "x \<in> span T" "\<And>y. y \<in> span S \<Longrightarrow> orthogonal x y" |
1571 proof - |
1570 proof - |
1572 obtain B where "B \<subseteq> span S" and orthB: "pairwise orthogonal B" |
1571 obtain B where "B \<subseteq> span S" and orthB: "pairwise orthogonal B" |
1573 and "\<And>x. x \<in> B \<Longrightarrow> norm x = 1" |
1572 and "\<And>x. x \<in> B \<Longrightarrow> norm x = 1" |
1574 and "independent B" "card B = dim S" "span B = span S" |
1573 and "independent B" "card B = dim S" "span B = span S" |
1575 by (rule orthonormal_basis_subspace [of "span S", OF subspace_span]) |
1574 by (rule orthonormal_basis_subspace [of "span S", OF subspace_span]) (auto) |
1576 (auto simp: dim_span) |
|
1577 with assms obtain u where spanBT: "span B \<subseteq> span T" and "u \<notin> span B" "u \<in> span T" |
1575 with assms obtain u where spanBT: "span B \<subseteq> span T" and "u \<notin> span B" "u \<in> span T" |
1578 by auto |
1576 by auto |
1579 obtain C where orthBC: "pairwise orthogonal (B \<union> C)" and spanBC: "span (B \<union> C) = span (B \<union> {u})" |
1577 obtain C where orthBC: "pairwise orthogonal (B \<union> C)" and spanBC: "span (B \<union> C) = span (B \<union> {u})" |
1580 by (blast intro: orthogonal_extension [OF orthB]) |
1578 by (blast intro: orthogonal_extension [OF orthB]) |
1581 show thesis |
1579 show thesis |
1613 corollary\<^marker>\<open>tag unimportant\<close> orthogonal_to_subspace_exists: |
1611 corollary\<^marker>\<open>tag unimportant\<close> orthogonal_to_subspace_exists: |
1614 fixes S :: "'a :: euclidean_space set" |
1612 fixes S :: "'a :: euclidean_space set" |
1615 assumes "dim S < DIM('a)" |
1613 assumes "dim S < DIM('a)" |
1616 obtains x where "x \<noteq> 0" "\<And>y. y \<in> span S \<Longrightarrow> orthogonal x y" |
1614 obtains x where "x \<noteq> 0" "\<And>y. y \<in> span S \<Longrightarrow> orthogonal x y" |
1617 proof - |
1615 proof - |
1618 have "span S \<subset> UNIV" |
1616 have "span S \<subset> UNIV" |
1619 by (metis (mono_tags) UNIV_I assms inner_eq_zero_iff less_le lowdim_subset_hyperplane |
1617 by (metis (mono_tags) UNIV_I assms inner_eq_zero_iff less_le lowdim_subset_hyperplane |
1620 mem_Collect_eq top.extremum_strict top.not_eq_extremum) |
1618 mem_Collect_eq top.extremum_strict top.not_eq_extremum) |
1621 with orthogonal_to_subspace_exists_gen [of S UNIV] that show ?thesis |
1619 with orthogonal_to_subspace_exists_gen [of S UNIV] that show ?thesis |
1622 by (auto simp: span_UNIV) |
1620 by (auto) |
1623 qed |
1621 qed |
1624 |
1622 |
1625 corollary\<^marker>\<open>tag unimportant\<close> orthogonal_to_vector_exists: |
1623 corollary\<^marker>\<open>tag unimportant\<close> orthogonal_to_vector_exists: |
1626 fixes x :: "'a :: euclidean_space" |
1624 fixes x :: "'a :: euclidean_space" |
1627 assumes "2 \<le> DIM('a)" |
1625 assumes "2 \<le> DIM('a)" |
1692 by (simp add: \<open>pairwise orthogonal (S - {0})\<close> pairwise_orthogonal_independent) |
1690 by (simp add: \<open>pairwise orthogonal (S - {0})\<close> pairwise_orthogonal_independent) |
1693 show "finite (S - {0})" |
1691 show "finite (S - {0})" |
1694 using \<open>independent (S - {0})\<close> independent_imp_finite by blast |
1692 using \<open>independent (S - {0})\<close> independent_imp_finite by blast |
1695 show "card (S - {0}) = DIM('a)" |
1693 show "card (S - {0}) = DIM('a)" |
1696 using span_delete_0 [of S] S |
1694 using span_delete_0 [of S] S |
1697 by (simp add: \<open>independent (S - {0})\<close> indep_card_eq_dim_span dim_UNIV) |
1695 by (simp add: \<open>independent (S - {0})\<close> indep_card_eq_dim_span) |
1698 qed (use S \<open>a \<noteq> 0\<close> in auto) |
1696 qed (use S \<open>a \<noteq> 0\<close> in auto) |
1699 qed |
1697 qed |
1700 |
1698 |
1701 lemma vector_in_orthonormal_basis: |
1699 lemma vector_in_orthonormal_basis: |
1702 fixes a :: "'a::euclidean_space" |
1700 fixes a :: "'a::euclidean_space" |
1743 have "\<And>x y. \<lbrakk>x \<in> span A; y \<in> span B\<rbrakk> \<Longrightarrow> x \<bullet> y = 0" |
1741 have "\<And>x y. \<lbrakk>x \<in> span A; y \<in> span B\<rbrakk> \<Longrightarrow> x \<bullet> y = 0" |
1744 using 1 by (simp add: span_induct [OF _ subspace_hyperplane]) |
1742 using 1 by (simp add: span_induct [OF _ subspace_hyperplane]) |
1745 then have 0: "\<And>x y. \<lbrakk>x \<in> span A; y \<in> span B\<rbrakk> \<Longrightarrow> x \<bullet> y = 0" |
1743 then have 0: "\<And>x y. \<lbrakk>x \<in> span A; y \<in> span B\<rbrakk> \<Longrightarrow> x \<bullet> y = 0" |
1746 by simp |
1744 by simp |
1747 have "dim(A \<union> B) = dim (span (A \<union> B))" |
1745 have "dim(A \<union> B) = dim (span (A \<union> B))" |
1748 by (simp add: dim_span) |
1746 by (simp) |
1749 also have "span (A \<union> B) = ((\<lambda>(a, b). a + b) ` (span A \<times> span B))" |
1747 also have "span (A \<union> B) = ((\<lambda>(a, b). a + b) ` (span A \<times> span B))" |
1750 by (auto simp add: span_Un image_def) |
1748 by (auto simp add: span_Un image_def) |
1751 also have "dim \<dots> = dim {x + y |x y. x \<in> span A \<and> y \<in> span B}" |
1749 also have "dim \<dots> = dim {x + y |x y. x \<in> span A \<and> y \<in> span B}" |
1752 by (auto intro!: arg_cong [where f=dim]) |
1750 by (auto intro!: arg_cong [where f=dim]) |
1753 also have "... = dim {x + y |x y. x \<in> span A \<and> y \<in> span B} + dim(span A \<inter> span B)" |
1751 also have "... = dim {x + y |x y. x \<in> span A \<and> y \<in> span B} + dim(span A \<inter> span B)" |
1754 by (auto simp: dest: 0) |
1752 by (auto simp: dest: 0) |
1755 also have "... = dim (span A) + dim (span B)" |
1753 also have "... = dim (span A) + dim (span B)" |
1756 by (rule dim_sums_Int) (auto simp: subspace_span) |
1754 by (rule dim_sums_Int) (auto) |
1757 also have "... = dim A + dim B" |
1755 also have "... = dim A + dim B" |
1758 by (simp add: dim_span) |
1756 by (simp) |
1759 finally show ?thesis . |
1757 finally show ?thesis . |
1760 qed |
1758 qed |
1761 |
1759 |
1762 lemma dim_subspace_orthogonal_to_vectors: |
1760 lemma dim_subspace_orthogonal_to_vectors: |
1763 fixes A :: "'a::euclidean_space set" |
1761 fixes A :: "'a::euclidean_space set" |
1785 then show ?thesis |
1783 then show ?thesis |
1786 apply (auto simp: span_Un image_def \<open>x = y + z\<close> \<open>y \<in> span A\<close>) |
1784 apply (auto simp: span_Un image_def \<open>x = y + z\<close> \<open>y \<in> span A\<close>) |
1787 using \<open>y \<in> span A\<close> add.commute by blast |
1785 using \<open>y \<in> span A\<close> add.commute by blast |
1788 qed |
1786 qed |
1789 show "span B \<subseteq> span ({y \<in> B. \<forall>x\<in>A. orthogonal x y} \<union> A)" |
1787 show "span B \<subseteq> span ({y \<in> B. \<forall>x\<in>A. orthogonal x y} \<union> A)" |
1790 by (rule span_minimal) |
1788 by (rule span_minimal) (auto intro: * span_minimal) |
1791 (auto intro: * span_minimal simp: subspace_span) |
|
1792 qed |
1789 qed |
1793 then show ?thesis |
1790 then show ?thesis |
1794 by (metis (no_types, lifting) dim_orthogonal_sum dim_span mem_Collect_eq |
1791 by (metis (no_types, lifting) dim_orthogonal_sum dim_span mem_Collect_eq |
1795 orthogonal_commute orthogonal_def) |
1792 orthogonal_commute orthogonal_def) |
1796 qed |
1793 qed |