Let $U,V$ be $n\times n$ upper triangular matrices. For an entry below the diagonal, $i>j$, matrix multiplication givesIf $k<i$, then $U_{ik}=0$. If $k\ge i$, then $k>j$, so $V_{kj}=0$. Every summand is zero, givingThus $UV$ is an upper triangular matrix. Equivalently, a potentially nonzero summand would require $i\le k\le j$, impossible below the diagonal.

Apply the same elementary row operations to the augmented matrix:The last row establishes consistency; equivalently the third original row is the second minus twice the first, and the right-hand entries obey $3=7-2\cdot 2$. With $x_2=s$ and $x_4=5t$, the second equation gives $x_3=1+3t$ and the first gives $x_1=3-2s-17t$. All real solutions are thereforeThis affine solution space is one particular solution plus the null space. The two free variables show that there are no additional restrictions.

The reduced row echelon form givesTaking the free variables as $x_2=s$ and $x_4=5t$, the null space isThe two displayed vectors are linearly independent, as their second and fourth coordinates show, and each satisfies $Ax=0$. ThusThis also agrees with the rank-nullity theorem: $4-2=2$.

The pivot columns in the row echelon form are columns 1 and 3. Use those columns of the original matrix for a basis of the original column space:For a direct spanning check, column 2 is twice column 1 and column 4 is $(17/5)$ times column 1 minus $(3/5)$ times column 3. The displayed columns are linearly independent, since the first two coordinates of $\alpha c_1+\beta c_3=0$ give $\alpha -\beta =0$ and $\alpha +4\beta =0$, so $\alpha =\beta =0$.

Perform the elementary row operations $R_2\leftarrow R_2-R_1$ and $R_3\leftarrow R_3+R_1$, then $R_3\leftarrow R_3-R_2$:These operations preserve the row space. The two nonzero rows of this row echelon form are linearly independent: only the first has a nonzero first entry, and the second is nonzero. HenceFurther Gaussian elimination gives the reduced row echelon formwhich will also identify the free variables in the null space calculation.

For an $m\times n$ matrix $A$ with real entries, its row space is the linear span of its rows, a linear subspace of ${\mathbb{R}}^n$. Its column space is the linear span of its columns, a linear subspace of ${\mathbb{R}}^m$ and the image of a linear map $x\mapsto Ax$. Its null space isa linear subspace of ${\mathbb{R}}^n$. Finally,Thus the rank of a matrix counts the number of linearly independent columns, equivalently rows. The nullity is $\dim \ker A=n-\mathrm{rank}A$ by the rank-nullity theorem.

The remaining eigenvalues areThey have absolute value less than one. The three distinct eigenvalues give a basis of eigenvectors, which may be chosen as $v$, $u=(0,-1,1{)}^{\mathsf{T}}$ and $w=(-1,-1,2{)}^{\mathsf{T}}$, with $Pu=(3/5)u$ and $Pw=(1/2)w$. Write an arbitrary initial probability vector as $x_0=cv+\alpha u+\beta w$. Summing its entries shows $c=1$, because the entries of $v$ sum to one and those of $u,w$ sum to zero. ThereforeThis proves convergence for every initial probability vector, rather than merely identifying a possible limit. In particular,For the given initial probability vector, $\alpha =1/4$ and $\beta =-1/5$; substituting $n=1,2$ also recovers the previous answers. The slowest decaying eigenvector component has factor $(3/5{)}^n$.

The factorization of the characteristic polynomial shows that $\lambda =1$ is an eigenvalue. To find its normalized eigenvector, solve $(P-I)v=0$ together with $v_C+v_H+v_B=1$. The first two independent linear equations areThe first equation and normalization give $5v_C=1$. The second gives $v_H-v_B=v_C/2=1/10$, while $v_H+v_B=4/5$. Consequently,All entries are positive and sum to one. This probability vector is the stationary distribution.

Define the characteristic polynomial using $p(\lambda )=\det (\lambda I-P)$, where $I$ is the identity matrix. Expanding the determinant along the first row givesThus the characteristic equation isThe convention $\det (P-\lambda I)$ changes the sign of this cubic polynomial but gives the same roots.

Use matrix multiplication to evolve the probability vector by $x_{n+1}=P{x}_n$. With $x_0=(0.4,0.4,0.2{)}^{\mathsf{T}}$,Hence, in Central, Headington, Botley order,Both probability vectors have nonnegative entries summing to one.

For a square matrix $M$, an eigenvalue–eigenvector pair consists of a scalar $\lambda$ and a nonzero vector $v$ satisfyingThe linear map represented by $M$ therefore scales $v$ by $\lambda$. The exclusion of the zero vector matters: otherwise every scalar would satisfy the equation trivially.

The transition matrix acts on a column probability vector in the order Central, Headington, Botley. Thus column $j$ records the destinations of buses starting at station $j$. The Central-to-Headington, Headington-to-Botley and Botley-to-Central entries giveEach column sums to one, as required for this column convention for a stochastic matrix.

Let $H=\forall x\forall y(S(x,y)\vee \neg S(x,y))$ and abbreviateAssume $\exists bB(b)$ and eliminate the existential quantifier using a fresh eigenvariable $u$. Inside that subproof, specialize $B(u)$ at $p=u$. Write $s=S(u,u)$. The premise $H$ supplies $s\vee \neg s$, so a disjunction elimination rule finishes the contradiction:Line 7 abbreviates two consecutive universal quantifier elimination rule applications; no new rule is used. The fresh witness $u$ is absent from $H$, the assumed existential statement and the exported $\perp$, so the existential quantifier elimination rule satisfies its eigenvariable condition. This is the self-application behind the barber paradox, written entirely with the supplied rules.