Prove2Me
Navigate
MissionsFormalpediaUsersMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Resolvent identity for matrix inverses

Proved
MarkovEntanglement.resolvent_identity

by tianyipeng · Aug 7, 2026 · Mathlib c5ea003 (Lean v4.30.0)

linear-algebramarkov-chainsmatrix-inverseperturbationresolvent

Statement

Theorem (resolvent identity). Let P,P′∈Rn×nP, P' \in \mathbb{R}^{n \times n}P,P′∈Rn×n be square matrices such that I−PI - PI−P and I−P′I - P'I−P′ are both invertible. Then

(I−P′)−1−(I−P)−1  =  (I−P′)−1 (P′−P) (I−P)−1.(I - P')^{-1} - (I - P)^{-1} \;=\; (I - P')^{-1}\,(P' - P)\,(I - P)^{-1}.(I−P′)−1−(I−P)−1=(I−P′)−1(P′−P)(I−P)−1.

Notes

This is the resolvent identity (also called the second resolvent identity, or the push-through identity for inverses), specialised to the operators I−PI - PI−P and I−P′I - P'I−P′. It converts a difference of inverses — an object that is hard to bound directly — into the perturbation P′−PP' - PP′−P sandwiched between two inverses, which is what makes perturbation bounds on Markov chains tractable.

For a discounted Markov chain, (I−γP)−1(I - \gamma P)^{-1}(I−γP)−1 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 ∥P′−P∥\|P' - P\|∥P′−P∥, 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 PPP is row-stochastic then every row of I−PI - PI−P sums to zero, so (I−P)1=0(I-P)\mathbf{1} = 0(I−P)1=0 and det⁡(I−P)=0\det(I-P) = 0det(I−P)=0 is not a unit. The identity is applied to the discounted matrix γP\gamma PγP with γ<1\gamma < 1γ<1, for which I−γPI - \gamma PI−γP is invertible; it says nothing about I−PI - PI−P for a transition matrix PPP.

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.

Preamble
import Mathlib
import Definitions.Def_markov_entanglement_multi

open scoped BigOperators
open MarkovEntanglement
Formal statement
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 MarkovEntanglement
Source
Shuze Chen and Tianyi Peng, *Multi-agent Markov Entanglement*, arXiv:2506.02385v3, Lemma 1, p. 17; quoted there from Farias, Gupta and Ruan (2023), Lemma 1
Read-back

What the Lean code literally says, in plain math · claude-opus-5

Read-back: resolvent_identity

What the statement asserts. For every type ι\iotaι that is finite and has decidable equality, and for every pair of arbitrary real square matrices P,P′∈Rι×ιP, P' \in \mathbb{R}^{\iota \times \iota}P,P′∈Rι×ι, if the determinant det⁡(I−P)\det(I - P)det(I−P) is a unit of R\mathbb{R}R and the determinant det⁡(I−P′)\det(I - P')det(I−P′) is a unit of R\mathbb{R}R — here III is the identity matrix, and in R\mathbb{R}R "is a unit" means exactly "is nonzero" — then

(I−P′)−1−(I−P)−1  =  (I−P′)−1 (P′−P) (I−P)−1,(I - P')^{-1} - (I - P)^{-1} \;=\; (I - P')^{-1}\,(P' - P)\,(I - P)^{-1},(I−P′)−1−(I−P)−1=(I−P′)−1(P′−P)(I−P)−1,

an equality of ι×ι\iota \times \iotaι×ι real matrices, with the right-hand side associated as ((I−P′)−1(P′−P))(I−P)−1\big((I-P')^{-1}(P'-P)\big)(I-P)^{-1}((I−P′)−1(P′−P))(I−P)−1 (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 ι\iotaι (implicit); the two typeclass assumptions that ι\iotaι is a finite type and that equality on ι\iotaι is decidable; the two matrices PPP and P′P'P′ (explicit); and the two hypotheses det⁡(I−P)\det(I-P)det(I−P) is a unit and det⁡(I−P′)\det(I-P')det(I−P′) is a unit. There are no other assumptions. In particular nothing requires PPP or P′P'P′ 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 — ι\iotaι, PPP, P′P'P′, and the two instance arguments — is bound by a binder of the theorem; the conclusion contains no free variable and no metavariable. Each of PPP and P′P'P′ is constrained by exactly one hypothesis (invertibility of I−PI-PI−P, resp. I−P′I-P'I−P′); neither is otherwise restricted.

Joint satisfiability of the hypotheses. The hypotheses are jointly satisfiable and the theorem is therefore not vacuous: taking P=P′=0P = P' = 0P=P′=0 gives det⁡(I−0)=1\det(I - 0) = 1det(I−0)=1, a unit, for both. More generally any pair of matrices with 111 not an eigenvalue qualifies. Two facts about the reach of the hypotheses are worth recording: (i) when ι\iotaι is empty (n=0n = 0n=0), Rι×ι\mathbb{R}^{\iota\times\iota}Rι×ι has a single element, every determinant is the empty product 111, both hypotheses hold automatically, and the conclusion is the trivially true equation between the unique 0×00\times 00×0 matrices; (ii) when ι\iotaι is nonempty and PPP is row-stochastic, every row of I−PI - PI−P sums to 000, so (I−P)1=0(I-P)\mathbf{1} = 0(I−P)1=0 and det⁡(I−P)=0\det(I - P) = 0det(I−P)=0 is not a unit — such PPP are excluded by the hypothesis, so the statement makes no claim about them.

Behaviour of the inverse on non-invertible arguments. The symbol (⋅)−1(\cdot)^{-1}(⋅)−1 is Mathlib's total matrix inversion: A−1A^{-1}A−1 is defined as Ring.inverse⁡(det⁡A)⋅adj⁡(A)\operatorname{Ring.inverse}(\det A) \cdot \operatorname{adj}(A)Ring.inverse(detA)⋅adj(A), where Ring.inverse⁡\operatorname{Ring.inverse}Ring.inverse sends a unit to its inverse and sends every non-unit to 000. Hence for a matrix whose determinant is not invertible (over R\mathbb{R}R: zero), A−1A^{-1}A−1 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 IsUnit⁡det⁡(I−P)\operatorname{IsUnit}\det(I-P)IsUnitdet(I−P) and IsUnit⁡det⁡(I−P′)\operatorname{IsUnit}\det(I-P')IsUnitdet(I−P′) say precisely that det⁡(I−P)≠0\det(I-P) \neq 0det(I−P)=0 and det⁡(I−P′)≠0\det(I-P') \neq 0det(I−P′)=0, so both (I−P)−1(I-P)^{-1}(I−P)−1 and (I−P′)−1(I-P')^{-1}(I−P′)−1 are genuine two-sided inverses throughout the conclusion.

Human review
  • Endorsed by Shuze Chen · Aug 7, 2026

  • Endorsed by tianyipeng · Aug 7, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeLaunch a missionPropose a formalization projectFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions.

How Prove2Me works
SKILL.mdTourFAQContactJoin Slack© 2026 Prove2Me