What is this Toeplitz like matrix called and how do I represent it as a convolution?

Question

I have a matrix that is used to represent the Green's function in a popular class of fast E & M solvers (CG-FFT).

The matrix represents distances, that are later filled in using the appropriate function.

The matrix is of the the size $M N \times M N$ grid each row is the distance from each voxel on a 2-D grid to the next:

In Matlab, this looks something like:

m=3;n=2;
for c=1:n
    for r=1:m
        idx=r+(c-1)*m;
        [x,y]=meshgrid((1:n)-c,(1:m)-r);
        dist=sqrt(x.^2+y.^2);
        matrix(idx,:)=reshape(dist,1,[]);
    end
end
disp(matrix);

which yields:

     0    1.0000    2.0000    1.0000    1.4142    2.2361
1.0000         0    1.0000    1.4142    1.0000    1.4142
2.0000    1.0000         0    2.2361    1.4142    1.0000
1.0000    1.4142    2.2361         0    1.0000    2.0000
1.4142    1.0000    1.4142    1.0000         0    1.0000
2.2361    1.4142    1.0000    2.0000    1.0000         0

This kind of matrix looks almost Toeplitz, but the diagonal elements are mirrored rather than shifted.

Okay, what is this kind of matrix called, and certainly there must be a way to diagonalize it with something like the FFT?

Answer 1

Your matrix is a real symmetric Toeplitz matrix. In Matlab, your example can be generated more directly using the toeplitz function:

T = toeplitz([0 1 2 1 sqrt([2 5])])

You can use eigendecomposition via eig to diagonalize this as $T = V D V^{-1}$ (or $D = V^{-1} T V$) very easily:

[V,D] = eig(T);

where D is a diagonal matrix of eigenvalues and V is a matrix whose columns are the corresponding eigenvectors.