# Upper bound for $\|\textbf{D}^{-1}\|$, where $\textbf{D}$ is a matrix with specific sparse pattern

Consider the block matrix given by

$$\textbf{D} = \left[ \begin{array}{ccc} \left[ \begin{array}{ccc} D & \ldots & D\\ \vdots & \ddots & \vdots\\ D & \ldots & D\\ \end{array}\right] & \textbf{X} & \textbf{X}\\ \textbf{X} & \left[ \begin{array}{ccc} D & \ldots & D\\ \vdots & \ddots & \vdots\\ D & \ldots & D\\ \end{array}\right] & \textbf{X}\\ \textbf{X} & \textbf{X} & \left[ \begin{array}{ccc} D & \ldots & D\\ \vdots & \ddots & \vdots\\ D & \ldots & D\\ \end{array}\right]\\ \end{array}\right]$$

where each $\textbf{X}$ represents a dense matrix (but possible different from each other) in $\mathbb{C}^{nr \times nr}$. Each matrix in the form

$$\left[ \begin{array}{ccc} D & \ldots & D\\ \vdots & \ddots & \vdots\\ D & \ldots & D\\ \end{array}\right]\\$$ is composed by $r \times r$ of these matrices $D$, which are diagonal matrices (but possible different from each other) in $\mathbb{C}^{n \times n}$. So each of its $r^2$ entries is a diagonal matrix $D \in \mathbb{C}^{n \times n}$.

This matrix has a sparse pattern and is supposed to be invertible. What I'm trying to do is to obtain some upper bound for the norm of its inverse. Concretely, I want an upper bound for

$$\|\textbf{D}^{-1}\|$$ where the norm can be the spectral norm or the Frobenius norm. I am looking for some bound in terms of these blocks, in a way it take advantage of its sparsity.

I already looked through several papers and searched on the internet, but couldn't find anything helpful. All my ideas also didn't work, so my last hope is that someone here may have a good idea. This looks to be a very specific problem, and since I'm not so familiar with results about sparse matrices, the best option is to share with you in the hope someone knows something about it.

Thank you!

• You could probably start with the observation that the matrix $\mathbf{D}$ can be represented as $$I_3\otimes(\mathbf{1}_r\mathbf{1}_r^T\otimes D)+(\mathbf{1}_3\mathbf{1}_3^T-I_3)\otimes \mathbf{X}$$ Here I use $\mathbf{1}_l$ to represent a $l\times 1$ column of $1$'s, and $I_l$ to represent the $l\times l$ identity matrix. – Samrat Mukhopadhyay Aug 11 '17 at 6:19
• I don't understand why you are calling this a sparse structure. The matrix $A$ is very dense, at least 2/3 of its entries are arbitrary. – Anton Mellit Aug 12 '17 at 20:51
• @Anton Mellit There is two definitions of a sparse matrix. A matrix with a lot of zeros and a matrix with zeros in specific positions. I'm using the second . – Integral Aug 15 '17 at 11:41
• I think you mean "specific sparsity pattern" instead of "specific sparse structure". – Dirk Aug 18 '17 at 6:28
• Well, @Integral, I am also not sure how to proceed with this, but I just made this comment to put out the particular structure that this matrix has, so that probably it can make things easier. – Samrat Mukhopadhyay Aug 19 '17 at 16:27