Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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.
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.)
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)$$
