ICE: A BLACKBOARD PROBLEM Math 21b, O. KnillIn the movie”Good WillHunting”, themain characterWill Hunting(Matt Damon)solves a black-board challengeproblem, whichis given as achallenge to alinear algebraclass.THE ”WILL HUNTING” PROBLEM.G is the graph1 234Find.1) the adjacency matrix A.2) the matrix giving the number of 3 step walks.3) the generating function for walks from point i → j.4) the generating function for walks from points 1 → 3.This problem belongs to linear algebra and calculus evenso the problem origins from graph the-ory or combinatorics. For a calculus student who has never seen the connection between graphtheory, calculus and linear algebra, the assignment is actually hard – probably too hard - as themovie correctly indicates. The problem was posed in the last part of a linear algebra course.An explanation of some terms:THE ADJACENCY MATRIX. The structure of the graph can be encoded with a 4 × 4 arraywhich encodes how many paths of length 1, one can take in the graph from one node to another:no one no oneone none two oneno two no noone one no nowhich can more conve-niently be written asan array of numberscalled a matrix:L =0 1 0 11 0 2 10 2 0 01 1 0 0Problem 2 asks to find the matrix which encodes all possible paths of length 3.GENERATING FUNCTION. To any graph one can assign for every pair of nodes i, j a seriesf(z) =P∞n=0a(ij)nzn, where a(ij)nis the number of possible walks from node i to node j with nsteps. Problem 3) asks for an explicit expression of f(z) and problem 4) asks for an explicitexpression in the special case i = 1, j = 3.Linear algebra has many relations to other fields in mathematics. It is not true that linearalgebra is just about solving systems of linear equations.SOLUTION TO 2). [L2]ijis by definition of the matrix product the sum Li1L1j+ Li2L2j+... + Li4Lhj. Each term Li1L1jis 1 if and only if there is a path of length 2 going from i to jpassing through k. Therefore [L2]ijis the number of paths of length 2 going from node i to j.Similarly, [Ln]ijis the number of paths of length n going from i to j. The answer isL3=2 7 2 37 2 12 72 12 0 23 7 2 2SOLUTION TO 3). The geometric series formulaXnxn= (1 − x)−1holds also for matrices:f(z) =∞Xn=0[Ln]ijzn= [∞Xn=0Lnzn)]ij= (1 − Lz)−1Cramers formula for the inverse of a matrix which involves the determinantA−1= det(Aij)/det(A)This leads to an explicit formuladet(1 − zLij)/det(1 − zL)which can also be written asdet(Lij− z)/det(L − z) .SOLUTION TO 4). This is the special case, when i = 1 and j = 3.det(L − z) = det(1 −z 10 2 01 1 −z) = −2 − z + 3z2− z3.det(L − z) =−z 1 0 11 −z 2 10 2 −z 01 1 0 −z= 4 − 2z − 7z2+ z4The final result is(z3+ 3z2− z − 2)/(z4− 7z2− 2z + 4)
View Full Document
Unlocking...