Mathematics / Film

Revisiting the First Blackboard Problem in Good Will Hunting

What the film’s first problem actually shows, how its four tasks are connected, and where the mathematics leads.

Published Approximately 18 minutes

The scene is often remembered as a single quite impossible challenge. It actually presents two blackboard problems. The first is a carefully staged sequence: construct an adjacency matrix, use its powers to count walks, and package all walk lengths into a generating function.

Introduction

This is not a general review of Good Will Hunting, nor an attempt to score points against a film. It is a reconstruction of a few minutes of mathematics: Professor Lambeau’s lecture, his announcement of the first blackboard challenge, its four tasks later visible in the hallway, and the solution shown on another board. A second, supposedly even harder problem follows later; that is a separate story.

The result is a useful refresher for anyone—including me—whose linear algebra and Fourier analysis are no longer sitting at the front of the mind. The film heightens the difficulty for dramatic purposes, but the board itself contains real and pleasantly connected mathematics.

What happens in the scene?

At approximately 00:03:35, Lambeau is finishing a lecture involving Fourier analysis and Parseval’s identity. He asks the class to complete the Parseval material next time and dryly observes that many of them encountered it as undergraduates, so a review will do no harm.

Around 00:03:55, he turns from the lecture to a separate challenge placed on the chalkboard in the hallway (this is where later an “even harder” problem is written down), describing it as an advanced Fourier system. By about 00:04:00, he says that he hopes someone will prove it before the semester ends. A few seconds later he invokes academic fame and recognition—Nobel laureates, Fields Medal winners and other distinguished former names—in a deliberately grand, somewhat sardonic piece of classroom theatre. As you might remember, he is a Fields Medal laureate himself.

The surviving working notes are imperfect dialogue notes, so those lines are paraphrased here rather than polished into invented quotations. What matters for the mathematics is the transition: a Fourier lecture ends, and a challenge is announced. Later, the hallway board presents its concrete graph-theory tasks.

Lambeau at a chalkboard containing a Fourier-series expansion and a Parseval identity.
Lambeau concludes a lecture involving Fourier analysis and Parseval’s identity.

Fourier first, graph theory second

Two mathematical layers appear close together. The lecture board contains Fourier series and a Parseval-type norm identity. The first hallway challenge, by contrast, shows a four-vertex graph and asks about its adjacency matrix, walks and generating functions.

The first blackboard problem is therefore not itself a Fourier-analysis problem. But the subjects are not strangers. A generating function already changes how we represent a sequence, and the matrix behind it has other useful representations as well. Those connections lead to eigenmodes, transforms and approximation, but they are not hidden steps required to solve the four tasks. I develop that wider story separately in The Wonderful World of Mathematical Transformations.

The four tasks on the board

The screenshot shows four connected requests—not merely “find the adjacency matrix.” In clean notation, while preserving the board’s meaning, they are:

  1. Find the adjacency matrix \(A\).
  2. Find the matrix giving the number of three-step walks.
  3. Find the generating function for walks from vertex \(i\) to vertex \(j\).
  4. Find the generating function for walks from vertex \(1\) to vertex \(3\).

The progression is the point. Task 1 encodes the graph. Task 2 discovers what matrix powers count. Task 3 gives a scalar generating function for an arbitrary pair of vertices \(i,j\). Task 4 then specializes that general answer to \(i=1\) and \(j=3\).

The hallway chalkboard showing a four-vertex multigraph and four graph-theory tasks.
The hallway board presents four connected graph-theory tasks.

Task 1: the adjacency matrix

Perhaps a remark first: if you shake your head and say, “I never encountered this in my studies,” that may well be true. Even as a theoretical physicist, I did not meet adjacency matrices in my physics or mathematics courses, but only later in theoretical computer science, in connection with automata theory, Petri nets and related topics. So it would be no surprise if a mathematician, physicist or engineer had never seen this particular use of matrices. Cayley–Hamilton and related matrix identities do appear in finite-dimensional quantum mechanics, but interpreting matrix powers as counts of walks belongs to a different context.

The diagram has four labelled vertices. Vertices 1, 2 and 4 form a triangle; vertices 2 and 3 are joined by two parallel edges. Because a pair of vertices may have more than one edge, this is a multigraph.

Its adjacency matrix, checked against the graph visible in the screenshot, is

\[ A = \begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 2 & 1 \\ 0 & 2 & 0 & 0 \\ 1 & 1 & 0 & 0 \end{pmatrix}. \]

Rows and columns correspond to vertices, and \(A_{ij}\) counts edges between vertices \(i\) and \(j\). The graph is undirected, so \(A\) is symmetric. No loops are shown, so every diagonal entry is zero. The entries \(A_{23}=A_{32}=2\) record the two parallel edges between vertices 2 and 3.

Task 2: counting three-step walks

A walk may revisit vertices and edges. The standard adjacency-matrix result is that

\[ (A^n)_{ij} \]

counts walks of length \(n\) from vertex \(i\) to vertex \(j\), with parallel-edge choices counted separately.

Matrix multiplication explains why. For two steps,

\[ (A^2)_{ij} = \sum_k A_{ik}A_{kj}. \]

Fix an intermediate vertex \(k\). There are \(A_{ik}\) choices for the first edge and \(A_{kj}\) choices for the second, so their product counts the two-step walks passing through \(k\). Summing over all \(k\) counts every possible intermediate vertex. Repeated multiplication appends further steps, giving the result for \(A^n\).

For this graph, direct multiplication gives

\[ A^2 = \begin{pmatrix} 2 & 1 & 2 & 1 \\ 1 & 6 & 0 & 1 \\ 2 & 0 & 4 & 2 \\ 1 & 1 & 2 & 2 \end{pmatrix}, \]

and then

\[ A^3 = \begin{pmatrix} 2 & 7 & 2 & 3 \\ 7 & 2 & 12 & 7 \\ 2 & 12 & 0 & 2 \\ 3 & 7 & 2 & 2 \end{pmatrix}. \]

Thus \((A^3)_{13}=2\): exactly two three-step walks run from vertex 1 to vertex 3. They have the vertex sequence \(1\to4\to2\to3\); the final move can use either of the two parallel edges from 2 to 3.

The 12 in \((A^3)_{23}\) is larger but less transparent at a glance. The entry \((1,3)\) makes the multigraph bookkeeping especially easy to see, which is why it is a useful example before Task 4 asks for that same pair of vertices.

Tasks 3 and 4: generating functions

Rather than treating every length separately, introduce a variable \(t\) and collect all powers of \(A\) into the matrix generating function

\[ G(t) = I+tA+t^2A^2+t^3A^3+\cdots = \sum_{n=0}^{\infty}A^nt^n. \]

The coefficient of \(t^n\) in the \((i,j)\) entry is \((A^n)_{ij}\), the number of length-\(n\) walks from \(i\) to \(j\). For fixed vertices, that entry is the scalar generating function

\[ g_{ij}(t) = \sum_{n=0}^{\infty}(A^n)_{ij}t^n. \]

The distinction matters: \(G(t)\) is matrix-valued and stores every ordered pair of vertices; \(g_{ij}(t)\) is one scalar entry answering Task 3.

At first, \(t\) is a formal bookkeeping variable. Its powers keep different walk lengths separate. Analytically, the series converges for \(|t|<1/\rho(A)\), where \(\rho(A)\) is the spectral radius. In particular, it does not converge at \(t=1\): because the graph contains cycles, walks exist for arbitrarily large lengths, so infinitely many terms are at least 1.

The usual geometric-series cancellation works for matrices:

\[ \begin{aligned} (I-tA) \left( I+tA+t^2A^2+\cdots \right) &= I+tA+t^2A^2+\cdots\\ &\quad{}-tA-t^2A^2-t^3A^3-\cdots\\ &=I. \end{aligned} \]

Consequently, as a formal power series—and analytically throughout that disk of convergence—

\[ \boxed{G(t)=(I-tA)^{-1}.} \]

Taking one entry gives

\[ \boxed{ g_{ij}(t) = e_i^{\mathsf T}(I-tA)^{-1}e_j = \left[(I-tA)^{-1}\right]_{ij} = \frac{C_{ji}(I-tA)}{\det(I-tA)} }. \]

Here \(e_i\) and \(e_j\) are standard basis vectors. The last equality is the determinant/cofactor formula for an inverse; the reversed indices are important because the \((i,j)\) entry uses cofactor \(C_{ji}\).

Task 4 asks for \(i=1\), \(j=3\). An independent cofactor calculation gives

\[ C_{31}(I-tA)=2t^2+2t^3 \]

and

\[ \det(I-tA)=1-7t^2-2t^3+4t^4. \]

Therefore

\[ g_{13}(t) = \frac{2t^2+2t^3}{1-7t^2-2t^3+4t^4}. \]

Both numerator and denominator contain \(1+t\):

\[ 2t^2+2t^3=2t^2(1+t), \qquad 1-7t^2-2t^3+4t^4 =(1+t)(1-t-6t^2+4t^3). \]

After cancellation,

\[ \boxed{ g_{13}(t) = \frac{2t^2}{1-t-6t^2+4t^3} }. \]

Writing \(g_{13}(t)=\sum_{n=0}^{\infty}a_nt^n\) and comparing coefficients in

\[ (1-t-6t^2+4t^3)g_{13}(t)=2t^2 \]

gives \(a_0=a_1=0\), \(a_2=2\), and, for \(n\geq3\),

\[ a_n=a_{n-1}+6a_{n-2}-4a_{n-3}. \]

The division therefore begins

\[ \boxed{ g_{13}(t) = 2t^2+2t^3+14t^4+18t^5+94t^6+\cdots }. \]

These coefficients provide immediate checks. There are no walks of lengths 0 or 1 from vertex 1 to vertex 3. At length 2 there are two, both following \(1\to2\to3\) and differing only in the parallel edge used. At length 3 there are the two walks \(1\to4\to2\to3\) described above, agreeing with \((A^3)_{13}=2\). Direct matrix multiplication gives 14, 18 and 94 at lengths 4, 5 and 6, matching the series and the recurrence.

Detail of the solution board showing walk-count notation and a determinant expression.
The solution uses walk-count notation and the determinant/cofactor formula for an inverse-matrix entry.
Detail of the solution board showing the adjacency matrix, its third power and a generating function.
The adjacency matrix, its third power and the generating-function calculation appear together on the later board.

Where the mathematics leads next

The four blackboard tasks are complete. Yet their last answer opens a larger door. The inverse \((I-tA)^{-1}\) is closely related to the resolvent \((zI-A)^{-1}\) through \(z=1/t\); its denominator is tied to the characteristic polynomial, Cayley–Hamilton turns its coefficients into recurrences, and eigenvectors turn the matrix dynamics into separate modes. On another axis, the same power series is related to a unilateral Z-transform by a reciprocal change of variable. Fourier analysis, Parseval, SVD, PCA and wavelets then offer other examples of a recurring mathematical move: change the representation so that structure becomes visible.

That extended journey—and the important question of when a transformation is merely invertible and when discarding coefficients truly compresses information—belongs in The Wonderful World of Mathematical Transformations, not in the solution of Lambeau’s exercise.

Is the first problem really that difficult?

The first, four-part problem is mathematically genuine. Its sequence from adjacency matrix to walk counts and generating functions is elegant, compact and well suited to a blackboard. It also opens a door to deeper mathematics without requiring any of it for the original solution.

The film greatly amplifies the exercise’s research-level difficulty. That exaggeration serves the story, but it does not make the board meaningless or badly constructed. A fairer description is that it is a strong connected exercise in graph theory and linear algebra, presented with the dramatic reputation of something much larger. From this point on, the film becomes quite dramatic. A student excitedly reports that “someone solved the theorem!” Yet what appears on the blackboard is not a theorem at all but a carefully designed sequence of exercises—written there by Professor Lambeau himself. He then walks to the board and examines the solution with genuine astonishment. For the audience this creates suspense; mathematically, however, it is difficult to imagine a Fields Medal recipient being baffled by the solution to his own exercise at all.

Conclusion

Many viewers remember the scene as a fantasy of effortless genius. Revisited carefully, it can do something gentler and more useful: remind us how a matrix encodes structure, how its powers count processes, and how a generating function gathers an infinite sequence of questions into one object.

The lecture and hallway boards belong to different topics, but they are not sealed off from one another. The path between them is worth following—as a second story, after giving the film’s four tasks room to stand on their own.