Updating the Cholesky factorization of when one or more columns are added to or removed from matrix can be done very efficiently obviating the re-factorization from scratch.

## Removing columns

Assume we know the Cholesky factorisation of and we remove a column from matrix which can be written as follows

Then,

Once we delete the column at we have

from which we have that

and

The last equation is a rank-1 update (see Golub and Van Loan) and it comes at the

cost of .

## Appending columns using permutation matrix

Having computed a Cholesky factorisation with permutation for the matrix , that is , we need to compute the Cholesky factorisation of , where .

We have

From which we have that

and $\ell_1$ is computed from the following nice linear system

and, provided that , is positive definite and

*Remark*. to solve we do and we set so we then need to solve

The permuted Cholesky factor of is

and the corresponding permutation matrix is

The computational cost of this update is .

## Inserting columns

In this example we shall insert a column in , so we shall define the matrix

where .

There is then a permutation matrix so that .

It is then easy to update the factorisation

which is the updated Cholesky factorisation of with permutation matrix .

## Inserting many columns

Now we are going to insert many columns, recursively, at various positions in . Essentially, we are going to update a permuted Cholesky factorisation by inserting a column in any position in , so the updated matrix becomes

There is a permutation matrix so that

Say we have . We can then compute a permuted Cholesky factorisation for ,

which is the permuted Cholesky factorisation of with permutation matrix .

Let now be a given matrix and be a collection of column indexes of , and and we know the Cholesky factorisation of .

Let , i.e., the -th column of is added to to form the new matrix

Having augmented we can now update the factorisation of and compute an such that