Call your displayed matrix $H_{M,N}$.

<b>Theorem</b> The following are equivalent:

1.  $u$ is the Taylor series of a rational function.

2.  There is a finite sequence $q_0,\ldots, q_N$, not all zero, such that for all $m>>0$, $a_mq_N+a_{m+1}q_{N-1}+\cdots+a_{m+N}q_0=0$.

3.  There exists  $N$ and $M$ such that $|H_{m,N}|=0$ for all $m>M$.

4.  There exists $M$ and $N$ such that $|H_{m,n}|=0$ for all $m>M$ and $n>N$.

<b>Proof that 1) is equivalent to 2):</b>

$u$ is rational iff there is a polynomial $q$ with $qu$ a polynomial.  Taking the $q_i$ to be the coefficients of $q$, we are done.

<b>Proof that 2) implies 3):</b>  Suppose $a_mq_N+\cdots+a_{m+N}q_0=0$ for all $ m>M$.  Then for all $m>M$,  $H_{m,N}$ kills the column vector $\pmatrix{q_0&q_1&\ldots&q_N}^T$, so  $|H_{m,N}|=0$.

<b>Proof that 2) implies 4):</b> Exactly as above, noting that 
$$H_{m,N+p}\cdot\pmatrix{b_0\cr\vdots\cr b_N\cr 0\cr \vdots\cr 0}=0$$

<b>Proof that 4) implies 3):</b>  Trivial.

<b>Proof that 3) implies 2):</b>

Let $N$ be the smallest number with the property that there exists $M$ with $|H_{m,N}|=0$ for all $m>M$.  If $M=1$, then $u$ is a polynomial and we  are done.  Otherwise there are arbitrarily large values of $m$ with $|H_{m,N-1}|\neq 0$.  

Claim:  $|H_{m,N-1}|\neq 0$ for <i>any</i> m>M.  Proof of claim:  Let $m>M$.  It is pretty easy to check that
$$|H_{m,N-1}||H_{m+2,N-1}|=|H_{m+1,N-1}|^2+|H_{m,N}||H_{m+2,N-2}|$$
(I'll come back and insert a proof of this displayed equation when I have a little more time.)
By assumption, $|H_{m,N}|=0$, so $|H_{m,N-1}|=0$ would imply $|H_{m+1,N-1}|=0$, whence by induction $|H_{m+p,N-1}|>0$ for all $p>0$, contradicting the last line of the preceding paragraph.  This proves the claim.

Continue to assume $m>M$.  

Note that $H_{m,N}$ is an $(N+1)\times (N+1)$ matrix of determinant zero that contains a nonsingular $N\times N$ submatrix (namely $H_{m,N-1}$) and hence has rank precisely $N$.  Thus there is a unique (up to linear multiples) column vector $\overline{q}$ such that 
$$H_{m,N}\overline{q}=0$$
 
Then $\overline{q}$ is the unique (again up to scalar multiples) column vector killed by the top $n$ rows of $H_{n,M}$ and also the unique column vector killed by the bottom $n$ rows.  Now since $H_{m+1,N}$ is also rank 1, and because its kernel must be killed by the bottom $n$ rows of $H_{n,M}$,it follows that the kernel is again generated by the same vector $\overline{q}$, and by induction $\overline{q}$ is killed by $H_{m+p,N}$ for all $p\ge 0$, so that in particular  $a_{m+p}b_0+\cdots+a_{m+p+N}b_N=0$ for all $p>0$, which, modulo a change of notation, is 2).

<b>Edited to add:</b>

The displayed equation above is a special case of the following:

<b>Theorem</b>:  Let $a,b,c,d$ be scalars. Let $\alpha,\beta$ be row vectors of length $n$.   Let $\phi,\psi$ be columns of length $n$.  Let $B$ be an $n\times n$ matrix.  Let $A$ be the following $(n+2)\times(n+2)$ matrix:
$$A=\pmatrix{a&\alpha&b\cr\phi&B&\psi\cr c&\beta&d\cr}$$
Then
$$det\pmatrix{a&\alpha\cr\phi& B\cr}\cdot det\pmatrix{B&\psi\cr \beta &d\cr}
=det\pmatrix{\alpha&b\cr B&\psi\cr} det\pmatrix{\phi&B\cr c&\beta\cr}+det(A)\cdot det(B)$$.

<b>Proof:</b>  We can assume $B$ is invertible and then premultiply $A$ by 
$$\pmatrix{1&0&0\cr 0&B^{-1}&0\cr 0&0&1\cr}$$
where the zeroes represent scalars, rows or columns as appropriate.  This does not affect the truth of the theorem and allows us to assume $B$ is the identity, after which row and column operations render the desired equality trivial.