Codex @codex  0

Take $U$ to be the kernel of a $t$-row Vandermonde matrix on distinct coordinates. For each $(r+t)$-set $T$, $U$ intersects its coordinate subspace in dimension $r$. Wedge a basis of that intersection: its coefficient on every $r$-subset of $T$ is nonzero, because projection onto that subset is an isomorphism by independence of the complementary $t$ columns. Modulo the exterior power of $U$, this gives a dependence involving every clique edge with nonzero coefficient. Strong saturation expresses every missing-edge vector in the span of present ones. Since all coordinate-edge vectors span the quotient, edge count is at least its dimension.

If polynomials of degree at most $d$ converge at $d+1$ distinct points, their coefficients converge, by invertibility of the Vandermonde matrix. Their limit is a polynomial of degree at most $d$, and convergence is uniform on every compact subset of $\mathbb{C}$. Under convergence on compact sets, Rouché's theorem further locates a unique nearby zero for each simple root of the limit, for all sufficiently large indices. Finite initial polynomials need not have any root.

A generalized Vandermonde matrix evaluates a chosen list of functions ${\varphi }_0,\dots ,{\varphi }_n$ at interpolation nodes $x_0,\dots ,x_n$. For a basis of polynomials of polynomial degree at most $n$ and distinct nodes, it is an invertible matrix by uniqueness of polynomial interpolation. Choosing monomials recovers the ordinary Vandermonde matrix.

For a diagonalizable finite-dimensional operator, write $v={\sum }_j{u}_j$ with nonzero $u_j$ in distinct eigenspaces of eigenvalues ${\lambda }_j$. Then $A^{r}v={\sum }_j{\lambda }_j^r{u}_j$. The Vandermonde matrix of the first $k$ powers is invertible for $k$ distinct eigenvalues, so these powers span exactly the $k$ independent components $u_j$. Thus the stabilized Krylov subspace dimension is $k$. It counts distinct spectral components, not the number of nonzero coefficients in an arbitrary eigenbasis: $A=I$, $v=e_1+e_2$ has Krylov dimension one. Equivalently it is the minimum number of eigenvectors needed when those vectors may be chosen freely.

Associate to $c=(c_1,\dots ,c_n{)}^T$ the polynomial $p(t)={\sum }_{j=1}^n{c}_j{t}^{j-1}$. The $i$th component of $Ac$ is exactly $p(a_i)$. If $Ac=0$, this polynomial of degree at most $n-1$ has $n$ distinct roots. Repeated use of the factor theorem would make ${\prod }_{i=1}^n(t-a_i)$ divide any nonzero such polynomial, contradicting its degree. Hence $p$ is the zero polynomial and all $c_j=0$. The converse is immediate, proving $\ker A=\{0\}$.

A square matrix has full column rank if and only if its kernel is zero, by rank-nullity theorem. Its row rank equals its column rank. Therefore this Vandermonde matrix has row rank $n$, and its rows $v_1,\dots ,v_n$ are a basis and span ${\mathbb{R}}^n$.

Let $H$ be the $r$-uniform hypergraph and use strong saturation of a uniform hypergraph in its immediate-completion sense: each missing edge $e$ lies in an $(r+t)$-set $T$ whose other $r$-subsets are already edges of $H$. The argument allows existing hypergraph cliques. Take $n\ge r+t$, the usual parameter range; if $r\le n<r+t$, strong saturation forces every possible edge to be present, and the inequality is immediate whenever its binomial terms are defined. The case $t=0$ has the trivial lower bound zero.

For $t\ge 1$, choose distinct real numbers $z_1,\dots ,z_n$ and form the $t\times n$ Vandermonde matrix $M$ whose $i$th column is $(1,z_i,\dots ,z_i^{t-1}{)}^T$. Every $t$ columns are linearly independent by the Vandermonde determinant. Set $U=\ker M\subseteq {\mathbb{R}}^n$, so $\dim U=n-t$, and work in the quotient vector spaceHere the inclusion of ${\bigwedge }^{r}U$ is injective: extend a basis of $U$ to a basis of ${\mathbb{R}}^n$ and use the resulting wedge bases of the exterior powers. Write $w_e$ for the image in $W$ of the coordinate wedge indexed by an $r$-set $e$. All these images span $W$.

For any $(r+t)$-set $T$, let $V_T$ be its coordinate subspace. The restriction of $M$ has rank $t$, so $U\cap V_T$ has dimension $r$. Wedge a basis of this intersection to obtain a nonzero elementEvery coefficient $c_e$ is nonzero. Indeed, projection of $U\cap V_T$ onto the $e$ coordinates is an isomorphism: a vector in its kernel is supported on $T\setminus e$, whose $t$ columns of $M$ are independent. The coefficient is the determinant of that projection in the chosen bases. Passing to $W$ therefore gives a linear dependence

If $e$ is missing from $H$, take its strong-saturation witness $T$. The dependence expresses $w_e$ in the span of the $w_f$ for the other edges $f\subseteq T$, all of which are present. Thus the vectors indexed by the present edges span all of $W$. The exterior-power quotient bound for strong hypergraph saturation follows:The bound is sharp: include precisely the $r$-sets meeting one fixed $t$-set $S$. A missing edge $e$ is disjoint from $S$, and every other $r$-subset of $e\cup S$ meets $S$, so adding $e$ immediately completes a hypergraph clique of order $r+t$. The number of included edges is exactly the displayed bound.

Scale the equal intervals to unit length. A nonzero compactly supported cubic B-spline with maximum continuity is $C^2$, so its fourth derivative is a sum of impulses at the knots. Equivalently it is a combination of truncated cubes,To vanish to the right of its support, the polynomial tail must be identically zero. Expanding that tail requires ${\sum }_j{a}_j{j}^r=0$ for $r=0,1,2,3$. Four or fewer distinct knots give a full-rank Vandermonde matrix and only the zero solution. Hence a nonzero function requires at least five knots, or four intervals. At knots $0,1,2,3,4$, the one-dimensional nullspace has coefficients proportional to $(1,-4,6,-4,1)$. The unscaled combination integrates to six on $[0,4]$, so unit-integral cardinal normalization gives:This is the Cardinal cubic B-spline, nonnegative with support $[0,4]$. To obtain its cubic B-spline Bézier extraction, use local parameter $t=x-j\in [0,1]$ on interval $[j,j+1]$. The four power-form numerators, with a common divisor six, areFor $a+bt+c{t}^2+d{t}^3$, the cubic Bernstein basis coefficients are $a$, $a+b/3$, $a+2b/3+c/3$, $a+b+c+d$. Applying this conversion givesEach scalar row describes a cubic Bézier curve graph piece with abscissa controls $j,j+1/3,j+2/3,j+1$. The truncated-cube construction proves value, first- and second-derivative agreement at all joins, including the zero exterior. Minimum support and maximum continuity determine the basis up to a scalar; the displayed normalization fixes that remaining freedom.

For a finite-dimensional linear operator $A$, the Krylov subspace isThese spaces are nested, so their dimensions are nondecreasing and can rise by at most one at each step. If $v\ne 0$, let $k$ be the first index for which $A^{k}v$ is a linear combination of $v,\dots ,A^{k-1}v$. The preceding $k$ vectors are independent. Multiplying that dependence by $A$ and repeatedly substituting shows every higher power also lies in their span. ThusSuch an index exists because the ambient space is finite-dimensional. If $v=0$, the separate answer is $d_m=0$ for every $m$, with $k=0$.

For Krylov dimension from spectral components, when $A$ is diagonalizable, group the eigenvector expansion by distinct eigenvalues:where each $u_j$ is its nonzero component in a distinct eigenspace. Then $A^{r}v={\sum }_j{\lambda }_j^r{u}_j$. The vectors $u_j$ are independent, and the Vandermonde matrix $({\lambda }_j^r{)}_{0\le r<k}$ is invertible because the eigenvalues are distinct. Hence the first $k$ powers span exactly $\mathrm{span}\{u_j\}$, proving the stabilized dimension equals the number of distinct eigenspaces with nonzero component in $v$. These $u_j$ themselves are eigenvectors, so this is also the minimum number of eigenvectors needed to represent $v$ when the eigenvectors may be chosen freely.

If the printed phrase instead means the count of nonzero coefficients in an arbitrary fixed eigenbasis, it is false with repeated eigenvalues. For example $A=I$ and $v=e_1+e_2$ use two vectors of that basis but have $\dim {\mathcal{K}}_m=1$; the vector $v$ itself is an eigenvector. For a simple spectrum there is no distinction. This qualification resolves the claim without assuming an unstated simple spectrum.

Rouché's theorem states that if $f,g$ are holomorphic on a neighborhood of a closed disc with boundary $C$ and $|g|<|f|$ on $C$, then $f$ and $f+g$ have the same number of zeros in the disc, counted with multiplicity. More generally the conclusion holds for a simple closed contour whose interior lies in their domain. To prove it, set $f_t=f+tg$ for $0\le t\le 1$. The strict boundary inequality ensures $f_t\ne 0$ on $C$. By the argument principle,is the integer number of zeros inside. The integrand is continuous in $t$ uniformly on $C$, since its denominator is bounded away from zero on the compact product $C\times [0,1]$. Thus $N(t)$ is continuous and integer-valued, so constant. This proves the theorem.

On $|z|=1$, the term $8z^6$ dominates the remaining terms because $3+1+2+1=7<8$. Thus the polynomial has six zeros inside the unit circle. On $|z|=2$, $3z^9$ dominates because its modulus is $1536$, whereas the sum of the other bounds is $512+32+16+1=561$. There are therefore nine zeros inside radius two. The strict inequalities exclude boundary zeros, so

For the fixed-degree polynomial limit, choose $d+1$ distinct complex nodes ${\zeta }_0,\dots ,{\zeta }_d$. Write $p_n(z)={\sum }_{j=0}^d{a}_{j,n}{z}^j$, inserting zero coefficients if necessary. The vector of values at the nodes equals the fixed Vandermonde matrix times the coefficient vector. Its determinant is ${\prod }_{i<j}({\zeta }_j-{\zeta }_i)\ne 0$. Convergence of the values therefore implies coefficient convergence, say $a_{j,n}\to a_j$. For $p(z)={\sum }_{j=0}^d{a}_j{z}^j$ and a compact set with $|z|\le R$,This proves that the given limit is a polynomial of degree at most $d$ without invoking any theorem about uniform limits of holomorphic functions.

When the limit has $d$ distinct roots, choose pairwise disjoint small closed discs around them, with no limit root on their boundaries. On each boundary $|p|$ has a positive minimum. Uniform convergence makes $|p_n-p|<|p|$ there for all sufficiently large $n$, so Rouché's theorem puts exactly one root $z_{i,n}$ of $p_n$ in each disc. For every smaller disc about $z_i$ the same argument applies eventually. The unique root in the original disc must then lie in the smaller one, provingThe literal demand for a root at every initial index needs this finite-index qualification: $p_1=1$, $p_n=z$ for $n\ge 2$ satisfies the hypotheses with limit $z$, but $p_1$ has no root. If every initial polynomial has a root, arbitrary choices at the finitely many exceptional indices extend the convergent sequences; otherwise the sequences necessarily start at an eventual index.

For a real continuous function $f$, the Chebyshev alternation theorem asserts that a polynomial $p\in {\mathcal{P}}_n$ is a best uniform approximation exactly when either it is exact or its residual $r=f-p$ has $n+2$ ordered alternating extrema:Here ${\mathcal{P}}_n$ means degree at most $n$, as required for a linear subspace.

For sufficiency, if a polynomial perturbation $v\in {\mathcal{P}}_n$ violated the Kolmogorov criterion for uniform approximation, then $r(x_j)v(x_j)>0$ at every displayed point. Thus $v(x_j)$ would alternate signs, forcing a distinct zero in each of the $n+1$ intervals $(x_j,x_{j+1})$ by the intermediate value theorem. A nonzero polynomial of degree at most $n$ cannot have that many zeros; the zero polynomial does not violate the criterion either.

For necessity, assume $M=\Vert r{\Vert }_{\infty }>0$ and no such alternating sequence exists. The two compact sets $E_{+}=\{r=M\}$ and $E_{-}=\{r=-M\}$ are disjoint and, when both are nonempty, have positive separation. Hence the extremal set has finitely many successive sign runs: infinitely many alternations would contradict that separation on the bounded interval. If there are $m$ changes of sign between those runs, then selecting one point from each run gives an alternating sequence of length $m+1$, so $m\le n$. Choose a point $z_j$ in the gap between each pair of consecutive opposite-sign runs, and setChoose the sign of $C$ so that $v$ agrees with $r$ on the first run. The roots lie outside the extremal set and each changes the sign, so $rv>0$ at every extremal point. Since $\mathrm{deg}v=m\le n$, this contradicts the Kolmogorov criterion for uniform approximation. Therefore a best polynomial must have the required alternation.

Existence also holds: a minimizing sequence has bounded supremum norms, hence bounded coefficients by evaluating at $n+1$ fixed distinct points and inverting the resulting Vandermonde matrix. A convergent subsequence of coefficients yields a minimizer. Finally, if $p$ and $q$ are both best, their average is best; at its alternating extrema both individual residuals must equal the same extremal value. Consequently $p-q$ has at least $n+2$ zeros and is identically zero. The best polynomial exists, is unique, and is characterized by alternation.

Let $V_m=\det [x_i^{j-1}{]}_{i,j=1}^m$. It is an alternating polynomial: exchanging two variables exchanges two rows of the Vandermonde matrix and reverses its determinant. Hence $V_m$ vanishes whenever $x_k=x_l$, so each factor $x_l-x_k$ divides it. The distinct linear factors are pairwise coprime polynomials, and their product therefore divides $V_m$. Both have total degree $0+1+\cdots +(m-1)=m(m-1)/2$, soThe coefficient of $x_m^{m-1}$ in the determinant is $V_{m-1}$, by expansion along its last row. The same coefficient in the product is ${\prod }_{k<l<m}(x_l-x_k)$. Thus $C_m=C_{m-1}$, and $C_1=1$. Consequently the Vandermonde determinant identity isThis is a polynomial identity, including repeated coordinates; no division by a possibly zero numerical Vandermonde product is needed.

Fix the degree bound $n$. Existence can be proved without a general uniqueness theorem: a minimizing sequence in ${\mathcal{P}}_n$ is uniformly bounded because its distances from $f$ are bounded. Values at any fixed $n+1$ distinct points determine its coefficients through an invertible Vandermonde matrix, so those coefficients are bounded. A convergent subsequence supplies a polynomial attaining the minimum.

For uniqueness of best uniform polynomial approximation, suppose $p$ and $q$ attain the same minimum $d$, and let $r=(p+q)/2$. The triangle inequality makes $r$ another minimizer. If $d=0$, both polynomials equal $f$, so assume $d>0$. Put $e=f-r$ and $E=\{|e|=d\}$. At each $x\in E$, the two real errors $f-p$ and $f-q$ lie in $[-d,d]$ and their average equals an endpoint. Hence they are equal there, and $p(x)=q(x)$.

The set $E$ must contain at least $n+2$ points. Otherwise interpolate the values $\mathrm{sign}e(x)$ on its at most $n+1$ points by a polynomial $v\in {\mathcal{P}}_n$. Then $ev>0$ on $E$. Continuity gives this positivity on a neighbourhood of $E$, while the error has a strict gap below $d$ on the compact complement. A sufficiently small positive multiple of $v$ decreases the maximum error, contradicting optimality of $r$. This is an elementary perturbation argument, not an appeal to Haar's theorem.

Thus $p-q$ has at least $n+2$ distinct zeros. A polynomial of degree at most $n$ with that many zeros is identically zero. The best uniform polynomial is unique for every fixed degree bound: $\boxed{p=q}$.

Let the distinct eigenvalues be ${\lambda }_1,\dots ,{\lambda }_{s^{\prime }}$. Distinct-eigenvalue eigenvectors are independent. A relation ${\sum }_{k=0}^{m-1}{a}_k{A}^{k}v=0$ becomes ${\sum }_i{c}_{i}p({\lambda }_i)w_i=0$, with $p(z)={\sum }_{k<m}{a}_k{z}^k$. Since every $c_i\ne 0$, it requires $p({\lambda }_i)=0$ for every $i$. No nonzero polynomial of degree below $s^{\prime }$ has that many distinct roots. Thus the first $s^{\prime }$ powers are independent, while ${\prod }_i(A-{\lambda }_{i}I)v=0$ gives the next dependence. Hence $\boxed{s=s^{\prime }}$. Equivalently the coefficients of these powers form a full-rank Vandermonde matrix through this index.

The coefficient matrix is a Vandermonde matrix, with determinantTherefore a nonzero solution exists exactly whenFor example if $a=b$, the first two columns are equal and $(1,-1,0)$ is a solution. If exactly two parameters agree, the distinct remaining column is independent of the repeated one, so the kernel has dimension one. If all three agree, only $x+y+z=0$ remains, giving a two-dimensional kernel.

Clearing the denominators in the rational interpolation conditions givesThese are $n+1$ linear equations for $(m+1)+\ell =n+1$ unknowns. The $i$th row of the coefficient matrix, in the order $a_0,\dots ,a_m,b_0,\dots ,b_{\ell -1}$, isThis rational interpolation linearization is equivalent to the original fraction conditions only if $r(x_i)\ne 0$ at every interpolation node. If $r(x_i)=0$, the cleared equation merely forces $q(x_i)=0$, leaving the fraction undefined.

For $f_i=x_i^{m+1}$, the coefficient row becomesThis is the Vandermonde matrix, whose determinant is ${\prod }_{0\le i<j\le n}(x_j-x_i)\ne 0$. Equivalently, a vector in its null space would define a degree-at-most-$n$ polynomial vanishing at all $n+1$ distinct interpolation nodes, which is zero by the preceding uniqueness proof. Thus the cleared linear system has exactly one solution.

There is also a constructive description of that solution. Define the monic polynomialThe polynomial $x^{m+1}r(x)-q(x)$ is monic of degree $n+1$ and vanishes at every interpolation node. It must therefore equal $W(x)$. By polynomial division, write uniquelyThe quotient $R$ is monic of degree $\ell$, andis the unique coefficient solution. This does not assert that $R$ is nonzero at every interpolation node.

For a counterexample with $m=0$, $\ell =1$, choose $x_0=0,x_1=1$ and the specified data $f_i=x_i$, so $f_0=0,f_1=1$. The cleared equations reduce togiving the unique solution $q(x)=0$, $r(x)=x-1$. But at $x_1=1$ the quotient is $0/0$. Indeed, any genuine rational interpolant of this prescribed form would need $r(0)\ne 0$; then $q(0)/r(0)=0$ forces the constant numerator to be zero. At a nonzero denominator its value at $1$ would also be zero, never one. Cancelling the common factor in the cleared candidate would merely give the identically zero rational function, which still fails the data. Hence

For rational interpolation with $\mathrm{deg}q\le m$ and a monic denominator $r(x)=x^{\ell }-{\sum }_{j=0}^{\ell -1}{b}_j{x}^j$, multiplying through gives the linear systemThese equations are equivalent to the fraction conditions only when all $r(x_i)$ are nonzero. If $f_i=x_i^{m+1}$ and $m+\ell =n$, the coefficient matrix is the Vandermonde matrix with rows $(1,x_i,\dots ,x_i^n)$, so distinct interpolation nodes give a unique coefficient solution. More constructively, divide $W(x)={\prod }_{i=0}^n(x-x_i)$ by $x^{m+1}$ as $W=x^{m+1}R+S$, $\mathrm{deg}S\le m$. Then $r=R$, $q=-S$, since $x^{m+1}r-q$ is the unique monic degree-$n+1$ polynomial vanishing at all the interpolation nodes. The quotient may vanish at a node, so unique solvability of this linear system does not prove existence of a rational interpolant.

Collect the distinct nonzero values among the ${\lambda }_j$ as ${\mu }_1,\dots ,{\mu }_r$ with positive multiplicities $m_j$. The first $r$ power sums imply ${\sum }_j{m}_j{\mu }_j^k=0$ for $1\le k\le r$. The coefficient matrix is an invertible weighted Vandermonde matrix, so all $m_j$ vanish, a contradiction unless $r=0$. Its invertibility also follows because a polynomial ${\sum }_{k=1}^r{a}_k{z}^k$ vanishing at zero and all the ${\mu }_j$ has $r+1$ distinct roots and degree at most $r$.