The purpose of this article is to narrate you through solutions to the two math problems solved by the fictional character Will in the 1997 Academy Award-winning movie Good Will Hunting. The narration is based largely on the excellent paper Mathematics in Good Will Hunting II: Problems from the Students Perspective by Horváth, Korándi and Szabó (2010).

Spotify mood music. Happy reading!

Plot

Quickly summarized Good Will Hunting tells the story of the imaginary character Will Hunting, who despite his exceptional intelligence works as a janitor at the Massachusetts Institute of Technology in Boston. There, he one day spots a problem on blackboard in a hallway posed by a Fields Medal award-winning professor named Gerald Lambeau. Gifted with an eidetic memory, Will memorizes the problem and solves it on the mirror in his bathroom at home in South Boston. Back at MIT the next day, he can’t help himself but provide his solution anonymously on the blackboard.

When the next day none of Lambeau’s students claim credit, the professor poses another, more difficult problem. Will again solves it but gets caught in the act of writing out his solution by the professor, who is shocked to realize that the most brilliant young mathematician at MIT is an uneducated janitor.

The First Problem

Problem 1: Given the graph G, find1. The adjacency matrix, A
2. The matrix giving the number of 3 step walks
3. The generating function for walks from i → j
4. The generating function for walks from 1 → 3

The first problem, in graph theory, asks for the number of walks from a vertex ito vertex j in a graph G. For this, let G be a graph with set of vertices V = {1, 2, 3, 4} and set of edges E = {(1,2), (1,4), (2,4), (2,3),(2,3)} where (2,3) is a double edge.

Solutions to Problem 1

Problem 1.1
Given the graph G, find the adjacency matrix A

An adjacency matrix is a square matrix used to represent a finite graph. The elements of the adjacency matrix L indicate whether pairs of vertices in the graph are adjacent or not. For a simple graph with a set of vertices V, the adjacency matrix is a square |L| × |L| matrix such that its element Lᵢⱼ is 1 when there is one edge from vertex i to vertex j, 2 when there are two, and zero when there are no edges from vertex i to vertex j. The diagonal elements of the matrix are all zero, since edges from a vertex i to itself (loops) are not allowed in simple graphs. For all step walks of length 1 along the edge set E, this gives us the following adjacency matrix for the graph G:

Problem 1.2
Find the matrix giving the number of 3 step walks

The second task in problem 1 asks to find the matrix which encodes all possible walks of length 3 (Knill, 2003). That is, to find the number of different sequences of edges which join every distinct sequence of vertices.

An n + 1 step walk from i to j consists of an n step walk from i to k and then a 1 step walk from k to j. That is, the ij entry of Lⁿ⁺¹ is given by the sum:

Which in English for this problem states that “the number of walks of length 3 from vertex i to j" is equal to the sum of “the number of walks of length 2 from vertex i to k” multiplied by “the number of walks of length 1 from vertex k to j” for k = 1,2. By matrix multiplication, for all step walks of length 3 from i to j this gives the following matrix:

Problem 1.3
Find the generating function for walks from i → j

The third task in problem 1 asks for the generating function from vertex i to j. To answer this question, Horváth et al (2010) consider an analytic generating function defined by a power series

Where the coefficient zⁿ denotes the number of n step walks from i to j. From task 1.3, we found that ω_n(i → j) is the ij entry of the matrix Lⁿ. The problem asks for the generating function that gives all the entries simultaneously, and so it makes sense to consider a matrix L given by the familiar power series (Horváth et al, 2010):

Where Lⁿ is the matrix containing the number of step walks from each vertex i to j (the general case of the solution to problem 1.2). The sum can be calculated using the familiar identity for geometric power series, that is:

To calculate the inverse of (I − z × L) we can use Cramer’s rule. According to Horváth et al (2010) for a matrix M let Mᵢⱼ denote the matrix obtained from Mby removing the ith column and the jth row. If we do so, we obtain a matrix N whose ij entry is

By Cramer’s rule, if M is invertible (there exists some n×n matrix N such that M×N = N×M = I_n) then

That is, the ij entry of of the inverse matrix M is:

Applied to compute the inverse of M = (I − z × L), we obtain:

Substituting for M:

As Horváth et al (2010) notes, this is Will’s solution in the movie, except his solution omits the term (−1)^(i+j) (likely due to notation), and he denotes the identity matrix with 1 instead of the more common I.

Problem 1.4
Find the generating function for walks from 1 → 3

To solve task 1.4, we simply apply the general formula for walks from i to j (from task 1.3) to the case of walks from 1 → 3:

Whose determinants are trivial to find:

Giving the following expressions, obtain by using the definition of a determinant:

To obtain the coefficients of this power series, one computes the Taylor series of the function:

For our expression f(z), we can use the quotient rule where g(z) = 2z² and h(z) = 4z³− 6z² −z +1. In the movie, Will provides the values for the first six derivatives of the f(z) expansion, which are:

The Second Problem

As Will didn’t sign his work on the board for his solution to the first problem, Professor Lambeau posed a second problem, of which he states to his class “took us more than two years to prove”. The problem again regards tree structures:

Problem 2
a. How many trees are there with n labeled vertices?
b. Draw all homomorphically irreducible trees with n = 10

Solutions to Problem 2

As Horváth et al (2010) points out, task 2a actually just asks for Cayley’s formula that for every positive integer n the number of trees on n-labeled vertices is nⁿ⁻². The formula is named after Arthur Cayley, but has been known since it was discovered by Carl Wilhelm Borchardt in 1860. In Cayley’s 1889 note A theorem on trees in the Quarterly Journal of Pure and Applied Mathematics, he extended the formula by taking into account the degrees of the vertices, and so it has since bore his name. There are several known proofs of the result.

The final task, problem 2b asks for drawings of all the homomorphically irreducible trees with n = 10. A homomorphically irreducible tree is one with no points of degree 2. The problem was likely inspired by the paper The Number of Homomorphically Irreducible Trees, and Other Species by Harary & Prins (1959).

We can group the homomorphically irreducible trees by labelling their vertices by 1,…., 10 and the degrees of their vertices by d₁, …,d₁₀ (Horváth et al, 2010). As the trees have 10 vertices, we know they have 9 edges. We can categorize these various trees by their number of leaves (nodes/vertices of vertex degree 1):

• If there are 9 leaves and 1 non-leaf, then we obtain a “star”, a single vertex connected to every leaf:

• If there are 8 leaves and 2 non-leaf, then d₁ + d₂ = 10 and d₁ ≥ d₂ ≥ 3, so either: a) d₁ =7 and d₂ = 3 (one tree), or b) d₁ = 6 and d₂ = 4 (one tree), or c) d₁ = d₂ = 5 (one tree).

• If there are 7 leaves , then d₁ + d₂ + d₃ = 11 and d₁ ≥ d₂ ≥d₃ ≥ 3, so either a) d₁ = d₂ = 5 and d₃ = 3 (two trees), or b) d₁ = 5 and d₂ = d₃ = 3 (three trees).

• If there are 6 leaves, then d₁ + d₂ + d₃ +d₄ = 3.

That totals to 10 trees with n=10. On the blackboard in the movie, only 8 appear, either because Will was interrupted by Professor Lambeau or due to an oversight on the filmmakers’ part.

Backstory

In early versions of the script for Good Will Hunting, the character Will was a physics prodigy, but Sheldon Glashow at Harvard suggested it be about a mathematician instead, as modern physics is “typically a group project” whereas “doing some mathematical theorem is a singular undertaking very often” (London, 2016). The film’s mathematics consultant was Professor of physics at the University of Toronto, the late Patrick O’Donnell.

It has been speculated that the character of Will is based on child prodigy William Sidis (1898–1944), known for his exceptional mathematical abilities.

Acknowledgement

The narration provided in this essay is based largely on the wonderful paper Mathematics in Good Will Hunting II: Problems from the students perspective by Horváth, Korándi and Szabó (2010). I encourage everyone interested to read their original, in-depth paper available here which also includes discussions of the other pieces of mathematics shown in various scenes throughout the movie.

Cantor's Book Recommendations

• A First Course in Graph Theory* by Chartrand & Zhang
• The Fascinating World of Graph Theory* by Benjamin, Chartrand & Zhang
• Introduction to Graph Theory* by Richard J. Trudeau

* These are Amazon Affiliate links