The most basic and powerful operation for linear discrete-time system
analysis, control, and design is discrete-time convolution. We first define
the discrete-time unit impulse, also known as the Kronecker delta function,
as

**Derivation of the Convolution Sum**

We first define a complete set of orthogonal basis functions by

If the system is linear but time varying, we denote the response to an impulse
at

By a change of variables, one can easily show that the convolution sum can
also be written

Convolution is used analytically analyze linear systems and it can also be used to calculate the output of a system by only knowing its impulse response. This is a very powerful tool because it does not require any detailed knowledge of the system itself. It only uses one experimentally obtainable response. However, this summation cannot only be used to analyze or calculate the response of a given system, it can be an implementation of the system. This summation can be implemented in hardware or programmed on a computer and become the signal processor.

**The Matrix Formulation of Convolution**

Some of the properties and characteristics of convolution and of the systems
it represents can be better described by a matrix formulation than by the
summation notation. The first

If the input sequence

Although the formulation of constructing the matrix from the impulse response of the system and having it operate on the input vector seems most natural, the matrix could have been formulated from the input and the vector would have been the impulse response. Indeed, this might the appropriate formulation if one were specifying the input and output and designing the system.

The basic convolution defined in
(Equation 1), derived in
(Equation 2), and given in
matrix form in (Equation 3)
relates the input to the output for linear systems. This is the form of
convolution that is related to multiplication of the DTFT and z-transform of
signals. However, it is cyclic convolution that is fundamentally related to
the DFT and that will be efficiently calculated by the fast Fourier transform
(FFT) developed in Part III of these notes. Matrix formulation of length-L
cyclic convolution is given by

This matrix description makes it clear that the matrix operator is always
square and the three signals,

There are several useful conclusions that can be drawn from linear algebra [1]. The eigenvalues of the non-cyclic are all the same since the eigenvalues of a lower triangular matrix are simply the values on the diagonal.

Although it is less obvious, the eigenvalues of the cyclic convolution matrix
are the

The matrix form of the length-N cyclic convolution in (3.10) is written

Taking the DFT both sides and using the IDFT on

An important practical question is how one calculates the non-cyclic
convolution needed by system analysis using the cyclic convolution of the DFT.
The answer is easy to see using the matrix description of

If fewer zeros or none had been appended to