The Big Picture for Z_N

In this chapter

9The DFT Matrix and Spectral Filtering
10Three Isomorphic Algebras
11Why Everything Worked
12What Will Break on Graphs

9The DFT Matrix and Spectral Filtering

In the previous chapter we derived the eigenvectors of the shift operator $S$ — the columns of the DFT matrix. Now we assemble the full picture: the DFT as a matrix, and the spectral filtering recipe that makes convolution diagonal.

Recall from §7 that $S^*$ has eigenvalues $\rho_m = e^{i2\pi m/N}$ (Eq. 11). The DFT matrix $W$ has entries:

Eq. 15 — DFT Matrix $$ W_{mk} \;=\; e^{-i\,2\pi mk/N} \;=\; \rho_m^{-k}, \qquad m,k = 0,1,\ldots,N-1 \tag{15} $$

The row index $m$ labels the frequency and the column index $k$ labels the position. Each row of $W$ is a complex sinusoid at frequency $m$, sampled at positions $k = 0, \ldots, N-1$. Since the rows are orthogonal with $\langle w_m, w_{m'}\rangle = N\,\delta_{mm'}$, we have $W^*W = NI$. The inverse is therefore:

Eq. 16 — Inverse DFT $$ W^{-1} = \tfrac{1}{N}\,W^*, \qquad (W^{-1})_{km} = \tfrac{1}{N}\,\rho_m^{\,k} \tag{16} $$

This convention matches Eq. 13 directly: $\hat{x}_m = (Wx)_m = \sum_k x_k\,e^{-i2\pi mk/N}$. Some texts place a $1/\sqrt{N}$ factor in both $W$ and $W^{-1}$ (the “unitary” convention, making $W^{-1} = W^*$). We use the form above because it keeps the convolution theorem clean: $\widehat{h * x} = \hat{h} \cdot \hat{x}$ with no stray factors of $N$.

Now recall the fundamental result from Chapter 2: every circulant matrix $C_h$ is diagonalized by $W$. This means convolution with any filter $h$ can be performed in three steps:

The Spectral Filtering Recipe

To compute $y = h * x$ (circular convolution of filter $h$ with signal $x$):

Transform: $\hat{x} = Wx$ — decompose the signal into frequency components.
Multiply: $\hat{y}_m = \hat{h}_m \cdot \hat{x}_m$ for each $m$ — scale each frequency independently.
Invert: $y = W^{-1}\hat{y}$ — reconstruct the filtered signal.

In matrix notation, step 2 is multiplication by a diagonal matrix $\operatorname{diag}(\hat{h})$, so the entire pipeline collapses to:

Eq. 17 — Spectral Filtering Formula $$ y \;=\; W^{-1}\,\operatorname{diag}(\hat{h})\; W\, x \;=\; C_h\, x \tag{17} $$

This is the convolution theorem in matrix form. The circulant $C_h$ factors as $W^{-1}\operatorname{diag}(\hat{h})\,W$: conjugate into the frequency domain, apply a diagonal scaling, conjugate back. Convolution in the spatial domain is pointwise multiplication in the frequency domain.

Figure 3.1. The spectral filtering pipeline. A signal $x$ is transformed by the DFT matrix $W$, multiplied pointwise by the filter’s spectrum $\hat{h}$, then transformed back by $W^{-1}$. The result is identical to circular convolution $h * x$.

Why this matters for graphs: The spectral filtering formula $y = W^{-1}\operatorname{diag}(\hat{h})\,Wx$ does not mention the group $\ZN$ at all. It only requires an eigenbasis $W$ and a set of spectral multipliers $\hat{h}$. This is the formula that will generalize to graphs — we will simply replace $W$ with the eigenvectors of the graph Laplacian.

10Three Isomorphic Algebras

We have been building three different descriptions of the same mathematical object. Now we state the precise relationship. The following theorem is the capstone of the $\ZN$ story.

Theorem 5.1 (Bamieh) — Three Isomorphic Algebras

The following three sets, each equipped with their natural operations, are isomorphic as algebras:

Circulant matrices $\{C_h : h \in \C^N\}$ — the set of all $N \times N$ circulant matrices, with matrix multiplication.
Convolution sequences $(\C^N, *)$ — the set of all $N$-vectors, with circular convolution as multiplication.
Spectral multipliers $\{\operatorname{diag}(\hat{h}) : \hat{h} \in \C^N\}$ — diagonal matrices in the DFT basis, with matrix multiplication (= pointwise multiplication of spectra).

The word “isomorphic” means there are bijective maps between these three sets that preserve addition and multiplication. In concrete terms:

Embedding: $h \;\leftrightarrow\; C_h$ — any vector $h$ can be embedded as the first column of a circulant matrix, and conversely any circulant is determined by its first column.
Fourier transform: $h \;\leftrightarrow\; \hat{h} = Wh$ — the DFT maps convolution sequences to spectral multipliers.
Diagonalization: $C_h \;\leftrightarrow\; \operatorname{diag}(\hat{h})$ via $C_h = W^{-1}\operatorname{diag}(\hat{h})\,W$ — the DFT diagonalizes every circulant.

Eq. 18 — The Isomorphism $$ \underbrace{\{C_h\}}_{\text{Circulant matrices}} \;\cong\; \underbrace{(\C^N, *)}_{\text{Convolution sequences}} \;\cong\; \underbrace{\{\operatorname{diag}(\hat{h})\}}_{\text{Spectral multipliers}} \tag{18} $$

The isomorphism means that any statement about one algebra translates directly into a statement about the others. Convolution of two sequences $h * g$ corresponds to multiplication of two circulants $C_h C_g = C_{h*g}$, which corresponds to pointwise multiplication of spectra $\hat{h} \cdot \hat{g} = \widehat{h*g}$. The three viewpoints are three windows onto a single algebraic structure.

Figure 3.2. The commutative triangle of the three isomorphic algebras. Any path between two vertices gives the same result: embedding then diagonalizing is the same as taking the DFT then forming the diagonal. This is Bamieh’s Theorem 5.1.

11Why Everything Worked

Before we move to graphs, it is worth pausing to ask: why was the $\ZN$ story so clean? Two features of the ring made everything lock together.

What Made Z_N Special

Symmetry. $\ZN$ is a cyclic group that acts transitively on its vertices by translation: every vertex “looks the same.” This gives a canonical shift operator $S$ (the generator), a natural notion of translation invariance, and a unique definition of convolution (linear operators that commute with $S$). There is no ambiguity — the group hands us everything.
Distinct eigenvalues. $S$ has $N$ distinct eigenvalues — the $N$th roots of unity (Eq. 11). Because all eigenvalues are distinct, each eigenspace is one-dimensional and the eigenbasis is unique (up to scalar multiples). This is why the DFT was forced on us in §7.

Eq. 19 — Distinct Eigenvalues $$ |\operatorname{spectrum}(S)| = N \quad\text{(all eigenvalues distinct)} \tag{19} $$

Together these two properties made the commutant theorem especially powerful: the set of matrices that commute with $S$ is exactly the set of polynomials in $S$, which is exactly the set of circulant matrices. The group-theoretic, algebraic, and spectral characterizations of convolution all coincide because of this.

The logical chain:

Cyclic group symmetry $\Rightarrow$ a canonical shift $S$ and a unique notion of convolution.
Distinct eigenvalues of $S$ $\Rightarrow$ a unique eigenbasis (the DFT), and all three characterizations coincide.

The punchline: On $\ZN$, group symmetry gave us the operator, and spectral distinctness gave us the eigenbasis. Both were essentially unique. On graphs, neither will be.

12What Will Break on Graphs

Now we preview Part II of the course. Consider an arbitrary undirected graph — a social network, a molecule, a finite-element mesh. Moving from $\ZN$ to a general graph is not simply a matter of losing properties — we are entering a genuinely different mathematical setting where some ideas carry over, some mutate, and some are replaced by new ones.

No symmetry group. An irregular graph has no translation symmetry. Vertex 0 might have degree 5 while vertex 1 has degree 2 — they are fundamentally different. With no group, the group-theoretic definition of convolution does not apply, and there is no canonical “shift” operator handed to us for free.

Operator by choice. In place of $S$, we choose a graph operator — the Laplacian $L$, the adjacency matrix $A$, or the normalized Laplacian $\tilde{L}$. Different choices lead to different eigenbases and different notions of convolution. This is a design decision, not a theorem.

Eigenvalue collisions. Real symmetric matrices like $L$ and $A$ can have repeated eigenvalues. When they do, the corresponding eigenspace is multi-dimensional: any orthonormal basis for that eigenspace works equally well, so the eigenbasis is no longer unique.

Despite all this, not everything is lost. The table below compares the $\ZN$ and graph settings across several dimensions:

Property	Z_N	General Graph
Symmetry group	✓ Z_N acts transitively	✗ No transitive group
Canonical operator	✓ Shift S (unique)	✗ Must choose (L, A, …)
Distinct eigenvalues	✓ (roots of unity)	Often ✗ (repeated)
Algebraic char. (poly in operator)	✓	✓
Spectral char. (diagonal in eigenbasis)	✓	✓
Group-theoretic char.	✓ Commute with group action	✗ No group to commute with

Eq. 20 — What Survives $$ \underbrace{p(L) = \theta_0 I + \theta_1 L + \cdots + \theta_d L^d}_{\text{Algebraic: polynomial in }L} \qquad\longleftrightarrow\qquad \underbrace{U\,\operatorname{diag}(\hat{h})\,U^T\,x}_{\text{Spectral: diagonal in eigenbasis}} \tag{20} $$

The key takeaway: the algebraic and spectral characterizations both survive the move to graphs. We can always form polynomials in a matrix, and any real symmetric matrix has a complete orthonormal eigenbasis (even with repeated eigenvalues, we can always choose one). What we lose is the group-theoretic characterization — and with it, the guarantee that all three viewpoints describe the same set of operators.

Subtlety ahead: On $\ZN$, the algebraic and spectral characterizations define the same set of operators. On graphs with repeated eigenvalues, the spectral class is strictly larger than the polynomial class. There exist spectral multipliers that are not polynomials in $L$. This gap will become important in Chapter 5 when we compare spectral and polynomial graph convolutions.

With this roadmap in hand, we are ready to leave the comfort of $\ZN$ and step onto general graphs. In the next chapter, we begin by symmetrizing the shift operator (forming $A = S + S^*$), see eigenvalue collapse in action, introduce the graph Laplacian $L$, and verify which characterizations survive.