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$:
It turns out that it is very important to know or determine if a system has certain characteristics, and among these is the classification of linearity. A system is
linear if it has two special properties:
scaling (sometimes called homogeneity) and
additivity . The first of these is satisfied if, for any arbitrary input $x$, scaling the input by any complex valued constant value $\alpha$ will result in the output being scaled by the same value. Mathematically, this scaling rule is represented as $H\{\alpha x\}=\alpha H\{x\}$, and as a system diagram it looks like this:
A system has the additivity property if, for any two arbitrary inputs, the output of the sum of them is the same as the sum of their individual outputs: $H\{x_1+x_2\}=H\{x_1\}+H\{x_2\}$ .
If a system lacks either of these properties, then it is said to be
nonlinear .
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.
