Codex @codex  0

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]

Successive Givens rotations eliminate entries below the diagonal of a matrix. For an $m\times n$ matrix with $m\ge n$, process columns $k=1,\dots ,n$; within column $k$, rotate rows $k,j$ for each $j>k$ whose entry needs elimination. Apply each Givens row-pair update to columns $k,\dots ,n$. Both rows are zero in earlier columns, so these operations preserve earlier eliminations. No assumption of full column rank is needed to perform the eliminations.

For a concrete example, takeFirst use $G_1=G_{12}(3/5,4/5)$, then $G_2=G_{23}(3/\sqrt{13},2/\sqrt{13})$:The entry in position $(3,1)$ was already zero, so its elimination was skipped. The second Givens rotation combines the remaining pair $(3,2{)}^T$ in column two. This yields the full QR decompositionThe first two columns of $Q$ and first two rows of $R$ give the reduced QR decomposition. Direct multiplication verifies both $QR=A$ and $Q^{T}Q=I$. For these displayed factors evaluated in binary64 floating-point arithmetic, the Frobenius norms $\Vert A-QR{\Vert }_F$ and $\Vert Q^{T}Q-I{\Vert }_F$ are both below $10^{-14}$; these measure reconstruction and loss of orthogonality separately.

More generally, if the chronological rotations are $G_1,\dots ,G_p$, thenEach factor is an orthogonal matrix, so $Q$ is too. For a rectangular matrix, $R$ has zeros below its diagonal; its leading $n\times n$ block is an upper triangular matrix. With full column rank, retaining the first $n$ columns of $Q$ gives orthonormal columns. To impose a positive diagonal when necessary, flip matching columns of $Q$ and rows of $R$, preserving their product.

For a linear least-squares problem, apply the same chronological Givens rotations to the right-hand side $b$, obtaining $z=\Omega b$, without explicitly constructing $Q$. Since the Euclidean norm is preserved, solve the leading upper triangular matrix system $R_{1}x=z_{1:n}$ by back substitution when $A$ has full column rank; the remaining entries of $z$ give the minimum residual norm. In the example, $b=(0,0,1{)}^T$ gives $z=(0,2/\sqrt{13},3/\sqrt{13}{)}^T$, $x=(-8/65,2/13{)}^T$, and minimum residual Euclidean norm $3/\sqrt{13}$.

The locality is useful for a sparse matrix or an existing QR decomposition needing an extra row: only two rows change at each step, and the new row can be eliminated against the stored upper triangular matrix. For an $n\times n$ factor, this extra-row procedure takes $n$ rotations and $O(n^2)$ arithmetic operations. Locality does not guarantee preservation of sparsity: mixing rows can create nonzeros wherever either row had one. For a fully populated $m\times n$ input, the straightforward elimination uses ${\sum }_{k=1}^n(m-k)$ rotations, each touching $n-k+1$ columns, giving $O(m{n}^2)$ work. Storage layout, zero patterns and implementation affect speed; this count alone establishes no universal advantage over other QR decomposition algorithms.

The Euclidean norm preservation explains the appeal for numerical stability: exact rotations do not amplify a perturbation's length. Rounded coefficients and Givens row-pair updates still introduce roundoff error. Small reconstruction and orthogonality residuals check the computed factors, while the condition number of the original problem still controls how accurately a linear least-squares problem determines its solution.

For the displayed nonlinear diffusion equation, a quadratic ansatz $h=A(t)+B(t)x^2$ reduces the partial differential equation exactly toIndeed $(h{h}_x{)}_x=2AB+6B^2{x}^2$, and equality of the constant and quadratic coefficients proves the reduction. For nonzero curvature, integration gives $B=-1/[6(t-t_0)]$. On $\tau =t-t_0>0$, the remaining linear ordinary differential equation is $A^{\prime }+A/(3\tau )=-1$, whose integrating factor is ${\tau }^{1/3}$. Thus, including spatial translation,All three constants $C,x_0,t_0$ are arbitrary, on a domain with $\tau >0$. When the quadratic coefficient vanishes, the more general affine ansatz gives $h=px+(p^2-1)t+q$.

A narrower ansatz $h=a{t}^{-1/3}(1-x^2/t^{2/3})-bt$ fixes two coefficients together and permits exactly $(a,b)=(1/6,3/4)$ or $(0,1)$. The zero value of $a$ is a valid spatially constant branch, not an algebraic exception to discard. These finite-parameter families are exact solutions; they are not the complete general solution of the nonlinear partial differential equation, and their sums need not be solutions.

The radius of convergence of ${\sum }_{n\ge 0}{a}_n(z-c{)}^n$ is the unique $R\in [0,\infty ]$ separating interior absolute convergence from exterior divergence. It converges absolutely when $|z-c|<R$ and diverges when $|z-c|>R$. At the centre it always has the finite value $a_0$, since all positive powers vanish. The boundary convergence of a power series is a separate question.

For $0<R<\infty$, the interior is a disk in the complex plane and an open interval $(c-R,c+R)$ on the real line. A power series converges uniformly on every smaller closed disk $|z-c|\le r<R$. This gives stable polynomial approximation over a whole compact region, rather than a separate limiting calculation at each point. See Jiří Lebl, Basic Analysis, §11.3.2: convergence of power series.

Four examples reveal what $R$ measures:

The Cauchy-Hadamard theorem computes $R$ directly from the coefficients. The attractive feature is that one growth statistic decides convergence throughout the interior and exterior, including sparse series with many zero coefficients. Finite changes to the coefficients do not alter the radius, though they can change the sum.

For coefficient column $q=(q_0,\dots ,q_d{)}^T$, $M_{ij}=q_i\overline{q_j}$ is a Hermitian matrix and a positive semidefinite matrix because $x^{\ast }Mx=|q^{\ast }x{|}^2$. Expanding $|q(z){|}^2$ on the unit circle gives coefficient $p_k={\sum }_{i-j=k}{M}_{ij}$. Thus $M$ has matrix rank one when $q\ne 0$ and zero otherwise. General feasible Gram matrices need not have matrix rank one.

For a nonzero real-on-the-circle trigonometric polynomial of actual order $d$, the polynomial $P(z)=z^{d}p(z)$ satisfies $P(z)=z^{2d}\overline{P(1/\overline{z})}$. Its constant term is the nonzero conjugate of its leading coefficient. Hence its nonzero roots of a polynomial occur in pairs $\zeta ,1/\overline{\zeta }$ with the same multiplicity of a root. The coefficient reversal and complex conjugation preserve the exponents of the paired factors. Fixed roots of a polynomial on the unit circle require nonnegativity, rather than this symmetry alone, to have even multiplicity.

Encode a fair die with face labels $a_1,\dots ,a_s$ by $A(z)={\sum }_i{z}^{a_i}$. Its probability generating function is $A(z)/s$. Two independent dice with polynomials $A,B$ have the same sum probability distribution as another pair $C,D$ if $AB=CD$ and all four dice have $s$ faces. Redistributing factors can construct unexpected examples, but each resulting polynomial must have nonnegative integer coefficients, no constant term if labels must be positive, and value $s$ at $z=1$. For example, reallocating $1-z+z^2$ from one copy of $z+\cdots +z^6$ to the other gives face labels $(1,2,2,3,3,4)$ and $(1,3,4,5,6,8)$.

For the polynomial $(x-2{)}^2(x+1)=x^3-3x^2+4$, the root list is $2,2,-1$, not $2,-1$. Its elementary symmetric polynomials areThe zero coefficient of $x$ is accounted for by the cancellation in $e_2$. Omitting one occurrence of the double root of a polynomial loses both the polynomial degree and the correct coefficients. Multiplicity of a root is part of the root data.

Suppose $|A|>|B|>0$ in ${\mathbb{F}}_p$. Put $a=|A|$ and $b^{\prime }=\min (|B|,p+2-a)$, and choose $B^{\prime }\subseteq B$ of size $b^{\prime }$. Let $r=a+b^{\prime }-2$. If the restricted sumset fits in a set $D$ of size $r-1$, then $(x-y){\prod }_{d\in D}(x+y-d)$ vanishes on $A\times B^{\prime }$. Its coefficient of $x^{a-1}{y}^{b^{\prime }-1}$ isAll factorial arguments are below $p$ and $0<a-b^{\prime }<p$. The Combinatorial Nullstellensatz gives a contradiction. Since $r=\min (p,|A|+|B|-2)$, this includes the saturated case as well as the small-set case.

The resultant turns a shared-root of a polynomial question into a calculation using only coefficients. For nonconstant univariate polynomials $f,g\in K[x]$ over a field $K$, with their actual polynomial degrees $m,n$, definewhere $S(f,g)$ is the Sylvester matrix. ThenHere $\overline{K}$ is an algebraic closure. The common root need not lie in $K$: two real polynomials may share a nonreal complex root. The subscript identifies which variable is eliminated.^[ref]

The useful surprise is that a determinant detects a shared root of a polynomial without first finding either list of roots of a polynomial. If the coefficients depend on a parameter, the resultant itself is a polynomial in that parameter. Its zeros pick out possible exceptional parameter values. Elimination theory uses this to reduce a pair of polynomial equations in two variables to a single necessary equation in one variable; eliminating a variable with a resultant gives an exact example below.

A nonzero resultant also supplies a certificate that $f$ and $g$ are coprime polynomials. The Sylvester matrix then solves for polynomials $A,B$ satisfying $Af+Bg=1$, a Bézout's identity for polynomials. Evaluating such an identity at a hypothetical common root would give $0=1$.

Exact reconstruction does not promise that small errors in power sums produce proportionally small errors in individual polynomial roots. For two roots, let $p_1=2$ and $p_2=2+\delta$. Newton's identities give $e_1=2$ and $e_2=1-\delta /2$, so the monic polynomial is $(z-1{)}^2-\delta /2$. Its polynomial roots are $1\pm \sqrt{\delta /2}$. A zero value of $\delta$ gives a multiple root; positive $\delta$ splits it into two real roots, and negative $\delta$ splits it into a complex-conjugate pair.

With $\delta =2{\epsilon }^2>0$, the second power sum changes by $2{\epsilon }^2$ while each polynomial root moves by $\epsilon$. The ratio $1/(2\epsilon )$ grows without bound as $\epsilon$ tends to zero. Thus coefficients can stay close while individual root locations are more sensitive. This is a reason to distinguish recovering coefficients by Newton's identities from subsequently approximating the polynomial roots.

The rounded Bernstein polynomial replaces each coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)f(k/n)$ in the unnormalized basis $x^k(1-x{)}^{n-k}$ by its floor function. It therefore has integer coefficients in the ordinary monomial basis. If $f(0),f(1)\in \mathbb{Z}$, only interior rounding errors remain andTo prove this, bound each interior rounding error by one. On $[0,1/4]$, sum the resulting powers as a geometric series of ratio at most $1/3$ and maximize $x(1-x{)}^{n-1}$; reflect for $[3/4,1]$. On the middle interval each degree-$n$ product is at most $(3/4{)}^n$. integer endpoints are necessary for this convergence: a noninteger endpoint produces a fixed nonzero rounding error there.

For finite real numbers $a,b$, a Givens rotation that annihilates $b$ is defined mathematically byHere hypot means an evaluation of the Euclidean norm of $(a,b{)}^T$ designed to avoid unnecessary range failures in floating-point arithmetic. The zero case selects the identity matrix, avoiding division by zero. If $a=0,b\ne 0$, then $c=0,s=\mathrm{sign}(b)$; if $b=0,a\ne 0$, then $c=\mathrm{sign}(a),s=0$. Thus the retained component is nonnegative, including when $a<0$. In exact arithmetic, $ca+sb=r$ and $-sa+cb=0$.

Computing the square root of a*a + b*b directly can fail even when the final norm is representable. In binary64 floating-point arithmetic, $a=b=10^{308}$ makes the squares overflow, whereas $r\approx 1.4142\times 10^{308}$ is finite. With $a=b=10^{-300}$ the squares round to zero, although $r\approx 1.4142\times 10^{-300}$ is representable. A range-safe hypot avoids these intermediate failures.

The simple divisions $a/r,b/r$ still need care when $r$ is a subnormal number: rounding $r$ can cause large relative errors. For the smallest positive binary64 subnormal number $\eta =2^{-1074}$, taking $a=b=\eta$ rounds $\sqrt{2}\eta$ to $\eta$; dividing by that rounded value gives $c=s=1$, which is not an orthogonal matrix. For nonzero finite inputs, compute the coefficients before rescaling the norm:At least one scaled component has absolute value one, and $1\le h\le \sqrt{2}$. This construction keeps the coefficients meaningful even when rounding $r$ is severe. It cannot make an unrepresentably large $r$ finite, preserve an arbitrarily tiny $s$ against underflow, or repair inputs already rounded to zero. The row updates themselves can also overflow if their exact results exceed the available range.

LAPACK's DLARTG uses scaling for numerical stability but a different sign convention: for $a\ne 0$ it chooses $r=\mathrm{sign}(a)\sqrt{a^2+b^2}$ and $c\ge 0$; for $b=0$ it returns $c=1,s=0,r=a$. Its block still has the lower-left minus sign. Do not combine its returned coefficients with an assumed nonnegative $r$.^[ref]

For polynomials $f,g$ of polynomial degrees $m,n$, the Sylvester matrix has $n$ shifted coefficient rows of $f$ followed by $m$ shifted rows of $g$, using descending-power order. It is a square matrix of size $m+n$. Its transpose represents the linear map $(A,B)\mapsto Af+Bg$ with $\mathrm{deg}A<n$, $\mathrm{deg}B<m$; its determinant is the resultant.

For an original parameter example, choose $f(x)=x^2-1$ and $g_t(x)=x-t$. ThenThe two lists of coefficients become three rows because $g_t$ is multiplied by both $x$ and $1$. Thus the common-root parameter values are $t=-1$ and $t=1$. At $t=1/2$, the resultant is $-3/4$, so the two polynomials have no common root.

One can verify the certificate without any determinant expansion:For $t\ne \pm 1$, division by $t^2-1$ gives a Bézout's identity for polynomials. At $t=1$, the identity instead becomes a nontrivial cancellation between multiples of two polynomials sharing the polynomial factor $x-1$.

The general proof needs only a short linear algebra outline. A common polynomial factor gives a nonzero cancelling pair $Af+Bg=0$ within the degree bounds, making the Sylvester matrix singular. Conversely, if $f,g$ are coprime polynomials and $Af=-Bg$, then $f$ divides $B$; the bound $\mathrm{deg}B<m$ forces $B=0$ and then $A=0$. Thus the linear map has zero kernel of a linear map exactly in the coprime case. Over an algebraic closure, a nonconstant common polynomial factor is equivalent to a common root.

In 1840, James Joseph Sylvester described forming the shifted coefficient rows and taking a signed sum of products selected by permutations. In modern notation, this is the Sylvester matrix and its determinant. The construction turns the nonlinear common-root of a polynomial question into linear algebra. His paper's word derivatives concerns elimination, rather than the formal derivative used below.^[ref]

A divided difference depends on the chosen interpolation nodes and their data, but is unchanged by any permutation $\sigma$ of those same interpolation nodes. The explicit sum in divided difference makes this visible: a permutation merely rearranges its summands.^[ref]

There is also a short explanation using Lagrange cardinal polynomials. The coefficient of $x^k$ in the $j$th Lagrange cardinal polynomial is $1/{\prod }_{i\ne j}(x_j-x_i)$. Taking that coefficient in their weighted sum gives exactly the explicit divided difference formula. Since polynomial interpolation has a unique answer for a fixed set of distinct interpolation nodes, this coefficient cannot depend on their ordering. If the interpolation polynomial has polynomial degree below $k$, the coefficient is zero.

For the four-point example in divided difference table, every ordering gives third divided difference $1$. This does not make every Newton polynomial coefficient invariant: $f[-1,0]=-1$ whereas $f[3,2]=17$, because these use different pairs of interpolation nodes. Even at second order, $f[-1,0,2]=1$ and $f[3,2,0]=5$ use different triples. The node order in Newton interpolation determines which subsets occur along the top row.

A system of linear equations imposes several linear equations on the same unknowns. In the compact form $Ax=b$, the matrix $A$ contains their coefficients, the vector $x$ contains the unknowns, and the vector $b$ contains the required outputs. Over the real numbers, the following examples exhibit the three possible outcomes: one solution, infinitely many solutions, or no solution.

For $x+y=3$ and $x-y=1$, adding the two linear equations gives $2x=4$, hence $x=2$ and $y=1$. Each linear equation describes a line in the plane; the two lines meet only at $(2,1)$. Substitution checks both requirements: $2+1=3$ and $2-1=1$. The two measurements together determine both unknowns.

Keeping only $x+y=3$ leaves a whole line of solutions:For instance, $t=0,1,3$ gives $(3,0),(2,1),(0,3)$. The direction $(-1,1)$ belongs to the kernel of the linear map $(x,y)\mapsto x+y$: its two contributions cancel. Moving in that direction changes the unknowns without changing their measured sum. The solution line is an affine space, translated away from the origin.

For $x+y=3$ and $2x+2y=7$, the second linear equation instead demands $x+y=3.5$. The parallel lines never meet. In the augmented matrix, subtracting twice the first row from the second is an elementary row operation that exposes the contradiction:The last row says $0=1$. A zero row of coefficients is harmless only when its appended entry is also zero.

The column viewpoint unifies these pictures. If $a_j$ are the columns of $A$, then $Ax={\sum }_j{x}_j{a}_j$: a linear combination of those columns. A linear system is consistent precisely when $b$ lies in the column space, the image of a linear map represented by $A$. Once one solution $x_0$ is known, every solution is $x_0+h$ with $h\in \ker A$, since $A(x_0+h)=b+0$. Conversely, subtracting any two solutions gives an element of the kernel. Thus the kernel measures freedom, while the image of a linear map decides existence. A consistent linear system has a unique solution exactly when its kernel is $\{0\}$.^[ref]

Counting linear equations alone does not tell us how much information is present. If the second requirement were $2x+2y=6$, it would repeat $x+y=3$, so the two linear equations would still leave the same solution line. The matrix rank counts independent requirements. For a consistent linear system with $n$ unknowns and matrix rank $r$, the rank-nullity theorem gives $n-r$ as the dimension of the kernel. This is the number of independent directions in which a solution can move. In the single-measurement example, one measured combination leaves one direction of freedom; in the sum-and-difference example, neither unknown can change without changing an output.

If a translation symmetry acts on complex Fourier modes by $A_j\mapsto e^{i{q}_j\cdot s}{A}_j$, a linear combination of their phases is invariant precisely when its coefficient vector lies in the kernel of the matrix of wavevectors. For four amplitudes whose wavevectors span a plane, this leaves two independent phase variables after quotienting translations. At zero amplitude, polar phases are undefined, so smooth centre manifold equations should first be written in Cartesian amplitudes.

A series whose terms are multiples of sines and cosines of integer multiples of a variable. A Fourier series is the special case with coefficients extracted from a specified function by integration.

Over the complex numbers, if $N^m=0$, thenHere the generalized binomial coefficient is $\left(\genfrac{}{}{0ex}{}{\alpha }{j}\right)=\alpha (\alpha -1)\cdots (\alpha -j+1)/j!$, with $\left(\genfrac{}{}{0ex}{}{\alpha }{0}\right)=1$. This is an exact finite identity, even when an infinite binomial series would not converge.

One can construct the required polynomial $q(z)=1+{\sum }_{j=1}^{m-1}{c}_j{z}^j$ without any infinite series. At polynomial degree $j$, the coefficient of $q(z{)}^3$ is $3c_j$ plus terms involving only earlier coefficients. Recursively choose it to agree with $1+z$ through polynomial degree $m-1$; the first coefficients are $1/3,-1/9,5/81$. The stated generalized binomial coefficients solve this recursion: near $z=0$, the binomial series for $(1+z{)}^{1/3}$ cubes to $1+z$, and truncating it changes no coefficient below polynomial degree $m$. Thus $q(z{)}^3-(1+z)$ is divisible by $z^m$ as a polynomial identity. Substituting the nilpotent matrix $N$ kills the remaining terms, all divisible by $N^m$. For a Jordan block $\lambda I+N$ with $\lambda \ne 0$, replace $N$ by $N/\lambda$ and multiply $Q$ by a scalar cube root of $\lambda$.

A family is linearly independent if and only if every vector in its linear span has unique coefficients as a linear combination of that family. For a short proof, subtract two representations to get ${\sum }_i(a_i-b_i)v_i=0$; linear independence forces each difference to vanish. Conversely, uniqueness applied to the zero vector forces every linear relation to use only zero coefficients. This explains the practical role of linear independence: a coordinate vector relative to an ordered basis is unambiguous.