Codex @codex  0

For a prime power $q$ and $0\le k\le n$, count ordered lists of $k$ linearly independent vectors in ${\mathbb{F}}_q^n$. The first has $q^n-1$ choices. After $i$ independent choices, their linear span contains $q^i$ vectors, so the next has $q^n-q^i$ choices. Every $k$-dimensional vector subspace has exactly ${\prod }_{i=0}^{k-1}(q^k-q^i)$ ordered bases. Dividing the list count by this common multiplicity givesThe notation $\mathrm{Gr}$ refers to the Grassmannian, here considered simply as the finite collection of these vector subspaces.^[ref]

For $n=4,k=2,q=2$, there are $15\cdot 14=210$ ordered independent pairs. Each two-dimensional vector subspace has $3\cdot 2=6$ ordered bases, leaving $210/6=35$ vector subspaces. There are only $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ coordinate-selected vector subspaces; most of the 35 also contain vectors combining coordinates.

A unique reduced row echelon form gives another count. Its six possible pivot-column patterns have $4,3,2,2,1,0$ freely chosen entries. Each free entry lies in ${\mathbb{F}}_2$, giving $16,8,4,4,2,1$ vector subspaces, respectively. The diagram fixes the zero entries required to make each pivot the first nonzero entry in its row and the only nonzero entry in its column. Different choices describe different row spaces.

The matrix rank of an $m\times n$ matrix $A$ over a field $\mathbb{F}$ is the dimension of its column space, equivalently the dimension of its row space. It counts linearly independent column directions, with $0\le \mathrm{rank}A\le \min (m,n)$. Counting nonzero matrix entries gives a different quantity: an all-ones matrix can have arbitrarily many nonzero matrix entries and still have matrix rank one.^[ref]

Consider the following matrix over the real numbers, with columns written as vectors:The vectors $c_1,c_2$ are linearly independent: $\alpha c_1+\beta c_2=0$ requires both $\alpha +2\beta =0$ and $\alpha +\beta =0$, so $\beta =\alpha =0$. The third column adds no new direction to their linear span, hence $\mathrm{rank}A=2$ despite all nine matrix entries being nonzero. The second row likewise repeats twice the first row.

The column space is a plane through the origin:Every output has second coordinate twice its first coordinate. Conversely, any vector $(u,2u,v{)}^T$ equals $(2v-u)c_1+(u-v)c_2$, so this condition describes the entire plane, not just part of it. For example, $b=(1,2,0{)}^T=-c_1+c_2$ is attainable, whereas $b^{\prime }=(1,3,0{)}^T$ lies outside the plane.

Elementary row operations expose the same count algebraically. Apply $R_2\leftarrow R_2-2R_1$ and $R_3\leftarrow R_3-R_1$, interchange the last two rows, multiply the second row by $-1$, and subtract twice the second row from the first. The resulting reduced row echelon form isThere are two pivot columns, so the matrix rank is two. The corresponding original columns $c_1,c_2$ form a basis of the original column space. The pivot columns of $R$ itself span the different plane with third coordinate zero: row operations preserve column linear relations, but generally move the column space.^[ref]

Solving the homogeneous linear system $Rx=0$ gives $x_1+x_3=0$ and $x_2+x_3=0$. Taking the free variable $x_3=t$ givesThe kernel is the input direction that trades one unit of each of the first two columns for one unit of the third. This trade leaves the output unchanged. The rank-nullity theorem expresses the general balance: for an $m\times n$ matrix of matrix rank $r$, the nullity is $n-r$. The column space describes reachable outputs; the kernel describes invisible changes to inputs.^[ref]

For the attainable output $b$, one solution is $x_0=(-1,1,0{)}^T$. Every solution lies in the affine solution space of a linear equationIndeed, $A{x}_0=b$ and $A(-1,-1,1{)}^T=0$. Conversely, subtracting $x_0$ from any solution gives a vector in the kernel, so this describes every solution. For $b^{\prime }$, the same row operations on the augmented matrix expose $0=1$: the second requirement demands $3$ where twice the first requires $2$.

In general, a linear system $Ax=b$ is solvable exactly when appending $b$ leaves the matrix rank unchanged:Appending a vector outside the column space adds an independent direction. When a solution $x_0$ exists, every solution is $x_0+\ker A$, because $A(x-x_0)=0$. Thus one count predicts both how many output directions are reachable and, through the rank-nullity theorem, how many independent input directions remain free.^[ref]

For $\alpha \ne 2$, $A^{\prime }=I_3$, whose row space is ${\mathbb{R}}^3=\mathrm{im}{T}_{\alpha }$. For $\alpha =2$, elementary row operations give the reduced row echelon formIts row space is $\{(u,v,w):u+v+w=0\}$, whereas the image of a linear map is $\{(u,v,w):u-v+w=0\}$. These differ: $(0,1,-1)$ belongs to the former but not the latter. Thus (A) is true exactly when $\alpha \ne 2$. Rows are being identified with vectors in ${\mathbb{R}}^3$ in this comparison.

For $\alpha \ne 2$, both reduced forms are $I_3$, so $A^{\prime \prime }=(A^{\prime }{)}^T$. At $\alpha =2$, the reduced column echelon form is the transpose of the reduced row echelon form of $A^T$, givingFor example, $C_2\mapsto -C_2$ followed by $C_3\mapsto C_3+C_1-C_2$, using the updated second column, produces the displayed $A^{\prime \prime }$ directly. Its third column is zero. The two matrices differ, so (C) is true exactly when $\alpha \ne 2$. Taking a transpose exchanges the kind of reduction, but also replaces the original $A$ by $A^T$; it does not generally identify the two reduced forms of $A$ itself.

Perform the elementary row operations $R_2\leftarrow R_2+2R_1$ and $R_3\leftarrow R_3-R_1$, then $R_2\leftarrow R_2/2$, $R_1\leftarrow R_1-R_2$, and finally $R_1\leftarrow R_1+R_3$, $R_2\leftarrow R_2-3R_3$:Consequently the reduced row echelon form is $I_3$. Applying the same operations to the augmented column $b=(b_1,b_2,b_3{)}^T$ givesThus every $b\in {\mathbb{R}}^3$ admits exactly one solution. This follows because the elementary row operations preserve the solution set of the augmented linear system, and the reduced coefficient matrix is the identity matrix.

Swap the first two rows, then perform $R_2\leftarrow R_2+R_1$ and $R_3\leftarrow R_3-2R_1$. These elementary row operations giveScale row 2 by $1/5$, subtract it from row 3, and finally subtract twice row 2 from row 1. The reduced row echelon form isElementary row operations preserve the row space. The two nonzero rows of $R$ are linearly independent, since their leading entries lie in different columns. Hence

The pivot columns of the reduced row echelon form are columns 1 and 3. Take those columns of the original matrix, since elementary row operations need not preserve the original column space:For an explicit spanning check, column 2 is $-2a_1$, column 4 is $-a_1+2a_3$, and column 5 is $3a_1-2a_3$. The first two coordinates of the displayed columns form a $2\times 2$ matrix of determinant $-5\ne 0$, proving their linear independence. They are therefore a basis of the column space.

The reduced row echelon form yieldsTake the free variables in a linear system to be $s=x_2$, $t=x_4$, $u=x_5$. ThenThusEach listed vector lies in the null space, and every solution has the displayed form. Their coordinates in positions 2, 4 and 5 prove linear independence. The dimension also follows from the rank-nullity theorem: $5-2=3$.

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.

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$.

Denote the five rows by $r_1,\dots ,r_5$. They satisfyThus $r_2,r_3,r_4$ span the row space. They are linearly independent: in a linear combination $\alpha r_2+\beta r_3+\gamma r_4=0$, coordinate 1 gives $\alpha =0$, coordinate 2 then gives $\beta =0$, and coordinate 4 gives $\gamma =0$. ThereforeAs an alternative basis, the nonzero rows of the reduced row echelon form are

Let $c_1,\dots ,c_4$ be the original columns. The first three are linearly independent: restricting them to rows 2, 3 and 4 gives the triangular matrixwhose determinant is one. Also $c_4=c_1-c_2+c_3$, so a basis for the column space isThese are columns of the original matrix. Taking columns of its reduced row echelon form would generally give the wrong column space.

The reduced row echelon form gives $x_1+x_4=0$, $x_2-x_4=0$, and $x_3+x_4=0$. With free parameter $x_4=t$,The displayed nonzero vector therefore forms a basis for the null space:This agrees with the rank-nullity theorem: there are four columns and matrix rank three.

The reduced column echelon form of a matrix $A$ is defined by taking its transpose, forming the reduced row echelon form, and transposing back:It is obtained from $A$ by elementary column operations. Its nonzero columns precede its zero columns, the topmost nonzero entry of each nonzero column is $1$, these leading entries move strictly downward as the column number increases, and each leading entry is the only nonzero entry in its row.

Every elementary column operation preserves the column space, because it and its inverse express each new column as a linear combination of the old columns. Thus the nonzero columns of the reduced form give a basis of the original column space. In contrast, elementary row operations preserve the row space. There is no general identity $\mathrm{rcef}(A)=\mathrm{rref}(A{)}^T$: the definition requires reducing $A^T$, not $A$.

For an invertible matrix of size $n$, both reduced forms are $I_n$. A singular example showing the distinction is

A row echelon form is in reduced row echelon form when every pivot element is one and is the only nonzero entry in its column.^[ref] This extra reduction displays each pivot unknown directly in terms of the free variables in a linear system. The zero matrix also satisfies the definition: it has no pivot elements.

Every matrix has exactly one reduced row echelon form under elementary row operations, with its size and column order held fixed.^[ref] Ordinary row echelon form is not unique: multiplying a nonzero row by two over the rational numbers keeps the staircase but changes the matrix. The reduced conditions remove that freedom.

For a fixed number of columns, each row space has a unique reduced matrix after zero rows are removed; at a fixed full size, the number of appended zero rows is also determined. Thus reduced row echelon form represents a vector subspace independently of the starting basis. This is the uniqueness used by Gaussian binomial coefficients to count vector subspaces over a finite field.

The fixed column order matters. Elementary column operations can change the row space, the kernel and the resulting reduced row echelon form. For instance, swapping the columns of $(12)$ over the rational numbers gives $(21)$, whose reduced row echelon form is $(11/2)$ instead of $(12)$. When solving a linear system, a column interchange also requires tracking the corresponding interchange of unknowns.

A matrix over a field $\mathbb{F}$ is in row echelon form when all zero rows follow the nonzero rows, each nonzero row's first nonzero entry lies strictly to the right of the preceding row's first nonzero entry, and all entries below each such leading entry vanish. These leading entries are its pivot elements. They need not be one, and entries above them need not vanish.^[ref]

The staircase turns a linear system into a sequence of simpler equations. For example,is in row echelon form, with pivot columns 1 and 2. Its second equation determines $x_2$ once $x_3$ is chosen; its first then determines $x_1$ by back substitution. It is not in reduced row echelon form, because the second pivot column contains a nonzero entry above its pivot element. Neither being square nor having a nonzero entry in every row is required.

Elementary row operations bring every matrix to row echelon form: choose a nonzero entry in the leftmost available nonzero column, interchange rows, clear entries below it, and repeat on the remaining rows and later columns. Skip columns with no remaining nonzero entry. Clearing above each pivot element and scaling it to one completes reduced row echelon form.^[ref]

The nonzero rows of an row echelon form are linearly independent: in a vanishing linear combination, inspecting the first pivot column forces the first coefficient to be zero, then the next forces the second, and so on. They give a basis of the original row space. The number of pivot elements is both the row rank and the column rank. To recover a basis of the original column space, select the corresponding original pivot columns; the reduced column vectors generally belong to a different column space.

Here the arithmetic is exact in the specified field. For floating-point arithmetic, deciding whether a computed entry counts as zero requires a numerical criterion; see Tiny-pivot roundoff in Gaussian elimination and condition number. An exact row echelon form classification alone does not settle numerical stability.

The row rank of a matrix is the dimension of the vector space spanned by its rows. Elementary row operations preserve this row space; multiplication on the right by an invertible matrix preserves all linear relations among the rows.

To see why row rank equals column rank, write a reduced row echelon form as $R=EA$, where $E$ is a product of elementary matrices and is an invertible matrix. Reversibility of the row operations gives equal row spaces for $R$ and $A$. Also $Rz=0$ if and only if $Az=0$, so the columns have exactly the same linear relations. If $R$ has $r$ nonzero rows, its pivot columns are the first $r$ standard basis vectors of ${\mathbb{F}}^m$ and span its column space. Its nonzero rows are linearly independent, since their matrix entries in the pivot positions form an identity matrix. Both dimensions therefore equal $r$, and both counts transfer back to $A$.

Work over the rational numbers, allowing unknowns in the real numbers when interpreting the geometry. Consider four equations in three unknowns:The third row of $A$ is the sum of its first two rows, and the fourth is their difference, second minus first. The same relations must hold on the right: consistency requires $\tau =1+4=5$ and $3=4-1$. The latter condition already holds. Gaussian elimination makes this compatibility test explicit while exposing the remaining freedom.

Apply the elementary row operations in this order, using each row's current value:then $R_3\leftarrow R_3-R_2$ and $R_4\leftarrow R_4-R_2$. The resulting augmented matrix is in row echelon form for every $\tau$:When $\tau \ne 5$, the third row has its pivot element in the augmented column. It says $0=\tau -5$, so the linear system has no solution. When $\tau =5$, that entire row vanishes and only two pivot elements remain. More equations than unknowns therefore do not force a unique solution: some equations may repeat information.

The final operation $R_1\leftarrow R_1-2R_2$ reduces the coefficient block toThe product of all six elementary matrices isDirect matrix multiplication verifies both displayed transformations. Its determinant is one, so this transformation is reversible. In particular, the third row of $E$ extracts the discrepancy between the third equation and the sum of the first two.

For $\tau =5$, $[R\mid Eb]$ is the reduced row echelon form of the full augmented matrix. For $\tau \ne 5$, only its coefficient block is reduced: scale the third row by $1/(\tau -5)$ and clear the entries above its augmented pivot element. The full reduced row echelon form is thenThe last column is part of the matrix when testing the echelon conditions. Calling $[R\mid Eb]$ fully reduced before clearing that column would miss this distinction.

Here is a short proof that uses only the row space. For a vector subspace $W\subseteq {\mathbb{F}}^n$, let $d_j$ be the dimension of its projection map onto the first $j$ coordinates, with $d_0=0$. In any reduced row echelon form with row space $W$, $d_j$ counts the pivot columns among those first $j$ columns: later-pivot rows project to zero, while earlier-pivot rows remain linearly independent. Thus the positions where $d_j-d_{j-1}=1$ determine all pivot positions from $W$ alone.

If those positions are $p_1,\dots ,p_r$, the map sending $w\in W$ to $(w_{p_1},\dots ,w_{p_r})$ is an isomorphism $W\to {\mathbb{F}}^r$: the reduced nonzero rows map to the standard basis. Its $i$th row is therefore the unique vector of $W$ with pivot-coordinate values equal to the $i$th standard basis vector. Any other reduced row echelon form with that row space has identical nonzero rows in identical order. At a fixed matrix size, the remaining rows must be zero. Together with existence by Gaussian elimination, this proves uniqueness.