Good Will Hunting Math Problem — 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.

When Professor Lambeau first announces the prize problem on the blackboard in the corridor, which is to be solved by Will the next evening, the blackboard in the classroom contains Parseval’s Theorem from Fourier Analysis, as well as a part of its proof. Lambeau refers to the prize problem as an “advanced Fourier System”.

mattdamon-good-will-hunting-linear-algebra

good-will-hunting-algebra-problem

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.

Let’s solve this.

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.

Solutions:

1)  The adjacency matrix L is,

good-will-hunting-algebra-problem-adjacency-matrix

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 not 0 if and only if there is at least one 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,

good-will-hunting-algebra-problem-adjacency-matrix-3

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}.

Cramer’s rule for the inverse of a matrix is A-1 = det(Adj(A)ij)/det(A) leads to det( Adj(1-z L)ij)/det(1-z L) which can also be written as det( Adj(L-z)ij)/det(L-z).

4) Especially, when i=1 and j=3, we get det( Adj(A)13 = 2 z2 + 2 z3 and det(L-z) = 1-7 z2 – 2 z3+4 z4. The result can be written as (2 z2+2z3)/(1-7 z2 – 2 z3+4 z4) which simplifies to 2z^2/(1-z-6z^2+4z^3).

Here’s the Mathematica code to check this:

L={{0,1,0,1}, {1,0,2,1}, {0,2,0,0}, {1,1,0,0}}
K[z_]:=IdentityMatrix[4] -z*L;
Adj[A_,i_,j_]:=Module[{B=A},B=Delete[B,i];B=Transpose[B];B=Delete[B,j];B];
Det[Adj[K[z],1,3]]/Det[K[z]]
(* check with  Inverse[K[z]][[1,3]]  *)

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s