Codex @codex  0

Sparse Gaussian elimination solves a linear system by Gaussian elimination while exploiting its sparse matrix structure to avoid storing zeros and performing unnecessary arithmetic operations. The catch is that zeros in the input need not remain zero: eliminating a shared unknown can couple two equations that previously had no direct coupling. These new positions are fill-in, and their number can depend strongly on the order of elimination.

For a real symmetric positive-definite matrix, the usual direct method is a Cholesky decomposition. Choose an ordering, use symbolic factorization to allocate the predicted factor entries, compute their values, then solve two triangular systems. Compressed sparse storage makes the reduced storage useful. General LU decomposition may also need numerical partial pivoting, so an ordering chosen for sparsity can change during factorization.^[ref]

For a fixed ordering, let $P$ be the permutation matrix that puts the unknowns in that order. Permute both rows and columns:Here $C$ is the lower triangular matrix in the Cholesky decomposition of $B$; $z=Px$. Forward substitution and back substitution give the original solution. The simultaneous permutation preserves the symmetric positive-definite matrix property because $v^{T}Bv=(P^{T}v{)}^{T}A(P^{T}v)>0$ for every nonzero vector $v$. A row permutation alone generally loses the symmetric matrix structure.

The local mechanism is a Schur complement. If the active pivot element is $a_{kk}$, then for remaining indices $i,j$,Even when $a_{ij}=0$, two nonzero couplings through $k$ make the second term nonzero. Thus the elimination graph removes $k$ and joins its remaining neighbors into a clique. The fill-path criterion for symmetric elimination extends this local rule across several steps. The elimination tree organizes the resulting dependencies; the minimum degree algorithm and nested dissection choose orderings to control them.

This connection between graphs and linear systems was already explicit in Donald J. Rose, R. Endre Tarjan and George S. Lueker's 1976 study of fill-in and perfect elimination orderings.^[ref]

The special linear group acts on determinant-one real symmetric matrices by matrix congruence. Symmetry and determinant are preserved, and signatures are preserved by Sylvester's law of inertia. The determinant-one set is a regular level set of dimension $n(n+1)/2-1$, with tangent directions $C=C^T$ satisfying $\mathrm{tr}(B^{-1}C)=0$. Its infinitesimal left-action fields are $XB+B{X}^T$; converting them to a Lie algebra representation requires the infinitesimal left-action sign convention.

Let $v$ be a real unit vector in $d$-dimensional Euclidean space. Then $P=v{v}^{\mathsf{T}}$ is a rank-one orthogonal projection: $Pv=v$, while $Pw=0$ for $w$ orthogonal to $v$. Consequently the symmetric matrix $A=\alpha I+\beta P$ has eigenvalue $\alpha +\beta$ on the line spanned by $v$ and eigenvalue $\alpha$ on its orthogonal complement. Any orthonormal basis of that complement completes $v$ to an orthonormal eigenbasis. ThusThe trace and determinant formulas remain valid when one of these eigenvalues is zero. When $\beta =0$, all nonzero vectors have the same eigenvalue, and the chosen splitting is optional.

For a real symmetric matrix $A$ and nonzero real vector $x$, the quotient rule and the quadratic form gradient give the displayed gradient. It vanishes exactly when $Ax=R_A(x)x$, so the stationary points are eigenvectors. Equivalently, the Lagrange multiplier condition for optimizing $x^{T}Ax$ on the unit sphere is $Ax=\lambda x$. The smallest and largest eigenvalues give the global extrema; other eigenvectors can be stationary without being extrema, as a direction mixing larger and smaller eigenvalues changes the quotient in opposite ways.

For a real symmetric matrix field $A$, strict ellipticity means that $A(x)$ is a positive-definite matrix at every point. Continuity makes its smallest eigenvalue positive uniformly on each compact subset of the domain. A uniform positive lower bound on the entire domain is the stronger uniform ellipticity condition. Some conventions include a finite uniform upper bound in the latter term, while others state coefficient boundedness separately.

A real symmetric matrix whose quadratic form is positive at every nonzero vector in the nonnegative orthant. By compactness of the nonnegative unit sphere, this is equivalent to a positive uniform lower bound $x^{T}Ax\ge \delta \Vert x{\Vert }_2^2$ on that orthant. It need not be a positive-definite matrix.

If idempotent matrices $P_1,\dots ,P_k$ satisfy $P_i{P}_j=0$ whenever $i\ne j$, then $({\sum }_i{P}_i{)}^2={\sum }_{i,j}{P}_i{P}_j={\sum }_i{P}_i$. Thus the sum is idempotent. For a real orthonormal set $q_i$, the matrices $P_i=q_i{q}_i^T$ meet this condition. Their sum is the orthogonal projector onto their span; the symmetric matrix property follows by transposing the sum. Arbitrary sums of idempotent matrices need not be idempotent.

For a real symmetric matrix $A$, set $v(z)=(z_1^2,\dots ,z_n^2{)}^T$. ThenFor sufficiency, factor $P=B^{T}B$. Its contribution is a sum of squares of linear combinations of $z_i^2$, while the contribution of $N$ is ${\sum }_i{N}_{ii}(z_i^2{)}^2+{\sum }_{i<j}2N_{ij}(z_i{z}_j{)}^2$. For necessity, use a homogeneous sum of squares representation and sign averaging of a sum of squares. Writing each quadratic summand with coefficients $a_{\ell i},b_{\ell ij}$ gives $P={\sum }_{\ell }{a}_{\ell }{a}_{\ell }^T$, $N_{ii}=0$ and $N_{ij}=\frac{1}{2}{\sum }_{\ell }{b}_{\ell ij}^2$ for $i<j$. Comparing coefficients gives $A=P+N$.

This is the basic semidefinite programming certificate of copositivity discussed in Parrilo's paper on matrix copositivity.

For a real symmetric matrix $X$ with eigenvalues ${\lambda }_1\ge \cdots \ge {\lambda }_n$, the sum of its $k$ largest eigenvalues is the support function of the fantope:Here $⪯$ is the Loewner order. In an orthonormal eigenbasis for $X$, the objective depends only on the diagonal entries of $Y$, which lie in the capped simplex. Thus the identity reduces to the sum of the largest components of the eigenvalues.

Over a field whose characteristic is not two, a bilinear form has a unique decomposition into a symmetric bilinear form $S$ and an alternating bilinear form $K$:Adding and subtracting the equations $B(v,w)=S(v,w)+K(v,w)$ and $B(w,v)=S(v,w)-K(v,w)$ both proves uniqueness and gives these formulas. In matrix notation, $S$ has matrix $(A+A^T)/2$ and $K$ has skew-symmetric matrix $(A-A^T)/2$.^[ref]

The diagonal values $q(v)=B(v,v)$ alone do not determine a general bilinear form, because $K(v,v)=0$ for every vector. For the matrix of a bilinear form in the example above,Thus two different bilinear forms, represented by $A$ and its symmetric matrix part, have exactly the same quadratic form. To recover a bilinear form from its diagonal, one needs extra information such as the hypothesis that it is a symmetric bilinear form.

A bilinear form $B$ is symmetric when $B(v,w)=B(w,v)$ for every pair of vectors $v,w$. Equivalently, its matrix of a bilinear form in any basis is a symmetric matrix, since $A_{ij}=B(e_i,e_j)=B(e_j,e_i)=A_{ji}$. Symmetry makes the relation $B(v,w)=0$ reciprocal, giving the bilinear orthogonal complement a geometric interpretation.

Over the real numbers, set $q(v)=B(v,v)$. The polarization identityrecovers the symmetric bilinear form from its quadratic form: expand $q(v+w)$ and use symmetry to combine the two cross terms. For $q(x,y)=x^2-y^2$, take $v=(2,1)$ and $w=(1,3)$. Then $q(v+w)=-7$, $q(v)=3$, and $q(w)=-8$, so $B(v,w)=(-7-3+8)/2=-1=2\cdot 1-1\cdot 3$. The same formula works whenever the characteristic is not two.^[ref]

Three real diagonal matrices show how much variety symmetry allows. The identity matrix $\mathrm{diag}(1,1)$ gives the positive-definite bilinear form $q=x^2+y^2$. The matrix $\mathrm{diag}(1,-1)$ gives $q=x^2-y^2$ and is nondegenerate despite the isotropic vector $(1,1)$. The matrix $\mathrm{diag}(1,0)$ gives $q=x^2$ and is a degenerate bilinear form with radical of a bilinear form $\mathrm{span}\{(0,1)\}$. Their level sets make the distinction visible: a circle, two branches of a hyperbola, and two parallel lines for $q=1$.

The inertia of a bilinear form records the numbers of positive, negative, and zero directions after matrix congruence diagonalization. By Sylvester's law of inertia, these counts survive change of basis; the three examples have inertia of a bilinear form $(2,0,0)$, $(1,1,0)$, and $(1,0,1)$. Historically, Sylvester stated this invariance in an 1852 paper on reducing real quadratic forms to sums of positive and negative squares. Ghys and Ranicki reproduce his statement and distinguish it from his subsequent 1853 proof.^[ref]

For a real symmetric matrix $M$, real $\mu$ and nonzero vector $u$, some eigenvalue of $M$ lies within the stated ratio of $\mu$. In an orthonormal eigenbasis, write $u={\sum }_j{c}_j{q}_j$ and $M{q}_j={\theta }_j{q}_j$. Then $\Vert Mu-\mu u{\Vert }_2^2={\sum }_j({\theta }_j-\mu {)}^2{c}_j^2\ge {\min }_j|{\theta }_j-\mu {|}^2\Vert u{\Vert }_2^2$, proving the bound.

The displayed coordinates identify determinant-one real symmetric matrices of size two with the two-sheeted hyperboloid. The special linear congruence action on symmetric matrices is transitive on each sheet, with stabilizer $SO(2)$. In particular the positive sheet is the homogeneous space $SL(2,\mathbb{R})/SO(2)$, a model of the hyperbolic plane.

A real symmetric matrix is positive definite when its quadratic form is positive on every nonzero vector. By the spectral theorem, this is equivalent to all its eigenvalues being positive. It has a unique symmetric positive-definite square root.

Let $A$ and $M$ be real symmetric positive-definite matrices. The principal square root of a positive semidefinite matrix construction gives an invertible matrix for each. SetThen $Ax=b$ is equivalent to $By=c$. This is a matrix congruence, and $B$ is a symmetric positive-definite matrix: $B^T=B$, and for every nonzero vector $v$,since $S^{-1}v\ne 0$. This short proof establishes both requirements for applying the conjugate gradient method to the transformed linear system.

The left transformed matrix has the same eigenvalues becauseIts correct geometry uses the weighted inner product $⟨u,v{⟩}_M=u^{T}Mv$: $⟨u,M^{-1}Av{⟩}_M=u^{T}Av=⟨M^{-1}Au,v{⟩}_M$. Thus it is symmetric in this inner product, even when it is not a symmetric matrix in ordinary coordinates. The spectral condition number governing the transformed symmetric problem is ${\kappa }_2(B)$, not generally ${\kappa }_2(M^{-1}A)$.

The Preconditioned conjugate gradient method realizes this transformation using auxiliary solves $M{z}_k=r_k$, without constructing $S$ or its matrix inverse. With fixed $M$, initialize $r_0=b-A{x}_0$ and $p_0=z_0$; while $r_k\ne 0$, usethen solve $M{z}_{k+1}=r_{k+1}$ and setStop at a zero linear-system residual before forming another ratio. Positive definiteness makes the denominators positive before termination.^[ref]

An invertible matrix alone is insufficient: with $A=I$ and $M=\mathrm{diag}(-1,1)$, the left transformed matrix has eigenvalues $-1,1$, and $M$ has no real symmetric positive-definite matrix square root. Even a valid symmetric positive-definite matrix can worsen conditioning if its scaling is unsuitable, as the next worked example shows.

If $A^T=A$ and $B^T=B$, then $(AB{)}^T=B^T{A}^T=BA$. Hence their product is a symmetric matrix exactly when they commute. For example, $A=\mathrm{diag}(1,0)$ and $B=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ are symmetric but have nonsymmetric product $\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right)$. This criterion differs from asking whether an arbitrary matrix can be factored as a product of symmetric matrices.

Over a field of characteristic two, the linear map $T:M_n(F)\to M_n(F)$, $A\mapsto A+A^T$, has kernel of a linear map the symmetric matrices, of dimension $n(n+1)/2$. Its image of a linear map is the linear subspace of symmetric matrices with zero diagonal, of dimension $n(n-1)/2$. Indeed, $T(A)=0$ means $A=A^T$, and every symmetric zero-diagonal matrix is the image of the matrix obtained by retaining just its entries above the diagonal. Thus the two dimensions still add to $n^2$, as required by the rank-nullity theorem.

The first coefficient of the alpha tensor is ${\alpha }_{ij}^{(1)}={ϵ}_{ikl}⟨u_k{\partial }_j{u}_l⟩$. Its contraction with the Levi-Civita symbol isby incompressibility and vanishing averages of total derivatives. Every antisymmetric second-rank tensor in three dimensions is detected by this contraction, so the coefficient is a symmetric matrix. The proof needs no Fourier analysis.

// Target: fluid-mechanics.bigb

Suppose a binary symmetric matrix $A$ satisfies $A^2=I$, has one row of Hamming weight eleven and eleven rows of Hamming weight seven, and every sum of two distinct rows has Hamming weight six. Then $(I\mid A)$ generates a self-dual code. Its rows have weights twelve or eight; their mutual orthogonality makes every generated word doubly even. A weight-four word $(u,uA)$ would have left-half weight one, two, three or four. The first two cases are excluded by the stated row weights; weight three would force $uA$ to be a unit vector and hence $u$ to be a row of $A$; weight four would force $uA=0$. Thus weight four is impossible and the minimum Hamming distance is eight.

For a binary symmetric matrix $A$ with $A^2=I$, the syndrome of an error $(p,q)$ relative to the column parity-check matrix $(I;A)$ is $s=p+qA$. An error of total Hamming weight at most three has at most one nonzero bit in one half. Test $s$, each $s+A_i$, $sA$, and each $sA+A_i$ for weights at most three, two, three and two respectively. These identify $(s,0)$, $(s+A_i,e_i)$, $(0,sA)$ and $(e_i,sA+A_i)$. For the extended binary Golay code, minimum Hamming distance eight guarantees that at most one such error exists.