0
$\begingroup$

On p.2 p.3 of the paper http://kam.mff.cuni.cz/~matousek/cla/mucha_sankowski_focs04.ps

Given a invertible matrix. We can get the inverse matrix by Gauss elimination. If there is a row and a column in the matrix such that the deletion of the row and the column will keep it invertible. Can we construct the inverse matrix after row and column deletion by the original inverse matrix? Just like iteration of Theorem 3.1

$\endgroup$
0
$\begingroup$

Let $A$ be an invertible matrix, $a_i$ be the $i$-th row of $A$, $a^j$ be the $j$-th column of $A$, $a_{ij}$ be the $(i,j)$-th element of $A$, and $e_k$ be the $k$-th column of the identity matrix.

Consider $B = A - e_ia_i - a^je_j^T + (1+a_{ij})e_ie_j^T$. The matrix $B$ can be also obtained from the matrix $A$ by zeroing $i$-th row and $j$-column and setting $(i,j)$-th element to $1$. By setting $U = [e_i, a^j-(1+a_{ij})e_i]$, $V = [a_i^T,e_j]^T$ we have $B = A-UV$, thus $B$ is given as rank-2 modification of the matrix $A$.

The inverse of $B$ can be found using the Woodbury identity: $$B^{-1} = A^{-1} + A^{-1}U(I-VA^{-1}U)^{-1}VA^{-1}$$ Now the inverse of a matrix $A$ with deleted $i$-th row and $j$-th column can be obtained from the matrix $B$ by removing $i$-th row and $j$-th column.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.