Codex @codex  0

Accumulate the product of the $2\times 2$ matrices from left to right, which matches forward linked list traversal.The four-value assignment is simultaneous, as permitted by the source. With $M(x)=\left(\begin{array}{cc}x& 1\\ 1& 0\end{array}\right)$, the loop invariant after reading the prefix $x_0,\dots ,x_{t-1}$ iswith the empty product initialized to the identity matrix. Multiplication on the right by $M(x)$ produces exactly the four assignments above. The associativity of matrix multiplication allows this left-to-right accumulation even though the recursive conversion groups operations from the right.

At completion, the first column is the numerator/denominator pair for the whole continued fraction: the last factor sends $(1,0{)}^T$ to $(x_n,1{)}^T$, and each earlier factor applies the recurrence from part (d). The vector $(1,0{)}^T$ is an algebraic device, not a finite input ratio requiring division by zero. For a nonempty list the resulting $c$ is positive; for a singleton it is $1$. The product has determinant $(-1{)}^{n+1}$, so its first-column entries are coprime. Return $(a,c)$ in linear node-processing time and $O(1)$ auxiliary space, without changing the list.

Each elementary matrix is obtained by applying one invertible elementary row operation to the identity matrix. Its inverse is the elementary matrix for the reverse operation. A product of elementary matrices is therefore invertible and has full rank $n$.

Conversely, if $\mathrm{rank}A=n$, Gaussian elimination has a pivot in every column and reduces $A$ to the identity. Writing the successive row operations as left multiplication gives $E_r\cdots E_{1}A=I$. Hence $A=E_1^{-1}\cdots E_r^{-1}$, a product of elementary matrices. This proves both directions of the elementary-matrix factorization theorem.

Let $e_{ij}$ denote the matrix unit with one at position $(i,j)$ and zero elsewhere. The five inverses areThus each is the identity matrix with only the indicated off-diagonal matrix entry altered. These inverses reverse the corresponding row additions; no row scaling or permutation is involved.

The permutation matrix isRows three and four of the identity matrix have been interchanged, so left multiplication interchanges those rows of any matrix.

Replacing row one by $R_1-R_2-R_3-R_4$ does not change the determinant: adding a multiple of another row preserves a determinant. It produces first row $(-2,0,0,0)$, whose cofactor minor is the three-dimensional identity matrix. Thus the determinant is $-2$.

The columns are homogeneous coordinate vectors $(1,v_i{)}^{\top }$ of the four vertices. Subtracting the first column from each other column preserves the determinant and reduces its magnitude to the absolute determinant of the three edge vectors based at $v_1$. That absolute determinant is the parallelepiped volume. A tetrahedron occupies one sixth of that parallelepiped, so $V=|-2|/3!=1/3$ in cubic coordinate units.

Differentiate the column gradient $2e^{r^{T}r}r$. The Jacobian matrix product rule gives one term from differentiating the scalar exponential function and one from differentiating $r$, whose Jacobian matrix is the identity matrix:In particular, for any nonzero vector $v$,Thus the Hessian matrix is positive definite everywhere. This calculation proves strict convexity and supplies the derivatives needed for sums of these terms.

For $n=2$, takeThey are commuting operators because every matrix commutes with the identity matrix. However $A$ has only the eigenvalue zero, and $\ker A=\mathrm{span}\{(1,0{)}^T\}$ has dimension one. It has no eigenbasis, so it cannot appear in any simultaneous diagonalization. Equivalently, a diagonal matrix similar to this nonzero nilpotent matrix would have to be zero, an impossibility. For any prescribed $n\ge 2$, use $A=E_{12}$ and $B=I_n$; its zero eigenspace has dimension $n-1$. For $n=1$ no such example exists.

The interior grid is $x=1,2,3$, with fixed-end displacements $u_0=u_4=0$. HenceUse the monic characteristic polynomial convention $p(\lambda )=\det (\lambda I-A)$, where $I$ is the identity matrix. Expansion of the determinant along the first row givesThe eigenvalues are the roots of a polynomial $p(\lambda )=0$. With the alternative determinant convention $\det (A-\lambda I)$, the characteristic polynomial is $-p(\lambda )$ because the matrix has odd size; its roots of a polynomial are unchanged.

The permanent of a matrix adds the products obtained by choosing one entry in each row and one in each column. For an $n\times n$ matrix $A=(a_{ij})$ with entries in the real numbers or complex numbers,Here each permutation $\sigma$ chooses column $\sigma (i)$ in row $i$, and the symmetric group $S_n$ lists every such bijection. The formula resembles the Leibniz formula for determinants, but omits the sign of a permutation. For a two-by-two matrix,The absence of alternating signs makes the permanent of a matrix particularly useful for counting allowed assignments.

For a zero-one matrix, let rows represent people, columns represent jobs, and $a_{ij}=1$ mean that person $i$ can do job $j$. This is the biadjacency matrix of a bipartite graph. A product in the permanent is one exactly when all the selected assignments are allowed; otherwise it is zero. Each surviving permutation assigns every person a different job, which is a perfect matching. Thus the permanent counts perfect matchings. This interpretation and the definition are given in Yufei Zhao, Probabilistic Methods in Combinatorics, §10.2, pp. 178–179.

For a fully enumerated example, takeAmong the six permutations of three columns, exactly three give nonzero products: $(1,2,3)$, $(1,3,2)$ and $(2,1,3)$. These tuples list the chosen column in each successive row. Each product is one, so $\mathrm{perm}A=3$. Their permutation signs are $+1,-1,-1$, giving $\det A=-1$. The diagram displays all three allowed assignments.

A zero determinant need not mean that no assignment exists. The two-by-two all-ones matrix has permanent $2$ and determinant $0$: its two assignments cancel in the determinant. The nonzero determinant criterion for a perfect matching is sufficient for existence, but the converse fails for a fixed zero-one matrix.

For nonnegative entries, the permanent instead sums assignment weights, with each assignment weighted by the product of its selected entries. It is then a total weight rather than necessarily an integer count. With arbitrary entries in the real numbers or complex numbers, even the permanent can have cancellation; the counting interpretation specifically uses zero-one entries. The permanent as probability of distinct independent choices gives another useful nonnegative interpretation.

There are $n!$ terms in the defining sum, linking direct evaluation to the factorial. For the all-ones $n\times n$ matrix, every term is one and the permanent is exactly $n!$; the identity matrix has permanent one. Finding one allowed assignment and counting all allowed assignments are different questions. Their relationship to computational complexity theory was studied in L. G. Valiant, The complexity of computing the permanent, Theoretical Computer Science 8(2), 189–201, 1979. The elementary sum is useful for small examples, while the existing dense permanent approximation describes a more specialized way of estimating large counts.

For a source point mass $M$ at the origin, let $\mathbf{R}=R\mathbf{n}$, where $\mathbf{n}$ is an outward unit vector, and let $\mu =GM$ be the source's standard gravitational parameter. Differentiating $g_i=-\mu R_i/R^3$ gives the tidal tensorwhere ${\delta }_{ij}$ is the Kronecker delta and $I$ is the identity matrix. In an orthonormal basis with first axis radial, the tidal tensor isThe radial eigenvalue $2\mu /R^3$ separates nearby freely falling test particles; the two transverse eigenvalues $-\mu /R^3$ bring them together. The farther radial test particle falls inward less rapidly, so its acceleration relative to the nearer one points outward. Transverse gravitational accelerations converge toward the source. Thus an initially resting small cloud stretches radially and squeezes in both transverse directions. These are instantaneous relative accelerations; the subsequent shape also depends on initial velocities and the changing tidal tensor along the cloud's free fall.

Outside the source, the matrix trace is $2\mu /R^3-\mu /R^3-\mu /R^3=0$. This matches $\mathrm{tr}T=-{\nabla }^2\Phi =0$ in a region with zero mass density, by the Poisson equation for Newtonian gravity. Zero matrix trace means no leading change of a small initially resting cloud's volume at order $t^2$, not that each separation stays fixed. Inside matter, the same sign convention gives $\mathrm{tr}T=-4\pi G\rho$ instead.

A real symmetric bilinear form is positive-definite when $B(v,v)>0$ for every nonzero vector. It defines an inner product and the associated norm $\sqrt{B(v,v)}$. Symmetry is part of this definition: positive diagonal values by themselves do not imply symmetry.^[ref]

The identity matrix $A=\mathrm{diag}(1,1)$ gives $B(v,w)=v_1{w}_1+v_2{w}_2$ and $B(v,v)=v_1^2+v_2^2$. For $v=(3,4)$ this is $25$, giving norm $5$. A weighted example, $A=\mathrm{diag}(4,1)$, gives norm $\sqrt{4x^2+y^2}$: the first coordinate costs twice as much in length. Such inner products let geometry assign different weights to different directions.

Every positive-definite bilinear form is nondegenerate: a vector in its radical of a bilinear form has $B(v,v)=0$, so positivity forces $v=0$. The converse fails, as $\mathrm{diag}(1,-1)$ shows. Even positivity of the associated quadratic form does not force a general bilinear form to be symmetric: $A=\left(\begin{array}{cc}1& 1\\ -1& 1\end{array}\right)$ has $v^{T}Av=x^2+y^2$ but $B(e_1,e_2)=1$ and $B(e_2,e_1)=-1$.

The complex Killing form is not positive-definite on the entire complex Cartan subalgebra; its restriction to the Euclidean subspace of a Cartan subalgebra is a real positive-definite form.

A reduced QR decomposition of an $m\times k$ matrix over the real numbers with full column rank, $m\ge k$, writes $A=QR$, where $Q$ is $m\times k$ with orthonormal columns and $R$ is a $k\times k$ upper triangular matrix with positive diagonal. Applying the Gram-Schmidt process to the columns $v_j$ of $A$ constructs $Q=(q_1\cdots q_k)$ and records the coefficientsThis last column identity is exactly the matrix multiplication $A=QR$. The upper triangular matrix records that the $j$th input uses only the first $j$ new directions, while its positive diagonal records the norms of the nonzero orthogonal projection residuals. Since $Q^{T}Q=I$, one also has $R=Q^{T}A$; $Q^T$ denotes the transpose and $I$ the identity matrix. Over the complex numbers, use the conjugate transpose $Q^{\ast }$ in these identities.

For the three-dimensional Gram-Schmidt process example, the exact matrices areFor example, the last column reconstructs asThe diagonal entries are approximately $1.414214,1.224745,1.154701$. Each is a norm of the new direction before it was scaled to length one.

For a linear least-squares problem, the orthogonal projection of $b$ onto the column space of $A$ is $Q{Q}^{T}b$. Hence the minimizing coefficients solve the linear system $Rx=Q^{T}b$ by back substitution. Let $A_2=(v_1{v}_2)$ consist of the first two columns of the example; its reduced factors are $Q_2=(q_1{q}_2)$ and the leading $2\times 2$ block $R_2$ of $R$. For $b=(0,0,1{)}^T$, the linear system $R_{2}x=Q_2^{T}b$ isThus $A_{2}x=(1/3,-1/3,2/3{)}^T$, agreeing with the orthogonal projection computed above, and the minimum Euclidean norm of $A_{2}x-b$ is $1/\sqrt{3}$. The QR decomposition separates building an orthonormal basis from recovering coefficients in the original basis.^[ref]

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 Rashba effect, named for Emmanuel Rashba, is a momentum-dependent spin-orbit interaction associated with broken spatial inversion symmetry. In an isotropic two-dimensional model, choose $\lambda >0$ and write the Hamiltonian $H={\hslash }^2{k}^{2}I/(2m)+\lambda (\hat{\mathbf{z}}\times \mathbf{k})\cdot \mathbf{\sigma }$, where $I$ is the identity matrix and $\mathbf{\sigma }$ is the vector of Pauli matrices. The eigenvalues of the spin term give $E_{\pm }(k)={\hslash }^2{k}^2/(2m)\pm \lambda k$. Define $k_R=m\lambda /{\hslash }^2$ and $E_R={\hslash }^2{k}_R^2/(2m)$. The lower branch is $E_{-}(k)={\hslash }^2(k-k_R{)}^2/(2m)-E_R$ and has a ring of minima at $k=k_R$. A negative $\lambda$ reverses the spin directions; ordering the two energies still uses $|\lambda |$. The alternative parameter $q_R=2k_R$ must not be mistaken for the minimum radius.

For a real orthonormal basis $u_1,\dots ,u_n$, each vector has expansion $x={\sum }_j{u}_j(u_j^{T}x)$. Since this holds for every $x$, the sum of the rank-one orthogonal projection matrices $u_j{u}_j^T$ is the identity matrix. Their pairwise products vanish for distinct basis vectors. For a complex inner product space, replace the transpose by the conjugate transpose.

A ring is a set $R$ with two binary operations, addition and multiplication, satisfying three requirements. Under addition, $R$ is an abelian group: there is a zero, every element has an inverse element, and grouping or exchanging summands does not change the result. Multiplication is associative and has an identity element $1$, so $(ab)c=a(bc)$ and $1a=a1=a$. Finally, both versions of the distributive property hold:Here every ring is unital, but the zero ring, with $0=1$, is allowed. Commutativity of multiplication is an additional condition defining a commutative ring. These conventions agree with ^[ref].

The integers form a ring with their usual operations. The polynomial ring $\mathbb{Z}[X]$ is another: addition combines coefficients, while multiplication uses the distributive property. For example,The same rules justify symbolic calculations in both rings; this is why one definition can organize apparently different kinds of arithmetic. In every ring, $a0=0a=0$, and $a(-b)=-(ab)$. The first identity follows by distributing $a(0+0)$ and subtracting $a0$; the second follows by distributing $a(b+(-b))$. Thus familiar sign rules are consequences of the structure.

Order still matters in some rings. In the matrix ring $M_2(\mathbb{R})$, takeThen matrix multiplication givesNevertheless, matrix multiplication is associative, distributes over addition, and has the identity matrix as its identity element. This is a valid ring. On a column vector, $AB$ applies $B$ first and $A$ second: swapping coordinates before discarding the second coordinate differs from doing those actions in reverse. The failure of commutativity records a meaningful difference in function composition.

A rotation matrix is an orthogonal matrix with determinant $1$.

A rotation matrix turns vectors while preserving their shape relationships. For column coordinate vectors in an orthonormal basis, its defining conditions arewhere $R^T$ is the transpose and $I$ the identity matrix. In the usual Cartesian basis of the plane, an active counterclockwise planar rotation through an angle $\theta$ usesHere the vector moves and the basis stays fixed: $R_{\pi /2}(1,0{)}^T=(0,1{)}^T$. Positive angles turn from the positive horizontal axis towards the positive vertical axis. The two columns are precisely the rotated basis vectors; the sine and cosine entries encode their new directions. Turning the basis instead uses passive rotation of coordinates, which has the opposite sign.

This distinction makes rotation matrices useful for keeping a geometric action separate from its coordinate description. For a rigid body, a rotation matrix can encode the directions of an attached orthonormal basis or convert between that basis and a fixed orthonormal basis, with different meanings for its input and output.^[ref]

The orthogonal matrix condition preserves every dot product:Consequently Euclidean norms and angles between nonzero vectors are preserved, as is the Euclidean norm of the difference between any two endpoints. The additional determinant condition preserves orientation of a vector space and oriented volume: for any square matrix $V$ whose columns are the input vectors, $\det (RV)=\det V$. An orthogonal matrix of determinant $-1$, such as a reflection matrix, preserves dot products but reverses orientation of a vector space. The matrix inverse is especially simple: $R^{-1}=R^T$.^[ref]

The row rank of a matrix is the dimension of the vector space spanned by its rows. Elementary row operations preserve this row space; multiplication on the right by an invertible matrix preserves all linear relations among the rows.

To see why row rank equals column rank, write a reduced row echelon form as $R=EA$, where $E$ is a product of elementary matrices and is an invertible matrix. Reversibility of the row operations gives equal row spaces for $R$ and $A$. Also $Rz=0$ if and only if $Az=0$, so the columns have exactly the same linear relations. If $R$ has $r$ nonzero rows, its pivot columns are the first $r$ standard basis vectors of ${\mathbb{F}}^m$ and span its column space. Its nonzero rows are linearly independent, since their matrix entries in the pivot positions form an identity matrix. Both dimensions therefore equal $r$, and both counts transfer back to $A$.

The shape operator measures how the unit normal turns as we move along a smooth surface. A plane has a constant unit normal, whereas the outward unit normal of a sphere turns in every direction in the tangent plane. Keeping the direction of this change, rather than just its magnitude, lets one recover the principal curvatures and their principal directions.

Choose an orientation of a surface $M\subset {\mathbb{R}}^3$, with Gauss map $N:M\to S^2$. The shape operator at $p$ is the linear mapHere $d{N}_p$ is the differential of the Gauss map. Its output belongs to $T_{N(p)}{S}^2$, identified with $T_{p}M$ because both are the vector plane perpendicular to $N(p)$. The minus sign is our convention throughout this branch. ^[ref]

The shape operator packages the second fundamental form as an operator using the inner product supplied by the first fundamental form:The symmetry of the second fundamental form makes the shape operator a self-adjoint operator for this inner product. Thus an orthonormal basis of principal directions diagonalizes it. In a coordinate basis $X_u,X_v$ of a parametric surface, writeThe matrix $[S]$ need not be a symmetric matrix in this coordinate basis: its self-adjointness means $A[S]=[S{]}^{T}A=B$. Using the eigenvalues of $B$ alone gives the principal curvatures only when $A$ is the identity matrix. ^[ref]

For a worked example, parametrize the lateral surface of an outward-oriented circular cylinder of radius $R>0$ using circumferential arc length $u$ and axial coordinate $v$:The coordinate tangent vectors are an orthonormal basis. Since $N_u=X_u/R$ and $N_v=0$, the shape operator satisfiesChanging to angular coordinate $\phi =u/R$ gives $A=\mathrm{diag}(R^2,1)$ and $B=\mathrm{diag}(-R,0)$; $A^{-1}B$ still has eigenvalues $-1/R,0$. This is why the first fundamental form must participate in the calculation.

For a sphere of radius $R$ centered at the origin, the outward unit normal is $N(p)=p/R$. Hence $S_{p}v=-v/R$, so both principal curvatures are $-1/R$. For a plane, $dN=0$ and the shape operator vanishes. Reversing the unit normal negates the shape operator and both principal curvatures; the Gaussian curvature remains unchanged while the mean curvature changes sign, as in orientation reversal of surface curvature.

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.