# CNN - Is this a Toeplitz Matrix?

I have been reading through Chapter 9 of www.deeplearningbbook.org, where convolutional networks are being described.

The following image represents the output of a 2D convolution, without kernel flipping.

The book goes on to describe this matrix as a Toeplitz matrix where,

for univariate discrete convolution, each row of the matrix is constrained to be equal to the row above shifted by one element.

I fully understand this statement since w, x, y and z are constants in their respective columns with shifting elements.

However, there is no mention of diagonal-constants which are a key feature of such matrices. As per Wikipedia (link above) and several other sources:

a Toeplitz matrix or diagonal-constant matrix, named after Otto Toeplitz, is a matrix in which each descending diagonal from left to right is constant.

Going back to the image above, does this mean that, for instance, aw == cx == gy? How can this be ensured when all elements are different?

First of all, be assured that the kernel matrix (the 2x2 matrix in the figure) in CNN is not constrained to have its diagonal filled with a unique value, and is thus not a Toeplitz matrix.

"Discrete convolution can be viewed as multiplication by a matrix, but the matrix has several entries constrained to be equal to other entries"

This means that the global operation of passing a kernel on the input data of a CNN could be expressed as the multiplication of this input data by a matrix. i.e. by a large and sparse Toeplitz matrix.

Authors mention the illustrative simple case of univariate discrete convolution. In univariate discrete convolution, we would be applying a 1-D kernel matrix of length $$m$$ on 1-D input data of length $$n$$. Let us take n=10 and m=3. Doing the convolution could be done by multiplying the input vector data by a n*n matrix, whose diagonal would be composed of the 3 weights of the kernel, shifted of one column to the right at each new row.