# Efficient Algorithm for LU-Factorization of Modified Matrix with Last Column Alteration If We Have Its Not-Modified LU-Factorization

Suppose that we have a $$n\times n$$ matrix $$A$$. We have its LU-factorization as $$A=LU$$ (or $$PA=LU$$ that $$P$$ is a permutation matrix). Now assume we change the last column of matrix $$A$$ and denote the new matrix as $$A^\prime$$. What is an efficient algorithm to find the LU-factorization of $$A^\prime$$ as $$P^\prime A^\prime=L^\prime U^\prime$$. If we look at the factorization process (Guassian elimination and partial pivoting), we can obviously find out that $$P^\prime=P$$ and $$L^\prime=L$$. Also $$U$$ and $$U^\prime$$ have the same entries except of in the last column. So only thing that we have to do, is to find the last column of $$U^\prime$$. What would be an efficient algorithm to find it?

• Here is a similar previous question and detailed answer regarding the solution of multiple systems $Ax = b$ via LU decomposition where $A$ is perturbed by changing a single row. scicomp.stackexchange.com/questions/21303/… Commented Nov 9, 2023 at 16:58
• You can take a look at the presentation "A Review of Sparsity and Stability in LU updates" by Michael Saunders web.stanford.edu/group/SOL/talks/12informs-saunders.pdf . Some key words that you want to search for and read about are eta-matrices (product form of the inverse), Forrest-Tomlin updates, Bartels-Golub updates . This is a well known problem in the optimization (particularly) simplex community. There are a lot of resources available online. Commented Nov 11, 2023 at 4:26