# Elementary proof of Fourier domain formula of multidimensional downsampling by $M$

I am trying to prove a well-know formula for the multidimensional downsampling by arbitrary downsampling integer matrix $M$ in $d$-dimensional case. The formula is

$$\hat{y}(\omega)=\frac{1}{\textrm{det}(M)}\sum_{k\in \mathcal{N}(M^T)}\hat{x}\left(M^{-T}(\omega-2\pi k)\right)$$ where $\omega\in\mathbb{R}^d$, $y[n]=x[Mn]$ for $n\in\mathbb{Z}^d$, $M^{-T}=(M^T)^{-1}$ and $\mathcal{N}(M^T)=\{ M^Tt; t\in [0,1)^d\}\cap\mathbb{Z}^d$. The key step of the proof is to prove the following equation

$$\frac{1}{\textrm{det}(M)}\sum_{k\in \mathcal{N}(M^T)}\exp\left(-2i\pi m^TM^{-1}k\right)=\begin{cases}1\quad & m\in\mathcal{L}(M^T) \\ 0\quad &m\notin\mathcal{L}(M^T),m\in\mathbb{Z}^d \end{cases}$$ where $\mathcal{L}(M^T)=\{M^Tn;n\in\mathbb{Z}^d\}$. The $1$-dimensional case of this equation $$\frac{1}{M}\sum_{k=0}^{\textrm{M}-1}\exp\left(-2i\pi \frac{mk}{M}\right)=\begin{cases}1\quad & m|M=0 \\ 0\quad &m|M\neq0 \end{cases}$$ is simple to prove because $m$ is a sequence of integer numbers and the sum can be calculated using geometric series sum formula. But for $d$-dimensional, $m$ is a set of vectors which I can't see a pattern from. I learnt a kind of advanced proof from the problem $12.29$, page 657, multirate systems and filter banks by Vaidyanathan. It uses delta function and fourier transform to prove the second equation. I think it will be more appealing to use a elementary approach similar to $1$-dimensional case to prove it. Any tips?

• It's been a while; but I think this was the "trick" (don't be angry if it isn't): your "key step" formula is equivalent to (for all $m\in\mathcal L$) $\det(M) = \sum e^{-2j\pi m^T M^-1 k}$; these complex exponentials happen to be the eigenvectors of the interpolation $M^{-1}$, i.e. dirac impulses just at $t=km$. The determinant is the product of all eigenvalues. – Marcus Müller Aug 21 '16 at 14:40
• @MarcusMüller I'm not familiar with the relationship between eigenvectors and dirac impulses. Can you explain more? It seems your idea is close to the one in the book. – Hua Aug 21 '16 at 14:55
• Very very roughly: in time domain, the interpolation criterion says that the output at $mt$ must be the input at $t$ for any integer $t$ and the interpolation factor $m$. So, we know that vectors with only one entry at these $mt$ positions are eigenvectors of the inverse operation, the decimation. Now, transform these vectors using the DFT: you'll get $e^{-j2\pi mtk}$ – Marcus Müller Aug 21 '16 at 15:00
• take a look at this (Eq 13) research.ibm.com/people/r/rameshg/… – msm Sep 10 '16 at 0:43
• @msm Thanks for this. Actually I read this before and it employs the key equation I mentioned in my post without proof. – Hua Sep 10 '16 at 10:23