I am spinning this question off from the question from johnny. Matt L. and I have had directly opposite conclusions to johnny's question.

I want to decouple the question from issues of causality and other goofy stuff.

So we have a simple first-order recursive system described with time-domain I/O equation:

$$ y[n] = p \cdot y[n-1] \ + \ x[n] \quad \quad \forall n \in \mathbb{Z} $$

Of course, the Z-transform of this is

$$ Y(z) = p \cdot z^{-1} Y(z) \ + \ X(z) $$

and transfer function

$$ H(z) \triangleq \frac{Y(z)}{X(z)} = \frac{z}{z-p} $$

We would normally identify this as a simple and realizable LTI system with a zero at $0$ and a pole at $p$. But in the other question, there is an issue regarding linearity and time-invariance for the case when $p=-1 \ $.

For what values $p$ is this system linear? For what values $p$ is this system time-invariant?

This is, I believe, the kernel of the disagreement I have with Dr. Matt L.

  • $\begingroup$ If we expand it to its fir form. Theoretically the system is always linear. $\endgroup$
    – learner
    Oct 8 '14 at 18:32
  • $\begingroup$ okay @learner , so if $p=-1$, then MattL suggests you can have for input $x[n]=0 \ \forall n$ the output $$ y[n] = A (-1)^n \quad \forall A \in \mathbb{R} $$ including non-zero $A$. input is identically zero, output is non-zero. can that system be linear? $\endgroup$ Oct 8 '14 at 18:42
  • 1
    $\begingroup$ Please clarify: for what integers $n$ does the relationship $$y[n] = p \cdot y[n-1] \ + \ x[n]$$ hold? For all integers $n$? For $n \geq 0$? For $n > 0$? And in the latter two cases, please specify what is the value of $y[-1]$ (respectively $y[0]$) since we are agreed that $y[0]=-py[-1]+x[0]$ or $y[1]=-py[0]+x[1]$. $\endgroup$ Oct 9 '14 at 2:54
  • 1
    $\begingroup$ i had never placed a restriction on it. in the other question, i was explicit that $n\in\mathbb{Z}$. i should have said so here, but i neglected to. so i will modify the question. in my opinion, if not specified, the assumption is that there is no restriction. $\endgroup$ Oct 9 '14 at 5:00
  • $\begingroup$ and since $$ y[n] = \sum\limits_{i=-\infty}^{+\infty} h[i] x[n-i] $$ you can derive $y[0]$ or any other specific $y[n]$ from that. if you assume causality, you get a right-sided $h[n]$. if you assume anti-causality (which is not the way i stated the difference equation), you get a left-sided $h[n]$. in either case that affects one limit or the other for the convolution summation. $\endgroup$ Oct 9 '14 at 5:04

I don't know how the discussion arrived to this point but it is pretty convoluted to follow after this much of time. It is an ordinary difference equation with constant coefficients thus defines a linear, time invariant system. There is no need to pursue further from that if a unique solution exists. Here we have a problem with the emphasized part.

Let's first write the descriptor state space equations: the system is described by

$$ \begin{align} \begin{bmatrix}1&-1\\0&0\end{bmatrix} \begin{bmatrix}s_1[k+1]\\s_2[k+1]\end{bmatrix} &= \begin{bmatrix}p&0\\0&0\end{bmatrix} \begin{bmatrix}s_1[k]\\s_2[k]\end{bmatrix} + \begin{bmatrix}0\\1\end{bmatrix}x[k]\\ y[k] &= \begin{bmatrix}1&0\end{bmatrix} \begin{bmatrix}s_1[k]\\s_2[k]\end{bmatrix} +[1]x[k] \end{align} $$

Now this is where I think the problematic part is. This system, though being LTI, is not regular (relevant buzz words are regular, impulse-free, index-1 descriptor systems). In other words, there exists no $\lambda$ for which the expression $\det(\lambda E-A)$ is nonzero and hence one of the modes is $\frac{\bullet}{0}$ and in fact this is $\frac{0}{0}$ for this example. This means that our system has solution uniqueness issues, unlike the causal LTI system, there is no guarantee on the existence of a unique solution. There is no guarantee of an admissible solution for that matter(buzzword impulsive systems). Hence the LTI reasoning of the other answers won't cut it.

And this what causes the trouble as far as I can tell from Matt L's argument is that he found two nontrivially distinct solutions for the same system and concluded that this cannot be a linear system. But this also assumes the uniqueness and existence of a solution and initial conditions.

It only differs from the regular systems in the way that the uniqueness and existence guarantees of the standard LTI systems cannot be assumed. The models no longer can be assumed to have admissible trajectories for all possible signals.


The answer is no. In order to label a discrete-time system as LTI, we only look for its linearity and time invariance properties and don't need to care whether it is stable or not. That is another independent property of a system that can mutually co-exist with other properties. And indeed many LTI systems are unstable and they are still LTI systems. For abundance of examples please refer to Alan Oppenheim's book: Signals & Systems, 2ed, chapter 2. (or any other college text book on signals & and systems, or digital signal processing) Consider for example non stable IIR filters which are still linear and time invariant. (indeed your example is one such)

Coming to your LCDDE that is supposed define a recursive discrete time system, as you may know, the LCDDE itself is not enough to uniquely specify a solution, as you also need a set of auxiliary conditions (initial conditions). Without those initial conditions explicitly set, you can neither solve the equation, nor determine whether the system it represents will be LTI or causal. Because for some initial conditions, it may be non causal, non linear and time varying, while for some other set (namely the initial rest conditions) it will be linear, time invariant and causal. Therefore in order for a single LCCDE to uniquely represent a LTI system its initial conditions must be properly set to initial rest and not arbitrarily...


Linearity and time-invariance do not depend on the value of $p$. The two possible linear and time-invariant (LTI) systems described by the difference equation

$$y[n]=p\cdot y[n-1]+x[n]\tag{1},\quad p\neq 0$$

are given by the inverse $\mathcal{Z}$-transform of the transfer function as formulated in the question:


Note that (2) does not uniquely define an impulse response unless the region of convergence (ROC) of $H(z)$ is given. For the transfer function (2), there are two possible ROCs: $|z|>|p|$ and $|z|<|p|$. In the first case, the corresponding impulse response is right-sided and corresponds to a causal LTI system:


where $u[n]$ is the unit step function. If we choose $|z|<|p|$ as the ROC, we get a left-sided impulse response corresponding to an anti-causal system:


If $|p|<1$ then the causal LTI system characterized by $h_1[n]$ is stable, and the anti-causal LTI system characterized by $h_2[n]$ is unstable, and if $|p|\ge 1$ the opposite holds.

So far we have seen that the difference equation (1) defines two LTI systems, one causal and the other one anti-causal. The two corresponding impulse responses $h_1[n]$ and $h_2[n]$ are solutions of the difference equation (1) for $x[n]=\delta[n]$. However, these are not the only solutions of (1). It is well-known from the theory of linear difference equations that the general solution is given by a particular solution for some given $x[n]$, and by a solution to the homogeneous equation defined by $x[n]=0$. For the given difference equation, the corresponding homogeneous equation is

$$y[n]=p\cdot y[n-1]\tag{5}$$

The solution of (5) is

$$y_h[n]=c\cdot p^n,\quad c\in \mathbf{R}\tag{6}$$

Now we can express the general solution of (1) (with $x[n]=\delta[n]$) by combining a particular solution (either $h_1[n]$ or $h_2[n]$) with $y_h[n]$:

$$y[n]=h_1[n]+y_h[n]=h_1[n]+c\cdot p^n\tag{7}$$

Note that the solution $h_2[n]$ can be obtained from (7) by choosing $c=-1$. Also note that (7) is valid for all $n\in\mathbf{Z}$.

If we were to scale the input signal and use $x_1[n]=a\delta[n]$ with some $a\in\mathbf{R}$, the resulting output would be

$$y_1[n]=a\cdot h_1[n]+c\cdot p^n\tag{8}$$

This output signal is generally not equal to $a\cdot y[n]$ (with $y[n]$ given by (7)), unless $c=0$ or $c=-1$. Consequently, the corresponding system is not linear. For the input signal $x_2=\delta[n-n_0]$ the output is

$$y_2[n]=h_1[n-n_0]+c\cdot p^n\tag{9}$$

which is generally not equal to $y[n-n_0]$ (again, unless $c=0$ or $c=-1$). So the corresponding system is also not time-invariant.

In sum, the difference equation (1) describes infinitely many systems with responses to the input signal $x[n]=\delta[n]$ given by (7). Only two of these systems are LTI, the others are not. The two LTI systems are described by the impulse responses $h_1[n]$ and $h_2[n]$ given by (3) and (4), respectively.

  • $\begingroup$ so, bottom line, the system described by this equation $$ y[n] = p \cdot y[n-1] \ + \ x[n] \quad \quad \forall n \in \mathbb{Z} $$ is not LTI. or not necessarily LTI. right? $$ \ $$ now, to simplify the discussion, can you agree that the reason you assert that it is not LTI is because with an input that is identically zero $$x[n]=0 \ \forall n \in \mathbb{Z}$$, that the output can be non-zero $$ y[n] = c \cdot p^n \ \forall n \in \mathbb{Z} $$ and $c \ne 0 \ $? $\endgroup$ Oct 9 '14 at 12:37
  • $\begingroup$ also, if $p=0$, might that be an exception to your initial assertion that "Linearity and time-invariance do not depend on the value of $p$"? $\endgroup$ Oct 9 '14 at 12:46
  • $\begingroup$ and lastly, are you are apparently denying that, even for a properly chosen $h[n]$, that $$ y[n] = \sum\limits_{i=-\infty}^{+\infty} h[i] x[n-i] $$ cannot be a general solution to $$ y[n] = p \cdot y[n-1] \ + \ x[n] \quad \quad \forall n \in \mathbb{Z} $$ or systems described similarly? $\endgroup$ Oct 9 '14 at 12:52
  • $\begingroup$ MattL, are you interested in addressing any of these questions? $\endgroup$ Oct 11 '14 at 20:01
  • $\begingroup$ @robertbristow-johnson: Yes, but you seem to ask many questions at the same time, and I feel that most of them have already been answered explicitly by my answer to your original question. But I'll give it a go ... $\endgroup$
    – Matt L.
    Oct 11 '14 at 20:53

I find this discussion intriguing and I wanted to add another viewpoint to the mix:

The system under consideration ( $y[n]=p⋅y[n−1] + x[n]$ ) can be thought of as a mapping from one (infinite dimensional) vector space to another. Let's call this this mapping $M$, and we can (initially) define it as:

$$ M : \mathbb{R}^\mathbb{Z} \rightarrow \mathbb{R}^\mathbb{Z} $$

This terminology says that $M$ is a mapping from $\mathbb{R}^\mathbb{Z}$ (the space of all real-valued functions of an integer variable) to $\mathbb{R}^\mathbb{Z}$.

If system has any zeros (and the system under consideration here has a zero at $z=1$), this means that our mapping $M$ is not one-to-one, because two different input signals will lead to the same output signal. For example, for any input signal, $x[n]$, we can say that $M(x)=M(x+\lambda)$ for any real $\lambda$.

The set of functions that are "zeros" of our system can be defined as:

$$K_{zeros}=\{f[n]=\lambda:\forall \lambda \in \mathbb{R}\}$$

Likewise, we note that if our system has any poles (and the system under consideration here has a zero at $z=-1$), then this means that the inverse mapping, $M^{-1}$ is not one-to-one. Specifically, $M^{-1}(x)=M^{-1}(x+\lambda(-1)^n)$ for any real $\lambda$.

The set of functions that are "poles" of our system can be defined as:

$$K_{poles}=\{f[n]=\lambda(-1)^n:\forall \lambda \in \mathbb{R}\}$$

Now, $\mathbb{R}^\mathbb{Z}$ is a vector space, $K_{zeros}$ is a vector space, and $K_{poles}$ is a vector space.

We can now define two quotient spaces (see Wikipedia for more information about quotient spaces):

$$ Q_{input} = \mathbb{R}^\mathbb{Z} / K_{zeros} $$

$$ Q_{output} = \mathbb{R}^\mathbb{Z} / K_{poles} $$

You can think of $Q_{output}$ as being the subset of $\mathbb{R}^\mathbb{Z}$ that does not contain any signal components of the form $\lambda(-1)^n$, or alternatively, you can think of $Q_{output}$ as being identical to $\mathbb{R}^\mathbb{Z}$ with equivalence classes that tell us "for our current application, we will consider any function $y[n]$ to be eqivalent to $y[n]+\lambda(-1)^n$ for any real $\lambda$"

By doing this, we can now redefine a new mapping $M'$ as a mapping from $Q_{input}$ to $Q_{output}$. This new mapping is really just the same as our old mapping, $M$, except we've reduced the vector-spaces on which it operates. Furthermore, this new mapping is now a bijection (it's "one-to-one" and "onto"), so it is guaranteed to also be invertible.

Finally, this mapping, $M'$ is linear.

So, the point of this whole rambling explanation is that, by defining the appropriate equivalence classes (or alternatively, by restricting our space of allowable functions to a sub-space of $\mathbb{R}^\mathbb{Z}$), we can maintain the property that our mapping should be linear (and time-invariant).

For example, the rules of linearity tell us that, if $x[n]$ is an input signal and $\alpha$ is any real scalar, then $M(\alpha x) = \alpha M(x)$. Hence, this implies that, by setting $\alpha=0$, we should therefore expect that $M(0\times x)=y[n]=0$ (i.e. if we input the zero-signal to our filter, the output should be $y[n]=0$).

However, we know that it's possible for have a situation where the input to the filter is zero, but the output is of the form $y'[n]=(-1)^n$, so we might be tempted to say "that proves our system is not linear, because $y'[n]$ is not zero". However, you will recall that the equivalence class we have enforced on the output vector space says that "for our current application, we will consider any function $y[n]$ to be eqivalent to $y[n]+\lambda(-1)^n$ for any real $\lambda$", which means that $y'[n]=(-1)^n$ is equivalent to zero!


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.