The letters
DefinitionSpencerEight_Supplement_Letterdiscrepancymatrix-spencerp2o-gran-per-chapterp2o-plan-bookp2o-v1random-matrices
The four letters of Section 15.2 are the real matrices
are symmetric; is antisymmetric with .
Formalization Note An inductive type of four letters together with its matrix map Letter.mat.
Definition code
import Mathlib namespace SpencerEight.Supplement /-- The four letters `I, X, Z, J` of Section 15.2 (Song, Zhang, *Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense Input*, arXiv:2609.15025 (held version, sha256 9ccbcdb8…), p.289 (PDF p.289)). -/ inductive Letter where | I | X | Z | J deriving DecidableEq /-- The `2 × 2` real matrix of a letter (Section 15.2, p.289): `I = [[1,0],[0,1]]`, `X = [[0,1],[1,0]]`, `Z = [[1,0],[0,−1]]`, `J = [[0,1],[−1,0]]` (`J` is antisymmetric, `J² = −I`). -/ def Letter.mat : Letter → Matrix (Fin 2) (Fin 2) ℝ | .I => !![1, 0; 0, 1] | .X => !![0, 1; 1, 0] | .Z => !![1, 0; 0, -1] | .J => !![0, 1; -1, 0] end SpencerEight.Supplement
Source
Song, Zhang, Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense Input, arXiv:2609.15025 (held version, sha256 9ccbcdb8…), Section 15.2, p.289 (PDF p.289)