src/HOL/Analysis/Linear_Algebra.thy
changeset 71044 cb504351d058
parent 71043 2fab72ab919a
child 71120 f4579e6800d7
equal deleted inserted replaced
71043:2fab72ab919a 71044:cb504351d058
   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
  1843         unfolding dist_norm
  1840         unfolding dist_norm
  1844       proof (rule eventually_mono)
  1841       proof (rule eventually_mono)
  1845         show "norm (h (f x) - h l) < e" if "norm (f x - l) < e / B" for x
  1842         show "norm (h (f x) - h l) < e" if "norm (f x - l) < e / B" for x
  1846           using that B
  1843           using that B
  1847           apply (simp add: field_split_simps)
  1844           apply (simp add: field_split_simps)
  1848           by (metis \<open>linear h\<close> le_less_trans linear_diff mult.commute)
  1845           by (metis \<open>linear h\<close> le_less_trans linear_diff)
  1849       qed
  1846       qed
  1850     qed
  1847     qed
  1851   qed
  1848   qed
  1852 qed
  1849 qed
  1853 
  1850