I know we can do (Discrete) Fourier Transform of vectors of polynomial coefficients. This is useful for example when multiplying polynomials, since convolution turns into multiplication in Fourier domain which reduces computational complexity.

But, what if we have a matrix where each element is a polynomial?

Is there some useful sense we can take the Fourier transform of this matrix?


Your question is unclear. With $F$ the DFT and $g\in \Bbb{C}[t]_{n-1}$ (the polynomials of degree $\le n-1$) then $F[g]_m = g(e^{-2i \pi m/n})$.

If $g,h,gh \in \Bbb{C}[t]_{n-1}$ then $F[gh]_m= F[g]_mF[h]_m$.

You are asking if something similar exists for $G \in M_k(\Bbb{C}[t]_{n-1})$, then yes it is $$F[G]_m = G(e^{-2i\pi m/n}) \in M_k(\Bbb{C})$$

With $\times$ the multiplication of matrix, if $G,H,G\times H \in M_k(\Bbb{C}[t]_{n-1})$ then $$F[G \times H]_m = F[G]_m \times F[H]_m$$

We still have the inverse DFT $$G(t) = \sum_{l=0}^{n-1} t^l\frac1n \sum_{m=0}^{n-1} G(e^{-2i\pi m/n})e^{2i \pi lm/n} $$

If you want to unify all the different degrees you'll need to look at $F[G](x) = G(e^{-2i \pi x}), G(t) = \sum_{l=0}^\infty t^l \int_0^1 G(e^{-2i\pi x}) e^{2i \pi l x}dx$

  • $\begingroup$ Sorry. I dont get it. $\endgroup$ – mathreadler Jul 10 '19 at 1:40
  • $\begingroup$ ??? You don't understand the first line, that the DFT of the coefficients of $g$ is $g(e^{-2i \pi m/n})$ ? $\endgroup$ – reuns Jul 10 '19 at 1:57
  • $\begingroup$ @mathreadler allo $\endgroup$ – reuns Jul 10 '19 at 18:57
  • 1
    $\begingroup$ correct me if I'm wrong reuns, but are you just stating mathematically how to perform the DFT on each polynomial element of the matrix? I think OP was asking for a use case. How can this be useful? In OP's example, DFT of the coefficients enables easier polynomial multiplication. What can the DFT of the matrix of polynomials be used for? $\endgroup$ – Zach Favakeh Jul 10 '19 at 19:24
  • 1
    $\begingroup$ @ZachFavakeh I don't see what you are asking. If you prefer words : The DFT of a vector of size $n$ is a vector of same length, a polynomial is the vector of its coefficients and its DFT is the vector obtained by evaluating the polynomial at $n$-th roots of unity. When taking many polynomials and putting them in a matrix or a vector it doesn't change those facts. The only point is that the obtained thing is compatible not only with entrywise multiplication (multiplication of polynomials, ie. convolution of the coefficients) but also with matrix multiplication. $\endgroup$ – reuns Jul 10 '19 at 19:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.