The Wonderful World of Mathematical Transformations

A second look at one generating function

In the first blackboard problem from Good Will Hunting, powers of an adjacency matrix count walks through a graph. If \(A\) is the matrix, then \((A^n)_{ij}\) counts the length-\(n\) walks from vertex \(i\) to vertex \(j\). Instead of keeping those answers in an endless list, we place them into one matrix-valued power series:

The companion article, Revisiting the First Blackboard Problem in Good Will Hunting, derives this identity from the four tasks shown in the film and carefully distinguishes \(G(t)\) from its scalar entry

Here I want to follow the idea further. The essential move is not peculiar to graphs: represent a sequence by a function, a linear evolution by its modes, or a signal by coefficients in a different basis. In the right representation, a shift can become multiplication, a recurrence can become a rational denominator, and a complicated object can reveal that most of its energy—or most of what we care about—lives in only a few directions.

That last phrase needs care. A transform can reveal the possibility of compression, but it does not compress anything merely by existing. An invertible change of coordinates preserves all the information and normally preserves the number of coefficients as well. Compression begins only when we encode those coefficients more economically or decide that some of them can be discarded or approximated.

From a sequence to a function

Suppose a scalar sequence \(x_0,x_1,x_2,\ldots\) has the ordinary generating function

The unilateral Z-transform of the same one-sided sequence is conventionally written

The two expressions contain the same coefficients in reciprocal variables:

As an identity of formal series, this is simply the substitution \(z=1/t\). Analytically, it also maps convergence regions. If the power series for \(G_x\) has radius \(R\), then the corresponding exterior part of the Z-transform converges for \(|z|>1/R\). Boundary points require separate examination; a radius of convergence alone does not say what happens there.

For the matrix sequence \(A^n\), the same substitution gives

The Neumann series converges for \(|z|>\rho(A)\), equivalently \(|t|<1/\rho(A)\), where \(\rho(A)\) is the largest absolute value of an eigenvalue. The inverse itself may be evaluated at many points outside the series’ original domain, but that rational continuation should not be confused with convergence of the defining infinite sum.

This distinction is concrete in the film’s graph. Its walk counts grow, so substituting \(t=1\) into the formal generating function does not produce the sum of all walks as a finite number. The rational expression \((I-tA)^{-1}\) and the convergent power series agree near \(t=0\); elsewhere the rational function can continue past points where the original sum no longer converges, except at its poles.

Recurrences hiding inside rational functions

Why is a rational function so useful? Because multiplication by \(t\) shifts coefficients. If

satisfies

then, after the finitely many coefficients affected by the polynomial \(q\), coefficient comparison yields

The denominator is a compact description of a recurrence. Conversely, a constant-coefficient linear recurrence leads to a rational generating function once its initial values are supplied.

For walks from vertex 1 to vertex 3 in the film’s graph, the scalar entry simplifies to

Its coefficients obey

with the initial coefficients interpreted through the displayed identity. An infinite list has not disappeared; it has become reproducible from a finite rule and initial data.

The same object as a dynamical system

Now read \(A\) not only as an adjacency matrix but as a state-transition matrix. In a discrete-time autonomous system,

the state after \(n\) steps is

Its unilateral Z-transform is therefore

where the series converges outside the system’s spectral radius. The same resolvent that is related to the graph-walk generating function now describes repeated state evolution.

Inputs and observations add two maps. For

the zero-initial-state transfer function is

This formula is indexed slightly differently from \(\sum_{n\geq0}A^nz^{-n}\): its strictly dynamic impulse-response terms are \(CA^{n-1}B\) for \(n\geq1\). Keeping track of that one-step shift prevents an attractive analogy from becoming an incorrect identity.

The common structure is the resolvent. It answers a family of questions at once: how repeated transitions accumulate, how an input excites internal states, and how those states appear at an output.

Eigenvalues turn evolution into modes

If \(A\) is diagonalizable, write

Then

In the eigenvector coordinates \(V^{-1}x\), the coupled matrix evolution becomes a collection of scalar evolutions. Each eigenvalue \(\lambda_k\) contributes a factor \(\lambda_k^n\) in time and a factor

to the generating-function resolvent. In the Z-plane, the corresponding form is \(z/(z-\lambda_k)\). Eigenvalues therefore appear as poles: at \(t=1/\lambda_k\) in the generating-function variable and at \(z=\lambda_k\) in the Z-transform variable.

There are qualifications. Repeated eigenvalues can produce higher-order behavior when a matrix is not diagonalizable. And a particular scalar quantity such as \(e_i^{\mathsf T}(I-tA)^{-1}e_j\) need not display every pole of the full matrix resolvent: its numerator may cancel a factor when that input-output pair does not excite or observe a mode. This is exactly what happens when the film’s \(g_{13}(t)\) reduces from a fourth-degree common denominator to a third-degree one.

For a real symmetric matrix, the spectral theorem gives the especially clean form

where the columns \(q_k\) of \(Q\) are orthonormal. Then

Each rank-one matrix \(q_kq_k^{\mathsf T}\) projects onto one eigenmode. What looked like repeated matrix multiplication becomes independent amplification or decay along orthogonal directions.

Cayley–Hamilton: why finitely many powers suffice

The eigenmode picture has an algebraic companion. If

is the characteristic polynomial, the Cayley–Hamilton theorem says

For an \(m\times m\) matrix this expresses \(A^m\) as a combination of lower powers. Multiplying by further powers of \(A\) generates a recurrence for the entire matrix sequence. Every scalar sequence \(u^{\mathsf T}A^nv\) consequently obeys a recurrence whose characteristic polynomial divides a polynomial associated with \(A\); the minimal polynomial often gives a shorter recurrence than the full characteristic polynomial.

For the four-vertex adjacency matrix in the film,

so

The determinant in the matrix generating function is the reciprocal characteristic polynomial:

Recurrence, characteristic polynomial, eigenvalues and poles are not separate tricks. They are different views of the same finite-dimensional structure.

When the Z-transform meets Fourier analysis

For a sufficiently summable sequence \(x_n\), evaluating its Z-transform on the unit circle, \(z=e^{i\omega}\), gives the discrete-time Fourier transform

For a one-sided sequence we set \(x_n=0\) for \(n<0\). The unit circle must lie in a suitable convergence region; otherwise the displayed series is not an ordinary convergent Fourier transform. Graph-walk counts generally grow too quickly for that. One can instead introduce damping and study

choosing \(r\) inside the radius of convergence. This is a Fourier analysis of the damped sequence, not a license to ignore divergence at \(r=1\).

When \(x\in\ell^2(\mathbb Z)\), Parseval’s identity states, with this normalization,

The sequence index \(n\) is a time—or walk-length—index, while \(\omega\) is a temporal frequency. This must not be mixed up with a different decomposition that also appears nearby. For a graph signal \(f\), the coefficients

are indexed by the graph eigenmode \(k\), not by the time-frequency variable \(\omega\). Because \(Q\) is orthogonal,

In graph signal processing, the graph Laplacian is commonly used to define spatial frequencies through its eigenvectors and eigenvalues. The adjacency matrix also admits a spectral decomposition when it is symmetric, but adjacency eigenvalues do not in general have the same interpretation as Laplacian frequencies.

Both formulas are Parseval-type norm identities arising from orthonormal representations. Their indices describe different axes: one decomposes variation along a sequence, the other decomposes a signal across the vertices of a particular graph. A time-varying graph signal can have both indices, but naming them separately is then more—not less—important.

SVD and PCA: directions chosen for the data

Fourier modes are fixed by translation and graph modes by a chosen operator such as an adjacency matrix or Laplacian. The singular value decomposition starts instead from the data matrix itself. For

the singular vectors provide orthonormal input and output directions, and the singular values

measure how strongly those paired directions are represented.

Keeping every singular triplet is an exact change of representation, apart from numerical roundoff. Keeping only the first \(r\) produces the rank-\(r\) approximation

The Eckart–Young–Mirsky theorem makes the loss precise: among all rank-\(r\) matrices, \(M_r\) minimizes both the spectral norm and Frobenius norm of the reconstruction error. In particular,

PCA applies the same geometry to centered observations. Its leading principal directions maximize captured sample variance, and projection onto the first \(r\) directions minimizes squared reconstruction error among \(r\)-dimensional linear subspaces. “Best” here has a defined metric and a defined dataset. PCA does not promise to preserve every rare event, causal feature or physically important small-amplitude component.

A rank-\(r\) SVD approximation is not automatically a saving in storage. In a straightforward dense factor representation, storing \(U_r\), the \(r\) singular values and \(V_r\) takes approximately \(r(m+n+1)\) numbers for an \(m\times n\) matrix, compared with \(mn\) entries in the original. Compression in bits additionally depends on quantization, encoding and any overhead from storing the factors.

This is a crucial difference from diagonalizing a known dynamics matrix. Eigenvectors of \(A\) reveal modes of the operator; PCA directions reveal variance in observed data. They may coincide in special models, but there is no general reason they must.

Why wavelets sometimes see what Fourier modes miss

A sinusoidal Fourier basis is global: each basis function extends across the entire domain. That is excellent for persistent frequencies but less natural for sharp, localized events. Wavelets use functions localized in both position and scale. A wavelet transform can therefore represent smooth regions coarsely while concentrating edges, transients or singularities into relatively few significant coefficients.

Again, the transform itself is not the compression. An orthonormal wavelet transform maps \(N\) samples to \(N\) coefficients and is invertible. Compression becomes possible when many coefficients are small enough to quantize heavily, encode cheaply or set to zero. The usefulness of the representation depends on the structure of the signal: piecewise-smooth data often become sparse in a wavelet basis, whereas a pure stationary tone is more naturally sparse in a Fourier basis.

Wavelets are therefore not a decorative extra member of a transform catalogue. They make a specific point: no representation is universally simplest. Locality, scale and the expected features of the object should influence the basis we choose.

Transformation is not compression

It helps to separate three claims that are often blended together.

First, invertibility asks whether the original object can be reconstructed exactly from all transformed coefficients. Orthogonal Fourier, eigenvector and wavelet transforms are invertible under their stated assumptions; a full SVD is an exact factorization.

Second, storage asks how those coefficients are represented. An invertible transform usually leaves the coefficient count unchanged, and storing a learned basis may cost additional space. Exact compression requires exploitable structure in the representation and an encoding scheme that uses fewer bits—perhaps repeated values, predictable symbols or exact sparsity.

Third, lossy reduction deliberately replaces the original by an approximation. We may truncate singular values, project onto selected modes, threshold wavelet coefficients or quantize values. The reduced description can be much smaller, but reconstruction is no longer exact.

For an orthonormal basis \(\{q_k\}\), if we retain an index set \(S\), then

and Parseval gives the exact squared error

That formula tells us how much energy was discarded. It does not by itself tell us whether the loss is acceptable. A weak spectral line may encode a fault in a machine; a small image component may delineate a tumor; a brief transient may be the event an experiment was designed to detect. Physically relevant preservation may require weighted errors, constraints, feature-specific tests or validation on the downstream task—not just a high percentage of retained variance or energy.

One habit of thought, many representations

Generating functions, Z-transforms, eigendecompositions, Fourier series, SVD, PCA and wavelets do not all solve the same problem. Their commonality is more modest and more useful: each offers a representation in which a chosen structure may become easier to see. Not all of these operations are simply changes of coordinates, and not all have inverses.

For the graph in Good Will Hunting, the list of walk counts becomes a rational function. In state-space language, the matrix generating function is closely related to a resolvent: for \(t\neq0\), \((I-tA)^{-1}=t^{-1}(t^{-1}I-A)^{-1}\). In eigenvector coordinates, repeated evolution separates into modes. Cayley–Hamilton explains why an apparently infinite sequence is governed by finite algebra. Fourier analysis organizes variation by temporal frequency; suitable graph operators, especially the graph Laplacian, organize variation by spatial mode. SVD and PCA find directions adapted to data, while wavelets offer locality and scale.

No transformation supplies understanding automatically. We must still ask what is being indexed, where a series converges, whether a map is invertible, what has actually been discarded, and which notion of error matters.

The same habit of thought extends beyond mathematics. When facing a difficult problem, we might first ask whether we are looking at it from the right perspective. Could a different representation reveal possibilities we have overlooked? And before trying to optimize a solution, have we even identified what we really want to achieve?

But that discipline is exactly why transformations are so powerful: they make those questions explicit. The art lies not in transforming for its own sake, but in choosing a representation whose visible structure matches the problem we genuinely want to solve.