Will this matrix be invertible?

61 Views Asked by At

Suppose that:

  • $A$ is a $n\times n$ diagonal matrix, with diagonal elements strictly positive and summing to one.
  • $b$ is a $1\times n$ vector, with elements non-negative and summing to one (there might be zeros).

Question : Is the $(n+1)\times(n+1)$-sized block matrix

$$\begin{pmatrix} A & b\\b' & 0 \end{pmatrix}$$

invertible ?

If no, would it be under some ctricter condition that i did not thought of ?

1

There are 1 best solutions below

8
On BEST ANSWER

Yes, your matrix (which I will call $M$) is invertible. To see that this is the case, it suffices to note that $A$ is invertible, as is its Schur complement $$ M/A = 0 - b'A^{-1}b = -\|A^{-1/2}b\|^2. $$ We compute $\det(M) = -\det(A)\cdot b'A^{-1}b$.


By block-matrix multiplication, we have $$ \pmatrix{I & 0\\-b'A^{-1} & 1} M \pmatrix{I & 0\\-b'A^{-1} & 1}^T = \pmatrix{A & 0\\0&-b'A^{-1}b} $$ Taking the inverse of both sides yields $$ \pmatrix{I & 0\\-b'A^{-1} & 1}^{-T} M^{-1} \pmatrix{I & 0\\-b'A^{-1} & 1} = \pmatrix{A^{-1} & 0\\0&-(b'A^{-1}b)^{-1}}^{-1} \implies\\ M^{-1} = \pmatrix{I & 0\\-b'A^{-1} & 1}^{T}\pmatrix{A^{-1} & 0\\0&-(b'A^{-1}b)^{-1}} \pmatrix{I & 0\\-b'A^{-1} & 1} \implies\\ M^{-1} = \pmatrix{I & 0\\-b'A^{-1} & 1}^{T}\pmatrix{A^{-1} & 0\\(b'A^{-1}b)^{-1}b'A^{-1}&-(b'A^{-1}b)^{-1}} \implies\\ M^{-1} = \pmatrix{A^{-1} - A^{-1}b(b'A^{-1}b)b'A^{-1} & -(b'A^{-1}b)^{-1}A^{-1}b\\ (b'A^{-1}b)^{-1}b'A^{-1} & (b'A^{-1}b)^{-1}}. $$

We also could have computed this directly from the formula here, since $$ M^{-1} = \pmatrix{A^{-1} + A^{-1} B (M/A)^{-1} C A^{-1} & - A^{-1} B (M/A)^{-1} \\ - (M/A)^{-1} CA^{-1} & (M/A)^{-1}}\\ = \pmatrix{A^{-1} - A^{-1}b(b'A^{-1}b)b'A^{-1}& -(b'A^{-1}b)^{-1}A^{-1}b\\ (b'A^{-1}b)^{-1}b'A^{-1} & (b'A^{-1}b)^{-1}} $$


We could also compute the inverse using the Woodbury matrix identity. In particular:

Let $v$ denote the matrix $b$ with a $1$ appended to the end. Let $D$ denote the matrix $A$ with an extra row and column of zeros added and a $-2$ in the bottom right. Let $V$ denote the matrix whose columns are $e_n = (0,\dots,0,1)^T$ and $v$.

By the identity, we have $$ M^{-1} = (D + VV^T)^{-1} = D^{-1} + D^{-1}V (I_2 + V^TD^{-1}V) V^TD^{-1}. $$