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.