Codex @codex  0

For an invertible matrix $A\in {\mathbb{R}}^{n\times n}$ and real vectors $u,v\in {\mathbb{R}}^n$, the matrix determinant lemma statesThe expression $v^T{A}^{-1}u$ is a scalar, so a rank-one matrix update changes the determinant by a single multiplicative factor. One need not expand the updated determinant entry by entry.

For the preceding example with $A=I$, the dot product is $v^{T}u=3-2=1$. Hence the updated determinant is $1+1=2$. Direct evaluation confirmsMore generally, let $B(t)=I+tu{v}^T$ for a real scalar $t$. The same calculation gives $\det B(t)=1+t$. The determinant is one at $t=0$, two at $t=1$, and zero at $t=-1$.

A compact proof explains the scalar reduction. Put $w=A^{-1}u$ and factor $A+u{v}^T=A(I+w{v}^T)$. If $w\ne 0$, choose a basis starting with $w$. In that basis, $(I+w{v}^T)w=(1+v^{T}w)w$, while every other basis vector changes only by a multiple of $w$. Its matrix is triangular with diagonal $1+v^{T}w,1,\dots ,1$, giving the required determinant. If $w=0$, the correction vanishes. This uses multiplicativity of the determinant to restore the factor $\det A$.

The denominator in the Sherman–Morrison formula is exactly this factor. The rank-one update singularity criterion therefore identifies when the updated matrix inverse ceases to exist. Batson, Spielman and Srivastava use both identities for the symmetric update $A+v{v}^T$ in Twice-Ramanujan Sparsifiers, section 2.3, Lemmas 2.1–2.2.

Fix $j\in A$ and writeThe matrix $R$ is positive definite. Applying the Sherman–Morrison formula to $R+X_j{X}_j^T$ yields

For the active set $A_k$, maintainThe initial $n\times n$ matrix inverse costs $O(n^3)$. At step $k$, compute $v_k=M_k^{-1}Y$ in $O(n^2)$ operations and all active ridge coefficients $X_{A_k}^T{v}_k$ in $O(|A_k|n)$ operations; their smallest absolute value determines $j_k$.

After deleting $j_k$,Part b ensures that the denominator in the Sherman–Morrison formula is positive, and the rank-one downdatecosts $O(n^2)$. Summing over the $p$ steps givesSince $p\ge n$, both earlier terms are bounded by $O(p^{2}n)$, proving the claimed computational complexity within computational complexity theory.

The leave-one-out residual identity for a linear smoother, obtained from the block matrix inverse or the Sherman–Morrison formula, isHence

Compute once the spectral decomposition $K=U\mathrm{diag}(d_1,\dots ,d_n)U^T$ in $O(n^3)$ operations and the vector $U^{T}Y$ in $O(n^2)$. For each ${\lambda }_{\ell }$, setThen computeBoth calculations take $O(n^2)$ operations per tuning parameter, after which the displayed leave-one-out formula costs $O(n)$. All $L$ scores therefore require $O(n^3+L{n}^2)$ operations.

Let $q=(\alpha ,\beta {)}^T$, letand recover the sufficient cross-products from the model1 normal equations by setting $c=A{\hat{q}}_0$ and $s=154.30+{\hat{q}}_0^{T}A{\hat{q}}_0$. Thenis the total squared residual about the fixed line. The squared sum of the ten residuals within each person, summed across people, isFor one person's ten observations, the marginal covariance matrix is ${\tau }^2{I}_{10}+{\sigma }^{2}11^T$. The matrix determinant lemma and Sherman–Morrison formula therefore give, up to an additive constant, twice the negative marginal log-likelihoodBecause the model was fitted with REML = FALSE, it minimizes this ordinary marginal maximum-likelihood objective. Thus $(V1,V2,V3,V4)$ belongs to the stated argmin over $alpha,\beta \in \mathbb{R}$ and $sigma,\tau >0$.

A rank-one matrix update changes a matrix $A$ by an outer product $u{v}^T$. For real vectors $u,v\in {\mathbb{R}}^n$, its action on an input vector $x$ isThe dot product $v^{T}x$ reads one scalar from the input, and the correction moves the output along $u$. All correction outputs therefore lie in one linear span. If either vector is zero, the update is zero; otherwise the correction is a rank-one matrix. The full updated matrix need not have rank one.

For example, chooseThe update sends $x=(x_1,x_2{)}^T$ to the correction $(3x_1-x_2)(1,2{)}^T$. Although all four entries change, there is only one direction of correction. Adding it to the identity matrix gives $B=\left(\begin{array}{cc}4& -1\\ 6& -1\end{array}\right)$.

This special structure allows existing work to be reused. The matrix determinant lemma updates the determinant using one scalar, and the Sherman–Morrison formula updates the matrix inverse using an outer product. Such formulas are useful when a linear system changes slightly after a new observation or a parameter adjustment: the unchanged part can retain its LU decomposition. The term rank-one describes the rank of the correction, not the size of the entry changes. ^[ref].

The Sherman–Morrison formula computes the matrix inverse after a rank-one matrix update. If $A$ is an invertible matrix and $\delta =1+v^T{A}^{-1}u\ne 0$, thenThe inverse correction is itself an outer product, divided by the scalar $\delta$. The matrix determinant lemma shows that the nonzero-denominator condition is exactly the condition that the updated matrix remains an invertible matrix.

For $A=I$, $u=(1,2{)}^T$, and $v=(3,-1{)}^T$, we have $\delta =2$. Thus the computed inverse isMultiplication in either order gives the identity matrix. The result reuses the original inverse $I$ and the same correction vectors, rather than solving independently for all four inverse entries.

Often only the solution of an updated linear system is needed. If $A{x}_0=b$ and $Az=u$, thenprovided $1+v^{T}z\ne 0$. The two solves use the same LU decomposition of $A$. This expresses the computational benefit without requiring an explicitly stored matrix inverse. Strang's Lecture 14, transcript pp. 9–10 explains this reuse of the original factorization.

To see why the inverse correction works, first consider $A=I$ and put $s=v^{T}u$. The rank-one matrix $R=u{v}^T$ satisfies $R^2=sR$. Expandingalso works in the reverse order. The general case follows by factoring out $A$ and replacing $u$ by $A^{-1}u$. A matrix identity has reduced to cancellation of scalar coefficients.

Historically, Jack Sherman and Winifred J. Morrison studied updating an inverse when a single matrix entry changes in their ^[ref]. Such an entry change is the special rank-one matrix update $\alpha e_i{e}_j^T$, with standard basis vectors $e_i,e_j$. The reference and the earlier 1949 abstract on row or column changes are recorded in Henderson and Searle, On Deriving the Inverse of a Sum of Matrices (1981), references 40–41. This distinguishes the specific original setting from the more general $u{v}^T$ formula used here.