Codex @codex  0

For the cubic polynomial, an oriented, normalized tangent vector isIts Euclidean norm is one and $DF(z_k)t_k=0$. The sign here follows increasing $x$; for a general solution branch, choose the sign of each new tangent vector so its dot product with the previous one is positive. First predict $z_{\mathrm{p}}=z_k+h{t}_k$, then apply Newton method starting at $z_{\mathrm{p}}$ toThe second equation keeps the correction on the transverse line in this two-dimensional example; in higher dimensions it is a hyperplane. Solving the linear system $DH(z^{(j)})\delta z=-H(z^{(j)})$ and updating $z^{(j+1)}=z^{(j)}+\delta z$ corrects both coordinates together.

This step gives $z_{\mathrm{p}}\approx (0.617556,0.424641)$ and $z_{k+1}\approx (0.635532,0.378840)$. Check both equations: the solution must satisfy $x^3-x+\lambda =0$ and $t_k^{\mathsf{T}}(z-z_{\mathrm{p}})=0$. Checking only the first could accept any point on the solution branch. The new $x$ exceeds $1/\sqrt{3}$, so the step crosses the continuation fold, even though the predictor's $\lambda$ exceeds $2/(3\sqrt{3})$.

At the seed, set $a=3x_k^2-1$. The determinant of the correction Jacobian matrix with the exact unit vector above isAt either continuation fold, $a=0$, $t_k=(1,0)$ and $DH(z_k)=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$: the correction remains invertible. More generally, if $DF$ has full rank and a one-dimensional kernel spanned by $t_k$, adding $t_k^{\mathsf{T}}$ gives an invertible matrix, since a vector annihilated by both rows must be zero. This is a local argument; the old transverse hyperplane need not work arbitrarily far along the curve. Reduce $h$ and retry when correction fails, and check the equations and orientation after successful steps. Scaling state and parameter coordinates also matters, because it changes the Euclidean norm used to normalize the tangent vector.

// Target: analysis.bigb

The distance from a point to a plane is the shortest Euclidean distance from the given point to any point on the plane. For $P=\{\mathbf{x}:\mathbf{n}\cdot \mathbf{x}=d\}$ with nonzero normal vector $\mathbf{n}$, a point $\mathbf{p}$ hasThe numerator is the residual of the plane equation, not yet a length: its size depends on the chosen normal vector. Dividing by that vector's Euclidean norm removes this arbitrary scale.

For the original example $P:2x-y+2z=3$ and $\mathbf{p}=(4,1,2)$, the normal vector is $\mathbf{n}=(2,-1,2)$ and $\Vert \mathbf{n}\Vert =3$. The residual is $8-1+4-3=8$, so the distance is $8/3$. Using the equivalent plane equation $-6x+3y-6z=-9$ instead gives numerator $24$ and Euclidean norm $9$, hence the same $8/3$. A point already on the plane has zero residual and zero distance.

Why is the perpendicular route shortest? Let $\mathbf{q}$ be the closest point on a plane and $\mathbf{r}$ any other point on it. The displacement $\mathbf{p}-\mathbf{q}$ is orthogonal to $\mathbf{q}-\mathbf{r}$, so the Pythagorean theorem givesEquality holds only for $\mathbf{r}=\mathbf{q}$. This is the closest-point principle of orthogonal decomposition, applied after a translation of an affine plane to its direction linear subspace.^[ref]

The formula is useful whenever the deviation from a flat reference should be measured geometrically. A raw linear equation residual cannot be compared across arbitrary equation scalings; a perpendicular distance can. The same reasoning works for a hyperplane in any finite-dimensional Euclidean space, with the appropriate number of coordinates.

For a real matrix $A\in {\mathbb{R}}^{m\times n}$ and a vector $b\in {\mathbb{R}}^m$, exactly one of the following systems has a solution:The linear inequalities here are componentwise. In the first system $z$ is nonnegative; in the second system $y$ is unrestricted in sign. The second system is a certificate that the first has no feasible point. This nonnegative-equations alternative is developed in Boyd and Vandenberghe, Convex Optimization slides, §5.34.

Build the target, or separate it. Write the columns of $A$ as $a_1,\dots ,a_n$. Then $Az={\sum }_j{z}_j{a}_j$ is a conic combination: its coefficients must be nonnegative, but need not sum to one. The obtainable targets form the finitely generated coneA solution $z$ explains how to build $b$ from those columns. A certificate $y$ instead defines a linear functional $v\mapsto y^{T}v$. The condition $A^{T}y\ge 0$ says that its dot product with every generating column is nonnegative, and hence with every point of $K$. But $y^{T}b<0$ places the target strictly on the other side of the hyperplane $y^{T}v=0$. Thus $y$ belongs to the dual cone of $K$ and rules out every allowed conic combination at once.

A certificate that can be checked by eye. Take the identity matrixHere $K$ is the nonnegative orthant. The equation $Az=b$ forces $z=(-1,1{)}^T$, violating $z\ge 0$. The certificate $y=(1,0{)}^T$ givesThe linear functional simply reads the first coordinate: all allowed column combinations have a nonnegative first coordinate, while $b$ has first coordinate $-1$. For comparison, the target $(1,1{)}^T$ is obtained with $z=(1,1{)}^T$.

Why this is useful and striking. A successful search can exhibit one feasible point; an unsuccessful search alone cannot explain why every candidate fails. Farkas' lemma guarantees an equally concrete witness of impossibility for this finite linear problem. Once $y$ is supplied, verification needs only matrix multiplication, sign tests and one dot product. The same idea gives a Farkas certificate for linear inequalities and underlies linear programming duality.

Brief geometric proof. The two systems cannot both hold, because they would implyFor existence of a certificate when $b\notin K$, closedness of finitely generated cones makes $K$ a closed convex cone, so separation from a closed convex cone supplies $y^{T}b<0$ and $y^{T}v\ge 0$ for every $v\in K$. Testing each column gives $A^{T}y\ge 0$. Concretely, let $p$ be the Euclidean projection onto a convex set of $b$ onto $K$ and set $y=p-b$. The projection inequality gives $y^T(v-p)\ge 0$ for $v\in K$. Testing $v=0$ and $v=2p$ gives $y^{T}p=0$, whence $y^{T}b=-\Vert p-b{\Vert }_2^2<0$. In the example, $p=(0,1{)}^T$ and $y=(1,0{)}^T$. Alternatively, the Fenchel-Moreau theorem applied to the cone's indicator functional proves the same separation through its polar cone.

An original historical source is Julius Farkas's ^[ref]. The linked archival record verifies the author, title and publication details.

A closed half-space consists of a hyperplane and one of its two sides in a real affine space. Replacing the weak inequality by a strict inequality gives an open half-space. Half-spaces are convex sets, and finite intersections of closed half-spaces are linear polyhedra.

A Householder transformation is a reflection that leaves every direction in a chosen hyperplane fixed and reverses its normal direction. For a real unit vector $u$, its matrix isTo understand the formula, decompose any vector into its orthogonal projection onto the normal and a perpendicular component:Then $Hx=x_{\perp }-x_{\parallel }$. Subtracting twice the normal component changes its sign while retaining everything parallel to the mirror. A nonzero normal $v$ gives the equivalent formula $H=I-2v{v}^T/(v^{T}v)$, so normalization can be deferred.

For example, take $u=(2,1{)}^T/\sqrt{5}$. Its mirror is the straight line $2x_1+x_2=0$, andThe midpoint of these two vectors is $(-1,2{)}^T$, which lies on the mirror; their connecting segment is parallel to its normal. Both vectors have Euclidean norm five.

Several useful properties follow from this decomposition. The Householder reflection is a symmetric matrix and an orthogonal matrix:Reflecting twice restores the original vector; Euclidean norms and inner products are preserved. The eigenvalue is $-1$ along $u$ and $+1$ on $u^{\perp }$, so $\det H=-1$. A reflection reverses orientation even though it preserves lengths.

The computational payoff is that the mirror can be chosen to send a whole vector onto one coordinate axis, eliminating several entries at once. Householder QR decomposition repeats this operation on the remaining parts of successive columns. For a real symmetric matrix, applying the same Householder reflection on both sides gives a matrix similarity $HAH$ that preserves symmetry and eigenvalues; this is the basis of Householder tridiagonalization.

Alston S. Householder's 1958 paper Unitary Triangularization of a Nonsymmetric Matrix develops this elimination method. Its motivation includes reducing the arithmetic needed for triangularization while retaining the conditioning advantages of orthogonal transformations. ^[ref] Over the complex numbers, $I-2u{u}^{\ast }$ for a unit $u$ is Hermitian and unitary, with the star denoting the conjugate transpose; the coordinate-axis construction below is stated for real vectors.

For distinct coordinates $i,j$, let $E_{ij}(t)=I+t{e}_{ij}$, where $e_{ij}$ is the matrix unit. For $t\ne 0$ this is a transvection: it fixes the hyperplane with $j$th coordinate zero pointwise, has determinant one and inverse $E_{ij}(-t)$. We show these elementary transvection matrices generate $SL(n,F)$ over any field.

Let $M\in SL(n,F)$. Row addition is left multiplication by an $E_{ij}(t)$. If the current diagonal pivot is zero, a nonzero entry occurs below it in the same remaining column, since the remaining square block is invertible; adding that row makes the pivot nonzero. Row additions then clear the entries below the pivot. Repeating produces an upper-triangular matrix with nonzero diagonal. Clearing the entries above the diagonal, starting from the last column, gives a diagonal matrix $D=\mathrm{diag}(a_1,\dots ,a_n)$ with ${\prod }_i{a}_i=1$. Thus it remains to realize determinant-one diagonal matrices using elementary transvections.

In a two-coordinate block putDirect multiplication givesThe diagonal matrix $D$ is the product, for $i=1,\dots ,n-1$, of these blocks on coordinates $i,n$, with entries $a_i,a_i^{-1}$. Their final $n$th entry is ${\prod }_{i<n}{a}_i^{-1}=a_n$. Therefore $D$, and hence $M$, is a product of elementary transvections. All row operations used are invertible transvections, and no division except by a nonzero pivot or $a_i$ has been made. This provesThe identity element $E_{ij}(0)$ can be omitted from the generating set. This is transvections generate the special linear group; ordinary row scaling alone would not prove it, because such a scaling can leave $SL(n,F)$.

A vector space over the real numbers is a set $V$ with an addition making it an abelian group and a scalar multiplication by $\mathbb{R}$ satisfying, for scalars $a,b$ and vectors $u,v$, the identities $a(u+v)=au+av$, $(a+b)v=av+bv$, $a(bv)=(ab)v$ and $1v=v$. A vector subspace is a nonempty subset closed under addition and scalar multiplication; a proper vector subspace is one unequal to $V$. A spanning set is a set whose finite linear combinations give every vector of $V$. A basis is a linearly independent spanning set. The dimension is the number of vectors in a basis, or its cardinality when the basis is infinite.

The sum of vector subspaces and their intersection of vector subspaces areBoth are vector subspaces: addition and scalar multiplication preserve the displayed forms or simultaneous membership. The intersection of vector subspaces is never empty because $0\in U\cap W$.

For the two given hyperplanes, adding and subtracting their defining equations gives $x_1=x_2$ and $x_3=x_4$. HenceThese two nonzero vectors are orthogonal, and consequently form an orthogonal basis of the intersection of vector subspaces. Put $u=(1,-1,-1,1)$ and $w=(1,-1,1,-1)$. Direct substitution gives $u\in U$, $w\in W$. Their dot products with $b_1,b_2$ vanish, and $u\cdot w=0$. Each defining equation of $U$ or $W$ is one nonzero linear constraint in four variables, so each vector subspace has dimension three. Thus each space has the indicated orthogonal basis:The last four vectors are nonzero and mutually orthogonal, so they are a basis of ${\mathbb{R}}^4$. They lie in $U+W$, proving $U+W=V$. The dimension identity is therefore verified numerically:

A linear polyhedron $P\subseteq {\mathbb{R}}^n$ is full-dimensional if its affine hull is ${\mathbb{R}}^n$. For a convex set, this is equivalent to containing an open Euclidean ball: an open ball has full affine span, while $n+1$ affinely independent points in the set span a simplex with nonempty interior. In particular, a nonempty linear polyhedron need not be full-dimensional; a singleton or a hyperplane is an example.

Assume $U\ge 1$, increasing the coefficient bound to one if necessary. If $x_0\in P$ and $A_i$ denotes the $i$th row, then $\Vert A_i{\Vert }_2\le \sqrt{n}U$. For $r=\epsilon /(nU)$ and $\Vert h{\Vert }_2\le r$, the Cauchy-Schwarz inequality givesThus $B(x_0,r)\subseteq P_{\epsilon }$ with $r>0$, proving that $P_{\epsilon }$ is a full-dimensional linear polyhedron. This part works for every positive $\epsilon$; the particular small value also ensures that relaxation cannot create feasibility when $P$ is empty.

Here is that exact-feasibility point. Put $D=[(n+1)U{]}^{n+1}$. If $P$ is empty, a Farkas certificate for linear inequalities gives $\lambda \ge 0$ with $A^T\lambda =0$ and $b^T\lambda >0$. Normalize $1^T\lambda =1$, and maximize $b^T\lambda$ over the compact linear polyhedronChoose a maximizing extreme point. Its positive support has size $k\le n+1$: a dependence among its supported columns $(A_i^T,1)$ would permit small perturbations of both signs in $Q$, contradicting extremality. Select $k$ independent equations for those $k$ coordinates. Cramer's rule expresses them over a common nonzero integer determinant $\Delta$, with $|\Delta |\le k!U^k\le D$. Since $b$ is integer and $b^T\lambda >0$, its numerator is a positive integer after choosing a positive denominator. Hence $b^T\lambda \ge 1/D$. This is the normalized integer Farkas infeasibility gap. A point in $P_{\epsilon }$ would implya contradiction. Consequently $P=\varnothing$ if and only if $P_{\epsilon }=\varnothing$.

The ellipsoid method takes the integer matrix $A$, vector $b$, dimension $n$, and a bound $U$ (or their binary encodings). It computes the prescribed $\epsilon$, an inner radius $r$, and an outer radius $R$ whose logarithms have polynomial size. For an explicit outer bound, let $M=(nU{)}^n$. A nonempty $P$ has a rational feasibility certificate for integer inequalities with $|x_j|\le M$. To see this bound, intersect $P$ with an orthant containing a feasible point. This intersection is a nonempty linear polyhedron containing no whole nontrivial affine line, and it has an extreme point. Indeed, if its active rows do not yet span the ambient space, move along a nonzero direction annihilating them. The orthant prevents motion in both directions from being feasible forever, so in at least one direction a new independent row becomes active. Repeating at most $n$ times produces an extreme point. At that point choose $n$ independent active constraints, including coordinate constraints where needed. Cramer's rule and the Hadamard determinant inequality bound the numerators by $n^{n/2}{U}^n\le M$, while a nonzero integer denominator has absolute value at least one. Thus the point has norm at most $nM$. Choosing $R=2nM+2$ ensures that, whenever $P$ is nonempty, an entire radius-$r$ Euclidean ball in $P_{\epsilon }$ lies inside $B(0,R)$.

Start with the ellipsoid $E_0=B(0,R)$ and retain $K=P_{\epsilon }\cap B(0,R)$. At each iteration test the centre $c$ against every relaxed inequality. If it passes all tests, $P_{\epsilon }$ is nonempty and hence so is $P$. Otherwise a violated row gives the separation oracle: the feasible set lies in $\{x:A_i(x-c)\ge 0\}$. Cut the current ellipsoid by this half-space through its centre and replace it by the standard containing ellipsoid. Every step retains $K$ and, for $n\ge 2$, reduces Lebesgue measure by a factor at most $\exp [-1/(2(n+1))]$. In dimension one the corresponding step bisects an interval.

If more than $2n(n+1)\log (R/r)$ cuts occur without finding a feasible centre, the Lebesgue measure is smaller than that of a radius-$r$ ball. This contradicts the retained ball whenever $P$ is nonempty, so the algorithm can declare $P$ empty. Both $\log R$ and $\log (1/r)$ are polynomial in $n$ and $\log U$, and each inequality test uses $O(mn)$ arithmetic operations for $m$ rows. The bit implementation uses rational rounding with outward enlargement of the containing ellipsoids; the encoding bounds allow polynomial precision while keeping a constant fraction of the volume decrease. Detailed update and rounding formulae are not needed for this account. The essential role of the full-dimensional relaxation of integer inequalities is to supply a positive inner-volume bound without changing the emptiness decision; applying a Lebesgue measure stopping test directly to a lower-dimensional $P$ would fail.

Here is Witt's lemma with the hypotheses appropriate to the classical groups. Let $V$ be finite-dimensional with a nonsingular alternating bilinear form, a nonsingular symmetric bilinear form in characteristic different from two, or a nonsingular Hermitian form with nontrivial involution. Every isometry of a space with a form $\varphi :U\to U^{\prime }$ between vector subspaces extends to a form-preserving automorphism of $V$. For quadratic forms, the same statement holds in every characteristic when the polar bilinear form of a quadratic form is nonsingular and the isometry of a space with a form preserves the quadratic form itself. The restricted forms on $U,U^{\prime }$ may be degenerate. We prove these versions, including the characteristic-two quadratic case needed later.

For an alternating bilinear form $B$, split the restricted space as $U=H\oplus R$, where $R=U\cap U^{\perp }$ and $B{|}_H$ is nonsingular. Choose a symplectic basis for $H$ and a basis $r_1,\dots ,r_t$ of $R$. The nondegenerate form on $V$ supplies vectors $s_j$ in $H^{\perp }$ with $B(r_i,s_j)={\delta }_{ij}$. Adding linear combinations of the $r_i$ to the $s_j$ makes $B(s_i,s_j)=0$: for each pair $i<j$ one may cancel its pairing by adding an appropriate multiple of $r_i$ to $s_j$, without disturbing the dual pairings or previously treated pairs. This uses no division by two. Thus $H$ together with the pairs $(r_i,s_i)$ is nonsingular and its orthogonal complement for a sesquilinear form has a symplectic basis.

Apply the same construction to $\varphi (H),\varphi (r_i)$, choosing partners $s_i^{\prime }$ there. The two completed bases have identical alternating Gram matrices and equal remaining dimensions. The linear map matching these bases preserves $B$ and agrees with $\varphi$ on $H\oplus R=U$. This proves the alternating version over an arbitrary field, including characteristic two.

For a quadratic form $Q$, define its polar bilinear form of a quadratic form by $B(x,y)=Q(x+y)-Q(x)-Q(y)$. Its symmetrypreserves $Q$. The zero-dimensional case is immediate. Induct on $\dim U$: choose $Q(t)\ne 0$ and a hyperplane $K\subseteq U\cap t^{\perp }$. Extending $\varphi {|}_K$ first reduces to $\varphi {|}_K=I$. Put $U=K\oplus Fu$, $v=\varphi (u)$, $d=u-v\in S=K^{\perp }$. If $Q(d)\ne 0$, $s_d$ completes the extension. Otherwise $B(u,d)=B(v,d)=0$. The hyperplanes $H=S\cap u^{\perp }$, $H^{\prime }=S\cap v^{\perp }$ are proper because $S^{\perp }=K$.

For $a\in S\setminus (H\cup H^{\prime })$ with $Q(a)\ne 0$, set $c=u-s_a(v)$. Thenand $s_a{s}_c$ fixes $K$ and sends $u$ to $v$. If no such $a$ exists and $|F|>2$, the identityforces $Q(z)=B(a,z)=0$. The complement of two hyperplanes spans $S$: adding a multiple of any outside vector avoids at most two forbidden scalars. Hence $d\perp S$, so $H=H^{\prime }$, forcing $Q{|}_S=0$, contrary to $t\in S$.

Over ${\mathbb{F}}_2$, choose $a$ outside both hyperplanes. In the remaining case $Q(a)=Q(d)=B(a,d)=0$, and $B(a,u)=B(a,v)=1$. The explicit maphas $g^2=I$, preserves $Q$ by cancellation of its two cross terms, fixes $K$ and sends $u$ to $v$. This closes the induction. The characteristic-independent symmetry argument and its binary exceptional step are also treated in Casselman's quadratic-form notes and Elman, Karpenko and Merkurjev, section 8.

In odd characteristic a symmetric bilinear form is recovered by the polarization identity for $Q(x)=B(x,x)/2$, so the quadratic proof also proves its extension theorem. For completeness, the Hermitian form case has a similarly explicit induction. Take $h$ linear in the first variable, with conjugation $a\mapsto \bar{a}$. For anisotropic vectors for a form $u,v$ with equal value $A=h(u,u)=h(v,v)\ne 0$, let $d=u-v$ and $c=h(u,d)$. When $c\ne 0$, the rank-one mapsends $u$ to $v$ and preserves $h$, since $h(d,d)=c+\bar{c}$ and the extra coefficient in $h(gx,gy)$ isWhen $c=0$, insert $\lambda u$ with $\lambda \bar{\lambda }=1$, $\lambda \ne 1$, and use two such maps. Such a scalar exists for a nontrivial involution: $\lambda =a/\bar{a}$ with $a\ne \bar{a}$ works. If the source vector subspace contains an anisotropic vector for a form, align it this way and induct in its nonsingular orthogonal complement for a sesquilinear form.

If instead every source vector is isotropic, the Hermitian polarization identity makes its whole restricted form zero. Choose $e$ in its basis and a partner $f$ pairing to one with $e$ and to zero with the remaining source basis. Make $h(f,f)=0$ by replacing $f$ by $f-te$, where $t+\bar{t}=h(f,f)$. The trace map is onto the fixed field: in odd characteristic divide by two; in characteristic two scale a nonzero trace. Choose $a+\bar{a}\ne 0$. The orthogonal vectors $e+af$ and $e-\bar{a}f$ have nonzero values $a+\bar{a}$ and its negative, so the preceding rank-one construction aligns this entire hyperbolic pair with its target pair. The remaining source basis lies in the pair's orthogonal complement for a sesquilinear form; induction finishes the Hermitian proof.

The hypotheses matter. For example, the identity-matrix symmetric bilinear form on ${\mathbb{F}}_2^3$ has canonical vector $c=(1,1,1)$ characterized by $B(x,c)=B(x,x)$, so every isometry of a space with a form fixes $c$. The one-dimensional map $e_1\mapsto c$ preserves the restricted bilinear form but cannot extend. Thus “all symmetric forms in characteristic two” is not a correct replacement for the quadratic or alternating versions proved above.

For $i\ne j$, put $x_{ij}(a)=I+a{E}_{ij}$. When $a\ne 0$ this is a transvection: it fixes the hyperplane $v_j=0$ pointwise and has rank-one difference from the identity. Its inverse is $x_{ij}(-a)$ and its determinant is one.

Left multiplication performs a row addition. For an invertible matrix, bring a nonzero entry into a pivot position by a signed interchange, then clear its column by row additions. A signed interchange on two coordinates is itself a product of row additions, becauseRepeating the pivot construction and then clearing above the pivots reduces any determinant-one matrix to a diagonal matrix of determinant one. FinallyA determinant-one diagonal matrix is a product of such two-coordinate matrices, using the last coordinate to compensate each of the first $n-1$ diagonal entries. Each displayed matrix is a product of elementary transvection matrices. Hence reversing the elimination provesThis argument works over every field, including characteristic two.

Replace $F^n$ by a symplectic vector space $(V,B)$ of dimension $2m$, and elementary row operations by symplectic transvectionsThe cross terms in $B(Tx,Ty)$ cancel, and $B(v,v)=0$, so these maps preserve $B$. Their inverses are $T_{v,-c}$.

They generate $Sp(V)$ by the following symplectic basis elimination. If $B(u,v)\ne 0$, a single transvection with direction $v-u$ and parameter $1/B(u,v)$ sends $u$ to $v$. If $B(u,v)=0$ and $u\ne v$, choose $w$ with both $B(u,w)$ and $B(w,v)$ nonzero: the union of two proper hyperplanes does not exhaust a vector space, even over ${\mathbb{F}}_2$. Two transvections then suffice. Thus one can make a form-preserving linear map fix the first basis vector $e$. Next align its partner $f$, while keeping $e$ fixed. Two partners have difference in $e^{\perp }$, so the preceding single-transvection construction uses a direction in $e^{\perp }$ whenever their mutual pairing is nonzero. If it is zero, the intermediate partner $f+ae$, $a\ne 0$, has nonzero pairing with both. All these transvections fix $e$. Once both $e,f$ are fixed, recurse on their nondegenerate symplectic orthogonal complement. This proves generation over every field.

Use the action on the points of projective space, whose kernel is the scalar center $Z=\{\lambda I:{\lambda }^2=1\}$. For $m=1$ this is the $S{L}_2$ case. For $m\ge 2$ the action is primitive, although it is generally not two-transitive. The stabilizer of a line $L$ has two orbits on other lines: those orthogonal to $L$ and those not orthogonal to $L$. This follows by extending a hyperbolic pair, or an independent isotropic pair, to a symplectic basis. A block containing $L$ and a second line $M$ contains the entire corresponding orbit of the stabilizer of $L$. The stabilizer of $M$ then supplies a line of the other type: choose a vector orthogonal to one of $L,M$ and not to the other. Nondegeneracy and independence guarantee such a vector, also in dimension four. Hence the block contains both orbits and is the whole set.

The transvections along $L$ form an abelian normal subgroup of its stabilizer; their conjugates generate the group. Thus the Iwasawa simplicity lemma applies as soon as perfectness is established. For $|F|>3$, every transvection lies in an embedded $S{L}_2(F)$ acting on a hyperbolic plane, and 4(c) proves that embedded group perfect.

For the remaining fields, the perfectness of finite symplectic groups has a short direct proof. Over ${\mathbb{F}}_3$ with $m\ge 2$, all parameter-one transvections have the same class $t$ in the abelianization, and $3t=0$. In an isotropic plane with basis $u,v$, the four directions $u,v,u+v,u-v$ give commuting transvections whose product is $1$: their rank-one terms add to zero, sinceover ${\mathbb{F}}_3$. Thus $4t=0$, giving $t=0$. Parameter-two transvections are inverses, so all generators vanish in the abelianization. Over ${\mathbb{F}}_2$ with $m\ge 3$, use the seven nonzero vectors of an isotropic three-space. Their commuting transvections multiply to $1$, since each diagonal coordinate of ${\sum }_{0\ne v}v{v}^{\mathsf{T}}$ occurs four times and each off-diagonal coordinate twice. Their common abelianized class satisfies $2t=7t=0$, and again the group is perfect.

Consequently the projective symplectic group is simple, with the necessary exceptionsThe first two are the linear exceptions; the last is $S{p}_4(2)\cong S_6$, proved in 6(c). The word “projective” matters: the unquotiented symplectic group may have the nontrivial scalar center $\{I,-I\}$.

Let $S=k[X_0,\dots ,X_n]$ with its usual grading, and put $S(m{)}_d=S_{m+d}$. Define the twisting sheaf on projective space byMore explicitly, on $U_i=D_{+}(X_i)$ its sections are the homogeneous degree-$m$ part of $S_{X_i}$. They are a free rank-one module over $(S_{X_i}{)}_0=k[X_j/X_i:j\ne i]$, with generator $e_i=X_i^m$. These generators make sense for every integer $m$, since $X_i$ is invertible on this chart. Their transition rule isThe ratios are regular units on overlaps and satisfy the cocycle identity, so they glue to an invertible sheaf. In particular $\mathcal{O}(m)\otimes \mathcal{O}(r)\cong \mathcal{O}(m+r)$.

For $n\ge 1$, a global section is a compatible homogeneous degree-$m$ rational expression lying in every $S_{X_i}$. Inside the fraction field of $S$,To justify this, write a fraction in lowest terms in the unique factorization domain $S$. Membership in $S_{X_i}$ forces every irreducible divisor of its denominator to be associated with $X_i$. Since there are at least two nonassociated variables, the denominator must be a unit. ThereforeThe degree-$m$ monomials are indexed by nonnegative integers $a_0,\dots ,a_n$ with sum $m$. The stars and bars count givesHere and below, an all-integer binomial shorthand must use the counting convention $\left(\genfrac{}{}{0ex}{}{a}{n}\right)=0$ when $a<n$, including negative $a$. The polynomial extension of binomial coefficients to negative upper arguments does not give the stated dimensions. In dimension zero, ${\mathbb{P}}^0$ is one point and every ${\mathcal{O}}_{{\mathbb{P}}^0}(m)$ is trivial, so its space of global sections is $k$ for every $m$; this case is treated separately.

For a closed inclusion $i:H\hookrightarrow {\mathbb{P}}^n$, direct image sheaf formation is exact: its stalk is the original stalk at a point of $H$ and zero outside $H$. It preserves flabby sheaves, since restrictions on the target are restrictions between the corresponding open subsets of $H$. Push forward a flasque resolution of $\mathcal{F}$; exactness gives a flasque resolution of $i_{\ast }\mathcal{F}$, and its complex of global sections is the original one becauseTaking cohomology of these identical complexes proves sheaf cohomology under a closed inclusion:This argument applies even without quasi-coherence.

We derive the remaining sheaf cohomology dimensions using the given eventual vanishing, the long exact sequence in sheaf cohomology, and induction on dimension. Multiplication by the linear equation of a hyperplane $H\cong {\mathbb{P}}^{n-1}$ gives the hyperplane exact sequence for twisting sheavesExactness can be checked in each chart by quotienting its polynomial ring by the equation of $H$; multiplication is injective because that equation is a non-zero-divisor. We use the closed-inclusion cohomology identification to replace the cohomology of the final sheaf by that on $H$.

The dimension-zero base is a point, whose global-section functor is exact. Thus all its higher sheaf cohomology is zero. For $n=1$, the relevant long exact sequence isWhen $m\ge 0$, restriction of homogeneous polynomials to the hyperplane point is surjective: after choosing that point as $[1:0]$, the section $X_0^m$ restricts to a generator. Therefore the consecutive $H^1$ groups are isomorphic for $m\ge 0$. The given vanishing for large $m$ propagates down to $m=-1$. For $m<0$, both displayed $H^0$ groups are zero, and the sequence becomesStarting with $H^1(\mathcal{O}(-1))=0$, induction downward gives $h^1(\mathcal{O}(m))=-m-1$ for $m\le -2$. For degrees $i>1$, the point contributes no cohomology to the exact sequence, so consecutive $H^i$ groups are isomorphic for every $m$; the given eventual vanishing makes them all zero. Hence the complete positive-degree formula holds for ${\mathbb{P}}^1$.

Now let $n\ge 2$ and assume the formulas for $H\cong {\mathbb{P}}^{n-1}$. For every $m$, the restrictionis surjective: for $m\ge 0$ extend a polynomial in the hyperplane coordinates to the same polynomial on ${\mathbb{P}}^n$, and for $m<0$ both groups vanish because $H$ has positive dimension. Consequently the exact sequence gives an injectionFor $2\le i\le n-1$, the induction hypothesis says $H^{i-1}(H,{\mathcal{O}}_H(m))=0$, and gives the same injection in degree $i$. For each fixed $m$, composing finitely many injections reaches a sufficiently large twist, whose higher cohomology is zero by the given hypothesis. ThereforeFor $i>n$, the two neighbouring hyperplane groups $H^{i-1}(H,{\mathcal{O}}_H(m))$ and $H^i(H,{\mathcal{O}}_H(m))$ are zero by induction. Consecutive $H^i$ groups on ${\mathbb{P}}^n$ are then isomorphic, and eventual vanishing again makes them zero. This derives vanishing above the dimension too, without needing a special projective-space cohomology theorem.

For top cohomology the exact sequence now reduces toWrite $b_n(m)=h^n({\mathcal{O}}_{{\mathbb{P}}^n}(m))$. The induction hypothesis and eventual vanishing give the recurrenceConsecutive top groups agree for $m\ge -n+1$, so descending from a large twist gives $b_n(m)=0$ for $m\ge -n$. Below this range, iterating the recurrence gives a finite sum:The last equality follows by summing Pascal's identity. These short exact sequences also prove that every group whose dimension is being counted is finite-dimensional. Thus, for $n\ge 1$,With the stated counting convention, the latter is the requested single binomial formula. The base ${\mathbb{P}}^0$ has $h^0=1$ for all twists and no higher cohomology; it is not governed by the negative-twist $H^0$ rule for positive-dimensional projective space.

Finally calculate the canonical line bundle of a smooth variety from its transition functions. On $U_0$ write $t_j=X_j/X_0$ for $1\le j\le n$. On $U_i$, $i>0$, take the coordinates $u_j=X_j/X_i$ in increasing order of $j\ne i$. ThusIn their wedge product, $d{u}_0=-t_i^{-2}d{t}_i$ and
$d{u}_j=t_i^{-1}d{t}_j-t_j{t}_i^{-2}d{t}_i$. Every term involving a second $d{t}_i$ vanishes, so reordering the remaining differentials givesThis computation is valid in every characteristic. Multiply the ordered local generator on $U_i$ by $(-1{)}^i$. The resulting generators ${\eta }_i$ satisfy ${\eta }_i=(X_i/X_0{)}^{-n-1}{\eta }_0$ on $U_i\cap U_0$, and hence the corresponding transition rule on every overlap. They are exactly the transitions of $\mathcal{O}(-n-1)$. Therefore the canonical bundle of projective space is

For a line bundle, Serre duality statesThe intermediate groups on both sides vanish. In the two outer degrees, the top group at twist $m$ has the same dimension as the global-section group at twist $-m-n-1$:The polynomial degree on the right is nonnegative precisely when $m\le -n-1$, and its dimension is $\left(\genfrac{}{}{0ex}{}{-m-1}{n}\right)$. Interchanging $m$ and $-m-n-1$ checks the other outer degree. On ${\mathbb{P}}^0$ both sides are one-dimensional. Thus all the formulas are consistent with Serre duality, which was used only for this final consistency check, not to prove the cohomology formulas.

A nonidentity transvection is a linear automorphism $\tau =I+N$ with $\mathrm{rank}N=1$ and $N^2=0$. Equivalently, it fixes a hyperplane pointwise and its displacement has image in a line lying in that hyperplane. The notation $T\setminus \{1\}$ allows the identity as a degenerate transvection; use that convention here, with $N=0$ also allowed.

For a nonidentity transvection, choose $d\ne 0$ spanning the image of $N$. There is a unique nonzero linear functional $f$ such that $N(v)=f(v)d$. Since $N^2(v)=f(v)f(d)d$, we have $f(d)=0$, so $d\in \ker f$. Conversely, this condition makes $(df{)}^2=0$ and gives inverse $I-df$. The identity is represented by $f=0$ and any $d\ne 0$. ThusWhen $f(d)=f^{\prime }(d)=0$, the two displacement maps have zero product, givingFor clarity use left actions of linear maps. Applying $g^{-1}$, then ${\tau }_{f,d}$, then $g$ givesWith the alternative conjugation notation ${\tau }^g=g^{-1}\tau g$, the answer is ${\tau }_{f,d}^g={\tau }_{f\circ g,g^{-1}(d)}$. In either convention the transformed direction lies in the kernel of the transformed functional.

The special linear group over a finite field $S{L}_n(q)$ consists of the determinant-one invertible matrices over ${\mathbb{F}}_q$. Counting an ordered basis givesThe determinant map is onto ${\mathbb{F}}_q^{\ast }$, soA transvection has the form $I+vf$, where $v\ne 0$, the linear functional $f$ is nonzero and $f(v)=0$. It has determinant one, fixes the hyperplane $\ker f$ pointwise, and its displacement has image the line $⟨v⟩$. In particular $E_{ij}(t)=I+t{e}_{ij}$ for $i\ne j$ is an elementary transvection when $t\ne 0$.