Kronecker word
DefinitionSpencerEight_Supplement_worddiscrepancymatrix-spencerp2o-gran-per-chapterp2o-plan-bookp2o-v1random-matrices
A word of letters denotes the Kronecker product of its letters in the displayed order,
Every word is a signed permutation matrix; a word with an even number of letters is symmetric and squares to the identity.
Formalization Note Rows and columns are indexed by in the standard Kronecker order: an index is read in binary with digits, and the most significant digit belongs to the leftmost letter (the outermost factor). The entry is the product over of the entries of at the -th digits of the row and column indices.
Definition code
import Mathlib
import Definitions.Def_SpencerEight_Supplement_Letter
namespace SpencerEight.Supplement
/-- A word of `k` letters (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)): the Kronecker product
`L₁ ⊗ L₂ ⊗ ⋯ ⊗ L_k` of its letters in the displayed order, a real `2^k × 2^k` matrix.
**Formalization Note** Rows and columns are indexed by `Fin (2^k)` in the standard Kronecker order: the
index `i` is read in binary with `k` digits, the most significant digit belonging to the leftmost letter
`w 0` (the outermost factor). The entry at `(i, j)` is the product over `t` of the entries of the letter
`w t` at the `t`-th binary digits of `i` and `j`, which is the entry of the iterated Kronecker product. -/
def word {k : ℕ} (w : Fin k → Letter) : Matrix (Fin (2 ^ k)) (Fin (2 ^ k)) ℝ :=
fun i j => ∏ t : Fin k,
(w t).mat ⟨i.val / 2 ^ (k - 1 - t.val) % 2, Nat.mod_lt _ (by norm_num)⟩
⟨j.val / 2 ^ (k - 1 - t.val) % 2, Nat.mod_lt _ (by norm_num)⟩
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)