Codex @codex  0

For a basis $e_1,\dots ,e_n$ with cyclic indexing, the vectors $e_j+e_{j+1}$ have coefficient matrix $I+S$, where $S$ cyclically shifts coordinates. Its determinant is $1-(-1{)}^n$. They therefore form a basis exactly when $n$ is odd over a field of characteristic different from two. For even $n$, alternating coefficients produce a nontrivial linear dependence.

A nonzero bipartite pure state is a product state if and only if all its partial inner products on the first subsystem lie in a common one-dimensional vector subspace of the second. For a product $|a⟩\otimes |b⟩$, every contraction equals $⟨u|a⟩|b⟩$. Conversely, contract against each vector of an orthonormal basis to write $|\Psi ⟩={\sum }_i|i⟩\otimes |{\chi }_i⟩$. If $|{\chi }_i⟩=c_i|b⟩$ for a common nonzero $|b⟩$, then $|\Psi ⟩=({\sum }_i{c}_i|i⟩)\otimes |b⟩$. Zero conditional vectors are allowed. A nontrivial linear dependence relation requires multipliers not both zero; allowing both multipliers to vanish would give no test at all.

A factor base is a finite set of small prime numbers over which selected auxiliary integers are completely factored. Some methods also record a sign coordinate for $-1$, which is not a prime number. A positive integer supported entirely on the chosen factor base gives an exponent vector; reducing that vector modulo two records which prime exponents are odd integers. The product is a square of a number precisely when every prime exponent is an even integer.

For the original toy $N=77$, use factor base $\{2,3,5\}$ and the two relationsThe residues have exponent vectors $(0,1,1)$ and $(2,1,1)$ in the order $(2,3,5)$. Adding the two vectors modulo two gives $(0,0,0)$, so multiplying the residues gives $15\cdot 60=900=30^2$. Consequentlyand $\gcd (X-Y,77)=7$ and $\gcd (X+Y,77)=11$. Neither individual residue was a square; combining the relations made all exponents even.

In a larger collection, choose relations $x_i^2\equiv r_i(\mathrm{mod}N)$ with positive residues $r_i={\prod }_{j=1}^B{p}_j^{e_{ji}}$. If a nonempty selection $I$ has an even sum in every exponent coordinate, setThen $X^2\equiv Y^2(\mathrm{mod}N)$. Finding such a selection is a linear dependence problem over the finite field ${\mathbb{F}}_2$: the indicator vector of the chosen relations belongs to the kernel of a linear map given by the parity matrix. This is why a problem about prime factors recruits linear algebra. The final congruence of squares may still be trivial, so another selection can be needed. ^[ref].

There is a tradeoff: a small factor base gives a smaller parity matrix, but fewer auxiliary integers factor completely over it. A larger factor base accepts more relations but makes the linear algebra larger. Negative auxiliary values need an additional sign coordinate, and a selected product needs even sign parity as well as even prime exponents. Pomerance's account explains this balance and the historical development of combining smooth relations; the toy example omits algorithm-specific sieving and running-time claims. ^[ref].

For four vectors in three-dimensional real Euclidean space, write $[a,b,c]=a\cdot (b\times c)$. Expand the same cross product in two ways using the vector triple product identity:Rearrangement gives the displayed identity. It expresses linear dependence of four vectors in three dimensions with explicit determinant coefficients and remains valid when some or all of those coefficients vanish.

The Gram-Schmidt process turns a finite ordered family of linearly independent vectors $v_1,\dots ,v_k$ in an inner product space over the real numbers into an orthonormal basis $q_1,\dots ,q_k$ of their linear span. It keeps every successive linear span, so the first $j$ new vectors describe exactly the same directions as the first $j$ inputs. Its idea is geometric: remove the orthogonal projection onto directions already found, then divide the remaining vector by its norm. This makes a complicated basis easier to use without changing the vector subspace it describes.^[ref]

Start with $u_1=v_1$ and $q_1=v_1/\Vert v_1\Vert$. At step $j$, use the previously obtained orthonormal set to defineThe sum is the orthogonal projection onto a finite-dimensional subspace $W_{j-1}=\mathrm{span}(q_1,\dots ,q_{j-1})$, and $u_j$ is the orthogonal projection residual. Linear independence ensures $u_j\ne 0$: otherwise $v_j$ would already be a linear combination of earlier inputs. If the input family is linearly dependent, use only the retained orthonormal vectors in the sum and omit an input whenever its remainder is the zero vector; do not divide by zero. The retained outputs still form an orthonormal basis of the original linear span, but their number can be smaller than $k$.

For a short verification, orthonormality makes every earlier inner product vanish:Also $u_j$ is $v_j$ minus a linear combination of earlier vectors, while $v_j$ is $u_j$ plus that same linear combination. These two inclusions, followed by division by a nonzero norm, giveThe argument also works in an inner product space over the complex numbers with the existing inner product convention, linear in the first argument: the coefficients remain $⟨v_j,q_i⟩$. With the convention linear in the second argument, write $⟨q_i,v_j⟩$ instead.

For a first picture, take $v_1=(1,1{)}^T$ and $v_2=(1,0{)}^T$ in ${\mathbb{R}}^2$ with the ordinary dot product. ThenSubtracting the diagonal component leaves an orthogonal direction; dividing by its norm $1/\sqrt{2}$ makes its length one. If the second input were $(2,2{)}^T$ instead, its orthogonal projection would be the entire input and $u_2=0$, revealing linear dependence.

For a full three-dimensional calculation, use the ordinary dot product and the input vectorsThe first two steps giveAt the third step, the inner products are $⟨v_3,q_1⟩=1/\sqrt{2}$ and $⟨v_3,q_2⟩=1/\sqrt{6}$. ConsequentlyThe three numerator vectors have pairwise dot products $0$ and squared Euclidean norms $2,6,3$. Thus the displayed outputs are indeed an orthonormal basis, and the three nonzero remainders also confirm linear independence of the inputs. Keeping the removed coefficients produces the QR decomposition below.

An immediate reward is a reusable orthogonal projection: once an orthonormal basis of a vector subspace $W$ is known, any vector $b$ hasFor the linear span of just the first two inputs in the three-dimensional example, $b=(0,0,1{)}^T$ gives $P_{W}b=(1/3,-1/3,2/3{)}^T$. Its orthogonal projection residual is $(-1/3,1/3,1/3{)}^T=q_3/\sqrt{3}$, visibly in the missing orthogonal direction. This is the geometry behind the linear least-squares problem.

The formulas above describe exact arithmetic. With floating-point arithmetic, subtracting an orthogonal projection nearly equal to the input can leave a small remainder; dividing by its small norm can magnify existing roundoff error. The Classical Gram-Schmidt and Modified Gram-Schmidt arrangements agree in exact arithmetic but can give different rounded results. Exact linear dependence and a small computed remainder therefore require different judgments in a numerical implementation.^[ref]

A Hermitian inner product is a Hermitian form $H$ on a complex vector space which has positive definiteness: $H(v,v)>0$ for every nonzero vector $v$. It is precisely a complex inner product. Only with this definiteness condition doesdefine a norm rather than a seminorm or an expression that may not be real. The standard Hermitian inner product on ${\mathbb{C}}^n$ is $H(z,w)={\sum }_j{z}_j\overline{w_j}$; positive weights $c_j$ give ${\sum }_j{c}_j{z}_j\overline{w_j}$, with squared norm ${\sum }_j{c}_j|z_j{|}^2$.^[ref]

A Hermitian inner product need not have a real matrix. For instance, with the linear-first coordinate convention,The last expression proves positive definiteness without a lengthy calculation of eigenvalues. For $z=(1,i)$ it gives $6$, while for $z=(1,-i)$ it gives $2$. These unequal values expose why a silent switch to $z^{\ast }Az$ would change this particular Hermitian inner product: with these same entries it gives $2$ at $(1,i)$. All entries must keep their roles from the matrix of a Hermitian form.

The Cauchy-Schwarz inequality for a Hermitian inner product statesEquality holds exactly when $u,v$ are linearly dependent, including when either is zero. For a nonzero $u$, outline the proof by setting $a=H(v,u)/H(u,u)$ and $r=v-au$. Then $H(r,u)=0$, and the Pythagorean theorem givesNonnegativity proves the inequality, while positive definiteness makes equality equivalent to $r=0$. The scalar $a$ has no extra conjugate because the first argument is linear.^[ref]

The Cauchy-Schwarz inequality also holds for a positive semidefinite Hermitian form, but equality need not imply linear dependence: for $H_0(z,w)=z_1\overline{w_1}$, the independent vectors $e_1$ and $e_1+e_2$ give $1=1$. Equality then describes dependence after passing to the quotient vector space by the radical of a Hermitian form. The indefinite Hermitian form in Hermitian form shows that conjugate symmetry alone does not even guarantee the inequality.

For a worked orthogonal projection, take $H_{+}(z,w)=z_1\overline{w_1}+2z_2\overline{w_2}$, $u=(1,1)$ and $v=(2,0)$. Then $a=2/3$, $au=(2/3,2/3)$ and $r=(4/3,-2/3)$, with $H_{+}(r,u)=0$ and $4=4/3+8/3$ for the squared norms. The residual is perpendicular in this Hermitian inner product even though its ordinary real dot product with $u$ is $2/3$. For complex $v=(1,i)$, the same orthogonal projection uses $a=(1+2i)/3$; rotating $v$ multiplies $a$ by $e^{i\theta }$, while rotating $u$ multiplies $a$ by $e^{-i\theta }$. This combines geometric decomposition with sensitivity to the relative complex arguments of the multipliers.

A Hermitian inner product therefore supplies more than a positive diagonal: orthogonality, orthogonal projection onto a span, and the triangle inequality for its norm make approximation and distance meaningful. For the function space of complex continuous functions on $[0,1]$, $H(f,g)={\int }_0^{1}f(t)\overline{g(t)}dt$ has positive definiteness, because a nonzero continuous function has positive modulus on a small interval. The same construction turns overlap under integration into lengths and best approximation in finite-dimensional vector subspaces.

A finite family of vectors in a vector space over a specified field $F$ is linearly dependent if it has a nontrivial linear relation: ${\sum }_i{a}_i{v}_i=0$ with $a_i\in F$ and at least one coefficient nonzero. One can then solve for a vector whose coefficient is nonzero as a linear combination of the others; removing that entry preserves the linear span. Repeated vectors in a list give linear dependence: for example $(v,v)$ has the linear relation $1v+(-1)v=0$. A list keeps both entries even though the set $\{v,v\}$ has only one element. Strang's notes illustrate redundant columns by expressing one as the sum of two others.^[ref]

Keep $v_1=(1,1)$ and $v_2=(1,-1)$, and add $v_3=(2,0)=v_1+v_2$. The three vectors still have linear span ${\mathbb{R}}^2$, but nowThe two coefficient triples $(2,1,0)$ and $(1,0,1)$ differ by the nontrivial linear relation $(-1,-1,1)$. In fact all linear combination representations of this target areTo check both completeness and correctness, use $c_1{v}_1+c_2{v}_2+c_3{v}_3=(c_1+c_3)v_1+(c_2+c_3)v_2$. Linear independence of $v_1,v_2$ forces $c_1+c_3=2$ and $c_2+c_3=1$, giving exactly the displayed family. Redundancy therefore preserves attainable targets while allowing their coefficients to move. For solving a linear system, these alternatives matter; for assigning unique coordinate vectors, one instead chooses a basis.

The following example shows why linear independence depends on the scalar field.

A linear matroid has a finite ground set indexing a family of vectors in a vector space over a specified field. A subset of labels is a matroid independent set precisely when its vectors are linearly independent. Labels distinguish repeated vectors; the ground set is not required to consist of distinct numerical vectors. The matroid bases correspond to bases for the linear span of all the supplied vectors.

Exchange outline. The linear span of $|I|$ linearly independent vectors has dimension $|I|$. If $|J|>|I|$, not all the linearly independent vectors indexed by $J$ can lie in that linear span. A vector outside it can be added to $I$. Heredity follows because a linear dependence in a subset would also be a linear dependence in the full selection.

For two triples of distinct points on two projective lines, the intersections $r_{ij}=p_i{q}_j\cap p_j{q}_i$ are collinear when the configuration is defined. Normalize a projective frame so $p_1=[0,1,0]$, $p_2=[1,1,0]$, $q_1=[0,0,1]$, $q_2=[1,0,1]$, and write $p_3=[1,\alpha ,0]$, $q_3=[1,0,\beta ]$. Then representatives of the three intersections are $(1,1,1)$, $(1,\alpha ,\beta )$, and $(\alpha \beta -1,\alpha (\beta -1),\beta (\alpha -1))$. The last is $\alpha \beta$ times the first minus the second, proving collinearity by linear dependence. This gives a coordinate proof over any field when the normalizations are available.

In the usual column convention, a codeword $c$ of a linear code obeys $H{c}^T=0$, so its nonzero coordinates give a linear dependence among columns of its parity-check matrix. Conversely a dependence gives a nonzero codeword supported on those coordinates. Minimizing the support gives the minimum Hamming distance of a linear code. In the transposed convention $cP=0$, the corresponding objects are the rows of $P$. The size of a dependent set means the number of its coordinate positions, even when some check vectors coincide.

If $v=0$, equality is immediate. If $v\ne 0$, the nonnegative squared normproves the Cauchy-Schwarz inequality. Equality holds precisely when the displayed vector vanishes. Thus equality is equivalent to linear dependence of $u,v$, including the cases with a zero vector.

Differentiate the Wronskian:It is therefore constant. Linear dependence plainly makes it zero. Conversely, if it is zero, the two initial-data vectors $(u(0),u^{\prime }(0))$ and $(v(0),v^{\prime }(0))$ are linearly dependent. Some constants $A,B$, not both zero, make $Au+Bv$ and its derivative zero at zero. Uniqueness for a linear second-order equation with continuous coefficients then makes $Au+Bv$ identically zero. Thus $\boxed{w=0⟺u,v\text{ are linearly dependent}}$.

For the prescribed integral put $K(x,s)=[u(x)v(s)-u(s)v(x)]/w$. Then $K(x,x)=0$, $K_x(x,x)=-1$, and $K_{xx}(x,s)=-q(x)K(x,s)$. Differentiation under the integral, using continuity of the coefficients and forcing, givesThis proves the required inhomogeneous equation, with the sign of the forcing as printed.

For the explicit forcing take $u=\cosh x$, $v=\sinh x$, so $w=1$ and $K(x,s)=-\sinh (x-s)$. Since $2/(e^s+e^{-s})=\mathrm{sech}s$, the integral isIndeed expand $\sinh (x-s)=\sinh x\cosh s-\cosh x\sinh s$ and integrate $1$ and $\tanh s$. Adding the entire homogeneous solution givesFinally multiply the other equation by $\sin x$ and integrate from zero to $\pi$. Integration by parts givesThus $\boxed{{\int }_0^{\pi }f(s)\sin sds=0}$ is necessary. It is also sufficient: the solution with $y(0)=0$ is $B\sin x-{\int }_0^x\sin (x-s)f(s)ds$, and the integral condition gives its value zero at $\pi$.

Differentiate the Wronskian:It is therefore constant. Linear dependence plainly makes it zero. Conversely, if it is zero, the two initial-data vectors $(u(0),u^{\prime }(0))$ and $(v(0),v^{\prime }(0))$ are linearly dependent. Some constants $A,B$, not both zero, make $Au+Bv$ and its derivative zero at zero. Uniqueness for a linear second-order equation with continuous coefficients then makes $Au+Bv$ identically zero. Thus $\boxed{w=0⟺u,v\text{ are linearly dependent}}$.

For the prescribed integral put $K(x,s)=[u(x)v(s)-u(s)v(x)]/w$. Then $K(x,x)=0$, $K_x(x,x)=-1$, and $K_{xx}(x,s)=-q(x)K(x,s)$. Differentiation under the integral, using continuity of the coefficients and forcing, givesThis proves the required inhomogeneous equation, with the sign of the forcing as printed.

For the explicit forcing take $u=\cosh x$, $v=\sinh x$, so $w=1$ and $K(x,s)=-\sinh (x-s)$. Since $2/(e^s+e^{-s})=\mathrm{sech}s$, the integral isIndeed expand $\sinh (x-s)=\sinh x\cosh s-\cosh x\sinh s$ and integrate $1$ and $\tanh s$. Adding the entire homogeneous solution givesFinally multiply the other equation by $\sin x$ and integrate from zero to $\pi$. Integration by parts givesThus $\boxed{{\int }_0^{\pi }f(s)\sin sds=0}$ is necessary. It is also sufficient: the solution with $y(0)=0$ is $B\sin x-{\int }_0^x\sin (x-s)f(s)ds$, and the integral condition gives its value zero at $\pi$.

Let $J\ne 0$ be a two-sided ideal of $A{\otimes }_{k}B$. Choose a nonzero $x\in J$ of least possible two-factor tensor rank $n$, and take a shortest expressionBoth families $(a_i)$ and $(b_i)$ are linearly independent: a linear dependence in either family would combine terms and shorten the expression. In particular $a_1,b_1\ne 0$.

Because $A$ is a simple ring, the two-sided ideal generated by $a_1$ is $A$. Thus there are finitely many $u_j,v_j\in A$ with ${\sum }_j{u}_j{a}_1{v}_j=1$. FormSince the $b_i$ are linearly independent, applying a linear functional selecting $b_1$ shows $y\ne 0$. Its two-factor tensor rank is at most $n$ and hence, by the choice of $x$, exactly $n$. Consequently $c_1=1,c_2,\dots ,c_n$ are linearly independent.

Similarly, simplicity of $B$ gives finitely many $p_j,q_j\in B$ with ${\sum }_j{p}_j{b}_1{q}_j=1$. NowThe linear independence of the $c_i$ shows $z\ne 0$, and minimality again makes its two-factor tensor rank exactly $n$. We have obtainedBoth coefficient families in this expression are linearly independent. Retaining this additional property is the key to the next part. This is coefficient normalization in an ideal of a tensor product.

We prove Lie's theorem in the required form by induction on $\dim L$. If $L=0$, any nonzero vector works. Otherwise solvability gives $[L,L]\ne L$, so choose a codimension-one ideal $K\supseteq [L,L]$ and $x\in L\setminus K$. By induction there are $v\ne 0$ and a linear functional $\lambda :K\to \mathbb{C}$ with $av=\lambda (a)v$ for all $a\in K$.

Let $W=\mathrm{span}\{v,xv,x^{2}v,\dots \}$. Choose the cyclic basis $v,xv,\dots ,x^{r-1}v$ up to its first linear dependence. The commutator identity $a{x}^j=xa{x}^{j-1}+[a,x]x^{j-1}$, with $[a,x]\in K$, proves inductively thatHence $W$ is invariant under $K$ and $x$, and every $a\in K$ has trace $r\lambda (a)$ on $W$. In particular ${\mathrm{tr}}_W([x,a])=0$ implies $r\lambda ([x,a])=0$. Characteristic zero gives $\lambda ([x,a])=0$.

The simultaneous weight space $V_{\lambda }=\{w:aw=\lambda (a)w\forall a\in K\}$ is nonzero and stable under $x$, becauseOver $\mathbb{C}$, the restriction of $x$ to this nonzero finite-dimensional space has an eigenvector. That vector is an eigenvector of both $x$ and every $a\in K$, hence of every element of $L$.

No. Calling the three vectors $v_1,v_2,v_3$ in order, direct addition gives $v_3=v_1+v_2$. This nontrivial linear dependence prevents them from forming a basis of ${\mathbb{R}}^3$. The first two are not proportional, so the span has dimension two.

For two nonparallel vectors $v_1,v_2\in {\mathbb{R}}^2$, a nontrivial relation $a{v}_1+b{v}_2=0$ would make one a scalar multiple of the other. They are therefore linearly independent. Two independent vectors in a two-dimensional vector space form a basis.

Likewise, three vectors in ${\mathbb{R}}^3$ that are not contained in one plane through the origin cannot obey a nontrivial linear dependence: such a relation would express one as a combination of the other two, or already make that pair dependent. Thus they are independent and form a basis of ${\mathbb{R}}^3$. The plane condition here is linear coplanarity with the origin, as required for vectors, rather than affine coplanarity of three arbitrary points.

The vectors are linearly independent over $F$ if ${\sum }_{j=1}^n{c}_j{\mathbf{v}}_j=0$ with $c_j\in F$ implies $c_j=0$ for every $j$. Otherwise there is a nontrivial linear dependence. Forming a matrix with the displayed vectors as columns givesThusis the unique dependent case. At that value the explicit relation $2{\mathbf{v}}_1-\frac{3}{2}{\mathbf{v}}_2-{\mathbf{v}}_3=0$ verifies the dependence.

A family $x_1,\dots ,x_n$ is linearly independent if ${\sum }_{i=1}^n{a}_i{x}_i=0$ forces $a_1=\cdots =a_n=0$. For the three specified vectors, direct substitution givesThe coefficients are not all zero, so the vectors are linearly dependent.

For the implication question, using the usual interpretation that a basis contains the listed family as independent entries, the answers in order (i)–(x) areThe key distinctions are that the unrestricted zero combination always exists, whereas linear dependence requires a nontrivial combination; and dependence does not necessarily let the specified third vector be solved in terms of the first two. For example $x=y=e_1$, $z=e_2$ makes (iii) and (iv) false, while $x=e_1,y=e_2,z=e_3$ disproves (vi).

There is a set-versus-family qualification in (v). If “contains” is interpreted as literal set containment, repeated nonzero vectors need only occur once in the basis. Then $x=y=e_1,z=e_2$ is dependent as a family but all three belong to the basis $\{e_1,e_2\}$, so (v) becomes false. With three distinct vectors, or with family-containment as above, basis extension gives (v) true. Implication (x) remains true on either reading.

In Siegel's original convention, an E-function is an entire series $F(z)={\sum }_{n\ge 0}{a}_n{z}^n/n!$ with coefficients in a fixed number field, satisfying a nonzero linear differential equation over $\overline{\mathbb{Q}}(z)$, together with these arithmetic bounds: for every $ϵ>0$, all conjugates of $a_0,\dots ,a_n$ have size $O_{ϵ}(n^{ϵn})$, and some positive integer $d_n=O_{ϵ}(n^{ϵn})$ makes every $d_n{a}_j$, $j\le n$, an algebraic integer. A frequently used stricter convention replaces both bounds by $C^{n+1}$. The original and strict growth definitions should not simply be declared equivalent; the exponential examples below satisfy the strict one.

For sums, work in the compositum of the coefficient fields. Coefficient conjugate bounds add. The product of the two common denominators clears both lists; using $ϵ/2$ in each original denominator bound gives the required $O_{ϵ}(n^{ϵn})$ product bound. Finally all derivatives of $F+G$ lie in the sum of the two finite-dimensional derivative spaces over that rational function field, so they satisfy a nontrivial linear dependence, giving a differential equation for the sum. Thus sums are again E-functions, the addition closure of Siegel E-functions.

The Siegel–Shidlovsky theorem states that if a vector of E-functions satisfies $F^{\prime }=A(z)F$ with rational-function matrix over $\overline{\mathbb{Q}}$, then at every nonzero algebraic $\xi$ which is not a pole of $A$,In particular algebraically independent functions give algebraically independent values.

Take $F_j(z)=e^{{\gamma }_{j}z}$ for algebraic numbers ${\gamma }_j$ linearly independent over $\mathbb{Q}$. Their coefficients are ${\gamma }_j^n$ with exponential conjugate and denominator bounds, and $F_j^{\prime }={\gamma }_j{F}_j$. A polynomial relation among the functions expands into a relation among exponentials with distinct exponents $\sum m_j{\gamma }_j$ and polynomial coefficients after clearing rational-function denominators; exponential-polynomial independence excludes it. At $\xi =1$ the theorem gives algebraic independence of the $e^{{\gamma }_j}$. For arbitrary distinct algebraic ${\alpha }_i$, choose a rational basis of their span and divide that basis by a common denominator. The $e^{{\alpha }_i}$ are distinct Laurent monomials in the corresponding algebraically independent exponential values, so are linearly independent over $\overline{\mathbb{Q}}$. This recovers the general Lindemann–Weierstrass theorem. Its simplest instance uses just $F(z)=e^z$ at nonzero algebraic $\xi$.