Discrete-time systems are mathematical transformations that take input signals and map them to output signals. For a given input $x$, a discrete-time system will produce a new signal $y$:
Determining linearity
Consider again the definition of linearity; to be linear, a system must preserve the scaling and additivity properties for any arbitrary input. Therefore, determining linearity amounts to completing a mathematical proof that assumes an arbitrary input (or two inputs, for additivity) and the conditions of property in question, and then shows the necessary result. Suppose $H\{x[n]\}=3x[n]$. Here is how the additivity proof would look:Let $x_1$ and $x_2$ be arbitrary inputs to system $H$. $\begin{align*}H\{x_1[n]\}&=3x_1[n]\\H\{x_2[n]\}&=3x_2[n]\\H\{x_1[n]+x_2[n]\}&=3(x_1[n]+x_2[n])\\&=3x_1[n]+3x_2[n]\\&=H\{x_1[n]\}+H\{x_2[n]\} \end{align*}$
Now, to show a system is nonlinear requires a different kind of proof. Rather than having to prove both of the properties hold for any arbitrary input(s), only a single example needs to be provided for which either of the properties fail. For example, consider the system $H\{x[n]\}=x[n]+1$. We can show it is nonlinear thus: $\begin{align*}\textrm{Let } x[n]&=0\\ H\{x[n]\}&=x[n]+1\\&=0+1\\&=1\\ \textrm{But } H\{2x[n]\}&=2x[n]+1\\&=2\cdot 0+1\\&=1\\&\neq 2 H\{x[n]\}\rightarrow \textrm{Nonlinear}\end{align*}$
Good students of signals and systems must become adept at determining the linearity (or nonlinearity) of systems. Practice on the system examples below; which of them are linear?
- Identity: $y[n] = x[n]$
- Scaling: $y[n] = 2\, x[n]$
- Offset: $y[n] = x[n]+2$
- Square signal: $y[n] = (x[n])^2$
- Shift: $y[n] = x[n+m]\quad m\in Z$ \]
- Decimate: $y[n] = x[2n]$
- Square time: $y[n] = x[n^2]$
- Moving average (combines shift, sum, scale): $y[n] = \frac{1}{2}(x[n]+x[n-1])$
- Recursive average: $y[n] = x[n]+ \alpha\,y[n-1]$
- Identity: $y[n] = x[n]$ Linear
- Scaling: $y[n] = 2\, x[n]$ Linear
- Offset: $y[n] = x[n]+2$ Nonlinear
- Square signal: $y[n] = (x[n])^2$ Nonlinear
- Shift: $y[n] = x[n+m]\quad m\in Z$ Linear
- Decimate: $y[n] = x[2n]$ Linear
- Square time: $y[n] = x[n^2]$ Linear
- Moving average (combines shift, sum, scale): $y[n] = \frac{1}{2}(x[n]+x[n-1])$ Linear
- Recursive average: $y[n] = x[n]+ \alpha\,y[n-1]$ Linear
Linear systems and matrix multiplication
One of the interesting characteristics of linear systems is that the systems' input/output relationship can be expressed as a matrix multiplication (note that this is distinct from the notion of using matrix multiplication to express one signal as a linear combination of others [LINK]). In fact, this relationship is actually an identity: any linear system can be expressed as a matrix multiplication, and matrix multiplications are linear systems. Below is how to represent any linear system mathematically, either in matrix multiplication notation,$y ~=~ {\bf H}\, x$ or, in summation notation:$y[n] ~=~ \sum_m \: [{\bf H}]_{n,m} \, x[m] ~=~ \sum_m \: h_{n,m} \, x[m]$ (where $h_{n,m} ~=~ [{\bf H}]_{n,m}$ represents the row-$n$, column-$m$ entry of the matrix $\bf H$).This matrix multiplication can be understood in two ways. First, the multiplication means that each value in the vector $y$ is the inner product of the corresponding row of $H$ with the vector $x$. Or, equivalently, the vector $y$ can be seen as a weighted sum of the columns of $H$, with the values in the vector $x$ being the weights of the corresponding columns. Below is a picture of matrix multiplication, with different colors representing different values. Try to comprehend the multiplication with both perspectives.