Are there any decompositions of a symmetric matrix that allow for the inversion of any submatrix?

I am given a $J \times J$ symmetric matrix $\Sigma$. For a subset of $\{1, ..., J\}$, $v$, let $\Sigma_{v}$ denote the associated square submatrix. I am in need of an efficient scheme for inverting $\Sigma_v$ for potentially any subset $v$. Essentially, I will have to invert many different submatricies $\Sigma_v$, but I won't know which ones I need to invert in advance of running some program; I would rather invest in a good matrix decomposition at the outset, if one exists (or otherwise get whatever information necessary, if not a decomposition).

I've messed around with the eigen decomposition a little bit, but wasn't able to coerce the inverse of a submatrix out of it.

UPDATE: Apparently the term for the type of submatricies I want to invert is "principal submatrix". I'm wondering if I can't make some progress on this via the Cholesky decomposition. Suppose I'm content to calculate $\Sigma_{jj} ^ {-1}$ for any $j \in \{1, 2, ..., J\}$, where $\Sigma_{jj}$ denotes the submatrix obtained by deleting rows/columns greater than $j$. Write $\Sigma = LL^T$ and let $Q = L^{-1}$. Write $$ L = \begin{pmatrix}L_1 & \mathbf 0 \\ B & L_2\end{pmatrix}, Q = \begin{pmatrix}Q_1 & \mathbf 0 \\ C & Q_2\end{pmatrix} $$ where $L_1$ and $Q_1$ and $j \times j$. It follows that $\Sigma_{jj} = L_1 L_1^T$ and $Q_1 = L_1 ^{-1}$ so that $\Sigma_{jj} ^{-1} = Q_1^T Q_1$. So, once I have the Cholesky decomposition I have the inverses of the leading principal submatricies. This doesn't solve the problem as stated since I may need to deal with other principal submatricies, but it should be a useful partial solution.


I imagine the best you can do is only one rank at a time building up or down to attain the desired sub-matrix portion. To reduce the dimension by one the simple formula is

$$\mathbf{A}^{-1} = E - \frac{\mathbf{f}\mathbf{g}^T}{h}$$

To see this, use the known inverse of the original and larger dimension matrix $$\pmatrix{\mathbf A & \mathbf b\\ \mathbf c^T & d}^{-1} = \pmatrix{\mathbf E & \mathbf f\\ \mathbf g^T & h}$$

to have $$\pmatrix{\mathbf E & \mathbf f\\ \mathbf g^T & h}\pmatrix{\mathbf A & \mathbf b\\ \mathbf c^T & d} = \pmatrix{ \mathbf I & \mathbf 0 \\ \mathbf 0^T & 1}$$

Now to find the quantity $A^{-1}$, simply left multiply the equation with $$\pmatrix{\mathbf{I} & -\mathbf{f}\frac{1}{h} \\ \mathbf{0}^T & 1}$$ giving $$ \pmatrix{\mathbf{E}- \mathbf{f}\frac{1}{h}\mathbf{g}^T & \mathbf{0} \\ \mathbf{g}^T & h}\pmatrix{\mathbf{A} & \mathbf{b} \\ \mathbf{c}^T & d} = \pmatrix{\mathbf{I} & -\mathbf{f}\frac{1}{h} \\ \mathbf{0}^T & 1}$$ The upper left portion of this matrix equation is $$\left( \mathbf{E} - \mathbf{f}\frac{1}{h}\mathbf{g}^T\right)\mathbf{A} = \mathbf{I}$$ and shows the formula.

To go the other direction (adding a row and column) you can use what is called the bordering method as described in this answer