Why does row rank equal column rank?

Everyone who studies elementary linear algebra encounters the concepts of row rank and column rank of a matrix at some point. Interestingly, it turns out that they are always equal. Although this is not difficult to prove, it often remains somewhat of a mystery: Why is this true? The aim of this course is to present a surprisingly ostensive answer to this question for matrices over the real numbers.

Everyone can follow the explanations, including those who have never heard of the rank of a matrix, since we introduce all needed concepts on an intuitive level. For all who are already familiar with the terminology, we also include formal proofs based on the intuitive arguments.

Suppose we have a linear system of equations:

It consists of $m$ equations in the variables  $x_1,\dots ,x_n$. The $a_{ij}$ are coefficients in $ℝ$.

For which values $y_1,\dots ,y_m\in ℝ$ do these equations have a solution $(x_1,\dots ,x_n)$? This question certainly depends on the number of equations and their relationship to each other.

Example: The system

does not always have a solution. For instance, it has no solution for $y_1=0$ and $y_2=1$, since the second equation is two times the first equation. More generally the same reasoning gives that there does not exist a solution whenever $2y_1\ne y_2$. On the other hand it has a solution for $y_1=1$ and $y_2=2$ or more generally for $2y_1=y_2$, for example $x_1=y_1$ and $x_2=0$.

Writing a linear system of equations the way we wrote it above carries a lot of redundancy. For example the variables $x_1,\dots ,x_n$ appear in every row. To ease notation, we can use the matrix vector multiplication: We assemble the coefficients $a_{ij}$ into an $(m\times n)$-matrix and write the $x_i$’s and $y_j$’s as vectors.

By definition of matrix vector multiplication, we have $y_i=a_{i1}{x}_1+\dots a_{in}{x}_n$ for each $i\in \{1,\dots ,m\}$.

Our example turns into the following matrix vector multiplication

In the previous example we saw that the linear equation

has a solution $y=(y_1,y_2{)}^T\in {ℝ}^2$ if and only if $2y_1=y_2$.

We can plot this to see that the $y$’s which have a solution form a line in ${ℝ}^2$:

We give these $y$’s, for which the linear system has a solution, a name: the image of the matrix. That is, for an $(m\times n)$-matrix $A$ we define

If $y=(y_1,y_2{)}^T$ and $y\text{’}=(y_1\text{’},y_2\text{’}{)}^T$ are in the image of the coefficient matrix of the above linear system, then their sum $y+y\text{’}$ is again in the image, as well as any multiple $\alpha \cdot y=(\alpha y_1,\alpha y_2{)}^T$ with $\alpha \in ℝ$.

This holds for the image of any matrix. We say that the image of a matrix is a subspace of ${ℝ}^m$. It contains the columns of the matrix, since the $i$-th column is $A{e}_i$ where $e_i=(0,\dots ,1,\dots ,0{)}^T$ with the $1$ in the $i$-th position. Moreover, one can show that it is the smallest subspace containing the columns. We say that $\mathrm{im}(A)$ is spanned by the columns of A.

In particular, we can speak of the dimension of $\mathrm{im}(A)$. Intuitively this is the number of different “directions” in the space. For example a single point is zero-dimensional, a line is one-dimensional, a plane is two-dimensional, and a space looking like reality is three-dimensional. In our example, $\mathrm{im}(A)$ is one-dimensional.

The dimension of the image of a matrix has a special name: The column rank of the matrix.

We have defined the column rank as the dimension of the space generated by the columns of the matrix. Similarly we can look at the dimension of the space spanned by the rows of a matrix. This number is called the row rank.

We found two numerical values associated to a matrix: Its row rank and its column rank. Now we want to understand how the row rank and the column rank relate to each other.

The question is the following: How do the rows of the matrix (i.e. the different equations of the linear system) affect the dimension of the image of the matrix (i.e. the “size” of the space of vectors y for which the system $Ax=y$ is solvable)? Put differently, can the dimension of the image be determined directly by the relations between the rows of the matrix? And if so, why?

Let’s look at the following linear systems of equations in three variables $x_1,x_2,x_3\in ℝ$:

System 1: Consider

It has the unique solution $x_1=1,x_2=2,x_3=-10$.

System 2: Consider

For each $x_1\in ℝ$ it has the solution $x_2=5-3x_1,x_3=-21+11x_1$. Hence there are infinitely many solutions.

System 3: Consider

Here we can choose $x_2=5-3x_1$ and get a solution for arbitrary $x_1,x_3\in ℝ$.

If there are more redundant rows then the linear system of equations has more solutions.

• System 1: unique solution; represents a point in ${ℝ}^3$

• System 2: solution for any $x_1$; solutions represent a straight line in ${ℝ}^3$

• System 3: solution for any choice of $x_1$ and $x_3$; represents a plane in ${ℝ}^3$

If we have more than one solution, what do they have in common?

Let $x\text{’}$ and $x\text{’}\text{’}$ be two solutions of a linear system of equations $Ax=y$. What is the difference between the two solutions $x\text{’}$ and $x\text{’}\text{’}$? We apply $A$ to the difference $x\text{’}-x\text{’}\text{’}$: $A(x\text{’}-x\text{’}\text{’})=Ax\text{’}-Ax\text{’}\text{’}=y-y=0$.

The more solutions to the system $Ax=y$ there are, the more vectors we can find that get mapped to zero. Hence the “amount” of x with $Ax=0$ is a measure for the uniqueness of the solution $Ax=y$ for any $y$. For that reason, we give it a name: The kernel of $A$. We write it as

The bigger the kernel the more solutions exist. If $\ker (A)=0$ the solution is unique.

We have seen that the kernel of a matrix is a measure for the uniqueness of solutions. But how to compute this kernel? A vector $x\in {ℝ}^n$ is in the kernel if and only if $Ax=0$. Explicitly this is the case if

for all $i\in \{1,\dots ,m\}$. This is the standard scalar product of the vector $x$ with the $i$-th row vector

We thus have the description that the kernel of A is given by all vectors in ${ℝ}^n$ which are orthogonal to the vectors $r_1,\dots ,r_m$. Formally

where $⟨y,x⟩:=y^{T}x$ is the standard scalar product of $x,y\in {ℝ}^n$.

Consider the linear system of equations

that we encountered before. It is represented by the matrix

with kernel

If we draw the kernel and the span of the rows

we see that they are indeed orthogonal to each other:

If we have $y\in \mathrm{im}(A)$, by definition we find an $x\in {ℝ}^2$ such that $Ax=y$. In the last section we defined the kernel and found that the difference of solutions is contained in the kernel. On the other hand, we can add any element from $\ker (A)$ to $x$ and obtain a new solution $x\text{’}$ with $Ax\text{’}=y$: If we have $Ax=y$ and $z\in \ker (A)$, then $A(x+z)=Ax+Az=y+0=y$. In the picture this corresponds to moving the point x parallel to the kernel.

If we pick the right element in the kernel, we can move $x$ into the span of the rows $R$ and get $x\text{’}\in R$ with $Ax\text{’}=y$. We can do this with any element in the image of $A$. Hence we find for every element $b\in \mathrm{im}(A)$, an element $x\in R$ with $Ax=y$.

The picture suggests even more: Whenever we have another solution $x\text{’}\text{’}\in R$, then the difference $x\text{’}-x\text{’}\text{’}$ has to lie in the kernel of $A$. Since $x\text{’}-x\text{’}\text{’}$ is also in $R$, it has to lie in the intersection of the kernel and $R$. By the picture it has to be zero, which implies $x\text{’}=x\text{’}\text{’}$. If we look closely, we find a familiar reason for this: The kernel is orthogonal to the span of the rows.

Formally we can express this observation as follows. We know that $x\text{’}-x\text{’}\text{’}$ is in $R$, hence we can write it as a linear combination $x\text{’}-x\text{’}\text{’}={\lambda }_1{r}_1+\cdots +{\lambda }_m{r}_m$ of the rows $r_1,\dots ,r_m$ of $A$. Next we can exploit that elements in the kernel are orthogonal to the rows, by computing the scalar product of $x\text{’}-x\text{’}\text{’}\in \ker (A)$ with $x\text{’}-x\text{’}\text{’}$ as the linear combination of the rows. That is

Hence we get $x\text{’}-x\text{’}\text{’}=0$ and thus $x\text{’}=x\text{’}\text{’}$.

All together, we showed that given some $y$ in the image of $A$, i.e. some linear combination of the columns, there exists a unique solution $x$ with $Ax=y$, such that $x$ is a linear combination of the rows. So, the matrix $A$ yields a 1-1-correspondence between the space of linear combinations of the rows $R$ and the span of the columns $\mathrm{im}(A)$. Formally, the restriction of $A$ to $R$

gives a bijection (a 1-1 map or correspondence) between $R$ and $\mathrm{im}(A)$. Furthermore, the correspondence preserves the structure of $R$ and $\mathrm{im}(A)$. This means that we can transport all calculations and relations between elements from $R$ to $\mathrm{im}(A)$ and back using the above restriction of $A$ to $R$ (and its inverse). Hence both spaces have the same properties. In particular $R$ and $\mathrm{im}(A)$, i.e. the span of the rows and the span of the columns, have the same dimension. The dimension of $R$ is the row rank and the dimension of $\mathrm{im}(A)$ is the column rank. Hence the row rank equals the column rank.

We have seen that there is a 1-1 correspondence, induced by the matrix, between the subspace of ${ℝ}^n$ spanned by its rows and the subspace of ${ℝ}^m$ spanned by its columns (that is, the image of the matrix). This means that the dimensions of these two subspaces are equal. The dimension of the space spanned by the rows is the row rank and the dimension of the space spanned by the columns is the column rank. We have seen before why they are equal. Because of that one simply speaks of the “rank” of the matrix.

Our derivation of the equality of row rank and column rank works only in ${ℝ}^n$, since our argument relies on the standard scalar product in ${ℝ}^n$: $⟨x,y⟩=x^{T}y$. In ${ℂ}^n$ the mapping $⟨x,y⟩=x^{T}y$ is not a scalar product, since in ${ℂ}^2$

Note that this means that the vector $(1,i{)}^T$ is in the kernel of the matrix

Hence, even over $ℂ$, the kernel of a matrix is in general not the orthogonal complement of the rows.

If $x^{T}y$ was a sensible notion of a scalar product on ${ℂ}^2$, this would mean that the nonzero vector $(1,i{)}^T$ is orthogonal to itself. Intuitively this does not make sense.