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!

  • 1
    $\begingroup$ 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. $\endgroup$ Aug 11, 2017 at 6:19
  • 2
    $\begingroup$ 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. $\endgroup$ Aug 12, 2017 at 20:51
  • $\begingroup$ @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 . $\endgroup$
    – Integral
    Aug 15, 2017 at 11:41
  • 1
    $\begingroup$ I think you mean "specific sparsity pattern" instead of "specific sparse structure". $\endgroup$
    – Dirk
    Aug 18, 2017 at 6:28
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 19, 2017 at 16:27


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.