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 Horvth, Korndi and Szab (2010).
Spotify mood music. Happy reading!
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
Professor Gerald Lambeau (portrayed by Stellan Skarsgrd) looking over Will?s proposed solution. Photo: 1997 Miramax PicturesProblem 1: Given the graph G, find1. The adjacency matrix, A2. The matrix giving the number of 3 step walks3. The generating function for walks from i ? j4. The generating function for walks from 1 ? 3
Figure 1: The graph G
The first problem, in graph theory, asks for the number of walks from a vertex i to 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.1Given 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:
Solution 1.1. Edge elements from vertices i to j and adjacency matrix of graph G, showing the number of edges between vertices i and jProblem 1.2Find 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:
Equation 1
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:
Solution 1.2. The matrix representing the number of 3 walks from vertex i to j in graph GProblem 1.3Find 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, Horvth et al (2010) consider an analytic generating function defined by a power series
Equation 2
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 (Horvth et al, 2010):
Equation 3
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:
Equation 4
To calculate the inverse of (I ? z L) we can use Cramer?s rule. According to Horvth et al (2010) for a matrix M let M?? denote the matrix obtained from M by removing the ith column and the jth row. If we do so, we obtain a matrix N whose ij entry is
Equation 5
By Cramer?s rule, if M is invertible (there exists some nn matrix N such that MN = NM = I_n) then
Equation 6
That is, the ij entry of of the inverse matrix M is:
Equation 7
Applied to compute the inverse of M = (I ? z L), we obtain:
Equation 8
Substituting for M:
Solution 1.3. The generating equation for walks from i to j
As Horvth 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.4Find 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:
Equation 9.
Whose determinants are trivial to find:
Equation 10 and 11. Determinants of (I ? zL) and its minor/reduced determinant (I?? ? zL??)
Giving the following expressions, obtain by using the definition of a determinant:
Equation 12. Formula for determining the generating function for walks from vertex 1 to 3.
Equation 13. Formula for determining the values of the generating function for walks from vertex 1 to 3, solved
To obtain the coefficients of this power series, one computes the Taylor series of the function:
Equation 14. Function for calculating the Taylor series of f(z), the Maclaurin series, where f?(0) is the nth derivative of f at 0.
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:
Solution 1.4. Taylor expansion for determining the values of the generating function for walks from vertex 1 to 3
The Second Problem
A shocked Professor Lambeau gazes at the correct solution to the second problem, provided by the anonymous janitor he had just chased away. Photo: 1997 Miramax Pictures
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 Horvth et al (2010) points out, task 2.1 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 2.2 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?? (Horvth 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).
Homomorphically irreducible trees with 8 leaves
- 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).
a) Homomorphically irreducible trees with 7 leaves and d? ) d? = 5 and d? = 3
b) Homomorphically irreducible trees with 7 leaves and d? = 5 and d? = d? = 3
- If there are 6 leaves, then d? + d? + d? +d? = 3.
Homomorphically irreducible trees with 6 leaves and 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 skills.
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 Horvth, Korndi 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.
This essay is part of a series of stories on math-related topics, published in Cantor?s Paradise, a weekly Medium publication. Thank you for reading!
