Reference to an explicit formula for the Hadamard product of two rational generating functions

Question

It is a theorem that if two sequences $\{f_n\}_{n=0}^\infty$ and $\{g_n\}_{n=0}^\infty$ have generating functions $f(x) = \sum_{n=0}^\infty f_n x^n$ and $g(x) = \sum_{n=0}^\infty g_n x^n$ that can be expressed as rational functions $f(x) = p_1(x)/q_1(x)$ and $g(x)=p_2(x)/q_2(x)$, then the Hadamard product of these two sequences, i.e. the sequence $\{h_n\}_{n=0}^\infty$ with $h_n = f_n g_n$ for all $n \geq 0$, has a generating function $h(x) = \sum_{n=0}^\infty h_n x^n$ that also can be expressed as a rational function $h(x) = p(x)/q(x)$. An existing thread here, "Algorithm for computing Hadamard product of two rational generating functions" outlines a explicit procedure to explicitly calculate the coefficients of the polynomials $p(x)$ and $q(x)$ from the coefficients of the polynomials $p_1(x)$, $q_1(x)$, $p_2(x)$, and $q_2(x)$.

Does anyone know a citation to a paper or a textbook in which the procedure given in that thread (or any procedure like it) is given completely explicitly and also completely proven, as opposed to being just outlined? I have not had any luck in finding such a citation, but I feel that there must be one out there.

Answer 1

I assume you're referring to my answer here. Unfortunately I'm not aware of a reference; I checked Stanley's Enumerative Combinatorics Vol. I and Flajolet and Sedgewick's Analytic Combinatorics and couldn't find this result in either of those.

If you need this in a paper I think the result is short enough to prove in an appendix. Here is a slightly longer sketch: 

Lemma 1. A sequence $f_n$ has a rational generating function $F(x) = \sum_{n \ge 0} f_n x^n = P(x) / Q(x)$ where $\deg P < \deg Q$ iff $f_n$ can be written as a finite sum of the form $\sum_{i=1}^d p_i(n) \lambda_i^n$ where the $p_i(n)$ are polynomials and the $\lambda_i$ are complex numbers. If $F(x) = \frac{P(x)}{Q(x)}$ in lowest terms then the $\lambda_i$ are the reciprocals of the roots of $Q(x)$.

This result is part of Theorem 4.1.1 in Stanley. The degree requirement corresponds to requiring that $f_n$ satisfy a linear recurrence relation with no exceptions; if you relax it then you get sequences that satisfy a linear recurrence relation with finitely many exceptions and the statements and proofs are a tiny bit messier but don't require any substantive changes.

Lemma 2a. If $M$ and $N$ are two square matrices with eigenvalues $\lambda_i$ and $\mu_j$ then the Kronecker product $M \otimes N$ has eigenvalues $\lambda_i \mu_j$.

I actually don't know a reference for this. It's a bit trickier to prove than it seems; the obvious argument involving taking Kronecker products of eigenvectors does not completely finish it off because we have to take into account algebraic multiplicities. But we can prove the result for diagonalizable matrices and then argue that it must be true for all matrices by a density argument (Euclidean or Zariski, either will work). 

Lemma 2b (corollary of 2a). If $Q_1(x)$ is a polynomial with roots $\lambda_i$ and $Q_2(x)$ is a polynomial with roots $\mu_j$ then the polynomial $Q(x)$ of degree $\deg Q_1 \deg Q_2$ with roots $\lambda_i \mu_j$ is $\det (x - M \otimes N)$ where $M$ and $N$ are any matrices with eigenvalues $\lambda_i$ and $\mu_j$, such as the companion matrices of $Q_1(x)$ and $Q_2(x)$.

Now let $f_n$ be a sequence with a rational generating function $F(x)$ as in Lemma 1 (satisfying the degree requirement for simplicity) and let $g_n$ be another such sequence with a rational generating function $G(x)$. By Lemma 1 we can write

$$f_n = \sum_{i=1}^d p_i(n) \lambda_i^n, g_n = \sum_{j=1}^e q_j(n) \mu_j^n.$$

Then the Hadamard product

$$f_n g_n = \sum_{(i, j) = (1, 1)}^{(d, e)} p_i(n) q_j(n) \lambda_i^n \mu_j^n$$

also has a rational generating function $H(x)$ (by a second application of Lemma 1; this is Proposition 4.2.5 in Stanley, where he proves that the Hadamard product of rational generating functions is rational but doesn't elaborate on how to compute this product), and the denominator of $H(x)$ has roots the reciprocals of $\lambda_i \mu_j$, so can be computed using Lemma 2b.