←
→

LOG#055. Will Hunting problems.

Posted: 2012/11/27 | Author: | Filed under: Physmatics | Tags: , , , , , , , , , , , , , , , , , |6 Comments

The off-topic post today (I am trying to edit a complete long thread about “fundamental constants” and “units” in Physics for the next posts, so be patient, please) is graph theory through a wonderful film. I have always loved the movie Good Will Hunting. It has some remarkable problems I solved long ago…Here you are my solutions ( and a final challenge at the end of this blog post to test your mathematical skills).

Problem A. Given the graph G below:

1) Find the adjacency matrix L of G.

2) Find the matrix giving the number of 3 step walks in G.

3) Find the generating function of the graph G for walks from node (i) to node (j).

4) Find the generating function for walks from point/node 1 to point/node 3. Explain the final result.

The adjacency matrix L or L=(L_{ij}) encodes some beautiful features of the graph. The entry L_{ij}  is equal to k if there are k connections/links/edges between node i and j. Otherwise, the entry is zero. Problem A1 is to find L and A2 asks to find the matrix which encodes all possible paths of length 3. L^2_{ij} is by definition of the matrix product the sum

L_{i1}L_{1j}+L_{i2}L_{2j}+\ldots+L_{in}L_{nj}

Each term in this sum, like L_{i1}L_{1j} 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, the matrix (L^2)_{ij} is the number of paths of length 2 leading from node i to j.

Similarly, L^n_{ij} will be the number of paths of length n going from i to j. A walk/path of length k is an ordered sucession of vertices and edges (v_1,e_1,\ldots,v_n,e_n) and such as v_1=v_n if the walk is “closed”  after k-steps/jumps from node to node.

Generating function/Generating function matrix. To a graph one can assign for pair of nodes (i,j) a series

\displaystyle{f(z)=\sum_{n=0}^\infty a_n^{(ij)}z^n}

and where a_n^{(ij)} is the number of walks from i to j with n steps. Problem A3 asks for a formula for f(z) and problem A4 asks an explicit expression in the case i=1,j=3. In the movie, the generating function is written in a different notation

\displaystyle{\Gamma^\omega \left(P_i\rightarrow P_j; z\right)=\sum_{n=0}^\infty \omega_n \left( i\rightarrow j\right)z^n}

There, a_n^{(ij)}=\omega_n \left( i\rightarrow j\right)=\omega_n^{(ij)}

The formula \displaystyle{\sum_n x^n=(1-x)^{-1}}  for the summation of a geometric series holds also for matrices, since

\displaystyle{f(z)_{ij}=\sum_{ n=0}^\infty L^n_{ij}z^n=\left[\sum_{n=0}^\infty L^nz^n\right]_{ij}=\left[\left( 1-Lz\right)^{-1}\right]_{ij}}

Solution A1.

\boxed{A=L_{ij}=\begin{pmatrix} 0 & 1 & 0 & 1\\ 1 & 0 & 2 & 1\\ 0 & 2 & 0 & 0\\ 1 & 1& 0 & 0\end{pmatrix}}

Solution A2.

A^2=L^2_{ij}=\begin{pmatrix}2 & 1 & 2 & 1\\ 1 & 6 & 0 & 1\\ 2 & 0 & 4 & 2\\ 1 & 1 & 2 & 2\end{pmatrix}

\boxed{A^3=L^3_{ij}=\begin{pmatrix}2 & 7 & 2 & 3\\ 7 & 2 & 12 & 7\\ 2 & 12 & 0 & 2\\ 3 & 7 & 2 & 2\end{pmatrix}}

Solution A3.

The Cramer’s rule for the inverse of a matrix is

A^{-1}=\dfrac{\mbox{Adj}(A)^T}{\det A}

and it leads to the equivalent formulae

A^{-1}_{ij}=\dfrac{\mbox{Adj}(A^T)_{ij}}{\det A_{ij}}

and with A=1-zL

(1-zL)^{-1}_{ij}=\dfrac{\mbox{Adj}((1-zL)^T)_{ij}}{\det (1-zL)_{ij}}

\vert A^{-1}_{ij}\vert =\dfrac{\vert \mbox{Adj}(A^T)_{ij}\vert }{\vert A_{ij}\vert }=\dfrac{\vert \mbox{Adj}(A)_{ij}\vert }{\vert A_{ij}\vert }

as \det A=\det A^T. For A=\mathbb{I}-z\mathbb{L}, we get

\det A^{-1}_{ij}=\dfrac{\det \left(\mathbb{I}-z\mathbb{L}\right)}{\det (1-zL)}=\dfrac{\det (\mathbb{I}_{ij}-zL_{ij})}{\det (1-zL)}

It can also be written as

\det A^{-1}_{ij}=\dfrac{\det \left(\mbox{Adj}(L^{-1}-z)_{ij}\right)}{\det (L^{-1}-z)}

Solution A4.

Especially, when i=1 and j=3, we get

\det (\mbox{Adj}(L)_{13})=2z^2+2z^3 and \det (1-zL)=1-7z^2-2z^3+4z^4. Then, the generating function can be written as the fraction

f(z)=\dfrac{2z^2+2z^3}{1-7z^2-2z^3+4z^4}=\dfrac{2z^2(1+z)}{1-7z^2-2z^3+4z^4}=\dfrac{2z^2}{1-z-6z^2+4z^3}

Indeed, the computation can be done for every pair of nodes. The generating function matrix comes from

A=L_{ij}=\begin{pmatrix}0 & 1 & 0 & 1\\ 1 & 0 & 2 & 1\\ 0 & 2 & 0 & 0\\ 1 & 1& 0 & 0\end{pmatrix}

and then

A^{-1}=L_{ij}^{-1}=f(z)_{ij}=W(z)_{ij}=(I-zL)^{-1}=\begin{pmatrix}1 & -z & 0 & -z\\ -z & 1 & -2z & -z\\ 0 & -2z & 1 & 0\\ -z & -z& 0 & 1\end{pmatrix}^{-1}

A long and tedious calculation provides

W(z)_{ij}=\dfrac{1}{1-z-6z^2+4z^3}\begin{pmatrix}\frac{1-5z^2}{1+z} & z & 2z^2 & \frac{z+z^2-4z^3}{1+z}\\ z & 1-z & 2(z-z^2) & z \\ 2z^2 & 2(z-z^2) & 1-z-2z^2 & 2z^2\\ \frac{z+z^2-4z^3}{1+z} & z & 2z^2 & \frac{1-5z^2}{1+z}\end{pmatrix}

Finally, let us remark that if we expand the generating function into an infinite series, we can obtain the number of walks of k-length as the numerical coefficient in the kth-power of z. In our example and problem from the Will Hunting’s movie, we deduce that

f(z)=\dfrac{2z^2}{1-z-6z^2+4z^3}

and then

f(z)\approx 2z^2+2z^3+14z^4+18z^5+96z^6+146z^7+638z^8+1138z^9+\mathcal{O}(z^{10})

or up to 12th degree in z

f(z)\approx 2z^2+2z^3+14z^4+18z^5+96z^6+146z^7+638z^8+1138z^9+4382z^{10}+8568z^{11}+30398z^{12}+\mathcal{O}(z^{13})

Then, from the node 1 to the node 3 there is 2 walks of length 2, 2 walks of length 3, 14 walks of length 4, 18 paths of length 5, 96 paths of length 6, 146 walks of length 7, 638 paths of length 8, 1138 walks of length 9, and so on.

The movie provides this cool picture of the problem and the solutions I have already deduced

Problem B.

1) State the Cayley’s theorem/formula and explain its meaning.

2) Find every homeomorphically irreducible tree of degree 10 ( i.e., irreducible trees of 10 nodes non-isomorphic to each other, and without vertices of degree 2).

Answer B1. Cayley’s formula is a result in graph theory named after the mathematician Arthur Cayley. It states that for any positive integer n the number of trees with labeled vertices is n^{n-2}, i.e, it says that the number of trees on n-labeled vertices is n^{n-2}.

Remark: The formula equivalently counts the number of “spanning trees” of a complete graph K_n with n-labeled vertices.

Answer B2. The solution is given by the following trees

Only 8 of these graphs are in the movie, since when Will Hunting is writing them on the blackboard, Prof. Lambeau appeared and Will didn’t continue with the solution to the problem.

Remark: The counting function for homeomorphically (inequivalent) irreducible trees is

h(x)=x+x^2+x^4+x^5+2x^6+2x^7+4x^8+5x^9+10x^{10}+14x^{11}+26x^{12}+\mathcal{O}(x^{13})

Homeomorphically irreducible trees are also called series-reduced trees  or topological trees. Indeed, the generating function expansion is a series formed by the so-called number of reduced trees with n-nodes. It is  the Sloane series A000014, and it is given by the following numbers:

a_n=0, 1, 1, 0, 1, 1, 2, 2, 4, 5, 10, 14, 26, 42, 78, 132, 249, 445, 842, 1561, 2988, 5671, 10981,

21209, 41472, 81181, 160176, 316749, 629933, 1256070, 2515169, 5049816, 10172638,

20543579, 41602425, 84440886, 171794492, 350238175, 715497037, 146440711,\ldots

Here you are the complete list of homeomorphically irreducible trees up to n=12 ( n=0 is absent since it is the empty set) :

HomeoIrrTreesNleq12PartI

HomeoIrrTreesNleq12partII

PS: A final poster of the Good Will Hunting movie and some of the problem B solutions, with solution in b) being wrong in one case AND incomplete ( be aware!)…

PS(II): A challenge for eager readers is…Are you able to guess AND prove the complicated formulae providing the last series and numbers? I mean, are you able to find the generating function producing the series above?

a_n=0, 1, 1, 0, 1, 1, 2, 2, 4, 5, 10, 14, 26, 42, 78, 132, 249, 445, 842, 1561, 2988, 5671, 10981,

21209, 41472, 81181, 160176, 316749, 629933, 1256070, 2515169, 5049816, 10172638,

20543579, 41602425, 84440886, 171794492, 350238175, 715497037, 146440711,\ldots

It is not easy but it is fun and enlightening!

STAY TUNED!!!

6 Comments on “LOG#055. Will Hunting problems.”

  1. Philippe Lefebvre (@Z_E_U_S_0) says:
    2013/04/03 at 12:05 AM

    Hi . Could you provide the solution for problem PS(II)? . I do not have the proper mathematical knowledge to arrive at the answer yet but I am very interested in knowing the generating function for this series.

    Reply
    • amarashiki says:
      2013/04/03 at 1:10 PM

      Well, the solution is tricky and very hard, because there is no analytical generating function per se. You have to guess a numerical solution for an implicit equation of 3 specific graph types and then you solve the implicit equation with a computer or by hand by brute force(I did the latter long ago). As far as I know, there is no analytical closed formula to that series, but an implicit solution in terms of 3 generating functions makes the job. You can also search for the solution in a mathematical page devoted to the origin and uses of series if you are clever enough. However, it is a nice excercise to face with the problem, as I did myself some years ago, and compute analitically the first numbers and/or use your computer (with the aid of Mathematica, Maple,…) to solve the 3 equations providing the solution implicitly. I will not provide solutions of this class of excercises in my blog (explicitly) since I believe that “young people” go too fast for the solution without thinking in general the procedure to get them! It is important the process to arrive at solutions! Otherwise, and more now in the internet era, you google it and you have the solution. That is not how the world works. Scientists like me face problems without knowing most of the time how to solve it…Hehehe…Engineers and other people are interested only in “the solution”… It also happens with problems like those I wrote long ago relative to neutrinos in some Cherenkov detectors. I really believe that what matters for people interested in science should also be how to get the solutions. Of course, some of these ideas I have could be preposterous in the far future, when every question has been solved, it is likely that people were only interested in the solutions, and not how to get them (with computers only?)…A pity! Try harder! You will learn a lot if you face the problem yourself… I urge you to post the solution in the future, when you find it. I will be honored and glad to know some people do/solve the problems I proposed here :).

  2. srandy6977 says:
    2013/05/23 at 7:14 AM

    Two of the entries in your matrix L^2 are incorrect. The final two entries of Row 2 should be 01. In your matrix they are transposed as 10.

    Reply
  3. omar Raskolnikov says:
    2013/09/10 at 6:04 PM

    just wondering if n=10 is the only case witch the number of nodes is equal to the number of solutions.

    Reply

Leave a comment

←
→