A convolution matrix is a matrix whose multiplication by a vector computes a discrete convolution.
For a vector 
and an input vector 
, where 
and 
are positive integers,
the full linear convolution is represented by an
matrix 
with entries
 |
(1)
|
where 
, ..., 
and 
, ..., 
. Thus 
,
with 
outside the range 
. The entries are constant
along each negative-sloping diagonal, so 
has Toeplitz structure
(MathWorks).
For example, the convolution of 
and 
is given by
![[a 0; b a; c b; 0 c][u; v]=[au; bu+av; cu+bv; cv].](/images/equations/ConvolutionMatrix/NumberedEquation2.svg) |
(2)
|
The zero padding distinguishes full linear convolution from circular convolution, in which indices wrap around and the corresponding matrix is a circulant matrix.
