Skip to main content
improve LaTeX ($\gg$ and some missing dollars)
Source Link

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

Theorem 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$$m\gg0$, $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$.

Proof that 1) is equivalent to 2):

$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.

Proof that 2) implies 3): 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$.

Proof that 2) implies 4): Exactly as above, noting that $$H_{m,N+p}\cdot\pmatrix{q_0\cr\vdots\cr q_N\cr 0\cr \vdots\cr 0}=0$$

Proof that 4) implies 3): Trivial.

Proof that 3) implies 2):

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 areare done. Otherwise there are arbitrarily large values of $m$ with $|H_{m,N-1}|\neq 0$.

Claim: $|H_{m,N-1}|\neq 0$ for any m>M$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_{m,N}$ 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_{m,N}$,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).

Edited to add:

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

Theorem: 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)$$.$$\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).$$

Proof: 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.

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

Theorem 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$.

Proof that 1) is equivalent to 2):

$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.

Proof that 2) implies 3): 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$.

Proof that 2) implies 4): Exactly as above, noting that $$H_{m,N+p}\cdot\pmatrix{q_0\cr\vdots\cr q_N\cr 0\cr \vdots\cr 0}=0$$

Proof that 4) implies 3): Trivial.

Proof that 3) implies 2):

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 any 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_{m,N}$ 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_{m,N}$,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).

Edited to add:

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

Theorem: 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)$$.

Proof: 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.

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

Theorem 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\gg0$, $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$.

Proof that 1) is equivalent to 2):

$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.

Proof that 2) implies 3): 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$.

Proof that 2) implies 4): Exactly as above, noting that $$H_{m,N+p}\cdot\pmatrix{q_0\cr\vdots\cr q_N\cr 0\cr \vdots\cr 0}=0$$

Proof that 4) implies 3): Trivial.

Proof that 3) implies 2):

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 any $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_{m,N}$ 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_{m,N}$,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).

Edited to add:

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

Theorem: 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).$$

Proof: 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.

edited body
Source Link
Steven Landsburg
  • 23k
  • 5
  • 95
  • 153

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

Theorem 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$.

Proof that 1) is equivalent to 2):

$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.

Proof that 2) implies 3): 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$.

Proof that 2) implies 4): Exactly as above, noting that $$H_{m,N+p}\cdot\pmatrix{q_0\cr\vdots\cr q_N\cr 0\cr \vdots\cr 0}=0$$

Proof that 4) implies 3): Trivial.

Proof that 3) implies 2):

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 any 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}$$H_{m,N}$ 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}$$H_{m,N}$,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).

Edited to add:

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

Theorem: 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)$$.

Proof: 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.

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

Theorem 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$.

Proof that 1) is equivalent to 2):

$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.

Proof that 2) implies 3): 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$.

Proof that 2) implies 4): Exactly as above, noting that $$H_{m,N+p}\cdot\pmatrix{q_0\cr\vdots\cr q_N\cr 0\cr \vdots\cr 0}=0$$

Proof that 4) implies 3): Trivial.

Proof that 3) implies 2):

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 any 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).

Edited to add:

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

Theorem: 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)$$.

Proof: 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.

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

Theorem 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$.

Proof that 1) is equivalent to 2):

$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.

Proof that 2) implies 3): 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$.

Proof that 2) implies 4): Exactly as above, noting that $$H_{m,N+p}\cdot\pmatrix{q_0\cr\vdots\cr q_N\cr 0\cr \vdots\cr 0}=0$$

Proof that 4) implies 3): Trivial.

Proof that 3) implies 2):

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 any 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_{m,N}$ 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_{m,N}$,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).

Edited to add:

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

Theorem: 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)$$.

Proof: 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.

edited body
Source Link
Steven Landsburg
  • 23k
  • 5
  • 95
  • 153

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

Theorem 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$.

Proof that 1) is equivalent to 2):

$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.

Proof that 2) implies 3): 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$.

Proof that 2) implies 4): 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$$$$H_{m,N+p}\cdot\pmatrix{q_0\cr\vdots\cr q_N\cr 0\cr \vdots\cr 0}=0$$

Proof that 4) implies 3): Trivial.

Proof that 3) implies 2):

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 any 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).

Edited to add:

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

Theorem: 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)$$.

Proof: 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.

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

Theorem 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$.

Proof that 1) is equivalent to 2):

$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.

Proof that 2) implies 3): 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$.

Proof that 2) implies 4): 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$$

Proof that 4) implies 3): Trivial.

Proof that 3) implies 2):

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 any 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).

Edited to add:

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

Theorem: 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)$$.

Proof: 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.

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

Theorem 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$.

Proof that 1) is equivalent to 2):

$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.

Proof that 2) implies 3): 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$.

Proof that 2) implies 4): Exactly as above, noting that $$H_{m,N+p}\cdot\pmatrix{q_0\cr\vdots\cr q_N\cr 0\cr \vdots\cr 0}=0$$

Proof that 4) implies 3): Trivial.

Proof that 3) implies 2):

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 any 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).

Edited to add:

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

Theorem: 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)$$.

Proof: 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.

deleted 6 characters in body
Source Link
Steven Landsburg
  • 23k
  • 5
  • 95
  • 153
Loading
edited body
Source Link
Steven Landsburg
  • 23k
  • 5
  • 95
  • 153
Loading
added 1 character in body
Source Link
Steven Landsburg
  • 23k
  • 5
  • 95
  • 153
Loading
added 917 characters in body
Source Link
Steven Landsburg
  • 23k
  • 5
  • 95
  • 153
Loading
Source Link
Steven Landsburg
  • 23k
  • 5
  • 95
  • 153
Loading