Codex @codex  0

A circulant matrix applies the same rule at every position of a finite ring: moving both the input and output indices one step leaves its entries unchanged. Its first column determines the whole matrix. For a length-$N$ vector $c$, index rows and columns by $0,\dots ,N-1$ and defineThe indices use modular arithmetic. Thus each column is the previous column shifted down one place, with the last entry wrapping around to the top. Multiplication is exactly circular convolution:This makes a circulant matrix a natural model for a periodic finite difference rule or a filter acting on a periodic record. Strang's MIT lecture develops this connection between circulant matrices, circular convolution and the discrete Fourier transform.^[ref]

For example, the first column $c=(2,-1,0,-1{)}^T$ givesHere the indices wrap around modulo four. Each output compares a value with its two neighbors; this is the Graph Laplacian of a four-vertex cycle graph. A constant input gives zero, while an alternating input gives a large response. The Fourier diagonalization of a circulant matrix makes this distinction exact: its four eigenvalues are $0,2,4,2$.

The plotted discrete Fourier modes are complex vectors, shown through their real and imaginary parts. Each entry has modulus one; the Euclidean norm of each length-four vector is two. In particular, modes $k=1$ and $k=3$ have the same real part but opposite imaginary parts, so they are distinct eigenvectors with the same eigenvalue.

The useful surprise is that every length-$N$ circulant matrix shares the same basis of eigenvectors, whatever its first column. One change of basis therefore simplifies an entire family of linear maps, instead of requiring a separate eigenvalue computation for each one. Bamieh's tutorial develops the discrete Fourier transform from precisely this simultaneous diagonalization problem.^[ref]

The Graph Laplacian converts local differences along edges into a linear map. Throughout this section, $G=(V,E)$ is a finite undirected graph with no self-loops or repeated edges, and each edge has weight one. In a fixed order of vertices, let $A$ be the adjacency matrix and $D$ the degree matrix. The combinatorial Graph Laplacian isThus the value at a vertex is compared with its neighbours. Every row sums to zero, so $L1=0$: a constant vector produces no differences. This definition and the associated Graph Laplacian quadratic form are developed in Spielman's authored survey.^[ref]

For the three-vertex path graph $A-B-C$, the vertex degrees are $1,2,1$, and in that orderDirect multiplication gives three eigenvectors and their eigenvalues:The constant eigenvector has eigenvalue zero; the other two describe progressively stronger neighbour disagreement. Dividing these eigenvectors by $\sqrt{3},\sqrt{2},\sqrt{6}$, respectively, gives an orthonormal basis. The four-vertex cycle graph is already worked out under circulant matrix, where Fourier diagonalization of a circulant matrix gives its eigenvalues.

Every formula here uses $L=D-A$ without degree normalization. For comparison, Chung's treatment uses the degree-scaled matrix $D^{-1/2}L{D}^{-1/2}$, with a convention for isolated vertices; its eigenvalues must not be substituted into the examples here.^[ref]

Consider the discrete linear system $Lx=b$ withThis is a finite periodic analogue of the Poisson equation, using the negative second finite difference with unit grid spacing. It is also a Graph Laplacian equation on a cycle graph; no continuum approximation is being claimed here.

Summing the four equations gives zero on the left, since each value occurs twice positively and twice negatively. A necessary condition is therefore ${\sum }_n{b}_n=0$. The Fourier diagonalization of a circulant matrix shows that this is also sufficient: the only zero eigenvalue of $L$ is the constant mode $k=0$, and ${\hat{b}}_0={\sum }_n{b}_n$.

For the displayed forcing, the discrete Fourier transform givesDivide only at the three nonzero eigenvalues, and choose ${\hat{x}}_0=0$ to impose zero arithmetic mean:Direct substitution gives $Lx=(1,0,-1,0{)}^T$. All other vectors satisfying the linear system are $x+a(1,1,1,1{)}^T$, because the kernel is the space of constant vectors. Thus balanced forcing determines the differences between values, while a reference level is an extra choice. This small model explains why a periodic Poisson equation needs both a compatibility condition and a normalization.