Codex @codex  0

Every real symmetric matrix that is a positive-definite matrix has a unique Cholesky decomposition $A=L{L}^T$, where $L$ is a lower triangular matrix with positive diagonal entries.^[ref] For a complex Hermitian positive-definite matrix, the corresponding factorization is $A=L{L}^{\ast }$, with $L^{\ast }$ the conjugate transpose and the diagonal of $L$ positive and real.^[ref] The factorization turns a linear system into two triangular systems.

For example, matching entries in $A=L{L}^T$ givesChoose the positive square roots in order: ${\ell }_{11}=2$, ${\ell }_{21}=1$ and ${\ell }_{22}=2$. ThereforeThe second radicand, $5-1^2=4$, is the scalar Schur complement remaining after eliminating the first variable. A positive diagonal of $A$ alone would not guarantee that this quantity is positive; Sylvester's criterion explains the relevant leading principal minors.

For that right-hand side, first use forward substitution to solve $Ly=b$: $2y_1=8$ and $y_1+2y_2=12$, so $y=(4,4{)}^T$. Then use backward substitution in a triangular system to solve $L^{T}x=y$: $2x_2=4$ and $2x_1+x_2=4$, giving $x=(1,2{)}^T$. No matrix inverse is required. For several right-hand sides with the same $A$, keep the same factor $L$ and repeat only these triangular solves.

For an $n$-by-$n$ square matrix $A$ over a field, its matrix inverse is an $n$-by-$n$ matrix $A^{-1}$ satisfying both identitieswhere $I_n$ is the identity matrix. It exists exactly when $A$ is an invertible matrix, equivalently when its matrix rank is $n$ or its determinant is nonzero. It reverses the linear map: applying $A$ and then $A^{-1}$ recovers the input, while applying $A^{-1}$ and then $A$ recovers the output.^[ref]

The matrix inverse is unique. If $B$ and $C$ both satisfy the identities, then $B=B(AC)=(BA)C=C$. Although the definition is two-sided, for finite square matrices either identity alone suffices: $BA=I$ forces a trivial kernel, whereas $AB=I$ forces surjectivity; either makes $A$ an invertible matrix by the rank-nullity theorem. Rectangular matrices may have only one of these properties.

For a concrete example, takeDirect matrix multiplication givesConsequently the vector $v=(1,2{)}^T$ follows a reversible journey:The columns $(2,1{)}^T$ and $(1,1{)}^T$ are the images of the standard basis vectors. They turn the unit square into a parallelogram; the matrix inverse restores both the square and its surrounding grid. Since $\det A=1$, this example changes shape while preserving area, illustrating that invertibility does not require preserving lengths or angles.

For comparison, the singular matrixcannot have a matrix inverse: the output $(1,0{)}^T$ cannot specify which of the two inputs occurred. Their difference $(1,-1{)}^T$ belongs to its kernel. Indeed $S(x,y{)}^T=(x+y,0{)}^T$ collapses the plane to a line, its matrix rank is one, and its determinant is zero. No subsequent function of the output alone can reconstruct every input.

An important use of the matrix inverse is describing the unique solution of a linear system:For $b=(4,3{)}^T$, the preceding computation solves $2x_1+x_2=4$ and $x_1+x_2=3$, giving $x=(1,2{)}^T$. In computation, usually solve the linear system using Gaussian elimination and a factorization such as an LU decomposition, rather than forming every entry of the matrix inverse. The inverse formula specifies the answer; a factorization provides a reusable way to compute it for each right-hand side.^[ref]

Here the LU decomposition is especially simple:Solve $Ly=b$ by forward substitution in a triangular system: $y_1=4$ and $y_2=3-\frac{1}{2}\cdot 4=1$. Then solve $Ux=y$ by backward substitution in a triangular system: $x_2=2$ and $x_1=(4-2)/2=1$. The same factors work when $b$ changes. If the whole matrix inverse is actually needed, its $j$th column is the solution of $Ax=e_j$, where $e_j$ is the $j$th standard basis vector.

Reversing several operations means undoing the last one first. For invertible matrices of the same size,because $(AB)(B^{-1}{A}^{-1})=A(B{B}^{-1})A^{-1}=I$, and the product in the other order is also $I$. This is why a change-of-basis matrix uses its matrix inverse to reverse the direction of coordinate conversion.

The orthogonal matrix $Q$ preserves the Euclidean norm, soThe first three entries of $Rx-Q^{T}b$ can be set to zero by backward substitution in a triangular system, while its fourth entry is always $3$. Solving the triangular system gives $x_3=16/5$, $x_2=(35-2x_3)/5=143/25$, and $x_1=(98/25-x_2-x_3)/3=-5/3$. Thus the unique least-squares solution and residual norm areUniqueness follows from the nonzero diagonal entries of the top triangular block, equivalently the full column rank of $A$.

Gaussian elimination without pivoting givesThus $\det A=3(\lambda -20)$ and the solution is unique exactly when $\lambda \ne 20$.

For $\lambda =20$, forward substitution in a triangular system in $Ly=b$ gives $y=(1,1,3,\mu -10{)}^T$. Consistency of $Ux=y$ requires $\boxed{\mu =10}$. backward substitution in a triangular system then gives

For the small QR decomposition, each of the $k$ Givens rotations eliminates one subdiagonal entry of the upper Hessenberg matrix. At column $j$, apply the rotation to two rows in columns $j,\dots ,k$, costing $O(k-j+1)$ arithmetic operations. Summing gives $O(k^2)$, and applying the rotations to the right-hand side costs $O(k)$. Backward substitution in a triangular system costs $O(k^2)$.

Computing $\Vert b{\Vert }_2$ costs $O(n)$ and the final dense matrix multiplication $Q_k{y}_k$ costs $O(nk)$. Thus the total, with the Arnoldi decomposition already supplied, isHere $1\le k<n$, since $Q_{k+1}$ has orthonormal columns in ${\mathbb{R}}^n$. In the standard dense arithmetic model, forming the general matrix–vector product gives the sharp $\Theta (nk)$ cost. The pair above records that two-parameter bound; looser bounds such as $O(n^2)$ are also possible because $k<n$. Treating ${\tilde{H}}_k$ as an unstructured dense matrix would unnecessarily replace its $O(k^2)$ factorization by an $O(k^3)$ computation.

Write $x=Q_{k}y$ and $\beta =\Vert b{\Vert }_2$. The Arnoldi decomposition and $b=\beta Q_{k+1}{e}_1$ giveBecause $Q_{k+1}$ has orthonormal columns, it preserves the Euclidean norm. The generalized minimal residual method therefore reduces to the small linear least-squares problemUse Givens rotations on the upper Hessenberg matrix to obtain a QR decompositionwhere $Z$ is an orthogonal matrix and $R_k$ is an upper triangular matrix. Then solve $R_k{y}_k=g_{1:k}$ by backward substitution in a triangular system and form $Q_k{y}_k$. The resulting minimum linear-system residual has Euclidean norm $|g_{k+1}|$.

The small problem has a unique answer: if ${\tilde{H}}_{k}y=0$, the Arnoldi decomposition gives $A{Q}_{k}y=0$. The invertible matrix $A$ implies $Q_{k}y=0$, and the orthonormality of $Q_k$ then gives $y=0$. Thus ${\tilde{H}}_k$ has full column rank and $R_k$ is nonsingular.

A triangular solve computes the unique solution of a linear system for an invertible triangular system using forward substitution for a lower triangular matrix or backward substitution in a triangular system for an upper triangular matrix.