src/HOL/Analysis/Determinants.thy
author immler
Thu, 24 May 2018 17:06:39 +0200
changeset 68263 e4e536a71e3d
parent 68143 58c9231c2937
child 68833 fde093888c16
permissions -rw-r--r--
generalized Cramer's rule
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
63627
6ddb43c6b711 rename HOL-Multivariate_Analysis to HOL-Analysis.
hoelzl
parents: 63469
diff changeset
     1
(*  Title:      HOL/Analysis/Determinants.thy
68143
58c9231c2937 tidied some messy proofs
paulson <lp15@cam.ac.uk>
parents: 68138
diff changeset
     2
    Author:     Amine Chaieb, University of Cambridge; proofs reworked by LCP
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
     3
*)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
     4
60420
884f54e01427 isabelle update_cartouches;
wenzelm
parents: 59867
diff changeset
     5
section \<open>Traces, Determinant of square matrices and some properties\<close>
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
     6
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
     7
theory Determinants
44228
5f974bead436 get Multivariate_Analysis/Determinants.thy compiled and working again
huffman
parents: 41959
diff changeset
     8
imports
5f974bead436 get Multivariate_Analysis/Determinants.thy compiled and working again
huffman
parents: 41959
diff changeset
     9
  Cartesian_Euclidean_Space
66453
cc19f7ca2ed6 session-qualified theory imports: isabelle imports -U -i -d '~~/src/Benchmarks' -a;
wenzelm
parents: 64272
diff changeset
    10
  "HOL-Library.Permutations"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    11
begin
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    12
60420
884f54e01427 isabelle update_cartouches;
wenzelm
parents: 59867
diff changeset
    13
subsection \<open>Trace\<close>
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    14
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    15
definition trace :: "'a::semiring_1^'n^'n \<Rightarrow> 'a"
64267
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
    16
  where "trace A = sum (\<lambda>i. ((A$i)$i)) (UNIV::'n set)"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    17
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
    18
lemma trace_0: "trace (mat 0) = 0"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    19
  by (simp add: trace_def mat_def)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    20
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
    21
lemma trace_I: "trace (mat 1 :: 'a::semiring_1^'n^'n) = of_nat(CARD('n))"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    22
  by (simp add: trace_def mat_def)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    23
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
    24
lemma trace_add: "trace ((A::'a::comm_semiring_1^'n^'n) + B) = trace A + trace B"
64267
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
    25
  by (simp add: trace_def sum.distrib)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    26
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
    27
lemma trace_sub: "trace ((A::'a::comm_ring_1^'n^'n) - B) = trace A - trace B"
64267
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
    28
  by (simp add: trace_def sum_subtractf)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    29
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
    30
lemma trace_mul_sym: "trace ((A::'a::comm_semiring_1^'n^'m) ** B) = trace (B**A)"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    31
  apply (simp add: trace_def matrix_matrix_mult_def)
66804
3f9bb52082c4 avoid name clashes on interpretation of abstract locales
haftmann
parents: 66453
diff changeset
    32
  apply (subst sum.swap)
57512
cc97b347b301 reduced name variants for assoc and commute on plus and mult
haftmann
parents: 57418
diff changeset
    33
  apply (simp add: mult.commute)
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    34
  done
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    35
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
    36
subsubsection \<open>Definition of determinant\<close>
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    37
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
    38
definition det:: "'a::comm_ring_1^'n^'n \<Rightarrow> 'a" where
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    39
  "det A =
64272
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
    40
    sum (\<lambda>p. of_int (sign p) * prod (\<lambda>i. A$i$p i) (UNIV :: 'n set))
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    41
      {p. p permutes (UNIV :: 'n set)}"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    42
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
    43
text \<open>Basic determinant properties\<close>
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    44
67673
c8caefb20564 lots of new material, ultimately related to measure theory
paulson <lp15@cam.ac.uk>
parents: 67399
diff changeset
    45
lemma det_transpose [simp]: "det (transpose A) = det (A::'a::comm_ring_1 ^'n^'n)"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    46
proof -
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    47
  let ?di = "\<lambda>A i j. A$i$j"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    48
  let ?U = "(UNIV :: 'n set)"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    49
  have fU: "finite ?U" by simp
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    50
  {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    51
    fix p
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    52
    assume p: "p \<in> {p. p permutes ?U}"
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
    53
    from p have pU: "p permutes ?U"
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
    54
      by blast
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    55
    have sth: "sign (inv p) = sign p"
44260
7784fa3232ce Determinants.thy: avoid using mem_def/Collect_def
huffman
parents: 44228
diff changeset
    56
      by (metis sign_inverse fU p mem_Collect_eq permutation_permutes)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    57
    from permutes_inj[OF pU]
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
    58
    have pi: "inj_on p ?U"
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
    59
      by (blast intro: subset_inj_on)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    60
    from permutes_image[OF pU]
64272
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
    61
    have "prod (\<lambda>i. ?di (transpose A) i (inv p i)) ?U =
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
    62
      prod (\<lambda>i. ?di (transpose A) i (inv p i)) (p ` ?U)"
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
    63
      by simp
64272
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
    64
    also have "\<dots> = prod ((\<lambda>i. ?di (transpose A) i (inv p i)) \<circ> p) ?U"
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
    65
      unfolding prod.reindex[OF pi] ..
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
    66
    also have "\<dots> = prod (\<lambda>i. ?di A i (p i)) ?U"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    67
    proof -
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
    68
      have "((\<lambda>i. ?di (transpose A) i (inv p i)) \<circ> p) i = ?di A i (p i)" if "i \<in> ?U" for i
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
    69
        using that permutes_inv_o[OF pU] permutes_in_image[OF pU]
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
    70
        unfolding transpose_def by (simp add: fun_eq_iff)
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
    71
      then show "prod ((\<lambda>i. ?di (transpose A) i (inv p i)) \<circ> p) ?U = prod (\<lambda>i. ?di A i (p i)) ?U"
64272
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
    72
        by (auto intro: prod.cong)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    73
    qed
64272
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
    74
    finally have "of_int (sign (inv p)) * (prod (\<lambda>i. ?di (transpose A) i (inv p i)) ?U) =
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
    75
      of_int (sign p) * (prod (\<lambda>i. ?di A i (p i)) ?U)"
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
    76
      using sth by simp
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    77
  }
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    78
  then show ?thesis
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    79
    unfolding det_def
68138
c738f40e88d4 auto-tidying
paulson <lp15@cam.ac.uk>
parents: 68134
diff changeset
    80
    by (subst sum_permutations_inverse) (blast intro: sum.cong)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    81
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    82
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    83
lemma det_lowerdiagonal:
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
    84
  fixes A :: "'a::comm_ring_1^('n::{finite,wellorder})^('n::{finite,wellorder})"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    85
  assumes ld: "\<And>i j. i < j \<Longrightarrow> A$i$j = 0"
64272
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
    86
  shows "det A = prod (\<lambda>i. A$i$i) (UNIV:: 'n set)"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    87
proof -
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    88
  let ?U = "UNIV:: 'n set"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    89
  let ?PU = "{p. p permutes ?U}"
64272
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
    90
  let ?pp = "\<lambda>p. of_int (sign p) * prod (\<lambda>i. A$i$p i) (UNIV :: 'n set)"
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
    91
  have fU: "finite ?U"
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
    92
    by simp
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
    93
  have id0: "{id} \<subseteq> ?PU"
68138
c738f40e88d4 auto-tidying
paulson <lp15@cam.ac.uk>
parents: 68134
diff changeset
    94
    by (auto simp: permutes_id)
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
    95
  have p0: "\<forall>p \<in> ?PU - {id}. ?pp p = 0"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
    96
  proof
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    97
    fix p
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
    98
    assume "p \<in> ?PU - {id}"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
    99
    then obtain i where i: "p i > i"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   100
      by clarify (meson leI permutes_natset_le)
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   101
    from ld[OF i] have "\<exists>i \<in> ?U. A$i$p i = 0"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   102
      by blast
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   103
    with prod_zero[OF fU] show "?pp p = 0"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   104
      by force
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   105
  qed
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   106
  from sum.mono_neutral_cong_left[OF finite_permutations[OF fU] id0 p0] show ?thesis
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   107
    unfolding det_def by (simp add: sign_id)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   108
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   109
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   110
lemma det_upperdiagonal:
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
   111
  fixes A :: "'a::comm_ring_1^'n::{finite,wellorder}^'n::{finite,wellorder}"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   112
  assumes ld: "\<And>i j. i > j \<Longrightarrow> A$i$j = 0"
64272
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
   113
  shows "det A = prod (\<lambda>i. A$i$i) (UNIV:: 'n set)"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   114
proof -
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   115
  let ?U = "UNIV:: 'n set"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   116
  let ?PU = "{p. p permutes ?U}"
64272
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
   117
  let ?pp = "(\<lambda>p. of_int (sign p) * prod (\<lambda>i. A$i$p i) (UNIV :: 'n set))"
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   118
  have fU: "finite ?U"
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   119
    by simp
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   120
  have id0: "{id} \<subseteq> ?PU"
68138
c738f40e88d4 auto-tidying
paulson <lp15@cam.ac.uk>
parents: 68134
diff changeset
   121
    by (auto simp: permutes_id)
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   122
  have p0: "\<forall>p \<in> ?PU -{id}. ?pp p = 0"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   123
  proof
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   124
    fix p
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   125
    assume p: "p \<in> ?PU - {id}"
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   126
    then obtain i where i: "p i < i"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   127
      by clarify (meson leI permutes_natset_ge)
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   128
    from ld[OF i] have "\<exists>i \<in> ?U. A$i$p i = 0"
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   129
      by blast
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   130
    with prod_zero[OF fU]  show "?pp p = 0"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   131
      by force
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   132
  qed
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   133
  from sum.mono_neutral_cong_left[OF finite_permutations[OF fU] id0 p0] show ?thesis
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   134
    unfolding det_def by (simp add: sign_id)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   135
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   136
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   137
lemma det_diagonal:
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
   138
  fixes A :: "'a::comm_ring_1^'n^'n"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   139
  assumes ld: "\<And>i j. i \<noteq> j \<Longrightarrow> A$i$j = 0"
64272
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
   140
  shows "det A = prod (\<lambda>i. A$i$i) (UNIV::'n set)"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   141
proof -
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   142
  let ?U = "UNIV:: 'n set"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   143
  let ?PU = "{p. p permutes ?U}"
64272
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
   144
  let ?pp = "\<lambda>p. of_int (sign p) * prod (\<lambda>i. A$i$p i) (UNIV :: 'n set)"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   145
  have fU: "finite ?U" by simp
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   146
  from finite_permutations[OF fU] have fPU: "finite ?PU" .
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   147
  have id0: "{id} \<subseteq> ?PU"
68138
c738f40e88d4 auto-tidying
paulson <lp15@cam.ac.uk>
parents: 68134
diff changeset
   148
    by (auto simp: permutes_id)
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   149
  have p0: "\<forall>p \<in> ?PU - {id}. ?pp p = 0"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   150
  proof
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   151
    fix p
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   152
    assume p: "p \<in> ?PU - {id}"
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   153
    then obtain i where i: "p i \<noteq> i"
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   154
      by fastforce
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   155
    with ld have "\<exists>i \<in> ?U. A$i$p i = 0"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   156
      by (metis UNIV_I)
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   157
    with prod_zero [OF fU] show "?pp p = 0"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   158
      by force
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   159
  qed
64267
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   160
  from sum.mono_neutral_cong_left[OF fPU id0 p0] show ?thesis
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   161
    unfolding det_def by (simp add: sign_id)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   162
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   163
67673
c8caefb20564 lots of new material, ultimately related to measure theory
paulson <lp15@cam.ac.uk>
parents: 67399
diff changeset
   164
lemma det_I [simp]: "det (mat 1 :: 'a::comm_ring_1^'n^'n) = 1"
c8caefb20564 lots of new material, ultimately related to measure theory
paulson <lp15@cam.ac.uk>
parents: 67399
diff changeset
   165
  by (simp add: det_diagonal mat_def)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   166
67673
c8caefb20564 lots of new material, ultimately related to measure theory
paulson <lp15@cam.ac.uk>
parents: 67399
diff changeset
   167
lemma det_0 [simp]: "det (mat 0 :: 'a::comm_ring_1^'n^'n) = 0"
67970
8c012a49293a A couple of new results
paulson <lp15@cam.ac.uk>
parents: 67733
diff changeset
   168
  by (simp add: det_def prod_zero power_0_left)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   169
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   170
lemma det_permute_rows:
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
   171
  fixes A :: "'a::comm_ring_1^'n^'n"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   172
  assumes p: "p permutes (UNIV :: 'n::finite set)"
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   173
  shows "det (\<chi> i. A$p i :: 'a^'n^'n) = of_int (sign p) * det A"
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   174
proof -
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   175
  let ?U = "UNIV :: 'n set"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   176
  let ?PU = "{p. p permutes ?U}"
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   177
  have *: "(\<Sum>q\<in>?PU. of_int (sign (q \<circ> p)) * (\<Prod>i\<in>?U. A $ p i $ (q \<circ> p) i)) =
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   178
           (\<Sum>n\<in>?PU. of_int (sign p) * of_int (sign n) * (\<Prod>i\<in>?U. A $ i $ n i))"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   179
  proof (rule sum.cong)
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   180
    fix q
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   181
    assume qPU: "q \<in> ?PU"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   182
    have fU: "finite ?U"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   183
      by simp
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   184
    from qPU have q: "q permutes ?U"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   185
      by blast
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   186
    have "prod (\<lambda>i. A$p i$ (q \<circ> p) i) ?U = prod ((\<lambda>i. A$p i$(q \<circ> p) i) \<circ> inv p) ?U"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   187
      by (simp only: prod.permute[OF permutes_inv[OF p], symmetric])
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   188
    also have "\<dots> = prod (\<lambda>i. A $ (p \<circ> inv p) i $ (q \<circ> (p \<circ> inv p)) i) ?U"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   189
      by (simp only: o_def)
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   190
    also have "\<dots> = prod (\<lambda>i. A$i$q i) ?U"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   191
      by (simp only: o_def permutes_inverses[OF p])
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   192
    finally have thp: "prod (\<lambda>i. A$p i$ (q \<circ> p) i) ?U = prod (\<lambda>i. A$i$q i) ?U"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   193
      by blast
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   194
    from p q have pp: "permutation p" and qp: "permutation q"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   195
      by (metis fU permutation_permutes)+
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   196
    show "of_int (sign (q \<circ> p)) * prod (\<lambda>i. A$ p i$ (q \<circ> p) i) ?U =
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   197
          of_int (sign p) * of_int (sign q) * prod (\<lambda>i. A$i$q i) ?U"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   198
      by (simp only: thp sign_compose[OF qp pp] mult.commute of_int_mult)
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   199
  qed auto
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   200
  show ?thesis
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   201
    apply (simp add: det_def sum_distrib_left mult.assoc[symmetric])
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   202
    apply (subst sum_permutations_compose_right[OF p])
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   203
    apply (rule *)
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   204
    done
68143
58c9231c2937 tidied some messy proofs
paulson <lp15@cam.ac.uk>
parents: 68138
diff changeset
   205
qed
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   206
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   207
lemma det_permute_columns:
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
   208
  fixes A :: "'a::comm_ring_1^'n^'n"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   209
  assumes p: "p permutes (UNIV :: 'n set)"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   210
  shows "det(\<chi> i j. A$i$ p j :: 'a^'n^'n) = of_int (sign p) * det A"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   211
proof -
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   212
  let ?Ap = "\<chi> i j. A$i$ p j :: 'a^'n^'n"
35150
082fa4bd403d Rename transp to transpose in HOL-Multivariate_Analysis. (by himmelma)
hoelzl
parents: 35028
diff changeset
   213
  let ?At = "transpose A"
082fa4bd403d Rename transp to transpose in HOL-Multivariate_Analysis. (by himmelma)
hoelzl
parents: 35028
diff changeset
   214
  have "of_int (sign p) * det A = det (transpose (\<chi> i. transpose A $ p i))"
082fa4bd403d Rename transp to transpose in HOL-Multivariate_Analysis. (by himmelma)
hoelzl
parents: 35028
diff changeset
   215
    unfolding det_permute_rows[OF p, of ?At] det_transpose ..
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   216
  moreover
35150
082fa4bd403d Rename transp to transpose in HOL-Multivariate_Analysis. (by himmelma)
hoelzl
parents: 35028
diff changeset
   217
  have "?Ap = transpose (\<chi> i. transpose A $ p i)"
44228
5f974bead436 get Multivariate_Analysis/Determinants.thy compiled and working again
huffman
parents: 41959
diff changeset
   218
    by (simp add: transpose_def vec_eq_iff)
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   219
  ultimately show ?thesis
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   220
    by simp
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   221
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   222
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   223
lemma det_identical_columns:
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   224
  fixes A :: "'a::comm_ring_1^'n^'n"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   225
  assumes jk: "j \<noteq> k"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   226
    and r: "column j A = column k A"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   227
  shows "det A = 0"
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   228
proof -
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   229
  let ?U="UNIV::'n set"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   230
  let ?t_jk="Fun.swap j k id"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   231
  let ?PU="{p. p permutes ?U}"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   232
  let ?S1="{p. p\<in>?PU \<and> evenperm p}"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   233
  let ?S2="{(?t_jk \<circ> p) |p. p \<in>?S1}"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   234
  let ?f="\<lambda>p. of_int (sign p) * (\<Prod>i\<in>UNIV. A $ i $ p i)"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   235
  let ?g="\<lambda>p. ?t_jk \<circ> p"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   236
  have g_S1: "?S2 = ?g` ?S1" by auto
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   237
  have inj_g: "inj_on ?g ?S1"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   238
  proof (unfold inj_on_def, auto)
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   239
    fix x y assume x: "x permutes ?U" and even_x: "evenperm x"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   240
      and y: "y permutes ?U" and even_y: "evenperm y" and eq: "?t_jk \<circ> x = ?t_jk \<circ> y"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   241
    show "x = y" by (metis (hide_lams, no_types) comp_assoc eq id_comp swap_id_idempotent)
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   242
  qed
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   243
  have tjk_permutes: "?t_jk permutes ?U" unfolding permutes_def swap_id_eq by (auto,metis)
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   244
  have tjk_eq: "\<forall>i l. A $ i $ ?t_jk l  =  A $ i $ l"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   245
    using r jk
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   246
    unfolding column_def vec_eq_iff swap_id_eq by fastforce
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   247
  have sign_tjk: "sign ?t_jk = -1" using sign_swap_id[of j k] jk by auto
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   248
  {fix x
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   249
    assume x: "x\<in> ?S1"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   250
    have "sign (?t_jk \<circ> x) = sign (?t_jk) * sign x"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   251
      by (metis (lifting) finite_class.finite_UNIV mem_Collect_eq
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   252
          permutation_permutes permutation_swap_id sign_compose x)
68138
c738f40e88d4 auto-tidying
paulson <lp15@cam.ac.uk>
parents: 68134
diff changeset
   253
    also have "\<dots> = - sign x" using sign_tjk by simp
c738f40e88d4 auto-tidying
paulson <lp15@cam.ac.uk>
parents: 68134
diff changeset
   254
    also have "\<dots> \<noteq> sign x" unfolding sign_def by simp
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   255
    finally have "sign (?t_jk \<circ> x) \<noteq> sign x" and "(?t_jk \<circ> x) \<in> ?S2"
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   256
      using x by force+
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   257
  }
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   258
  hence disjoint: "?S1 \<inter> ?S2 = {}"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   259
    by (force simp: sign_def)
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   260
  have PU_decomposition: "?PU = ?S1 \<union> ?S2"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   261
  proof (auto)
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   262
    fix x
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   263
    assume x: "x permutes ?U" and "\<forall>p. p permutes ?U \<longrightarrow> x = Fun.swap j k id \<circ> p \<longrightarrow> \<not> evenperm p"
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   264
    then obtain p where p: "p permutes UNIV" and x_eq: "x = Fun.swap j k id \<circ> p"
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   265
      and odd_p: "\<not> evenperm p"
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   266
      by (metis (mono_tags) id_o o_assoc permutes_compose swap_id_idempotent tjk_permutes)
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   267
    thus "evenperm x"
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   268
      by (meson evenperm_comp evenperm_swap finite_class.finite_UNIV
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   269
          jk permutation_permutes permutation_swap_id)
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   270
  next
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   271
    fix p assume p: "p permutes ?U"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   272
    show "Fun.swap j k id \<circ> p permutes UNIV" by (metis p permutes_compose tjk_permutes)
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   273
  qed
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   274
  have "sum ?f ?S2 = sum ((\<lambda>p. of_int (sign p) * (\<Prod>i\<in>UNIV. A $ i $ p i))
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   275
  \<circ> (\<circ>) (Fun.swap j k id)) {p \<in> {p. p permutes UNIV}. evenperm p}"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   276
    unfolding g_S1 by (rule sum.reindex[OF inj_g])
68138
c738f40e88d4 auto-tidying
paulson <lp15@cam.ac.uk>
parents: 68134
diff changeset
   277
  also have "\<dots> = sum (\<lambda>p. of_int (sign (?t_jk \<circ> p)) * (\<Prod>i\<in>UNIV. A $ i $ p i)) ?S1"
c738f40e88d4 auto-tidying
paulson <lp15@cam.ac.uk>
parents: 68134
diff changeset
   278
    unfolding o_def by (rule sum.cong, auto simp: tjk_eq)
c738f40e88d4 auto-tidying
paulson <lp15@cam.ac.uk>
parents: 68134
diff changeset
   279
  also have "\<dots> = sum (\<lambda>p. - ?f p) ?S1"
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   280
  proof (rule sum.cong, auto)
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   281
    fix x assume x: "x permutes ?U"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   282
      and even_x: "evenperm x"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   283
    hence perm_x: "permutation x" and perm_tjk: "permutation ?t_jk"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   284
      using permutation_permutes[of x] permutation_permutes[of ?t_jk] permutation_swap_id
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   285
      by (metis finite_code)+
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   286
    have "(sign (?t_jk \<circ> x)) = - (sign x)"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   287
      unfolding sign_compose[OF perm_tjk perm_x] sign_tjk by auto
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   288
    thus "of_int (sign (?t_jk \<circ> x)) * (\<Prod>i\<in>UNIV. A $ i $ x i)
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   289
      = - (of_int (sign x) * (\<Prod>i\<in>UNIV. A $ i $ x i))"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   290
      by auto
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   291
  qed
68138
c738f40e88d4 auto-tidying
paulson <lp15@cam.ac.uk>
parents: 68134
diff changeset
   292
  also have "\<dots>= - sum ?f ?S1" unfolding sum_negf ..
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   293
  finally have *: "sum ?f ?S2 = - sum ?f ?S1" .
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   294
  have "det A = (\<Sum>p | p permutes UNIV. of_int (sign p) * (\<Prod>i\<in>UNIV. A $ i $ p i))"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   295
    unfolding det_def ..
68138
c738f40e88d4 auto-tidying
paulson <lp15@cam.ac.uk>
parents: 68134
diff changeset
   296
  also have "\<dots>= sum ?f ?S1 + sum ?f ?S2"
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   297
    by (subst PU_decomposition, rule sum.union_disjoint[OF _ _ disjoint], auto)
68138
c738f40e88d4 auto-tidying
paulson <lp15@cam.ac.uk>
parents: 68134
diff changeset
   298
  also have "\<dots>= sum ?f ?S1 - sum ?f ?S1 " unfolding * by auto
c738f40e88d4 auto-tidying
paulson <lp15@cam.ac.uk>
parents: 68134
diff changeset
   299
  also have "\<dots>= 0" by simp
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   300
  finally show "det A = 0" by simp
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   301
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   302
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   303
lemma det_identical_rows:
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   304
  fixes A :: "'a::comm_ring_1^'n^'n"
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   305
  assumes ij: "i \<noteq> j" and r: "row i A = row j A"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   306
  shows "det A = 0"
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   307
  by (metis column_transpose det_identical_columns det_transpose ij r)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   308
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   309
lemma det_zero_row:
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   310
  fixes A :: "'a::{idom, ring_char_0}^'n^'n" and F :: "'b::{field}^'m^'m"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   311
  shows "row i A = 0 \<Longrightarrow> det A = 0" and "row j F = 0 \<Longrightarrow> det F = 0"
68138
c738f40e88d4 auto-tidying
paulson <lp15@cam.ac.uk>
parents: 68134
diff changeset
   312
  by (force simp: row_def det_def vec_eq_iff sign_nz intro!: sum.neutral)+
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   313
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   314
lemma det_zero_column:
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   315
  fixes A :: "'a::{idom, ring_char_0}^'n^'n" and F :: "'b::{field}^'m^'m"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   316
  shows "column i A = 0 \<Longrightarrow> det A = 0" and "column j F = 0 \<Longrightarrow> det F = 0"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   317
  unfolding atomize_conj atomize_imp
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   318
  by (metis det_transpose det_zero_row row_transpose)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   319
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   320
lemma det_row_add:
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   321
  fixes a b c :: "'n::finite \<Rightarrow> _ ^ 'n"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   322
  shows "det((\<chi> i. if i = k then a i + b i else c i)::'a::comm_ring_1^'n^'n) =
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   323
    det((\<chi> i. if i = k then a i else c i)::'a::comm_ring_1^'n^'n) +
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   324
    det((\<chi> i. if i = k then b i else c i)::'a::comm_ring_1^'n^'n)"
64267
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   325
  unfolding det_def vec_lambda_beta sum.distrib[symmetric]
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   326
proof (rule sum.cong)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   327
  let ?U = "UNIV :: 'n set"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   328
  let ?pU = "{p. p permutes ?U}"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   329
  let ?f = "(\<lambda>i. if i = k then a i + b i else c i)::'n \<Rightarrow> 'a::comm_ring_1^'n"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   330
  let ?g = "(\<lambda> i. if i = k then a i else c i)::'n \<Rightarrow> 'a::comm_ring_1^'n"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   331
  let ?h = "(\<lambda> i. if i = k then b i else c i)::'n \<Rightarrow> 'a::comm_ring_1^'n"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   332
  fix p
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   333
  assume p: "p \<in> ?pU"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   334
  let ?Uk = "?U - {k}"
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   335
  from p have pU: "p permutes ?U"
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   336
    by blast
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   337
  have kU: "?U = insert k ?Uk"
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   338
    by blast
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   339
  have eq: "prod (\<lambda>i. ?f i $ p i) ?Uk = prod (\<lambda>i. ?g i $ p i) ?Uk"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   340
           "prod (\<lambda>i. ?f i $ p i) ?Uk = prod (\<lambda>i. ?h i $ p i) ?Uk"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   341
    by auto
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   342
  have Uk: "finite ?Uk" "k \<notin> ?Uk"
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   343
    by auto
64272
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
   344
  have "prod (\<lambda>i. ?f i $ p i) ?U = prod (\<lambda>i. ?f i $ p i) (insert k ?Uk)"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   345
    unfolding kU[symmetric] ..
64272
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
   346
  also have "\<dots> = ?f k $ p k * prod (\<lambda>i. ?f i $ p i) ?Uk"
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   347
    by (rule prod.insert) auto
64272
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
   348
  also have "\<dots> = (a k $ p k * prod (\<lambda>i. ?f i $ p i) ?Uk) + (b k$ p k * prod (\<lambda>i. ?f i $ p i) ?Uk)"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   349
    by (simp add: field_simps)
64272
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
   350
  also have "\<dots> = (a k $ p k * prod (\<lambda>i. ?g i $ p i) ?Uk) + (b k$ p k * prod (\<lambda>i. ?h i $ p i) ?Uk)"
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   351
    by (metis eq)
64272
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
   352
  also have "\<dots> = prod (\<lambda>i. ?g i $ p i) (insert k ?Uk) + prod (\<lambda>i. ?h i $ p i) (insert k ?Uk)"
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   353
    unfolding  prod.insert[OF Uk] by simp
64272
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
   354
  finally have "prod (\<lambda>i. ?f i $ p i) ?U = prod (\<lambda>i. ?g i $ p i) ?U + prod (\<lambda>i. ?h i $ p i) ?U"
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   355
    unfolding kU[symmetric] .
64272
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
   356
  then show "of_int (sign p) * prod (\<lambda>i. ?f i $ p i) ?U =
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
   357
    of_int (sign p) * prod (\<lambda>i. ?g i $ p i) ?U + of_int (sign p) * prod (\<lambda>i. ?h i $ p i) ?U"
36350
bc7982c54e37 dropped group_simps, ring_simps, field_eq_simps
haftmann
parents: 35542
diff changeset
   358
    by (simp add: field_simps)
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   359
qed auto
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   360
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   361
lemma det_row_mul:
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   362
  fixes a b :: "'n::finite \<Rightarrow> _ ^ 'n"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   363
  shows "det((\<chi> i. if i = k then c *s a i else b i)::'a::comm_ring_1^'n^'n) =
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   364
    c * det((\<chi> i. if i = k then a i else b i)::'a::comm_ring_1^'n^'n)"
64267
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   365
  unfolding det_def vec_lambda_beta sum_distrib_left
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   366
proof (rule sum.cong)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   367
  let ?U = "UNIV :: 'n set"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   368
  let ?pU = "{p. p permutes ?U}"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   369
  let ?f = "(\<lambda>i. if i = k then c*s a i else b i)::'n \<Rightarrow> 'a::comm_ring_1^'n"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   370
  let ?g = "(\<lambda> i. if i = k then a i else b i)::'n \<Rightarrow> 'a::comm_ring_1^'n"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   371
  fix p
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   372
  assume p: "p \<in> ?pU"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   373
  let ?Uk = "?U - {k}"
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   374
  from p have pU: "p permutes ?U"
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   375
    by blast
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   376
  have kU: "?U = insert k ?Uk"
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   377
    by blast
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   378
  have eq: "prod (\<lambda>i. ?f i $ p i) ?Uk = prod (\<lambda>i. ?g i $ p i) ?Uk"
68138
c738f40e88d4 auto-tidying
paulson <lp15@cam.ac.uk>
parents: 68134
diff changeset
   379
    by auto
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   380
  have Uk: "finite ?Uk" "k \<notin> ?Uk"
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   381
    by auto
64272
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
   382
  have "prod (\<lambda>i. ?f i $ p i) ?U = prod (\<lambda>i. ?f i $ p i) (insert k ?Uk)"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   383
    unfolding kU[symmetric] ..
64272
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
   384
  also have "\<dots> = ?f k $ p k  * prod (\<lambda>i. ?f i $ p i) ?Uk"
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   385
    by (rule prod.insert) auto
64272
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
   386
  also have "\<dots> = (c*s a k) $ p k * prod (\<lambda>i. ?f i $ p i) ?Uk"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   387
    by (simp add: field_simps)
64272
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
   388
  also have "\<dots> = c* (a k $ p k * prod (\<lambda>i. ?g i $ p i) ?Uk)"
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   389
    unfolding eq by (simp add: ac_simps)
64272
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
   390
  also have "\<dots> = c* (prod (\<lambda>i. ?g i $ p i) (insert k ?Uk))"
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   391
    unfolding prod.insert[OF Uk] by simp
64272
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
   392
  finally have "prod (\<lambda>i. ?f i $ p i) ?U = c* (prod (\<lambda>i. ?g i $ p i) ?U)"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   393
    unfolding kU[symmetric] .
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   394
  then show "of_int (sign p) * prod (\<lambda>i. ?f i $ p i) ?U = c * (of_int (sign p) * prod (\<lambda>i. ?g i $ p i) ?U)"
36350
bc7982c54e37 dropped group_simps, ring_simps, field_eq_simps
haftmann
parents: 35542
diff changeset
   395
    by (simp add: field_simps)
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   396
qed auto
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   397
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   398
lemma det_row_0:
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   399
  fixes b :: "'n::finite \<Rightarrow> _ ^ 'n"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   400
  shows "det((\<chi> i. if i = k then 0 else b i)::'a::comm_ring_1^'n^'n) = 0"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   401
  using det_row_mul[of k 0 "\<lambda>i. 1" b]
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   402
  apply simp
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   403
  apply (simp only: vector_smult_lzero)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   404
  done
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   405
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   406
lemma det_row_operation:
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   407
  fixes A :: "'a::{comm_ring_1}^'n^'n"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   408
  assumes ij: "i \<noteq> j"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   409
  shows "det (\<chi> k. if k = i then row i A + c *s row j A else row k A) = det A"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   410
proof -
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   411
  let ?Z = "(\<chi> k. if k = i then row j A else row k A) :: 'a ^'n^'n"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   412
  have th: "row i ?Z = row j ?Z" by (vector row_def)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   413
  have th2: "((\<chi> k. if k = i then row i A else row k A) :: 'a^'n^'n) = A"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   414
    by (vector row_def)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   415
  show ?thesis
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   416
    unfolding det_row_add [of i] det_row_mul[of i] det_identical_rows[OF ij th] th2
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   417
    by simp
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   418
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   419
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   420
lemma det_row_span:
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   421
  fixes A :: "'a::{field}^'n^'n"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   422
  assumes x: "x \<in> vec.span {row j A |j. j \<noteq> i}"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   423
  shows "det (\<chi> k. if k = i then row i A + x else row k A) = det A"
68069
36209dfb981e tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents: 68050
diff changeset
   424
  using x
68074
8d50467f7555 fixed HOL-Analysis
immler
parents: 68073
diff changeset
   425
proof (induction rule: vec.span_induct_alt)
68069
36209dfb981e tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents: 68050
diff changeset
   426
  case base
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   427
  have "(if k = i then row i A + 0 else row k A) = row k A" for k
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   428
    by simp
68069
36209dfb981e tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents: 68050
diff changeset
   429
  then show ?case
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   430
    by (simp add: row_def)
68069
36209dfb981e tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents: 68050
diff changeset
   431
next
36209dfb981e tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents: 68050
diff changeset
   432
  case (step c z y)
36209dfb981e tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents: 68050
diff changeset
   433
  then obtain j where j: "z = row j A" "i \<noteq> j"
36209dfb981e tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents: 68050
diff changeset
   434
    by blast
36209dfb981e tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents: 68050
diff changeset
   435
  let ?w = "row i A + y"
36209dfb981e tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents: 68050
diff changeset
   436
  have th0: "row i A + (c*s z + y) = ?w + c*s z"
36209dfb981e tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents: 68050
diff changeset
   437
    by vector
36209dfb981e tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents: 68050
diff changeset
   438
  let ?d = "\<lambda>x. det (\<chi> k. if k = i then x else row k A)"
36209dfb981e tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents: 68050
diff changeset
   439
  have thz: "?d z = 0"
36209dfb981e tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents: 68050
diff changeset
   440
    apply (rule det_identical_rows[OF j(2)])
36209dfb981e tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents: 68050
diff changeset
   441
    using j
36209dfb981e tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents: 68050
diff changeset
   442
    apply (vector row_def)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   443
    done
68069
36209dfb981e tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents: 68050
diff changeset
   444
  have "?d (row i A + (c*s z + y)) = ?d (?w + c*s z)"
36209dfb981e tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents: 68050
diff changeset
   445
    unfolding th0 ..
36209dfb981e tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents: 68050
diff changeset
   446
  then have "?d (row i A + (c*s z + y)) = det A"
36209dfb981e tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents: 68050
diff changeset
   447
    unfolding thz step.IH det_row_mul[of i] det_row_add[of i] by simp
36209dfb981e tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents: 68050
diff changeset
   448
  then show ?case
36209dfb981e tidying up and using real induction methods
paulson <lp15@cam.ac.uk>
parents: 68050
diff changeset
   449
    unfolding scalar_mult_eq_scaleR .
68143
58c9231c2937 tidied some messy proofs
paulson <lp15@cam.ac.uk>
parents: 68138
diff changeset
   450
qed
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   451
67673
c8caefb20564 lots of new material, ultimately related to measure theory
paulson <lp15@cam.ac.uk>
parents: 67399
diff changeset
   452
lemma matrix_id [simp]: "det (matrix id) = 1"
c8caefb20564 lots of new material, ultimately related to measure theory
paulson <lp15@cam.ac.uk>
parents: 67399
diff changeset
   453
  by (simp add: matrix_id_mat_1)
c8caefb20564 lots of new material, ultimately related to measure theory
paulson <lp15@cam.ac.uk>
parents: 67399
diff changeset
   454
c8caefb20564 lots of new material, ultimately related to measure theory
paulson <lp15@cam.ac.uk>
parents: 67399
diff changeset
   455
lemma det_matrix_scaleR [simp]: "det (matrix ((( *\<^sub>R) r)) :: real^'n^'n) = r ^ CARD('n::finite)"
c8caefb20564 lots of new material, ultimately related to measure theory
paulson <lp15@cam.ac.uk>
parents: 67399
diff changeset
   456
  apply (subst det_diagonal)
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   457
   apply (auto simp: matrix_def mat_def)
67673
c8caefb20564 lots of new material, ultimately related to measure theory
paulson <lp15@cam.ac.uk>
parents: 67399
diff changeset
   458
  apply (simp add: cart_eq_inner_axis inner_axis_axis)
c8caefb20564 lots of new material, ultimately related to measure theory
paulson <lp15@cam.ac.uk>
parents: 67399
diff changeset
   459
  done
c8caefb20564 lots of new material, ultimately related to measure theory
paulson <lp15@cam.ac.uk>
parents: 67399
diff changeset
   460
60420
884f54e01427 isabelle update_cartouches;
wenzelm
parents: 59867
diff changeset
   461
text \<open>
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   462
  May as well do this, though it's a bit unsatisfactory since it ignores
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   463
  exact duplicates by considering the rows/columns as a set.
60420
884f54e01427 isabelle update_cartouches;
wenzelm
parents: 59867
diff changeset
   464
\<close>
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   465
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   466
lemma det_dependent_rows:
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   467
  fixes A:: "'a::{field}^'n^'n"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   468
  assumes d: "vec.dependent (rows A)"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   469
  shows "det A = 0"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   470
proof -
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   471
  let ?U = "UNIV :: 'n set"
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   472
  from d obtain i where i: "row i A \<in> vec.span (rows A - {row i A})"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   473
    unfolding vec.dependent_def rows_def by blast
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   474
  show ?thesis
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   475
  proof (cases "\<forall>i j. i \<noteq> j \<longrightarrow> row i A \<noteq> row j A")
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   476
    case True
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   477
    with i have "vec.span (rows A - {row i A}) \<subseteq> vec.span {row j A |j. j \<noteq> i}"
68138
c738f40e88d4 auto-tidying
paulson <lp15@cam.ac.uk>
parents: 68134
diff changeset
   478
      by (auto simp: rows_def intro!: vec.span_mono)
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   479
    then have "- row i A \<in> vec.span {row j A|j. j \<noteq> i}"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   480
      by (meson i subsetCE vec.span_neg)
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   481
    from det_row_span[OF this]
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   482
    have "det A = det (\<chi> k. if k = i then 0 *s 1 else row k A)"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   483
      unfolding right_minus vector_smult_lzero ..
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   484
    with det_row_mul[of i 0 "\<lambda>i. 1"]
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   485
    show ?thesis by simp
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   486
  next
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   487
    case False
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   488
    then obtain j k where jk: "j \<noteq> k" "row j A = row k A"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   489
      by auto
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   490
    from det_identical_rows[OF jk] show ?thesis .
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   491
  qed
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   492
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   493
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   494
lemma det_dependent_columns:
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   495
  assumes d: "vec.dependent (columns (A::real^'n^'n))"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   496
  shows "det A = 0"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   497
  by (metis d det_dependent_rows rows_transpose det_transpose)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   498
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   499
text \<open>Multilinearity and the multiplication formula\<close>
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   500
44228
5f974bead436 get Multivariate_Analysis/Determinants.thy compiled and working again
huffman
parents: 41959
diff changeset
   501
lemma Cart_lambda_cong: "(\<And>x. f x = g x) \<Longrightarrow> (vec_lambda f::'a^'n) = (vec_lambda g :: 'a^'n)"
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   502
  by auto
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   503
64267
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   504
lemma det_linear_row_sum:
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   505
  assumes fS: "finite S"
64267
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   506
  shows "det ((\<chi> i. if i = k then sum (a i) S else c i)::'a::comm_ring_1^'n^'n) =
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   507
    sum (\<lambda>j. det ((\<chi> i. if i = k then a  i j else c i)::'a^'n^'n)) S"
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   508
  using fS  by (induct rule: finite_induct; simp add: det_row_0 det_row_add cong: if_cong)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   509
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   510
lemma finite_bounded_functions:
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   511
  assumes fS: "finite S"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   512
  shows "finite {f. (\<forall>i \<in> {1.. (k::nat)}. f i \<in> S) \<and> (\<forall>i. i \<notin> {1 .. k} \<longrightarrow> f i = i)}"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   513
proof (induct k)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   514
  case 0
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   515
  have *: "{f. \<forall>i. f i = i} = {id}"
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   516
    by auto
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   517
  show ?case
68138
c738f40e88d4 auto-tidying
paulson <lp15@cam.ac.uk>
parents: 68134
diff changeset
   518
    by (auto simp: *)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   519
next
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   520
  case (Suc k)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   521
  let ?f = "\<lambda>(y::nat,g) i. if i = Suc k then y else g i"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   522
  let ?S = "?f ` (S \<times> {f. (\<forall>i\<in>{1..k}. f i \<in> S) \<and> (\<forall>i. i \<notin> {1..k} \<longrightarrow> f i = i)})"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   523
  have "?S = {f. (\<forall>i\<in>{1.. Suc k}. f i \<in> S) \<and> (\<forall>i. i \<notin> {1.. Suc k} \<longrightarrow> f i = i)}"
68138
c738f40e88d4 auto-tidying
paulson <lp15@cam.ac.uk>
parents: 68134
diff changeset
   524
    apply (auto simp: image_iff)
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   525
    apply (rename_tac f)
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   526
    apply (rule_tac x="f (Suc k)" in bexI)
68138
c738f40e88d4 auto-tidying
paulson <lp15@cam.ac.uk>
parents: 68134
diff changeset
   527
    apply (rule_tac x = "\<lambda>i. if i = Suc k then i else f i" in exI, auto)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   528
    done
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   529
  with finite_imageI[OF finite_cartesian_product[OF fS Suc.hyps(1)], of ?f]
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   530
  show ?case
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   531
    by metis
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   532
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   533
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   534
64267
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   535
lemma det_linear_rows_sum_lemma:
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   536
  assumes fS: "finite S"
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   537
    and fT: "finite T"
64267
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   538
  shows "det ((\<chi> i. if i \<in> T then sum (a i) S else c i):: 'a::comm_ring_1^'n^'n) =
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   539
    sum (\<lambda>f. det((\<chi> i. if i \<in> T then a i (f i) else c i)::'a^'n^'n))
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   540
      {f. (\<forall>i \<in> T. f i \<in> S) \<and> (\<forall>i. i \<notin> T \<longrightarrow> f i = i)}"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   541
  using fT
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   542
proof (induct T arbitrary: a c set: finite)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   543
  case empty
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   544
  have th0: "\<And>x y. (\<chi> i. if i \<in> {} then x i else y i) = (\<chi> i. y i)"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   545
    by vector
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   546
  from empty.prems show ?case
62408
86f27b264d3d Conformal_mappings: a big development in complex analysis (+ some lemmas)
paulson <lp15@cam.ac.uk>
parents: 61286
diff changeset
   547
    unfolding th0 by (simp add: eq_id_iff)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   548
next
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   549
  case (insert z T a c)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   550
  let ?F = "\<lambda>T. {f. (\<forall>i \<in> T. f i \<in> S) \<and> (\<forall>i. i \<notin> T \<longrightarrow> f i = i)}"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   551
  let ?h = "\<lambda>(y,g) i. if i = z then y else g i"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   552
  let ?k = "\<lambda>h. (h(z),(\<lambda>i. if i = z then i else h i))"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   553
  let ?s = "\<lambda> k a c f. det((\<chi> i. if i \<in> T then a i (f i) else c i)::'a^'n^'n)"
57129
7edb7550663e introduce more powerful reindexing rules for big operators
hoelzl
parents: 56545
diff changeset
   554
  let ?c = "\<lambda>j i. if i = z then a i j else c i"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   555
  have thif: "\<And>a b c d. (if a \<or> b then c else d) = (if a then c else if b then c else d)"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   556
    by simp
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   557
  have thif2: "\<And>a b c d e. (if a then b else if c then d else e) =
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   558
     (if c then (if a then b else d) else (if a then b else e))"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   559
    by simp
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   560
  from \<open>z \<notin> T\<close> have nz: "\<And>i. i \<in> T \<Longrightarrow> i \<noteq> z"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   561
    by auto
64267
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   562
  have "det (\<chi> i. if i \<in> insert z T then sum (a i) S else c i) =
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   563
    det (\<chi> i. if i = z then sum (a i) S else if i \<in> T then sum (a i) S else c i)"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   564
    unfolding insert_iff thif ..
64267
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   565
  also have "\<dots> = (\<Sum>j\<in>S. det (\<chi> i. if i \<in> T then sum (a i) S else if i = z then a i j else c i))"
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   566
    unfolding det_linear_row_sum[OF fS]
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   567
    by (subst thif2) (simp add: nz cong: if_cong)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   568
  finally have tha:
64267
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   569
    "det (\<chi> i. if i \<in> insert z T then sum (a i) S else c i) =
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   570
     (\<Sum>(j, f)\<in>S \<times> ?F T. det (\<chi> i. if i \<in> T then a i (f i)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   571
                                else if i = z then a i j
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   572
                                else c i))"
64267
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   573
    unfolding insert.hyps unfolding sum.cartesian_product by blast
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   574
  show ?case unfolding tha
60420
884f54e01427 isabelle update_cartouches;
wenzelm
parents: 59867
diff changeset
   575
    using \<open>z \<notin> T\<close>
64267
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   576
    by (intro sum.reindex_bij_witness[where i="?k" and j="?h"])
57129
7edb7550663e introduce more powerful reindexing rules for big operators
hoelzl
parents: 56545
diff changeset
   577
       (auto intro!: cong[OF refl[of det]] simp: vec_eq_iff)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   578
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   579
64267
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   580
lemma det_linear_rows_sum:
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   581
  fixes S :: "'n::finite set"
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   582
  assumes fS: "finite S"
64267
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   583
  shows "det (\<chi> i. sum (a i) S) =
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   584
    sum (\<lambda>f. det (\<chi> i. a i (f i) :: 'a::comm_ring_1 ^ 'n^'n)) {f. \<forall>i. f i \<in> S}"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   585
proof -
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   586
  have th0: "\<And>x y. ((\<chi> i. if i \<in> (UNIV:: 'n set) then x i else y i) :: 'a^'n^'n) = (\<chi> i. x i)"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   587
    by vector
64267
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   588
  from det_linear_rows_sum_lemma[OF fS, of "UNIV :: 'n set" a, unfolded th0, OF finite]
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   589
  show ?thesis by simp
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   590
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   591
64267
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   592
lemma matrix_mul_sum_alt:
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
   593
  fixes A B :: "'a::comm_ring_1^'n^'n"
64267
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   594
  shows "A ** B = (\<chi> i. sum (\<lambda>k. A$i$k *s B $ k) (UNIV :: 'n set))"
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   595
  by (vector matrix_matrix_mult_def sum_component)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   596
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   597
lemma det_rows_mul:
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
   598
  "det((\<chi> i. c i *s a i)::'a::comm_ring_1^'n^'n) =
64272
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
   599
    prod (\<lambda>i. c i) (UNIV:: 'n set) * det((\<chi> i. a i)::'a^'n^'n)"
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
   600
proof (simp add: det_def sum_distrib_left cong add: prod.cong, rule sum.cong)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   601
  let ?U = "UNIV :: 'n set"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   602
  let ?PU = "{p. p permutes ?U}"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   603
  fix p
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   604
  assume pU: "p \<in> ?PU"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   605
  let ?s = "of_int (sign p)"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   606
  from pU have p: "p permutes ?U"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   607
    by blast
64272
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
   608
  have "prod (\<lambda>i. c i * a i $ p i) ?U = prod c ?U * prod (\<lambda>i. a i $ p i) ?U"
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
   609
    unfolding prod.distrib ..
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   610
  then show "?s * (\<Prod>xa\<in>?U. c xa * a xa $ p xa) =
64272
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
   611
    prod c ?U * (?s* (\<Prod>xa\<in>?U. a xa $ p xa))"
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   612
    by (simp add: field_simps)
57418
6ab1c7cb0b8d fact consolidation
haftmann
parents: 57129
diff changeset
   613
qed rule
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   614
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   615
lemma det_mul:
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   616
  fixes A B :: "'a::comm_ring_1^'n^'n"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   617
  shows "det (A ** B) = det A * det B"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   618
proof -
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   619
  let ?U = "UNIV :: 'n set"
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   620
  let ?F = "{f. (\<forall>i \<in> ?U. f i \<in> ?U) \<and> (\<forall>i. i \<notin> ?U \<longrightarrow> f i = i)}"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   621
  let ?PU = "{p. p permutes ?U}"
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   622
  have "p \<in> ?F" if "p permutes ?U" for p
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   623
    by simp
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   624
  then have PUF: "?PU \<subseteq> ?F" by blast
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   625
  {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   626
    fix f
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   627
    assume fPU: "f \<in> ?F - ?PU"
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   628
    have fUU: "f ` ?U \<subseteq> ?U"
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   629
      using fPU by auto
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   630
    from fPU have f: "\<forall>i \<in> ?U. f i \<in> ?U" "\<forall>i. i \<notin> ?U \<longrightarrow> f i = i" "\<not>(\<forall>y. \<exists>!x. f x = y)"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   631
      unfolding permutes_def by auto
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   632
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   633
    let ?A = "(\<chi> i. A$i$f i *s B$f i) :: 'a^'n^'n"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   634
    let ?B = "(\<chi> i. B$f i) :: 'a^'n^'n"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   635
    {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   636
      assume fni: "\<not> inj_on f ?U"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   637
      then obtain i j where ij: "f i = f j" "i \<noteq> j"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   638
        unfolding inj_on_def by blast
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   639
      then have "row i ?B = row j ?B"
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   640
        by (vector row_def)
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   641
      with det_identical_rows[OF ij(2)]
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   642
      have "det (\<chi> i. A$i$f i *s B$f i) = 0"
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   643
        unfolding det_rows_mul by force
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   644
    }
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   645
    moreover
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   646
    {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   647
      assume fi: "inj_on f ?U"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   648
      from f fi have fith: "\<And>i j. f i = f j \<Longrightarrow> i = j"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   649
        unfolding inj_on_def by metis
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   650
      note fs = fi[unfolded surjective_iff_injective_gen[OF finite finite refl fUU, symmetric]]
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   651
      have "\<exists>!x. f x = y" for y
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   652
        using fith fs by blast
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   653
      with f(3) have "det (\<chi> i. A$i$f i *s B$f i) = 0"
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   654
        by blast
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   655
    }
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   656
    ultimately have "det (\<chi> i. A$i$f i *s B$f i) = 0"
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   657
      by blast
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   658
  }
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   659
  then have zth: "\<forall> f\<in> ?F - ?PU. det (\<chi> i. A$i$f i *s B$f i) = 0"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   660
    by simp
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   661
  {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   662
    fix p
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   663
    assume pU: "p \<in> ?PU"
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   664
    from pU have p: "p permutes ?U"
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   665
      by blast
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   666
    let ?s = "\<lambda>p. of_int (sign p)"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   667
    let ?f = "\<lambda>q. ?s p * (\<Prod>i\<in> ?U. A $ i $ p i) * (?s q * (\<Prod>i\<in> ?U. B $ i $ q i))"
64267
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   668
    have "(sum (\<lambda>q. ?s q *
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   669
        (\<Prod>i\<in> ?U. (\<chi> i. A $ i $ p i *s B $ p i :: 'a^'n^'n) $ i $ q i)) ?PU) =
64267
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   670
      (sum (\<lambda>q. ?s p * (\<Prod>i\<in> ?U. A $ i $ p i) * (?s q * (\<Prod>i\<in> ?U. B $ i $ q i))) ?PU)"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   671
      unfolding sum_permutations_compose_right[OF permutes_inv[OF p], of ?f]
64267
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   672
    proof (rule sum.cong)
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   673
      fix q
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   674
      assume qU: "q \<in> ?PU"
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   675
      then have q: "q permutes ?U"
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   676
        by blast
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   677
      from p q have pp: "permutation p" and pq: "permutation q"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   678
        unfolding permutation_permutes by auto
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   679
      have th00: "of_int (sign p) * of_int (sign p) = (1::'a)"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   680
        "\<And>a. of_int (sign p) * (of_int (sign p) * a) = a"
57512
cc97b347b301 reduced name variants for assoc and commute on plus and mult
haftmann
parents: 57418
diff changeset
   681
        unfolding mult.assoc[symmetric]
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   682
        unfolding of_int_mult[symmetric]
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   683
        by (simp_all add: sign_idempotent)
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   684
      have ths: "?s q = ?s p * ?s (q \<circ> inv p)"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   685
        using pp pq permutation_inverse[OF pp] sign_inverse[OF pp]
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   686
        by (simp add: th00 ac_simps sign_idempotent sign_compose)
64272
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
   687
      have th001: "prod (\<lambda>i. B$i$ q (inv p i)) ?U = prod ((\<lambda>i. B$i$ q (inv p i)) \<circ> p) ?U"
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   688
        by (rule prod.permute[OF p])
64272
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
   689
      have thp: "prod (\<lambda>i. (\<chi> i. A$i$p i *s B$p i :: 'a^'n^'n) $i $ q i) ?U =
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
   690
        prod (\<lambda>i. A$i$p i) ?U * prod (\<lambda>i. B$i$ q (inv p i)) ?U"
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
   691
        unfolding th001 prod.distrib[symmetric] o_def permutes_inverses[OF p]
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
   692
        apply (rule prod.cong[OF refl])
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   693
        using permutes_in_image[OF q]
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   694
        apply vector
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   695
        done
64272
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
   696
      show "?s q * prod (\<lambda>i. (((\<chi> i. A$i$p i *s B$p i) :: 'a^'n^'n)$i$q i)) ?U =
f76b6dda2e56 setprod -> prod
nipkow
parents: 64267
diff changeset
   697
        ?s p * (prod (\<lambda>i. A$i$p i) ?U) * (?s (q \<circ> inv p) * prod (\<lambda>i. B$i$(q \<circ> inv p) i) ?U)"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   698
        using ths thp pp pq permutation_inverse[OF pp] sign_inverse[OF pp]
36350
bc7982c54e37 dropped group_simps, ring_simps, field_eq_simps
haftmann
parents: 35542
diff changeset
   699
        by (simp add: sign_nz th00 field_simps sign_idempotent sign_compose)
57418
6ab1c7cb0b8d fact consolidation
haftmann
parents: 57129
diff changeset
   700
    qed rule
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   701
  }
64267
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   702
  then have th2: "sum (\<lambda>f. det (\<chi> i. A$i$f i *s B$f i)) ?PU = det A * det B"
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   703
    unfolding det_def sum_product
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   704
    by (rule sum.cong [OF refl])
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   705
  have "det (A**B) = sum (\<lambda>f.  det (\<chi> i. A $ i $ f i *s B $ f i)) ?F"
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   706
    unfolding matrix_mul_sum_alt det_linear_rows_sum[OF finite]
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   707
    by simp
64267
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   708
  also have "\<dots> = sum (\<lambda>f. det (\<chi> i. A$i$f i *s B$f i)) ?PU"
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   709
    using sum.mono_neutral_cong_left[OF finite PUF zth, symmetric]
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   710
    unfolding det_rows_mul by auto
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   711
  finally show ?thesis unfolding th2 .
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   712
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   713
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   714
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   715
subsection \<open>Relation to invertibility\<close>
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   716
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   717
lemma invertible_det_nz:
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   718
  fixes A::"'a::{field}^'n^'n"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   719
  shows "invertible A \<longleftrightarrow> det A \<noteq> 0"
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   720
proof (cases "invertible A")
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   721
  case True
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   722
  then obtain B :: "'a^'n^'n" where B: "A ** B = mat 1"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   723
    unfolding invertible_right_inverse by blast
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   724
  then have "det (A ** B) = det (mat 1 :: 'a^'n^'n)"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   725
    by simp
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   726
  then show ?thesis
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   727
    by (metis True det_I det_mul mult_zero_left one_neq_zero)
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   728
next
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   729
  case False
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   730
  let ?U = "UNIV :: 'n set"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   731
  have fU: "finite ?U"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   732
    by simp
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   733
  from False obtain c i where c: "sum (\<lambda>i. c i *s row i A) ?U = 0" and iU: "i \<in> ?U" and ci: "c i \<noteq> 0"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   734
    unfolding invertible_right_inverse matrix_right_invertible_independent_rows
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   735
    by blast
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   736
  have thr0: "- row i A = sum (\<lambda>j. (1/ c i) *s (c j *s row j A)) (?U - {i})"
68143
58c9231c2937 tidied some messy proofs
paulson <lp15@cam.ac.uk>
parents: 68138
diff changeset
   737
    unfolding sum_cmul  using c ci
68138
c738f40e88d4 auto-tidying
paulson <lp15@cam.ac.uk>
parents: 68134
diff changeset
   738
    by (auto simp: sum.remove[OF fU iU] eq_vector_fraction_iff add_eq_0_iff)
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   739
  have thr: "- row i A \<in> vec.span {row j A| j. j \<noteq> i}"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   740
    unfolding thr0 by (auto intro: vec.span_base vec.span_scale vec.span_sum)
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   741
  let ?B = "(\<chi> k. if k = i then 0 else row k A) :: 'a^'n^'n"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   742
  have thrb: "row i ?B = 0" using iU by (vector row_def)
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   743
  have "det A = 0"
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   744
    unfolding det_row_span[OF thr, symmetric] right_minus
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   745
    unfolding det_zero_row(2)[OF thrb] ..
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   746
  then show ?thesis
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   747
    by (simp add: False)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   748
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   749
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   750
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   751
lemma det_nz_iff_inj_gen:
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   752
  fixes f :: "'a::field^'n \<Rightarrow> 'a::field^'n"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   753
  assumes "Vector_Spaces.linear ( *s) ( *s) f"
67990
c0ebecf6e3eb some more random results
paulson <lp15@cam.ac.uk>
parents: 67986
diff changeset
   754
  shows "det (matrix f) \<noteq> 0 \<longleftrightarrow> inj f"
c0ebecf6e3eb some more random results
paulson <lp15@cam.ac.uk>
parents: 67986
diff changeset
   755
proof
c0ebecf6e3eb some more random results
paulson <lp15@cam.ac.uk>
parents: 67986
diff changeset
   756
  assume "det (matrix f) \<noteq> 0"
c0ebecf6e3eb some more random results
paulson <lp15@cam.ac.uk>
parents: 67986
diff changeset
   757
  then show "inj f"
c0ebecf6e3eb some more random results
paulson <lp15@cam.ac.uk>
parents: 67986
diff changeset
   758
    using assms invertible_det_nz inj_matrix_vector_mult by force
c0ebecf6e3eb some more random results
paulson <lp15@cam.ac.uk>
parents: 67986
diff changeset
   759
next
c0ebecf6e3eb some more random results
paulson <lp15@cam.ac.uk>
parents: 67986
diff changeset
   760
  assume "inj f"
c0ebecf6e3eb some more random results
paulson <lp15@cam.ac.uk>
parents: 67986
diff changeset
   761
  show "det (matrix f) \<noteq> 0"
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   762
    using vec.linear_injective_left_inverse [OF assms \<open>inj f\<close>]
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   763
    by (metis assms invertible_det_nz invertible_left_inverse matrix_compose_gen matrix_id_mat_1)
67990
c0ebecf6e3eb some more random results
paulson <lp15@cam.ac.uk>
parents: 67986
diff changeset
   764
qed
c0ebecf6e3eb some more random results
paulson <lp15@cam.ac.uk>
parents: 67986
diff changeset
   765
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   766
lemma det_nz_iff_inj:
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   767
  fixes f :: "real^'n \<Rightarrow> real^'n"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   768
  assumes "linear f"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   769
  shows "det (matrix f) \<noteq> 0 \<longleftrightarrow> inj f"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   770
  using det_nz_iff_inj_gen[of f] assms
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   771
  unfolding linear_matrix_vector_mul_eq .
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   772
67990
c0ebecf6e3eb some more random results
paulson <lp15@cam.ac.uk>
parents: 67986
diff changeset
   773
lemma det_eq_0_rank:
c0ebecf6e3eb some more random results
paulson <lp15@cam.ac.uk>
parents: 67986
diff changeset
   774
  fixes A :: "real^'n^'n"
c0ebecf6e3eb some more random results
paulson <lp15@cam.ac.uk>
parents: 67986
diff changeset
   775
  shows "det A = 0 \<longleftrightarrow> rank A < CARD('n)"
c0ebecf6e3eb some more random results
paulson <lp15@cam.ac.uk>
parents: 67986
diff changeset
   776
  using invertible_det_nz [of A]
c0ebecf6e3eb some more random results
paulson <lp15@cam.ac.uk>
parents: 67986
diff changeset
   777
  by (auto simp: matrix_left_invertible_injective invertible_left_inverse less_rank_noninjective)
c0ebecf6e3eb some more random results
paulson <lp15@cam.ac.uk>
parents: 67986
diff changeset
   778
67981
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   779
subsubsection\<open>Invertibility of matrices and corresponding linear functions\<close>
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   780
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   781
lemma matrix_left_invertible_gen:
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   782
  fixes f :: "'a::field^'m \<Rightarrow> 'a::field^'n"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   783
  assumes "Vector_Spaces.linear ( *s) ( *s) f"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   784
  shows "((\<exists>B. B ** matrix f = mat 1) \<longleftrightarrow> (\<exists>g. Vector_Spaces.linear ( *s) ( *s) g \<and> g \<circ> f = id))"
67981
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   785
proof safe
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   786
  fix B
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   787
  assume 1: "B ** matrix f = mat 1"
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   788
  show "\<exists>g. Vector_Spaces.linear ( *s) ( *s) g \<and> g \<circ> f = id"
67981
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   789
  proof (intro exI conjI)
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   790
    show "Vector_Spaces.linear ( *s) ( *s) (\<lambda>y. B *v y)"
68138
c738f40e88d4 auto-tidying
paulson <lp15@cam.ac.uk>
parents: 68134
diff changeset
   791
      by simp
67981
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   792
    show "(( *v) B) \<circ> f = id"
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   793
      unfolding o_def
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   794
      by (metis assms 1 eq_id_iff matrix_vector_mul(1) matrix_vector_mul_assoc matrix_vector_mul_lid)
67981
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   795
  qed
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   796
next
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   797
  fix g
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   798
  assume "Vector_Spaces.linear ( *s) ( *s) g" "g \<circ> f = id"
67981
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   799
  then have "matrix g ** matrix f = mat 1"
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   800
    by (metis assms matrix_compose_gen matrix_id_mat_1)
67981
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   801
  then show "\<exists>B. B ** matrix f = mat 1" ..
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   802
qed
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   803
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   804
lemma matrix_left_invertible:
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   805
  "linear f \<Longrightarrow> ((\<exists>B. B ** matrix f = mat 1) \<longleftrightarrow> (\<exists>g. linear g \<and> g \<circ> f = id))" for f::"real^'m \<Rightarrow> real^'n"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   806
  using matrix_left_invertible_gen[of f]
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   807
  by (auto simp: linear_matrix_vector_mul_eq)
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   808
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   809
lemma matrix_right_invertible_gen:
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   810
  fixes f :: "'a::field^'m \<Rightarrow> 'a^'n"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   811
  assumes "Vector_Spaces.linear ( *s) ( *s) f"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   812
  shows "((\<exists>B. matrix f ** B = mat 1) \<longleftrightarrow> (\<exists>g. Vector_Spaces.linear ( *s) ( *s) g \<and> f \<circ> g = id))"
67981
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   813
proof safe
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   814
  fix B
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   815
  assume 1: "matrix f ** B = mat 1"
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   816
  show "\<exists>g. Vector_Spaces.linear ( *s) ( *s) g \<and> f \<circ> g = id"
67981
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   817
  proof (intro exI conjI)
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   818
    show "Vector_Spaces.linear ( *s) ( *s) (( *v) B)"
68138
c738f40e88d4 auto-tidying
paulson <lp15@cam.ac.uk>
parents: 68134
diff changeset
   819
      by simp
67981
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   820
    show "f \<circ> ( *v) B = id"
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   821
      using 1 assms comp_apply eq_id_iff vec.linear_id matrix_id_mat_1 matrix_vector_mul_assoc matrix_works
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   822
      by (metis (no_types, hide_lams))
67981
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   823
  qed
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   824
next
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   825
  fix g
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   826
  assume "Vector_Spaces.linear ( *s) ( *s) g" and "f \<circ> g = id"
67981
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   827
  then have "matrix f ** matrix g = mat 1"
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   828
    by (metis assms matrix_compose_gen matrix_id_mat_1)
67981
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   829
  then show "\<exists>B. matrix f ** B = mat 1" ..
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   830
qed
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   831
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   832
lemma matrix_right_invertible:
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   833
  "linear f \<Longrightarrow> ((\<exists>B. matrix f ** B = mat 1) \<longleftrightarrow> (\<exists>g. linear g \<and> f \<circ> g = id))" for f::"real^'m \<Rightarrow> real^'n"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   834
  using matrix_right_invertible_gen[of f]
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   835
  by (auto simp: linear_matrix_vector_mul_eq)
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   836
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   837
lemma matrix_invertible_gen:
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   838
  fixes f :: "'a::field^'m \<Rightarrow> 'a::field^'n"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   839
  assumes "Vector_Spaces.linear ( *s) ( *s) f"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   840
  shows  "invertible (matrix f) \<longleftrightarrow> (\<exists>g. Vector_Spaces.linear ( *s) ( *s) g \<and> f \<circ> g = id \<and> g \<circ> f = id)"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   841
    (is "?lhs = ?rhs")
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   842
proof
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   843
  assume ?lhs then show ?rhs
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   844
    by (metis assms invertible_def left_right_inverse_eq matrix_left_invertible_gen matrix_right_invertible_gen)
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   845
next
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   846
  assume ?rhs then show ?lhs
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   847
    by (metis assms invertible_def matrix_compose_gen matrix_id_mat_1)
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   848
qed
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   849
67981
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   850
lemma matrix_invertible:
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   851
  "linear f \<Longrightarrow> invertible (matrix f) \<longleftrightarrow> (\<exists>g. linear g \<and> f \<circ> g = id \<and> g \<circ> f = id)"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   852
  for f::"real^'m \<Rightarrow> real^'n"
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   853
  using matrix_invertible_gen[of f]
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   854
  by (auto simp: linear_matrix_vector_mul_eq)
67981
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   855
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   856
lemma invertible_eq_bij:
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   857
  fixes m :: "'a::field^'m^'n"
67981
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   858
  shows "invertible m \<longleftrightarrow> bij (( *v) m)"
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   859
  using matrix_invertible_gen[OF matrix_vector_mul_linear_gen, of m, simplified matrix_of_matrix_vector_mul]
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   860
  by (metis bij_betw_def left_right_inverse_eq matrix_vector_mul_linear_gen o_bij
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   861
      vec.linear_injective_left_inverse vec.linear_surjective_right_inverse)
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   862
67981
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   863
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   864
subsection \<open>Cramer's rule\<close>
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   865
35150
082fa4bd403d Rename transp to transpose in HOL-Multivariate_Analysis. (by himmelma)
hoelzl
parents: 35028
diff changeset
   866
lemma cramer_lemma_transpose:
68263
e4e536a71e3d generalized Cramer's rule
immler
parents: 68143
diff changeset
   867
  fixes A:: "'a::{field}^'n^'n"
e4e536a71e3d generalized Cramer's rule
immler
parents: 68143
diff changeset
   868
    and x :: "'a::{field}^'n"
64267
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   869
  shows "det ((\<chi> i. if i = k then sum (\<lambda>i. x$i *s row i A) (UNIV::'n set)
68263
e4e536a71e3d generalized Cramer's rule
immler
parents: 68143
diff changeset
   870
                             else row i A)::'a::{field}^'n^'n) = x$k * det A"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   871
  (is "?lhs = ?rhs")
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   872
proof -
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   873
  let ?U = "UNIV :: 'n set"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   874
  let ?Uk = "?U - {k}"
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   875
  have U: "?U = insert k ?Uk"
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   876
    by blast
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   877
  have kUk: "k \<notin> ?Uk"
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   878
    by simp
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   879
  have th00: "\<And>k s. x$k *s row k A + s = (x$k - 1) *s row k A + row k A + s"
36350
bc7982c54e37 dropped group_simps, ring_simps, field_eq_simps
haftmann
parents: 35542
diff changeset
   880
    by (vector field_simps)
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   881
  have th001: "\<And>f k . (\<lambda>x. if x = k then f k else f x) = f"
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   882
    by auto
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   883
  have "(\<chi> i. row i A) = A" by (vector row_def)
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   884
  then have thd1: "det (\<chi> i. row i A) = det A"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   885
    by simp
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   886
  have thd0: "det (\<chi> i. if i = k then row k A + (\<Sum>i \<in> ?Uk. x $ i *s row i A) else row i A) = det A"
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   887
    by (force intro: det_row_span vec.span_sum vec.span_scale vec.span_base)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   888
  show "?lhs = x$k * det A"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   889
    apply (subst U)
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
   890
    unfolding sum.insert[OF finite kUk]
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   891
    apply (subst th00)
57512
cc97b347b301 reduced name variants for assoc and commute on plus and mult
haftmann
parents: 57418
diff changeset
   892
    unfolding add.assoc
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   893
    apply (subst det_row_add)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   894
    unfolding thd0
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   895
    unfolding det_row_mul
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   896
    unfolding th001[of k "\<lambda>i. row i A"]
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   897
    unfolding thd1
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   898
    apply (simp add: field_simps)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   899
    done
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   900
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   901
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   902
lemma cramer_lemma:
68263
e4e536a71e3d generalized Cramer's rule
immler
parents: 68143
diff changeset
   903
  fixes A :: "'a::{field}^'n^'n"
e4e536a71e3d generalized Cramer's rule
immler
parents: 68143
diff changeset
   904
  shows "det((\<chi> i j. if j = k then (A *v x)$i else A$i$j):: 'a::{field}^'n^'n) = x$k * det A"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   905
proof -
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   906
  let ?U = "UNIV :: 'n set"
64267
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
   907
  have *: "\<And>c. sum (\<lambda>i. c i *s row i (transpose A)) ?U = sum (\<lambda>i. c i *s column i A) ?U"
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   908
    by (auto intro: sum.cong)
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   909
  show ?thesis
67673
c8caefb20564 lots of new material, ultimately related to measure theory
paulson <lp15@cam.ac.uk>
parents: 67399
diff changeset
   910
    unfolding matrix_mult_sum
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   911
    unfolding cramer_lemma_transpose[of k x "transpose A", unfolded det_transpose, symmetric]
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   912
    unfolding *[of "\<lambda>i. x$i"]
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   913
    apply (subst det_transpose[symmetric])
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   914
    apply (rule cong[OF refl[of det]])
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   915
    apply (vector transpose_def column_def row_def)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   916
    done
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   917
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   918
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   919
lemma cramer:
68263
e4e536a71e3d generalized Cramer's rule
immler
parents: 68143
diff changeset
   920
  fixes A ::"'a::{field}^'n^'n"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   921
  assumes d0: "det A \<noteq> 0"
36362
06475a1547cb fix lots of looping simp calls and other warnings
huffman
parents: 35542
diff changeset
   922
  shows "A *v x = b \<longleftrightarrow> x = (\<chi> k. det(\<chi> i j. if j=k then b$i else A$i$j) / det A)"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   923
proof -
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   924
  from d0 obtain B where B: "A ** B = mat 1" "B ** A = mat 1"
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   925
    unfolding invertible_det_nz[symmetric] invertible_def
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   926
    by blast
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   927
  have "(A ** B) *v b = b"
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   928
    by (simp add: B)
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   929
  then have "A *v (B *v b) = b"
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   930
    by (simp add: matrix_vector_mul_assoc)
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   931
  then have xe: "\<exists>x. A *v x = b"
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   932
    by blast
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   933
  {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   934
    fix x
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   935
    assume x: "A *v x = b"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   936
    have "x = (\<chi> k. det(\<chi> i j. if j=k then b$i else A$i$j) / det A)"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   937
      unfolding x[symmetric]
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   938
      using d0 by (simp add: vec_eq_iff cramer_lemma field_simps)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   939
  }
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   940
  with xe show ?thesis
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
   941
    by auto
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   942
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   943
67968
a5ad4c015d1c removed dots at the end of (sub)titles
nipkow
parents: 67733
diff changeset
   944
subsection \<open>Orthogonality of a transformation and matrix\<close>
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   945
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   946
definition "orthogonal_transformation f \<longleftrightarrow> linear f \<and> (\<forall>v w. f v \<bullet> f w = v \<bullet> w)"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   947
67981
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   948
definition "orthogonal_matrix (Q::'a::semiring_1^'n^'n) \<longleftrightarrow>
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   949
  transpose Q ** Q = mat 1 \<and> Q ** transpose Q = mat 1"
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   950
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   951
lemma orthogonal_transformation:
67733
346cb74e79f6 generalized lemmas about orthogonal transformation
immler
parents: 67683
diff changeset
   952
  "orthogonal_transformation f \<longleftrightarrow> linear f \<and> (\<forall>v. norm (f v) = norm v)"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   953
  unfolding orthogonal_transformation_def
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   954
  apply auto
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   955
  apply (erule_tac x=v in allE)+
35542
8f97d8caabfd replaced \<bullet> with inner
himmelma
parents: 35150
diff changeset
   956
  apply (simp add: norm_eq_sqrt_inner)
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
   957
  apply (simp add: dot_norm linear_add[symmetric])
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   958
  done
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   959
67683
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
   960
lemma orthogonal_transformation_id [simp]: "orthogonal_transformation (\<lambda>x. x)"
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
   961
  by (simp add: linear_iff orthogonal_transformation_def)
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
   962
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
   963
lemma orthogonal_orthogonal_transformation:
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
   964
    "orthogonal_transformation f \<Longrightarrow> orthogonal (f x) (f y) \<longleftrightarrow> orthogonal x y"
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
   965
  by (simp add: orthogonal_def orthogonal_transformation_def)
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
   966
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
   967
lemma orthogonal_transformation_compose:
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
   968
   "\<lbrakk>orthogonal_transformation f; orthogonal_transformation g\<rbrakk> \<Longrightarrow> orthogonal_transformation(f \<circ> g)"
68138
c738f40e88d4 auto-tidying
paulson <lp15@cam.ac.uk>
parents: 68134
diff changeset
   969
  by (auto simp: orthogonal_transformation_def linear_compose)
67683
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
   970
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
   971
lemma orthogonal_transformation_neg:
67733
346cb74e79f6 generalized lemmas about orthogonal transformation
immler
parents: 67683
diff changeset
   972
  "orthogonal_transformation(\<lambda>x. -(f x)) \<longleftrightarrow> orthogonal_transformation f"
67683
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
   973
  by (auto simp: orthogonal_transformation_def dest: linear_compose_neg)
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
   974
67981
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   975
lemma orthogonal_transformation_scaleR: "orthogonal_transformation f \<Longrightarrow> f (c *\<^sub>R v) = c *\<^sub>R f v"
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   976
  by (simp add: linear_iff orthogonal_transformation_def)
349c639e593c more new theorems on real^1, matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67971
diff changeset
   977
67683
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
   978
lemma orthogonal_transformation_linear:
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
   979
   "orthogonal_transformation f \<Longrightarrow> linear f"
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
   980
  by (simp add: orthogonal_transformation_def)
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
   981
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
   982
lemma orthogonal_transformation_inj:
67733
346cb74e79f6 generalized lemmas about orthogonal transformation
immler
parents: 67683
diff changeset
   983
  "orthogonal_transformation f \<Longrightarrow> inj f"
346cb74e79f6 generalized lemmas about orthogonal transformation
immler
parents: 67683
diff changeset
   984
  unfolding orthogonal_transformation_def inj_on_def
346cb74e79f6 generalized lemmas about orthogonal transformation
immler
parents: 67683
diff changeset
   985
  by (metis vector_eq)
67683
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
   986
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
   987
lemma orthogonal_transformation_surj:
67733
346cb74e79f6 generalized lemmas about orthogonal transformation
immler
parents: 67683
diff changeset
   988
  "orthogonal_transformation f \<Longrightarrow> surj f"
346cb74e79f6 generalized lemmas about orthogonal transformation
immler
parents: 67683
diff changeset
   989
  for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space"
67683
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
   990
  by (simp add: linear_injective_imp_surjective orthogonal_transformation_inj orthogonal_transformation_linear)
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
   991
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
   992
lemma orthogonal_transformation_bij:
67733
346cb74e79f6 generalized lemmas about orthogonal transformation
immler
parents: 67683
diff changeset
   993
  "orthogonal_transformation f \<Longrightarrow> bij f"
346cb74e79f6 generalized lemmas about orthogonal transformation
immler
parents: 67683
diff changeset
   994
  for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space"
67683
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
   995
  by (simp add: bij_def orthogonal_transformation_inj orthogonal_transformation_surj)
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
   996
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
   997
lemma orthogonal_transformation_inv:
67733
346cb74e79f6 generalized lemmas about orthogonal transformation
immler
parents: 67683
diff changeset
   998
  "orthogonal_transformation f \<Longrightarrow> orthogonal_transformation (inv f)"
346cb74e79f6 generalized lemmas about orthogonal transformation
immler
parents: 67683
diff changeset
   999
  for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space"
67683
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1000
  by (metis (no_types, hide_lams) bijection.inv_right bijection_def inj_linear_imp_inv_linear orthogonal_transformation orthogonal_transformation_bij orthogonal_transformation_inj)
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1001
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1002
lemma orthogonal_transformation_norm:
67733
346cb74e79f6 generalized lemmas about orthogonal transformation
immler
parents: 67683
diff changeset
  1003
  "orthogonal_transformation f \<Longrightarrow> norm (f x) = norm x"
67683
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1004
  by (metis orthogonal_transformation)
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1005
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1006
lemma orthogonal_matrix: "orthogonal_matrix (Q:: real ^'n^'n) \<longleftrightarrow> transpose Q ** Q = mat 1"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1007
  by (metis matrix_left_right_inverse orthogonal_matrix_def)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1008
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
  1009
lemma orthogonal_matrix_id: "orthogonal_matrix (mat 1 :: _^'n^'n)"
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
  1010
  by (simp add: orthogonal_matrix_def)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1011
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1012
lemma orthogonal_matrix_mul:
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
  1013
  fixes A :: "real ^'n^'n"
68143
58c9231c2937 tidied some messy proofs
paulson <lp15@cam.ac.uk>
parents: 68138
diff changeset
  1014
  assumes  "orthogonal_matrix A" "orthogonal_matrix B"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1015
  shows "orthogonal_matrix(A ** B)"
68143
58c9231c2937 tidied some messy proofs
paulson <lp15@cam.ac.uk>
parents: 68138
diff changeset
  1016
  using assms
58c9231c2937 tidied some messy proofs
paulson <lp15@cam.ac.uk>
parents: 68138
diff changeset
  1017
  by (simp add: orthogonal_matrix matrix_transpose_mul matrix_left_right_inverse matrix_mul_assoc)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1018
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1019
lemma orthogonal_transformation_matrix:
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
  1020
  fixes f:: "real^'n \<Rightarrow> real^'n"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1021
  shows "orthogonal_transformation f \<longleftrightarrow> linear f \<and> orthogonal_matrix(matrix f)"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1022
  (is "?lhs \<longleftrightarrow> ?rhs")
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1023
proof -
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1024
  let ?mf = "matrix f"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1025
  let ?ot = "orthogonal_transformation f"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1026
  let ?U = "UNIV :: 'n set"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1027
  have fU: "finite ?U" by simp
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1028
  let ?m1 = "mat 1 :: real ^'n^'n"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1029
  {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1030
    assume ot: ?ot
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
  1031
    from ot have lf: "Vector_Spaces.linear ( *s) ( *s) f" and fd: "\<And>v w. f v \<bullet> f w = v \<bullet> w"
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
  1032
      unfolding orthogonal_transformation_def orthogonal_matrix linear_def scalar_mult_eq_scaleR
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
  1033
      by blast+
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1034
    {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1035
      fix i j
35150
082fa4bd403d Rename transp to transpose in HOL-Multivariate_Analysis. (by himmelma)
hoelzl
parents: 35028
diff changeset
  1036
      let ?A = "transpose ?mf ** ?mf"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1037
      have th0: "\<And>b (x::'a::comm_ring_1). (if b then 1 else 0)*x = (if b then x else 0)"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1038
        "\<And>b (x::'a::comm_ring_1). x*(if b then 1 else 0) = (if b then x else 0)"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1039
        by simp_all
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
  1040
      from fd[of "axis i 1" "axis j 1",
63170
eae6549dbea2 tuned proofs, to allow unfold_abs_def;
wenzelm
parents: 63075
diff changeset
  1041
        simplified matrix_works[OF lf, symmetric] dot_matrix_vector_mul]
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1042
      have "?A$i$j = ?m1 $ i $ j"
50526
899c9c4e4a4c Remove the indexed basis from the definition of euclidean spaces and only use the set of Basis vectors
hoelzl
parents: 47108
diff changeset
  1043
        by (simp add: inner_vec_def matrix_matrix_mult_def columnvector_def rowvector_def
64267
b9a1486e79be setsum -> sum
nipkow
parents: 63918
diff changeset
  1044
            th0 sum.delta[OF fU] mat_def axis_def)
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1045
    }
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
  1046
    then have "orthogonal_matrix ?mf"
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
  1047
      unfolding orthogonal_matrix
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1048
      by vector
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
  1049
    with lf have ?rhs
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
  1050
      unfolding linear_def scalar_mult_eq_scaleR
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
  1051
      by blast
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1052
  }
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1053
  moreover
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1054
  {
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
  1055
    assume lf: "Vector_Spaces.linear ( *s) ( *s) f" and om: "orthogonal_matrix ?mf"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1056
    from lf om have ?lhs
68143
58c9231c2937 tidied some messy proofs
paulson <lp15@cam.ac.uk>
parents: 68138
diff changeset
  1057
      unfolding orthogonal_matrix_def norm_eq orthogonal_transformation
58c9231c2937 tidied some messy proofs
paulson <lp15@cam.ac.uk>
parents: 68138
diff changeset
  1058
      apply (simp only: matrix_works[OF lf, symmetric] dot_matrix_vector_mul)
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
  1059
      apply (simp add: dot_matrix_product linear_def scalar_mult_eq_scaleR)
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1060
      done
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1061
  }
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
  1062
  ultimately show ?thesis
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
  1063
    by (auto simp: linear_def scalar_mult_eq_scaleR)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1064
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1065
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1066
lemma det_orthogonal_matrix:
35028
108662d50512 more consistent naming of type classes involving orderings (and lattices) -- c.f. NEWS
haftmann
parents: 34291
diff changeset
  1067
  fixes Q:: "'a::linordered_idom^'n^'n"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1068
  assumes oQ: "orthogonal_matrix Q"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1069
  shows "det Q = 1 \<or> det Q = - 1"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1070
proof -
68143
58c9231c2937 tidied some messy proofs
paulson <lp15@cam.ac.uk>
parents: 68138
diff changeset
  1071
  have "Q ** transpose Q = mat 1"
58c9231c2937 tidied some messy proofs
paulson <lp15@cam.ac.uk>
parents: 68138
diff changeset
  1072
    by (metis oQ orthogonal_matrix_def)
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1073
  then have "det (Q ** transpose Q) = det (mat 1:: 'a^'n^'n)"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1074
    by simp
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1075
  then have "det Q * det Q = 1"
68072
493b818e8e10 added Johannes' generalizations Modules.thy and Vector_Spaces.thy; adapted HOL and HOL-Analysis accordingly
immler
parents: 67990
diff changeset
  1076
    by (simp add: det_mul)
68143
58c9231c2937 tidied some messy proofs
paulson <lp15@cam.ac.uk>
parents: 68138
diff changeset
  1077
  then show ?thesis
58c9231c2937 tidied some messy proofs
paulson <lp15@cam.ac.uk>
parents: 68138
diff changeset
  1078
    by (simp add: square_eq_1_iff)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1079
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1080
67683
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1081
lemma orthogonal_transformation_det [simp]:
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1082
  fixes f :: "real^'n \<Rightarrow> real^'n"
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1083
  shows "orthogonal_transformation f \<Longrightarrow> \<bar>det (matrix f)\<bar> = 1"
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1084
  using det_orthogonal_matrix orthogonal_transformation_matrix by fastforce
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1085
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1086
67968
a5ad4c015d1c removed dots at the end of (sub)titles
nipkow
parents: 67733
diff changeset
  1087
subsection \<open>Linearity of scaling, and hence isometry, that preserves origin\<close>
53854
78afb4c4e683 tuned proofs;
wenzelm
parents: 53600
diff changeset
  1088
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1089
lemma scaling_linear:
67733
346cb74e79f6 generalized lemmas about orthogonal transformation
immler
parents: 67683
diff changeset
  1090
  fixes f :: "'a::real_inner \<Rightarrow> 'a::real_inner"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1091
  assumes f0: "f 0 = 0"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1092
    and fd: "\<forall>x y. dist (f x) (f y) = c * dist x y"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1093
  shows "linear f"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1094
proof -
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1095
  {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1096
    fix v w
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
  1097
    have "norm (f x) = c * norm x" for x
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
  1098
      by (metis dist_0_norm f0 fd)
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
  1099
    then have "f v \<bullet> f w = c\<^sup>2 * (v \<bullet> w)"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1100
      unfolding dot_norm_neg dist_norm[symmetric]
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
  1101
      by (simp add: fd power2_eq_square field_simps)
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
  1102
  }
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
  1103
  then show ?thesis
67733
346cb74e79f6 generalized lemmas about orthogonal transformation
immler
parents: 67683
diff changeset
  1104
    unfolding linear_iff vector_eq[where 'a="'a"] scalar_mult_eq_scaleR
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
  1105
    by (simp add: inner_add field_simps)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1106
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1107
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1108
lemma isometry_linear:
67733
346cb74e79f6 generalized lemmas about orthogonal transformation
immler
parents: 67683
diff changeset
  1109
  "f (0::'a::real_inner) = (0::'a) \<Longrightarrow> \<forall>x y. dist(f x) (f y) = dist x y \<Longrightarrow> linear f"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1110
  by (rule scaling_linear[where c=1]) simp_all
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1111
68134
cfe796bf59da part tidy-up of Determinants
paulson <lp15@cam.ac.uk>
parents: 68074
diff changeset
  1112
text \<open>Hence another formulation of orthogonal transformation\<close>
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1113
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1114
lemma orthogonal_transformation_isometry:
67733
346cb74e79f6 generalized lemmas about orthogonal transformation
immler
parents: 67683
diff changeset
  1115
  "orthogonal_transformation f \<longleftrightarrow> f(0::'a::real_inner) = (0::'a) \<and> (\<forall>x y. dist(f x) (f y) = dist x y)"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1116
  unfolding orthogonal_transformation
67683
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1117
  apply (auto simp: linear_0 isometry_linear)
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1118
   apply (metis (no_types, hide_lams) dist_norm linear_diff)
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1119
  by (metis dist_0_norm)
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1120
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1121
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1122
lemma image_orthogonal_transformation_ball:
67733
346cb74e79f6 generalized lemmas about orthogonal transformation
immler
parents: 67683
diff changeset
  1123
  fixes f :: "'a::euclidean_space \<Rightarrow> 'a"
67683
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1124
  assumes "orthogonal_transformation f"
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1125
  shows "f ` ball x r = ball (f x) r"
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1126
proof (intro equalityI subsetI)
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1127
  fix y assume "y \<in> f ` ball x r"
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1128
  with assms show "y \<in> ball (f x) r"
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1129
    by (auto simp: orthogonal_transformation_isometry)
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1130
next
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1131
  fix y assume y: "y \<in> ball (f x) r"
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1132
  then obtain z where z: "y = f z"
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1133
    using assms orthogonal_transformation_surj by blast
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1134
  with y assms show "y \<in> f ` ball x r"
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1135
    by (auto simp: orthogonal_transformation_isometry)
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1136
qed
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1137
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1138
lemma image_orthogonal_transformation_cball:
67733
346cb74e79f6 generalized lemmas about orthogonal transformation
immler
parents: 67683
diff changeset
  1139
  fixes f :: "'a::euclidean_space \<Rightarrow> 'a"
67683
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1140
  assumes "orthogonal_transformation f"
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1141
  shows "f ` cball x r = cball (f x) r"
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1142
proof (intro equalityI subsetI)
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1143
  fix y assume "y \<in> f ` cball x r"
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1144
  with assms show "y \<in> cball (f x) r"
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1145
    by (auto simp: orthogonal_transformation_isometry)
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1146
next
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1147
  fix y assume y: "y \<in> cball (f x) r"
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1148
  then obtain z where z: "y = f z"
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1149
    using assms orthogonal_transformation_surj by blast
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1150
  with y assms show "y \<in> f ` cball x r"
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1151
    by (auto simp: orthogonal_transformation_isometry)
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1152
qed
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1153
67968
a5ad4c015d1c removed dots at the end of (sub)titles
nipkow
parents: 67733
diff changeset
  1154
subsection\<open> We can find an orthogonal matrix taking any unit vector to any other\<close>
67683
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1155
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1156
lemma orthogonal_matrix_transpose [simp]:
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1157
     "orthogonal_matrix(transpose A) \<longleftrightarrow> orthogonal_matrix A"
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1158
  by (auto simp: orthogonal_matrix_def)
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1159
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1160
lemma orthogonal_matrix_orthonormal_columns:
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1161
  fixes A :: "real^'n^'n"
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1162
  shows "orthogonal_matrix A \<longleftrightarrow>
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1163
          (\<forall>i. norm(column i A) = 1) \<and>
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1164
          (\<forall>i j. i \<noteq> j \<longrightarrow> orthogonal (column i A) (column j A))"
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1165
  by (auto simp: orthogonal_matrix matrix_mult_transpose_dot_column vec_eq_iff mat_def norm_eq_1 orthogonal_def)
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1166
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1167
lemma orthogonal_matrix_orthonormal_rows:
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1168
  fixes A :: "real^'n^'n"
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1169
  shows "orthogonal_matrix A \<longleftrightarrow>
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1170
          (\<forall>i. norm(row i A) = 1) \<and>
817944aeac3f Lots of new material about matrices, etc.
paulson <lp15@cam.ac.uk>
parents: 67673
diff changeset
  1171