What is this Toeplitz like matrix called and how do I represent it as a convolution? 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?
 A: Horchler's answer is wrong. T is not equal to the matrix you have written (let's call it $M$).
$$T = \left[\begin{array}{cccccc}0&1&2&1&1.4142135623731&2.23606797749979\\1&0&1&2&1&1.4142135623731\\2&1&0&1&2&1\\1&2&1&0&1&2\\1.4142135623731&1&2&1&0&1\\2.23606797749979&1.4142135623731&1&2&1&0\end{array}\right]$$
As you can see the $\sqrt{2},\sqrt 5$ not in same place

Your matrix $M$ is however block-Toeplitz with the 3x3 sub blocks:
$$M_1 = \left[\begin{array}{ccc}0&1&2\\1&0&1\\2&1&0\end{array}\right]$$
$$M_2 = \left[\begin{array}{ccc}1&\sqrt{2}&\sqrt{5}\\\sqrt{2}&1&\sqrt{2}\\\sqrt{5}&\sqrt{2}&1\end{array}\right]$$
$$M = \left[\begin{array}{cc}M_1&M_2\\M_2&M_1\end{array}\right]$$
Which you can write with for example Kronecker products ($\otimes$)
$$M = I_2 \otimes {M_1} + ({\bf 11}^T - I_2)\otimes M_2$$
In Gnu Octave or Matlab:
kron(eye(2),toeplitz([0,1,2])) + kron(1-eye(2),toeplitz([1,sqrt(2),sqrt(5)]))

A: 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.
