# Fast Algorithm For Adding An Equation To A System?

Assume an $N \times N$ matrix $A$ and a length $N$ vector $b$. I've already solved the system $Ax = b$ for $x$ using standard methods. (If you want you can assume that I have the inverse of $A$ as well.)

Now, I have a block matrix $$A' = \begin{pmatrix} A & V \\ U & 0 \\ \end{pmatrix}$$

and a block vector $b' = (b, b^*)^T$. $U$ is an $1 \times N$ matrix, $V$ is an $N \times 1$ matrix, and the zero in the lower right corner is a scalar (or $1 \times 1$ matrix if you prefer).

In other words $A'$ is a matrix created by adding one row and one column onto $A$ and $b'$ is a vector created by adding one element onto $b$. I want to solve the system $A'x' = b'$ for $x'$. This is the same system as $Ax=b$ except that it has one extra equation and one extra variable to be solved for. Is there an efficient (less than $O(N^3)$) algorithm for this given that I've already computed the solution to $Ax=b$?

-

## 1 Answer

Look up Sherman Morrison Woodbury formula. That precisely answers your question. You will need to solve for $Ay = b$ though (or) if you have the inverse of $A$, the solution can be updated in $\mathcal{O}(N^2)$ steps. A nice thing about Sherman Morrison Woodbury thing is that it works even if $V \in \mathbb{R}^{N \times p}$ and $U \in \mathbb{R}^{p \times N}$. It will cost $\mathcal{O}(pN^2)$. The special case with $p=1$ is also called the Sherman Morrison formula.

-

I saw that before I posted here.  The problem is that the matrix multiplies involved in applying it make it also O(N^3).  You have to multiply two NxN matrices at some point, which is an O(N^3) operation. – dsimcha Aug 17 '11 at 18:07
@dsimcha: If you have the inverse of $A$, all you will be doing is matrix vector products and hence the additional cost will only be $\mathcal{O}(N^2)$ – user17762 Aug 17 '11 at 18:09
@Sirvarm:  Look at equation 1 in the Wikipedia article you linked to.  IIUC, A^-1 * U * (C - V * A^-1 * U) * V is an NxN matrix.  You then multiply this monstrosity by A^-1, hence O(N^3). – dsimcha Aug 17 '11 at 18:58
@dsimcha: You multiply a vector by a matrix. Hence the cost is $\mathcal{O}(N^2)$. Note that $U$ and $V$ are vectors. – user17762 Aug 17 '11 at 19:03
Right, but (C - V * A^-1 * U) is a scalar, A^-1 ^ U is a column vector and V is a row vector.  Thus this multiplication produces a matrix. – dsimcha Aug 17 '11 at 19:13
show 7 more comments
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 34, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": false, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9257380962371826, "perplexity_flag": "head"}