Matrix rank ($\mathrm{rank}A$)

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 a matrix of matrix rank $r$, choose an ordered basis of its column space as the columns of $B$. Express every column of $A$ in that basis and put its coordinates in $C$. Then $A=BC$, $B$ has full column rank and $C$ has full row rank. Choosing independent original columns makes the corresponding columns of $C$ the standard basis vectors, directly proving its rank.

The basis choice is not unique: for any invertible $r\times r$ matrix $S$, the factors $BS$ and $S^{-1}C$ have the same product. Once $B$ is fixed, its coordinate matrix is unique. For rank zero, the empty factors of the displayed shapes represent the zero matrix.

Let $A$ be a real $n\times n$ matrix of matrix rank $n-m$, and let the columns of $L,R$ be bases of $\ker A^{\top }$ and $\ker A$, respectively. Then $B=L{R}^{\top }$ has matrix rank $m$, $A^{\top }B=A{B}^{\top }=0$, and $M=A+B$ is an invertible matrix.

Proof. Since $R$ has independent columns, its Gram matrix $R^{\top }R$ is invertible, and $R^{\top }$ maps onto ${\mathbb{R}}^m$. Thus $\mathrm{im}B=\mathrm{im}L=\ker A^{\top }$ and $\mathrm{rank}B=m$. The basis conditions give the two zero products. In particular,If $M{M}^{\top }x=0$, taking its dot product with $x$ gives $\Vert A^{\top }x{\Vert }^2+\Vert B^{\top }x{\Vert }^2=0$. Hence $x\in \ker A^{\top }=\mathrm{im}B$ and simultaneously $x\in \ker B^{\top }=(\mathrm{im}B{)}^{\perp }$. Therefore $x=0$, and $M$ is invertible. The case $m=0$ is immediate.

For a common eigenvector of $A{A}^{\top }$ and $B{B}^{\top }$, the two eigenvalues have zero product and positive sum: exactly one is zero. Thus the added term fills the missing orthogonal output directions without interfering with the original ones.

For composable linear maps, $\mathrm{im}(AB)=A(\mathrm{im}B)$ lies in $\mathrm{im}A$ and has dimension at most that of $\mathrm{im}B$. This proves the bound on the rank of a matrix product. When $A$ is $m\times p$, $B$ is $p\times n$, and $m,n\ge p$, the bound $p$ is attained by $A=\left(\genfrac{}{}{0ex}{}{I_p}{0}\right)$ and $B=(I_{p}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 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]

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

Two rectangular matrices are related by invertible left and right multiplication exactly when their ranks agree. The rank-$r$ orbit in ${\mathrm{Mat}}_{b\times a}(k)$ has dimension $r(a+b-r)$: choose its image in a Grassmannian, then a surjective map to that image. These are the representation orbits of the one-arrow quiver.

The image of the linear map $A+B$ is contained in the sum of the images of $A$ and $B$. Since the dimension of a vector space of this sum is at most the sum of their dimensions, matrix rank is subadditive. Iteration shows that a sum of $r$ matrices of matrix rank at most one has matrix rank at most $r$, over any field.

An $m\times n$ matrix has full column rank when its matrix rank is $n$, equivalently when its columns are linearly independent vectors. This requires $n\le m$. Its kernel is $\{0\}$, so the represented linear map is injective and every solvable linear system $Ax=b$ has a unique solution. It need not reach every output.^[ref]

For example,has full column rank two, but its column space is the plane $b_3=b_1+b_2$ in ${\mathbb{R}}^3$. An attainable output fixes the input uniquely as $(b_1,b_2{)}^T$; an output outside this plane has no preimage.

An $m\times n$ matrix has full row rank when its matrix rank is $m$, equivalently when its rows are linearly independent vectors. This requires $m\le n$. Its column space is all of ${\mathbb{F}}^m$, so the represented linear map is surjective and every linear system $Ax=b$ is solvable. If $n>m$, its nullity is $n-m>0$, so solutions are not unique.^[ref]

For example, the matrix transpose of the matrix in full column rank isIt has full row rank two. Every output $(p,q{)}^T$ has solutions $(p-t,q-t,t{)}^T$, with $t\in \mathbb{R}$. A square matrix of size $n$ has full row rank and full column rank together exactly when its matrix rank is $n$; then it is an invertible matrix. A nonsquare matrix cannot have both properties, and has no two-sided inverse: such an inverse would make its linear map a linear isomorphism between vector spaces of different dimensions.