# inverse of an AR(1) or Laplacian(?) or Kac-Murdock-Szegö matrix

My current problem involves having an exact (symbolic) inverse of a scaled AR(1) matrix for n-dimension. (I don't know what this matrix would be called in general; I'm sure it is used often.) This is used as a smoothing prior on a function sampled on a uniform grid. For a 1-dimensional function, the matrix is

$C = \rho \begin{bmatrix} 1 & \alpha & \alpha^2 & \cdots & \alpha^n \\\\ \alpha & 1 & \alpha & \cdots & \alpha^{n-1}\\\\ \alpha^2 & \alpha & 1 & \\\\ \vdots & \vdots & & \ddots & \\\\ \alpha^n & \alpha^{n-1} & & & 1 \end{bmatrix}$

and I know the inverse which is,

$C^{-1} = \frac{1}{\rho(1-\alpha^2)} \begin{bmatrix} 1 & -\alpha & & & 0\\\\ -\alpha & 1+\alpha^2 & - \alpha \\\\ & -\alpha & 1+\alpha^2 &\ddots \\\\ & &\ddots & \ddots & -\alpha \\\\ 0 & & & -\alpha & 1 \end{bmatrix}$

(This can be also found in Kac, M., Murdock, W., and Szegö, G. (1953). On the eigenvalues of certain Hermitian forms. J. Rational Mech. Anal, 2:767–800.)

I would imagine that this can be generalized to higher dimensional case where the $\alpha$ now spreads in each direction. This would allow my uniformly sampled n-dimensional function to be smooth. Sort of having the form $$C_{(i,j),(k,l)} = \rho \alpha_x^{|i-k|} \alpha_y^{|j-l|},$$ But as a giant matrix for flattened function (the vec-operation; representing the n-dimensional function as a vector with some ordering). Can anybody recommend a book on such symbolic matrix inversions that would have this?

-
Your $C_{(i,j)(k,l)}$ is the Kronecker product of two $C$ matrices (with different constant $\alpha_x$ and $\alpha_y$. And $(A \otimes B)^{-1}=A^{-1}\otimes B^{-1}$.
If $C_{(i,j),(k,l)}=\rho \alpha_x^{∣i−j∣} \alpha_x^{∣k−l∣}$, then I would agree, but the indices are a bit mixed. Does it still hold? –  Memming May 24 '11 at 19:16
I think so, unless I'm totally misunderstanding your notation. The pair $(i,j)$ forms the row index of the large matrix, doesn't it? –  Federico Poloni May 24 '11 at 21:11
Correct. Well, $(i,j)$ for column, $(k,l)$ for row, but that's not important. The Kronecker product of $C_{i,k}$ and $C_{j,l}$ is correct. Thanks. –  Memming May 24 '11 at 22:04