# To find the inverse of a special kind of matrix.

In a matrix analysis problem, I encountered the following special kind of matrix

$$\begin{bmatrix} 0 & 1 & a & a & a & a \\ 1 & 0 & a& a& a& a \\ a& a &0 & 1& a& a \\ a& a &1 & 0 & a& a \\ a & a & a & a &0 & 1\\ a & a & a & a &1 & 0 \end{bmatrix}$$

where $$a$$ is a positive integer.But this matrix is not a circulant matrix. It is not in my knowledge if this is any known form.

We can also search for inverses for the general form of the matrix for even order.

• wolframalpha.com/input/… – Matti P. Feb 12 at 10:07
• Is the dimension fixed to $(6 \times 6)$ or can it vary? – Bertrand Feb 12 at 10:08
• the matrix is block-circulant, with components that are also circulant (a "BCCB matrix"). I think this provides an answer stackoverflow.com/questions/17007587/… (If you can diagonalize, inverting is trivial). Essentially you diagonalize this by 2D DFT matrix (instead of the (1D) DFT matrix for circulant matrices) – Andreas H. Feb 12 at 10:14
• @Bertrand it can be any even order matrix – user8795 Feb 12 at 10:17

You can write it as a sum:

$$\begin{bmatrix} 0 & 1 & a & a & a & a \\ 1 & 0 & a & a & a & a \\ a & a & 0 & 1 & a & a \\ a & a & 1 & 0 & a & a \\ a & a & a & a & 0 & 1 \\ a & a & a & a & 1 & 0 \end{bmatrix} = \begin{bmatrix} -a & 1-a & 0 & 0 & 0 & 0 \\ 1-a & -a & 0 & 0 & 0 & 0 \\ 0 & 0 & -a & 1-a & 0 & 0 \\ 0 & 0 & 1-a & -a & 0 & 0 \\ 0 & 0 & 0 & 0 & -a & 1-a \\ 0 & 0 & 0 & 0 & 1-a & -a \end{bmatrix} + \begin{bmatrix} a \\ a\\ a \\ a \\ a \\ a \end{bmatrix}.\begin{bmatrix}1 \\ 1 \\ 1 \\ 1\\ 1 \\ 1 \end{bmatrix}^T$$ and then use the Sherman–Morrison formula to invert this sum of two matrices. The dimension of the matrix can be easily adapted.

This is a BCCB matrix (Block circulant with circulant blocks). We have

$$\mathbf A = \begin{pmatrix} \mathbf{C}_1 & \mathbf{C}_2 & \mathbf{C}_2 \\ \mathbf{C}_2 & \mathbf{C}_1 & \mathbf{C}_2 \\ \mathbf{C}_2 & \mathbf{C}_2 & \mathbf{C}_1 \\ \end{pmatrix}$$

with $$\mathbf C_1 = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$$ and $$\mathbf C_2 = \begin{pmatrix} a & a \\ a & a \end{pmatrix}$$. Clearly $$\mathbf A$$ is block-circulant and $$C_1$$ and $$C_2$$ are also circulant.

It can be diagonalized with the 2D DFT matrix (instead of the (1D) DFT matrix for ordinary circulant matrices). When it is diagonalized the inverse is readily obtained by inverting the elements in the diagonal matrix (any applying the inverse 2D DFT). Also one knows that it is invertable if and only if there are no zeros in the diagonal matrix.

Details can be found here.

• can you explain how are you partitioning the matrix into blocks? – user8795 Feb 12 at 10:51
• @user8795 Sure see my edit. – Andreas H. Feb 12 at 14:53
• Yes, I got it!! – user8795 Feb 12 at 14:55

Suppose your matrix is $$2n\times 2n$$. Let $$J=\pmatrix{0&1\\ 1&0},\ E=\pmatrix{1&1\\ 1&1}$$. Then your matrix can be written as $$M=\pmatrix{J&aE&\cdots&aE\\ aE&\ddots&\ddots&\vdots\\ \vdots&\ddots&\ddots&aE\\ aE&\cdots&aE&J}.$$ Note that $$\pmatrix{J&aE&\cdots&aE\\ aE&\ddots&\ddots&\vdots\\ \vdots&\ddots&\ddots&aE\\ aE&\cdots&aE&J} \underbrace{\pmatrix{pJ+qE&rE&\cdots&rE\\ rE&\ddots&\ddots&\vdots\\ \vdots&\ddots&\ddots&rE\\ rE&\cdots&rE&pJ+qE}}_{\text{educated guess for } M^{-1}} =\pmatrix{X&Y&\cdots&Y\\ Y&\ddots&\ddots&\vdots\\ \vdots&\ddots&\ddots&Y\\ Y&\cdots&Y&X},$$ where \begin{aligned} X&=J(pJ+qE)+(n-1)(aE)(rE)\\ &=pI+\left[q+2(n-1)ar\right]E,\\ Y&=(aE)(pJ+qE)+J(rE)+(n-2)(aE)(rE)\\ &=\left[ap+2aq+(2(n-2)a+1)r\right]E. \end{aligned} So, $$M^{-1}$$ can be found by solving the system of equations $$p=1$$, $$q+2(n-1)ar=0$$ and $$ap+2aq+(2(n-2)a+1)r=0$$. It is not hard to see that the solution is given by $$p=1,\qquad q=\dfrac{-2(n-1)a^2}{4(n-1)a^2-2(n-2)a-1},\qquad r=\dfrac{a}{4(n-1)a^2-2(n-2)a-1}.$$ (As $$a$$ is an integer, the denominator terms in $$q$$ and $$r$$ are odd numbers and hence they are never zero.)

• If I may ask, how did you arrive at that educated guess for $M^{-1}$? – Rodrigo de Azevedo Feb 13 at 12:38
• @RodrigodeAzevedo You may rewrite the $2n\times 2n$ matrix as $X=(J-aE)\cdot\widetilde{I}+(aE)\cdot\widetilde{E}$, where $\widetilde{I}$ and $\widetilde{E}$ are respectively the identity matrix and the all-one matrix in $M_n(R)$, where $R$ is the commutative ring generated by $J$ and $E$ and the symbol "$\cdot$" denotes "scalar" multiplication (but the "scalars" here are 2-by-2 matrices in $R$). By Cayley-Hamilton thm, we know that $X^{-1}$ is a polynomial in $X$. So, strictly speaking, one should try the general form $X^{-1}=(pJ+qE+rI)\cdot\widetilde{I}+(sJ+tE+uI)\cdot\widetilde{E}$. – user1551 Feb 13 at 13:25
• @RodrigodeAzevedo However, in view of the fact that $JE=EJ=E$ and $E^2=2E$, although not all linear combinations of $J$ and $E$ are invertible, there is a good chance that an expression of the form $X^{-1}=(pJ+qE)\cdot\widetilde{I}+(rE)\cdot\widetilde{E}$ is enough to create $I$s in the diagonal part of $XX^{-1}$ and $E$s in the off-diagonal part. – user1551 Feb 13 at 13:26

Let

$$\mathrm B := \begin{bmatrix} -a & 1-a\\ 1-a & -a\end{bmatrix}$$

whose inverse is

$$\mathrm B^{-1} = \frac{1}{1-2a} \begin{bmatrix} a & 1-a\\ 1-a & a\end{bmatrix}$$

We would like to compute the inverse of

$$\mathrm M := a 1_6 1_6^\top + (\mathrm I_3 \otimes \mathrm B)$$

where $$\otimes$$ denotes the Kronecker product. Using Sherman-Morrison,

$$\mathrm M^{-1} = \left( \mathrm I_3 \otimes \mathrm B^{-1} \right) - \frac{\left( \mathrm I_3 \otimes \mathrm B^{-1} \right) a 1_6 1_6^\top \left( \mathrm I_3 \otimes \mathrm B^{-1} \right)}{1 + a 1_6^\top \left( \mathrm I_3 \otimes \mathrm B^{-1} \right) 1_6}$$

where

$$\left( \mathrm I_3 \otimes \mathrm B^{-1} \right) 1_6 = \left( \mathrm I_3 \otimes \mathrm B^{-1} \right) \left( 1_3 \otimes 1_2 \right) = 1_3 \otimes \left( \mathrm B^{-1} 1_2\right) = \left( \frac{1}{1-2a} \right) 1_6$$

and

$$1_6^\top \left( \mathrm I_3 \otimes \mathrm B^{-1} \right) = \left( \left( \mathrm I_3 \otimes \mathrm B^{-\top} \right) 1_6 \right)^\top = \left( \left( \mathrm I_3 \otimes \mathrm B^{-1} \right) 1_6 \right)^\top = \left( \frac{1}{1-2a} \right) 1_6^\top$$

Hence,

\begin{aligned} \mathrm M^{-1} &= \left( \mathrm I_3 \otimes \mathrm B^{-1} \right) - \frac{1}{(1- 2 a)^2} \left(\frac{a}{1 + \left( \frac{6a}{1-2a} \right)}\right) 1_6 1_6^\top \\ &= \left( \mathrm I_3 \otimes \mathrm B^{-1} \right) - \frac{a}{(1 - 2 a) (1 + 4 a)} 1_6 1_6^\top \end{aligned}

Using SymPy:

>>> from sympy import *
>>> a = Symbol('a', real=True, positive=True)
>>> M = Matrix([[0,1,a,a,a,a],
[1,0,a,a,a,a],
[a,a,0,1,a,a],
[a,a,1,0,a,a],
[a,a,a,a,0,1],
[a,a,a,a,1,0]])
>>> B = Matrix([[ -a,1-a],
[1-a, -a]])
>>> M_inv = TensorProduct(eye(3), B**-1) - (a / ((1+4*a) * (1-2*a))) * ones(6,6)


Verifying if the inverse was computed correctly:

>>> simplify(M * M_inv)
Matrix([
[1, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0],
[0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 1]])


Indeed, it was. Factoring out $$1 - 2 a$$ and $$1 + 4 a$$:

>>> simplify((1-2*a) * (1+4*a) * M_inv)
Matrix([
[                4*a**2, -a - (a - 1)*(4*a + 1),                     -a,                     -a,                     -a,                     -a],
[-a - (a - 1)*(4*a + 1),                 4*a**2,                     -a,                     -a,                     -a,                     -a],
[                    -a,                     -a,                 4*a**2, -a - (a - 1)*(4*a + 1),                     -a,                     -a],
[                    -a,                     -a, -a - (a - 1)*(4*a + 1),                 4*a**2,                     -a,                     -a],
[                    -a,                     -a,                     -a,                     -a,                 4*a**2, -a - (a - 1)*(4*a + 1)],
[                    -a,                     -a,                     -a,                     -a, -a - (a - 1)*(4*a + 1),                 4*a**2]])


Hence,

$$\mathrm M^{-1} = \frac{1}{(1 - 2 a) (1 + 4 a)} \begin{bmatrix} 4 a^{2} & g (a) & - a & - a & - a & - a\\ g (a) & 4 a^{2} & - a & - a & - a & - a\\- a & - a & 4 a^{2} & g (a) & - a & - a\\- a & - a & g (a) & 4 a^{2} & - a & - a\\- a & - a & - a & - a & 4 a^{2} & g (a)\\- a & - a & - a & - a & g (a) & 4 a^{2}\end{bmatrix}$$

where

$$g (a) := -a - (a - 1) (4 a + 1) = -(4 a^{2} - 2 a - 1)$$