I was discussing a programming competition problem with one of my math professors in Linear Algebra that reads as follows:
A matrix is an $r\times c$ array of numbers, where $r$ is the number of rows and $c$ is the number of columns. Given two matrices $M_1$ and $M_2$ with dimensions $r_1\times c_1$ and $r_1\times c_2$, respectively, their multiplication, $M_1M_2$, is defined only if the number of columns, $c_1$, in $M_1$ is equal to the number of rows, $r_2$ , in $M_2$. The matrix resulting from $M_1M_1$ will have $r_1$ rows and $c_2$ columns. Similarly, $M_2M_1$ is defined only if $c_2=r_1$. In this case, the resulting matrix will have dimensions $r_2\times c_1$. Given a list of matrix dimensions, your job is to determine whether or not some combination of all the matrices can be successfully multiplied together.
The actual solution presented after the competition made use of dynamic programming techniques to solve it in polynomial time... but this professor of mine, having not seen the problem before, thought that it could be converted into a graph problem where each node in the graph represented a matrix, and there was a directed edge between two nodes if their matrix product was defined. He then posited that you just needed to find a Hamiltonian path through the graph... After mentioning to him that the Hamiltonian path problem is NP-Hard, he says "Not if it's a digraph".
Is he mistaken, or am I missing something?
It sounds like the professor is confused.
Finding Hamiltonians in a directed graph is certainly just as NP-hard as finding them in an undirected one. If you have an efficient solver for digraph Hamiltonians and an undirected graph, just replace edge with a pair of edges going in both directions, and feed the resulting graph to your assumed digraph solver.
The obvious graph representation of the problem is to construct a (directed multi)graph where there is one vertex for each dimension, and an edge for each matrix, connecting its horizontal dimension with its vertical one.
The problem is then just to find out whether this directed graph has an Eulerian path, which is quite a bit easier than finding a Hamiltonian one.
Dynamic programming doesn't seem to be needed here -- just check that (1) the graph is connected, and (2) every vertex has indegree equal to outdegree, except possibly for two vertices having a degree unbalance of $\pm 1$.