Predicting Diagonalizability of a Mean Matrix

Abstract

Wu and Santhanam asked whether one can determine, from an increasing i.i.d. sample of binary random matrices, whether the unknown mean matrix is diagonalizable while making only finitely many errors almost surely. We answer this question affirmatively, for diagonalizability over either $\mathbb{R}$ or $\mathbb{C}$. The main observation is a general principle: every semialgebraic property of a fixed-dimensional bounded mean parameter is eventually almost surely predictable. We give a self-contained shrinking-confidence-set proof and an explicit predictor obtained from polynomial sign tests. Tarski--Seidenberg quantifier elimination shows that both the real- and complex-diagonalizable loci are semialgebraic, despite being neither closed nor open. We further extend the positive result to unbounded observations with any fixed finite moment of order $r>1$, using the Marcinkiewicz--Zygmund strong law. Combined with the Dembo--Peres topological criterion, this yields a sharp contrast: over the class of all merely integrable matrix laws, diagonalizability is not eventually almost surely predictable when the dimension is at least two. The construction is effective for fixed dimension, although no practical complexity bound is claimed.

Disclosure

“ties, deriving useful finite-sample error profiles away from algebraic boundaries, and identifying subclasses for which the predictor can be implemented efficiently. 8 Disclosure The proof strategy and counterexample were produced by OpenAI’s GPT-5.6 Sol Ultra through Codex in response to prompts from the author. Codex was also used to revise the exposition and prepare the LaTeX manuscript. The author selected the problem, directed the interactions and”

PDF page 8

Classification

Substantial mathematical content or result generation

Multiplier

10

Verified

2026-08-23T05:08:50.306495Z

Structural counts