Resolvent identity for matrix inverses
ProvedMarkovEntanglement.resolvent_identityStatement
Theorem (resolvent identity). Let be square matrices such that and are both invertible. Then
Notes
This is the resolvent identity (also called the second resolvent identity, or the push-through identity for inverses), specialised to the operators and . It converts a difference of inverses — an object that is hard to bound directly — into the perturbation sandwiched between two inverses, which is what makes perturbation bounds on Markov chains tractable.
For a discounted Markov chain, is the resolvent whose entries are the discounted occupancy measures, so this identity is the standard first step in comparing the value functions of two chains whose transition matrices are close: bound , then propagate that bound through the two resolvents.
One caveat worth stating, because the naming invites the mistake: the hypotheses exclude transition matrices themselves. If is row-stochastic then every row of sums to zero, so and is not a unit. The identity is applied to the discounted matrix with , for which is invertible; it says nothing about for a transition matrix .
Mathlib carries Commute.inv_sub_inv for commuting elements of a group with zero, but
matrices do not commute in general and the identity above holds without any commutation
hypothesis, so it is stated here in the form actually needed. The statement is generic
in the index type and does not mention Markov chains, so it is reusable for any
perturbation argument about matrix inverses.
import Mathlib import Definitions.Def_markov_entanglement_multi open scoped BigOperators open MarkovEntanglement
namespace MarkovEntanglement
theorem resolvent_identity {ι : Type*} [Fintype ι] [DecidableEq ι]
(P P' : Matrix ι ι ℝ) (hP : IsUnit (1 - P).det) (hP' : IsUnit (1 - P').det) :
(1 - P')⁻¹ - (1 - P)⁻¹ = (1 - P')⁻¹ * (P' - P) * (1 - P)⁻¹ := by
sorry
end MarkovEntanglementRead-back
What the Lean code literally says, in plain math · claude-opus-5
Read-back: resolvent_identity
What the statement asserts. For every type that is finite and has decidable equality, and for every pair of arbitrary real square matrices , if the determinant is a unit of and the determinant is a unit of — here is the identity matrix, and in "is a unit" means exactly "is nonzero" — then
an equality of real matrices, with the right-hand side associated as (matrix multiplication is associative, so the grouping is immaterial). Subtraction on both sides is entrywise matrix subtraction.
Binders and hypotheses, in full. The declaration quantifies over: the index type (implicit); the two typeclass assumptions that is a finite type and that equality on is decidable; the two matrices and (explicit); and the two hypotheses is a unit and is a unit. There are no other assumptions. In particular nothing requires or to be stochastic, nonnegative, symmetric, substochastic, or related to one another in any way, and no hypothesis about spectral radius, norms, or a discount factor appears.
Constrained vs. free variables in the conclusion. Every variable occurring in the conclusion — , , , and the two instance arguments — is bound by a binder of the theorem; the conclusion contains no free variable and no metavariable. Each of and is constrained by exactly one hypothesis (invertibility of , resp. ); neither is otherwise restricted.
Joint satisfiability of the hypotheses. The hypotheses are jointly satisfiable and the theorem is therefore not vacuous: taking gives , a unit, for both. More generally any pair of matrices with not an eigenvalue qualifies. Two facts about the reach of the hypotheses are worth recording: (i) when is empty (), has a single element, every determinant is the empty product , both hypotheses hold automatically, and the conclusion is the trivially true equation between the unique matrices; (ii) when is nonempty and is row-stochastic, every row of sums to , so and is not a unit — such are excluded by the hypothesis, so the statement makes no claim about them.
Behaviour of the inverse on non-invertible arguments. The symbol is Mathlib's total matrix inversion: is defined as , where sends a unit to its inverse and sends every non-unit to . Hence for a matrix whose determinant is not invertible (over : zero), is the zero matrix, not an error and not an undefined value; the operation is total and returns this junk value silently. In this statement that degenerate branch is explicitly ruled out for both inverted matrices: the hypotheses and say precisely that and , so both and are genuine two-sided inverses throughout the conclusion.
Confirmed by the mission captain (proposal self-audit).