Theory Hermitian_Functional_Calculus

theory Hermitian_Functional_Calculus
  imports "HOL-Analysis.L2_Norm" QHLProver.Complex_Matrix Isabelle_Marries_Dirac.Quantum
begin

(*<*)
hide_const (open) Quantum.X Quantum.Y Quantum.Z Quantum.H Quantum.S Quantum.T
(*>*)

section ‹Functional calculus for Hermitian matrices›

text ‹For Hermitian $A$ and $g:\mathbb R\to\mathbb C$, $g(A)$ is the matrix that acts on every
eigenvector $v$ of $A$ with eigenvalue $\lambda$ as multiplication by $g(\lambda)$.  The
eigenvectors span $\C^n$, so this determines $g(A)$; for a spectral decomposition
$A=U\,\mathrm{diag}(D)\,U^*$ it is $U\,\mathrm{diag}(g\circ D)\,U^*$.›

text ‹$\diag(x_1,\dots,x_n)$, the diagonal matrix with the entries of a list.›

definition diag_matrix :: "complex list ⇒ complex Matrix.mat" where
  "diag_matrix xs = mat_diag (length xs) (λi. xs ! i)"

lemma diag_matrix_carrier [simp]: "diag_matrix xs ∈ carrier_mat (length xs) (length xs)"
  by (simp add: diag_matrix_def mat_diag_def)

lemma dim_diag_matrix [simp]: "dim_row (diag_matrix xs) = length xs" "dim_col (diag_matrix xs) = length xs"
  by (simp_all add: diag_matrix_def mat_diag_def)

text ‹\[ \diag(x_1,\dots,x_n)\,w=(x_1w_1,\dots,x_nw_n) \]›

lemma diag_matrix_mult_vec:
  assumes "dim_vec w = length xs"
  shows "diag_matrix xs *v w = Matrix.vec (length xs) (λi. xs ! i * w $ i)"
proof (rule eq_vecI)
  fix i assume "i < dim_vec (Matrix.vec (length xs) (λi. xs ! i * w $ i))"
  hence i: "i < length xs" by simp
  have "(diag_matrix xs *v w) $ i = (∑k = 0..<length xs. (if i = k then xs ! i else 0) * w $ k)"
    using i assms by (simp add: diag_matrix_def mat_diag_def mult_mat_vec_def scalar_prod_def cong: if_cong)
  also have "… = (∑k = 0..<length xs. if k = i then xs ! i * w $ i else 0)"
    by (rule sum.cong) auto
  also have "… = xs ! i * w $ i" using i by simp
  finally show "(diag_matrix xs *v w) $ i = Matrix.vec (length xs) (λi. xs ! i * w $ i) $ i"
    using i by simp
qed simp

text ‹\[ \bigl(M\,\diag(x)\bigr)_{\ast j}=x_j\,M_{\ast j} \]›

lemma col_mult_diag:
  assumes M: "M ∈ carrier_mat n (length xs)" and j: "j < length xs"
  shows "Matrix.col (M * diag_matrix xs) j = xs ! j ⋅v Matrix.col M j"
proof (rule eq_vecI)
  fix i assume "i < dim_vec (xs ! j ⋅v Matrix.col M j)"
  hence i: "i < n" using M by simp
  have "Matrix.col (M * diag_matrix xs) j $ i = (∑k = 0..<length xs. M $$ (i, k) * (if k = j then xs ! k else 0))"
    using M i j by (simp add: diag_matrix_def mat_diag_def scalar_prod_def atLeast0LessThan cong: if_cong)
  also have "… = (∑k = 0..<length xs. if k = j then M $$ (i, j) * xs ! j else 0)"
    by (rule sum.cong) auto
  also have "… = M $$ (i, j) * xs ! j" using j by simp
  finally show "Matrix.col (M * diag_matrix xs) j $ i = (xs ! j ⋅v Matrix.col M j) $ i"
    using M i j by (simp add: mult.commute)
qed (use M in simp)

text ‹\[ \diag(x)^*=\diag(\overline x) \]›

lemma diag_matrix_dagger: "(diag_matrix xs)† = diag_matrix (map cnj xs)"
  by (rule eq_matI) (auto simp: diag_matrix_def mat_diag_def dagger_def)

subsection ‹Adjoints›

text ‹QHLProver's const‹hermitian› and Schur decomposition, with IMD's adjoint $M^\dagger$,
const‹unitary› and norm $\norm v$.›

lemma dagger_adjoint: "M† = Complex_Matrix.adjoint M"
  by (rule eq_matI, simp_all add: dagger_def adjoint_eval)

lemma hermitian_dagger: "hermitian A ⟷ A† = A"
  by (simp add: hermitian_def dagger_adjoint)

lemma dagger_carrier: "M ∈ carrier_mat m n ⟹ M† ∈ carrier_mat n m"
  by (simp add: dagger_def)

lemma unitary_dagger: "unitary A ⟹ unitary (A†)"
  unfolding unitary_def by (simp add: dagger_of_dagger_is_id)

lemma unitary_from_complex_unitary:
  assumes "P ∈ carrier_mat n n" "Complex_Matrix.unitary P"
  shows "unitary P"
  using assms unfolding unitary_def dagger_adjoint by simp

lemma one_smult_mat: "(1::complex) ⋅m M = M"
  by (rule eq_matI, simp_all)

lemma diag_conj_carrier:
  assumes U: "U ∈ carrier_mat n n" and xs: "length xs = n"
  shows "U * diag_matrix xs * (U†) ∈ carrier_mat n n"
proof -
  have "diag_matrix xs ∈ carrier_mat n n" using diag_matrix_carrier[of xs] xs by simp
  thus ?thesis using mult_carrier_mat[OF mult_carrier_mat[OF U] dagger_carrier[OF U]] by blast
qed

subsection ‹Vector norms›

lemma cpx_vec_length_smult: "∥a ⋅v v∥ = cmod a * ∥v∥"
proof -
  have "(∑i<dim_vec v. (cmod (a * v $ i))2) = (cmod a)2 * (∑i<dim_vec v. (cmod (v $ i))2)"
    by (simp add: norm_mult power_mult_distrib sum_distrib_left)
  thus ?thesis by (simp add: cpx_vec_length_def real_sqrt_mult)
qed

text ‹The Euclidean norm $\norm v=\bigl(\sum_i|v_i|^2\bigr)^{1/2}$, with $\norm v^2=\mathrm{Re}\braket vv$, is
positive for $v\ne0$.›

lemma vnorm_L2: "∥v∥ = L2_set (λi. cmod (v $ i)) {..<dim_vec v}"
  by (simp add: cpx_vec_length_def L2_set_def)

lemma vnorm_ge0: "0 ≤ ∥v∥"
  by (simp add: cpx_vec_length_def sum_nonneg)

lemma vnorm_pos:
  assumes v: "dim_vec v = n" "v ≠ 0v n"
  shows "0 < ∥v∥"
proof -
  obtain i where i: "i < n" "v $ i ≠ 0"
  proof (rule ccontr)
    assume "¬ thesis"
    hence "v = 0v n" using that v(1) by (intro eq_vecI) auto
    thus False using v(2) by simp
  qed
  have "0 < (cmod (v $ i))2" using i by simp
  also have "… ≤ (∑j<dim_vec v. (cmod (v $ j))2)" using i v by (intro member_le_sum) auto
  finally show ?thesis by (simp add: cpx_vec_length_def)
qed

lemma vnorm_sq: "∥v∥2 = (∑i<dim_vec v. (cmod (v $ i))2)"
  by (simp add: cpx_vec_length_def sum_nonneg)

lemma vnorm_Re_inner: "Re ⟨v|v⟩ = ∥v∥2"
  unfolding cpx_vec_length_inner_prod[symmetric] by simp

text ‹The triangle inequality, in the forms used later, and its reverse
$\bigl|\norm a-\norm b\bigr|\le\norm{a-b}$:›

lemma vnorm_add_le:
  assumes "dim_vec a = dim_vec b"
  shows "∥a + b∥ ≤ ∥a∥ + ∥b∥"
proof -
  have "∥a + b∥ = L2_set (λi. cmod (a $ i + b $ i)) {..<dim_vec b}"
    unfolding vnorm_L2 using assms by (intro L2_set_cong) simp_all
  also have "… ≤ L2_set (λi. cmod (a $ i) + cmod (b $ i)) {..<dim_vec b}"
    by (rule L2_set_mono) (simp_all add: norm_triangle_ineq)
  also have "… ≤ L2_set (λi. cmod (a $ i)) {..<dim_vec b} + L2_set (λi. cmod (b $ i)) {..<dim_vec b}"
    by (rule L2_set_triangle_ineq)
  finally show ?thesis unfolding vnorm_L2 assms .
qed

lemma vnorm_minus_commute:
  assumes "dim_vec a = dim_vec b"
  shows "∥a - b∥ = ∥b - a∥"
  using assms by (simp add: cpx_vec_length_def norm_minus_commute)

lemma vnorm_diff_le:
  assumes a: "dim_vec a = n" and b: "dim_vec b = n" and c: "dim_vec c = n"
  shows "∥a - c∥ ≤ ∥a - b∥ + ∥b - c∥"
proof -
  have "a - c = (a - b) + (b - c)" using a b c by (intro eq_vecI) simp_all
  thus ?thesis using vnorm_add_le[of "a - b" "b - c"] a b c by simp
qed

lemma vnorm_le_diff_add:
  assumes "dim_vec a = dim_vec b"
  shows "∥a∥ ≤ ∥a - b∥ + ∥b∥"
proof -
  have "(a - b) + b = a" using assms by (intro eq_vecI) simp_all
  thus ?thesis using vnorm_add_le[of "a - b" b] assms by simp
qed

lemma vnorm_reverse:
  assumes "dim_vec a = dim_vec b"
  shows "¦∥a∥ - ∥b∥¦ ≤ ∥a - b∥"
  using vnorm_le_diff_add[OF assms] vnorm_le_diff_add[of b a] assms vnorm_minus_commute[OF assms] by simp

lemma vnorm_zero_vec: "∥0v m∥ = 0"
  by (simp add: cpx_vec_length_def)

text ‹A unitary is square: comparing $\Tr(U^*U)=\Tr(I_n)=n$ with $\Tr(UU^*)=\Tr(I_m)=m$, both being
$\sum_{i,j}|u_{ij}|^2$.›

lemma unitary_square_dim:
  assumes "unitary A"
  shows "dim_row A = dim_col A"
proof -
  let ?m = "dim_row A" and ?n = "dim_col A"
  have l: "(A†) * A = 1m ?n" and r: "A * (A†) = 1m ?m" using assms unfolding unitary_def by auto
  have "of_nat ?n = (∑c<?n. ((A†) * A) $$ (c, c))" by (simp add: l)
  also have "… = (∑c<?n. ∑r<?m. cnj (A $$ (r, c)) * A $$ (r, c))"
    by (rule sum.cong) (auto simp: scalar_prod_def dagger_def atLeast0LessThan)
  also have "… = (∑r<?m. ∑c<?n. A $$ (r, c) * cnj (A $$ (r, c)))"
    by (subst sum.swap) (simp add: mult.commute)
  also have "… = (∑r<?m. (A * (A†)) $$ (r, r))"
    by (rule sum.cong) (auto simp: scalar_prod_def dagger_def atLeast0LessThan)
  also have "… = of_nat ?m" by (simp add: r)
  finally show ?thesis by simp
qed

text ‹Unitaries preserve the norm, $\norm{Wy}=\norm y$; only the number of columns of $W$ has to
match $y$.›

lemma unitary_vnorm:
  assumes W: "W ∈ carrier_mat m n" "unitary W" and y: "dim_vec y = n"
  shows "∥W *v y∥ = ∥y∥"
proof -
  have "Matrix.col (W * |y⟩) 0 = W *v y"
    using W(1) y by (intro eq_vecI) (auto simp: ket_vec_def scalar_prod_def)
  thus ?thesis using unitary_is_length_preserving[OF W(2), of y] W(1) y by simp
qed

text ‹Products of unitaries are unitary.›

lemma unitary_mult:
  assumes "unitary A" "unitary B" "A ∈ carrier_mat n n" "B ∈ carrier_mat n n"
  shows "unitary (A * B)"
proof -
  have d: "A† ∈ carrier_mat n n" "B† ∈ carrier_mat n n" using assms(3,4) by (simp_all add: dagger_carrier)
  have u: "A† * A = 1m n" "A * (A†) = 1m n" "B† * B = 1m n" "B * (B†) = 1m n"
    using assms unfolding unitary_def by auto
  have "(A * B)† = (B†) * (A†)" using assms(3,4) by (simp add: dagger_of_prod)
  moreover have "(B†) * (A†) * (A * B) = (B†) * ((A†) * A) * B"
      "A * B * ((B†) * (A†)) = A * (B * (B†)) * (A†)"
    using assms(3,4) d by (mat_assoc n)+
  ultimately show ?thesis unfolding unitary_def using u assms(3,4) d by simp
qed

text ‹Powers of a unitary are unitary.›

lemma unitary_pow:
  assumes U: "U ∈ carrier_mat m m" and u: "unitary U"
  shows "unitary (U ^m k)"
proof (induction k)
  case 0
  show ?case by simp
next
  case (Suc k)
  have "unitary (U ^m k * U)" by (rule unitary_mult[OF Suc u pow_carrier_mat[OF U] U])
  thus ?case by simp
qed

subsection ‹Spectral decompositions›

text ‹‹spectral_decomp A U D›: $U$ unitary and $U^*AU=\mathrm{diag}(D)$.›

definition spectral_decomp :: "complex Matrix.mat ⇒ complex Matrix.mat ⇒ real list ⇒ bool" where
  "spectral_decomp A U D ⟷ U ∈ carrier_mat (dim_row A) (dim_row A) ∧ unitary U ∧
     length D = dim_row A ∧ U† * A * U = diag_matrix (map complex_of_real D)"
                                             
text ‹The spectral theorem, from QHLProver's Schur decomposition of Hermitian matrices.›

lemma spectral_decomp_exists:
  assumes A: "A ∈ carrier_mat n n" "hermitian A"
  shows "∃U D. spectral_decomp A U D"
proof -
  obtain es where c: "char_poly A = (∏e←es. [:- e, 1:])"
    using complex_mat_char_poly_factorizable[OF A(1)] by blast
  obtain B P Q where s: "unitary_schur_decomposition A es = (B, P, Q)"
    by (cases "unitary_schur_decomposition A es") auto
  have h: "similar_mat_wit A B P (Complex_Matrix.adjoint P)" "diagonal_mat B" "Complex_Matrix.unitary P"
      "∀i<n. B $$ (i, i) ∈ ℝ"
    using hermitian_eigenvalue_real[OF A c s] by auto
  have P: "P ∈ carrier_mat n n" "B ∈ carrier_mat n n" "A = P * B * Complex_Matrix.adjoint P"
    using h(1) A(1) unfolding similar_mat_wit_def Let_def by auto
  have u: "unitary P" by (rule unitary_from_complex_unitary[OF P(1) h(3)])
  hence PP: "P† * P = 1m n" using P(1) unfolding unitary_def by simp
  define D where "D = map (λi. Re (B $$ (i, i))) [0..<n]"
  have BD: "B = diag_matrix (map complex_of_real D)"
  proof (rule eq_matI)
    fix i j assume "i < dim_row (diag_matrix (map complex_of_real D))" "j < dim_col (diag_matrix (map complex_of_real D))"
    hence ij: "i < n" "j < n" by (simp_all add: D_def)
    show "B $$ (i, j) = diag_matrix (map complex_of_real D) $$ (i, j)"
      using h(2,4) ij P(2) by (cases "i = j") (auto simp: diag_matrix_def mat_diag_def D_def diagonal_mat_def)
  qed (use P(2) in ‹simp_all add: D_def›)
  have Pd: "P† ∈ carrier_mat n n" by (rule dagger_carrier[OF P(1)])
  have "P† * A * P = (P† * P) * B * (P† * P)"
    unfolding P(3) dagger_adjoint[symmetric] using P(1,2) Pd by (mat_assoc n)
  hence "P† * A * P = B" unfolding PP using P(2) by simp
  hence "spectral_decomp A P D" unfolding spectral_decomp_def BD using P(1) A(1) u by (simp add: D_def)
  thus ?thesis by blast
qed

text ‹Unpacking a spectral decomposition: $UU^*=U^*U=I$ and $A=U\,\diag(D)\,U^*$.›

lemma spectral_decompD:
  assumes A: "A ∈ carrier_mat n n" and sd: "spectral_decomp A U D"
  shows "U ∈ carrier_mat n n" "unitary U" "length D = n" "U† * U = 1m n" "U * (U†) = 1m n"
    "A = U * diag_matrix (map complex_of_real D) * (U†)" "A * U = U * diag_matrix (map complex_of_real D)"
proof -
  show U: "U ∈ carrier_mat n n" and u: "unitary U" and D: "length D = n"
    using sd A unfolding spectral_decomp_def by auto
  show UU: "U† * U = 1m n" and UU': "U * (U†) = 1m n" using u U unfolding unitary_def by auto
  have e: "U† * A * U = diag_matrix (map complex_of_real D)" using sd unfolding spectral_decomp_def by auto
  have Ud: "U† ∈ carrier_mat n n" by (rule dagger_carrier[OF U])
  have "U * diag_matrix (map complex_of_real D) * (U†) = (U * (U†)) * A * (U * (U†))"
    unfolding e[symmetric] using U Ud A by (mat_assoc n)
  thus "A = U * diag_matrix (map complex_of_real D) * (U†)" unfolding UU' using A by simp
  have "U * diag_matrix (map complex_of_real D) = (U * (U†)) * A * U"
    unfolding e[symmetric] using U Ud A by (mat_assoc n)
  thus "A * U = U * diag_matrix (map complex_of_real D)" unfolding UU' using A by simp
qed

text ‹The columns of $U$ are eigenvectors: $Au_j=D_ju_j$.›

lemma spectral_decomp_col:
  assumes A: "A ∈ carrier_mat n n" and sd: "spectral_decomp A U D" and j: "j < n"
  shows "A *v Matrix.col U j = complex_of_real (D ! j) ⋅v Matrix.col U j"
proof -
  note d = spectral_decompD[OF A sd]
  have "A *v Matrix.col U j = Matrix.col (A * U) j" by (rule col_mult2[OF A d(1) j, symmetric])
  also have "… = Matrix.col (U * diag_matrix (map complex_of_real D)) j" using d(7) by simp
  also have "… = complex_of_real (D ! j) ⋅v Matrix.col U j"
    using col_mult_diag[of U n "map complex_of_real D" j] d(1,3) j by simp
  finally show ?thesis .
qed

subsection ‹The definition›

text ‹$B$ acts as $g$ on the eigenvectors of $A$, written ‹B acts_as g on_eigenvectors_of A›, if
$Av=\lambda v$ implies $Bv=g(\lambda)\,v$.  The matrix
$g(A)$ is the $n\times n$ matrix with this property; it exists and is unique (below).›

definition acts_on_eigenvectors :: "complex Matrix.mat ⇒ (real ⇒ complex) ⇒ complex Matrix.mat ⇒ bool" where
  "acts_on_eigenvectors A g B ⟷ (∀v l. dim_vec v = dim_row A ⟶
     A *v v = complex_of_real l ⋅v v ⟶ B *v v = g l ⋅v v)"

(*<*)
syntax "_acts_on_eigenvectors" :: "complex Matrix.mat ⇒ (real ⇒ complex) ⇒ complex Matrix.mat ⇒ bool"
  ("(_/ acts'_as _/ on'_eigenvectors'_of _)" [51, 51, 51] 50)
syntax_consts "_acts_on_eigenvectors" ⇌ acts_on_eigenvectors
translations "B acts_as g on_eigenvectors_of A" ⇌ "CONST acts_on_eigenvectors A g B"
(*>*)

definition mat_fun :: "(real ⇒ complex) ⇒ complex Matrix.mat ⇒ complex Matrix.mat" where
  "mat_fun g A = (SOME B. B ∈ carrier_mat (dim_row A) (dim_row A) ∧ B acts_as g on_eigenvectors_of A)"

text ‹The spectrum: the real eigenvalues (JNF's ‹eigenvalue›).›

definition herm_spectrum :: "complex Matrix.mat ⇒ real set" where
  "herm_spectrum A = {l. eigenvalue A (complex_of_real l)}"

lemma herm_spectrum_iff:
  "l ∈ herm_spectrum A ⟷ (∃v. dim_vec v = dim_row A ∧ v ≠ 0v (dim_row A) ∧ A *v v = complex_of_real l ⋅v v)"
  unfolding herm_spectrum_def mem_Collect_eq eigenvalue_def eigenvector_def carrier_vec_def by simp

text ‹Each $D_j$ of a spectral decomposition is an eigenvalue of $A$.›

lemma spectral_decomp_eig_in_spectrum:
  assumes A: "A ∈ carrier_mat n n" and sd: "spectral_decomp A U D" and j: "j < n"
  shows "D ! j ∈ herm_spectrum A"
proof -
  note d = spectral_decompD[OF A sd]
  have cd: "dim_vec (Matrix.col U j) = n" using d(1) by simp
  have nz: "Matrix.col U j ≠ 0v n"
  proof
    assume z: "Matrix.col U j = 0v n"
    have "(U† * U) $$ (j, j) = Matrix.row (U†) j ∙ Matrix.col U j"
      by (rule index_mult_mat(1)) (use d(1) j in simp_all)
    also have "… = 0" unfolding z by (rule scalar_prod_right_zero) (use d(1) j in ‹simp add: dagger_def›)
    finally show False using d(4) j by simp
  qed
  show ?thesis unfolding herm_spectrum_iff
    using spectral_decomp_col[OF A sd j] cd nz A by (intro exI[of _ "Matrix.col U j"]) simp
qed

lemma acts_on_eigenvectorsD:
  "B acts_as g on_eigenvectors_of A ⟹ dim_vec v = dim_row A ⟹ A *v v = complex_of_real l ⋅v v ⟹
   B *v v = g l ⋅v v"
  unfolding acts_on_eigenvectors_def by blast

text ‹$U\,\mathrm{diag}(g\circ D)\,U^*$ acts correctly on eigenvectors: if $Av=\lambda v$ then
$w=U^*v$ has $D_iw_i=\lambda w_i$, so $g(D_i)w_i=g(\lambda)w_i$.›

lemma spectral_decomp_acts_on_eigenvectors:
  assumes A: "A ∈ carrier_mat n n" and sd: "spectral_decomp A U D"
  shows "U * diag_matrix (map g D) * (U†) acts_as g on_eigenvectors_of A"
  unfolding acts_on_eigenvectors_def
proof (intro allI impI)
  fix v l assume v: "dim_vec v = dim_row A" and ev: "A *v v = complex_of_real l ⋅v v"
  note d = spectral_decompD[OF A sd]
  have vc: "v ∈ carrier_vec n" by (rule carrier_vecI) (use v A in simp)
  have Uc: "U† ∈ carrier_mat n n" by (rule dagger_carrier[OF d(1)])
  define w where "w = U† *v v"
  have wc: "w ∈ carrier_vec n" unfolding w_def using Uc vc by simp
  have Uw: "U *v w = v"
    unfolding w_def using assoc_mult_mat_vec[OF d(1) Uc vc, symmetric] d(5) vc by simp
  have "diag_matrix (map complex_of_real D) *v w = (U† * A * U) *v w"
    using sd unfolding spectral_decomp_def by simp
  also have "… = U† *v (A *v (U *v w))"
    using Uc A d(1) wc by (simp add: assoc_mult_mat_vec[of _ n n _ n])
  also have "… = complex_of_real l ⋅v w"
    unfolding Uw ev unfolding w_def by (rule mult_mat_vec[OF Uc vc])
  finally have Dw: "diag_matrix (map complex_of_real D) *v w = complex_of_real l ⋅v w" .
  have wi: "w $ i = 0 ∨ D ! i = l" if i: "i < n" for i
  proof -
    have "(diag_matrix (map complex_of_real D) *v w) $ i = complex_of_real (D ! i) * w $ i"
      using diag_matrix_mult_vec[of w "map complex_of_real D"] wc d(3) i by simp
    hence "complex_of_real (D ! i) * w $ i = complex_of_real l * w $ i"
      using Dw i wc by (metis carrier_vecD index_smult_vec(1))
    thus ?thesis by auto
  qed
  have gw: "diag_matrix (map g D) *v w = g l ⋅v w"
  proof (rule eq_vecI)
    fix i assume "i < dim_vec (g l ⋅v w)"
    hence i: "i < n" using wc by simp
    show "(diag_matrix (map g D) *v w) $ i = (g l ⋅v w) $ i"
      using diag_matrix_mult_vec[of w "map g D"] wc d(3) i wi[OF i] by auto
  qed (use wc d(3) in simp)
  have gc: "diag_matrix (map g D) ∈ carrier_mat n n" using d(3) diag_matrix_carrier by (metis length_map)
  have "(U * diag_matrix (map g D) * (U†)) *v v = U *v (diag_matrix (map g D) *v w)"
    unfolding w_def assoc_mult_mat_vec[OF mult_carrier_mat[OF d(1) gc] Uc vc]
    by (rule assoc_mult_mat_vec[OF d(1) gc mult_mat_vec_carrier[OF Uc vc]])
  also have "… = g l ⋅v (U *v w)" unfolding gw using d(1) wc by (rule mult_mat_vec)
  also note Uw
  finally show "(U * diag_matrix (map g D) * (U†)) *v v = g l ⋅v v" .
qed

text ‹Two matrices that agree on every eigenvector of a Hermitian $A$ agree on its eigenbasis $U$, hence
are equal.›

lemma eigvec_mat_eqI:
  assumes A: "A ∈ carrier_mat n n" "hermitian A"
      and B1: "B1 ∈ carrier_mat K n" and B2: "B2 ∈ carrier_mat K n"
      and eq: "⋀v l. dim_vec v = n ⟹ A *v v = complex_of_real l ⋅v v ⟹ B1 *v v = B2 *v v"
  shows "B1 = B2"
proof -
  obtain U D where sd: "spectral_decomp A U D" using spectral_decomp_exists[OF A] by blast
  note d = spectral_decompD[OF A(1) sd]
  have BU: "B1 * U = B2 * U"
  proof (rule Matrix.mat_col_eqI)
    fix j assume "j < dim_col (B2 * U)"
    hence j: "j < n" using d(1) by simp
    have cU: "dim_vec (Matrix.col U j) = n" using d(1) by simp
    have "Matrix.col (B1 * U) j = B1 *v Matrix.col U j" by (rule col_mult2[OF B1 d(1) j])
    also have "… = B2 *v Matrix.col U j" by (rule eq[OF cU spectral_decomp_col[OF A(1) sd j]])
    also have "… = Matrix.col (B2 * U) j" by (rule col_mult2[OF B2 d(1) j, symmetric])
    finally show "Matrix.col (B1 * U) j = Matrix.col (B2 * U) j" .
  qed (use B1 B2 d(1) in simp_all)
  have "B1 = (B1 * U) * (U†)"
    using assoc_mult_mat[OF B1 d(1) dagger_carrier[OF d(1)]] d(5) B1 by simp
  also have "… = (B2 * U) * (U†)" by (simp only: BU)
  also have "… = B2"
    using assoc_mult_mat[OF B2 d(1) dagger_carrier[OF d(1)]] d(5) B2 by simp
  finally show ?thesis .
qed

text ‹Hence $g(A)$ is well defined: an $n\times n$ matrix acting as $g$ on the eigenvectors.›

lemma
  assumes A: "A ∈ carrier_mat n n" "hermitian A"
  shows mat_fun_carrier [simp]: "mat_fun g A ∈ carrier_mat n n"
    and mat_fun_acts_on_eigenvectors: "mat_fun g A acts_as g on_eigenvectors_of A"
proof -
  obtain U D where sd: "spectral_decomp A U D" using spectral_decomp_exists[OF A] by blast
  note d = spectral_decompD[OF A(1) sd]
  have "U * diag_matrix (map g D) * (U†) ∈ carrier_mat n n"
    by (rule diag_conj_carrier) (use d(1,3) in simp_all)
  hence ex: "∃B. B ∈ carrier_mat (dim_row A) (dim_row A) ∧ B acts_as g on_eigenvectors_of A"
    using spectral_decomp_acts_on_eigenvectors[OF A(1) sd] A(1) by auto
  have "mat_fun g A ∈ carrier_mat (dim_row A) (dim_row A) ∧ mat_fun g A acts_as g on_eigenvectors_of A"
    unfolding mat_fun_def by (rule someI_ex[OF ex])
  thus "mat_fun g A ∈ carrier_mat n n" "mat_fun g A acts_as g on_eigenvectors_of A" using A(1) by auto
qed

text ‹In particular $g(A)$ has the dimensions of $A$.›

lemma mat_fun_dims [simp]:
  assumes "A ∈ carrier_mat n n" "hermitian A"
  shows "dim_row (mat_fun g A) = n" "dim_col (mat_fun g A) = n"
  using mat_fun_carrier[OF assms] by auto

text ‹\[ Av=\lambda v\quad\Longrightarrow\quad g(A)\,v=g(\lambda)\,v. \]›

theorem mat_fun_eigen:
  assumes A: "A ∈ carrier_mat n n" "hermitian A"
      and v: "dim_vec v = n" and ev: "A *v v = complex_of_real l ⋅v v"
  shows "mat_fun g A *v v = g l ⋅v v"
  using acts_on_eigenvectorsD[OF mat_fun_acts_on_eigenvectors[OF A] _ ev] v A(1) by simp

text ‹Uniqueness: every $n\times n$ matrix acting as $g$ on the eigenvectors is $g(A)$.›

lemma mat_fun_eqI:
  assumes A: "A ∈ carrier_mat n n" "hermitian A"
      and B: "B ∈ carrier_mat n n" "B acts_as g on_eigenvectors_of A"
  shows "mat_fun g A = B"
proof (rule eigvec_mat_eqI[OF A mat_fun_carrier[OF A] B(1)])
  fix v l assume v: "dim_vec v = n" and ev: "A *v v = complex_of_real l ⋅v v"
  show "mat_fun g A *v v = B *v v"
    using acts_on_eigenvectorsD[OF mat_fun_acts_on_eigenvectors[OF A] _ ev] acts_on_eigenvectorsD[OF B(2) _ ev] v A(1) by simp
qed

text ‹So $g(A)$ is the unique $n\times n$ matrix that acts as $g$ on the eigenvectors of $A$.›

corollary mat_fun_unique:
  assumes A: "A ∈ carrier_mat n n" "hermitian A"
  shows "∃!B. B ∈ carrier_mat n n ∧ B acts_as g on_eigenvectors_of A"
  using mat_fun_carrier[OF A] mat_fun_acts_on_eigenvectors[OF A] mat_fun_eqI[OF A] by blast

text ‹So for every spectral decomposition of $A$,
\[ g(A)=U\,\diag\bigl(g(D_1),\dots,g(D_n)\bigr)\,U^*. \]›

theorem mat_fun_decomp:
  assumes A: "A ∈ carrier_mat n n" "hermitian A" and sd: "spectral_decomp A U D"
  shows "mat_fun g A = U * diag_matrix (map g D) * (U†)"
proof (rule mat_fun_eqI[OF A])
  note d = spectral_decompD[OF A(1) sd]
  show "U * diag_matrix (map g D) * (U†) ∈ carrier_mat n n"
    by (rule diag_conj_carrier) (use d(1,3) in simp_all)
  show "U * diag_matrix (map g D) * (U†) acts_as g on_eigenvectors_of A"
    by (rule spectral_decomp_acts_on_eigenvectors[OF A(1) sd])
qed

text ‹Only the values of $g$ on the spectrum matter.›

lemma mat_fun_cong:
  assumes A: "A ∈ carrier_mat n n" "hermitian A"
      and gh: "⋀l. l ∈ herm_spectrum A ⟹ g l = h l"
  shows "mat_fun g A = mat_fun h A"
proof (rule mat_fun_eqI[OF A mat_fun_carrier[OF A]])
  show "mat_fun h A acts_as g on_eigenvectors_of A" unfolding acts_on_eigenvectors_def
  proof (intro allI impI)
    fix v l assume v: "dim_vec v = dim_row A" and ev: "A *v v = complex_of_real l ⋅v v"
    have hv: "mat_fun h A *v v = h l ⋅v v" using mat_fun_eigen[OF A _ ev] v A(1) by simp
    show "mat_fun h A *v v = g l ⋅v v"
    proof (cases "v = 0v (dim_row A)")
      case True
      thus ?thesis using hv by (auto intro!: eq_vecI)
    next
      case False
      hence "l ∈ herm_spectrum A" unfolding herm_spectrum_iff using v ev by blast
      thus ?thesis using hv gh by simp
    qed
  qed
qed

subsection ‹Algebra›

text ‹The identity function gives $A$, a constant $c$ gives $cI$:›

lemma mat_fun_id: "A ∈ carrier_mat n n ⟹ hermitian A ⟹ mat_fun complex_of_real A = A"
  by (rule mat_fun_eqI) (auto simp: acts_on_eigenvectors_def)

lemma mat_fun_const:
  assumes A: "A ∈ carrier_mat n n" "hermitian A"
  shows "mat_fun (λ_. c) A = c ⋅m 1m n"
proof (rule mat_fun_eqI[OF A])
  show "c ⋅m 1m n acts_as (λ_. c) on_eigenvectors_of A" unfolding acts_on_eigenvectors_def
    using A(1) by (auto simp: smult_mat_mult_mat_vec_assoc[of "1m n" n n])
qed simp

lemma mat_fun_one: "A ∈ carrier_mat n n ⟹ hermitian A ⟹ mat_fun (λ_. 1) A = 1m n"
  using mat_fun_const[of A n 1] by (auto intro!: eq_matI)

text ‹The calculus is multiplicative and respects adjoints:
\[ g(A)\,h(A)=(gh)(A),\qquad g(A)^*=\overline g(A). \]›

theorem mat_fun_mult:
  assumes A: "A ∈ carrier_mat n n" "hermitian A"
  shows "mat_fun g A * mat_fun h A = mat_fun (λx. g x * h x) A"
proof (rule mat_fun_eqI[OF A, symmetric])
  show "mat_fun g A * mat_fun h A ∈ carrier_mat n n" by (rule mult_carrier_mat[OF mat_fun_carrier[OF A] mat_fun_carrier[OF A]])
  show "mat_fun g A * mat_fun h A acts_as (λx. g x * h x) on_eigenvectors_of A" unfolding acts_on_eigenvectors_def
  proof (intro allI impI)
    fix v l assume v: "dim_vec v = dim_row A" and ev: "A *v v = complex_of_real l ⋅v v"
    have vn: "dim_vec v = n" using v A(1) by simp
    have vc: "v ∈ carrier_vec n" by (rule carrier_vecI[OF vn])
    have "(mat_fun g A * mat_fun h A) *v v = mat_fun g A *v (mat_fun h A *v v)"
      by (rule assoc_mult_mat_vec[OF mat_fun_carrier[OF A] mat_fun_carrier[OF A] vc])
    also have "… = mat_fun g A *v (h l ⋅v v)" by (simp only: mat_fun_eigen[OF A vn ev])
    also have "… = h l ⋅v (mat_fun g A *v v)" by (rule mult_mat_vec[OF mat_fun_carrier[OF A] vc])
    also have "… = (g l * h l) ⋅v v" by (simp add: mat_fun_eigen[OF A vn ev] smult_smult_assoc mult.commute)
    finally show "(mat_fun g A * mat_fun h A) *v v = (g l * h l) ⋅v v" .
  qed
qed

theorem mat_fun_dagger:
  assumes A: "A ∈ carrier_mat n n" "hermitian A"
  shows "(mat_fun g A)† = mat_fun (λx. cnj (g x)) A"
proof -
  obtain U D where sd: "spectral_decomp A U D" using spectral_decomp_exists[OF A] by blast
  note d = spectral_decompD[OF A(1) sd]
  have gc: "diag_matrix (map g D) ∈ carrier_mat n n" using d(3) diag_matrix_carrier by (metis length_map)
  have Ud: "U† ∈ carrier_mat n n" by (rule dagger_carrier[OF d(1)])
  have cg: "diag_matrix (map (λx. cnj (g x)) D) ∈ carrier_mat n n"
    using diag_matrix_carrier[of "map (λx. cnj (g x)) D"] d(3) by simp
  have Ug: "U * diag_matrix (map g D) ∈ carrier_mat n n" by (rule mult_carrier_mat[OF d(1) gc])
  have "(U * diag_matrix (map g D) * (U†))† = ((U†)†) * ((U * diag_matrix (map g D))†)"
    by (rule dagger_of_prod) (use d(1,3) in simp)
  also have "… = U * (((diag_matrix (map g D))†) * (U†))"
    using dagger_of_prod[of U "diag_matrix (map g D)"] d(1,3) gc by (simp add: dagger_of_dagger_is_id)
  also have "… = U * (diag_matrix (map (λx. cnj (g x)) D) * (U†))"
    by (simp add: diag_matrix_dagger o_def)
  also have "… = U * diag_matrix (map (λx. cnj (g x)) D) * (U†)"
    by (rule assoc_mult_mat[OF d(1) cg Ud, symmetric])
  finally show ?thesis using mat_fun_decomp[OF A sd] by simp
qed

text ‹Hence $f(A)$ is Hermitian for real $f$, and $g(A)$ is unitary when $|g|=1$ on the spectrum, since
$g(A)^*g(A)=|g|^2(A)=I$.›

lemma mat_fun_hermitian:
  assumes A: "A ∈ carrier_mat n n" "hermitian A"
  shows "hermitian (mat_fun (λx. complex_of_real (f x)) A)"
  unfolding hermitian_dagger by (simp add: mat_fun_dagger[OF A])

theorem mat_fun_unitary:
  assumes A: "A ∈ carrier_mat n n" "hermitian A"
      and g: "⋀l. l ∈ herm_spectrum A ⟹ cmod (g l) = 1"
  shows "unitary (mat_fun g A)"
proof -
  have c: "mat_fun (λx. cnj (g x) * g x) A = 1m n" "mat_fun (λx. g x * cnj (g x)) A = 1m n"
  proof -
    have e: "cnj (g l) * g l = 1" "g l * cnj (g l) = 1" if "l ∈ herm_spectrum A" for l
    proof -
      have "g l * cnj (g l) = complex_of_real ((cmod (g l))2)" by (rule complex_norm_square[symmetric])
      thus "g l * cnj (g l) = 1" "cnj (g l) * g l = 1" using g[OF that] by (simp_all add: mult.commute)
    qed
    show "mat_fun (λx. cnj (g x) * g x) A = 1m n"
      using mat_fun_cong[OF A, of "λx. cnj (g x) * g x" "λ_. 1"] e(1) mat_fun_one[OF A] by simp
    show "mat_fun (λx. g x * cnj (g x)) A = 1m n"
      using mat_fun_cong[OF A, of "λx. g x * cnj (g x)" "λ_. 1"] e(2) mat_fun_one[OF A] by simp
  qed
  show ?thesis unfolding unitary_def
    using c mat_fun_mult[OF A] mat_fun_dagger[OF A] carrier_matD[OF mat_fun_carrier[OF A, of g]] by simp
qed

text ‹The calculus is additive in the function: $(g+h)(A)=g(A)+h(A)$.›

lemma mat_fun_add:
  assumes A: "A ∈ carrier_mat n n" "hermitian A"
  shows "mat_fun (λx. g x + h x) A = mat_fun g A + mat_fun h A"
proof (rule mat_fun_eqI[OF A])
  show "mat_fun g A + mat_fun h A ∈ carrier_mat n n" using A by simp
  show "mat_fun g A + mat_fun h A acts_as (λx. g x + h x) on_eigenvectors_of A" unfolding acts_on_eigenvectors_def
  proof (intro allI impI)
    fix v l assume v: "dim_vec v = dim_row A" and ev: "A *v v = complex_of_real l ⋅v v"
    have vn: "dim_vec v = n" using v A(1) by simp
    have vc: "v ∈ carrier_vec n" by (rule carrier_vecI[OF vn])
    have "(mat_fun g A + mat_fun h A) *v v = mat_fun g A *v v + mat_fun h A *v v"
      by (rule add_mult_distrib_mat_vec[OF mat_fun_carrier[OF A] mat_fun_carrier[OF A] vc])
    also have "… = g l ⋅v v + h l ⋅v v" by (simp add: mat_fun_eigen[OF A vn ev])
    also have "… = (g l + h l) ⋅v v" by (simp add: add_smult_distrib_vec)
    finally show "(mat_fun g A + mat_fun h A) *v v = (g l + h l) ⋅v v" .
  qed
qed

text ‹It is homogeneous: $(cg)(A)=c\,g(A)$.›

lemma mat_fun_smult:
  assumes A: "A ∈ carrier_mat n n" "hermitian A"
  shows "mat_fun (λx. c * g x) A = c ⋅m mat_fun g A"
proof (rule mat_fun_eqI[OF A])
  show "c ⋅m mat_fun g A ∈ carrier_mat n n" using A by simp
  show "c ⋅m mat_fun g A acts_as (λx. c * g x) on_eigenvectors_of A" unfolding acts_on_eigenvectors_def
  proof (intro allI impI)
    fix v l assume v: "dim_vec v = dim_row A" and ev: "A *v v = complex_of_real l ⋅v v"
    have vn: "dim_vec v = n" using v A(1) by simp
    have vc: "v ∈ carrier_vec n" by (rule carrier_vecI[OF vn])
    have "(c ⋅m mat_fun g A) *v v = c ⋅v (mat_fun g A *v v)"
      by (rule smult_mat_mult_mat_vec_assoc[OF mat_fun_carrier[OF A] vc])
    thus "(c ⋅m mat_fun g A) *v v = (c * g l) ⋅v v" by (simp add: mat_fun_eigen[OF A vn ev] smult_smult_assoc)
  qed
qed

text ‹Any two functions of $A$ commute: $g(A)\,h(A)=h(A)\,g(A)$.›

lemma mat_fun_commute:
  assumes A: "A ∈ carrier_mat n n" "hermitian A"
  shows "mat_fun g A * mat_fun h A = mat_fun h A * mat_fun g A"
  by (simp add: mat_fun_mult[OF A] mult.commute)

text ‹Powers: $g(A)^k=(g^k)(A)$.›

lemma mat_fun_pow:
  assumes A: "A ∈ carrier_mat n n" "hermitian A"
  shows "mat_fun g A ^m k = mat_fun (λx. g x ^ k) A"
proof (induction k)
  case 0 show ?case using mat_fun_one[OF A] mat_fun_carrier[OF A, of g] by simp
next
  case (Suc k)
  have "mat_fun g A ^m Suc k = mat_fun (λx. g x ^ k) A * mat_fun g A" using Suc by simp
  also have "… = mat_fun (λx. g x ^ Suc k) A" by (simp add: mat_fun_mult[OF A] mult.commute)
  finally show ?case .
qed

text ‹Composition: for real $f$, $g(f(A))=(g\circ f)(A)$, since an eigenvector of $A$ with eigenvalue
$\lambda$ is one of $f(A)$ with eigenvalue $f(\lambda)$.›

lemma mat_fun_comp:
  assumes A: "A ∈ carrier_mat n n" "hermitian A"
  shows "mat_fun g (mat_fun (λx. complex_of_real (f x)) A) = mat_fun (λx. g (f x)) A"
proof -
  let ?B = "mat_fun (λx. complex_of_real (f x)) A"
  have B: "?B ∈ carrier_mat n n" "hermitian ?B" using A mat_fun_hermitian[OF A, of f] by simp_all
  show ?thesis
  proof (rule mat_fun_eqI[OF A, symmetric])
    show "mat_fun g ?B ∈ carrier_mat n n" using B by simp
    show "mat_fun g ?B acts_as (λx. g (f x)) on_eigenvectors_of A" unfolding acts_on_eigenvectors_def
    proof (intro allI impI)
      fix v l assume v: "dim_vec v = dim_row A" and ev: "A *v v = complex_of_real l ⋅v v"
      have vn: "dim_vec v = n" using v A(1) by simp
      have "?B *v v = complex_of_real (f l) ⋅v v" by (rule mat_fun_eigen[OF A vn ev])
      thus "mat_fun g ?B *v v = g (f l) ⋅v v" by (rule mat_fun_eigen[OF B vn])
    qed
  qed
qed

text ‹For a real diagonal matrix the calculus acts entrywise:
\[ g\bigl(\diag(D_1,\dots,D_n)\bigr)=\diag\bigl(g(D_1),\dots,g(D_n)\bigr). \]›

lemma mat_fun_diag:
  "mat_fun g (diag_matrix (map complex_of_real D)) = diag_matrix (map g D)"
proof -
  let ?n = "length D" and ?A = "diag_matrix (map complex_of_real D)"
  have Ac: "?A ∈ carrier_mat ?n ?n" by (metis diag_matrix_carrier length_map)
  have Ah: "hermitian ?A" unfolding hermitian_dagger diag_matrix_dagger by (simp add: comp_def)
  have sd: "spectral_decomp ?A (1m ?n) D"
    unfolding spectral_decomp_def using Ac by (simp add: id_is_unitary)
  have "mat_fun g ?A = (1m ?n * diag_matrix (map g D)) * ((1m ?n)†)" by (rule mat_fun_decomp[OF Ac Ah sd])
  also have "… = diag_matrix (map g D)" by simp
  finally show ?thesis .
qed

text ‹Powers: $G^{i+j}=G^iG^j$, and $Uu=zu$ implies $U^ku=z^ku$.›

lemma pow_mat_add: "G ∈ carrier_mat m m ⟹ G ^m (i + j) = G ^m i * G ^m j"
proof (induction j)
  case 0
  show ?case using 0 by simp
next
  case (Suc j)
  have "G ^m (i + Suc j) = G ^m i * G ^m j * G" using Suc by simp
  also have "… = G ^m i * (G ^m j * G)" by (rule assoc_mult_mat) (use Suc.prems in auto)
  finally show ?case by simp
qed

lemma pow_eigen:
  fixes U :: "complex Matrix.mat"
  assumes U: "U ∈ carrier_mat m m" and u: "dim_vec u = m" and ev: "U *v u = z ⋅v u"
  shows "(U ^m k) *v u = z ^ k ⋅v u"
proof (induction k)
  case 0
  have "u ∈ carrier_vec m" using u by (rule carrier_vecI)
  thus ?case using carrier_matD(1)[OF U] by (auto intro!: eq_vecI)
next
  case (Suc k)
  have uc: "u ∈ carrier_vec m" using u by (rule carrier_vecI)
  have "(U ^m Suc k) *v u = (U ^m k) *v (U *v u)"
    using assoc_mult_mat_vec[OF pow_carrier_mat[OF U] U uc, of k] by simp
  also have "… = z ⋅v ((U ^m k) *v u)" unfolding ev by (rule mult_mat_vec[OF pow_carrier_mat[OF U] uc])
  also have "… = z ^ Suc k ⋅v u" unfolding Suc by (simp add: smult_smult_assoc)
  finally show ?case .
qed

subsection ‹Time evolution›

text ‹$e^{itA}$, the evolution under the Hamiltonian $A$.›

definition evolution :: "complex Matrix.mat ⇒ real ⇒ complex Matrix.mat" where
  "evolution A t = mat_fun (λx. cis (t * x)) A"

context
  fixes A :: "complex Matrix.mat" and n :: nat
  assumes A: "A ∈ carrier_mat n n" "hermitian A"
begin

text ‹$e^{itA}$ is unitary, acts on an eigenvector by $e^{itA}v=e^{it\lambda}v$, and is a one-parameter group:
\[ e^{i0A}=I,\qquad e^{i(s+t)A}=e^{isA}e^{itA},\qquad \bigl(e^{itA}\bigr)^k=e^{iktA}. \]›

lemma evolution_carrier [simp]: "evolution A t ∈ carrier_mat n n"
  unfolding evolution_def using A by simp

lemma evolution_dims [simp]: "dim_row (evolution A t) = n" "dim_col (evolution A t) = n"
  using carrier_matD[OF evolution_carrier] by auto

lemma evolution_eigen:
  "dim_vec v = n ⟹ A *v v = complex_of_real l ⋅v v ⟹ evolution A t *v v = cis (t * l) ⋅v v"
  unfolding evolution_def by (rule mat_fun_eigen[OF A])

lemma evolution_unitary: "unitary (evolution A t)"
  unfolding evolution_def by (rule mat_fun_unitary[OF A]) simp

lemma evolution_zero: "evolution A 0 = 1m n"
  unfolding evolution_def using mat_fun_one[OF A] by simp

lemma evolution_add: "evolution A (s + t) = evolution A s * evolution A t"
  unfolding evolution_def mat_fun_mult[OF A] by (simp add: cis_mult distrib_right)

lemma evolution_pow: "evolution A t ^m k = evolution A (real k * t)"
proof (induction k)
  case 0
  show ?case using evolution_zero carrier_matD(1)[OF evolution_carrier] by simp
next
  case (Suc k)
  have "evolution A t ^m Suc k = evolution A (real k * t) * evolution A t" using Suc by simp
  also have "… = evolution A (real (Suc k) * t)" by (simp add: evolution_add[symmetric] distrib_right add.commute)
  finally show ?case .
qed

end

subsection ‹The inverse›

text ‹$A^{-1}=g(A)$ for $g(x)=1/x$; since $1/0=0$ in HOL this is the pseudo-inverse in general.›

definition herm_inv :: "complex Matrix.mat ⇒ complex Matrix.mat" where
  "herm_inv A = mat_fun (λx. complex_of_real (inverse x)) A"

text ‹$A^{-1}$ is an $n\times n$ matrix.›

lemma herm_inv_carrier [simp]: "A ∈ carrier_mat n n ⟹ hermitian A ⟹ herm_inv A ∈ carrier_mat n n"
  unfolding herm_inv_def by simp

lemma herm_inv_dims [simp]:
  assumes "A ∈ carrier_mat n n" "hermitian A"
  shows "dim_row (herm_inv A) = n" "dim_col (herm_inv A) = n"
  using herm_inv_carrier[OF assms] by auto

text ‹If $0$ is not an eigenvalue, $g(x)=1/x$ gives the inverse: $A^{-1}A=AA^{-1}=I$.›

theorem herm_inv:
  assumes A: "A ∈ carrier_mat n n" "hermitian A" and z: "0 ∉ herm_spectrum A"
  shows "herm_inv A * A = 1m n" "A * herm_inv A = 1m n"
proof -
  have "mat_fun (λx. complex_of_real (inverse x) * complex_of_real x) A = mat_fun (λ_. 1) A"
       "mat_fun (λx. complex_of_real x * complex_of_real (inverse x)) A = mat_fun (λ_. 1) A"
    by (rule mat_fun_cong[OF A], metis z of_real_eq_0_iff left_inverse right_inverse of_real_inverse)+
  thus "herm_inv A * A = 1m n" "A * herm_inv A = 1m n"
    unfolding herm_inv_def using mat_fun_mult[OF A] mat_fun_id[OF A] mat_fun_one[OF A] by metis+
qed

text ‹So $x=A^{-1}b$ solves $Ax=b$; $A^{-1}$ acts on eigenvectors by $\lambda^{-1}$ and is Hermitian.›

lemma herm_inv_solves:
  assumes A: "A ∈ carrier_mat n n" "hermitian A" and z: "0 ∉ herm_spectrum A" and b: "dim_vec b = n"
  shows "A *v (herm_inv A *v b) = b"
proof -
  have Hc: "herm_inv A ∈ carrier_mat n n" unfolding herm_inv_def by (rule mat_fun_carrier[OF A])
  have "A *v (herm_inv A *v b) = (A * herm_inv A) *v b" by (rule assoc_mult_mat_vec[symmetric, OF A(1) Hc]) (use b in auto)
  also have "A * herm_inv A = 1m n" by (rule herm_inv(2)[OF A z])
  finally show ?thesis using b by (simp add: one_mult_mat_vec[OF carrier_vecI[OF b]])
qed

lemma herm_inv_eigen:
  assumes A: "A ∈ carrier_mat n n" "hermitian A"
      and v: "dim_vec v = n" and ev: "A *v v = complex_of_real l ⋅v v"
  shows "herm_inv A *v v = complex_of_real (inverse l) ⋅v v"
  unfolding herm_inv_def by (rule mat_fun_eigen[OF A v ev])

lemma herm_inv_hermitian: "A ∈ carrier_mat n n ⟹ hermitian A ⟹ hermitian (herm_inv A)"
  unfolding herm_inv_def by (rule mat_fun_hermitian)

lemma mult_zero_vec_right: "B ∈ carrier_mat K n ⟹ B *v 0v n = 0v K"
  by (rule eq_vecI) (auto simp: scalar_prod_def)

text ‹For a unit vector $b$ and invertible $A$ the solution $A^{-1}b$ is not zero.›

lemma herm_inv_sol_pos:
  assumes A: "A ∈ carrier_mat n n" "hermitian A" and z: "0 ∉ herm_spectrum A" and b: "dim_vec b = n" "∥b∥ = 1"
  shows "0 < ∥herm_inv A *v b∥"
proof (rule vnorm_pos)
  have Hc: "herm_inv A ∈ carrier_mat n n" unfolding herm_inv_def by (rule mat_fun_carrier[OF A])
  thus "dim_vec (herm_inv A *v b) = n" by simp
  show "herm_inv A *v b ≠ 0v n"
  proof
    assume "herm_inv A *v b = 0v n"
    hence "b = 0v n" using herm_inv_solves[OF A z b(1)] mult_zero_vec_right[OF A(1)] by simp
    thus False using b(2) vnorm_zero_vec by simp
  qed
qed

end