Codex @codex  0

A homogeneous motion has an acceleration potential exactly when $A=\ddot{F}{F}^{-1}$ is a symmetric matrix. Necessity follows because $A$ is the spatial gradient of the material acceleration, which must be a negative Hessian matrix. For sufficiency, put $\mathbf{y}=\mathbf{x}-\mathbf{c}(t)$ and take $\xi =-{\mathbf{y}}^{T}A\mathbf{y}/2-\ddot{\mathbf{c}}\cdot \mathbf{y}+g(t)$. Direct spatial differentiation gives $-\nabla \xi =A\mathbf{y}+\ddot{\mathbf{c}}$. Equivalently $F^T\dot{F}-{\dot{F}}^{T}F$ is constant: its time derivative is $F^T\ddot{F}-{\ddot{F}}^{T}F$.

The acoustic tensor determines the plane waves of a locally uniform incremental elastic medium. For a unit material direction $\nu$, its eigenvalues are ${\rho }_0{c}^2$ and its eigenvectors are displacement polarizations. Major symmetry of the incremental elastic moduli makes $Q$ a real symmetric matrix. Positivity on every rank-one matrix $m\otimes \nu$ makes all its wave speeds real and nonzero.

Write $n=|V|$ and $m=|E|$. Suppose each vertex identifier, list descriptor, link and optional edge weight occupies a constant number of machine words, and indexed array access and identifier comparison take constant time. There are $n$ list descriptors and $m$ directed, or $2m$ undirected, neighbour entries. Hence adjacency lists use $O(n+m)$ machine words in Big O notation. A full adjacency matrix has $n^2$ entries, regardless of $m$. These are counts under a storage model, not fixed byte sizes.^[ref]

Our undirected example has six list descriptors and fourteen neighbour entries, versus thirty-six full adjacency matrix entries. The numbers $20$ and $36$ count different kinds of logical items: they do not prove a particular byte saving. A linked list also needs links; an array may have unused capacity. Storing only half of a symmetric matrix changes its exact count while leaving quadratic growth. If identifiers or weights require growing numbers of machine words, their size must be included in the space complexity.

An unsorted adjacency list answers "does the edge $u\to v$ exist?" by linear search through $\mathrm{Adj}[u]$. In the worst case it inspects all $d$ entries, giving $O(1+d)$ time, or $O(d)$ for $d\ge 1$. Even if $v$ is absent, an uninspected entry could still contain it, so arbitrary lists require the whole scan. On our example, looking for $CF$ in $C$'s list compares $F$ with $A,B,D$ and fails after three comparisons. A full adjacency matrix instead answers from its single $C,F$ entry in $O(1)$ time.^[ref]

Different promises change the query. A sorted array of neighbour identifiers permits binary search in $O(\log (d+1))$ time, but maintaining order after insertion may require shifting entries. A per-vertex hash table permits expected constant-time membership under the hashing and load assumptions of that data structure; it does not give that guarantee to an arbitrary adjacency list. A stored list length can likewise make a vertex degree query constant-time even though neighbour enumeration still has to visit its entries.

The advantage grows with scale. For a graph path on $n\ge 2$ vertices, $m=n-1$, so there are $2n-2$ undirected neighbour entries and $n$ descriptors, versus $n^2$ full adjacency matrix entries. Such a family is a sparse graph with $m=O(n)$. For a complete graph, $m=n(n-1)/2$, so the undirected neighbour entries already number $n(n-1)$: the adjacency list advantage in growth rate disappears. Choose by the workload: following existing edges favours adjacency lists; many arbitrary pair-membership queries can favour a full adjacency matrix. The representation organizes the same graph for different questions.

Every complex symmetric matrix admits a unitary congruence decomposition with a unitary matrix $U$ and nonnegative diagonal entries $s_j$ equal to its singular values. This differs from unitary similarity diagonalization. It reduces a multimode squeezed vacuum to independent oscillator squeezing factors.

Fix $v\ne 0$, put $s=v^{T}v$, $t=v^{T}Tv$, and $P=I-v{v}^T/s$. Any real symmetric matrix on three-dimensional Euclidean space has a unique decomposition with $C^{T}v=0$, $Dv=0$ and $\mathrm{tr}D=0$:The transverse restriction is a symmetric two-dimensional matrix, whose traceless matrix part has dimension two. Together the two scalars, two components of $C$ and two components of $D$ give the six parameters of $T$.

A quasi-Newton method that maintains a symmetric curvature approximation for differentiable optimization. For a positive-definite symmetric matrix $H$ approximating inverse curvature, step $s$, gradient change $y$ and $\rho =1/(y^{\mathsf{T}}s)>0$, its inverse update isMultiplying by $y$ gives $H_{+}y=s$, the inverse form of the Quasi-Newton secant equation. The update is a symmetric matrix. For any nonzero $v$,Both terms are nonnegative, and both can vanish only if $s^{\mathsf{T}}v=0$ and then $v=0$. Thus positive definiteness is preserved when $y^{\mathsf{T}}s>0$, making $-H_{+}\nabla f$ a descent direction away from a stationary point. Full updates use quadratic storage in the dimension; the method does not require explicit Hessian matrix evaluations. Superlinear convergence requires additional local smoothness and line search assumptions.^[ref]

The equation of a quadric surface after orthogonal diagonalization of its symmetric matrix and appropriate translation. The spectral theorem for real symmetric matrices removes mixed quadratic terms, and completing squares removes linear terms in directions with nonzero eigenvalues. Linear terms in zero-eigenvalue directions can remain and generate elliptic paraboloids or hyperbolic paraboloids. The signs, zero coefficients and constant distinguish ordinary surfaces, degenerate conics in plane sections, and empty real loci.

Use the induced spectral norm for the symmetric matrix $H$ and interpret $\Vert g\Vert /\Vert H\Vert =+\infty$ when $H=0$. If $q=g^{T}Hg\le 0$, the Cauchy point gives a decrease at least $\Delta \Vert g\Vert$. If $q>0$, its step size satisfies $\tau q\le \Vert g{\Vert }^2$ and $q\le \Vert H\Vert \Vert g{\Vert }^2$, soThus the numerical constant $1/2$ is independent of the model data. The bound links a nonzero gradient to a definite predicted decrease, including for an indefinite matrix $H$.

For a real three-dimensional linear map $A$, preservation of every surface area is equivalent to being an orthogonal matrix. For necessity, diagonalize the symmetric matrix $A^{T}A$ in an orthonormal basis, with nonnegative eigenvalues ${\lambda }_i$. The three unit coordinate parallelograms have image areas $\sqrt{{\lambda }_1{\lambda }_2}$, $\sqrt{{\lambda }_1{\lambda }_3}$, and $\sqrt{{\lambda }_2{\lambda }_3}$. Setting all three equal to $1$ forces every ${\lambda }_i=1$. Sufficiency follows from preservation of dot products and $\Vert \mathbf{u}\times \mathbf{v}{\Vert }^2=\Vert \mathbf{u}{\Vert }^2\Vert \mathbf{v}{\Vert }^2-(\mathbf{u}\cdot \mathbf{v}{)}^2$. This specifically uses dimension three; in dimension two, preservation of planar area alone only requires $|\det A|=1$.

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.

Use the conic Carathéodory theorem in the real space of symmetric matrices, of dimension $N=n(n+1)/2$. A convergent sequence $B_{\ell }$ in the completely positive cone has padded factorizations $B_{\ell }={\sum }_{j=1}^N{x}_{\ell j}{x}_{\ell j}^T$ with nonnegative factors. Their total squared norms equal $\mathrm{tr}{B}_{\ell }$ and are uniformly bounded. A simultaneous convergent subsequence of the finite factor tuple gives $B={\sum }_j{x}_j{x}_j^T$ with $x_j\ge 0$. Thus the limit remains in the cone. The argument also bounds the required number of factors by $N$.

A coarse-grid correction improves a fine-grid approximation by solving a smaller equation for the part of its approximation error representable on a coarse mesh. Use the signed convention $e_h=u_h^{\ast }-v_h$ and the linear-system residual $r_h=b_h-A_h{v}_h=A_h{e}_h$. A prolongation linear map $P:{\mathbb{R}}^m\to {\mathbb{R}}^n$ interpolates coarse corrections into fine-grid corrections, and a restriction linear map $R:{\mathbb{R}}^n\to {\mathbb{R}}^m$ transfers the linear-system residual. Solve $A_H{z}_H=R{r}_h$ exactly or approximately and update $v_h\leftarrow v_h+P{z}_H$. The plus sign follows from defining the approximation error as exact minus approximate. It is the correction equation's right-hand side $R{r}_h$, rather than merely restricted solution values, that determines the update.

For the multigrid method model $A_h=h^{-2}\mathrm{tridiag}(-1,2,-1)$, take $n=2m+1$, so $H=2h$ and the coarse nodes coincide with every second fine node. Use linear interpolation with zero boundary corrections $z_0=z_{m+1}=0$:Use full-weighting restriction for the interior linear-system residual:Here $P^T$ is the matrix transpose in ordinary unweighted coordinates. With these specific transfers, the Galerkin coarse-grid operator isThus it equals the rediscretized Poisson equation operator on this constant-coefficient one-dimensional mesh. The equality is special to the stated model and transfers. In particular, dropping $h^{-2}$ from the fine matrix while using $H^{-2}$ on the coarse mesh changes the correction unless the right-hand sides and transfers are rescaled consistently.

Take seven interior points, $h=1/8$, three coarse unknowns, and the deliberately constructed approximation errorFor example, choose $b_h=0$, so $u_h^{\ast }=0$ and $v_h=-e_h$. Direct matrix multiplication givesThe exact coarse solve returns $z_H=z$, so adding $P{z}_H$ removes the entire chosen approximation error. A broad triangular error can have a sharply localized linear-system residual: the latter measures discrete curvature, not error height. This is why the two should not be confused. A smooth sine mode instead has linear-system residual ${\lambda }_k(A_h)e_h$, so interpreting its magnitude also requires the eigenvalue and the equation's scaling.

The algebra explains the exact cancellation beyond this example. Assume $P$ has linearly independent columns and choose an invertible Galerkin coarse-grid operator $A_H=R{A}_{h}P$. With an exact coarse solve, the iteration matrix for the remaining approximation error isThe short proof is to substitute $R{A}_{h}P=A_H$. Thus every vector in the column space of $P$ is eliminated, and the corrected linear-system residual restricts to zero. These are exact projection identities, not a statement that every visually smooth vector belongs to that column space. If $A_h$ is a symmetric matrix and a positive-definite matrix, and $R=c{P}^T$ with $c>0$, then $A_H$ is also a positive-definite matrix. Moreover $P^T{A}_{h}C{e}_h=0$: $C$ is an orthogonal projection onto the complement of the column space of $P$ in the energy norm $\Vert q{\Vert }_{A_h}=\sqrt{q^T{A}_{h}q}$. Equivalently, the added correction is the best approximation to $e_h$ from that column space in this energy norm. Without these symmetry and transfer assumptions, the projection need not be orthogonal.^[ref]

For an approximate coarse solve represented by a fixed linear map $B_H$, replace $A_H^{-1}$ by $B_H$. ThenThere is no exact cancellation of coarse-representable approximation error unless $B_H{A}_H=I$ on the relevant directions. For the triangular example, deliberately returning half the exact correction, $B_H=\frac{1}{2}{A}_H^{-1}$, leaves $e_h/2$, as the figure shows. This controlled mathematical comparison illustrates an incomplete coarse solve; it is not a measured performance result or a prescription for a geometric multigrid V-cycle. More generally, if $z_H^{\ast }=A_H^{-1}R{r}_h$, then an approximate $z_H$ leaves $C{e}_h+P(z_H^{\ast }-z_H)$, separating the nonrepresentable remainder from the coarse-solve defect.

With pre- and post-relaxation iteration matrices $S_{\mathrm{pre}}$ and $S_{\mathrm{post}}$, a two-grid error step has iteration matrix $E=S_{\mathrm{post}}{C}_B{S}_{\mathrm{pre}}$. A geometric multigrid V-cycle supplies $B_H$ by one recursive coarse cycle from zero, with a direct solve only at the bottom. Effective smoothing, a coarse column space that approximates the surviving approximation error, and a sufficiently accurate coarse correction must work together. Coarsening alone supplies no convergence guarantee, and correcting an arbitrary fine-grid vector exactly would require a coarse column space large enough to contain it.

Two real symmetric matrices are coaxial when they share an orthonormal eigenbasis. Equivalently they commute. Degenerate eigenspaces can have several choices of shared axes.

For commuting real symmetric matrices $A,B$, each eigenspace of $A$ is invariant under $B$: $A(Bv)=B(Av)=\lambda Bv$. The restriction of $B$ to that eigenspace is again symmetric. The spectral theorem therefore supplies an orthonormal eigenbasis for $B$ inside each eigenspace of $A$. Combining these bases gives a common orthonormal eigenbasis of the whole space. Conversely, two symmetric matrices diagonal in the same orthonormal basis commute.

A real symmetric matrix admitting a finite sum of nonnegative rank-one matrices $x_j{x}_j^T$. It is both a positive semidefinite matrix and a nonnegative matrix, but these two properties alone need not imply membership in the completely positive cone in arbitrary dimension. This matrix notion is distinct from a completely positive map.

Conic optimization using the completely positive cone. For a real symmetric matrix $Q$, the trace-normalized program $\min \{⟨Q,X{⟩}_F:X\in {\mathrm{CP}}_n,\mathrm{tr}X=1\}$ minimizes a weighted average of nonnegative-unit-vector Rayleigh quotients. The weights are the squared norms of the factors in $X={\sum }_j{x}_j{x}_j^T$. Hence a minimizing rank-one factor attains the same value as the original orthant minimum.

For a second-degree equation $A{x}^2+Bxy+C{y}^2+Dx+Ey+F=0$, the number ${\Delta }_2=B^2-4AC$ is the discriminant of a binary quadratic form associated with its quadratic part. For a nonempty, nondegenerate real conic section, a negative value gives an ellipse, zero a parabola, and a positive value a hyperbola. It is invariant under a rotation of orthonormal coordinates.^[ref]

A short explanation uses the symmetric matrixAn orthogonal matrix $R$ changes this matrix to $R^{\mathsf{T}}HR$, whose determinant equals $\det H$. The spectral theorem for real symmetric matrices then removes the mixed term. Equal-sign, opposite-sign and one-zero eigenvalues give the three types after the remaining linear terms and offsets are considered.

The qualification matters. The equations $x^2+y^2=0$, $y^2=0$ and $xy=0$ describe a point, a repeated straight line, and two crossing straight lines, respectively. Their quadratic discriminants have the signs expected of ellipse, parabola and hyperbola types, but all three are degenerate conics. Also, $x^2+y^2=-1$ has an empty set of real solutions despite its negative quadratic discriminant.

If the constant symmetric matrix $A$ satisfies $A\xi \cdot \xi \ge \theta |\xi {|}^2$, then every smooth function $u$ with compact support satisfiesIndeed, the Fourier transform of a derivative and the Plancherel theorem turn the squared norms into integrals with Fourier multipliers $|\xi {|}^4$ and $(A\xi \cdot \xi {)}^2$.

A stationary iterative method for a linear system converges to its specified fixed point for every initial vector if and only if its iteration matrix satisfies $\rho (H)<1$, where the spectral radius is the largest modulus of an eigenvalue.^[ref]

For a diagonalizable matrix, write $H=V\Lambda V^{-1}$. Then $H^k=V{\Lambda }^k{V}^{-1}$, so each eigenvector coefficient tends to zero exactly when its eigenvalue has modulus less than one. For a general matrix, the Jordan normal form gives the same result: a Jordan block $J=\lambda I+K$ with a nilpotent matrix $K$ of size $m$ satisfiesIf $0<|\lambda |<1$, every coefficient tends to zero because exponential decay beats any fixed polynomial in $k$; if $\lambda =0$, the block vanishes once $k\ge m$. Conversely, an eigenvector with $|\lambda |\ge 1$ provides an initial error that cannot tend to zero. For a real matrix with complex eigenvalues, the same obstruction appears in the real invariant subspace spanned by the real and imaginary parts of an eigenvector.

The words "every initial vector" matter. For example, $H=\mathrm{diag}(3/2,1/2)$ fails the criterion, but $e^{(0)}=(0,1{)}^T$ still tends to zero. Here a generic initial error has a nonzero first coordinate and diverges; the exceptional errors lie on the second coordinate axis. With $H=\mathrm{diag}(-1,1/2)$, generic errors oscillate rather than diverge in norm, while the same exceptional axis still converges. Both are valid matrix splittings with $M=I$ and $A=I-H$. In general the convergent errors form the direct sum of the generalized eigenspaces for $|\lambda |<1$; if $\rho (H)\ge 1$, this is a proper linear subspace.

A small spectral radius describes eventual convergence, but does not imply that the Euclidean norm of the error decreases on every step for a non-normal matrix. An operator norm bound $\Vert H\Vert <1$ does give the stepwise estimate $\Vert e^{(k)}\Vert \le \Vert H{\Vert }^k\Vert e^{(0)}\Vert$. For a real symmetric matrix, the matrix 2-norm equals its spectral radius, making this particularly direct.

The real symmetric matrices that are copositive matrices form a closed convex cone:Each fixed $x$ gives a closed linear inequality in $A$. Their intersection is therefore closed and convex, and it is preserved by nonnegative scaling.