# How does it work ?¶

We give here the mathematical formulas used in the det_manip class. As this class mainly contains the determinant and the inverse of a matrix $$A$$, we need to know how to update these two members as operations are performed (addition/removal/replacement of one/two lines).

## Cofactors¶

For any $$n\times n$$ matrix $$A$$, its inverse (if it is defined) is related to the matrix of its cofactors $$\rm{Cof}$$ through:

$A\,{\rm Cof}(A^T) = {\rm Det}A\, I_n.$

The matrix of the cofactors is defined as:

$\begin{split}{\rm Cof}(A)_{i,j} =(-1)^{i+j}{\rm Det}\begin{pmatrix} a_{1,1} & \dots & a_{1,j-1} & a_{1,j+1} & \dots & a_{1,n} \\ \vdots & & \vdots & \vdots & & \vdots \\ a_{i-1,1} & \dots & a_{i-1,j-1} & a_{i-1,j+1}& \dots & a_{i-1,n} \\ a_{i+1,1} & \dots & a_{i+1,j-1} & a_{i+1,j+1}& \dots & a_{i+1,n} \\ \vdots & & \vdots & \vdots & & \vdots \\ a_{n,1} & \dots & a_{n,j-1} & a_{n,j+1} & \dots & a_{n,n} \end{pmatrix}.\end{split}$

## The Sherman-Morrison formula¶

$$A$$ is an invertible $$n\times n$$ matrix, and $$u$$, $$v$$ are $$n$$ vectors. Suppose furthermore that $$1+v^t A^{-1} u != 0$$. Then the Sherman-Morrison formula states that

$(A + u v^t)^{-1} = A^{-1} - \frac{ A^{-1} u v^t A^{-1} }{ 1 + v^t A^{-1} u}$

Similar formula for the determinant:

${\rm Det}(A + u v^t) = Det(A)(1 + v^t A^{-1} u).$

## Addition of a line and a column, or more¶

$$A$$ is an invertible $$n\times n$$ matrix. $$A'$$ is a $$(n+1)\times (n+1)$$ matrix obtained by adding a line and a column to $$A$$:

$\begin{split}A'=\begin{pmatrix} A & B \\ C & D \end{pmatrix}.\end{split}$

$$B$$ is a column and $$C$$ a line both of size $$n$$. $$D$$ is a scalar.

Using the following variables:

$\xi=D-C A^{-1} B, \qquad B'=A^{-1}B, \qquad C'=CA^{-1},$

and the previous formula with the cofactors, we get the determinant and the inverse of $$A'$$ as:

$\frac{{\rm Det}A'}{{\rm Det}A}={\rm Det}\xi.$
$\begin{split}(A')^{-1}= \begin{pmatrix} A^{-1}+ B'\xi^{-1}C' & -B'\xi^{-1} \\ -\xi^{-1}C' & \xi^{-1} \end{pmatrix}\end{split}$

For the addition of two or more lines and columns, the formulas remain the same, but $$B$$, $$C$$, $$D$$, $$\xi$$, $$B'$$ and $$C'$$ are now matrices of different sizes.

## Removal of a line and a column, or more¶

We remove the last line and column of the matrix $$A$$ of size $$(n+1)\times (n+1)$$. Writing:

$\begin{split}(A)^{-1}= \begin{pmatrix} F & G\\ H & I \end{pmatrix}\end{split}$

where $$G$$ is a column and $$H$$ a line both of size $$n$$, $$I$$ is a scalar, we get the determinant and the inverse of the new matrix $$A'$$ as:

$\frac{{\rm Det}A'}{{\rm Det}A}={\rm Det}I,$
$(A')^{-1}= \begin{pmatrix} F - GI^{-1}H \end{pmatrix}.$

For the removal of two or more lines and columns, the formulas remain the same, but $$F$$, $$G$$, $$H$$, and $$I$$ are now matrices of different sizes.

## Change of a column¶

$$A'$$ is the new matrix of size $$n\times n$$, where the last column has been changed:

Writing:

$A'= \begin{pmatrix} A_0 & B+\Delta B \end{pmatrix}.$

We know the inverse of the old matrix $$A$$ (of the same size as $$A'$$):

$\begin{split}A^{-1}= \begin{pmatrix} F\\ G \end{pmatrix}\end{split}$

Using the following variables:

$M = A^{-1}\Delta B,$

We have

$(A')^{-1} = A^{-1} - \frac{ M G }{ 1 + M_n }$
$\frac{{\rm Det}A'}{{\rm Det}A}= 1 + M_n$

To ameliorate the precision of the algorithm, the last line of $$A^{-1}$$ should only be divided by $$1 + M_n$$ and not updated by the general formula.

## Change of a line¶

It is a straightformward adaptation of the previous section:

Writing:

$\begin{split}A'= \begin{pmatrix} A_0 \\ C+\Delta C \end{pmatrix}.\end{split}$

We know the inverse of the old matrix $$A$$ (of the same size as $$A'$$):

$A^{-1}= \begin{pmatrix} F & G \end{pmatrix}$

Using the following variables:

$M =\Delta C A^{-1},$

We have

$(A')^{-1} = A^{-1} - \frac{ G M }{ 1 + M_n }$
$\frac{{\rm Det}A'}{{\rm Det}A}= 1 + M_n$

To ameliorate the precision of the algorithm, the last column of $$A^{-1}$$ should only be divided by $$1 + M_n$$ and not updated by the general formula.

## Change of a line and a column¶

$$A'$$ is the new matrix of size $$n\times n$$ where the last line and column has been changed:

Writing:

$\begin{split}A'=\begin{pmatrix} A_0 & B \\ C & D \end{pmatrix}.\end{split}$

We know the inverse of the old matrix $$A$$ (of the same size as $$A'$$):

$\begin{split}(A)^{-1}= \begin{pmatrix} F & G\\ H & I \end{pmatrix}\end{split}$

Using the following variables:

$h = HB, \qquad g=CG,$
$C'=CF, \qquad B'=FB,$
$f=C'B-D=CB'-D, \qquad \xi=gh-If,$
$G'=\xi^{-1}(hG-IB'), \qquad H'=\xi^{-1}(gH-IC'),$
$F' = F-G'C'+\xi^{-1}(fG-gB')H = F-B'H'+\xi^{-1}G(fH-hC')$

We get

$\begin{split}(A')^{-1}= \begin{pmatrix} F' & G'\\ H' & \xi^{-1}I \end{pmatrix}\end{split}$
$\frac{{\rm Det}A'}{{\rm Det}A}=\xi$

Note that this formulas remain valid if $$A_0$$ is not invertible.