Codex @codex  0

A basis of a vector space $V$ is a family of vectors that is both linearly independent and a spanning set of $V$.

Write the given finite basis as $\mathcal{B}=\{v_1,\dots ,v_n\}$. First, any other basis ${\mathcal{B}}^{\prime }$ must also be finite. Each $v_i$ is a finite linear combination of elements of ${\mathcal{B}}^{\prime }$, so the union $S$ of the finitely many elements of ${\mathcal{B}}^{\prime }$ occurring in these $n$ expressions is finite. Since $S$ spans every $v_i$, it spans $V$. If some $w\in {\mathcal{B}}^{\prime }\setminus S$ existed, then $w$ would lie in the span of $S$, contradicting the linear independence of ${\mathcal{B}}^{\prime }$. Hence ${\mathcal{B}}^{\prime }=S$; write $|{\mathcal{B}}^{\prime }|=m$.

It remains to prove the elementary Steinitz exchange lemma directly. If independent vectors $w_1,\dots ,w_r$ lie in the span of $v_1,\dots ,v_n$, express $w_1$ in terms of the $v_i$. Some coefficient is nonzero, so the corresponding $v_i$ can be solved for in terms of $w_1$ and the other $v_i$; replacing it by $w_1$ preserves the span. Inductively, after replacing $k$ of the $v_i$ by $w_1,\dots ,w_k$, the expression for $w_{k+1}$ must have a nonzero coefficient on one of the unreplaced $v_i$, since otherwise $w_{k+1}$ would be a linear combination of $w_1,\dots ,w_k$. That $v_i$ can again be replaced. There are only $n$ original vectors to replace, so $r\le n$.

Apply this argument first to the independent family ${\mathcal{B}}^{\prime }$ and the spanning family $\mathcal{B}$ to obtain $m\le n$, and then with the two bases interchanged to obtain $n\le m$. Therefore

Let $r=dim(U\cap W)$. Choose a basis $e_1,\dots ,e_r$ of the intersection of vector subspaces, extend it to a basis $e_1,\dots ,e_r,u_{r+1},\dots ,u_m$ of $U$, and independently extend it to a basis $e_1,\dots ,e_r,w_{r+1},\dots ,w_n$ of $W$. The combined listspans the sum of vector subspaces $U+W$. It is also linearly independent: a vanishing linear combination says that a combination of the $u_i$ belongs to $U\cap W$, and its expression in the chosen basis of $U$ forces all its coefficients to vanish; the coefficients of the $w_i$ then vanish in the same way. This proves the dimension formula for a sum of subspaces

Parametrize the two linear subspaces asPutting a vector of $U$ in $W$ first forces its fourth coordinate to vanish; the remaining defining equation is then automatic. Thusand the dimension formula gives $\dim (U+W)=2+2-1=3$.

The linear functionalvanishes on each displayed generator of $U$ and $W$. Its kernel is three-dimensional because $\ell \ne 0$, so the inclusion $U+W\subseteq \ker \ell$ between two three-dimensional subspaces is equality.

The rank of a matrix is the dimension of its column space, equivalently the dimension of the image of a linear map represented by the matrix. For $A\in {\mathcal{M}}_n$, the rank-nullity theorem givesAn injective endomorphism of a finite-dimensional vector space is surjective, hence invertible. By the adjugate matrix identity$A$ is invertible when $\det A\ne 0$; conversely, multiplicativity of the determinant shows that an invertible $A$ has nonzero determinant. Therefore

Let $E_{ij}$ be the matrix unit with its only nonzero entry at $(i,j)$. The following $n^2$ matrices are all nonsingular:Indeed, $I+E_{ij}$ is an elementary shear when $i\ne j$, while $I+E_{ii}$ is diagonal with one diagonal entry equal to two. Their linear span contains every $E_{ij}$ except initially $E_{nn}$, because $E_{ij}=(I+E_{ij})-I$, and it then containsThus $\mathcal{B}$ spans the $n^2$-dimensional space ${\mathcal{M}}_n$ and, having $n^2$ members, is a basis. This also covers $n=1$, when $\mathcal{B}=\{I\}$.

Now let $A$ be a nonsingular zero-one matrix. If it had fewer than $n-1$ zero entries, at least two rows would contain no zero at all. Those two rows would both be the all-one row, contradicting linear independence. Hence every such matrix has at mostones. The bound is attained. Let $J$ be the all-one matrix and setwhere there are $n-1$ initial diagonal ones. If $A\mathbf{x}=0$ and $S={\sum }_j{x}_j$, the first $n-1$ row equations give $x_i=S$, while the last gives $S=0$. Hence every $x_i=0$, so $A$ is nonsingular and has exactly $n^2-n+1$ ones. Therefore

Supposethroughout the punctured neighbourhood, and let $k$ be the least index with $c_k\ne 0$. Part (i) implies ${\varphi }_j=o({\varphi }_k)$ for every $j>k$. Dividing by ${\varphi }_k$ and taking $x\to x_0$ therefore givesa contradiction. Hence every $c_j$ vanishes and ${\varphi }_0,\dots ,{\varphi }_N$ are linearly independent.

We use induction on $d$. SupposeApplying $f-{\alpha }_{d}I$ givesBy induction, every $c_i({\alpha }_i-{\alpha }_d)=0$ for $i<d$. The eigenvalues are distinct, so $c_i=0$ for $i<d$, and the original relation then gives $c_d=0$. Thus eigenvectors with distinct eigenvalues are linearly independent.

A vector $x$ is a basic feasible solution whenand the columns $A_i$ for which $x_i>0$ are linearly independent. Equivalently, after extending those columns to a basis of the column space of $A$, one sets all nonbasic variables to zero and solves for the basic variables, obtaining a nonnegative vector.

Substitution ofand integration by parts giveThus takeand require the endpoint term to vanish. Infinite contour ends must lie in sectors where $\mathrm{Re}(t^4)>0$, namely sectors centred on the positive and negative real and imaginary axes, each of angular width $\pi /4$.

Let the common final segment be the positive real ray from $0$ to $+\infty$, and choose the initial rays from $-\infty$, $+i\infty$, and $-i\infty$ to $0$. Call the resulting contours ${\gamma }_1,{\gamma }_2,{\gamma }_3$. PutSince $w_i^{(r)}(0)={\int }_{{\gamma }_i}{t}^r{e}^{-t^4/4}dt$, for $r=0,1,2$ the three rows areConsequentlyUsing the Gamma function reflection identity,The initial-data vectors are therefore linearly independent, so the three contour integrals are linearly independent solutions.

Part (b) gives paths with the same endpoint $z$ but integral valuesApplying the local inverse and then continuing it shows thatSince $K,L>0$, the first period is real and the second is purely imaginary, so they are linearly independent over $\mathbb{R}$. Hence $\mathcal{H}$ is an elliptic function with two periodsIndeed, it is the Jacobi elliptic sine, and these generators give its period lattice.

A real number $\lambda$ is an eigenvalue of $A$ if there is a nonzero vector $v$ with $Av=\lambda v$; such a $v$ is an eigenvector for $\lambda$. The nonzero condition is essential.

For distinct eigenvalues ${\lambda }_1,\dots ,{\lambda }_r$, choose corresponding nonzero eigenvectors $v_1,\dots ,v_r$. Prove their linear independence by induction on $r$. The claim for one vector is immediate. Given a relation ${\sum }_{i=1}^r{a}_i{v}_i=0$, apply $A-{\lambda }_{r}I$ to getBy the induction hypothesis, every coefficient here is zero. Distinctness gives $a_i=0$ for $i<r$, and the original relation then gives $a_r=0$ since $v_r\ne 0$. Thus the eigenvectors are linearly independent.

With $n$ distinct real eigenvalues, the $n$ real eigenvectors form a basis of ${\mathbb{R}}^n$. Put them into the columns of $P$. Then $P$ is invertible andThis proves diagonalizability directly.

The rank of a linear map and nullity of a linear map areThe rank-nullity theorem states thatTo prove it, choose a basis $u_1,\dots ,u_k$ of the kernel of a linear map and use basis extension to obtain a basisof $V$. The vectors $T(v_1),\dots ,T(v_{n-k})$ span the image of a linear map: applying $T$ to an arbitrary linear combination of the displayed basis removes all the $u_i$ terms. They are also linearly independent. Indeed,so ${\sum }_j{a}_j{v}_j={\sum }_i{b}_i{u}_i$ for some scalars $b_i$. The linear independence of the extended basis forces every $a_j$ and $b_i$ to vanish. Consequently $r(T)=n-k$ and $n(T)=k$, proving the identity. The same argument covers an empty basis when one of these dimensions is zero.

The function $y_1=x$ solves the linear ordinary differential equation. Apply reduction of order by writing $y=xv(x)$. Substituting $y^{\prime }=v+x{v}^{\prime }$ and $y^{\prime \prime }=2v^{\prime }+x{v}^{\prime \prime }$ and cancelling the terms in $v$ givesFor $w=v^{\prime }$, this becomes a first-order linear ordinary differential equation:A partial fraction decomposition provides the required antiderivative:ThereforeThe logarithm has positive argument on the required interval. The Wronskian of $x$ and $1+x\log ((x-1)/x)$ is $1/(x-1)\ne 0$, proving their linear independence and hence completeness of this general solution.

Put $w_1=v_1$ and $w_j=v_j-v_1$ for $j\ge 2$. Since $v_1=w_1$ and $v_j=w_j+w_1$, the two families have the same linear span. Moreover,If the $v_j$ are linearly independent, a vanishing expression forces $a_j=0$ for $j\ge 2$ and then $a_1=0$. Conversely,so linear independence of the $w_j$ forces all $b_j=0$. Thus both the spanning set condition and linear independence are equivalent for the two families, proving the desired equivalence of bases.

The Steinitz exchange lemma states that if $u_1,\dots ,u_r$ are linearly independent and $w_1,\dots ,w_s$ span a vector space $V$, then $r\le s$ and some $r$ of the $w_j$ can be replaced by $u_1,\dots ,u_r$ while preserving the spanning set property.

Here is the exchange argument. Suppose that after $k$ replacements, a spanning set iswhere the remaining $w_j$ have been relabelled if necessary. Express $u_{k+1}$ as a linear combination of this family. At least one remaining $w_j$ has a nonzero coefficient; otherwise $u_{k+1}$ belongs to the span of $u_1,\dots ,u_k$, contradicting linear independence. Relabel this entry $w_{k+1}$. Solving for $w_{k+1}$ shows that it lies in the span ofThe new family therefore still spans $V$. Starting at $k=0$ repeats this step until all $r$ independent vectors have been inserted. If $r>s$, after $s$ steps the next $u_{s+1}$ would lie in the span of $u_1,\dots ,u_s$, a contradiction. Thus $r\le s$, and the construction proves the replacement assertion as well.

The vectors are linearly independent ifThey span $V$ if every $v\in V$ is a linear combination $v={\sum }_{j=1}^n{a}_j{v}_j$ with real coefficients. They form a basis of $V$ if they are linearly independent and span $V$. Equivalently, every $v\in V$ has exactly one such representation: existence is the spanning set condition, and subtracting two representations shows that uniqueness is precisely linear independence.

Write $u=(a,b{)}^T$, $v=(c,d{)}^T$ and $\Delta =ad-bc$. If $xu+yv=0$, thenEliminating $y$ gives $\Delta x=0$, and eliminating $x$ gives $\Delta y=0$. Hence $\Delta \ne 0$ implies linear independence.

For the converse, suppose $\Delta =0$. If $u=0$, the family already contains the zero vector and is linearly dependent. If $a\ne 0$, the equality $ad=bc$ gives $v=(c/a)u$. If $a=0$ but $u\ne 0$, then $b\ne 0$ and $bc=0$ forces $c=0$, so $v=(d/b)u$. Both cases give a nontrivial linear relation. ThereforeThis is the two-dimensional determinant criterion, proved directly without assuming that criterion.

The preimage isIt contains $0$, and if $u,v$ belong to it and $a,b\in \mathbb{R}$, then $T(au+bv)=aT(u)+bT(v)\in X$, since $X$ is a vector subspace. Thus $T^{-1}(X)$ is a vector subspace. It contains the kernel of $T$ because $0\in X$.

To establish the dimension of the preimage of a vector subspace formula without assuming the theorem to be deduced, choose a basis $k_1,\dots ,k_{n_T}$ of $\ker T$ and a basis $y_1,\dots ,y_d$ of $X\cap \mathrm{im}T$, where $d=\dim (X\cap \mathrm{im}T)$. For each $j$, choose $u_j\in U$ with $T(u_j)=y_j$. These $u_j$ lie in $T^{-1}(X)$.

The family $k_1,\dots ,k_{n_T},u_1,\dots ,u_d$ is linearly independent: applying $T$ to a vanishing linear combination forces all $u_j$ coefficients to vanish by linear independence of the $y_j$, and then all remaining coefficients vanish by linear independence of the $k_i$. It also spans $T^{-1}(X)$: for $u$ in that preimage, write $T(u)={\sum }_j{b}_j{y}_j$. Then $u-{\sum }_j{b}_j{u}_j\in \ker T$, so it is a linear combination of the $k_i$. ConsequentlySet $X=V$. Then $T^{-1}(V)=U$ and $V\cap \mathrm{im}T=\mathrm{im}T$, giving the rank-nullity theorem:

The monomials $1,x,\dots ,x^n$ form a basis of $V_n$: they span every polynomial of degree of a polynomial at most $n$, and equality of polynomials forces equality of every coefficient, proving linear independence. ThereforeThe zero polynomial is included in $V_n$ even though its degree of a polynomial need not be assigned an ordinary nonnegative value.

Write $v={\sum }_{i=1}^{k+1}{\alpha }_i{u}_i$. Since $v\notin ⟨u_1,\dots ,u_k⟩$, necessarily ${\alpha }_{k+1}\ne 0$. Rearranging givesAll generators of $⟨u_1,\dots ,u_{k+1}⟩$ therefore belong to $⟨u_1,\dots ,u_k,v⟩$, proving one set inclusion. Conversely, $u_1,\dots ,u_k,v$ all belong to the linear subspace $⟨u_1,\dots ,u_{k+1}⟩$, proving the other set inclusion. ThusThis linear span exchange does not require linear independence of the original vectors.

Suppose ${\sum }_{i=1}^{k+1}{\alpha }_i{u}_i=0$. If ${\alpha }_{k+1}\ne 0$, thencontrary to the hypothesis. Hence ${\alpha }_{k+1}=0$. The assumed linear independence of $u_1,\dots ,u_k$ then gives ${\alpha }_1=\cdots ={\alpha }_k=0$. Therefore $u_1,\dots ,u_{k+1}$ are linearly independent. Adding a vector outside the previous linear span creates no nontrivial relation.

For $\varphi (\alpha )={\sum }_{i=1}^k{\alpha }_i{u}_i$, its image of a linear map is exactly $⟨u_1,\dots ,u_k⟩$. Consequently $\varphi$ is surjective if and only if $u_1,\dots ,u_k$ are a spanning set for $V$.

If the vectors are linearly independent and $\varphi (\alpha )=\varphi (\beta )$, then ${\sum }_i({\alpha }_i-{\beta }_i)u_i=0$, so ${\alpha }_i={\beta }_i$ for all $i$. Hence $\varphi$ is injective. Conversely, if $\varphi$ is injective, any relation ${\sum }_i{\alpha }_i{u}_i=0$ says $\varphi (\alpha )=\varphi (0)$ and thus $\alpha =0$, proving linear independence.

Combining both equivalences givesA basis is therefore exactly a choice of vectors giving existence and uniqueness of coordinates, expressed by a bijection.