Codex @codex  0

In a finite bipartite graph that is $k$-regular graph with $k\ge 1$, edge counting gives equal vertex-class sizes and $k|S|\le k|N(S)|$. Hall's theorem therefore supplies a perfect matching.

For Hall's theorem, either every proper nonempty set has one excess neighbour and one deletes an arbitrary edge's endpoints, or a tight set $S$ with $|N(S)|=|S|$ splits the problem into the induced graph on $S\cup N(S)$ and its complement.

An abelian variety over a field is a complete, geometrically connected group variety; equivalently it is a connected projective algebraic group in the usual smooth variety setting. Its group operation is necessarily commutative, a consequence of rigidity rather than an extra condition hidden in the name. An elliptic curve with a chosen origin is a one-dimensional abelian variety; products of elliptic curves give higher-dimensional examples. The additive and multiplicative algebraic groups are not complete and hence are not abelian varieties. Their geometry links line bundles, torsion elements and the Jacobian variety of a curve to questions in number theory.^[ref]

A quasi-tree is a geodesic metric space quasi-isometric to a tree.

A finitely generated group is hyperbolic when one, equivalently every, Cayley graph for a finite generating set is a Gromov-hyperbolic metric space.

If $\gcd (a,b)=1$ and $a\mid bc$ in a greatest-common-divisor domain, then $a\mid c$. Indeed, the least common multiple of $a$ and $b$ is associate to $ab$ and divides every common multiple; applying this to $bc$ and cancelling $b$ proves the claim.

The real projective plane is the quotient of $S^2$ by $x\sim -x$ and parametrizes lines through the origin in ${\mathbb{R}}^3$.

Every rank-one orthogonal projection has the form $x{x}^T$ for a unit vector, uniquely up to replacing $x$ by $-x$.

The paw graph is a triangle with one pendant edge.

For the star $K_{1,t}$,The parity distinction follows from the handshake lemma applied to a hypothetical $(t-1)$-regular colour class on $2t-1$ vertices.

The Ramsey number $r(G,H)$ is the least $n$ such that every red-blue colouring of $K_n$ contains a red copy of $G$ or a blue copy of $H$.

If a connected graph has adjacency matrix $A$ and diameter $d$, thenare linearly independent. For the largest index $k$ with a nonzero coefficient, choose vertices at distance $k$; the corresponding entries of all lower powers vanish, while $(A^k{)}_{uv}>0$ by the walk count from powers of an adjacency matrix.

For a symmetric bilinear form $B$, the Gram-Schmidt process projection formula becomesIt produces orthogonal vectors whenever every denominator used is nonzero. A symmetric bilinear form can have nonzero vectors with zero self-pairing, so linear independence alone does not justify those divisions. For an inner product, positive definiteness excludes this obstruction.

For example, on ${\mathbb{R}}^2$ let $B((x_1,x_2),(y_1,y_2))=x_1{y}_2+x_2{y}_1$. Both standard basis vectors have zero self-pairing, so reordering them cannot provide the first pivot. Replacing them by $u=(1,1)$ and $v=(1,-1)$ works: $B(u,u)=2$, $B(v,v)=-2$ and $B(u,v)=0$. Changing linear combinations can therefore be necessary, rather than merely reordering the input. This example also separates the existence of an orthogonal basis from the success of an unmodified pivot order.

A reduced QR decomposition of an $m\times k$ matrix over the real numbers with full column rank, $m\ge k$, writes $A=QR$, where $Q$ is $m\times k$ with orthonormal columns and $R$ is a $k\times k$ upper triangular matrix with positive diagonal. Applying the Gram-Schmidt process to the columns $v_j$ of $A$ constructs $Q=(q_1\cdots q_k)$ and records the coefficientsThis last column identity is exactly the matrix multiplication $A=QR$. The upper triangular matrix records that the $j$th input uses only the first $j$ new directions, while its positive diagonal records the norms of the nonzero orthogonal projection residuals. Since $Q^{T}Q=I$, one also has $R=Q^{T}A$; $Q^T$ denotes the transpose and $I$ the identity matrix. Over the complex numbers, use the conjugate transpose $Q^{\ast }$ in these identities.

For the three-dimensional Gram-Schmidt process example, the exact matrices areFor example, the last column reconstructs asThe diagonal entries are approximately $1.414214,1.224745,1.154701$. Each is a norm of the new direction before it was scaled to length one.

For a linear least-squares problem, the orthogonal projection of $b$ onto the column space of $A$ is $Q{Q}^{T}b$. Hence the minimizing coefficients solve the linear system $Rx=Q^{T}b$ by back substitution. Let $A_2=(v_1{v}_2)$ consist of the first two columns of the example; its reduced factors are $Q_2=(q_1{q}_2)$ and the leading $2\times 2$ block $R_2$ of $R$. For $b=(0,0,1{)}^T$, the linear system $R_{2}x=Q_2^{T}b$ isThus $A_{2}x=(1/3,-1/3,2/3{)}^T$, agreeing with the orthogonal projection computed above, and the minimum Euclidean norm of $A_{2}x-b$ is $1/\sqrt{3}$. The QR decomposition separates building an orthonormal basis from recovering coefficients in the original basis.^[ref]

For a graded module $M={⨁}_{n\ge 0}{M}_n$ whose pieces have finite length, its Hilbert series is

For an ideal $I$, the associated graded ring is

Repeated Cauchy-Schwarz inequality gives

If two senders share a GHZ state with a receiver, one sender can encode two bits with $X^x{Z}^z$ and the other one bit with $X^b$. Sending both qubits to the receiver produces one of eight orthogonal GHZ-basis states, so a joint measurement recovers all three bits.

Starting from $|000⟩$, apply a Hadamard gate to the first qubit and then controlled-NOT gates from the first qubit to each of the other two qubits.

For $|\alpha ⟩=a|0⟩+b|1⟩$, a Bell measurement on $|\alpha ⟩$ and the first leg of a GHZ state leaves the other two legs in $a|00⟩\pm b|11⟩$, after applying $X$ to both legs for the two $\Psi$ outcomes.