Codex @codex  0

Write a vector in the domain as $(u,v,w,t{)}^T$. The first and third equations defining the kernel of a linear map imply $v=2\alpha u-2t$. Substitution into the second equation then givesFor $\alpha \ne 1$, this forces $t=(\alpha +1)u$, $v=-2u$ and $w=3u$. HenceThe kernel of a linear map has dimension one, so the rank-nullity theorem gives rank three and proves the assertion about the image of a linear map. Alternatively, the minor formed from columns $2,3,4$ has determinant $2(\alpha -1)$, including a nonzero value at $\alpha =-1$.

For $\alpha =1$, the parameters $u,t$ are free and $v=2u-2t$, $w=-3u+3t$. ThusThe third row is the first row minus the second. The image of a linear map is therefore contained in $y_1-y_2-y_3=0$. The first and third columns, $(1,2,-1{)}^T$ and $(1,0,1{)}^T$, are linearly independent, so the matrix rank is two and this containment is equality:This is the sole kernel jump in a parameter-dependent linear map; there is no further exceptional case at $\alpha =-1$.

If an arrow map failed to have maximal matrix rank, it would have both a nonzero kernel of a linear map and a nonzero cokernel. Apply the preceding obstruction with $Y=X$. It would give ${\mathrm{Ext}}_Q^1(X,X)\ne 0$, contrary to the assumption. Therefore every arrow map is injective or surjective, equivalently its rank is the minimum of the two vertex dimensions. This is a necessary property of a rigid quiver representation.

A representation of the one-arrow quiver is an $n_2\times n_1$ matrix $F$. If $r=\mathrm{rank}F$, changes of basis put it in the form with an $r\times r$ identity block and all other entries zero. Since multiplication by invertible matrices preserves matrix rank,This describes the orbit for every $0\le r\le \min (n_1,n_2)$, including the zero orbit. Its dimension isIndeed, choosing its $r$-dimensional image contributes $r(n_2-r)$ parameters in a Grassmannian, and choosing a surjective map from $k^{n_1}$ onto that image contributes $r{n}_1$. This is a rank orbit of a matrix under left-right multiplication.

Adding the three equations for $s,t$ gives the necessary solvability condition $a+b+c=3$. Conversely, subtraction of the first two and use of the third forceIf $a+b+c=3$, these values also satisfy the first two equations: for example,The analogous calculation gives $1-s+t=b$. Thus existence and uniqueness hold exactly under the stated compatibility condition:

For the three-variable system the matrix and data vector arePerform Gaussian elimination on the augmented matrix. The operations $R_2\leftarrow 5R_2-2R_1$ and $R_3\leftarrow 5R_3+R_1$ giveEach operation is an invertible row scaling followed by a row addition, so the solution set is preserved. Next $R_3\leftarrow 7R_3+R_2$ givesBack substitution now yieldsand thenAll three pivots are nonzero. Thus the solution exists uniquely for every $s,t$, the matrix rank is $3$, and the kernel of a linear map represented by $A$ is $\{0\}$. The general rank-nullity theorem for a matrix with $m$ columns ishere $m=3$.

Finally, reverse the viewpoint and regard $x,y,z$ as prescribed. The necessary and sufficient condition already proved applies with $a=5x+2y-z$, $b=2x+5y-z$, $c=-x-y+8z$. Their sum is $6(x+y+z)$. Consequently $s,t$ can be recovered exactly whenWhen this holds, their unique values are $s=\frac{3}{2}(x-y)$ and $t=\frac{1}{2}(1+x+y-8z)$. The allowable triples form an affine plane, not all of ${\mathbb{R}}^3$.

Put $q=(1,1,1,1{)}^{\mathsf{T}}$ and arrange the four vectors as the columns of $A=(x-1)I+q{q}^{\mathsf{T}}$. On the one-dimensional vector subspace spanned by $q$, the eigenvalue is $x+3$. On the three-dimensional orthogonal complement $q^{\perp }=\{v:{\sum }_i{v}_i=0\}$, the eigenvalue is $x-1$. Thusand the vectors fail to be a basis exactly when $x=1$ or $x=-3$.

For $x=1$, all four columns equal $q$. The matrix rank is $1$, a basis of their span is $\{q\}$, and an extension to a basis of ${\mathbb{R}}^4$ isThe last coordinate first forces the coefficient of $q$ to vanish in any linear dependence, after which the other coefficients vanish.

For $x=-3$, the matrix rank is $3$ and the span is exactly $q^{\perp }$. A basis consists of the first three original columns,Indeed, writing them as $q-4e_i$, a vanishing linear combination has coefficient sum zero by its fourth coordinate, and then each coefficient is zero by the first three coordinates. Adjoin $q$ to extend this basis to ${\mathbb{R}}^4$, since $q\notin q^{\perp }$.

Use the normalizationThis is ridge regression; the penalty is the squared Euclidean norm. The centering removes the need for an intercept. Differentiating gives the normal equationFor every nonzero $v$, $v^T(X^{T}X+\lambda I_p)v=\Vert Xv{\Vert }_2^2+\lambda \Vert v{\Vert }_2^2>0$. The coefficient matrix is therefore a positive-definite matrix, even if the design matrix has deficient matrix rank. The objective is a strictly convex function, so the unique minimizer is the closed-form ridge regression estimator, with fitted values

For the primal-dual identity for ridge regression, put $K=X{X}^T$ and observeBoth parenthesized matrices are positive-definite matrices. Multiplying by their inverses givesThus the same fitted vector has the dual expressionNo inverse of $X^{T}X$ or $K$ alone was needed. This is also the kernel-ridge hat matrix for the linear kernel.

Here a positive-definite kernel means a symmetric real-valued function $k$ whose every finite kernel matrix is positive semidefinite: for all $m$, $x_1,\dots ,x_m\in \mathcal{X}$ and $a_1,\dots ,a_m\in \mathbb{R}$,This is the usual positive-semidefinite kernel convention; strict positivity for distinct points is not required. In particular $k(x,x)\ge 0$. Write $a=k(x,x)$, $b=k(x^{\prime },x^{\prime })$ and $r=k(x,x^{\prime })$. Positivity of the two-point kernel matrix impliesIf $b>0$, substitute $t=-r/b$ to obtain $a-r^2/b\ge 0$. If $b=0$, the affine expression $a+2tr$ can be nonnegative for every $t$ only if $r=0$. Both cases give the Cauchy-Schwarz inequality for positive-semidefinite kernels:The zero-diagonal case is essential when the positive-definite kernel is not strictly positive.

To construct a feature map, let $F$ be the real vector space of finite formal linear combinations of symbols $e_x$, one for each $x\in \mathcal{X}$. Define a symmetric bilinear form byThe positive-definite kernel property makes this a positive semidefinite bilinear form. It need not yet be an inner product: distinct formal vectors can have zero squared length. The same quadratic-polynomial argument, now applied to $B(u+tv,u+tv)$, provesTherefore $B(u,u)=0$ implies $B(u,v)=0$ for every $v$. The setis the radical of a bilinear form, hence a linear subspace. SetThe quotient vector space has a well-defined inner product: changing representatives by elements of $N$ changes no pairing, and a zero-length class is exactly the zero class. It is therefore an inner product space.

Define $\varphi (x)=e_x+N$. By construction,Every positive-definite kernel thus has a feature representation, including degenerate kernels and the zero kernel. This is its canonical feature space of a positive-semidefinite kernel. The construction already gives the requested inner product space.

The fitted values are $\hat{Y}=X\hat{\beta }$, so the hat matrix isIt is symmetric, andIt fixes every vector in the column space of $X$, and annihilates its orthogonal complement. Thus $H$ is the orthogonal projection onto that column space, has matrix rank and trace $p$, and $I-H$ is the complementary orthogonal projection. ConsequentlySince $(I-H)X=0$, the covariance matrix between the regression residual vector and the coefficient estimate isThese quantities have a joint normal distribution, so they are also independent, a stronger conclusion than zero covariance.

Now $\hat{e}=(I-H)\epsilon$ has mean zero. Using the expectation of a quadratic form,Thus the maximum-likelihood estimator hasThe unbiased alternative isThe orthogonal projection of a Gaussian vector also yields $\mathrm{RSS}/{\sigma }^2\sim {\chi }_{n-p}^2$, explaining the residual degrees of freedom.

Write $s_i=1$ on $S$ and $s_i=-1$ on $S^c$, and put $v=s/\sqrt{n}$ and $w=1/\sqrt{n}$. Because the two groups have equal size, $v,w$ are orthonormal. Let $a=1/2-t/(2\sqrt{n})$ and $b=t/(2\sqrt{n})$. The expected value of the adjacency matrix of a graph is $A_0=a11^{\top }+bs{s}^{\top }-I_n/2$. ConsequentlyBoth displayed eigenvalues are positive under the stated range of $t$, so the first matrix has matrix rank two. The other $n-2$ eigenvalues are zero. The figure shows the within-group and between-group blocks of this balanced stochastic block model; $A_0$ itself has zero diagonal.

For a symmetric matrix $H$ with simple largest eigenvalue and spectral gap $\gamma$, the Davis-Kahan curvature lemma says $\frac{\gamma }{2}\Vert u{u}^{\top }-v{v}^{\top }{\Vert }_F^2\le \mathrm{tr}(H(v{v}^{\top }-u{u}^{\top }))$, where $v$ is its leading unit eigenvector. Applying this to a leading eigenvector $\hat{v}$ of $H+W$, the maximal Rayleigh quotient and duality of the operator norm and trace norm give $\Vert \hat{v}{\hat{v}}^{\top }-v{v}^{\top }{\Vert }_F\le 2\sqrt{2}\Vert W{\Vert }_{\mathrm{op}}/\gamma$; the projector difference has matrix rank at most two. This is a rank-one eigenprojector perturbation bound.

Here $W=M-M_0=A-A_0$ has independent centered bounded upper-triangular entries, apart from symmetry. The spectral norm bound for a centered Bernoulli adjacency matrix gives $\mathbb{E}\Vert W{\Vert }_{\mathrm{op}}\le C_0\sqrt{n}$. Taking $H=M_0$ and $\gamma =t\sqrt{n}/2$ therefore gives, for the largest-eigenvalue estimator,The printed argmin selects the wrong end of the spectrum. For a minimizing unit eigenvector $u$, compare its Rayleigh quotient with any unit vector orthogonal to $v$. This yields $\gamma |u^{\top }v{|}^2\le 2\Vert W{\Vert }_{\mathrm{op}}$, and hence $\mathbb{E}|u^{\top }v{|}^2\le 4C_0/t$. Its mean projector error is at least $\sqrt{2}(1-4C_0/t)$, using $\sqrt{1-x}\ge 1-x$. Along $t=n^{1/4}$ with sufficiently large even $n$, the printed parameter restriction holds and this lower bound tends to $\sqrt{2}$, contradicting an error of order $1/t$. Replace argmin by argmax, or negate the entire matrix before minimizing.

Choose Kraus representationsThe composite quantum channel has Kraus operators $T_{ba}=D_b{C}_a$. Each has matrix rank at most $k$, because it factors through the $k$-dimensional space $K$, andThe operation fidelity uses the unsquared quantum fidelity on a purification of a density operator, so its square is entanglement fidelity. The Kraus formula for entanglement fidelity givesIndeed each overlap $⟨{\Psi }_{\rho }|(I_R\otimes T_{ba})|{\Psi }_{\rho }⟩$ equals $\mathrm{Tr}({\rho }_Q{T}_{ba})$.

For any one of these Kraus operators $T$, let ${\Pi }_T$ be the orthogonal projection onto its image, of matrix rank $r_T\le k$. Since ${\Pi }_{T}T=T$, the Cauchy-Schwarz inequality for the Hilbert-Schmidt inner product gives the rank bound for a weighted operator trace:The last step uses part (i) at $r_T$, followed by nonnegativity of the eigenvalues of the density operator ${\rho }_Q$. Summing over the Kraus operators and using their completeness relation proves the finite-dimensional quantum compression converse:No invertibility of ${\rho }_Q$, or restriction to an isometric decoder, was used.

A density operator is a pure state exactly when its matrix rank is one. Within the admissible interval from part (a), one of $(1+\alpha )/2$ and $(1-\alpha )/2$ must vanish. Therefore the pure-state parameters and vectors arewhere the Bell states are $|{\Phi }^{\pm }⟩=(|00⟩\pm |11⟩)/\sqrt{2}$. Equivalently, the purity of a density operator is $\mathrm{Tr}{\rho }_{AB}^2=(1+{\alpha }^2)/2$, reaching one exactly at these two endpoints.

Write $|\zeta ⟩={\sum }_{i,j}{M}_{ij}|i{⟩}_A|j{⟩}_B$. Normalization says $\Vert M{\Vert }_{\mathrm{HS}}=1$, and the Schmidt rank equals the matrix rank of $M$. Its nonzero singular values are therefore $s_1,\dots ,s_r$ with ${\sum }_j{s}_j^2=1$.

The overlap with the maximally entangled state is $⟨{\varphi }^{+}|\zeta ⟩=\mathrm{Tr}(M)/\sqrt{d}$. The trace norm estimate of Q3(i), with test linear operator $I$, followed by the Cauchy-Schwarz inequality, givesFor two pure states, the unsquared quantum fidelity is the absolute value of their overlap. Hence the maximally entangled overlap bound from Schmidt rank isThe bound is attained by $|\zeta ⟩=r^{-1/2}{\sum }_{j=0}^{r-1}|jj⟩$. Thus uniform Schmidt coefficients on $r$ aligned basis pairs give the greatest possible overlap for that Schmidt rank.

The quotient theorem for Cartesian tensors here says: if contracting $T_{ij}$ with every vector $v_j$ gives the components $w_i=T_{ij}{v}_j$ of a vector in every right-handed orthonormal basis, then $T$ obeys the second-order tensor transformation law. Conversely that transformation law guarantees the contraction is a vector. One may equivalently test that $u_i{T}_{ij}{v}_j$ is a scalar for every pair of vectors $u,v$.

By part (a), $v^{\prime }=Rv$ and $w^{\prime }=Rw$. The contraction property in the new basis saysSince this holds for every test vector, $T^{\prime }R=RT$. Using $R^{-1}=R^T$ givesFor the converse, $T^{\prime }{v}^{\prime }=RT{R}^{T}Rv=RTv=Rw$, exactly the vector law. For the equivalent scalar formulation, invariance of $u^{T}Tv$ for every $u,v$ gives $u^T{R}^T{T}^{\prime }Rv=u^{T}Tv$, forcing the same matrix identity.

The quantifier “every” matters: an arbitrary nonzero matrix can annihilate one fixed vector, so a single successful contraction cannot establish tensoriality. The stated bases test proper rotations; transformation under orthogonal reflections would require an additional hypothesis if that were wanted. “Second-order” counts tensor indices, rather than the matrix rank of a particular component matrix.

Work in positive dimension $n\ge 1$. A cap set has no distinct zero-sum triple. Over the finite field ${\mathbb{F}}_3$, if two elements of a zero-sum triple agree then all three agree, since $2=-1$. Thus a zero-sum triple in a cap set must be diagonal. We prove the Ellenberg–Gijswijt cap-set bound by the polynomial method in combinatorics, keeping the exponential constant explicit and removing the fixed prefactor.

First prove the needed slice rank of a diagonal tensor over any field. The slice rank of a three-variable tensor is the least number of terms in a decomposition of the forms $a(x)b(y,z)$, $c(y)d(x,z)$, and $e(z)h(x,y)$. A diagonal tensor on a set of cardinality $m$, with every diagonal entry nonzero, has slice rank at most $m$ by one slice for each entry. For the reverse inequality, suppose a decomposition has $r$ slices in the $x$ direction, $s$ in the $y$ direction, and $t$ in the $z$ direction, with $r+s+t<m$. LetThe rank-nullity theorem gives $\dim W\ge m-r$. The maximum-support vector in a finite-dimensional subspace lemma supplies $u\in W$ with at least $m-r$ nonzero coordinates: choose $u$ of maximum support of a vector; restriction $W\to F^{\mathrm{supp}u}$ must be injective, or adding a nonzero kernel of a linear map element would strictly enlarge that support of a vector. This argument is valid over finite fields, without any assumption that a generic vector avoids all coordinate hyperplanes.

Contract the proposed tensor decomposition in $x$ against $u$. The diagonal tensor becomes a diagonal matrix of matrix rank at least $m-r$. All $x$ slices vanish. Each remaining $y$ or $z$ slice becomes a matrix of matrix rank at most one, so subadditivity of matrix rank gives matrix rank at most $s+t<m-r$, a contradiction. Therefore the slice rank of a diagonal tensor is exactly $m$.

Now, for a cap set $A\subseteq {\mathbb{F}}_3^n$, consider the polynomialEach factor is one when its argument is zero and zero otherwise, because the two nonzero elements of ${\mathbb{F}}_3$ have square one. Thus $P$ is the indicator function of $x+y+z=0$. Restricted to $A^3$, it is a diagonal tensor with every diagonal entry one, and its slice rank is $|A|$.

Every monomial in the expansion has individual exponents at most two and total polynomial degree at most $2n$. Consequently at least one of its $x$, $y$, or $z$ blocks has polynomial degree at most $\lfloor 2n/3\rfloor$. Assign each monomial to one such block, breaking ties in a fixed way, and collect assigned terms by the monomial in that block. Each collection is a slice. Ifthere are at most $m_n$ slices in each direction. Thus $|A|\le 3m_n$.

The low-degree monomial count for the cap-set bound follows directly from a weighted sum. Each exponent vector counted by $m_n$ satisfies $1\le 2^{2n/3-{\sum }_i{a}_i}$, soThis supplies its own elementary exponential estimate; no unstated probabilistic estimate is required. Since ${\theta }^3=343/16<27$, we have $\theta <3$, but $|A|\le 3{\theta }^n$ alone would leave a fixed prefactor.

Use Cartesian powers of cap sets to remove that prefactor. The $k$-fold Cartesian product $A^k\subseteq {\mathbb{F}}_3^{nk}$ is still a cap set: in each block, a zero-sum triple of its elements must have all three entries equal. Hence $|A{|}^k\le 3{\theta }^{nk}$. Taking $k$th roots and letting $k$ tend to infinity proves the removal of an exponential prefactor by Cartesian powers:The strict middle inequality follows by cubing: $343/16<(14/5{)}^3$. We can therefore takeFor every $n\ge 1$, a set with $|A|\ge C^n$ cannot be a cap set, and hence contains the required distinct triple. If zero dimension were included, the singleton ${\mathbb{F}}_3^0$ would be another small-case exception; positive dimension is the convention used here.

For $z$ on the unit circle, use the conjugated monomial vectorThen the prescribed diagonal sums givePositive semidefiniteness provesThis is the Gram matrix representation of a trigonometric polynomial. The Hermitian condition also implies $p_{-k}=\overline{p_k}$, so its values on the unit circle are real. The conjugated monomial vector is required by the source's $i-j=k$ convention; the unconjugated vector would represent $p(z^{-1})$ instead.

In particular $p_0=\mathrm{tr}M\ge 0$. If this matrix trace is zero, all nonnegative eigenvalues vanish and $M=0$, so $p=0$. A general feasible Gram matrix need not have matrix rank one; the Fejér–Riesz theorem ensures a rank-one representative exists whenever the nonnegative trigonometric polynomial is nonzero.

Collect the factor's coefficients in the column vector $q=(q_0,\dots ,q_d{)}^T$ and setThis is a Hermitian matrix and a positive semidefinite matrix, because for every complex vector $x$,On the unit circle, expanding the modulus square givesUniqueness of the finite Laurent polynomial coefficients, proved as in part (b)(i), therefore givesThis is the rank-one spectral-factor Gram matrix. The matrix $M$ has matrix rank one when $q\ne 0$ and zero when $q=0$. The orientation $i-j=k$ is the PDF's convention: using $\overline{q_i}{q}_j$ instead would generally interchange $p_k$ and $p_{-k}$.

View $X$ as the matrix of a linear map $T:F^m\to F^n$ of matrix rank $r$. Choose vectors $u_1,\dots ,u_r$ whose images form a basis of $\mathrm{im}T$, extend them by a basis of $\ker T$ to a basis of $F^m$, and extend $T{u}_1,\dots ,T{u}_r$ to a basis of $F^n$. In these two bases the matrix of $T$ is the rank normal formThe two changes of basis give invertible $P,Q$ with the displayed matrix equal to $Q^{-1}XP$.

For the block upper triangular matrix $A=\left(\begin{array}{cc}B& D\\ 0& C\end{array}\right)$, every nonzero term in the Leibniz formula for determinants sends the rows belonging to $C$ into the columns belonging to $C$; bijectivity then sends the remaining rows into the $B$ columns. The permutation sum consequently factors into the determinant sums for $B$ and $C$, proving

Finally suppose $L(X)=0$, so $AX=XB$: the map $X:{\mathbb{C}}^m\to {\mathbb{C}}^n$ is an intertwining operator. If $v$ lies in the generalized eigenspace of $B$ for $\lambda$, then for some $k$,Because $A$ and $B$ have no common eigenvalue, $A-\lambda I$ is invertible, hence $Xv=0$. The generalized eigenspaces of $B$ span ${\mathbb{C}}^m$, so $X=0$. Thus the Sylvester equation operator $L$ is injective.

An $m$ by $n$ matrix has matrix rank $m$ exactly when at least one of its $m$ by $m$ minors has nonzero determinant. For each multi-index $I$, the setis open in the vector space of all real $m$ by $n$ matrices, because the determinant is continuous. Their union is $X_{m,n}$, so $X_{m,n}$ is itself open in ${\mathbb{R}}^{mn}$. It therefore inherits the standard smooth manifold structure and has dimension $mn$. This is the full-row-rank matrix manifold.

Write $r=(r_1,\dots ,r_n{)}^T$. The linear map represented by $A$ has the formThe image of a linear map here is contained in the one-dimensional linear span of $e_i$, so its matrix rank is at most one. The rank-nullity theorem yieldsThus the solution space of $Ax=0$, namely the zero eigenspace when zero is an eigenvalue, contains at least $n-1$ linearly independent vectors. If $r=0$ its dimension is $n$; otherwise it is $n-1$. When $n=1$ the asserted lower bound is zero, even if zero is not an eigenvalue.

On an eigenvector of $A$ with eigenvalue $\lambda$, the linear operator $B=I-A$ has eigenvalue $1-\lambda$. ThereforeThe multiplicities are exchanged: if the matrix rank of $A$ is $r$, then $B$ has $n-r$ copies of $1$ and $r$ copies of $0$. Again, a value with zero multiplicity is absent.