Eigenvalues and Fourier Transform

MTHSC 985 Spring 2001 Clemson University
Topics on Computational Algebra Instructor: Shuhong Gao
Lecture 14, March 5 Scribe: Jira Limbupasiriporn

Let ${\mathbb F}$ be an algebraically closed field. Suppose ${\mathbf I}\subset {\mathbb F}[x_1, \dots, x_n]$ is a radical ideal with V(I) finite, say $V(I) = \{P_1, \dots, P_t\}$. There are polynomials $f_1,\dots,f_t \in {\mathbb F}[x_1, \dots, x_n]$ such that

$$f_i(P_j) = \begin{cases} 1, &\mbox{if $i = j$ ,} \\ 0, &\mbox{if $i \neq j$ .} \end{cases}$$

Let ${\mathbf R}={\mathbb F}[x_1, \dots, x_n]/{\mathbf I}$. Then we have by Theorem 13.3 that

$$\dim_{\mathbb F}({\mathbf R}) = \vert V({\mathbf I})\vert =t$$

and $f_1, \dots, f_t$ form a basis for R over ${\mathbb F}$ with

$$\begin{eqnarray*}f_i^2 & \equiv & f_i \pmod{{\mathbf I}} \quad \mbox{for} \quad ... ...& \equiv & 0 \pmod{{\mathbf I}} \quad \mbox{for} \quad i \neq j. \end{eqnarray*}$$

This implies that every $f \in {\mathbf R}$ can be represented uniquely as

$$f \equiv a_1f_1 + \dots + a_tf_t \pmod{{\mathbf I}} \quad \mb... ...ere $a_i=f(P_i) \in {\mathbb F}$\space for $1\leq i \leq t$ .}$$

For any $g\in {\mathbf R}$, define a map $g:{\mathbf R}\longrightarrow {\mathbf R}$ by

$$f\mapsto g\cdot f \pmod{{\mathbf I}}$$

where $g\cdot f$ is the multiplication of f by g in the ring R. This map is a linear map on R as a vector space over ${\mathbb F}$.

Recall that a scalar $\lambda \in {\mathbb F}$ is called an eigenvalue of g if

$$g\cdot f \equiv \lambda f \pmod{{\mathbf I}}$$

for some nonzero $f \in {\mathbf R}$; such an f is called an eigenvector of g associated with $\lambda$.

Theorem 14.1   For any $g\in {\mathbf R}$, the eigenvalues of g as a linear map are

$$g(P_1), \dots, g(P_t)$$

with eigenvectors $f_1, \dots, f_t$, respectively. Furthermore, if some of $g(P_1), \dots, g(P_t)$are equal, say $g(P_1)= \cdots = g(P_k)=\lambda$ but $g(P_j) \ne \lambda$ for j> k, then $f_1, \ldots, f_k$ form a basis for the eigenspace of $\lambda$.

Proof. Write g as

$$g \equiv \lambda_1f_1 + \dots + \lambda_t f_t \pmod{{\mathbf I}}$$

where $\lambda _i = g(P_i)$ for $1\leq{i}\leq{t}$. Then

$$\begin{eqnarray*}g \cdot f_i & \equiv & (\lambda_1 f_1 + \dots + \lambda_t f_t) ... ...{{\mathbf I}} \\ & \equiv & \lambda_i f_i \pmod{{\mathbf I}}. \end{eqnarray*}$$

Hence g(P_i) is an eigenvalue of g with eigenvector f_i for $1\leq{i}\leq{t}$.

Now suppose that

$$g\cdot f \equiv \lambda f \pmod{{\mathbf I}}$$

for some $\lambda \in {\mathbb F}$ and a nonzero $f \in {\mathbf R}$. We show that $\lambda =g(P_i)$ for some $1\leq{i}\leq{t}$. Write f as

$$f=a_1f_1+ \dots +a_tf_t$$

where $a_i \in {\mathbb F}$. Then we have

$$\begin{eqnarray*}g \cdot f &\equiv & (\lambda_1 a_1)f_1 + \dots + (\lambda_t a_t... ... (\lambda a_1)f_1 + \dots + (\lambda a_t)f_t \pmod{{\mathbf I}}. \end{eqnarray*}$$

Since $f_1, \cdots, f_t$ is a basis for R over ${\mathbb F}$,

$$g\cdot f \equiv \lambda f \pmod{{\mathbf I}}\quad \mbox{if a... ... a_i = \lambda a_i \quad \mbox{for all} \quad 1 \leq i \leq t.$$ (16)

As $f \not \equiv 0$, at least one of a_i is nonzero, so $\lambda = \lambda_i =g(P_i)$ for some i. Therefore $g(P_1), \dots, g(P_t)$ are all the eigenvalues of g.

The equation (17) tells us even more. If some of $\lambda_1, \dots, \lambda_t$ are equal, say $\lambda_1 = \cdots = \lambda_k= \lambda$ but $\lambda_j \ne \lambda$ for j > k, then $f_1, \cdots, f_k$ are eigenvectors of $\lambda$. Now (17) implies that a_j=0 for j>k, so f is a linear combination of $f_1, \cdots, f_k$. This means that $f_1, \cdots, f_k$ form a basis for the eigenspace of $\lambda$. $\Box$

Now, fix a monomial order on ${\mathbb F}[x_1, \dots, x_n]$. Let B=B(I) be as defined in the previous lectures. By Lemma 11.5, we know that the monomials $x^\alpha , \alpha \in B$, form a basis for R. This basis can be computed by a Gröbner basis under the same monomial order. Also, we know from Theorem 13.3 that

$$\vert V({\mathbf I})\vert=\vert B({\mathbf I})\vert=\dim_{\mathbb F}({\mathbf R}).$$

Let $B=\{\alpha_1, \dots, \alpha_t\}$. Then for any $g\in {\mathbf R}$we can compute

$$g \cdot x^{\alpha _i} \equiv \sum_{j=1}^t g_{ij} x^{\alpha _j} \pmod{{\mathbf I}}$$

where $g_{ij} \in {\mathbb F}$. So

$$g \cdot \left( \begin{array}{c} x^{\alpha_1}\\ \vdots \\ x^... ...\vdots \\ x^{\alpha_t} \end{array}\right) \pmod{{\mathbf I}}.$$

where $G=\left( g_{ij} \right)$ is a $t\times t$ matrix over ${\mathbb F}$. We want to see the relationship of the eigenvectors of g and those of the matrix G.

Recall that if $Gv=\lambda v$ for $\lambda \in {\mathbb F}$ and some nonzero column vector v then $\lambda$ is called an eigenvalue of G and van eigenvector of G associated with $\lambda$. On the other hand, if $uG=\lambda u$ where u is a nonzero row vector, then $\lambda$ is called a right eigenvalue of G and u a right eigenvector of G associated with $\lambda$.

Express $f_1, \cdots, f_t$ in the monomial basis $x^{\alpha_1}, \cdots, x^{\alpha_t}$:

$$f_i \equiv \sum_{j=1}^{t} w_{ij} x^{\alpha_j}, \ \ 1 \leq i \leq t,$$

where $w_{ij} \in {\mathbb F}$. Let W=(w_ij). Then

$$\begin{pmatrix}f_1\cr \vdots \cr f_t \end{pmatrix}= W \begin{pmatrix}x^{\alpha_1}\cr \vdots \cr x^{\alpha_t}\end{pmatrix}.$$

Note that

$$g\cdot \begin{pmatrix}f_1\cr \vdots \cr f_t \end{pmatrix}\eq... ...nd{pmatrix}\begin{pmatrix}f_1\cr \vdots \cr f_t \end{pmatrix},$$

and

$$g\cdot \begin{pmatrix}f_1\cr \vdots \cr f_t \end{pmatrix}= g\... ...{pmatrix}f_1\cr \vdots \cr f_t \end{pmatrix}\pmod{{\mathbf I}},$$

we have

$$W G W^{-1} = \begin{pmatrix}g(P_1) & \cr & \ddots & \cr &... ...atrix}g(P_1) & \cr & \ddots & \cr & & g(P_t) \end{pmatrix}W.$$ (17)

We see that the row vectors of W, which correspond to the f_i, are the right eigenvectors of G.

Corollary 14.2   Let g and G be defined as above. Then the right eigenvalues of G are g(P_i), $1\leq{i}\leq{t}$, with the row vectors of W as its right eigenvectors.

We can also express $x^{\alpha_1}, \cdots, x^{\alpha_t}$ in the orthogonal basis $f_1, \cdots, f_t$:

$$x^{\alpha_i} \equiv \sum_{j=1}^{t} m_{ij} f_j, \ \ 1 \leq i \leq t,$$

where $m_{ij} = P_j^{\alpha_i} \in {\mathbb F}$, the value of the polynomial $x^{\alpha_i}$ evaluated at the point x=P_j. For example, if $\alpha_1=(2,1,0,0,2,0)$ and P₁ = (1,2,3,4,5,0), then $x^{\alpha_1} = x_1^2x_2x_5^2$ and $P_1^{\alpha_1} = 1^2 \cdot 2 \cdot 5^2 =50$. Let M=(m_ij). Then

$$\begin{pmatrix}x^{\alpha_1}\cr \vdots \cr x^{\alpha_t}\end{pmatrix}= M \begin{pmatrix}f_1\cr \vdots \cr f_t \end{pmatrix}.$$

Since M and W are the transformation matrices between the two bases, we have M=W^-1. By the equation (17),

$$G M = M \begin{pmatrix}g(P_1) & \cr & \ddots & \cr & & g(P_t) \end{pmatrix}.$$ (18)

This means that the columns of M are eigenvectors of G.

Corollary 14.3   Let g and G be defined as above. Then the (left) eigenvalues of G are g(P_i), $1\leq{i}\leq{t}$, with (left) eigenvectors

$$(P^{\alpha _1}_i, P^{\alpha _2}_i, \dots, P^{\alpha _t}_i)^{tr}, \ \ 1\leq i\leq t,$$

respectively.

If we pick $g\in {\mathbf R}$ such that $g(P_1), \cdots, g(P_t)$ are distinct then all the eigenspaces of G have dimension one. The right eigenvectors of G corresponds to the special functions $f_1, \cdots, f_t$ and computing them is equivalent to interpolation. While the (left) eigenvectors of Gcorrespond to the vectors $(P^{\alpha _1}_i, P^{\alpha _2}_i, \dots, P^{\alpha _t}_i)^{tr}$ determined by points in V(I) and computing them is equivalent to finding points in V(I).

Fourier transform. The Fourier transform on R is just the transform between the two bases $x^{\alpha_1}, \cdots, x^{\alpha_t}$ and $f_1, \cdots, f_t$. More specifically, the forward Fourier transform is

$$a = (a_1, \cdots, a_t) \in {\mathbb F}^t \longrightarrow aM =(\hat{a}_1, \cdots, \hat{a}_t)=\hat{a}.$$ (19)

The inverse Fourier transform is

$$a =(a_1, \cdots, a_t)= \hat{a} W \longleftarrow \hat{a} = (\hat{a}_1, \cdots, \hat{a}_t) \in {\mathbb F}^t.$$ (20)

One should check that in R

$$\sum_{i=1}^{t} a_i x^{\alpha_i} = \sum_{i=1}^{t} \hat{a}_i f_i.$$

The forward Fourier transform can be computed as

$$\hat{a}_i = f(P_i), \ \ \ 1 \leq i \leq t,$$

where $f=\sum_{i=1}^{t} a_i x^{\alpha_i}$. Is there a similar relation for the inverse Fourier transform?

In the special case when ${\mathbf R}={\mathbb C}[x]/(x^n-1)$, the above Fourier transform agrees with the usual Fourier transform discussed in most textbooks (especially those on signal processing, where convolution corresponds to multiplication in ${\mathbb C}[x]/(x^n-1)$).

Question. What does Parseval Equality (or Plancherel Theorem) means in the general situation when ${\mathbf R}={\mathbb F}[x_1, \dots, x_n]/{\mathbf I}$?