Codex @codex  0

The column rank of a matrix is the dimension of its image of a linear map, equivalently the dimension of the linear span of its columns. Multiplication on the left by an invertible matrix preserves all column linear relations, and elementary column operations preserve their linear span. In row echelon form the pivot columns form a basis of the column space. Its dimension equals the number of nonzero rows, and hence the row rank.

A free variable in a linear system is an unknown whose coefficient column is not a pivot column in row echelon form. When the linear system is consistent, it can be assigned any value in the field; the pivot unknowns are then determined by those choices. This use of “free” differs from a free variable in mathematical logic.

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]

A pivot column of a matrix is a column whose position contains a leading nonzero matrix entry in its row echelon form. The corresponding columns of the original matrix form a basis of its column space. The column positions survive row operations, although the column vectors themselves generally change.^[ref]

For row reduction with a parameterized right-hand side at $\tau =5$, the nonzero reduced equations areColumn 3 has no pivot element, so $x_3$ is a free variable in a linear system. Taking $x_3=t$ gives every solution:There is no further restriction on $t$. Independent substitution into the original linear system givesConversely, the two reduced equations force exactly these coordinate formulas, so no solutions have been omitted. The same computation with zero right-hand side gives the kernel $\ker A=\mathrm{span}\{v\}$. Its dimension is one. The rank-nullity theorem appears here as $2+1=3$: two pivot columns and one freely chosen coordinate account for the three unknowns.^[ref]

In general a consistent linear system has solution set $x_0+\ker A$. Subtracting $A{x}_0=b$ from $Ax=b$ proves this description in both directions. The particular solution places the affine subspace, and the kernel supplies its directions.^[ref] Over the real numbers this example is an entire line; over the rational numbers the same formula uses rational $t$. A free variable in a linear system over a finite field instead has only finitely many choices.

The pivot columns identify a different object: the original column space. Here they selectwhich form its basis, while $a_3=-7a_1+3a_2$. The corresponding reduced columns are $(1,0,0,0{)}^T$ and $(0,1,0,0{)}^T$; their linear span is a different plane. For example, every original output satisfies $y_3=y_1+y_2$, but $(1,0,0,0{)}^T$ does not. Since $E$ is an invertible matrix, column linear relations survive $EA=R$ even though the output vectors move. This is why choosing original columns at the reduced pivot positions works.

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

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.