Nyström Error Beyond $M$-Matrices: A Minimal Diagonally Dominant Obstruction

Abstract

We study the nuclear-norm error of a column-selected Nyström approximation to $K=(L+γI)^{-1}$, where $L$ is symmetric diagonally dominant and $γ>0$. Our central question is whether this error has diminishing returns. A Schur-complement identity reduces the question to traces of inverses of principal submatrices. Existing $M$-matrix results settle the case in which $L$ is a symmetric diagonally dominant $M$-matrix (SDDM). However, diagonal dominance alone is not enough: failure occurs already in dimension three. We construct an exact one-parameter SDD family and determine its sharp failure interval. A $2\times2$ identity proves that dimension three is minimal within the SDD class. We then show that failure persists under strict diagonal dominance; with a nonempty selected base set, dimension four is minimal. Finally, we prove invariance under signature switching, derive a three-dimensional formula showing how a signed triangle causes failure, and give an example in which greedy column selection misses the optimal pair. Together, these findings complete the answer to Problem 4.6 in a recent Simons workshop report.

Disclosure

“re would provide a quantitative substitute for the exact property ruled out by our examples. AI declaration. Consistent with the Leiden Declaration on Artificial Intelligence and journal policy, we disclose all use of AI in this paper. An AI system was used as an initial search aid that suggested L0 , and subsequently for minor language editing and independent proofreading checks. No AI was used to produce the mathematical arguments or paper content. The author takes full responsibil”

PDF page 10

Classification

Rewriting existing author-written text

Multiplier

4

Verified

2026-08-23T19:02:19.685607Z

Structural counts