4
$\begingroup$

It seems that there is a nice inverse for matrices that can be written as a diagonal matrix plus a symmetric matrix consisting of scaled blocks of ones.

Consider a real matrix of the form: $$\begin{pmatrix}a_{11}{1}_{r_{1}\times r_{1}}+b_{1}I_{r_{1}} & a_{12}{1}_{r_{1}\times r_{2}} & a_{13}{1}_{r_{1}\times r_{3}} \\ a_{12}{1}_{r_{2}\times r_{1}} & a_{22}{1}_{r_{2}\times r_{2}}+b_{2}I_{r_{2}} & a_{23}{1}_{r_{2}\times r_{2}} \\ a_{13}{1}_{r_{3}\times r_{1}} & a_{23}{1}_{r_{2}\times r_{2}} & a_{33}{1}_{r_{3}\times r_{3}} +b_{3}I_{r_{3}} \end{pmatrix}$$ The $r_i$ are growing linearly in the matrix size $n$, the $a_{ij}$ are bounded in absolute value as $n$ grows, while the $b_i$ are bounded and bounded away from $0$. The matrices $1_{r_i \times r_j}$ are matrices of all ones of the appropriate dimensions, and $I_{r_i}$ are identity matrices.

Are there techniques to analyze the inverse of such a matrix? In the 2-by-2 case, we can compute that the inverse is \begin{pmatrix}-\frac{b_{1}^{-1}}{r_{1}}{1}_{r_{1}\times r_{1}}+b_{1}^{-1}I_{r_{1}}+O(1/n^{2}) & O(1/n^{2})\\ O(1/n^{2}) & -\frac{b_{2}^{-1}}{r_{2}}{1}_{r_{2}\times r_{2}}+b_{2}^{-1}I_{r_{2}}+O(1/n^{2}) \end{pmatrix} Is there an easy way to see why this should generalize?

$\endgroup$
5
  • $\begingroup$ If the r’s are equal then the matrix is $A\otimes I_r$, so finding the inverse is easy. $\endgroup$ Apr 3, 2018 at 15:54
  • 1
    $\begingroup$ Have you tried row and column reduction to get rid of most of the nonzero items? When I do it I get 9 nonzero entries off the diagonal, which might be handled by adding three rank 1 matrices to a diagonal matrix. Gerhard "Zero Is Easier Than One" Paseman. 2018.04.03. $\endgroup$ Apr 3, 2018 at 16:01
  • 1
    $\begingroup$ Oops, I did it wrong. I get six nonzero entries for the non diagonal blocks, and the diagonal blocks look like arrowheads of b's and (-b)'s. My guess is that this form can be analyzed and generalized to more than three diagonal blocks. I would expect a nice inverse for this reduced form. Gerhard "Is Struck By The Direction" Paseman, 2018.04.03. $\endgroup$ Apr 3, 2018 at 17:29
  • $\begingroup$ It seems that we can write the matrix in question as $XX^T$ for an $X$ that has the same form, so there may be a connection to projection that makes it obvious why the off-diagonal entries should be small. $\endgroup$
    – Ben Golub
    Apr 3, 2018 at 18:42
  • 1
    $\begingroup$ @AnthonyQuas Wouldn't it be $A\otimes 1_r + \operatorname{diag}(b_1,b_2,b_3)\otimes I_r$? $\endgroup$
    – Dirk
    Apr 3, 2018 at 19:12

1 Answer 1

2
$\begingroup$

$\newcommand{\de}{\delta} \newcommand{\De}{\Delta} \newcommand{\ep}{\epsilon} \newcommand{\ga}{\gamma} \newcommand{\Ga}{\Gamma} \newcommand{\la}{\lambda} \newcommand{\Si}{\Sigma} \newcommand{\thh}{\theta} \newcommand{\R}{\mathbb{R}} \newcommand{\E}{\operatorname{\mathsf E}} \newcommand{\PP}{\operatorname{\mathsf P}}$

Is there an easy way to see why this should generalize? Yes.

Indeed, this can be extended to any number of blocks. Say a matrix $M$ consists of $q\times q$ blocks, with its $ij$-block given by the formula \begin{equation} a_{ij}1_{r_i\times r_j}+b_i\de_{ij}I_{r_i}, \end{equation} where $i,j=1,\dots,q$ and $\de_{ij}$ is the Kronecker symbol. The $ij$-block of the inverse matrix $M^{-1}$ has the same form: \begin{equation} c_{ij}1_{r_i\times r_j}+d_i\de_{ij}I_{r_i} \end{equation} for some real $c_{ij}$ and $d_i$.

Noting that $1_{r\times s}1_{s\times t}=s1_{r\times t}$, we see that the $ij$-block of the identity matrix $MM^{-1}$ is \begin{equation} \sum_k (a_{ik}1_{r_i\times r_k}+b_i\de_{ik}I_{r_i})(c_{kj}1_{r_k\times r_j}+d_k\de_{kj}I_{r_k}) =u_{ij}1_{r_i\times r_j}+b_id_i\de_{ij}I_{r_i}, \end{equation} where \begin{equation} u_{ij}:=a_{ij}d_j+\sum_k(a_{ik}r_k+\de_{ik}b_k)c_{kj}. \end{equation} That is, \begin{equation} D_d=D_{1/b},\quad AD_b+(AD_r+D_b)C=0, \end{equation} where $D_v$ stands for the diagonal matrix with the coordinates of the vector $v=(v_1,\dots,v_q)$ on the diagonal, $d:=(d_1,\dots,d_q)$, $b:=(b_1,\dots,b_q)$, $1/b:=(1/b_1,\dots,1/b_q)$, $r:=(r_1,\dots,r_q)$, $A:=(a_{ij})$, and
\begin{multline*} C:=(c_{ij})=-(AD_r+D_b)^{-1}AD_b =-(I_q+D_r^{-1}A^{-1}D_b)^{-1}(AD_r)^{-1}AD_{1/b} \\ =-(I_q+D_r^{-1}A^{-1}D_b)^{-1}D_{1/(br)}\sim-D_{1/(br)} \end{multline*} if, for instance, $A^{-1}$ exists and $\min_i|r_i|\to\infty$, where $br:=(b_1r_1,\dots,b_qr_q)$. Thus, the $ij$-block $c_{ij}1_{r_i\times r_j}+d_i\de_{ij}I_{r_i}$ of the inverse matrix $M^{-1}$ behaves as \begin{equation} \Big(\frac1{b_i}\,I_{r_i}-\frac1{b_ir_i}\,1_{r_i\times r_i}\Big)\de_{ij}, \end{equation} as desired.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.