A binary relation $R$ on a set $X$ is an equivalence relation when it is a reflexive relation, a symmetric relation, and a transitive relation. In first-order logic, these three requirements are

The “same age” binary relation is a Euclidean relation, with age understood as one consistently measured value at a fixed time. If $x$ has the same age as both $y$ and $z$, the ages of $y$ and $z$ are equal. HenceThis is another instance of equality of the values of a function inducing an equivalence relation.

Inequality on a domain containing at least two people is not a Euclidean relation. Choose distinct people $a,b$ and put $x=a$, $y=z=b$. Both premises $a\ne b$ hold, but the conclusion would be $b\ne b$. ThusThe possibility $y=z$ matters: the defining universal quantifiers do not require distinct arguments. On a domain with at most one element the inequality binary relation is empty and the condition holds by vacuous truth.

Equality of remainders after division by eight is a Euclidean relation. If $x$, $y$ have the same remainder and $x$, $z$ have the same remainder, then $y$, $z$ have the same remainder. In the notation of modular arithmetic,Hence

The divisibility binary relation on positive natural numbers is not a Euclidean relation. With $x=1$, $y=2$, $z=3$, we have $1\mid 2$ and $1\mid 3$ but $2\nmid 3$. Therefore

The binary relation $x\le y$ on the natural numbers is not a Euclidean relation. Choose $x=1$, $y=3$, $z=2$. Then $1\le 3$ and $1\le 2$, but $3\nleqq 2$. Thus

Let $I$ be the number of heads in the initial allocation tosses. Then $I$ has the binomial distribution with parameters $n$ and $1/2$. Given $I=i$, the winning probability is $i/n$, including the already finished games $i=0,n$. The law of total probability and linearity of expectation giveThus, for $n\ge 1$,

Let $W$ be the event that $H$ wins, and $F$ the event that his first toss is a tail. For a nontrivial starting state $1\le i\le n-1$, a first tail has probability $1/2$ and changes his holding to $i-1$. By the chain rule for probabilities,Since $\mathbb{P}(W)=i/n>0$, the definition of conditional probability givesIn particular, when $i=1$, losing the first coin would end the game in defeat, so the conditional answer is zero. At $i=0$ conditioning on victory is undefined, while at $i=n$ the game has already ended and no first toss occurs.

Let $X_j$ be the indicator random variable that coin $j$ shows a head. Each expectation is $\mathbb{E}{X}_j=1/2$, so linearity of expectation gives the expected number of heads:For the game, write $p_i$ for the probability that $H$ eventually holds all $n$ coins when starting with $i$. The states $0,n$ are absorbing, so $p_0=0$ and $p_n=1$. Conditioning on the first toss and using the law of total probability givesThus $p_{i+1}-p_i=p_i-p_{i-1}$: successive differences are constant, and $p_i=A+Bi$. The boundary values give $A=0$, $B=1/n$, hence the gambler's ruin answer isFor completeness, the game terminates with probability one. From any nonabsorbing state, a run of $n$ consecutive heads would reach $n$ within the next $n$ tosses, and that run has probability $2^{-n}$. Conditional on survival, the same bound applies to the next block. Therefore the probability of surviving $kn$ tosses is at most $(1-2^{-n}{)}^k$, which tends to zero.

The partition theorem is the law of total probability. If $B_1,B_2,\dots$ form a finite or countable partition of a sample space into pairwise disjoint events with positive probabilities, then for any event $A$,Indeed, $A$ is the disjoint union of the events $A\cap B_j$, so countable additivity gives the formula after applying the definition of conditional probability. Zero-probability members can be omitted.

For events $A,B$ with $\mathbb{P}(B)>0$, the conditional probability isIt measures the probability of $A$ after restricting the sample space to $B$ and renormalizing. This quotient does not define conditional probability given an event of zero probability.

A square matrix is an invertible matrix exactly when its determinant is nonzero. The preceding recurrence relation therefore gives

Let $A_n$ denote the given tridiagonal matrix and put $D_n=\det A_n$, including $D_0=1$ for the empty determinant. The starting values areFor $n\ge 3$, apply the following elementary row operations in the indicated order, always using the updated rows:The first three rows now beginwith the fourth column omitted if $n=3$. When $n\ge 4$, also use $R_4\leftarrow R_4-R_3$. The resulting block upper triangular matrix has a $3\times 3$ upper triangular matrix with diagonal entries all one in its top left corner, and $A_{n-3}$ in its bottom right corner. All elementary row operations preserved the determinant except the single row interchange. ThereforeApplying this recurrence relation to the three starting values proves by mathematical induction thatEquivalently, the sequence is periodic with period six, with values $1,1,0,-1,-1,0$ starting at $n=0$. A compact closed form is $D_n=\sin ((n+1)\pi /3)/\sin (\pi /3)$.

If a square matrix $A$ is an invertible matrix, multiplicativity of the determinant givesso $\det A\ne 0$.

Conversely, suppose $\det A\ne 0$. Use Gaussian elimination to reduce $A$ to row echelon form $U$. Each elementary row operation multiplies the determinant by a nonzero factor, so $\det U\ne 0$. If this square matrix had fewer than $n$ pivots, its row echelon form would have a zero row and hence zero determinant, a contradiction. Therefore it has a pivot in every row and column, and further elementary row operations reduce it to $I$.

Each elementary row operation is multiplication on the left by an invertible matrix, its inverse being the reverse operation. Thus $E_k\cdots E_{1}A=I$ implies $A=E_1^{-1}\cdots E_k^{-1}$, a product of invertible matrices. Hence

For a square matrix, the corresponding changes in its determinant areThese follow respectively from the alternating property, multilinearity in the rows, and the fact that a determinant with two equal rows vanishes.

The three elementary row operations are:

The nonzero requirement in the second operation ensures that each elementary row operation is reversible.

Take the linear mapIts kernel of a linear map consists of all $(x,0)$, and its image of a linear map is the same line:Their set intersection is nonzero and their sum is only one-dimensional. In particular, $(0,1)$ cannot be written as a sum of one vector from each of these vector subspaces. The nonzero set intersection also prevents an internal direct sum of vector spaces. ThusThe matrix is a nonzero nilpotent matrix; its failure of diagonalizability explains why the preceding result does not apply.

By diagonalizability, $V$ has an eigenbasis $e_1,\dots ,e_m$ with $T{e}_j={\lambda }_j{e}_j$. Arrange the basis so that ${\lambda }_1=\cdots ={\lambda }_r=0$ and the remaining eigenvalues are nonzero. If there are no zero or no nonzero eigenvalues, the corresponding linear span below is simply the zero vector subspace.

For $v={\sum }_j{a}_j{e}_j$, the equation $Tv=0$ holds precisely when $a_j=0$ for every $j>r$. ThusEvery output is in $\mathrm{span}\{e_{r+1},\dots ,e_m\}$, and conversely $e_j=T({\lambda }_j^{-1}{e}_j)$ for each $j>r$. ThereforeThese two disjoint parts of a basis span $V$ and their linear spans intersect only at zero. This is exactly the direct sum of vector spaces assertion

The rank-nullity theorem states that a linear map $T:V\to W$ with finite-dimensional $V$ satisfiesChoose a basis $k_1,\dots ,k_r$ of $\ker T$ and use basis extension to obtain a basis $k_1,\dots ,k_r,u_1,\dots ,u_s$ of $V$. We prove that $T{u}_1,\dots ,T{u}_s$ is a basis of $\mathrm{im}T$.

Every $v\in V$ is a linear combination of the extended basis. Applying $T$ kills the $k_i$ terms, so $Tv$ is a linear combination of $T{u}_1,\dots ,T{u}_s$. This proves the linear span assertion. For linear independence, if ${\sum }_j{b}_{j}T{u}_j=0$, then ${\sum }_j{b}_j{u}_j$ belongs to the kernel of a linear map. Hence ${\sum }_j{b}_j{u}_j={\sum }_i{a}_i{k}_i$ for some scalars $a_i$. The linear independence of the extended basis forces every $a_i$ and $b_j$ to vanish. Consequently $\mathrm{rank}T=s$ and $\mathrm{nullity}T=r$, while $\dim V=r+s$, proving the theorem.

For a linear map $T:V\to W$, its image of a linear map and kernel of a linear map areTheir dimensions define the rank of a linear map and nullity:The image of a linear map measures which output vectors can occur, while the kernel of a linear map measures which input vectors are sent to zero.