3
$\begingroup$

Consider a subspace $C$ of $R^{n}$. How can I prove the following?

$C$ is invariant under $\pi$ if for any two vectors $a,b \in C$, $a\circledast b \in C$.

where $\pi :R^{n} \rightarrow R^{n}$ defined by $\pi(x_{1},x_{2},...,x_{n})=(x_{2},x_{3},...,x_{n}, x_{1})$

$\circledast $: circular convolution

$\endgroup$
9
  • 2
    $\begingroup$ This may sound silly but can you give the definition of circular convolution of two arbitrary vectors in $R^n$? Wikipedia seems to only give a definition for functions $\endgroup$
    – Vincent
    Aug 14, 2017 at 21:12
  • $\begingroup$ $c_{i}= \sum_{j} a_{j} b_{i-j}$ where $i,j= 0 ~to~ n-1$ $\endgroup$
    – Niki
    Aug 14, 2017 at 21:44
  • 2
    $\begingroup$ I find myself yearning to translate this into a question about the space of functions on a cyclic group of order $n$, where "circular convolution" is literal convolution-of-functions-on-a-group... Then $C$ is the translation effect on functions on the group (by generator $1$ of the group). Yes, group-algebra-invariant subspaces are the same as convolution-algebra-invariant subspaces... but this isn't quite what you're asking? Can you clarify? $\endgroup$ Aug 14, 2017 at 22:28
  • $\begingroup$ I'm not sure I understand the question (the set of vectors can be a subset of an invariant space, but also of a noninvariant superspace thereof), seems reasonable to look at this in the Fourier domain, where pi-invariant spaces are coordinate aligned and convolution is coordinate-wise multiplication. $\endgroup$ Aug 14, 2017 at 23:54
  • $\begingroup$ @YoavKallus, noninvariant superspace? $\endgroup$
    – Niki
    Aug 15, 2017 at 1:07

1 Answer 1

5
$\begingroup$

This isn't true. I follow Paul's suggestion of taking (discrete) Fourier transforms $\widehat{x}(\zeta)=\sum_{j=0}^{n-1} x_j\zeta^j$, $\zeta^n=1$. Then a subspace closed under convolution becomes one closed under pointwise multiplication, and $\widehat{\pi x} =\zeta^{-1}\widehat{x}$.

Now the subspace defined by the condition that $\widehat{x}(\zeta_1)=\widehat{x}(\zeta_2)$ is closed under multiplication, but won't be left invariant by multiplication by $\zeta$. We can make this more concrete, also to confirm that we can obtain real valued examples: Take $n=4$ and the subspace generated by (taking linear combinations of convolution powers of) $x=(1,-1,1,1)$. Notice that $\widehat{x}(1)=\widehat{x}(-1)=2$.

Alternatively, we can forget how we got this and just check directly that the subspace generated by $x$ is spanned by $e_1,x,e_3$, and this is not invariant under $\pi$.

$\endgroup$
10
  • $\begingroup$ Shorter still: "C = {(x0, x1, x2, -x1 )} is closed under circular convolution but not invariant under pi" $\endgroup$
    – user44143
    Aug 15, 2017 at 10:08
  • $\begingroup$ @christian, thanks for your response. May I ask you to explain your examples more? $\endgroup$
    – Niki
    Aug 15, 2017 at 11:55
  • $\begingroup$ @MattF. May I ask you to explain it more? $\endgroup$
    – Niki
    Aug 15, 2017 at 11:56
  • $\begingroup$ @Niki, what part of the comment needs explanation -- the definition of C, why it is closed under convolution, why it is not invariant under pi, or how this answers the question? $\endgroup$
    – user44143
    Aug 15, 2017 at 13:11
  • 1
    $\begingroup$ @Niki: If you don't like the first part about the FTs, then you can just check the claims directly: work out $x$, $x*x$, $x*x*x$, etc., show that the subspace $C$ spanned by these vectors has basis $e_1,e_3,x$, and finally observe that this $C$ is not $\pi$ invariant, but it is closed under convolution by construction (or check that directly, too). $\endgroup$ Aug 15, 2017 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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