How to prove if a recursive system is linear?

[Bipolarity]

Not sure if this is the right subforum.

This is technically a signal processing question, but it edges on proving whether a certain mapping is linear or non-linear, so I thought I'd post it here.

Say a digital system is defined in the following way:
$y[n] = 5*y[n-2]$

How might I prove that this system is linear?
In algebra, one usually proves it by showing that:
$L(x[n]+c*z[n]) = L(x[n]) + c*L(z[n])$

The problem here is that since the system is defined recursively, there are no input functions x, or rather the input to the system is the output. So how might this work?

Also, similarly, how might I prove time-invariance (I'm not sure if this system is even time-invariant by the way, but I think it is!).

Thanks!

BiP

 

[micromass]

In this case, it doesn't look too difficult to find an explicit (non-recursive) formula for $y$.

It will be something like $y[n] = 5^n y[0]$ or similar.

 

[Bipolarity]

In this case, it doesn't look too difficult to find an explicit (non-recursive) formula for $y$.

It will be something like $y[n] = 5^n y[0]$ or similar.

Right, but it turns out that in general,
$y[n] = y[n-k]$ is in fact linear and time-invariant for any integer k.

So how might I prove this general case micro?

BiP

 

[micromass]

Right, but it turns out that in general,
$y[n] = y[n-k]$ is in fact linear and time-invariant for any integer k.

So how might I prove this general case micro?

BiP

Wait, I'm actually not sure what you mean with linear in this case. You have a function

y:\mathbb{N}\rightarrow \mathbb{R}

that satisfies some conditions like $y[n] = y[n-k]$. What does it mean for $y$ to be linear? Have you seen some definition of that?

 

[Bipolarity]

Wait, I'm actually not sure what you mean with linear in this case. You have a function

y:\mathbb{N}\rightarrow \mathbb{R}

that satisfies some conditions like $y[n] = y[n-k]$. What does it mean for $y$ to be linear? Have you seen some definition of that?

That's what I'm worried about. I haven't really seen the definition, and my professor doesn't define stuff very clearly (that's the problem with non-mathematics professors!).

Whatever linear means in this context, I am sure it is linear because in signal processing we always have systems such as:
$y[n] = x[n-1] + 3*y[n-1]$ all of which are linear and time-invariant. In fact, if these types of systems weren't linear, many of the filters we use today wouldn't really work, because important results, like the convolution theorem, would not apply to non-linear systems.

Thanks for your help though. I'm still hoping a math/EE hybrid PF veteran might provide some insight on the matter.

BiP

 

[jbunniii]

In signal processing, we consider mappings from one sequence to another sequence. Thus if we use the somewhat annoying notation $S = \mathbb{R}^{\mathbb{N}}$ to mean the space of real-valued sequences, then we are interested in mappings from $S$ to $S$. If the mapping is linear, we often call it a linear operator. Linearity has the usual meaning: the mapping $L : S \rightarrow S$ is linear if $L(au + bv) = aL(u) + bL(v)$ for all $u,v\in S$ and all $a,b\in \mathbb{R}$. (We can of course use $\mathbb{C}$ or some other field in place of $\mathbb{R}$.)

Note that the recurrence relation $y[n] = y[n-k]$ does not define a mapping from $S$ to $S$. Indeed, it doesn't even give us enough information to define a unique sequence unless we are given some initial conditions such as the values of $y[0],y[1],\ldots,y[k-1]$. If we have this information, however, we may consider it as "input" information and define linearity to mean that if the initial conditions $y[0],y[1],\ldots,y[k-1]$ yield a particular solution $y[n]$, and a different set of initial conditions $y'[0],y'[1],\ldots,y'[k-1]$ yield another solution $y'[n]$, then the initial conditions $ay[0]+by'[0],\ldots,ay[k-1]+by'[k-1]$ yield the solution $ay[n] + by'[n]$.

 

[Bipolarity]

In signal processing, we consider mappings from one sequence to another sequence. Thus if we use the somewhat annoying notation $S = \mathbb{R}^{\mathbb{N}}$ to mean the space of real-valued sequences, then we are interested in mappings from $S$ to $S$. If the mapping is linear, we often call it a linear operator. Linearity has the usual meaning: the mapping $L : S \rightarrow S$ is linear if $L(au + bv) = aL(u) + bL(v)$ for all $u,v\in S$ and all $a,b\in \mathbb{R}$. (We can of course use $\mathbb{C}$ or some other field in place of $\mathbb{R}$.)

Note that the recurrence relation $y[n] = y[n-k]$ does not define a mapping from $S$ to $S$. Indeed, it doesn't even give us enough information to define a unique sequence unless we are given some initial conditions such as the values of $y[0],y[1],\ldots,y[k-1]$. If you wish to view $y$ as the "output" of some mapping, then you must relate it in some way to an "input" in order to even define a mapping, let alone to ask whether that mapping is linear.

So for example, the recurrence relation $y[n] = y[n-1] + x[n]$, along with some initial condition such as $y[0] = c$, defines a linear operator $L : S \rightarrow S$, such that $L(x) = y$. The initial condition is needed because without it, the mapping is not well defined: given $x$ and $y$ which satisfy the recurrence relation, we see that $x$ and $y+c$ also satisfy the relation, for any constant $c$.

Beautiful response! Thanks!
Given an initial condition, the recurrence relation determines a unique system or mapping, which can then be shown to be linear, correct?

BiP

 

[jbunniii]

Beautiful response! Thanks!
Given an initial condition, the recurrence relation determines a unique system or mapping, which can then be shown to be linear, correct?

BiP

I just edited my response, please take a look at the updated version. I defined a notion of linearity that makes sense for a system of the form $y[n] = y[n-k]$, provided you give enough initial conditions to produce a unique solution. It is analogous to the definition of linearity for differential equations in the absence of a "forcing function" (input).

 

[Bipolarity]

I just edited my response, please take a look at the updated version. I defined a notion of linearity that makes sense for a system of the form $y[n] = y[n-k]$, provided you give enough initial conditions to produce a unique solution. It is analogous to the definition of linearity for differential equations in the absence of a "forcing function" (input).

I see it! Thanks!

BiP

 

[jbunniii]

Just to fill in a bit more detail about the linearity, we can write the recurrence $y[n] = y[n-k]$ in the more suggestive form $y[n] - y[n-k] = 0$. Then define $L(y) = y - D_k y$, where $D_k$ shifts $y$ by $k$: $D_k y[n] = y[n-k]$. Our recurrence becomes simply $L(y) = 0$. Linearity has its usual meaning: $L(ay + by') = aL(y) + bL(y')$.

 

[jbunniii]

I think I should have explained this better. I blame the late hour when I was posting last night. Continuing with my previous notation, a general linear system may look like
$$L(y) = M(x)$$
where $L$ and $M$ are linear operators on $S$. In your special case, $M$ happens to be the zero operator (which is of course trivially linear).

Now as long as $L$ and $M$ are both linear, we can solve the system. We might naively like to write $y = L^{-1} M(x)$. But $L$ may not be invertible. Indeed, your system is not invertible, because $L(y) = 0$ has solutions other than $y = 0$.

Fortunately, we can overcome this problem. You were hoping for a math/EE hybrid explanation. Let me see if I can provide one.

Let $N$ denote the set of all $y$ such that $L(y) = 0$. We call $N$ the null space of $L$. We may now partition $S$ into equivalence classes: two elements $y_1, y_2 \in S$ are considered equivalent if they differ by an element of $N$. We denote the set of all such equivalence classes by $S/N$. This is a standard mathematical object called a quotient space. An element of $S/N$ is written as $s + N$, where $s$ is some element of $S$, and $N$ is the null space. By $s + N$ we simply mean the set of all elements of the form $s + n$ where $n \in N$.

OK, so what do we do with this quotient space? Well, there's a wonderful theorem of linear algebra (and abstract algebra in general) called the first isomorphism theorem, which allows us to convert our non-invertible linear map $L$, which maps from $S$ to $S$, into an invertible linear map which we'll call $\bar{L}$, which maps from $S/N$ to $S$. Then instead of writing $L(y)$, we may instead write $\bar{L}(y+N)$, and these give the same answer, except that $\bar{L}$ has a (left) inverse. So now we may solve our system:
$$L(y) = M(x)$$
becomes
$$\bar{L}(y + N) = M(x)$$
and we may invert $\bar{L}$ to obtain
$$y + N = \bar{L}^{-1} M(x)$$
Note that the solution is of the form $y + N$ instead of $y$. This simply means that we may add any element of $N$ to $y$ and obtain another solution. If we want a unique solution, then in general we must apply constraints (initial conditions). This is completely analogous to what we learn in elementary differential equations: the general solution consists of a particular solution plus any solution to the "homogeneous" equation $L(y) = 0$.

Note that since $\bar{L}^{-1}$ and $M$ are both linear, so is $\bar{L}^{-1} M$, so we have a linear relation between the input $x$ and the output $y$.

Computing $\bar{L}^{-1} M$ is another story, since the operators are usually infinite-dimensional so they aren't representable by matrices. Often in signal processing, we work with linear operators which are also time invariant, i.e. if we shift the input then the output is shifted by the same amount but otherwise unchanged. The action of a time-invariant linear operator on $x$ has a nice representation as the convolution of $x$ with a kernel $h$, often called the impulse response in signal processing. With this representation, we have many standard techniques available for solution, for example Fourier analysis or more general power series representations.

 

[Bipolarity]

I think I should have explained this better. I blame the late hour when I was posting last night. Continuing with my previous notation, a general linear system may look like
$$L(y) = M(x)$$
where $L$ and $M$ are linear operators on $S$. In your special case, $M$ happens to be the zero operator (which is of course trivially linear).

Now as long as $L$ and $M$ are both linear, we can solve the system. We might naively like to write $y = L^{-1} M(x)$. But $L$ may not be invertible. Indeed, your system is not invertible, because $L(y) = 0$ has solutions other than $y = 0$.

Fortunately, we can overcome this problem. You were hoping for a math/EE hybrid explanation. Let me see if I can provide one.

Let $N$ denote the set of all $y$ such that $L(y) = 0$. We call $N$ the null space of $L$. We may now partition $S$ into equivalence classes: two elements $y_1, y_2 \in S$ are considered equivalent if they differ by an element of $N$. We denote the set of all such equivalence classes by $S/N$. This is a standard mathematical object called a quotient space. An element of $S/N$ is written as $s + N$, where $s$ is some element of $S$, and $N$ is the null space. By $s + N$ we simply mean the set of all elements of the form $s + n$ where $n \in N$.

OK, so what do we do with this quotient space? Well, there's a wonderful theorem of linear algebra (and abstract algebra in general) called the first isomorphism theorem, which allows us to convert our non-invertible linear map $L$, which maps from $S$ to $S$, into an invertible linear map which we'll call $\bar{L}$, which maps from $S/N$ to $S$. Then instead of writing $L(y)$, we may instead write $\bar{L}(y+N)$, and these give the same answer, except that $\bar{L}$ has a (left) inverse. So now we may solve our system:
$$L(y) = M(x)$$
becomes
$$\bar{L}(y + N) = M(x)$$
and we may invert $\bar{L}$ to obtain
$$y + N = \bar{L}^{-1} M(x)$$
Note that the solution is of the form $y + N$ instead of $y$. This simply means that we may add any element of $N$ to $y$ and obtain another solution. If we want a unique solution, then in general we must apply constraints (initial conditions). This is completely analogous to what we learn in elementary differential equations: the general solution consists of a particular solution plus any solution to the "homogeneous" equation $L(y) = 0$.

Note that since $\bar{L}^{-1}$ and $M$ are both linear, so is $\bar{L}^{-1} M$, so we have a linear relation between the input $x$ and the output $y$.

Computing $\bar{L}^{-1} M$ is another story, since the operators are usually infinite-dimensional so they aren't representable by matrices. Often in signal processing, we work with linear operators which are also time invariant, i.e. if we shift the input then the output is shifted by the same amount but otherwise unchanged. The action of a time-invariant linear operator on $x$ has a nice representation as the convolution of $x$ with a kernel $h$, often called the impulse response in signal processing. With this representation, we have many standard techniques available for solution, for example Fourier analysis or more general power series representations.

Thank you so much!
I'm curious, what textbook would provide a similar explanation as you have provided? It seems most texts I have seen on signals fail to prove the theorems with rigor. What you have done is beautiful.

BiP

 

[jbunniii]

Thank you so much!
I'm curious, what textbook would provide a similar explanation as you have provided? It seems most texts I have seen on signals fail to prove the theorems with rigor. What you have done is beautiful.

Good question, I'm not sure I have seen one. The signal processing books are aimed at engineers, and they don't usually discuss the mathematical concepts very much, although they do a good job of explaining how to carry out the concrete calculations. Maybe have a look at a book on differential equations aimed at math students. Sorry, I can't recommend a good one offhand.