cyclic_matrix_fourier
The two-dimensional unitary Fourier transform of a matrix M indexed by ZMod N has (m,n)-entry equal to (1/N) ∑_{x,y} M(x,y) exp(-2πi(mx+ny)/N).
Statement
noncomputable def cyclic_matrix_fourier (N : ℕ) [NeZero N] (M : Matrix (ZMod N) (ZMod N) ℂ) : Matrix (ZMod N) (ZMod N) ℂ
- Defined in
- arXiv:2610.31807 Section 3, Equation (3.1)
- Verified
- 26 Oct 2026
- Axioms
- none listed
- Used by 9
- cyclic_fourier_col_zero_eq_zero_of_sharpFor any weighted partial permutation matrix whose (0,0) entry is non-zero, every other entry (m,0) in the 0-th column is zero.
- order_eight_hankel_admits_sharp_cyclic_labelingAny simple graph on ZMod 8 whose adjacency is given by (x + y).val ∈ {1, 3, 5} admits a sharp cyclic labeling.
- circulant_graph_admits_sharp_cyclic_labelingFor every N ≥ 1 and every subset s of ZMod N, if the circulant graph SimpleGraph.circulantGraph s has at least one edge, then it admits a…
- is_sharp_cyclic_labelingA bijection π from ZMod N to the vertex set of a simple graph G is a sharp cyclic labeling if the two-dimensional Fourier transform of the…
- cyclic_matrix_fourier_zero_zero_ne_zeroFor any finite graph G with at least one edge and any bijection π : ZMod N ≃ V, the (0,0) entry of the cyclic 2D Fourier transform of the…
- sharp_cyclic_graph_is_regularEvery finite simple graph G with at least one edge that admits a sharp cyclic labeling on ZMod N is regular of some degree d.
- cyclic_matrix_fourier_compl_adjMatrixFor any simple graph G on ZMod N, the two-dimensional cyclic Fourier transform of the complement graph's adjacency matrix at (m,n) is…
- sharp_cyclic_and_compl_imp_antidiagonalIf G is a simple graph on ZMod N such that both G and its complement G^c have at least one edge, and the standard cyclic labeling is sharp…
- row_sum_eq_of_fourier_col_zero_vanishIf the cyclic 2D Fourier transform of M has vanishing entries at (m,0) for all m ≠ 0, then all row sums of M are equal.
Read back from the Lean
For a natural number $N$ satisfying $N \neq 0$ (via [NeZero N]) and a matrix $M$ with rows and columns indexed by $\mathbb{Z}/N\mathbb{Z}$ and entries in $\mathbb{C}$, cyclic_matrix_fourier N M is defined as the $(\mathbb{Z}/N\mathbb{Z}) \times (\mathbb{Z}/N\mathbb{Z})$ matrix over $\mathbb{C}$ whose entry at row $m$ and column $n$ is
$$\frac{1}{N} \sum_{x \in \mathbb{Z}/N\mathbb{Z}} \sum_{y \in \mathbb{Z}/N\mathbb{Z}} M_{x, y} \exp\left( -2 \pi i \frac{(m x + n y)\mathrm{.val}}{N} \right),$$
where $m x + n y$ is computed in the ring $\mathbb{Z}/N\mathbb{Z}$ and then converted via .val to a natural number in $\{0, \dots, N-1\}$ before being coerced to $\mathbb{C}$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Two-dimensional unitary Fourier transform of a matrix on ZMod N x ZMod N. -/ noncomputable def cyclic_matrix_fourier (N : ℕ) [NeZero N] (M : Matrix (ZMod N) (ZMod N) ℂ) : Matrix (ZMod N) (ZMod N) ℂ := Matrix.of fun m n => (1 / (N : ℂ)) * ∑ x : ZMod N, ∑ y : ZMod N, M x y * Complex.exp (-2 * Real.pi * Complex.I * ((m * x + n * y).val / (N : ℂ)))