Harvard University,FAS
Fall 2003

Mathematics Math21b
Fall 2003

Linear Algebra and Differential Equations

Course Head: Oliver knill
Office: SciCtr 434
Email: knill@math.harvard.edu

The Good Will Hunting Problem

(A problem in Linear algebra)
In the movie "Good Will Hunting", the main character Will Hunting (Matt Damon) solves a blackboard problem, which had been assigned as a challenge to a linear algebra class. The Good Will graph


1) Find the adjacency matrix A of the graph G
2) Find the matrix giving the number of 3 step walks in G.
3) Find the generating function for walks from point i to j.
4) Find the generating function for walks from points 1 to 3.
The adjacency matrix L encodes the graph. The entry Lij is equal to k if there are k connections between node i and j. Otherwise, the entry is zero. Problem 2 asks to find the matrix which encodes all possible paths of length 3. Generating function. To a graph one can assign for pair of nodes i,j a series f(z) = \sum_{n=0}^{\infty} a_n<sup>(ij)</sup> z<sup>n</sup>, where an(ij) is the number of walks from i to j with n steps. Problem 3) asks for a formula for f(z) and in problem 4) an explicit expression in the case i=1,j=3.


Solution to 1). The adjacency matrix L is L = 0 & 1 & 0 & 1 \\ 1 & 0 & 2 & 1 \\ 0 & 2 & 0 & 0 \\ 1 & 1 & 0 & 0
Solution to 2). [L2]ij is by definition of the matrix product the sum Li 1 L1 j + Li 2 L2 j +... + Li n Ln j. Each term Li 1 L1 j is 1 if and only if there is a path of length 2 going from i to j passing through k. Therefore [L2]ij is the number of paths of length 2 leading from node i to j. Similarly, [Ln]ij is the number of paths of length n going from i to j. The answer is L^3 = [2 & 7 & 2 & 3 \\ 7 & 2 & 12 & 7 \\ 2 & 12 & 0 & 2 \\ 3 & 7 & 2 & 2]
Solution to 3). The \sum_{n} x^n = (1-x)^{-1} for the summation of a geometric series holds also for matrices: f(z) = \sum_{n=0}^{\infty} [L^n]_{ij} z^n = [\sum_{n=0}^{\infty} L^n z^n)]_{ij} = [(1-Lz)^{-1}]_{ij}. Cramers formula for the inverse of a matrix is A-1 = det(Aij)/det(A) leads to det(1-z Lij)/det(1-z L) which can also be written as det(Lij-z)/det(L-z).
Solution to 4). Especially, when i=1 and j=3, det(L-z) = det( 1 & -z & 1 \\ 0 & 2 & 0 \\ 1 & 1 &-z ) = -2-z+3z^2-z^3 det(L-z) = -z & 1 & 0 & 1 \\ 1 & -z & 2 & 1 \\ 0 & 2 & -z & 0 \\ 1 & 1 & 0 & -z =4-2z-7z^2+z^4. The result can be written as (-z3+3z2-z-2)/(z4-7z2-2z+4).


Back to the main page