src/HOL/Multivariate_Analysis/Determinants.thy
author wenzelm
Wed, 28 Aug 2013 23:41:21 +0200
changeset 53253 220f306f5c4e
parent 53077 a1b3784f8129
child 53600 8fda7ad57466
permissions -rw-r--r--
tuned proofs;
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
41959
b460124855b8 tuned headers;
wenzelm
parents: 40077
diff changeset
     1
(*  Title:      HOL/Multivariate_Analysis/Determinants.thy
b460124855b8 tuned headers;
wenzelm
parents: 40077
diff changeset
     2
    Author:     Amine Chaieb, University of Cambridge
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
     3
*)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
     4
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
     5
header {* Traces, Determinant of square matrices and some properties *}
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
5f974bead436 get Multivariate_Analysis/Determinants.thy compiled and working again
huffman
parents: 41959
diff changeset
    10
  "~~/src/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
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    13
subsection{* First some facts about products*}
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    14
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    15
lemma setprod_insert_eq:
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    16
  "finite A \<Longrightarrow> setprod f (insert a A) = (if a \<in> A then setprod f A else f a * setprod f A)"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    17
  apply clarsimp
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    18
  apply (subgoal_tac "insert a A = A")
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    19
  apply auto
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    20
  done
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    21
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    22
lemma setprod_add_split:
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    23
  assumes mn: "(m::nat) <= n + 1"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    24
  shows "setprod f {m.. n+p} = setprod f {m .. n} * setprod f {n+1..n+p}"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    25
proof -
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    26
  let ?A = "{m .. n+p}"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    27
  let ?B = "{m .. n}"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    28
  let ?C = "{n+1..n+p}"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    29
  from mn have un: "?B \<union> ?C = ?A" by auto
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    30
  from mn have dj: "?B \<inter> ?C = {}" by auto
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    31
  have f: "finite ?B" "finite ?C" by simp_all
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    32
  from setprod_Un_disjoint[OF f dj, of f, unfolded un] show ?thesis .
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    33
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    34
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    35
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    36
lemma setprod_offset: "setprod f {(m::nat) + p .. n + p} = setprod (\<lambda>i. f (i + p)) {m..n}"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    37
  apply (rule setprod_reindex_cong[where f="op + p"])
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    38
  apply (auto simp add: image_iff Bex_def inj_on_def)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    39
  apply presburger
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    40
  apply (rule ext)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    41
  apply (simp add: add_commute)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    42
  done
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    43
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    44
lemma setprod_singleton: "setprod f {x} = f x"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    45
  by simp
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    46
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    47
lemma setprod_singleton_nat_seg: "setprod f {n..n} = f (n::'a::order)"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    48
  by simp
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    49
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    50
lemma setprod_numseg:
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    51
  "setprod f {m..0} = (if m = 0 then f 0 else 1)"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    52
  "setprod f {m .. Suc n} =
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    53
    (if m \<le> Suc n then f (Suc n) * setprod f {m..n} else setprod f {m..n})"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    54
  by (auto simp add: atLeastAtMostSuc_conv)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    55
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    56
lemma setprod_le:
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    57
  assumes fS: "finite S"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    58
    and fg: "\<forall>x\<in>S. f x \<ge> 0 \<and> f x \<le> (g x :: 'a::linordered_idom)"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    59
  shows "setprod f S \<le> setprod g S"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    60
  using fS fg
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    61
  apply (induct S)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    62
  apply simp
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    63
  apply auto
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    64
  apply (rule mult_mono)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    65
  apply (auto intro: setprod_nonneg)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    66
  done
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    67
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    68
  (* FIXME: In Finite_Set there is a useless further assumption *)
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    69
lemma setprod_inversef:
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    70
  "finite A \<Longrightarrow> setprod (inverse \<circ> f) A = (inverse (setprod f A) :: 'a:: field_inverse_zero)"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    71
  apply (erule finite_induct)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    72
  apply (simp)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    73
  apply simp
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    74
  done
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    75
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    76
lemma setprod_le_1:
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    77
  assumes fS: "finite S"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    78
    and f: "\<forall>x\<in>S. f x \<ge> 0 \<and> f x \<le> (1::'a::linordered_idom)"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    79
  shows "setprod f S \<le> 1"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    80
  using setprod_le[OF fS f] unfolding setprod_1 .
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    81
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    82
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    83
subsection {* Trace *}
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    84
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    85
definition trace :: "'a::semiring_1^'n^'n \<Rightarrow> 'a"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
    86
  where "trace A = setsum (\<lambda>i. ((A$i)$i)) (UNIV::'n set)"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    87
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    88
lemma trace_0: "trace(mat 0) = 0"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    89
  by (simp add: trace_def mat_def)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    90
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
    91
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
    92
  by (simp add: trace_def mat_def)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    93
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
    94
lemma trace_add: "trace ((A::'a::comm_semiring_1^'n^'n) + B) = trace A + trace B"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    95
  by (simp add: trace_def setsum_addf)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    96
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
    97
lemma trace_sub: "trace ((A::'a::comm_ring_1^'n^'n) - B) = trace A - trace B"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    98
  by (simp add: trace_def setsum_subtractf)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
    99
52451
e64c1344f21b Generalize trace_mult_sym to square products of non-square matrices.
Stephen W. Nuchia
parents: 51489
diff changeset
   100
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
   101
  apply (simp add: trace_def matrix_matrix_mult_def)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   102
  apply (subst setsum_commute)
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   103
  apply (simp add: mult_commute)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   104
  done
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   105
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   106
(* ------------------------------------------------------------------------- *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   107
(* Definition of determinant.                                                *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   108
(* ------------------------------------------------------------------------- *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   109
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
   110
definition det:: "'a::comm_ring_1^'n^'n \<Rightarrow> 'a" where
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   111
  "det A =
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   112
    setsum (\<lambda>p. of_int (sign p) * setprod (\<lambda>i. A$i$p i) (UNIV :: 'n set))
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   113
      {p. p permutes (UNIV :: 'n set)}"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   114
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   115
(* ------------------------------------------------------------------------- *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   116
(* A few general lemmas we need below.                                       *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   117
(* ------------------------------------------------------------------------- *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   118
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   119
lemma setprod_permute:
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   120
  assumes p: "p permutes S"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   121
  shows "setprod f S = setprod (f o p) S"
51489
f738e6dbd844 fundamental revision of big operators on sets
haftmann
parents: 50526
diff changeset
   122
  using assms by (fact setprod.permute)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   123
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   124
lemma setproduct_permute_nat_interval:
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   125
  "p permutes {m::nat .. n} ==> setprod f {m..n} = setprod (f o p) {m..n}"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   126
  by (blast intro!: setprod_permute)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   127
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   128
(* ------------------------------------------------------------------------- *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   129
(* Basic determinant properties.                                             *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   130
(* ------------------------------------------------------------------------- *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   131
35150
082fa4bd403d Rename transp to transpose in HOL-Multivariate_Analysis. (by himmelma)
hoelzl
parents: 35028
diff changeset
   132
lemma det_transpose: "det (transpose A) = det (A::'a::comm_ring_1 ^'n^'n)"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   133
proof -
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   134
  let ?di = "\<lambda>A i j. A$i$j"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   135
  let ?U = "(UNIV :: 'n set)"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   136
  have fU: "finite ?U" by simp
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   137
  {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   138
    fix p
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   139
    assume p: "p \<in> {p. p permutes ?U}"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   140
    from p have pU: "p permutes ?U" by blast
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   141
    have sth: "sign (inv p) = sign p"
44260
7784fa3232ce Determinants.thy: avoid using mem_def/Collect_def
huffman
parents: 44228
diff changeset
   142
      by (metis sign_inverse fU p mem_Collect_eq permutation_permutes)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   143
    from permutes_inj[OF pU]
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   144
    have pi: "inj_on p ?U" by (blast intro: subset_inj_on)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   145
    from permutes_image[OF pU]
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   146
    have "setprod (\<lambda>i. ?di (transpose A) i (inv p i)) ?U =
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   147
      setprod (\<lambda>i. ?di (transpose A) i (inv p i)) (p ` ?U)" by simp
35150
082fa4bd403d Rename transp to transpose in HOL-Multivariate_Analysis. (by himmelma)
hoelzl
parents: 35028
diff changeset
   148
    also have "\<dots> = setprod ((\<lambda>i. ?di (transpose A) i (inv p i)) o p) ?U"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   149
      unfolding setprod_reindex[OF pi] ..
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   150
    also have "\<dots> = setprod (\<lambda>i. ?di A i (p i)) ?U"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   151
    proof -
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   152
      {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   153
        fix i
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   154
        assume i: "i \<in> ?U"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   155
        from i permutes_inv_o[OF pU] permutes_in_image[OF pU]
35150
082fa4bd403d Rename transp to transpose in HOL-Multivariate_Analysis. (by himmelma)
hoelzl
parents: 35028
diff changeset
   156
        have "((\<lambda>i. ?di (transpose A) i (inv p i)) o p) i = ?di A i (p i)"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   157
          unfolding transpose_def by (simp add: fun_eq_iff)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   158
      }
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   159
      then show "setprod ((\<lambda>i. ?di (transpose A) i (inv p i)) o p) ?U =
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   160
        setprod (\<lambda>i. ?di A i (p i)) ?U" by (auto intro: setprod_cong)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   161
    qed
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   162
    finally have "of_int (sign (inv p)) * (setprod (\<lambda>i. ?di (transpose A) i (inv p i)) ?U) =
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   163
      of_int (sign p) * (setprod (\<lambda>i. ?di A i (p i)) ?U)" using sth by simp
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   164
  }
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   165
  then show ?thesis
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   166
    unfolding det_def
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   167
    apply (subst setsum_permutations_inverse)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   168
    apply (rule setsum_cong2)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   169
    apply blast
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   170
    done
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   171
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   172
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   173
lemma det_lowerdiagonal:
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
   174
  fixes A :: "'a::comm_ring_1^('n::{finite,wellorder})^('n::{finite,wellorder})"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   175
  assumes ld: "\<And>i j. i < j \<Longrightarrow> A$i$j = 0"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   176
  shows "det A = setprod (\<lambda>i. A$i$i) (UNIV:: 'n set)"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   177
proof -
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   178
  let ?U = "UNIV:: 'n set"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   179
  let ?PU = "{p. p permutes ?U}"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   180
  let ?pp = "\<lambda>p. of_int (sign p) * setprod (\<lambda>i. A$i$p i) (UNIV :: 'n set)"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   181
  have fU: "finite ?U" by simp
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   182
  from finite_permutations[OF fU] have fPU: "finite ?PU" .
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   183
  have id0: "{id} \<subseteq> ?PU" by (auto simp add: permutes_id)
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   184
  {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   185
    fix p
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   186
    assume p: "p \<in> ?PU -{id}"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   187
    from p have pU: "p permutes ?U" and pid: "p \<noteq> id"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   188
      by blast+
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   189
    from permutes_natset_le[OF pU] pid obtain i where i: "p i > i"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   190
      by (metis not_le)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   191
    from ld[OF i] have ex:"\<exists>i \<in> ?U. A$i$p i = 0"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   192
      by blast
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   193
    from setprod_zero[OF fU ex] have "?pp p = 0"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   194
      by simp
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   195
  }
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   196
  then have p0: "\<forall>p \<in> ?PU -{id}. ?pp p = 0"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   197
    by blast
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   198
  from setsum_mono_zero_cong_left[OF fPU id0 p0] show ?thesis
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   199
    unfolding det_def by (simp add: sign_id)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   200
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   201
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   202
lemma det_upperdiagonal:
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
   203
  fixes A :: "'a::comm_ring_1^'n::{finite,wellorder}^'n::{finite,wellorder}"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   204
  assumes ld: "\<And>i j. i > j \<Longrightarrow> A$i$j = 0"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   205
  shows "det A = setprod (\<lambda>i. A$i$i) (UNIV:: 'n set)"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   206
proof -
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   207
  let ?U = "UNIV:: 'n set"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   208
  let ?PU = "{p. p permutes ?U}"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   209
  let ?pp = "(\<lambda>p. of_int (sign p) * setprod (\<lambda>i. A$i$p i) (UNIV :: 'n set))"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   210
  have fU: "finite ?U" by simp
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   211
  from finite_permutations[OF fU] have fPU: "finite ?PU" .
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   212
  have id0: "{id} \<subseteq> ?PU" by (auto simp add: permutes_id)
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   213
  {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   214
    fix p
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   215
    assume p: "p \<in> ?PU -{id}"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   216
    from p have pU: "p permutes ?U" and pid: "p \<noteq> id"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   217
      by blast+
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   218
    from permutes_natset_ge[OF pU] pid obtain i where i: "p i < i"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   219
      by (metis not_le)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   220
    from ld[OF i] have ex:"\<exists>i \<in> ?U. A$i$p i = 0" by blast
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   221
    from setprod_zero[OF fU ex] have "?pp p = 0" by simp
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   222
  }
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   223
  then have p0: "\<forall>p \<in> ?PU -{id}. ?pp p = 0"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   224
    by blast
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   225
  from setsum_mono_zero_cong_left[OF fPU id0 p0] show ?thesis
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   226
    unfolding det_def by (simp add: sign_id)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   227
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   228
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   229
lemma det_diagonal:
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
   230
  fixes A :: "'a::comm_ring_1^'n^'n"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   231
  assumes ld: "\<And>i j. i \<noteq> j \<Longrightarrow> A$i$j = 0"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   232
  shows "det A = setprod (\<lambda>i. A$i$i) (UNIV::'n set)"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   233
proof -
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   234
  let ?U = "UNIV:: 'n set"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   235
  let ?PU = "{p. p permutes ?U}"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   236
  let ?pp = "\<lambda>p. of_int (sign p) * setprod (\<lambda>i. A$i$p i) (UNIV :: 'n set)"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   237
  have fU: "finite ?U" by simp
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   238
  from finite_permutations[OF fU] have fPU: "finite ?PU" .
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   239
  have id0: "{id} \<subseteq> ?PU" by (auto simp add: permutes_id)
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   240
  {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   241
    fix p
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   242
    assume p: "p \<in> ?PU - {id}"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   243
    then have "p \<noteq> id" by simp
39302
d7728f65b353 renamed lemmas: ext_iff -> fun_eq_iff, set_ext_iff -> set_eq_iff, set_ext -> set_eqI
nipkow
parents: 39198
diff changeset
   244
    then obtain i where i: "p i \<noteq> i" unfolding fun_eq_iff by auto
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   245
    from ld [OF i [symmetric]] have ex:"\<exists>i \<in> ?U. A$i$p i = 0" by blast
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   246
    from setprod_zero [OF fU ex] have "?pp p = 0" by simp}
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   247
  then have p0: "\<forall>p \<in> ?PU - {id}. ?pp p = 0"  by blast
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   248
  from setsum_mono_zero_cong_left[OF fPU id0 p0] show ?thesis
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   249
    unfolding det_def by (simp add: sign_id)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   250
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   251
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
   252
lemma det_I: "det (mat 1 :: 'a::comm_ring_1^'n^'n) = 1"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   253
proof -
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   254
  let ?A = "mat 1 :: 'a::comm_ring_1^'n^'n"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   255
  let ?U = "UNIV :: 'n set"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   256
  let ?f = "\<lambda>i j. ?A$i$j"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   257
  {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   258
    fix i
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   259
    assume i: "i \<in> ?U"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   260
    have "?f i i = 1" using i by (vector mat_def)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   261
  }
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   262
  then have th: "setprod (\<lambda>i. ?f i i) ?U = setprod (\<lambda>x. 1) ?U"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   263
    by (auto intro: setprod_cong)
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   264
  {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   265
    fix i j
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   266
    assume i: "i \<in> ?U" and j: "j \<in> ?U" and ij: "i \<noteq> j"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   267
    have "?f i j = 0" using i j ij by (vector mat_def)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   268
  }
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   269
  then have "det ?A = setprod (\<lambda>i. ?f i i) ?U" using det_diagonal
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   270
    by blast
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   271
  also have "\<dots> = 1" unfolding th setprod_1 ..
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   272
  finally show ?thesis .
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   273
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   274
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
   275
lemma det_0: "det (mat 0 :: 'a::comm_ring_1^'n^'n) = 0"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   276
  by (simp add: det_def setprod_zero)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   277
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   278
lemma det_permute_rows:
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
   279
  fixes A :: "'a::comm_ring_1^'n^'n"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   280
  assumes p: "p permutes (UNIV :: 'n::finite set)"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   281
  shows "det(\<chi> i. A$p i :: 'a^'n^'n) = of_int (sign p) * det A"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   282
  apply (simp add: det_def setsum_right_distrib mult_assoc[symmetric])
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   283
  apply (subst sum_permutations_compose_right[OF p])
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   284
proof (rule setsum_cong2)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   285
  let ?U = "UNIV :: 'n set"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   286
  let ?PU = "{p. p permutes ?U}"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   287
  fix q
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   288
  assume qPU: "q \<in> ?PU"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   289
  have fU: "finite ?U" by simp
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   290
  from qPU have q: "q permutes ?U"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   291
    by blast
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   292
  from p q have pp: "permutation p" and qp: "permutation q"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   293
    by (metis fU permutation_permutes)+
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   294
  from permutes_inv[OF p] have ip: "inv p permutes ?U" .
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   295
  have "setprod (\<lambda>i. A$p i$ (q o p) i) ?U = setprod ((\<lambda>i. A$p i$(q o p) i) o inv p) ?U"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   296
    by (simp only: setprod_permute[OF ip, symmetric])
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   297
  also have "\<dots> = setprod (\<lambda>i. A $ (p o inv p) i $ (q o (p o inv p)) i) ?U"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   298
    by (simp only: o_def)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   299
  also have "\<dots> = setprod (\<lambda>i. A$i$q i) ?U"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   300
    by (simp only: o_def permutes_inverses[OF p])
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   301
  finally have thp: "setprod (\<lambda>i. A$p i$ (q o p) i) ?U = setprod (\<lambda>i. A$i$q i) ?U"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   302
    by blast
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   303
  show "of_int (sign (q o p)) * setprod (\<lambda>i. A$ p i$ (q o p) i) ?U =
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   304
    of_int (sign p) * of_int (sign q) * setprod (\<lambda>i. A$i$q i) ?U"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   305
    by (simp only: thp sign_compose[OF qp pp] mult_commute of_int_mult)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   306
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   307
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   308
lemma det_permute_columns:
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
   309
  fixes A :: "'a::comm_ring_1^'n^'n"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   310
  assumes p: "p permutes (UNIV :: 'n set)"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   311
  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
   312
proof -
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   313
  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
   314
  let ?At = "transpose A"
082fa4bd403d Rename transp to transpose in HOL-Multivariate_Analysis. (by himmelma)
hoelzl
parents: 35028
diff changeset
   315
  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
   316
    unfolding det_permute_rows[OF p, of ?At] det_transpose ..
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   317
  moreover
35150
082fa4bd403d Rename transp to transpose in HOL-Multivariate_Analysis. (by himmelma)
hoelzl
parents: 35028
diff changeset
   318
  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
   319
    by (simp add: transpose_def vec_eq_iff)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   320
  ultimately show ?thesis by simp
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   321
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   322
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   323
lemma det_identical_rows:
35028
108662d50512 more consistent naming of type classes involving orderings (and lattices) -- c.f. NEWS
haftmann
parents: 34291
diff changeset
   324
  fixes A :: "'a::linordered_idom^'n^'n"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   325
  assumes ij: "i \<noteq> j"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   326
    and r: "row i A = row j A"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   327
  shows "det A = 0"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   328
proof-
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   329
  have tha: "\<And>(a::'a) b. a = b \<Longrightarrow> b = - a \<Longrightarrow> a = 0"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   330
    by simp
47108
2a1953f0d20d merged fork with new numeral representation (see NEWS)
huffman
parents: 44457
diff changeset
   331
  have th1: "of_int (-1) = - 1" by simp
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   332
  let ?p = "Fun.swap i j id"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   333
  let ?A = "\<chi> i. A $ ?p i"
44228
5f974bead436 get Multivariate_Analysis/Determinants.thy compiled and working again
huffman
parents: 41959
diff changeset
   334
  from r have "A = ?A" by (simp add: vec_eq_iff row_def swap_def)
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   335
  then have "det A = det ?A" by simp
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   336
  moreover have "det A = - det ?A"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   337
    by (simp add: det_permute_rows[OF permutes_swap_id] sign_swap_id ij th1)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   338
  ultimately show "det A = 0" by (metis tha)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   339
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   340
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   341
lemma det_identical_columns:
35028
108662d50512 more consistent naming of type classes involving orderings (and lattices) -- c.f. NEWS
haftmann
parents: 34291
diff changeset
   342
  fixes A :: "'a::linordered_idom^'n^'n"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   343
  assumes ij: "i \<noteq> j"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   344
    and r: "column i A = column j A"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   345
  shows "det A = 0"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   346
  apply (subst det_transpose[symmetric])
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   347
  apply (rule det_identical_rows[OF ij])
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   348
  apply (metis row_transpose r)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   349
  done
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   350
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   351
lemma det_zero_row:
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
   352
  fixes A :: "'a::{idom, ring_char_0}^'n^'n"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   353
  assumes r: "row i A = 0"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   354
  shows "det A = 0"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   355
  using r
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   356
  apply (simp add: row_def det_def vec_eq_iff)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   357
  apply (rule setsum_0')
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   358
  apply (auto simp: sign_nz)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   359
  done
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_zero_column:
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
   362
  fixes A :: "'a::{idom,ring_char_0}^'n^'n"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   363
  assumes r: "column i A = 0"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   364
  shows "det A = 0"
35150
082fa4bd403d Rename transp to transpose in HOL-Multivariate_Analysis. (by himmelma)
hoelzl
parents: 35028
diff changeset
   365
  apply (subst det_transpose[symmetric])
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   366
  apply (rule det_zero_row [of i])
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   367
  apply (metis row_transpose r)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   368
  done
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   369
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   370
lemma det_row_add:
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   371
  fixes a b c :: "'n::finite \<Rightarrow> _ ^ 'n"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   372
  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
   373
    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
   374
    det((\<chi> i. if i = k then b i else c i)::'a::comm_ring_1^'n^'n)"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   375
    unfolding det_def vec_lambda_beta setsum_addf[symmetric]
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   376
proof (rule setsum_cong2)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   377
  let ?U = "UNIV :: 'n set"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   378
  let ?pU = "{p. p permutes ?U}"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   379
  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
   380
  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
   381
  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
   382
  fix p
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   383
  assume p: "p \<in> ?pU"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   384
  let ?Uk = "?U - {k}"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   385
  from p have pU: "p permutes ?U" by blast
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   386
  have kU: "?U = insert k ?Uk" by blast
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   387
  {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   388
    fix j
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   389
    assume j: "j \<in> ?Uk"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   390
    from j have "?f j $ p j = ?g j $ p j" and "?f j $ p j= ?h j $ p j"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   391
      by simp_all
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   392
  }
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   393
  then have th1: "setprod (\<lambda>i. ?f i $ p i) ?Uk = setprod (\<lambda>i. ?g i $ p i) ?Uk"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   394
    and th2: "setprod (\<lambda>i. ?f i $ p i) ?Uk = setprod (\<lambda>i. ?h i $ p i) ?Uk"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   395
    apply -
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   396
    apply (rule setprod_cong, simp_all)+
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   397
    done
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   398
  have th3: "finite ?Uk" "k \<notin> ?Uk" by auto
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   399
  have "setprod (\<lambda>i. ?f i $ p i) ?U = setprod (\<lambda>i. ?f i $ p i) (insert k ?Uk)"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   400
    unfolding kU[symmetric] ..
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   401
  also have "\<dots> = ?f k $ p k  * setprod (\<lambda>i. ?f i $ p i) ?Uk"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   402
    apply (rule setprod_insert)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   403
    apply simp
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   404
    apply blast
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   405
    done
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   406
  also have "\<dots> = (a k $ p k * setprod (\<lambda>i. ?f i $ p i) ?Uk) + (b k$ p k * setprod (\<lambda>i. ?f i $ p i) ?Uk)"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   407
    by (simp add: field_simps)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   408
  also have "\<dots> = (a k $ p k * setprod (\<lambda>i. ?g i $ p i) ?Uk) + (b k$ p k * setprod (\<lambda>i. ?h i $ p i) ?Uk)"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   409
    by (metis th1 th2)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   410
  also have "\<dots> = setprod (\<lambda>i. ?g i $ p i) (insert k ?Uk) + setprod (\<lambda>i. ?h i $ p i) (insert k ?Uk)"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   411
    unfolding  setprod_insert[OF th3] by simp
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   412
  finally have "setprod (\<lambda>i. ?f i $ p i) ?U =
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   413
    setprod (\<lambda>i. ?g i $ p i) ?U + setprod (\<lambda>i. ?h i $ p i) ?U" unfolding kU[symmetric] .
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   414
  then show "of_int (sign p) * setprod (\<lambda>i. ?f i $ p i) ?U =
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   415
    of_int (sign p) * setprod (\<lambda>i. ?g i $ p i) ?U + of_int (sign p) * setprod (\<lambda>i. ?h i $ p i) ?U"
36350
bc7982c54e37 dropped group_simps, ring_simps, field_eq_simps
haftmann
parents: 35542
diff changeset
   416
    by (simp add: field_simps)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   417
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   418
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   419
lemma det_row_mul:
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   420
  fixes a b :: "'n::finite \<Rightarrow> _ ^ 'n"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   421
  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
   422
    c * det((\<chi> i. if i = k then a i else b i)::'a::comm_ring_1^'n^'n)"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   423
  unfolding det_def vec_lambda_beta setsum_right_distrib
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   424
proof (rule setsum_cong2)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   425
  let ?U = "UNIV :: 'n set"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   426
  let ?pU = "{p. p permutes ?U}"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   427
  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
   428
  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
   429
  fix p
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   430
  assume p: "p \<in> ?pU"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   431
  let ?Uk = "?U - {k}"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   432
  from p have pU: "p permutes ?U" by blast
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   433
  have kU: "?U = insert k ?Uk" by blast
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   434
  {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   435
    fix j
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   436
    assume j: "j \<in> ?Uk"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   437
    from j have "?f j $ p j = ?g j $ p j" by simp
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   438
  }
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   439
  then have th1: "setprod (\<lambda>i. ?f i $ p i) ?Uk = setprod (\<lambda>i. ?g i $ p i) ?Uk"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   440
    apply -
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   441
    apply (rule setprod_cong)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   442
    apply simp_all
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   443
    done
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   444
  have th3: "finite ?Uk" "k \<notin> ?Uk" by auto
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   445
  have "setprod (\<lambda>i. ?f i $ p i) ?U = setprod (\<lambda>i. ?f i $ p i) (insert k ?Uk)"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   446
    unfolding kU[symmetric] ..
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   447
  also have "\<dots> = ?f k $ p k  * setprod (\<lambda>i. ?f i $ p i) ?Uk"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   448
    apply (rule setprod_insert)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   449
    apply simp
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   450
    apply blast
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   451
    done
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   452
  also have "\<dots> = (c*s a k) $ p k * setprod (\<lambda>i. ?f i $ p i) ?Uk"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   453
    by (simp add: field_simps)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   454
  also have "\<dots> = c* (a k $ p k * setprod (\<lambda>i. ?g i $ p i) ?Uk)"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   455
    unfolding th1 by (simp add: mult_ac)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   456
  also have "\<dots> = c* (setprod (\<lambda>i. ?g i $ p i) (insert k ?Uk))"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   457
    unfolding setprod_insert[OF th3] by simp
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   458
  finally have "setprod (\<lambda>i. ?f i $ p i) ?U = c* (setprod (\<lambda>i. ?g i $ p i) ?U)"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   459
    unfolding kU[symmetric] .
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   460
  then show "of_int (sign p) * setprod (\<lambda>i. ?f i $ p i) ?U =
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   461
    c * (of_int (sign p) * setprod (\<lambda>i. ?g i $ p i) ?U)"
36350
bc7982c54e37 dropped group_simps, ring_simps, field_eq_simps
haftmann
parents: 35542
diff changeset
   462
    by (simp add: field_simps)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   463
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   464
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   465
lemma det_row_0:
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   466
  fixes b :: "'n::finite \<Rightarrow> _ ^ 'n"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   467
  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
   468
  using det_row_mul[of k 0 "\<lambda>i. 1" b]
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   469
  apply simp
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   470
  apply (simp only: vector_smult_lzero)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   471
  done
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   472
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   473
lemma det_row_operation:
35028
108662d50512 more consistent naming of type classes involving orderings (and lattices) -- c.f. NEWS
haftmann
parents: 34291
diff changeset
   474
  fixes A :: "'a::linordered_idom^'n^'n"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   475
  assumes ij: "i \<noteq> j"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   476
  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
   477
proof -
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   478
  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
   479
  have th: "row i ?Z = row j ?Z" by (vector row_def)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   480
  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
   481
    by (vector row_def)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   482
  show ?thesis
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   483
    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
   484
    by simp
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   485
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   486
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   487
lemma det_row_span:
36593
fb69c8cd27bd define linear algebra concepts using scaleR instead of (op *s); generalized many lemmas, though a few theorems that used to work on type int^'n are a bit less general
huffman
parents: 36585
diff changeset
   488
  fixes A :: "real^'n^'n"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   489
  assumes x: "x \<in> span {row j A |j. j \<noteq> i}"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   490
  shows "det (\<chi> k. if k = i then row i A + x else row k A) = det A"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   491
proof -
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   492
  let ?U = "UNIV :: 'n set"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   493
  let ?S = "{row j A |j. j \<noteq> i}"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   494
  let ?d = "\<lambda>x. det (\<chi> k. if k = i then x else row k A)"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   495
  let ?P = "\<lambda>x. ?d (row i A + x) = det A"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   496
  {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   497
    fix k
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   498
    have "(if k = i then row i A + 0 else row k A) = row k A" by simp
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   499
  }
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   500
  then have P0: "?P 0"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   501
    apply -
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   502
    apply (rule cong[of det, OF refl])
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   503
    apply (vector row_def)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   504
    done
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   505
  moreover
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   506
  {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   507
    fix c z y
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   508
    assume zS: "z \<in> ?S" and Py: "?P y"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   509
    from zS obtain j where j: "z = row j A" "i \<noteq> j" by blast
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   510
    let ?w = "row i A + y"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   511
    have th0: "row i A + (c*s z + y) = ?w + c*s z" by vector
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   512
    have thz: "?d z = 0"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   513
      apply (rule det_identical_rows[OF j(2)])
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   514
      using j
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   515
      apply (vector row_def)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   516
      done
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   517
    have "?d (row i A + (c*s z + y)) = ?d (?w + c*s z)"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   518
      unfolding th0 ..
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   519
    then have "?P (c*s z + y)"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   520
      unfolding thz Py det_row_mul[of i] det_row_add[of i]
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   521
      by simp
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   522
  }
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   523
  ultimately show ?thesis
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   524
    apply -
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
   525
    apply (rule span_induct_alt[of ?P ?S, OF P0, folded scalar_mult_eq_scaleR])
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   526
    apply blast
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   527
    apply (rule x)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   528
    done
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   529
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   530
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   531
(* ------------------------------------------------------------------------- *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   532
(* May as well do this, though it's a bit unsatisfactory since it ignores    *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   533
(* exact duplicates by considering the rows/columns as a set.                *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   534
(* ------------------------------------------------------------------------- *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   535
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   536
lemma det_dependent_rows:
36593
fb69c8cd27bd define linear algebra concepts using scaleR instead of (op *s); generalized many lemmas, though a few theorems that used to work on type int^'n are a bit less general
huffman
parents: 36585
diff changeset
   537
  fixes A:: "real^'n^'n"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   538
  assumes d: "dependent (rows A)"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   539
  shows "det A = 0"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   540
proof -
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   541
  let ?U = "UNIV :: 'n set"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   542
  from d obtain i where i: "row i A \<in> span (rows A - {row i A})"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   543
    unfolding dependent_def rows_def by blast
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   544
  {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   545
    fix j k
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   546
    assume jk: "j \<noteq> k" and c: "row j A = row k A"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   547
    from det_identical_rows[OF jk c] have ?thesis .
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   548
  }
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   549
  moreover
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   550
  {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   551
    assume H: "\<And> i j. i \<noteq> j \<Longrightarrow> row i A \<noteq> row j A"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   552
    have th0: "- row i A \<in> span {row j A|j. j \<noteq> i}"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   553
      apply (rule span_neg)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   554
      apply (rule set_rev_mp)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   555
      apply (rule i)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   556
      apply (rule span_mono)
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   557
      using H i
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   558
      apply (auto simp add: rows_def)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   559
      done
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   560
    from det_row_span[OF th0]
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   561
    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
   562
      unfolding right_minus vector_smult_lzero ..
36593
fb69c8cd27bd define linear algebra concepts using scaleR instead of (op *s); generalized many lemmas, though a few theorems that used to work on type int^'n are a bit less general
huffman
parents: 36585
diff changeset
   563
    with det_row_mul[of i "0::real" "\<lambda>i. 1"]
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   564
    have "det A = 0" by simp
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   565
  }
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   566
  ultimately show ?thesis by blast
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   567
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   568
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   569
lemma det_dependent_columns:
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   570
  assumes d: "dependent (columns (A::real^'n^'n))"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   571
  shows "det A = 0"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   572
  by (metis d det_dependent_rows rows_transpose det_transpose)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   573
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   574
(* ------------------------------------------------------------------------- *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   575
(* Multilinearity and the multiplication formula.                            *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   576
(* ------------------------------------------------------------------------- *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   577
44228
5f974bead436 get Multivariate_Analysis/Determinants.thy compiled and working again
huffman
parents: 41959
diff changeset
   578
lemma Cart_lambda_cong: "(\<And>x. f x = g x) \<Longrightarrow> (vec_lambda f::'a^'n) = (vec_lambda g :: 'a^'n)"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   579
  by (rule iffD1[OF vec_lambda_unique]) vector
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   580
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   581
lemma det_linear_row_setsum:
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   582
  assumes fS: "finite S"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   583
  shows "det ((\<chi> i. if i = k then setsum (a i) S else c i)::'a::comm_ring_1^'n^'n) =
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   584
    setsum (\<lambda>j. det ((\<chi> i. if i = k then a  i j else c i)::'a^'n^'n)) S"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   585
proof (induct rule: finite_induct[OF fS])
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   586
  case 1
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   587
  then show ?case
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   588
    apply simp
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   589
    unfolding setsum_empty det_row_0[of k]
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   590
    apply rule
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   591
    done
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   592
next
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   593
  case (2 x F)
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   594
  then show ?case
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   595
    by (simp add: det_row_add cong del: if_weak_cong)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   596
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   597
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   598
lemma finite_bounded_functions:
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   599
  assumes fS: "finite S"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   600
  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
   601
proof (induct k)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   602
  case 0
44457
d366fa5551ef declare euclidean_simps [simp] at the point they are proved;
huffman
parents: 44260
diff changeset
   603
  have th: "{f. \<forall>i. f i = i} = {id}" by auto
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   604
  show ?case by (auto simp add: th)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   605
next
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   606
  case (Suc k)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   607
  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
   608
  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
   609
  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)}"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   610
    apply (auto simp add: image_iff)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   611
    apply (rule_tac x="x (Suc k)" in bexI)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   612
    apply (rule_tac x = "\<lambda>i. if i = Suc k then i else x i" in exI)
44457
d366fa5551ef declare euclidean_simps [simp] at the point they are proved;
huffman
parents: 44260
diff changeset
   613
    apply auto
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   614
    done
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   615
  with finite_imageI[OF finite_cartesian_product[OF fS Suc.hyps(1)], of ?f]
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   616
  show ?case by metis
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   617
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   618
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   619
44457
d366fa5551ef declare euclidean_simps [simp] at the point they are proved;
huffman
parents: 44260
diff changeset
   620
lemma eq_id_iff[simp]: "(\<forall>x. f x = x) = (f = id)" by auto
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   621
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   622
lemma det_linear_rows_setsum_lemma:
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   623
  assumes fS: "finite S" and fT: "finite T"
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
   624
  shows "det((\<chi> i. if i \<in> T then setsum (a i) S else c i):: 'a::comm_ring_1^'n^'n) =
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   625
    setsum (\<lambda>f. det((\<chi> i. if i \<in> T then a i (f i) else c i)::'a^'n^'n))
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   626
      {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
   627
  using fT
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   628
proof (induct T arbitrary: a c set: finite)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   629
  case empty
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   630
  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
   631
    by vector
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   632
  from empty.prems show ?case unfolding th0 by simp
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   633
next
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   634
  case (insert z T a c)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   635
  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
   636
  let ?h = "\<lambda>(y,g) i. if i = z then y else g i"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   637
  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
   638
  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)"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   639
  let ?c = "\<lambda>i. if i = z then a i j else c i"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   640
  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
   641
    by simp
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   642
  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
   643
     (if c then (if a then b else d) else (if a then b else e))"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   644
    by simp
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   645
  from `z \<notin> T` have nz: "\<And>i. i \<in> T \<Longrightarrow> i = z \<longleftrightarrow> False"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   646
    by auto
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   647
  have "det (\<chi> i. if i \<in> insert z T then setsum (a i) S else c i) =
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   648
    det (\<chi> i. if i = z then setsum (a i) S else if i \<in> T then setsum (a i) S else c i)"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   649
    unfolding insert_iff thif ..
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   650
  also have "\<dots> = (\<Sum>j\<in>S. det (\<chi> i. if i \<in> T then setsum (a i) S else if i = z then a i j else c i))"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   651
    unfolding det_linear_row_setsum[OF fS]
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   652
    apply (subst thif2)
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   653
    using nz
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   654
    apply (simp cong del: if_weak_cong cong add: if_cong)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   655
    done
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   656
  finally have tha:
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   657
    "det (\<chi> i. if i \<in> insert z T then setsum (a i) S else c i) =
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   658
     (\<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
   659
                                else if i = z then a i j
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   660
                                else c i))"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   661
    unfolding insert.hyps unfolding setsum_cartesian_product by blast
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   662
  show ?case unfolding tha
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   663
    apply (rule setsum_eq_general_reverses[where h= "?h" and k= "?k"],
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   664
      blast intro: finite_cartesian_product fS finite,
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   665
      blast intro: finite_cartesian_product fS finite)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   666
    using `z \<notin> T`
44457
d366fa5551ef declare euclidean_simps [simp] at the point they are proved;
huffman
parents: 44260
diff changeset
   667
    apply auto
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   668
    apply (rule cong[OF refl[of det]])
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   669
    apply vector
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   670
    done
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   671
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   672
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   673
lemma det_linear_rows_setsum:
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   674
  assumes fS: "finite (S::'n::finite set)"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   675
  shows "det (\<chi> i. setsum (a i) S) =
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   676
    setsum (\<lambda>f. det (\<chi> i. a i (f i) :: 'a::comm_ring_1 ^ 'n^'n)) {f. \<forall>i. f i \<in> S}"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   677
proof -
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   678
  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
   679
    by vector
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   680
  from det_linear_rows_setsum_lemma[OF fS, of "UNIV :: 'n set" a, unfolded th0, OF finite]
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   681
  show ?thesis by simp
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   682
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   683
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   684
lemma matrix_mul_setsum_alt:
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
   685
  fixes A B :: "'a::comm_ring_1^'n^'n"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   686
  shows "A ** B = (\<chi> i. setsum (\<lambda>k. A$i$k *s B $ k) (UNIV :: 'n set))"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   687
  by (vector matrix_matrix_mult_def setsum_component)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   688
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   689
lemma det_rows_mul:
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
   690
  "det((\<chi> i. c i *s a i)::'a::comm_ring_1^'n^'n) =
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   691
    setprod (\<lambda>i. c i) (UNIV:: 'n set) * det((\<chi> i. a i)::'a^'n^'n)"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   692
proof (simp add: det_def setsum_right_distrib cong add: setprod_cong, rule setsum_cong2)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   693
  let ?U = "UNIV :: 'n set"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   694
  let ?PU = "{p. p permutes ?U}"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   695
  fix p
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   696
  assume pU: "p \<in> ?PU"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   697
  let ?s = "of_int (sign p)"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   698
  from pU have p: "p permutes ?U"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   699
    by blast
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   700
  have "setprod (\<lambda>i. c i * a i $ p i) ?U = setprod c ?U * setprod (\<lambda>i. a i $ p i) ?U"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   701
    unfolding setprod_timesf ..
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   702
  then show "?s * (\<Prod>xa\<in>?U. c xa * a xa $ p xa) =
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   703
    setprod c ?U * (?s* (\<Prod>xa\<in>?U. a xa $ p xa))" by (simp add: field_simps)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   704
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   705
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   706
lemma det_mul:
35028
108662d50512 more consistent naming of type classes involving orderings (and lattices) -- c.f. NEWS
haftmann
parents: 34291
diff changeset
   707
  fixes A B :: "'a::linordered_idom^'n^'n"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   708
  shows "det (A ** B) = det A * det B"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   709
proof -
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   710
  let ?U = "UNIV :: 'n set"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   711
  let ?F = "{f. (\<forall>i\<in> ?U. f i \<in> ?U) \<and> (\<forall>i. i \<notin> ?U \<longrightarrow> f i = i)}"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   712
  let ?PU = "{p. p permutes ?U}"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   713
  have fU: "finite ?U" by simp
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   714
  have fF: "finite ?F" by (rule finite)
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   715
  {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   716
    fix p
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   717
    assume p: "p permutes ?U"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   718
    have "p \<in> ?F" unfolding mem_Collect_eq permutes_in_image[OF p]
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   719
      using p[unfolded permutes_def] by simp
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   720
  }
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   721
  then have PUF: "?PU \<subseteq> ?F"  by blast
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   722
  {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   723
    fix f
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   724
    assume fPU: "f \<in> ?F - ?PU"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   725
    have fUU: "f ` ?U \<subseteq> ?U" using fPU by auto
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   726
    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
   727
      unfolding permutes_def by auto
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   728
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   729
    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
   730
    let ?B = "(\<chi> i. B$f i) :: 'a^'n^'n"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   731
    {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   732
      assume fni: "\<not> inj_on f ?U"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   733
      then obtain i j where ij: "f i = f j" "i \<noteq> j"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   734
        unfolding inj_on_def by blast
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   735
      from ij
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   736
      have rth: "row i ?B = row j ?B" by (vector row_def)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   737
      from det_identical_rows[OF ij(2) rth]
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   738
      have "det (\<chi> i. A$i$f i *s B$f i) = 0"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   739
        unfolding det_rows_mul by simp
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   740
    }
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   741
    moreover
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   742
    {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   743
      assume fi: "inj_on f ?U"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   744
      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
   745
        unfolding inj_on_def by metis
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   746
      note fs = fi[unfolded surjective_iff_injective_gen[OF fU fU refl fUU, symmetric]]
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   747
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   748
      {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   749
        fix y
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   750
        from fs f have "\<exists>x. f x = y" by blast
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   751
        then obtain x where x: "f x = y" by blast
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   752
        {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   753
          fix z
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   754
          assume z: "f z = y"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   755
          from fith x z have "z = x" by metis
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   756
        }
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   757
        with x have "\<exists>!x. f x = y" by blast
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   758
      }
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   759
      with f(3) have "det (\<chi> i. A$i$f i *s B$f i) = 0" by blast
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   760
    }
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   761
    ultimately have "det (\<chi> i. A$i$f i *s B$f i) = 0" by blast
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   762
  }
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   763
  hence zth: "\<forall> f\<in> ?F - ?PU. det (\<chi> i. A$i$f i *s B$f i) = 0"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   764
    by simp
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   765
  {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   766
    fix p
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   767
    assume pU: "p \<in> ?PU"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   768
    from pU have p: "p permutes ?U" by blast
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   769
    let ?s = "\<lambda>p. of_int (sign p)"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   770
    let ?f = "\<lambda>q. ?s p * (\<Prod>i\<in> ?U. A $ i $ p i) * (?s q * (\<Prod>i\<in> ?U. B $ i $ q i))"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   771
    have "(setsum (\<lambda>q. ?s q *
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   772
        (\<Prod>i\<in> ?U. (\<chi> i. A $ i $ p i *s B $ p i :: 'a^'n^'n) $ i $ q i)) ?PU) =
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   773
      (setsum (\<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
   774
      unfolding sum_permutations_compose_right[OF permutes_inv[OF p], of ?f]
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   775
    proof(rule setsum_cong2)
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   776
      fix q
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   777
      assume qU: "q \<in> ?PU"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   778
      hence q: "q permutes ?U" by blast
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   779
      from p q have pp: "permutation p" and pq: "permutation q"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   780
        unfolding permutation_permutes by auto
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   781
      have th00: "of_int (sign p) * of_int (sign p) = (1::'a)"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   782
        "\<And>a. of_int (sign p) * (of_int (sign p) * a) = a"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   783
        unfolding mult_assoc[symmetric] unfolding of_int_mult[symmetric]
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   784
        by (simp_all add: sign_idempotent)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   785
      have ths: "?s q = ?s p * ?s (q o inv p)"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   786
        using pp pq permutation_inverse[OF pp] sign_inverse[OF pp]
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   787
        by (simp add:  th00 mult_ac sign_idempotent sign_compose)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   788
      have th001: "setprod (\<lambda>i. B$i$ q (inv p i)) ?U = setprod ((\<lambda>i. B$i$ q (inv p i)) o p) ?U"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   789
        by (rule setprod_permute[OF p])
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   790
      have thp: "setprod (\<lambda>i. (\<chi> i. A$i$p i *s B$p i :: 'a^'n^'n) $i $ q i) ?U =
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   791
        setprod (\<lambda>i. A$i$p i) ?U * setprod (\<lambda>i. B$i$ q (inv p i)) ?U"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   792
        unfolding th001 setprod_timesf[symmetric] o_def permutes_inverses[OF p]
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   793
        apply (rule setprod_cong[OF refl])
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   794
        using permutes_in_image[OF q]
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   795
        apply vector
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   796
        done
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   797
      show "?s q * setprod (\<lambda>i. (((\<chi> i. A$i$p i *s B$p i) :: 'a^'n^'n)$i$q i)) ?U =
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   798
        ?s p * (setprod (\<lambda>i. A$i$p i) ?U) * (?s (q o inv p) * setprod (\<lambda>i. B$i$(q o inv p) i) ?U)"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   799
        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
   800
        by (simp add: sign_nz th00 field_simps sign_idempotent sign_compose)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   801
    qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   802
  }
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   803
  then have th2: "setsum (\<lambda>f. det (\<chi> i. A$i$f i *s B$f i)) ?PU = det A * det B"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   804
    unfolding det_def setsum_product
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   805
    by (rule setsum_cong2)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   806
  have "det (A**B) = setsum (\<lambda>f.  det (\<chi> i. A $ i $ f i *s B $ f i)) ?F"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   807
    unfolding matrix_mul_setsum_alt det_linear_rows_setsum[OF fU] by simp
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   808
  also have "\<dots> = setsum (\<lambda>f. det (\<chi> i. A$i$f i *s B$f i)) ?PU"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   809
    using setsum_mono_zero_cong_left[OF fF PUF zth, symmetric]
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   810
    unfolding det_rows_mul by auto
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   811
  finally show ?thesis unfolding th2 .
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   812
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   813
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   814
(* ------------------------------------------------------------------------- *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   815
(* Relation to invertibility.                                                *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   816
(* ------------------------------------------------------------------------- *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   817
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   818
lemma invertible_left_inverse:
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
   819
  fixes A :: "real^'n^'n"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   820
  shows "invertible A \<longleftrightarrow> (\<exists>(B::real^'n^'n). B** A = mat 1)"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   821
  by (metis invertible_def matrix_left_right_inverse)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   822
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   823
lemma invertible_righ_inverse:
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
   824
  fixes A :: "real^'n^'n"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   825
  shows "invertible A \<longleftrightarrow> (\<exists>(B::real^'n^'n). A** B = mat 1)"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   826
  by (metis invertible_def matrix_left_right_inverse)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   827
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   828
lemma invertible_det_nz:
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
   829
  fixes A::"real ^'n^'n"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   830
  shows "invertible A \<longleftrightarrow> det A \<noteq> 0"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   831
proof -
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   832
  {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   833
    assume "invertible A"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   834
    then obtain B :: "real ^'n^'n" where B: "A ** B = mat 1"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   835
      unfolding invertible_righ_inverse by blast
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   836
    hence "det (A ** B) = det (mat 1 :: real ^'n^'n)" by simp
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   837
    hence "det A \<noteq> 0" by (simp add: det_mul det_I) algebra
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   838
  }
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   839
  moreover
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   840
  {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   841
    assume H: "\<not> invertible A"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   842
    let ?U = "UNIV :: 'n set"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   843
    have fU: "finite ?U" by simp
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   844
    from H obtain c i where c: "setsum (\<lambda>i. c i *s row i A) ?U = 0"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   845
      and iU: "i \<in> ?U" and ci: "c i \<noteq> 0"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   846
      unfolding invertible_righ_inverse
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   847
      unfolding matrix_right_invertible_independent_rows by blast
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   848
    have *: "\<And>(a::real^'n) b. a + b = 0 \<Longrightarrow> -a = b"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   849
      apply (drule_tac f="op + (- a)" in cong[OF refl])
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   850
      apply (simp only: ab_left_minus add_assoc[symmetric])
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   851
      apply simp
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   852
      done
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   853
    from c ci
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   854
    have thr0: "- row i A = setsum (\<lambda>j. (1/ c i) *s (c j *s row j A)) (?U - {i})"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   855
      unfolding setsum_diff1'[OF fU iU] setsum_cmul
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   856
      apply -
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   857
      apply (rule vector_mul_lcancel_imp[OF ci])
44457
d366fa5551ef declare euclidean_simps [simp] at the point they are proved;
huffman
parents: 44260
diff changeset
   858
      apply (auto simp add: field_simps)
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   859
      unfolding * ..
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   860
    have thr: "- row i A \<in> span {row j A| j. j \<noteq> i}"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   861
      unfolding thr0
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   862
      apply (rule span_setsum)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   863
      apply simp
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   864
      apply (rule ballI)
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
   865
      apply (rule span_mul [where 'a="real^'n", folded scalar_mult_eq_scaleR])+
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   866
      apply (rule span_superset)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   867
      apply auto
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   868
      done
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   869
    let ?B = "(\<chi> k. if k = i then 0 else row k A) :: real ^'n^'n"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   870
    have thrb: "row i ?B = 0" using iU by (vector row_def)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   871
    have "det A = 0"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   872
      unfolding det_row_span[OF thr, symmetric] right_minus
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   873
      unfolding det_zero_row[OF thrb] ..
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   874
  }
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   875
  ultimately show ?thesis by blast
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   876
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   877
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   878
(* ------------------------------------------------------------------------- *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   879
(* Cramer's rule.                                                            *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   880
(* ------------------------------------------------------------------------- *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   881
35150
082fa4bd403d Rename transp to transpose in HOL-Multivariate_Analysis. (by himmelma)
hoelzl
parents: 35028
diff changeset
   882
lemma cramer_lemma_transpose:
36593
fb69c8cd27bd define linear algebra concepts using scaleR instead of (op *s); generalized many lemmas, though a few theorems that used to work on type int^'n are a bit less general
huffman
parents: 36585
diff changeset
   883
  fixes A:: "real^'n^'n" and x :: "real^'n"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   884
  shows "det ((\<chi> i. if i = k then setsum (\<lambda>i. x$i *s row i A) (UNIV::'n set)
36593
fb69c8cd27bd define linear algebra concepts using scaleR instead of (op *s); generalized many lemmas, though a few theorems that used to work on type int^'n are a bit less general
huffman
parents: 36585
diff changeset
   885
                           else row i A)::real^'n^'n) = x$k * det A"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   886
  (is "?lhs = ?rhs")
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   887
proof -
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   888
  let ?U = "UNIV :: 'n set"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   889
  let ?Uk = "?U - {k}"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   890
  have U: "?U = insert k ?Uk" by blast
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   891
  have fUk: "finite ?Uk" by simp
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   892
  have kUk: "k \<notin> ?Uk" by simp
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   893
  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
   894
    by (vector field_simps)
44457
d366fa5551ef declare euclidean_simps [simp] at the point they are proved;
huffman
parents: 44260
diff changeset
   895
  have th001: "\<And>f k . (\<lambda>x. if x = k then f k else f x) = f" by auto
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   896
  have "(\<chi> i. row i A) = A" by (vector row_def)
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   897
  then have thd1: "det (\<chi> i. row i A) = det A"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   898
    by simp
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   899
  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"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   900
    apply (rule det_row_span)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   901
    apply (rule span_setsum[OF fUk])
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   902
    apply (rule ballI)
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
   903
    apply (rule span_mul [where 'a="real^'n", folded scalar_mult_eq_scaleR])+
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   904
    apply (rule span_superset)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   905
    apply auto
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   906
    done
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   907
  show "?lhs = x$k * det A"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   908
    apply (subst U)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   909
    unfolding setsum_insert[OF fUk kUk]
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   910
    apply (subst th00)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   911
    unfolding add_assoc
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   912
    apply (subst det_row_add)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   913
    unfolding thd0
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   914
    unfolding det_row_mul
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   915
    unfolding th001[of k "\<lambda>i. row i A"]
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   916
    unfolding thd1
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   917
    apply (simp add: field_simps)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   918
    done
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   919
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   920
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   921
lemma cramer_lemma:
36593
fb69c8cd27bd define linear algebra concepts using scaleR instead of (op *s); generalized many lemmas, though a few theorems that used to work on type int^'n are a bit less general
huffman
parents: 36585
diff changeset
   922
  fixes A :: "real^'n^'n"
fb69c8cd27bd define linear algebra concepts using scaleR instead of (op *s); generalized many lemmas, though a few theorems that used to work on type int^'n are a bit less general
huffman
parents: 36585
diff changeset
   923
  shows "det((\<chi> i j. if j = k then (A *v x)$i else A$i$j):: real^'n^'n) = x$k * det A"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   924
proof -
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   925
  let ?U = "UNIV :: 'n set"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   926
  have *: "\<And>c. setsum (\<lambda>i. c i *s row i (transpose A)) ?U = setsum (\<lambda>i. c i *s column i A) ?U"
35150
082fa4bd403d Rename transp to transpose in HOL-Multivariate_Analysis. (by himmelma)
hoelzl
parents: 35028
diff changeset
   927
    by (auto simp add: row_transpose intro: setsum_cong2)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   928
  show ?thesis  unfolding matrix_mult_vsum
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   929
    unfolding cramer_lemma_transpose[of k x "transpose A", unfolded det_transpose, symmetric]
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   930
    unfolding *[of "\<lambda>i. x$i"]
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   931
    apply (subst det_transpose[symmetric])
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   932
    apply (rule cong[OF refl[of det]])
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   933
    apply (vector transpose_def column_def row_def)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   934
    done
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   935
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   936
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   937
lemma cramer:
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
   938
  fixes A ::"real^'n^'n"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   939
  assumes d0: "det A \<noteq> 0"
36362
06475a1547cb fix lots of looping simp calls and other warnings
huffman
parents: 35542
diff changeset
   940
  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
   941
proof -
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   942
  from d0 obtain B where B: "A ** B = mat 1" "B ** A = mat 1"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   943
    unfolding invertible_det_nz[symmetric] invertible_def by blast
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   944
  have "(A ** B) *v b = b" by (simp add: B matrix_vector_mul_lid)
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   945
  then have "A *v (B *v b) = b" by (simp add: matrix_vector_mul_assoc)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   946
  then have xe: "\<exists>x. A*v x = b" by blast
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   947
  {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   948
    fix x
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   949
    assume x: "A *v x = b"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   950
    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
   951
      unfolding x[symmetric]
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   952
      using d0 by (simp add: vec_eq_iff cramer_lemma field_simps)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   953
  }
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   954
  with xe show ?thesis by auto
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   955
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   956
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   957
(* ------------------------------------------------------------------------- *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   958
(* Orthogonality of a transformation and matrix.                             *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   959
(* ------------------------------------------------------------------------- *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   960
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   961
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
   962
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   963
lemma orthogonal_transformation:
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   964
  "orthogonal_transformation f \<longleftrightarrow> linear f \<and> (\<forall>(v::real ^_). norm (f v) = norm v)"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   965
  unfolding orthogonal_transformation_def
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   966
  apply auto
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   967
  apply (erule_tac x=v in allE)+
35542
8f97d8caabfd replaced \<bullet> with inner
himmelma
parents: 35150
diff changeset
   968
  apply (simp add: norm_eq_sqrt_inner)
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   969
  apply (simp add: dot_norm  linear_add[symmetric])
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   970
  done
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   971
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   972
definition "orthogonal_matrix (Q::'a::semiring_1^'n^'n) \<longleftrightarrow>
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   973
  transpose Q ** Q = mat 1 \<and> Q ** transpose Q = mat 1"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   974
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   975
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
   976
  by (metis matrix_left_right_inverse orthogonal_matrix_def)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   977
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
   978
lemma orthogonal_matrix_id: "orthogonal_matrix (mat 1 :: _^'n^'n)"
35150
082fa4bd403d Rename transp to transpose in HOL-Multivariate_Analysis. (by himmelma)
hoelzl
parents: 35028
diff changeset
   979
  by (simp add: orthogonal_matrix_def transpose_mat matrix_mul_lid)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   980
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   981
lemma orthogonal_matrix_mul:
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
   982
  fixes A :: "real ^'n^'n"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   983
  assumes oA : "orthogonal_matrix A"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   984
    and oB: "orthogonal_matrix B"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   985
  shows "orthogonal_matrix(A ** B)"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   986
  using oA oB
35150
082fa4bd403d Rename transp to transpose in HOL-Multivariate_Analysis. (by himmelma)
hoelzl
parents: 35028
diff changeset
   987
  unfolding orthogonal_matrix matrix_transpose_mul
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   988
  apply (subst matrix_mul_assoc)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   989
  apply (subst matrix_mul_assoc[symmetric])
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   990
  apply (simp add: matrix_mul_rid)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   991
  done
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   992
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   993
lemma orthogonal_transformation_matrix:
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
   994
  fixes f:: "real^'n \<Rightarrow> real^'n"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   995
  shows "orthogonal_transformation f \<longleftrightarrow> linear f \<and> orthogonal_matrix(matrix f)"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   996
  (is "?lhs \<longleftrightarrow> ?rhs")
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
   997
proof -
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   998
  let ?mf = "matrix f"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
   999
  let ?ot = "orthogonal_transformation f"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1000
  let ?U = "UNIV :: 'n set"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1001
  have fU: "finite ?U" by simp
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1002
  let ?m1 = "mat 1 :: real ^'n^'n"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1003
  {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1004
    assume ot: ?ot
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1005
    from ot have lf: "linear f" and fd: "\<forall>v w. f v \<bullet> f w = v \<bullet> w"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1006
      unfolding  orthogonal_transformation_def orthogonal_matrix by blast+
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1007
    {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1008
      fix i j
35150
082fa4bd403d Rename transp to transpose in HOL-Multivariate_Analysis. (by himmelma)
hoelzl
parents: 35028
diff changeset
  1009
      let ?A = "transpose ?mf ** ?mf"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1010
      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
  1011
        "\<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
  1012
        by simp_all
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
  1013
      from fd[rule_format, of "axis i 1" "axis j 1", unfolded matrix_works[OF lf, symmetric] dot_matrix_vector_mul]
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1014
      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
  1015
        by (simp add: inner_vec_def matrix_matrix_mult_def columnvector_def rowvector_def
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1016
            th0 setsum_delta[OF fU] mat_def axis_def)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1017
    }
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1018
    then have "orthogonal_matrix ?mf" unfolding orthogonal_matrix
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1019
      by vector
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1020
    with lf have ?rhs by blast
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1021
  }
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1022
  moreover
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1023
  {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1024
    assume lf: "linear f" and om: "orthogonal_matrix ?mf"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1025
    from lf om have ?lhs
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1026
      unfolding orthogonal_matrix_def norm_eq orthogonal_transformation
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1027
      unfolding matrix_works[OF lf, symmetric]
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1028
      apply (subst dot_matrix_vector_mul)
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1029
      apply (simp add: dot_matrix_product matrix_mul_lid)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1030
      done
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1031
  }
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1032
  ultimately show ?thesis by blast
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1033
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1034
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1035
lemma det_orthogonal_matrix:
35028
108662d50512 more consistent naming of type classes involving orderings (and lattices) -- c.f. NEWS
haftmann
parents: 34291
diff changeset
  1036
  fixes Q:: "'a::linordered_idom^'n^'n"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1037
  assumes oQ: "orthogonal_matrix Q"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1038
  shows "det Q = 1 \<or> det Q = - 1"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1039
proof -
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1040
  have th: "\<And>x::'a. x = 1 \<or> x = - 1 \<longleftrightarrow> x*x = 1" (is "\<And>x::'a. ?ths x")
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1041
  proof -
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1042
    fix x:: 'a
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1043
    have th0: "x*x - 1 = (x - 1)*(x + 1)"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1044
      by (simp add: field_simps)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1045
    have th1: "\<And>(x::'a) y. x = - y \<longleftrightarrow> x + y = 0"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1046
      apply (subst eq_iff_diff_eq_0)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1047
      apply simp
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1048
      done
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1049
    have "x * x = 1 \<longleftrightarrow> x*x - 1 = 0" by simp
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1050
    also have "\<dots> \<longleftrightarrow> x = 1 \<or> x = - 1" unfolding th0 th1 by simp
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1051
    finally show "?ths x" ..
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1052
  qed
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1053
  from oQ have "Q ** transpose Q = mat 1"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1054
    by (metis orthogonal_matrix_def)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1055
  then have "det (Q ** transpose Q) = det (mat 1:: 'a^'n^'n)"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1056
    by simp
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1057
  then have "det Q * det Q = 1"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1058
    by (simp add: det_mul det_I det_transpose)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1059
  then show ?thesis unfolding th .
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1060
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1061
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1062
(* ------------------------------------------------------------------------- *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1063
(* Linearity of scaling, and hence isometry, that preserves origin.          *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1064
(* ------------------------------------------------------------------------- *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1065
lemma scaling_linear:
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
  1066
  fixes f :: "real ^'n \<Rightarrow> real ^'n"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1067
  assumes f0: "f 0 = 0"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1068
    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
  1069
  shows "linear f"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1070
proof -
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1071
  {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1072
    fix v w
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1073
    {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1074
      fix x
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1075
      note fd[rule_format, of x 0, unfolded dist_norm f0 diff_0_right]
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1076
    }
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1077
    note th0 = this
53077
a1b3784f8129 more symbols;
wenzelm
parents: 52451
diff changeset
  1078
    have "f v \<bullet> f w = c\<^sup>2 * (v \<bullet> w)"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1079
      unfolding dot_norm_neg dist_norm[symmetric]
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1080
      unfolding th0 fd[rule_format] by (simp add: power2_eq_square field_simps)}
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1081
  note fc = this
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
  1082
  show ?thesis
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1083
    unfolding linear_def vector_eq[where 'a="real^'n"] scalar_mult_eq_scaleR
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
  1084
    by (simp add: inner_add fc field_simps)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1085
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1086
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1087
lemma isometry_linear:
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1088
  "f (0:: real^'n) = (0:: real^'n) \<Longrightarrow> \<forall>x y. dist(f x) (f y) = dist x y \<Longrightarrow> linear f"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1089
  by (rule scaling_linear[where c=1]) simp_all
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1090
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1091
(* ------------------------------------------------------------------------- *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1092
(* Hence another formulation of orthogonal transformation.                   *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1093
(* ------------------------------------------------------------------------- *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1094
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1095
lemma orthogonal_transformation_isometry:
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
  1096
  "orthogonal_transformation f \<longleftrightarrow> f(0::real^'n) = (0::real^'n) \<and> (\<forall>x y. dist(f x) (f y) = dist x y)"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1097
  unfolding orthogonal_transformation
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1098
  apply (rule iffI)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1099
  apply clarify
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1100
  apply (clarsimp simp add: linear_0 linear_sub[symmetric] dist_norm)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1101
  apply (rule conjI)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1102
  apply (rule isometry_linear)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1103
  apply simp
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1104
  apply simp
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1105
  apply clarify
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1106
  apply (erule_tac x=v in allE)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1107
  apply (erule_tac x=0 in allE)
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1108
  apply (simp add: dist_norm)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1109
  done
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1110
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1111
(* ------------------------------------------------------------------------- *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1112
(* Can extend an isometry from unit sphere.                                  *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1113
(* ------------------------------------------------------------------------- *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1114
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1115
lemma isometry_sphere_extend:
34291
4e896680897e finite annotation on cartesian product is now implicit.
hoelzl
parents: 34289
diff changeset
  1116
  fixes f:: "real ^'n \<Rightarrow> real ^'n"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1117
  assumes f1: "\<forall>x. norm x = 1 \<longrightarrow> norm (f x) = 1"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1118
    and fd1: "\<forall> x y. norm x = 1 \<longrightarrow> norm y = 1 \<longrightarrow> dist (f x) (f y) = dist x y"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1119
  shows "\<exists>g. orthogonal_transformation g \<and> (\<forall>x. norm x = 1 \<longrightarrow> g x = f x)"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1120
proof -
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1121
  {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1122
    fix x y x' y' x0 y0 x0' y0' :: "real ^'n"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1123
    assume H:
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1124
      "x = norm x *\<^sub>R x0"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1125
      "y = norm y *\<^sub>R y0"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1126
      "x' = norm x *\<^sub>R x0'" "y' = norm y *\<^sub>R y0'"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1127
      "norm x0 = 1" "norm x0' = 1" "norm y0 = 1" "norm y0' = 1"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1128
      "norm(x0' - y0') = norm(x0 - y0)"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1129
    hence *: "x0 \<bullet> y0 = x0' \<bullet> y0' + y0' \<bullet> x0' - y0 \<bullet> x0 "
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1130
      by (simp add: norm_eq norm_eq_1 inner_add inner_diff)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1131
    have "norm(x' - y') = norm(x - y)"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1132
      apply (subst H(1))
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1133
      apply (subst H(2))
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1134
      apply (subst H(3))
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1135
      apply (subst H(4))
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1136
      using H(5-9)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1137
      apply (simp add: norm_eq norm_eq_1)
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
  1138
      apply (simp add: inner_diff scalar_mult_eq_scaleR) unfolding *
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1139
      apply (simp add: field_simps)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1140
      done
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1141
  }
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1142
  note th0 = this
44228
5f974bead436 get Multivariate_Analysis/Determinants.thy compiled and working again
huffman
parents: 41959
diff changeset
  1143
  let ?g = "\<lambda>x. if x = 0 then 0 else norm x *\<^sub>R f (inverse (norm x) *\<^sub>R x)"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1144
  {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1145
    fix x:: "real ^'n"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1146
    assume nx: "norm x = 1"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1147
    have "?g x = f x" using nx by auto
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1148
  }
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1149
  then have thfg: "\<forall>x. norm x = 1 \<longrightarrow> ?g x = f x"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1150
    by blast
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1151
  have g0: "?g 0 = 0" by simp
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1152
  {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1153
    fix x y :: "real ^'n"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1154
    {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1155
      assume "x = 0" "y = 0"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1156
      then have "dist (?g x) (?g y) = dist x y" by simp
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1157
    }
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1158
    moreover
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1159
    {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1160
      assume "x = 0" "y \<noteq> 0"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1161
      then have "dist (?g x) (?g y) = dist x y"
36362
06475a1547cb fix lots of looping simp calls and other warnings
huffman
parents: 35542
diff changeset
  1162
        apply (simp add: dist_norm)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1163
        apply (rule f1[rule_format])
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1164
        apply (simp add: field_simps)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1165
        done
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1166
    }
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1167
    moreover
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1168
    {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1169
      assume "x \<noteq> 0" "y = 0"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1170
      then have "dist (?g x) (?g y) = dist x y"
36362
06475a1547cb fix lots of looping simp calls and other warnings
huffman
parents: 35542
diff changeset
  1171
        apply (simp add: dist_norm)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1172
        apply (rule f1[rule_format])
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1173
        apply (simp add: field_simps)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1174
        done
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1175
    }
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1176
    moreover
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1177
    {
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1178
      assume z: "x \<noteq> 0" "y \<noteq> 0"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1179
      have th00:
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1180
        "x = norm x *\<^sub>R (inverse (norm x) *\<^sub>R x)"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1181
        "y = norm y *\<^sub>R (inverse (norm y) *\<^sub>R y)"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1182
        "norm x *\<^sub>R f ((inverse (norm x) *\<^sub>R x)) = norm x *\<^sub>R f (inverse (norm x) *\<^sub>R x)"
44228
5f974bead436 get Multivariate_Analysis/Determinants.thy compiled and working again
huffman
parents: 41959
diff changeset
  1183
        "norm y *\<^sub>R f (inverse (norm y) *\<^sub>R y) = norm y *\<^sub>R f (inverse (norm y) *\<^sub>R y)"
5f974bead436 get Multivariate_Analysis/Determinants.thy compiled and working again
huffman
parents: 41959
diff changeset
  1184
        "norm (inverse (norm x) *\<^sub>R x) = 1"
5f974bead436 get Multivariate_Analysis/Determinants.thy compiled and working again
huffman
parents: 41959
diff changeset
  1185
        "norm (f (inverse (norm x) *\<^sub>R x)) = 1"
5f974bead436 get Multivariate_Analysis/Determinants.thy compiled and working again
huffman
parents: 41959
diff changeset
  1186
        "norm (inverse (norm y) *\<^sub>R y) = 1"
5f974bead436 get Multivariate_Analysis/Determinants.thy compiled and working again
huffman
parents: 41959
diff changeset
  1187
        "norm (f (inverse (norm y) *\<^sub>R y)) = 1"
5f974bead436 get Multivariate_Analysis/Determinants.thy compiled and working again
huffman
parents: 41959
diff changeset
  1188
        "norm (f (inverse (norm x) *\<^sub>R x) - f (inverse (norm y) *\<^sub>R y)) =
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1189
          norm (inverse (norm x) *\<^sub>R x - inverse (norm y) *\<^sub>R y)"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1190
        using z
44457
d366fa5551ef declare euclidean_simps [simp] at the point they are proved;
huffman
parents: 44260
diff changeset
  1191
        by (auto simp add: field_simps intro: f1[rule_format] fd1[rule_format, unfolded dist_norm])
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1192
      from z th0[OF th00] have "dist (?g x) (?g y) = dist x y"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1193
        by (simp add: dist_norm)
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1194
    }
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1195
    ultimately have "dist (?g x) (?g y) = dist x y" by blast
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1196
  }
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1197
  note thd = this
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1198
    show ?thesis
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1199
    apply (rule exI[where x= ?g])
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1200
    unfolding orthogonal_transformation_isometry
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1201
    using g0 thfg thd
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1202
    apply metis
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1203
    done
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1204
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1205
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1206
(* ------------------------------------------------------------------------- *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1207
(* Rotation, reflection, rotoinversion.                                      *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1208
(* ------------------------------------------------------------------------- *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1209
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1210
definition "rotation_matrix Q \<longleftrightarrow> orthogonal_matrix Q \<and> det Q = 1"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1211
definition "rotoinversion_matrix Q \<longleftrightarrow> orthogonal_matrix Q \<and> det Q = - 1"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1212
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1213
lemma orthogonal_rotation_or_rotoinversion:
35028
108662d50512 more consistent naming of type classes involving orderings (and lattices) -- c.f. NEWS
haftmann
parents: 34291
diff changeset
  1214
  fixes Q :: "'a::linordered_idom^'n^'n"
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1215
  shows " orthogonal_matrix Q \<longleftrightarrow> rotation_matrix Q \<or> rotoinversion_matrix Q"
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1216
  by (metis rotoinversion_matrix_def rotation_matrix_def det_orthogonal_matrix)
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1217
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1218
(* ------------------------------------------------------------------------- *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1219
(* Explicit formulas for low dimensions.                                     *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1220
(* ------------------------------------------------------------------------- *)
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1221
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1222
lemma setprod_1: "setprod f {(1::nat)..1} = f 1"
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1223
  by simp
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1224
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1225
lemma setprod_2: "setprod f {(1::nat)..2} = f 1 * f 2"
40077
c8a9eaaa2f59 nat_number -> eval_nat_numeral
nipkow
parents: 39302
diff changeset
  1226
  by (simp add: eval_nat_numeral setprod_numseg mult_commute)
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1227
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1228
lemma setprod_3: "setprod f {(1::nat)..3} = f 1 * f 2 * f 3"
40077
c8a9eaaa2f59 nat_number -> eval_nat_numeral
nipkow
parents: 39302
diff changeset
  1229
  by (simp add: eval_nat_numeral setprod_numseg mult_commute)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1230
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1231
lemma det_1: "det (A::'a::comm_ring_1^1^1) = A$1$1"
44457
d366fa5551ef declare euclidean_simps [simp] at the point they are proved;
huffman
parents: 44260
diff changeset
  1232
  by (simp add: det_def sign_id)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1233
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1234
lemma det_2: "det (A::'a::comm_ring_1^2^2) = A$1$1 * A$2$2 - A$1$2 * A$2$1"
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1235
proof -
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1236
  have f12: "finite {2::2}" "1 \<notin> {2::2}" by auto
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1237
  show ?thesis
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1238
    unfolding det_def UNIV_2
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1239
    unfolding setsum_over_permutations_insert[OF f12]
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1240
    unfolding permutes_sing
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1241
    by (simp add: sign_swap_id sign_id swap_id_eq)
33175
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1242
qed
2083bde13ce1 distinguished session for multivariate analysis
himmelma
parents:
diff changeset
  1243
53253
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1244
lemma det_3:
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1245
  "det (A::'a::comm_ring_1^3^3) =
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1246
    A$1$1 * A$2$2 * A$3$3 +
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1247
    A$1$2 * A$2$3 * A$3$1 +
220f306f5c4e tuned proofs;
wenzelm
parents: 53077
diff changeset
  1248
    A$1$3 * A$2$1 * A$3$2 -