Is a shift operator always linear?

Question

Let $S$ be a shift operator acting on the index of sequences $a_n$ in the sense $Sa_n=a_{n+1}$.

I have two questions regarding this definition.

1. Can $S$ be properly defined to have this property acting on ANY sequence, or is its definition bound to a particular sequence?

2. Is $S$ always a linear operator?

My thought's on it:

Let's define a sequence $$a_{2n}=a_n+a_{n-1} \\ a_{2n+1}=a_n-a_{n-1}.$$ Now let $S$ be universal in the sense of 1) and furthermore let $S$ to have the property as in 2) (so it is linear). Since $S$ is linear, we have $$Sa_{2n}=S\left(a_n+a_{n-1}\right) \\ a_{2n+1} =a_{n+1}+a_n = a_{2n+2}$$ but also $$Sa_{2n+1}=S\left(a_n-a_{n-1}\right) \\ a_{2n+2}=a_{n+1}-a_n=a_{2n+3}$$ which seems to me as a contradiction, because why - in general - should we have $a_{2n+1}=a_{2n+2}$? In particular, using the equality of the last two equations, we find $$a_{2n+2}=a_{n+1}+a_n=a_{n+1}-a_n \, ,$$ which means $a_n=0$ for all $n$.

So for this $S$ it doesn't seem to be linear, because there seems to exist a non-trivial solution to the defintion of the sequence. At the same time, since $S$ is universal, you could do the same thing on a sequence where the linearity would work out.

Any thoughts?

Answer 1

Let $X$ be any set, then we can define $$ \Sigma := X^{\mathbb{N}} = \{a = (a_n)_{n=0}^\infty \ | \ a_n \in X\}.$$ Let $\pi_n : \Sigma \rightarrow X$ be the projection map defined by $\pi_n(a) := a_n.$ The left-shift map is the map defined by the relationship $$S : \Sigma \rightarrow \Sigma, \ \ \pi_n \circ S = \pi_{n+1}.$$

Exercise: Show that the relationship gives rise to a well-defined function. (Hint: Show that $S(a) = b$, where $b_n = a_{n+1}$. Then show that if $a = b$, then $S(a) = S(b)$.)

Notice there's nothing about linearity here, since $\Sigma$ is not even a vector space (as $X$ is arbitrary).

Exercise: Suppose $X = V$ for some vector space over $\mathbb{F}$. Give $\Sigma$ a vector space structure in the "obvious" way (addition is componentwise, scaling is componentwise).

1. Show that $\pi_n : \Sigma \rightarrow V$ is a linear map.
2. Show that this forces $S$ to be linear by the above relationship.

In your example, you define the sequence $a := (a_n)_{n=1}^\infty$ where $a_{2n} = a_n + a_{n-1}$. When you write $$S(a_{2n}) = S(a_n + a_{n-1}),$$ this doesn't make sense, because $a_{2n} \in X$ not in $\Sigma$.

Edit: I think I know what you are getting at now. Let $(a_n)_{n=0}^\infty \in \Sigma$ be a fixed sequence and define $Y := (a_n)_{n=0}^\infty$. Notice this is a set of elements in the sequence. Consider $$ T : Y \rightarrow Y, \ \ T(a_n) := a_{n+1}.$$ This would be the left-shift map on a specific sequence. Notice how it doesn't fit into the same framework as the usual left-shift map, so we shouldn't expect anything about the usual left-shift map to apply to this map $T$. As an easy example, think about the sequence $$ a_n := \begin{cases} 1 \text{ if } n \text{ is even}, \\ 0 \text{ otherwise}.\end{cases}$$ In particular, in our set up we have $Y := \{0,1\}$ and the map $T$ is just given by $T(0) = 1$ and $T(1) = 0$ (alternatively: $T(x) = 1-x$). Observe $Y$ is not a vector space over $\mathbb{R}$, since it's not closed under addition or scaling. In particular, it doesn't make sense to talk about $T$ being linear in this context.

If we think about it as a vector space over $\mathbb{Z}/2\mathbb{Z}$, it does make sense, but it's a bit silly (and it's really restricted to just this example). Even if we modify this so that it is a vector space, $T$ fails to be linear, since $$1 = T(0) = T(0 \cdot 0) \neq 0 \cdot T(0) = 0 \cdot 1 = 0.$$

Other observations to make:

• $T$ in the above example also arises as the left shift map of the sequence $(0,1,0,1,\ldots)$, so it's not limited to just one sequence.
• If $S(x) = x$ or $S \circ S(x) = x$, then $T$ is a well-defined map on just this sequence. However, outside of these examples, $T$ fails to be well-defined. Take the sequence $(0,0,1,0,0,1,\ldots)$. Then $Y := \{0,1\}$, and $T(0)$ could be either $0$ or $1$ (however $T(1)$ is always $0$). You can fix this by attaching an index to the points in $Y$, so instead of $Y$ you think about $$Y' := \{(x,n) \ | \ x \in Y, n \in \mathbb{N}, \text{ and } a_n = x),$$ but you'll see very quickly this is not a vector space, so $T$ defined on this space still fails to be linear (and if you go this route, you'll see $T$ really depends on the sequence).

I've thought about it a bit and I don't see the advantage of studying $T$ over $S$, except that it's giving you some information about a particular sequence. Even then, I think any information you get from $T$ you could also get from studying the orbit of a sequence under $S$.

Answer 2

You are being deceived by notation. $S$ is always a linear operator, on any space of sequences you like. What does that mean exactly?

$$S(a_1, a_2, a_3, \ldots ) = (a_2, a_3, \ldots)$$

Your recurrence relation can be written as an equation in terms of sequences,

$$(a_2, a_4, a_6, \ldots) = (a_1, a_2, a_3, \ldots) + (a_0, a_1, a_2, \ldots)$$

You can certainly apply a shift to this equation, and it will give you the right answer, since $S(a_2, a_4, a_6, \ldots) = (a_4, a_6, \ldots)$ and so on. You just get one less equation. Your implicit claim that $S$ should just "increase the index by 1" or whatever is just not accurate. If it's not clear, imagine the sequence instead of the index.