cyclic_fourier_col_zero_eq_zero_of_sharp
For any weighted partial permutation matrix whose (0,0) entry is non-zero, every other entry (m,0) in the 0-th column is zero.
Statement
theorem cyclic_fourier_col_zero_eq_zero_of_sharp (N : ℕ) [NeZero N]
(M : Matrix (ZMod N) (ZMod N) ℂ) (hs : is_weighted_partial_permutation (cyclic_matrix_fourier N M))
(h0 : cyclic_matrix_fourier N M 0 0 ≠ 0) (m : ZMod N) (hm : m ≠ 0) :
cyclic_matrix_fourier N M m 0 = 0- Source
- step towards sharp_cyclic_graph_is_regular
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- is_weighted_partial_permutationA square complex matrix M is a weighted partial permutation matrix if for every row index i, any two column indices with nonzero entries…
- cyclic_matrix_fourierThe 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)…
- Used by 1
- 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.
The proof, explained
The result is proved by contradiction. By definition, each column of a weighted partial permutation matrix contains at most one non-zero entry. Assuming for contradiction that the $(m, 0)$ entry is non-zero alongside the non-zero $(0, 0)$ entry forces their row indices to coincide, giving $m = 0$ and contradicting the hypothesis $m \neq 0$.
The entry of the Fourier transform matrix at $(m, 0)$ is zero.
We argue by contradiction: suppose that the $(m, 0)$ entry is non-zero. By definition, a weighted partial permutation matrix has at most one non-zero entry in each column (`hs.2`). Because both $(0, 0)$ and $(m, 0)$ belong to column $0$ and are non-zero, their row indices must coincide, giving $0 = m$ and hence $m = 0$. This directly contradicts the hypothesis that $m \neq 0$ (`hm`).
by_contra h exact hm (hs.2 0 0 m h0 h).symm
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- If the 2D Fourier transform is a weighted partial permutation matrix and entry (0,0) is nonzero, then all other entries (m,0) with m ≠ 0 in the 0-th column must vanish. -/theorem cyclic_fourier_col_zero_eq_zero_of_sharp (N : ℕ) [NeZero N] (M : Matrix (ZMod N) (ZMod N) ℂ) (hs : is_weighted_partial_permutation (cyclic_matrix_fourier N M)) (h0 : cyclic_matrix_fourier N M 0 0 ≠ 0) (m : ZMod N) (hm : m ≠ 0) : cyclic_matrix_fourier N M m 0 = 0 := by by_contra h exact hm (hs.2 0 0 m h0 h).symm