# Find the inverse of $A$

Let $$A= \begin{bmatrix} n & n_1 & n_2 & \cdots & n_s & 0 \\ n_1 & n_1 & 0 & \cdots & 0 & 1 \\ n_2 & 0 & n_2 & \cdots & 0 & 1 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ n_s & 0 & 0 & \cdots & n_s & 1 \\ 0 & 1 & 1 & \cdots & 1 & 0 \end{bmatrix},$$ where $$n=\sum_{i=1}^sn_i$$.

My questions: What is $$A^{-1}$$? Does it have an elegant expression?

My attempts: I tried some small matrices and found that $$A^{-1}$$ has the following form: $$A^{-1}=\begin{bmatrix} \cdots & \cdots & \cdots & \cdots & \cdots & -\frac{1}{s} \\ \cdots & \cdots & \cdots & \cdots & \cdots & \frac{1}{s} \\ \cdots & \cdots & \cdots & \cdots & \cdots & \frac{1}{s} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ \cdots & \cdots & \cdots & \cdots & \cdots & \frac{1}{s} \\ -\frac{1}{s} & \frac{1}{s} & \frac{1}{s} & \cdots & \frac{1}{s} & 0 \end{bmatrix}$$

While I faild to find patterns in those "dots" parts.

Thanks a lot.

• If all the $n_i$'s are $0$, the matrix is not invertible. Commented Sep 1, 2020 at 9:43
• @TheSilverDoe, thanks for the comment. But my interest lies in when $n_i$ are all positive numbers, or more specifically, positive integers. I suppose in this case, $A$ is invertible? Commented Sep 1, 2020 at 9:57
• I suspect that a nice approach would be to compute the inverse of the submatrix $$\begin{bmatrix} n & n_1 & n_2 & \cdots & n_s \\ n_1 & n_1 & 0 & \cdots & 0 \\ n_2 & 0 & n_2 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ n_s & 0 & 0 & \cdots & n_s \end{bmatrix},$$ then compute the full inverse using the Woodbury matrix identity Commented Sep 1, 2020 at 10:32
• Actually, it turns out that this submatrix is never invertible, which makes my suggestion problematic Commented Sep 1, 2020 at 10:38

## 1 Answer

Partial Answer: Here's a strategy you might find helpful.

Let $$M$$ denote the submatrix of $$A$$ given by $$M = \pmatrix{n & n_1 & n_2 & \cdots & n_s \\ n_1 & n_1 & 0 & \cdots & 0 \\ n_2 & 0 & n_2 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ n_s & 0 & 0 & \cdots & n_s}.$$ we see that $$M$$ can be expressed in the form $$M = \sum_{i=1}^s (e_1 + e_{1+i})(e_1 + e_{1+i})^T,$$ where $$e_1,e_2,\dots,e_{s+1}$$ denotes the canonical basis of $$\Bbb R^n$$. This gives us the decomposition $$M = BDB^T$$, where $$B = \pmatrix{e_1 + e_2 & e_1 + e_3 & \cdots & e_1 + e_{s+1}} = \pmatrix{1&1&\cdots&1\\1\\&1\\ && \ddots \\&&&1}, \quad D = \pmatrix{n_1 \\ & \ddots \\ && n_s}.$$ So, the matrix $$A$$ can be written in the form $$A = \pmatrix{BDB^T & x\\ x^T & 0},$$ where $$x = (0,1,1,\dots,1)^T$$.

Let $$C$$ denote the matrix $$C = \pmatrix{1&-1&\cdots & -1\\ &1\\ &&\ddots\\ &&&1}.$$ We note that $$CB = \pmatrix{0\\&I_{s}}.$$ With that in mind, we find that $$\tilde C A \tilde C ^T = \overbrace{\pmatrix{C&0\\0 & 1}}^{\tilde C} \pmatrix{BDB^T & x\\ x^T & 0} \pmatrix{C&0\\0 & 1}^T = \pmatrix{D & Cx\\ (Cx)^T & 0}.$$ It would suffice to find the inverse of this "nicer" matrix $$\tilde C A \tilde C ^T$$, then compute $$A^{-1} = \tilde C^T[\tilde C A \tilde C ^T]^{-1}\tilde C.$$

• Thanks for the hint, which is very helpful! But I suppose there are a few typos? For example, $B$ should be a $s+1$ by $s$ matrix, here column $e_1+e_{s+1}$ is missing. Besides, $CB$ should be $s+1$ by $s$ matrix with a zero vector as its first row and $I_s$ as the other part. As a result, the upper left corner of $\tilde{C}A\tilde{C}^T$ should be a $s+1$ by $s+1$ diagonal matrix with $0, n_1, \dots, n_s$ as its diagonal elements. Commented Sep 2, 2020 at 8:51
• @Chris Yes, that's all correct. I wasn't too careful when typing this up; sorry for any confusion Commented Sep 2, 2020 at 9:43