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 ≠ 0⇩v n"
shows "0 < ∥v∥"
proof -
obtain i where i: "i < n" "v $ i ≠ 0"
proof (rule ccontr)
assume "¬ thesis"
hence "v = 0⇩v 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: "∥0⇩v 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 = 1⇩m ?n" and r: "A * (A⇧†) = 1⇩m ?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 = 1⇩m n" "A * (A⇧†) = 1⇩m n" "B⇧† * B = 1⇩m n" "B * (B⇧†) = 1⇩m 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 = 1⇩m 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 = 1⇩m n" "U * (U⇧†) = 1⇩m 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 = 1⇩m n" and UU': "U * (U⇧†) = 1⇩m 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 ≠ 0⇩v (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 ≠ 0⇩v n"
proof
assume z: "Matrix.col U j = 0⇩v 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 = 0⇩v (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 1⇩m n"
proof (rule mat_fun_eqI[OF A])
show "c ⋅⇩m 1⇩m 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 "1⇩m n" n n])
qed simp
lemma mat_fun_one: "A ∈ carrier_mat n n ⟹ hermitian A ⟹ mat_fun (λ_. 1) A = 1⇩m 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 = 1⇩m n" "mat_fun (λx. g x * cnj (g x)) A = 1⇩m 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 = 1⇩m 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 = 1⇩m 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 (1⇩m ?n) D"
unfolding spectral_decomp_def using Ac by (simp add: id_is_unitary)
have "mat_fun g ?A = (1⇩m ?n * diag_matrix (map g D)) * ((1⇩m ?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 = 1⇩m 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 = 1⇩m n" "A * herm_inv A = 1⇩m 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 = 1⇩m n" "A * herm_inv A = 1⇩m 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 = 1⇩m 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 0⇩v n = 0⇩v 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 ≠ 0⇩v n"
proof
assume "herm_inv A *⇩v b = 0⇩v n"
hence "b = 0⇩v 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