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

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

**Solutions:**

1) The adjacency matrix L is,

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,

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(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 z^{2} + 2 z^{3} and det(L-z) = 1-7 z^{2} – 2 z^{3}+4 z^{4}. The result can be written as (2 z^{2}+2z^{3})/(1-7 z^{2} – 2 z^{3}+4 z^{4}) 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]] *)