Exact Spectral Certificates and Ordering Geometry for Overlapping Block Matrix Inversion

Abstract Iterative block matrix inversion (IBMI) approximates the inverse of a symmetric positive definite matrix through ordered block-inverse updates. We establish an exact pre-iteration certificate for the asymptotic convergence factor of the full inverse-error iteration. Each block update induces an energy-orthogonal projection, and a complete sweep admits a reduced cyclic return representation whose spectral radius determines the inverse-error factor. We show that the return matrix can be constructed entirely from the original matrix A through local principal-block solves, yielding the exact factor ρ(MA) 2 without forming A -1 or executing an IBMI sweep. The return framework provides finite-termination criteria, perturbation bounds, and a first-order sensitivity formula under a simple dominant-eigenvalue condition. For two update blocks, nested enlargement cannot increase the exact convergence factor; an explicit rational SPD counterexample shows that this monotonicity fails for three blocks. Nevertheless, a monotone canonical-correlation envelope holds for arbitrary block counts, with a quantitative condition-number contraction bound for separated adjacent complements. For singleton complements, the exact factor reduces to a weighted Hamiltonian-cycle product of inverse couplings. This characterization yields exact local ordering comparisons, an NP-hardness result for unrestricted SPD instances, and an explicit globally optimal ordering for exponential-line coupling structures. Numerical experiments on covariance models, public sparse SPD matrices, and controlled ordering instances confirm the spectral identities to numerical accuracy and demonstrate the matrix-dependent effects of overlap and ordering.