Online text: raw.githubusercontent.com/kevin-wayne/algs4/master/src/main/java/edu/princeton/cs/algs4/BipartiteX.java

Cited passages: BipartiteX.java, class documentation: breadth-first search, linear construction time and vertex-linear extra space; bfs method: odd-cycle reconstruction; BipartiteX.java, constructor component loop and bfs method: discovery colours, parent pointers and same-colour conflict.

A statement true whenever execution reaches a chosen point in a loop, usually immediately before its condition is tested. Establish it initially, preserve it through each iteration, and combine it with the exit condition to establish algorithm correctness. Termination needs a separate argument.^[ref]

Write $I$ for the loop invariant, $B$ for the condition, $P$ for the precondition, and $Q$ for the postcondition. Prove that initialization under $P$ establishes $I$, that a completed body starting with $I$ and $B$ restores $I$, and that $I$ with false $B$ implies $Q$.^[ref]

In the prefix maximum correctness example, the loop invariant remembers exactly the maximum of the processed prefix and the valid index bounds. The weaker statement $\mathrm{best}\ge a_0$ survives every iteration, but does not imply the postcondition: for $[3,1,4,4,2]$, the wrong value $3$ satisfies it. A useful loop invariant retains enough information to recover the answer when the condition becomes false.

Conformance of an implementation's behaviour to its specified functional requirements. The exact obligations come from the formal specification: correct delivery of an IPC payload and correct computation of a file read are different requirements. Neither requirement by itself supplies a numerical response-time bound.

Establishing specified properties of a system using formal proofs about a precise model. Formal verification connects an implementation to a formal specification; correctness of the model and its assumptions still matters when applying the result to a physical system.

For a small example, the summation loop verification below starts with executable steps and asks two separate questions: does any returned value satisfy the postcondition, and does execution reach that return? A loop invariant answers the first; a loop variant answers the second. This turns an unbounded family of permitted inputs into a few reusable proof obligations.

The model must specify programming language semantics, including the meaning of variable assignments, comparisons and integer arithmetic. A proof about exact mathematical integers need not describe a machine that wraps on integer overflow. Similarly, a correct formal proof of a weak or mistaken formal specification does not establish the intended behavior. Choosing the right formal specification and relating the model to the implemented system remain substantive tasks.

Software testing examines chosen executions and can expose a counterexample. A formal proof instead justifies a statement throughout its stated model; it does not require executing every permitted input. This makes formal verification valuable when rare boundary cases matter, while software testing can still reveal an incorrect model or misunderstood requirement.

In 1969, Tony Hoare presented rules for variable assignment, composition and iteration in a small programming language. His paper explicitly says those rules do not prove successful termination, and discusses the dependence of arithmetic reasoning on the chosen overflow behavior. These reservations already make the model's scope part of the argument.^[ref]

The tensor product of fields $L{\otimes }_{K}M$ is a $K$-algebra, not necessarily a field. If $L$ and $M$ sit in one overfield, the map $l\otimes m\mapsto lm$ has an image that generates their compositum as a field. When the extensions are algebraic, this image is already a field. Injectivity of this multiplication map is equivalent to linear disjointness.

The eight Gell-Mann matrices ${\lambda }_1,\dots ,{\lambda }_8$ form a conventional orthogonal basis of the real vector space of traceless Hermitian matrices of size three. In terms of matrix units $E_{ij}$, one standard ordering isDirect matrix multiplication gives $\mathrm{tr}({\lambda }_a{\lambda }_b)=2{\delta }_{ab}$. Thus a traceless Hermitian matrix $H$ has the expansion $H=\frac{1}{2}{\sum }_a\mathrm{tr}(H{\lambda }_a){\lambda }_a$. Multiplication by $i$ gives a real basis of the special unitary Lie algebra $\mathfrak{su}(3)$; physicists often use the Hermitian generators $T_a={\lambda }_a/2$ instead.

The first three matrices contain the Pauli matrices in the first two coordinates, so $[{\lambda }_1,{\lambda }_2]=2i{\lambda }_3$. This displays the special unitary Lie algebra $\mathfrak{su}(2)$ inside the three-state matrix algebra and provides concrete generators for calculations in the special unitary group $SU(3)$.

The Pauli matrices are the complex two-by-two matricesEach is a traceless matrix, a Hermitian matrix and a unitary matrix. Their eigenvalues are $+1,-1$, and direct matrix multiplication gives ${\sigma }_x{\sigma }_y=i{\sigma }_z$, with cyclic permutations and a minus sign for reversed order. This is the Pauli matrix multiplication law.

Together with the identity matrix, they form the Pauli operator basis of all complex two-by-two matrices. For spin one-half, the angular momentum operators are $S_j=\hslash {\sigma }_j/2$, so a spin measurement along a unit vector $n$ has outcomes $\pm \hslash /2$. For example, ${\sigma }_z$ has the standard basis as its eigenbasis, whereas ${\sigma }_x$ has normalized eigenvectors $(1,\pm 1{)}^T/\sqrt{2}$. This makes changing the measurement axis an explicit change of basis.^[ref]

For integers $a,b$ not both zero, there are integers $x,y$ such that $ax+by=\gcd (a,b)$. The extended Euclidean algorithm constructs them. For example, $4\cdot 252-5\cdot 198=18$ and $7\cdot 5-2\cdot 17=1$; the second identity also gives the modular inverse of $5$ modulo $17$.

The identity converts a greatest common divisor into a solvability certificate. The linear Diophantine equation $ax+by=c$ is solvable in integers precisely when $\gcd (a,b)$ divides $c$. Every common divisor divides any integer linear combination; conversely, multiplying a Bézout identity by $c/\gcd (a,b)$ constructs a solution when that quotient is integral. The coefficients generally are not unique, as the description of all solutions of a linear Diophantine equation makes explicit.

An algebraic derivation of an algebra over a field is a linear map satisfying the Leibniz rule for its multiplication: $D(xy)=D(x)y+xD(y)$. This definition makes sense even when the multiplication is not associative. A derivation of an algebra uses an associative product; a derivation of a Lie algebra uses the Lie bracket as its product.

An algebraic structure is a set equipped with specified algebraic operations satisfying selected axioms. An operation's domain is part of the structure: a binary operation on $S$ takes two elements of $S$ and produces another element of $S$. Groups specify one such operation, rings specify addition and multiplication, and vector spaces specify vector addition and scalar multiplication by a separate field.

Different choices of operations can give the same underlying set different structures. The integers form a group under addition, since every integer has an additive inverse. They do not form a group under multiplication: for example, $2$ has no multiplicative inverse among the integers. Even the nonzero integers fail that inverse requirement. In contrast, nonzero rational numbers form a group under multiplication.

Finite multiplication tables make such distinctions visible. Arithmetic modulo $5$ gives a field; arithmetic modulo $6$ gives a commutative ring with zero divisors. In the former, multiplying by any nonzero element permutes all residue classes. In the latter, multiplying by $2$ reaches only $0,2,4$, and $2\cdot 3=0$ even though both factors are nonzero.

The goal is to extract reusable properties rather than memorize isolated tables. A homomorphism preserves the specified operations, and an isomorphism shows that two structures have identical operation patterns after relabeling.

Algebraic K-theory studies invariants built from projective modules and their automorphisms over rings. Its lowest groups record the additive projective-module classes and stable invertible matrices, respectively. It differs from Topological K-theory, although vector-bundle clutching and module patching have parallel forms.

A mathematical expression combines symbols according to formation rules, such as $2x+1$, $(x+1{)}^2$, or $\sqrt{x}$. With values for its variables and meanings for its algebraic operations, it can be evaluated. An equation relates two mathematical expressions; an expression alone need not assert anything.

For example, $2x+3$ evaluates to seven at $x=2$ and nine at $x=3$. Neither value solves anything until a condition is imposed: the equation $2x+3=9$ selects $x=3$ from the real numbers. This distinction is useful when moving from a formula to a question about which inputs satisfy it. Evaluation by replacing the variables with assigned values is described in College Algebra 2e, §1.1: Evaluating Algebraic Expressions.

Different written mathematical expressions can have the same value for every input in a common domain of a function. The distributive property expands $(x+1{)}^2$ to $x^2+2x+1$, while factorizing reverses that change of form. The mathematical identity between them lets one choose the form suited to the next task: the factored form exposes a multiple root at $x=-1$, and the expanded form exposes its coefficients. Simplifying should preserve values on the stated domain, rather than silently enlarging it.

An equation asserts that two mathematical expressions have the same value. Solving it means finding all allowed assignments to its variables that make that assertion true. It converts a relationship into a constraint: a measurement, a geometric intersection, or an equilibrium model can leave an unknown value to determine.

The allowed values matter. The equation $2x=1$ has solution set $\{1/2\}$ over the rational numbers, but the empty set over the integers. Over the real numbers, $x^2=1$ has two solutions, $-1$ and $1$. A mathematical identity, such as $(x+1{)}^2=x^2+2x+1$, holds for every permitted real $x$. The familiar equality sign therefore does not by itself say whether one is checking a particular value, solving for an unknown, or stating an identity.

For a worked linear equation over the real numbers,The first step subtracts three from both sides; the second divides both sides by the nonzero number two. Reversing the steps recovers the original equation, so these are equivalent equations with the same solution set $\{3\}$. Checking the value gives $2\cdot 3+3=9$. The role of reversible operations and the classification by solution sets are described in College Algebra 2e, §2.2: Solving Linear Equations in One Variable.

When the two sides define real-valued functions $f$ and $g$ on a common domain of a function, solutions are exactly the input values at which their function graphs intersect. Equivalently, they are the zeros of a function $f-g$. This gives a useful connection between symbolic algebra and geometry: rearranging an equation can simplify the comparison without changing the inputs where equality holds.

Not every operation is reversible on every domain of a function. Dividing $x(x-1)=0$ by $x$ gives $x-1=0$ only after restricting to $x\ne 0$; it loses the solution $x=0$ if that restriction is forgotten. Squaring both sides can instead introduce an extraneous solution, because distinct real numbers can have the same square. The source equation, its domain of a function, and the direction of each implication should travel together.