928 by simp (simp add: Basis_vec_def inner_axis) |
928 by simp (simp add: Basis_vec_def inner_axis) |
929 |
929 |
930 lemma%unimportant const_vector_cart:"((\<chi> i. d)::real^'n) = (\<Sum>i\<in>Basis. d *\<^sub>R i)" |
930 lemma%unimportant const_vector_cart:"((\<chi> i. d)::real^'n) = (\<Sum>i\<in>Basis. d *\<^sub>R i)" |
931 by (rule vector_cart) |
931 by (rule vector_cart) |
932 |
932 |
|
933 subsection%unimportant \<open>Explicit formulas for low dimensions\<close> |
|
934 |
|
935 lemma%unimportant prod_neutral_const: "prod f {(1::nat)..1} = f 1" |
|
936 by simp |
|
937 |
|
938 lemma%unimportant prod_2: "prod f {(1::nat)..2} = f 1 * f 2" |
|
939 by (simp add: eval_nat_numeral atLeastAtMostSuc_conv mult.commute) |
|
940 |
|
941 lemma%unimportant prod_3: "prod f {(1::nat)..3} = f 1 * f 2 * f 3" |
|
942 by (simp add: eval_nat_numeral atLeastAtMostSuc_conv mult.commute) |
|
943 |
|
944 |
|
945 subsection%important \<open>Orthogonality of a matrix\<close> |
|
946 |
|
947 definition%important "orthogonal_matrix (Q::'a::semiring_1^'n^'n) \<longleftrightarrow> |
|
948 transpose Q ** Q = mat 1 \<and> Q ** transpose Q = mat 1" |
|
949 |
|
950 lemma%unimportant orthogonal_matrix: "orthogonal_matrix (Q:: real ^'n^'n) \<longleftrightarrow> transpose Q ** Q = mat 1" |
|
951 by (metis matrix_left_right_inverse orthogonal_matrix_def) |
|
952 |
|
953 lemma%unimportant orthogonal_matrix_id: "orthogonal_matrix (mat 1 :: _^'n^'n)" |
|
954 by (simp add: orthogonal_matrix_def) |
|
955 |
|
956 lemma%unimportant orthogonal_matrix_mul: |
|
957 fixes A :: "real ^'n^'n" |
|
958 assumes "orthogonal_matrix A" "orthogonal_matrix B" |
|
959 shows "orthogonal_matrix(A ** B)" |
|
960 using assms |
|
961 by (simp add: orthogonal_matrix matrix_transpose_mul matrix_left_right_inverse matrix_mul_assoc) |
|
962 |
|
963 lemma%important orthogonal_transformation_matrix: |
|
964 fixes f:: "real^'n \<Rightarrow> real^'n" |
|
965 shows "orthogonal_transformation f \<longleftrightarrow> linear f \<and> orthogonal_matrix(matrix f)" |
|
966 (is "?lhs \<longleftrightarrow> ?rhs") |
|
967 proof%unimportant - |
|
968 let ?mf = "matrix f" |
|
969 let ?ot = "orthogonal_transformation f" |
|
970 let ?U = "UNIV :: 'n set" |
|
971 have fU: "finite ?U" by simp |
|
972 let ?m1 = "mat 1 :: real ^'n^'n" |
|
973 { |
|
974 assume ot: ?ot |
|
975 from ot have lf: "Vector_Spaces.linear (*s) (*s) f" and fd: "\<And>v w. f v \<bullet> f w = v \<bullet> w" |
|
976 unfolding orthogonal_transformation_def orthogonal_matrix linear_def scalar_mult_eq_scaleR |
|
977 by blast+ |
|
978 { |
|
979 fix i j |
|
980 let ?A = "transpose ?mf ** ?mf" |
|
981 have th0: "\<And>b (x::'a::comm_ring_1). (if b then 1 else 0)*x = (if b then x else 0)" |
|
982 "\<And>b (x::'a::comm_ring_1). x*(if b then 1 else 0) = (if b then x else 0)" |
|
983 by simp_all |
|
984 from fd[of "axis i 1" "axis j 1", |
|
985 simplified matrix_works[OF lf, symmetric] dot_matrix_vector_mul] |
|
986 have "?A$i$j = ?m1 $ i $ j" |
|
987 by (simp add: inner_vec_def matrix_matrix_mult_def columnvector_def rowvector_def |
|
988 th0 sum.delta[OF fU] mat_def axis_def) |
|
989 } |
|
990 then have "orthogonal_matrix ?mf" |
|
991 unfolding orthogonal_matrix |
|
992 by vector |
|
993 with lf have ?rhs |
|
994 unfolding linear_def scalar_mult_eq_scaleR |
|
995 by blast |
|
996 } |
|
997 moreover |
|
998 { |
|
999 assume lf: "Vector_Spaces.linear (*s) (*s) f" and om: "orthogonal_matrix ?mf" |
|
1000 from lf om have ?lhs |
|
1001 unfolding orthogonal_matrix_def norm_eq orthogonal_transformation |
|
1002 apply (simp only: matrix_works[OF lf, symmetric] dot_matrix_vector_mul) |
|
1003 apply (simp add: dot_matrix_product linear_def scalar_mult_eq_scaleR) |
|
1004 done |
|
1005 } |
|
1006 ultimately show ?thesis |
|
1007 by (auto simp: linear_def scalar_mult_eq_scaleR) |
|
1008 qed |
|
1009 |
|
1010 |
|
1011 subsection%important \<open> We can find an orthogonal matrix taking any unit vector to any other\<close> |
|
1012 |
|
1013 lemma%unimportant orthogonal_matrix_transpose [simp]: |
|
1014 "orthogonal_matrix(transpose A) \<longleftrightarrow> orthogonal_matrix A" |
|
1015 by (auto simp: orthogonal_matrix_def) |
|
1016 |
|
1017 lemma%unimportant orthogonal_matrix_orthonormal_columns: |
|
1018 fixes A :: "real^'n^'n" |
|
1019 shows "orthogonal_matrix A \<longleftrightarrow> |
|
1020 (\<forall>i. norm(column i A) = 1) \<and> |
|
1021 (\<forall>i j. i \<noteq> j \<longrightarrow> orthogonal (column i A) (column j A))" |
|
1022 by (auto simp: orthogonal_matrix matrix_mult_transpose_dot_column vec_eq_iff mat_def norm_eq_1 orthogonal_def) |
|
1023 |
|
1024 lemma%unimportant orthogonal_matrix_orthonormal_rows: |
|
1025 fixes A :: "real^'n^'n" |
|
1026 shows "orthogonal_matrix A \<longleftrightarrow> |
|
1027 (\<forall>i. norm(row i A) = 1) \<and> |
|
1028 (\<forall>i j. i \<noteq> j \<longrightarrow> orthogonal (row i A) (row j A))" |
|
1029 using orthogonal_matrix_orthonormal_columns [of "transpose A"] by simp |
|
1030 |
|
1031 lemma%important orthogonal_matrix_exists_basis: |
|
1032 fixes a :: "real^'n" |
|
1033 assumes "norm a = 1" |
|
1034 obtains A where "orthogonal_matrix A" "A *v (axis k 1) = a" |
|
1035 proof%unimportant - |
|
1036 obtain S where "a \<in> S" "pairwise orthogonal S" and noS: "\<And>x. x \<in> S \<Longrightarrow> norm x = 1" |
|
1037 and "independent S" "card S = CARD('n)" "span S = UNIV" |
|
1038 using vector_in_orthonormal_basis assms by force |
|
1039 then obtain f0 where "bij_betw f0 (UNIV::'n set) S" |
|
1040 by (metis finite_class.finite_UNIV finite_same_card_bij finiteI_independent) |
|
1041 then obtain f where f: "bij_betw f (UNIV::'n set) S" and a: "a = f k" |
|
1042 using bij_swap_iff [of k "inv f0 a" f0] |
|
1043 by (metis UNIV_I \<open>a \<in> S\<close> bij_betw_inv_into_right bij_betw_swap_iff swap_apply(1)) |
|
1044 show thesis |
|
1045 proof |
|
1046 have [simp]: "\<And>i. norm (f i) = 1" |
|
1047 using bij_betwE [OF \<open>bij_betw f UNIV S\<close>] by (blast intro: noS) |
|
1048 have [simp]: "\<And>i j. i \<noteq> j \<Longrightarrow> orthogonal (f i) (f j)" |
|
1049 using \<open>pairwise orthogonal S\<close> \<open>bij_betw f UNIV S\<close> |
|
1050 by (auto simp: pairwise_def bij_betw_def inj_on_def) |
|
1051 show "orthogonal_matrix (\<chi> i j. f j $ i)" |
|
1052 by (simp add: orthogonal_matrix_orthonormal_columns column_def) |
|
1053 show "(\<chi> i j. f j $ i) *v axis k 1 = a" |
|
1054 by (simp add: matrix_vector_mult_def axis_def a if_distrib cong: if_cong) |
|
1055 qed |
|
1056 qed |
|
1057 |
|
1058 lemma%unimportant orthogonal_transformation_exists_1: |
|
1059 fixes a b :: "real^'n" |
|
1060 assumes "norm a = 1" "norm b = 1" |
|
1061 obtains f where "orthogonal_transformation f" "f a = b" |
|
1062 proof%unimportant - |
|
1063 obtain k::'n where True |
|
1064 by simp |
|
1065 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" |
|
1066 using orthogonal_matrix_exists_basis assms by metis |
|
1067 let ?f = "\<lambda>x. (B ** transpose A) *v x" |
|
1068 show thesis |
|
1069 proof |
|
1070 show "orthogonal_transformation ?f" |
|
1071 by (subst orthogonal_transformation_matrix) |
|
1072 (auto simp: AB orthogonal_matrix_mul) |
|
1073 next |
|
1074 show "?f a = b" |
|
1075 using \<open>orthogonal_matrix A\<close> unfolding orthogonal_matrix_def |
|
1076 by (metis eq matrix_mul_rid matrix_vector_mul_assoc) |
|
1077 qed |
|
1078 qed |
|
1079 |
|
1080 lemma%important orthogonal_transformation_exists: |
|
1081 fixes a b :: "real^'n" |
|
1082 assumes "norm a = norm b" |
|
1083 obtains f where "orthogonal_transformation f" "f a = b" |
|
1084 proof%unimportant (cases "a = 0 \<or> b = 0") |
|
1085 case True |
|
1086 with assms show ?thesis |
|
1087 using that by force |
|
1088 next |
|
1089 case False |
|
1090 then obtain f where f: "orthogonal_transformation f" and eq: "f (a /\<^sub>R norm a) = (b /\<^sub>R norm b)" |
|
1091 by (auto intro: orthogonal_transformation_exists_1 [of "a /\<^sub>R norm a" "b /\<^sub>R norm b"]) |
|
1092 show ?thesis |
|
1093 proof |
|
1094 interpret linear f |
|
1095 using f by (simp add: orthogonal_transformation_linear) |
|
1096 have "f a /\<^sub>R norm a = f (a /\<^sub>R norm a)" |
|
1097 by (simp add: scale) |
|
1098 also have "\<dots> = b /\<^sub>R norm a" |
|
1099 by (simp add: eq assms [symmetric]) |
|
1100 finally show "f a = b" |
|
1101 using False by auto |
|
1102 qed (use f in auto) |
|
1103 qed |
|
1104 |
|
1105 |
|
1106 subsection%important \<open>Linearity of scaling, and hence isometry, that preserves origin\<close> |
|
1107 |
|
1108 lemma%important scaling_linear: |
|
1109 fixes f :: "'a::real_inner \<Rightarrow> 'a::real_inner" |
|
1110 assumes f0: "f 0 = 0" |
|
1111 and fd: "\<forall>x y. dist (f x) (f y) = c * dist x y" |
|
1112 shows "linear f" |
|
1113 proof%unimportant - |
|
1114 { |
|
1115 fix v w |
|
1116 have "norm (f x) = c * norm x" for x |
|
1117 by (metis dist_0_norm f0 fd) |
|
1118 then have "f v \<bullet> f w = c\<^sup>2 * (v \<bullet> w)" |
|
1119 unfolding dot_norm_neg dist_norm[symmetric] |
|
1120 by (simp add: fd power2_eq_square field_simps) |
|
1121 } |
|
1122 then show ?thesis |
|
1123 unfolding linear_iff vector_eq[where 'a="'a"] scalar_mult_eq_scaleR |
|
1124 by (simp add: inner_add field_simps) |
|
1125 qed |
|
1126 |
|
1127 lemma%unimportant isometry_linear: |
|
1128 "f (0::'a::real_inner) = (0::'a) \<Longrightarrow> \<forall>x y. dist(f x) (f y) = dist x y \<Longrightarrow> linear f" |
|
1129 by (rule scaling_linear[where c=1]) simp_all |
|
1130 |
|
1131 text \<open>Hence another formulation of orthogonal transformation\<close> |
|
1132 |
|
1133 lemma%important orthogonal_transformation_isometry: |
|
1134 "orthogonal_transformation f \<longleftrightarrow> f(0::'a::real_inner) = (0::'a) \<and> (\<forall>x y. dist(f x) (f y) = dist x y)" |
|
1135 unfolding orthogonal_transformation |
|
1136 apply (auto simp: linear_0 isometry_linear) |
|
1137 apply (metis (no_types, hide_lams) dist_norm linear_diff) |
|
1138 by (metis dist_0_norm) |
|
1139 |
|
1140 |
|
1141 subsection%important \<open>Can extend an isometry from unit sphere\<close> |
|
1142 |
|
1143 lemma%important isometry_sphere_extend: |
|
1144 fixes f:: "'a::real_inner \<Rightarrow> 'a" |
|
1145 assumes f1: "\<And>x. norm x = 1 \<Longrightarrow> norm (f x) = 1" |
|
1146 and fd1: "\<And>x y. \<lbrakk>norm x = 1; norm y = 1\<rbrakk> \<Longrightarrow> dist (f x) (f y) = dist x y" |
|
1147 shows "\<exists>g. orthogonal_transformation g \<and> (\<forall>x. norm x = 1 \<longrightarrow> g x = f x)" |
|
1148 proof%unimportant - |
|
1149 { |
|
1150 fix x y x' y' u v u' v' :: "'a" |
|
1151 assume H: "x = norm x *\<^sub>R u" "y = norm y *\<^sub>R v" |
|
1152 "x' = norm x *\<^sub>R u'" "y' = norm y *\<^sub>R v'" |
|
1153 and J: "norm u = 1" "norm u' = 1" "norm v = 1" "norm v' = 1" "norm(u' - v') = norm(u - v)" |
|
1154 then have *: "u \<bullet> v = u' \<bullet> v' + v' \<bullet> u' - v \<bullet> u " |
|
1155 by (simp add: norm_eq norm_eq_1 inner_add inner_diff) |
|
1156 have "norm (norm x *\<^sub>R u' - norm y *\<^sub>R v') = norm (norm x *\<^sub>R u - norm y *\<^sub>R v)" |
|
1157 using J by (simp add: norm_eq norm_eq_1 inner_diff * field_simps) |
|
1158 then have "norm(x' - y') = norm(x - y)" |
|
1159 using H by metis |
|
1160 } |
|
1161 note norm_eq = this |
|
1162 let ?g = "\<lambda>x. if x = 0 then 0 else norm x *\<^sub>R f (x /\<^sub>R norm x)" |
|
1163 have thfg: "?g x = f x" if "norm x = 1" for x |
|
1164 using that by auto |
|
1165 have thd: "dist (?g x) (?g y) = dist x y" for x y |
|
1166 proof (cases "x=0 \<or> y=0") |
|
1167 case False |
|
1168 show "dist (?g x) (?g y) = dist x y" |
|
1169 unfolding dist_norm |
|
1170 proof (rule norm_eq) |
|
1171 show "x = norm x *\<^sub>R (x /\<^sub>R norm x)" "y = norm y *\<^sub>R (y /\<^sub>R norm y)" |
|
1172 "norm (f (x /\<^sub>R norm x)) = 1" "norm (f (y /\<^sub>R norm y)) = 1" |
|
1173 using False f1 by auto |
|
1174 qed (use False in \<open>auto simp: field_simps intro: f1 fd1[unfolded dist_norm]\<close>) |
|
1175 qed (auto simp: f1) |
|
1176 show ?thesis |
|
1177 unfolding orthogonal_transformation_isometry |
|
1178 by (rule exI[where x= ?g]) (metis thfg thd) |
|
1179 qed |
|
1180 |
|
1181 subsection%important\<open>Induction on matrix row operations\<close> |
|
1182 |
|
1183 lemma%unimportant induct_matrix_row_operations: |
|
1184 fixes P :: "real^'n^'n \<Rightarrow> bool" |
|
1185 assumes zero_row: "\<And>A i. row i A = 0 \<Longrightarrow> P A" |
|
1186 and diagonal: "\<And>A. (\<And>i j. i \<noteq> j \<Longrightarrow> A$i$j = 0) \<Longrightarrow> P A" |
|
1187 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)" |
|
1188 and row_op: "\<And>A m n c. \<lbrakk>P A; m \<noteq> n\<rbrakk> |
|
1189 \<Longrightarrow> P(\<chi> i. if i = m then row m A + c *\<^sub>R row n A else row i A)" |
|
1190 shows "P A" |
|
1191 proof - |
|
1192 have "P A" if "(\<And>i j. \<lbrakk>j \<in> -K; i \<noteq> j\<rbrakk> \<Longrightarrow> A$i$j = 0)" for A K |
|
1193 proof - |
|
1194 have "finite K" |
|
1195 by simp |
|
1196 then show ?thesis using that |
|
1197 proof (induction arbitrary: A rule: finite_induct) |
|
1198 case empty |
|
1199 with diagonal show ?case |
|
1200 by simp |
|
1201 next |
|
1202 case (insert k K) |
|
1203 note insertK = insert |
|
1204 have "P A" if kk: "A$k$k \<noteq> 0" |
|
1205 and 0: "\<And>i j. \<lbrakk>j \<in> - insert k K; i \<noteq> j\<rbrakk> \<Longrightarrow> A$i$j = 0" |
|
1206 "\<And>i. \<lbrakk>i \<in> -L; i \<noteq> k\<rbrakk> \<Longrightarrow> A$i$k = 0" for A L |
|
1207 proof - |
|
1208 have "finite L" |
|
1209 by simp |
|
1210 then show ?thesis using 0 kk |
|
1211 proof (induction arbitrary: A rule: finite_induct) |
|
1212 case (empty B) |
|
1213 show ?case |
|
1214 proof (rule insertK) |
|
1215 fix i j |
|
1216 assume "i \<in> - K" "j \<noteq> i" |
|
1217 show "B $ j $ i = 0" |
|
1218 using \<open>j \<noteq> i\<close> \<open>i \<in> - K\<close> empty |
|
1219 by (metis ComplD ComplI Compl_eq_Diff_UNIV Diff_empty UNIV_I insert_iff) |
|
1220 qed |
|
1221 next |
|
1222 case (insert l L B) |
|
1223 show ?case |
|
1224 proof (cases "k = l") |
|
1225 case True |
|
1226 with insert show ?thesis |
|
1227 by auto |
|
1228 next |
|
1229 case False |
|
1230 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" |
|
1231 have 1: "\<lbrakk>j \<in> - insert k K; i \<noteq> j\<rbrakk> \<Longrightarrow> ?C $ i $ j = 0" for j i |
|
1232 by (auto simp: insert.prems(1) row_def) |
|
1233 have 2: "?C $ i $ k = 0" |
|
1234 if "i \<in> - L" "i \<noteq> k" for i |
|
1235 proof (cases "i=l") |
|
1236 case True |
|
1237 with that insert.prems show ?thesis |
|
1238 by (simp add: row_def) |
|
1239 next |
|
1240 case False |
|
1241 with that show ?thesis |
|
1242 by (simp add: insert.prems(2) row_def) |
|
1243 qed |
|
1244 have 3: "?C $ k $ k \<noteq> 0" |
|
1245 by (auto simp: insert.prems row_def \<open>k \<noteq> l\<close>) |
|
1246 have PC: "P ?C" |
|
1247 using insert.IH [OF 1 2 3] by auto |
|
1248 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" |
|
1249 using \<open>k \<noteq> l\<close> by (simp add: vec_eq_iff row_def) |
|
1250 show ?thesis |
|
1251 using row_op [OF PC, of l k, where c = "B$l$k / B$k$k"] eqB \<open>k \<noteq> l\<close> |
|
1252 by (simp add: cong: if_cong) |
|
1253 qed |
|
1254 qed |
|
1255 qed |
|
1256 then have nonzero_hyp: "P A" |
|
1257 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 |
|
1258 by (auto simp: intro!: kk zeroes) |
|
1259 show ?case |
|
1260 proof (cases "row k A = 0") |
|
1261 case True |
|
1262 with zero_row show ?thesis by auto |
|
1263 next |
|
1264 case False |
|
1265 then obtain l where l: "A$k$l \<noteq> 0" |
|
1266 by (auto simp: row_def zero_vec_def vec_eq_iff) |
|
1267 show ?thesis |
|
1268 proof (cases "k = l") |
|
1269 case True |
|
1270 with l nonzero_hyp insert.prems show ?thesis |
|
1271 by blast |
|
1272 next |
|
1273 case False |
|
1274 have *: "A $ i $ Fun.swap k l id j = 0" if "j \<noteq> k" "j \<notin> K" "i \<noteq> j" for i j |
|
1275 using False l insert.prems that |
|
1276 by (auto simp: swap_def insert split: if_split_asm) |
|
1277 have "P (\<chi> i j. (\<chi> i j. A $ i $ Fun.swap k l id j) $ i $ Fun.swap k l id j)" |
|
1278 by (rule swap_cols [OF nonzero_hyp False]) (auto simp: l *) |
|
1279 moreover |
|
1280 have "(\<chi> i j. (\<chi> i j. A $ i $ Fun.swap k l id j) $ i $ Fun.swap k l id j) = A" |
|
1281 by (vector Fun.swap_def) |
|
1282 ultimately show ?thesis |
|
1283 by simp |
|
1284 qed |
|
1285 qed |
|
1286 qed |
|
1287 qed |
|
1288 then show ?thesis |
|
1289 by blast |
|
1290 qed |
|
1291 |
|
1292 lemma%unimportant induct_matrix_elementary: |
|
1293 fixes P :: "real^'n^'n \<Rightarrow> bool" |
|
1294 assumes mult: "\<And>A B. \<lbrakk>P A; P B\<rbrakk> \<Longrightarrow> P(A ** B)" |
|
1295 and zero_row: "\<And>A i. row i A = 0 \<Longrightarrow> P A" |
|
1296 and diagonal: "\<And>A. (\<And>i j. i \<noteq> j \<Longrightarrow> A$i$j = 0) \<Longrightarrow> P A" |
|
1297 and swap1: "\<And>m n. m \<noteq> n \<Longrightarrow> P(\<chi> i j. mat 1 $ i $ Fun.swap m n id j)" |
|
1298 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))" |
|
1299 shows "P A" |
|
1300 proof - |
|
1301 have swap: "P (\<chi> i j. A $ i $ Fun.swap m n id j)" (is "P ?C") |
|
1302 if "P A" "m \<noteq> n" for A m n |
|
1303 proof - |
|
1304 have "A ** (\<chi> i j. mat 1 $ i $ Fun.swap m n id j) = ?C" |
|
1305 by (simp add: matrix_matrix_mult_def mat_def vec_eq_iff if_distrib sum.delta_remove) |
|
1306 then show ?thesis |
|
1307 using mult swap1 that by metis |
|
1308 qed |
|
1309 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") |
|
1310 if "P A" "m \<noteq> n" for A m n c |
|
1311 proof - |
|
1312 let ?B = "\<chi> i j. if i = m \<and> j = n then c else of_bool (i = j)" |
|
1313 have "?B ** A = ?C" |
|
1314 using \<open>m \<noteq> n\<close> unfolding matrix_matrix_mult_def row_def of_bool_def |
|
1315 by (auto simp: vec_eq_iff if_distrib [of "\<lambda>x. x * y" for y] sum.remove cong: if_cong) |
|
1316 then show ?thesis |
|
1317 by (rule subst) (auto simp: that mult idplus) |
|
1318 qed |
|
1319 show ?thesis |
|
1320 by (rule induct_matrix_row_operations [OF zero_row diagonal swap row]) |
|
1321 qed |
|
1322 |
|
1323 lemma%unimportant induct_matrix_elementary_alt: |
|
1324 fixes P :: "real^'n^'n \<Rightarrow> bool" |
|
1325 assumes mult: "\<And>A B. \<lbrakk>P A; P B\<rbrakk> \<Longrightarrow> P(A ** B)" |
|
1326 and zero_row: "\<And>A i. row i A = 0 \<Longrightarrow> P A" |
|
1327 and diagonal: "\<And>A. (\<And>i j. i \<noteq> j \<Longrightarrow> A$i$j = 0) \<Longrightarrow> P A" |
|
1328 and swap1: "\<And>m n. m \<noteq> n \<Longrightarrow> P(\<chi> i j. mat 1 $ i $ Fun.swap m n id j)" |
|
1329 and idplus: "\<And>m n. m \<noteq> n \<Longrightarrow> P(\<chi> i j. of_bool (i = m \<and> j = n \<or> i = j))" |
|
1330 shows "P A" |
|
1331 proof - |
|
1332 have *: "P (\<chi> i j. if i = m \<and> j = n then c else of_bool (i = j))" |
|
1333 if "m \<noteq> n" for m n c |
|
1334 proof (cases "c = 0") |
|
1335 case True |
|
1336 with diagonal show ?thesis by auto |
|
1337 next |
|
1338 case False |
|
1339 then have eq: "(\<chi> i j. if i = m \<and> j = n then c else of_bool (i = j)) = |
|
1340 (\<chi> i j. if i = j then (if j = n then inverse c else 1) else 0) ** |
|
1341 (\<chi> i j. of_bool (i = m \<and> j = n \<or> i = j)) ** |
|
1342 (\<chi> i j. if i = j then if j = n then c else 1 else 0)" |
|
1343 using \<open>m \<noteq> n\<close> |
|
1344 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) |
|
1345 apply (simp add: if_if_eq_conj sum.neutral conj_commute cong: conj_cong) |
|
1346 done |
|
1347 show ?thesis |
|
1348 apply (subst eq) |
|
1349 apply (intro mult idplus that) |
|
1350 apply (auto intro: diagonal) |
|
1351 done |
|
1352 qed |
|
1353 show ?thesis |
|
1354 by (rule induct_matrix_elementary) (auto intro: assms *) |
|
1355 qed |
|
1356 |
|
1357 lemma%unimportant matrix_vector_mult_matrix_matrix_mult_compose: |
|
1358 "(*v) (A ** B) = (*v) A \<circ> (*v) B" |
|
1359 by (auto simp: matrix_vector_mul_assoc) |
|
1360 |
|
1361 lemma%unimportant induct_linear_elementary: |
|
1362 fixes f :: "real^'n \<Rightarrow> real^'n" |
|
1363 assumes "linear f" |
|
1364 and comp: "\<And>f g. \<lbrakk>linear f; linear g; P f; P g\<rbrakk> \<Longrightarrow> P(f \<circ> g)" |
|
1365 and zeroes: "\<And>f i. \<lbrakk>linear f; \<And>x. (f x) $ i = 0\<rbrakk> \<Longrightarrow> P f" |
|
1366 and const: "\<And>c. P(\<lambda>x. \<chi> i. c i * x$i)" |
|
1367 and swap: "\<And>m n::'n. m \<noteq> n \<Longrightarrow> P(\<lambda>x. \<chi> i. x $ Fun.swap m n id i)" |
|
1368 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)" |
|
1369 shows "P f" |
|
1370 proof - |
|
1371 have "P ((*v) A)" for A |
|
1372 proof (rule induct_matrix_elementary_alt) |
|
1373 fix A B |
|
1374 assume "P ((*v) A)" and "P ((*v) B)" |
|
1375 then show "P ((*v) (A ** B))" |
|
1376 by (auto simp add: matrix_vector_mult_matrix_matrix_mult_compose matrix_vector_mul_linear |
|
1377 intro!: comp) |
|
1378 next |
|
1379 fix A :: "real^'n^'n" and i |
|
1380 assume "row i A = 0" |
|
1381 show "P ((*v) A)" |
|
1382 using matrix_vector_mul_linear |
|
1383 by (rule zeroes[where i=i]) |
|
1384 (metis \<open>row i A = 0\<close> inner_zero_left matrix_vector_mul_component row_def vec_lambda_eta) |
|
1385 next |
|
1386 fix A :: "real^'n^'n" |
|
1387 assume 0: "\<And>i j. i \<noteq> j \<Longrightarrow> A $ i $ j = 0" |
|
1388 have "A $ i $ i * x $ i = (\<Sum>j\<in>UNIV. A $ i $ j * x $ j)" for x and i :: "'n" |
|
1389 by (simp add: 0 comm_monoid_add_class.sum.remove [where x=i]) |
|
1390 then have "(\<lambda>x. \<chi> i. A $ i $ i * x $ i) = ((*v) A)" |
|
1391 by (auto simp: 0 matrix_vector_mult_def) |
|
1392 then show "P ((*v) A)" |
|
1393 using const [of "\<lambda>i. A $ i $ i"] by simp |
|
1394 next |
|
1395 fix m n :: "'n" |
|
1396 assume "m \<noteq> n" |
|
1397 have eq: "(\<Sum>j\<in>UNIV. if i = Fun.swap m n id j then x $ j else 0) = |
|
1398 (\<Sum>j\<in>UNIV. if j = Fun.swap m n id i then x $ j else 0)" |
|
1399 for i and x :: "real^'n" |
|
1400 unfolding swap_def by (rule sum.cong) auto |
|
1401 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))" |
|
1402 by (auto simp: mat_def matrix_vector_mult_def eq if_distrib [of "\<lambda>x. x * y" for y] cong: if_cong) |
|
1403 with swap [OF \<open>m \<noteq> n\<close>] show "P ((*v) (\<chi> i j. mat 1 $ i $ Fun.swap m n id j))" |
|
1404 by (simp add: mat_def matrix_vector_mult_def) |
|
1405 next |
|
1406 fix m n :: "'n" |
|
1407 assume "m \<noteq> n" |
|
1408 then have "x $ m + x $ n = (\<Sum>j\<in>UNIV. of_bool (j = n \<or> m = j) * x $ j)" for x :: "real^'n" |
|
1409 by (auto simp: of_bool_def if_distrib [of "\<lambda>x. x * y" for y] sum.remove cong: if_cong) |
|
1410 then have "(\<lambda>x::real^'n. \<chi> i. if i = m then x $ m + x $ n else x $ i) = |
|
1411 ((*v) (\<chi> i j. of_bool (i = m \<and> j = n \<or> i = j)))" |
|
1412 unfolding matrix_vector_mult_def of_bool_def |
|
1413 by (auto simp: vec_eq_iff if_distrib [of "\<lambda>x. x * y" for y] cong: if_cong) |
|
1414 then show "P ((*v) (\<chi> i j. of_bool (i = m \<and> j = n \<or> i = j)))" |
|
1415 using idplus [OF \<open>m \<noteq> n\<close>] by simp |
|
1416 qed |
|
1417 then show ?thesis |
|
1418 by (metis \<open>linear f\<close> matrix_vector_mul) |
|
1419 qed |
|
1420 |
933 end |
1421 end |