2026/07/21 by Matthew J. Colbrook
#math.NA #cs.NA
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×2 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.