1
$\begingroup$

I want to inverse a very particular matrix numerically. The matrix is always symmetric and circulant.

As an example of a 4x4 matrix I would want to inverse \begin{pmatrix} v_0 & v_1 & v_2 & v_1 \\ v_1 & v_0 & v_1 & v_2 \\ v_2 & v_1 & v_0 & v_1 \\ v_1 & v_2 & v_1 & v_0 \end{pmatrix}

for a matrix of size 5x5, we have: \begin{pmatrix} v_0 & v_1 & v_2 & v_2 & v_1\\ v_1 & v_0 & v_1 & v_2 & v_2\\ v_2 & v_1 & v_0 & v_1 & v_2\\ v_2 & v_2 & v_1 & v_0 & v_1\\ v_1 & v_2 & v_2 & v_1 & v_0 \end{pmatrix}

There must be a way to inverse them very quickly, but I don't know how

$\endgroup$

1 Answer 1

1
$\begingroup$

Let $C$ be an $n \times n$ circulant matrix, with first column $ c = (c_1, \dots, c_n)^T$. Let $D$ be its inverse. Since $C$ is circulant, so is its inverse, so $D$ is circulant. Let $D$'s first column be $d = (d_1, \dots, d_n)^T$.

If we know the whole first column $d$ of $D$, we know the whole of $D$, so it is enough to solve the system $$Cd = \begin{pmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{pmatrix}$$ to find $d$ and through that find $D$. Solving linear systems with a circulant matrix can be done quite fast, $O(n \log n)$, as described on the Wikipedia page for circulant matrices.

If $C$ is also symmetric, the inverse $D$ will also be symmetric. $C$'s first column will be $c = (c_0, c_1, c_2, \dots, c_i, c_{i-1}, \dots, c_1)^T$ with $i = \lfloor i /2 \rfloor$ and one $c_i$ "in the middle" of $c$ if $n$ is even, two if $n$ is odd.

This goes for the inverse, $D$ as well. So in the system $Cd = e_1$ some variables will be the same in $d$, which is a bit of a hassle. You could just solve it anyway, then make sure that your solution $d$ is correct (e.g. the second element is the same as the last element, etc. Maybe it always will be correct, I do not know).

But we can alter the matrix $C$ and the vector $d$ to get a smaller, nicer system. We cut down $d$ to half: $\tilde d = (c_0, c_1, \dots, c_i)^T$ and "fold" $C$ on itself. The folding of $C$ has to be done differently depending on if $n$ is even or odd.

For example, for $n = 4$ we transform: $$ C = \begin{pmatrix} c_0 & c_1 & c_2 & c_1 \\ c_1 & c_0 & c_1 & c_2 \\ c_2 & c_1 & c_0 & c_1 \\ c_1 & c_2 & c_1 & c_0 \end{pmatrix} \to \begin{pmatrix} c_0 & c_1 + c_1 & c_2 \\ c_1 & c_0 + c_2 & c_1 \\ c_2 & c_1 + c_1 & c_0 \\ \end{pmatrix} = \tilde C $$ where the fourth column has been added to the second and the fourth row has been removed (it would be the same as the second row). For $n = 5$: $$ C = \begin{pmatrix} c_0 & c_1 & c_2 & c_2 & c_1\\ c_1 & c_0 & c_1 & c_2 & c_2\\ c_2 & c_1 & c_0 & c_1 & c_2\\ c_2 & c_2 & c_1 & c_0 & c_1\\ c_1 & c_2 & c_2 & c_1 & c_0 \end{pmatrix} \to \begin{pmatrix} c_0 & c_1 + c_1 & c_2 + c_2 \\ c_1 & c_0 + c_2 & c_1 + c_2 \\ c_2 & c_1 + c_2 & c_0 + c_1 \\ \end{pmatrix} = \tilde C $$ where the fourth column has been added to the third column, the fifth column has been added to the second and the fourth and fifth row has been discarded.

So the difference between if $n$ is odd or even is if something is added to the last row in $\tilde C$.

You can the solve the system $\tilde C \tilde d = e_1$. Note that this system is no longer circulant, so you can not solve it in $O(\frac{n}{2} \log \frac{n}{2})$, but instead $O(\frac{n^3}{2^3})$ so if the solution for circulant matrices works fine, I would probably go with that.

$\endgroup$
2
  • $\begingroup$ I found that you can get a bisymmetric matrix $\tilde{C}$ if n is even and a symmetric matrix if n is odd... For the case n=4, you can add the second line to itself. For the case n=5, you can do the same with the second and third line to get a bisymmetric matrix. It would be worth digging int that way I think... $\endgroup$
    – yakoudbz
    Commented Apr 3, 2015 at 11:23
  • $\begingroup$ @yakoudbz, cool! I did some experiments with the solution just exploiting the circulant structure, and it seems to work okay. I am somewhat doubtful if you can do it faster than $O(n \log n)$. $\endgroup$
    – Calle
    Commented Apr 3, 2015 at 13:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .