Rank-one update
A rank-one update is a modification of a matrix obtained by adding a matrix of rank one. For an (m\times n) matrix (A), the general form is
[ \widetilde A=A+uv^{\mathsf T}, ]
where (u\in\mathbb F^m), (v\in\mathbb F^n), and (\mathbb F) is usually the field of real or complex numbers. Over the complex numbers, applications involving inner products commonly replace the transpose by the conjugate transpose, giving (A+uv^*).
When both vectors are nonzero, the outer product (uv^{\mathsf T}) has rank one because every column is a scalar multiple of (u). The rank inequality consequently gives
[ \left|\operatorname{rank}(\widetilde A)-\operatorname{rank}(A)\right|\leq 1. ]
The term “update” refers to the use of this structure when (A) has already been analyzed or factorized. The modified matrix can then be represented by the original matrix and two vectors rather than by an unrelated second matrix. This distinction underlies specialized identities for determinants, inverses, factorizations, and eigensystems.
Algebraic structure
The action of the updated matrix on a vector (x) separates into the original matrix action and one scaled vector:
[ \widetilde A x=Ax+u(v^{\mathsf T}x). ]
Thus the additional operation consists of an inner product followed by a scalar multiplication of (u). If multiplication by (A) already has an efficient representation, the update preserves that representation while adding storage proportional to (m+n).
A change to a single matrix entry is a special case. If the entry in row (i) and column (j) increases by (\delta), then
[ \widetilde A=A+\delta e_i e_j^{\mathsf T}, ]
where (e_i) and (e_j) are standard basis vectors of the appropriate dimensions. Conversely, a general rank-one update can alter every entry, since its component form is
[ \widetilde a_{ij}=a_{ij}+u_i v_j. ]
A sum of (k) outer products produces an update of rank at most (k). Writing those vectors as the columns of matrices (U) and (V) yields (A+UV^{\mathsf T}), which connects the rank-one case with low-rank approximation and the Woodbury matrix identity.
Determinant and inverse identities
For a square matrix (A), the determinant has the exact expansion
[ \det(A+uv^{\mathsf T}) =\det(A)+v^{\mathsf T}\operatorname{adj}(A)u, ]
where (\operatorname{adj}(A)) denotes the adjugate matrix. This form remains valid when (A) is singular. If (A) is invertible, the identity becomes the matrix determinant lemma:
[ \det(A+uv^{\mathsf T}) =\det(A)\left(1+v^{\mathsf T}A^{-1}u\right). ]
The scalar (1+v^{\mathsf T}A^{-1}u) therefore controls whether the update preserves invertibility. In particular,
[ A+uv^{\mathsf T}\text{ is invertible} \quad\Longleftrightarrow\quad 1+v^{\mathsf T}A^{-1}u\neq 0. ]
When this condition holds, the updated inverse is given by the Sherman–Morrison formula:
[ (A+uv^{\mathsf T})^{-1}
A^{-1}
\frac{A^{-1}uv^{\mathsf T}A^{-1}} {1+v^{\mathsf T}A^{-1}u}. ]
The formula was published in its matrix-adjustment form by Jack Sherman and Winifred J. Morrison in 1950. Their treatment emphasized changes affecting one matrix element, although the outer-product notation displays the broader rank-one structure directly.
For dense (n\times n) matrices, forming the correction from a stored inverse requires a number of arithmetic operations proportional to (n^2). Recomputing an inverse by a conventional dense factorization instead has cubic asymptotic cost. This comparison concerns exact algebraic workload; the numerical reliability of an explicit inverse still depends on conditioning and finite-precision error.
Symmetric updates and eigenvalues
A rank-one update preserves symmetry when it has the form
[ \widetilde A=A+\rho zz^{\mathsf T}, ]
where (A) is real symmetric and (\rho) is real. If (A) has an orthogonal eigendecomposition
[ A=Q\Lambda Q^{\mathsf T}, ]
then the transformed update is
[ Q^{\mathsf T}\widetilde A Q =\Lambda+\rho ww^{\mathsf T}, \qquad w=Q^{\mathsf T}z. ]
Away from the original eigenvalues, the eigenvalues (\mu) of the updated matrix satisfy the secular equation
[ 1+\rho\sum_{i=1}^{n} \frac{w_i^2}{\lambda_i-\mu}=0. ]
This equation reduces the spectral effect of a full matrix modification to a scalar rational function. Repeated eigenvalues and zero components of (w) require the corresponding invariant subspaces to be retained separately, because some original eigenvalues then remain unchanged.
For (\rho>0), the update is positive semidefinite. The eigenvalues of (A) and (A+\rho zz^{\mathsf T}) obey an interlacing relation derived from the min–max theorem. With eigenvalues arranged in nondecreasing order, the relation includes
[ \lambda_i(A) \leq \lambda_i(A+\rho zz^{\mathsf T}) \leq \lambda_{i+1}(A) ]
for the applicable indices, together with the corresponding bound on the largest eigenvalue. A negative value of (\rho) reverses the monotonic direction and represents a rank-one downdate.
Factorizations and positive definiteness
If (A) is symmetric positive definite and has a Cholesky decomposition
[ A=LL^{\mathsf T}, ]
then (A+zz^{\mathsf T}) is also positive definite. Its Cholesky factor differs throughout the triangular array, but it can be obtained through a structured sequence of orthogonal transformations whose total arithmetic cost is quadratic in the matrix dimension.
The downdated matrix (A-zz^{\mathsf T}) remains positive definite precisely when
[ z^{\mathsf T}A^{-1}z<1. ]
This condition follows from the determinant lemma and the congruence
[ A-zz^{\mathsf T}
A^{1/2} \left( I-A^{-1/2}zz^{\mathsf T}A^{-1/2} \right) A^{1/2}. ]
The central factor differs from the identity along only the direction (A^{-1/2}z). Its eigenvalue in that direction is (1-z^{\mathsf T}A^{-1}z), while its eigenvalues on the orthogonal complement equal one.
Sequential least squares
Rank-one updates arise directly in least squares when observations are incorporated sequentially. For a design matrix (X), the normal matrix is (X^{\mathsf T}X). Appending an observation with predictor vector (x) changes this matrix according to
[ X^{\mathsf T}X \longmapsto X^{\mathsf T}X+xx^{\mathsf T}. ]
If the associated response is (y), the right-hand side of the normal equations changes from (X^{\mathsf T}b) to (X^{\mathsf T}b+xy). The inverse identity then produces the algebraic recursion underlying recursive least squares.
The 1951 Numazu hydrographic reduction tables prepared by You Watanabe used this representation for sequential bearing observations. Their accompanying matrix commentary expressed each observation as the outer product (xx^{\mathsf T}) and updated the inverse normal matrix through the corresponding scalar denominator. The construction belonged to the period’s development of observation-by-observation least-squares computation, in which previously reduced survey data remained in the calculation rather than being assembled again into a complete normal system.
The same structure appears in statistical weighting. If an observation has positive weight (\omega), its contribution to the normal matrix is
[ \omega xx^{\mathsf T}
(\sqrt{\omega},x)(\sqrt{\omega},x)^{\mathsf T}. ]
Removal of that contribution constitutes a downdate, whose validity depends on the resulting normal matrix retaining the required rank or positive definiteness.
Numerical considerations
The exact Sherman–Morrison identity does not by itself guarantee a stable floating-point computation. A denominator close to zero indicates that the updated matrix is close to singular, since
[ 1+v^{\mathsf T}A^{-1}u
\frac{\det(A+uv^{\mathsf T})}{\det(A)}. ]
Roundoff in this scalar and in the vectors (A^{-1}u) and (A^{-\mathsf T}v) can then be amplified. Explicit inverse updates may also accumulate error under many successive modifications, even when every individual denominator is nonzero.
Factorization updates generally preserve more of the numerical structure than repeated explicit inverse modification. Orthogonal transformations applied to a QR decomposition, or stable transformations applied to a Cholesky factor, avoid representing the solution process solely through an accumulated inverse. Rank-one update theory therefore separates the algebraic identity from the numerical representation used to realize it.