src/HOL/Analysis/Linear_Algebra.thy
changeset 70136 f03a01a18c6e
parent 69683 8b3458ca0762
child 70688 3d894e1cfc75
equal deleted inserted replaced
70135:ad6d4a14adb5 70136:f03a01a18c6e
   102     then have "x \<in> ((\<lambda>x. a+x) ` S)" by auto
   102     then have "x \<in> ((\<lambda>x. a+x) ` S)" by auto
   103   }
   103   }
   104   then show ?thesis by auto
   104   then show ?thesis by auto
   105 qed
   105 qed
   106 
   106 
   107 subsection%unimportant \<open>More interesting properties of the norm\<close>
   107 subsection\<^marker>\<open>tag unimportant\<close> \<open>More interesting properties of the norm\<close>
   108 
   108 
   109 unbundle inner_syntax
   109 unbundle inner_syntax
   110 
   110 
   111 text\<open>Equality of vectors in terms of \<^term>\<open>(\<bullet>)\<close> products.\<close>
   111 text\<open>Equality of vectors in terms of \<^term>\<open>(\<bullet>)\<close> products.\<close>
   112 
   112 
   228 qed simp
   228 qed simp
   229 
   229 
   230 
   230 
   231 subsection \<open>Orthogonality\<close>
   231 subsection \<open>Orthogonality\<close>
   232 
   232 
   233 definition%important (in real_inner) "orthogonal x y \<longleftrightarrow> x \<bullet> y = 0"
   233 definition\<^marker>\<open>tag important\<close> (in real_inner) "orthogonal x y \<longleftrightarrow> x \<bullet> y = 0"
   234 
   234 
   235 context real_inner
   235 context real_inner
   236 begin
   236 begin
   237 
   237 
   238 lemma orthogonal_self: "orthogonal x x \<longleftrightarrow> x = 0"
   238 lemma orthogonal_self: "orthogonal x x \<longleftrightarrow> x = 0"
   297 qed
   297 qed
   298 
   298 
   299 
   299 
   300 subsection  \<open>Orthogonality of a transformation\<close>
   300 subsection  \<open>Orthogonality of a transformation\<close>
   301 
   301 
   302 definition%important  "orthogonal_transformation f \<longleftrightarrow> linear f \<and> (\<forall>v w. f v \<bullet> f w = v \<bullet> w)"
   302 definition\<^marker>\<open>tag important\<close>  "orthogonal_transformation f \<longleftrightarrow> linear f \<and> (\<forall>v w. f v \<bullet> f w = v \<bullet> w)"
   303 
   303 
   304 lemma%unimportant  orthogonal_transformation:
   304 lemma\<^marker>\<open>tag unimportant\<close>  orthogonal_transformation:
   305   "orthogonal_transformation f \<longleftrightarrow> linear f \<and> (\<forall>v. norm (f v) = norm v)"
   305   "orthogonal_transformation f \<longleftrightarrow> linear f \<and> (\<forall>v. norm (f v) = norm v)"
   306   unfolding orthogonal_transformation_def
   306   unfolding orthogonal_transformation_def
   307   apply auto
   307   apply auto
   308   apply (erule_tac x=v in allE)+
   308   apply (erule_tac x=v in allE)+
   309   apply (simp add: norm_eq_sqrt_inner)
   309   apply (simp add: norm_eq_sqrt_inner)
   310   apply (simp add: dot_norm linear_add[symmetric])
   310   apply (simp add: dot_norm linear_add[symmetric])
   311   done
   311   done
   312 
   312 
   313 lemma%unimportant  orthogonal_transformation_id [simp]: "orthogonal_transformation (\<lambda>x. x)"
   313 lemma\<^marker>\<open>tag unimportant\<close>  orthogonal_transformation_id [simp]: "orthogonal_transformation (\<lambda>x. x)"
   314   by (simp add: linear_iff orthogonal_transformation_def)
   314   by (simp add: linear_iff orthogonal_transformation_def)
   315 
   315 
   316 lemma%unimportant  orthogonal_orthogonal_transformation:
   316 lemma\<^marker>\<open>tag unimportant\<close>  orthogonal_orthogonal_transformation:
   317     "orthogonal_transformation f \<Longrightarrow> orthogonal (f x) (f y) \<longleftrightarrow> orthogonal x y"
   317     "orthogonal_transformation f \<Longrightarrow> orthogonal (f x) (f y) \<longleftrightarrow> orthogonal x y"
   318   by (simp add: orthogonal_def orthogonal_transformation_def)
   318   by (simp add: orthogonal_def orthogonal_transformation_def)
   319 
   319 
   320 lemma%unimportant  orthogonal_transformation_compose:
   320 lemma\<^marker>\<open>tag unimportant\<close>  orthogonal_transformation_compose:
   321    "\<lbrakk>orthogonal_transformation f; orthogonal_transformation g\<rbrakk> \<Longrightarrow> orthogonal_transformation(f \<circ> g)"
   321    "\<lbrakk>orthogonal_transformation f; orthogonal_transformation g\<rbrakk> \<Longrightarrow> orthogonal_transformation(f \<circ> g)"
   322   by (auto simp: orthogonal_transformation_def linear_compose)
   322   by (auto simp: orthogonal_transformation_def linear_compose)
   323 
   323 
   324 lemma%unimportant  orthogonal_transformation_neg:
   324 lemma\<^marker>\<open>tag unimportant\<close>  orthogonal_transformation_neg:
   325   "orthogonal_transformation(\<lambda>x. -(f x)) \<longleftrightarrow> orthogonal_transformation f"
   325   "orthogonal_transformation(\<lambda>x. -(f x)) \<longleftrightarrow> orthogonal_transformation f"
   326   by (auto simp: orthogonal_transformation_def dest: linear_compose_neg)
   326   by (auto simp: orthogonal_transformation_def dest: linear_compose_neg)
   327 
   327 
   328 lemma%unimportant  orthogonal_transformation_scaleR: "orthogonal_transformation f \<Longrightarrow> f (c *\<^sub>R v) = c *\<^sub>R f v"
   328 lemma\<^marker>\<open>tag unimportant\<close>  orthogonal_transformation_scaleR: "orthogonal_transformation f \<Longrightarrow> f (c *\<^sub>R v) = c *\<^sub>R f v"
   329   by (simp add: linear_iff orthogonal_transformation_def)
   329   by (simp add: linear_iff orthogonal_transformation_def)
   330 
   330 
   331 lemma%unimportant  orthogonal_transformation_linear:
   331 lemma\<^marker>\<open>tag unimportant\<close>  orthogonal_transformation_linear:
   332    "orthogonal_transformation f \<Longrightarrow> linear f"
   332    "orthogonal_transformation f \<Longrightarrow> linear f"
   333   by (simp add: orthogonal_transformation_def)
   333   by (simp add: orthogonal_transformation_def)
   334 
   334 
   335 lemma%unimportant  orthogonal_transformation_inj:
   335 lemma\<^marker>\<open>tag unimportant\<close>  orthogonal_transformation_inj:
   336   "orthogonal_transformation f \<Longrightarrow> inj f"
   336   "orthogonal_transformation f \<Longrightarrow> inj f"
   337   unfolding orthogonal_transformation_def inj_on_def
   337   unfolding orthogonal_transformation_def inj_on_def
   338   by (metis vector_eq)
   338   by (metis vector_eq)
   339 
   339 
   340 lemma%unimportant  orthogonal_transformation_surj:
   340 lemma\<^marker>\<open>tag unimportant\<close>  orthogonal_transformation_surj:
   341   "orthogonal_transformation f \<Longrightarrow> surj f"
   341   "orthogonal_transformation f \<Longrightarrow> surj f"
   342   for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space"
   342   for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space"
   343   by (simp add: linear_injective_imp_surjective orthogonal_transformation_inj orthogonal_transformation_linear)
   343   by (simp add: linear_injective_imp_surjective orthogonal_transformation_inj orthogonal_transformation_linear)
   344 
   344 
   345 lemma%unimportant  orthogonal_transformation_bij:
   345 lemma\<^marker>\<open>tag unimportant\<close>  orthogonal_transformation_bij:
   346   "orthogonal_transformation f \<Longrightarrow> bij f"
   346   "orthogonal_transformation f \<Longrightarrow> bij f"
   347   for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space"
   347   for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space"
   348   by (simp add: bij_def orthogonal_transformation_inj orthogonal_transformation_surj)
   348   by (simp add: bij_def orthogonal_transformation_inj orthogonal_transformation_surj)
   349 
   349 
   350 lemma%unimportant  orthogonal_transformation_inv:
   350 lemma\<^marker>\<open>tag unimportant\<close>  orthogonal_transformation_inv:
   351   "orthogonal_transformation f \<Longrightarrow> orthogonal_transformation (inv f)"
   351   "orthogonal_transformation f \<Longrightarrow> orthogonal_transformation (inv f)"
   352   for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space"
   352   for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space"
   353   by (metis (no_types, hide_lams) bijection.inv_right bijection_def inj_linear_imp_inv_linear orthogonal_transformation orthogonal_transformation_bij orthogonal_transformation_inj)
   353   by (metis (no_types, hide_lams) bijection.inv_right bijection_def inj_linear_imp_inv_linear orthogonal_transformation orthogonal_transformation_bij orthogonal_transformation_inj)
   354 
   354 
   355 lemma%unimportant  orthogonal_transformation_norm:
   355 lemma\<^marker>\<open>tag unimportant\<close>  orthogonal_transformation_norm:
   356   "orthogonal_transformation f \<Longrightarrow> norm (f x) = norm x"
   356   "orthogonal_transformation f \<Longrightarrow> norm (f x) = norm x"
   357   by (metis orthogonal_transformation)
   357   by (metis orthogonal_transformation)
   358 
   358 
   359 
   359 
   360 subsection \<open>Bilinear functions\<close>
   360 subsection \<open>Bilinear functions\<close>
   361 
   361 
   362 definition%important
   362 definition\<^marker>\<open>tag important\<close>
   363 bilinear :: "('a::real_vector \<Rightarrow> 'b::real_vector \<Rightarrow> 'c::real_vector) \<Rightarrow> bool" where
   363 bilinear :: "('a::real_vector \<Rightarrow> 'b::real_vector \<Rightarrow> 'c::real_vector) \<Rightarrow> bool" where
   364 "bilinear f \<longleftrightarrow> (\<forall>x. linear (\<lambda>y. f x y)) \<and> (\<forall>y. linear (\<lambda>x. f x y))"
   364 "bilinear f \<longleftrightarrow> (\<forall>x. linear (\<lambda>y. f x y)) \<and> (\<forall>y. linear (\<lambda>x. f x y))"
   365 
   365 
   366 lemma bilinear_ladd: "bilinear h \<Longrightarrow> h (x + y) z = h x z + h y z"
   366 lemma bilinear_ladd: "bilinear h \<Longrightarrow> h (x + y) z = h x z + h y z"
   367   by (simp add: bilinear_def linear_iff)
   367   by (simp add: bilinear_def linear_iff)
   415 qed
   415 qed
   416 
   416 
   417 
   417 
   418 subsection \<open>Adjoints\<close>
   418 subsection \<open>Adjoints\<close>
   419 
   419 
   420 definition%important adjoint :: "(('a::real_inner) \<Rightarrow> ('b::real_inner)) \<Rightarrow> 'b \<Rightarrow> 'a" where
   420 definition\<^marker>\<open>tag important\<close> adjoint :: "(('a::real_inner) \<Rightarrow> ('b::real_inner)) \<Rightarrow> 'b \<Rightarrow> 'a" where
   421 "adjoint f = (SOME f'. \<forall>x y. f x \<bullet> y = x \<bullet> f' y)"
   421 "adjoint f = (SOME f'. \<forall>x y. f x \<bullet> y = x \<bullet> f' y)"
   422 
   422 
   423 lemma adjoint_unique:
   423 lemma adjoint_unique:
   424   assumes "\<forall>x y. inner (f x) y = inner x (g y)"
   424   assumes "\<forall>x y. inner (f x) y = inner x (g y)"
   425   shows "adjoint f = g"
   425   shows "adjoint f = g"
   577   apply auto
   577   apply auto
   578   apply (metis Suc_pred of_nat_Suc)
   578   apply (metis Suc_pred of_nat_Suc)
   579   done
   579   done
   580 
   580 
   581 
   581 
   582 subsection%unimportant \<open>Euclidean Spaces as Typeclass\<close>
   582 subsection\<^marker>\<open>tag unimportant\<close> \<open>Euclidean Spaces as Typeclass\<close>
   583 
   583 
   584 lemma independent_Basis: "independent Basis"
   584 lemma independent_Basis: "independent Basis"
   585   by (rule independent_Basis)
   585   by (rule independent_Basis)
   586 
   586 
   587 lemma span_Basis [simp]: "span Basis = UNIV"
   587 lemma span_Basis [simp]: "span Basis = UNIV"
   589 
   589 
   590 lemma in_span_Basis: "x \<in> span Basis"
   590 lemma in_span_Basis: "x \<in> span Basis"
   591   unfolding span_Basis ..
   591   unfolding span_Basis ..
   592 
   592 
   593 
   593 
   594 subsection%unimportant \<open>Linearity and Bilinearity continued\<close>
   594 subsection\<^marker>\<open>tag unimportant\<close> \<open>Linearity and Bilinearity continued\<close>
   595 
   595 
   596 lemma linear_bounded:
   596 lemma linear_bounded:
   597   fixes f :: "'a::euclidean_space \<Rightarrow> 'b::real_normed_vector"
   597   fixes f :: "'a::euclidean_space \<Rightarrow> 'b::real_normed_vector"
   598   assumes lf: "linear f"
   598   assumes lf: "linear f"
   599   shows "\<exists>B. \<forall>x. norm (f x) \<le> B * norm x"
   599   shows "\<exists>B. \<forall>x. norm (f x) \<le> B * norm x"
   771   fixes f :: "'a::euclidean_space \<Rightarrow> 'b::real_normed_vector"
   771   fixes f :: "'a::euclidean_space \<Rightarrow> 'b::real_normed_vector"
   772   shows "linear f \<Longrightarrow> f differentiable net"
   772   shows "linear f \<Longrightarrow> f differentiable net"
   773   by (metis linear_imp_has_derivative differentiable_def)
   773   by (metis linear_imp_has_derivative differentiable_def)
   774 
   774 
   775 
   775 
   776 subsection%unimportant \<open>We continue\<close>
   776 subsection\<^marker>\<open>tag unimportant\<close> \<open>We continue\<close>
   777 
   777 
   778 lemma independent_bound:
   778 lemma independent_bound:
   779   fixes S :: "'a::euclidean_space set"
   779   fixes S :: "'a::euclidean_space set"
   780   shows "independent S \<Longrightarrow> finite S \<and> card S \<le> DIM('a)"
   780   shows "independent S \<Longrightarrow> finite S \<and> card S \<le> DIM('a)"
   781   by (metis dim_subset_UNIV finiteI_independent dim_span_eq_card_independent)
   781   by (metis dim_subset_UNIV finiteI_independent dim_span_eq_card_independent)
  1035   using bilinear_eq[OF bf bg equalityD2[OF span_Basis] equalityD2[OF span_Basis]] fg by blast
  1035   using bilinear_eq[OF bf bg equalityD2[OF span_Basis] equalityD2[OF span_Basis]] fg by blast
  1036 
  1036 
  1037 
  1037 
  1038 subsection \<open>Infinity norm\<close>
  1038 subsection \<open>Infinity norm\<close>
  1039 
  1039 
  1040 definition%important "infnorm (x::'a::euclidean_space) = Sup {\<bar>x \<bullet> b\<bar> |b. b \<in> Basis}"
  1040 definition\<^marker>\<open>tag important\<close> "infnorm (x::'a::euclidean_space) = Sup {\<bar>x \<bullet> b\<bar> |b. b \<in> Basis}"
  1041 
  1041 
  1042 lemma infnorm_set_image:
  1042 lemma infnorm_set_image:
  1043   fixes x :: "'a::euclidean_space"
  1043   fixes x :: "'a::euclidean_space"
  1044   shows "{\<bar>x \<bullet> i\<bar> |i. i \<in> Basis} = (\<lambda>i. \<bar>x \<bullet> i\<bar>) ` Basis"
  1044   shows "{\<bar>x \<bullet> i\<bar> |i. i \<in> Basis} = (\<lambda>i. \<bar>x \<bullet> i\<bar>) ` Basis"
  1045   by blast
  1045   by blast
  1225 qed
  1225 qed
  1226 
  1226 
  1227 
  1227 
  1228 subsection \<open>Collinearity\<close>
  1228 subsection \<open>Collinearity\<close>
  1229 
  1229 
  1230 definition%important collinear :: "'a::real_vector set \<Rightarrow> bool"
  1230 definition\<^marker>\<open>tag important\<close> collinear :: "'a::real_vector set \<Rightarrow> bool"
  1231   where "collinear S \<longleftrightarrow> (\<exists>u. \<forall>x \<in> S. \<forall> y \<in> S. \<exists>c. x - y = c *\<^sub>R u)"
  1231   where "collinear S \<longleftrightarrow> (\<exists>u. \<forall>x \<in> S. \<forall> y \<in> S. \<exists>c. x - y = c *\<^sub>R u)"
  1232 
  1232 
  1233 lemma collinear_alt:
  1233 lemma collinear_alt:
  1234      "collinear S \<longleftrightarrow> (\<exists>u v. \<forall>x \<in> S. \<exists>c. x = u + c *\<^sub>R v)" (is "?lhs = ?rhs")
  1234      "collinear S \<longleftrightarrow> (\<exists>u v. \<forall>x \<in> S. \<exists>c. x = u + c *\<^sub>R v)" (is "?lhs = ?rhs")
  1235 proof
  1235 proof
  1563     using assms pairwise_orthogonal_imp_finite by auto
  1563     using assms pairwise_orthogonal_imp_finite by auto
  1564   with \<open>span B = span T\<close> show ?thesis
  1564   with \<open>span B = span T\<close> show ?thesis
  1565     by (rule_tac U=U in that) (auto simp: span_Un)
  1565     by (rule_tac U=U in that) (auto simp: span_Un)
  1566 qed
  1566 qed
  1567 
  1567 
  1568 corollary%unimportant orthogonal_extension_strong:
  1568 corollary\<^marker>\<open>tag unimportant\<close> orthogonal_extension_strong:
  1569   fixes S :: "'a::euclidean_space set"
  1569   fixes S :: "'a::euclidean_space set"
  1570   assumes S: "pairwise orthogonal S"
  1570   assumes S: "pairwise orthogonal S"
  1571   obtains U where "U \<inter> (insert 0 S) = {}" "pairwise orthogonal (S \<union> U)"
  1571   obtains U where "U \<inter> (insert 0 S) = {}" "pairwise orthogonal (S \<union> U)"
  1572                   "span (S \<union> U) = span (S \<union> T)"
  1572                   "span (S \<union> U) = span (S \<union> T)"
  1573 proof -
  1573 proof -
  1646   show ?thesis
  1646   show ?thesis
  1647     by (rule that [OF 1 2 3 4 5 6])
  1647     by (rule that [OF 1 2 3 4 5 6])
  1648 qed
  1648 qed
  1649 
  1649 
  1650 
  1650 
  1651 proposition%unimportant orthogonal_to_subspace_exists_gen:
  1651 proposition\<^marker>\<open>tag unimportant\<close> orthogonal_to_subspace_exists_gen:
  1652   fixes S :: "'a :: euclidean_space set"
  1652   fixes S :: "'a :: euclidean_space set"
  1653   assumes "span S \<subset> span T"
  1653   assumes "span S \<subset> span T"
  1654   obtains x where "x \<noteq> 0" "x \<in> span T" "\<And>y. y \<in> span S \<Longrightarrow> orthogonal x y"
  1654   obtains x where "x \<noteq> 0" "x \<in> span T" "\<And>y. y \<in> span S \<Longrightarrow> orthogonal x y"
  1655 proof -
  1655 proof -
  1656   obtain B where "B \<subseteq> span S" and orthB: "pairwise orthogonal B"
  1656   obtain B where "B \<subseteq> span S" and orthB: "pairwise orthogonal B"
  1692     ultimately show ?thesis
  1692     ultimately show ?thesis
  1693       using \<open>x \<noteq> 0\<close> that \<open>span B = span S\<close> by auto
  1693       using \<open>x \<noteq> 0\<close> that \<open>span B = span S\<close> by auto
  1694   qed
  1694   qed
  1695 qed
  1695 qed
  1696 
  1696 
  1697 corollary%unimportant orthogonal_to_subspace_exists:
  1697 corollary\<^marker>\<open>tag unimportant\<close> orthogonal_to_subspace_exists:
  1698   fixes S :: "'a :: euclidean_space set"
  1698   fixes S :: "'a :: euclidean_space set"
  1699   assumes "dim S < DIM('a)"
  1699   assumes "dim S < DIM('a)"
  1700   obtains x where "x \<noteq> 0" "\<And>y. y \<in> span S \<Longrightarrow> orthogonal x y"
  1700   obtains x where "x \<noteq> 0" "\<And>y. y \<in> span S \<Longrightarrow> orthogonal x y"
  1701 proof -
  1701 proof -
  1702 have "span S \<subset> UNIV"
  1702 have "span S \<subset> UNIV"
  1704       mem_Collect_eq top.extremum_strict top.not_eq_extremum)
  1704       mem_Collect_eq top.extremum_strict top.not_eq_extremum)
  1705   with orthogonal_to_subspace_exists_gen [of S UNIV] that show ?thesis
  1705   with orthogonal_to_subspace_exists_gen [of S UNIV] that show ?thesis
  1706     by (auto simp: span_UNIV)
  1706     by (auto simp: span_UNIV)
  1707 qed
  1707 qed
  1708 
  1708 
  1709 corollary%unimportant orthogonal_to_vector_exists:
  1709 corollary\<^marker>\<open>tag unimportant\<close> orthogonal_to_vector_exists:
  1710   fixes x :: "'a :: euclidean_space"
  1710   fixes x :: "'a :: euclidean_space"
  1711   assumes "2 \<le> DIM('a)"
  1711   assumes "2 \<le> DIM('a)"
  1712   obtains y where "y \<noteq> 0" "orthogonal x y"
  1712   obtains y where "y \<noteq> 0" "orthogonal x y"
  1713 proof -
  1713 proof -
  1714   have "dim {x} < DIM('a)"
  1714   have "dim {x} < DIM('a)"
  1715     using assms by auto
  1715     using assms by auto
  1716   then show thesis
  1716   then show thesis
  1717     by (rule orthogonal_to_subspace_exists) (simp add: orthogonal_commute span_base that)
  1717     by (rule orthogonal_to_subspace_exists) (simp add: orthogonal_commute span_base that)
  1718 qed
  1718 qed
  1719 
  1719 
  1720 proposition%unimportant orthogonal_subspace_decomp_exists:
  1720 proposition\<^marker>\<open>tag unimportant\<close> orthogonal_subspace_decomp_exists:
  1721   fixes S :: "'a :: euclidean_space set"
  1721   fixes S :: "'a :: euclidean_space set"
  1722   obtains y z
  1722   obtains y z
  1723   where "y \<in> span S"
  1723   where "y \<in> span S"
  1724     and "\<And>w. w \<in> span S \<Longrightarrow> orthogonal z w"
  1724     and "\<And>w. w \<in> span S \<Longrightarrow> orthogonal z w"
  1725     and "x = y + z"
  1725     and "x = y + z"