3
$\begingroup$

Given $A\in \mathbb{N}^{n\times n}$, then $A(\mathcal{I})$ is defined by first deleting the those columns with index in $\mathcal{I}$ and then extracting the first $n-|\mathcal{I}|$ rows.

Note that the definition of $A(\mathcal{I})$ is similar to principle submatrix, but they are not the same.

For example, if $$A=\begin{bmatrix} 11 & 12 & 13 & 14 & 15\\ 21 & 22 & 23 & 24 & 25\\ 31 & 32 & 33 & 34 & 35\\ 41 & 42 & 43 & 44 & 45\\ 51 & 52 & 53 & 54 & 55\end{bmatrix},$$ then $$A(\{1,3\})=\begin{bmatrix} 12 & 14 & 15\\ 22 & 24 & 25\\ 32 & 34 & 35\end{bmatrix}, A(\{2,3,5\})=\begin{bmatrix} 11 & 14 \\ 21 & 24 \end{bmatrix}.$$

The inverse of $A(\mathcal{I})$ can be computed in some ordinary ways. However, my question is: How can we calculate the inverse of $A(\mathcal{I})$ faster if we are given arbitrary $A(\mathcal{I})$ everytime, given that the inverse of $A$ is known by us?

If the knowledge of $A$ cannot help, which kind of prior knowledge can help us calculate the inverse of $A(\mathcal{I})$ faster?

If there is no such prior knowledge that can be helpful, I also want to ask whether there is some kind of special form of $A$ such that there exists some prior knowledge which can enable us to calculate $A(\mathcal{I})$ much faster?

$\endgroup$
4
  • 1
    $\begingroup$ Removing a row and column at once is a rank one update, so there is a way to do it. Scroll to the bottom of this answer I previously gave to a question to get a hint. $\endgroup$
    – adam W
    Jan 11, 2013 at 16:32
  • $\begingroup$ See Wikpedia page in en.wikipedia.org/wiki/Invertible_matrix#Blockwise_inversion for a ideia! Matrix inversion in block form! $\endgroup$ Jan 11, 2013 at 16:45
  • $\begingroup$ I checked the above sources. However, when I applied to my problem, since $\mathcal{I}$ can be arbitrary, I cannot determine the block first to simplify the computation. One way to use the above formula is to calculate all of possible block submatrices first. However, this results in significantly large storage overhead. $\endgroup$
    – user4478
    Jan 11, 2013 at 16:53
  • $\begingroup$ Is storing the inverse of the entire matrix too much? That is all you need. You then can use rank one operations to remove one column of choice and one row of choice, etc... all within the storage used for the inverse. This kind of question is so often asked, I guess a really good treatment of the subject needs be written... $\endgroup$
    – adam W
    Jan 11, 2013 at 18:40

0

You must log in to answer this question.

Browse other questions tagged .