Fall 2003 

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 adjacency matrix L encodes the graph. The entry L_{ij} 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 , where a_{n}^{(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  
Solution to 2). [L^{2}]_{ij} is by definition of the matrix product the sum L_{i 1} L_{1 j} + L_{i 2} L_{2 j} +... + L_{i n} L_{n j}. Each term L_{i 1} L_{1 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 [L^{2}]_{ij} is the number of paths of length 2 leading from node i to j. Similarly, [L^{n}]_{ij} is the number of paths of length n going from i to j. The answer is  
Solution to 3). The for the summation of a geometric series holds also for matrices: . Cramer's rule for the inverse of a matrix is A^{1} = det(Adj(A)_{ij})/det(A) leads to det( Adj(1z L)_{ij})/det(1z L).  
Solution to 4). Especially, when i=1 and j=3,
we get det( Adj(A)_{13} = 2 z^{2} + 2 z^{3} and
det(Lz) = 17 z^{2}  2 z^{3}+4 z^{4}.
The result can be written as
(2 z^{2}+2z^{3})/(17 z^{2}  2 z^{3}+4 z^{4})
which simplifies to 2z^2/(1z6z^2+4z^3). Handout [PDF] 
Here is 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]; (1)^(1+3) Det[Adj[K[z],1,3]]/Det[K[z]] (* check with Inverse[K[z]][[1,3]] *) 
