Algebraic or Analytic Proof of a Polynomial Identity

299 Views Asked by At

Let $m$, $n$, and $r$ be integers with $0\leq r \leq \min\{m,n\}$. Define $$f_{m,n,r}(q):=\left(\prod_{j=1}^r\,\left(q^m-q^{j-1}\right)\right)\,\left(\sum_{\substack{{j_1,\ldots,j_r\in\mathbb{Z}_{\geq 0}}\\{j_1+j_2+\ldots+j_r\leq n-r}}}\,q^{\sum_{i=1}^r\,i\,j_i}\right)\,,$$ so that $$f_{n,m,r}(q)=\left(\prod_{j=1}^r\,\left(q^n-q^{j-1}\right)\right)\,\left(\sum_{\substack{{j_1,\ldots,j_r\in\mathbb{Z}_{\geq 0}}\\{j_1+j_2+\ldots+j_r\leq m-r}}}\,q^{\sum_{i=1}^r\,i\,j_i}\right)$$ as polynomials over $\mathbb{Z}$ in the variable $q$. Prove that $$f_{m,n,r}(q)=f_{n,m,r}(q)\,.$$

Here is a combinatorial proof of this identity. The polynomial $f_{m,n,r}(q)$ counts the number of $m$-by-$n$ matrices over $\mathbb{F}_q$ of rank $r$, when $q$ is a power of a prime natural number. Since the transpose map from $\text{Mat}_{m\times n}\left(\mathbb{F}_q\right)\to\text{Mat}_{n\times m}\left(\mathbb{F}_q\right)$ is a bijection that preserves rank, we conclude that the number of $n$-by-$m$ matrices over $\mathbb{F}_q$ of rank $r$ is also $f_{m,n,r}(q)$. Ergo, $f_{m,n,r}(q)=f_{n,m,r}(q)$ whenever $q$ is a prime power, whence the equality $f_{m,n,r}(q)=f_{n,m,r}(q)$ is indeed an identity in $\mathbb{Z}[q]$. See here.

1

There are 1 best solutions below

0
On BEST ANSWER

We conjecture that

$$f_{m,n,r}(z) = \left(\prod_{j=1}^r (z^m-z^{j-1})\right) \left(\prod_{j=1}^r (z^n-z^{j-1})\right) \frac{(-1)^r}{z^{r(r-1)/2}} \prod_{j=1}^r \frac{1}{1-z^j}.$$

If we can prove this we have the symmetry. We must show that

$$\left(\prod_{j=1}^r (z^n-z^{j-1})\right) \frac{(-1)^r}{z^{r(r-1)/2}} \prod_{j=1}^r \frac{1}{1-z^j} = [w^{n-r}] \prod_{j=0}^r \frac{1}{1-wz^j}.$$

The LHS is

$$\begin{align} &\left(\prod_{j=1}^r z^{j-1} \prod_{j=1}^r (z^{n-(j-1)}-1)\right) \frac{(-1)^r}{z^{r(r-1)/2}} \prod_{j=1}^r \frac{1}{1-z^j} \\&\phantom{aaaaaaa} = \left(\prod_{j=1}^r (z^{n-(j-1)}-1)\right) (-1)^r \prod_{j=1}^r \frac{1}{1-z^j} \\&\phantom{aaaaaaa} = (-1)^r \prod_{j=1}^r \frac{1}{1-z^j} \prod_{j=n-(r-1)}^n (z^j-1) \\&\phantom{aaaaaaa} = \prod_{j=1}^r \frac{1}{z^j-1} \prod_{j=n-(r-1)}^n (z^j-1).\end{align}$$

We are therefore tasked with showing that

$$\prod_{j=n-(r-1)}^n (z^j-1) = [w^{n-r}] \frac{1}{1-w} \prod_{j=1}^r \frac{z^j-1}{1-wz^j}.$$

This can be done by induction. We have for $r=1$

$$\begin{align}z^n-1 &= [w^{n-1}] \frac{1}{1-w} \frac{z-1}{1-wz} \\ &= [w^{n-1}]\left(\frac{z}{1-wz} - \frac{1}{1-w}\right) = z \times z^{n-1} - 1.\end{align}$$

For the induction step we have for the RHS by the induction hypothesis multiplying both sides of the equation for $r$ by $z^{n-r}-1$

$$(z^{n-r}-1) [w^{n-r}] \frac{1}{1-w} \prod_{j=1}^r \frac{z^j-1}{1-wz^j}.$$

The first piece here is

$$\frac{z^{n-r}}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{n-r+1}} \frac{1}{1-w} \prod_{j=1}^r \frac{z^j-1}{1-wz^j} \; dw.$$

Now put $w/z=v$ so that $dw = z\; dv$ to get

$$\begin{align} &\frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{1}{v^{n-r+1}} \frac{1}{1-vz} \prod_{j=1}^r \frac{z^j-1}{1-vz^{j+1}} \; dv \\&\phantom{aaaaaaa} = \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{1}{v^{n-r+1}} \prod_{j=1}^r \frac{z^j-1}{1-vz^{j}}\frac{1}{1-vz^{r+1}} \; dv.\end{align}$$

Now

$$\frac{1}{1-vz^{r+1}} - \frac{1}{1-v} = \frac{1}{1-v} \frac{1}{1-vz^{r+1}} \big(1-v-\left(1-vz^{r+1}\right)\big) \\ = v \frac{1}{1-v} \frac{z^{r+1}-1}{1-vz^{r+1}}$$

and we obtain

$$\begin{align} &\frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{1}{v^{n-r+1}} \frac{v}{1-v} \prod_{j=1}^{r+1} \frac{z^j-1}{1-vz^{j}} \; dv \\&\phantom{aaaaaaa} = \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{1}{v^{n-r}} \frac{1}{1-v} \prod_{j=1}^{r+1} \frac{z^j-1}{1-vz^{j}} \; dv.\end{align}$$

This is

$$[v^{n-(r+1)}] \frac{1}{1-v} \prod_{j=1}^{r+1} \frac{z^j-1}{1-vz^j}$$

and we are done.