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?