• The Mathematics in the Cinema Movie "Good Will Hunting"
  • the multigraph G, its adjacency matrix A and the number of walks in G between two vertices.
  • the generatingfunction f(z) for the number of walks between two arbitrary, but fixed, vertices of G; in particular the vertices 1 and 3.
  • two eigenvalue problems on the classroom blackboard.
  • the chromatic polynomial of a triangular graph, determined jointly by Lambeau and Will by simplifying a rational function for it.
  • Cayley's theorem on the number of spanning trees in a complete graph.

> restart:with(linalg):with(networks):with(plots):

Warning, the protected names norm and trace have been redefined and unprotected

Warning, the names charpoly and rank have been redefined

Warning, the name changecoords has been redefined

The Mathematics in the Cinema Movie "Good Will Hunting"

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" ,but it turns out to be a second year problem in algebraic graph theory, to be solved in four stages. Let's see, if Maple can do the job.

the multigraph G, its adjacency matrix A and the number of walks in G between two vertices.

> G:=graph({1,2,3,4},{}):addedge([{1,2},{1,4},{2,3},{2,3},{2,4}],weights=[1,1,1,1,1],names=[a,b,c,d,e],G);
draw(Concentric([2,4,1],[3]),G); ( the line 2--3 should be doubled)

A:=adjacency(G);

Its third power counts the walks of length three in G.

> evalm(A^3);

For instance the number 2 in the [1,1]-entry of A is equal to two because there are exactly two walks of lenght 3 from vertex 1 back to 1, viz. 1--2--4--1 and the other way around: 1--4--2--1.

To determine the nth power of A, which, of course, counts the n-steps walks in G and is not necessary for the solution of the problem we need to diagonalize our symmetric matrix A, but the eigenvalues (obtained in the classical way, according to Cardano) are complicated enough (see below) to not persue this goal any further.

> p(lambda):=charpoly(G,lambda);(linalg)[charpoly](A,lambda);factor(p(lambda));
q(lambda):=simplify(p(lambda)/(lambda+1));plot(q(lambda),lambda=-3..3);solve(q(lambda)=0);
Surprise: The roots of the symmetric matrix A are real numbers, of course, but Maple doesn't give us a clue, at first, how to see this. I'll have to consult our local Maple experts Adri van der Meer and Peter Gragert (again) to learn about a PURE Maple way of evaluting the eigenvalues as exact real algebraic numbers.

> realroot(q(lambda),1/100);Digits:=20:fsolve(q(lambda),lambda=-2.4..-2.2);fsolve(q(lambda),lambda=0.6..0.7);fsolve(q(lambda),lambda=2.6..2.8);

An easier way to write the three eigenvalues is by using the three third roots of unity and the real-part function along the lines of Cardano's approach:

> lambda[1]:=(1+2*Re((-26+3*I*sqrt(687))^(1/3)))/3;
lambda[2]:=(1+2*Re(((-1+I*sqrt(3))/2)*(-26+3*I*sqrt(687))^(1/3)))/3;
lambda[3]:=(1+2*Re(((-1-I*sqrt(3))/2)*(-26+3*I*sqrt(687))^(1/3)))/3;
evalf(lambda[2],20);
evalf(lambda[3],20);
evalf(lambda[1],20);

Or, after normalizing to a complex number w of unit length and trisecting the appropriate angles:

> lambda[1]:='lambda[1]':lambda[2]:='lambda[2]':lambda[3]:='lambda[3]':
lambda:=n->(1+2*sqrt(19)*cos(phi(n)/3))/3;
w:=(-26+3*I*sqrt(687))/(19*sqrt(19));abs(w);phi:=n->arccos(-26/(19*sqrt(19)))+n*2*Pi;
for n from 1 by 1 to 3 do lambda[n]= evalf(lambda(n-1),20) od;

O.K. What you were waiting for; the experts do it as follows:

> solve(q(lambda)):evalc([%]);

> map(evalf(%),20);

So far the eigenvalues of A.

By the Cayley-Hamilton theorem we have the identity A^(n+4) = 7*A^(n+2) + 2*A^(n+1) - 4*A^n, which allows for a recursive evaluation of the powers of A avoiding multiplication (almost) completely.

We finally note that the coefficients of the characteristic polynomial of any graph have a distinct interpretation in terms of sesquilinear subgraphs, that is, in terms of subgraphs whose components are either cycles or single edges; see e.g."Chapter 7 of Norman Biggs' Algebraic Graph Theory". In the case at hand the coefficient 7 can be explained as the number of edges of G counting the edges in the 2-cycle (through the vertices 2 and 3) twice. The next coefficient 2 stems from the fact that the single triangle in G has two orientations.

the generatingfunction f(z) for the number of walks between two arbitrary, but fixed, vertices of G; in particular the vertices 1 and 3.

> id:=(i,j)-> if i=j then 1 else 0 fi: I4:=matrix(4,4,id);evalm(z*A);n:='n':f(z):=Sum((evalm(z*A))^n,n=0..infinity); f(z):=evalm(inverse((I4-z*A)));

> factor(f(z)[1,3]);

> (-1)^(1-3)*det(minor(I4 - z*A,3,1))/det(I4 - z*A);

> simplify(%);

> taylor(f(z)[1,3],z=0,13);

> for i from 2 by 1 to 12 do evalm(A^i)[1,3] od;

two eigenvalue problems on the classroom blackboard.

> restart:with(linalg):B:=matrix(3,3,[[1,1,0],[1,1,-2],[2,1,0]]);
C:=matrix(3,3,[[2*k,-k,-k],[-k,2*k,-k],[-k,-k,2*k]]);

Warning, the protected names norm and trace have been redefined and unprotected

> charpoly(B,lambda);eigenvects(C);
note that the eigenspaces of the symmetric matrix C are orthogonal indeed and that the eigenvalue 3k has multiplicity greater than 1 (called a degenerate case on the board).

the chromatic polynomial of a triangular graph, determined jointly by Lambeau and Will by simplifying a rational function for it.

I don't know where the rational fuction comes from. Anyway, the answer (below) is trivial. In fact there are k ways to color vertex 1 with a color from a colorset of size k and, in a proper vertex coloring, for each chosen color for vertex 1, vertex 2 can only be colored in k-1 ways, viz. with a color distinct from that picked out for 1. Now there are only k-2 admissible colors left for vertex 3 and so on.

> restart:with(networks):H:=graph({1,2,3,4,5,6},{{1,2},{1,3},{1,4},{1,5},{2,3},{2,4},{2,6},{3,5},{3,6}}):draw(Concentric([1,2,3],[4,6,5]),H);chrompoly(H,k);

Cayley's theorem on the number of spanning trees in a complete graph.

> restart:with(networks):K4:=complete(4):draw(K4);
This graph has 16 spanning trees; the has , by Cayley's theorem. This number (answer?) is written on the top leftside of the blackboard, when Will is drawing his (irrelevant) trees beneath and Lambeau and Tom enter the corridor. Many distinct original proofs exist for Cayley's result; among them one by my colleague Frits Gbel.