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 $mm$ equations in the variables  $x_1,\dots ,x_{n}x\_1,\; \backslash dots,\; x\_n$. The $a_{ij}a\_\{ij\}$ are coefficients in $\mathbb{R}\backslash R$.

For which values $y_1,\dots ,y_m\in \mathbb{R}y\_1,\; \backslash dots,\; y\_m\; \backslash in\; \backslash R$ do these equations have a solution $(x_1,\dots ,x_n)(x\_1,\; \backslash 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=0y\_1\; =\; 0$ and $y_2=1y\_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\mathrm{\ne }{y}_{2}2y\_1\backslash neq\; y\_2$. On the other hand it has a solution for $y_1=1y\_1\; =\; 1$ and $y_2=2y\_2=2$ or more generally for $2y_1=y_{2}2y\_1=y\_2$, for example $x_1=y_{1}x\_1\; =\; y\_1$ and $x_2=0x\_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}x\_1,\; \backslash dots,\; x\_n$ appear in every row. To ease notation, we can use the matrix vector multiplication: We assemble the coefficients $a_{ij}a\_\{ij\}$ into an $(m\times n)(m\backslash times\; n)$-matrix and write the $x_{i}x\_i$’s and $y_{j}y\_j$’s as vectors.

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

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 {\mathbb{R}}^{2}y=(y\_1,\; y\_2)^T\backslash in\backslash R^2$ if and only if $2y_1=y_{2}2\; y\_1\; =\; y\_2$.

We can plot this to see that the $yy$’s which have a solution form a line in ${\mathbb{R}}^2\backslash R^2$:

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

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

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

In particular, we can speak of the dimension of $\mathrm{im}(A)\backslash operatorname\{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)\backslash operatorname\{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=yAx=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 \mathbb{R}x\_1,x\_2,x\_3\backslash in\backslash R$:

System 1: Consider

It has the unique solution $x_1=1,x_2=2,x_3=-10x\_1=1,\; x\_2=2,\; x\_3\; =\; -10$.

System 2: Consider

For each $x_1\in \mathbb{R}x\_1\; \backslash in\; \backslash R$ it has the solution $x_2=5-3x_1,x_3=-21+11x_{1}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}x\_2=5-3x\_1$ and get a solution for arbitrary $x_1,x_3\in \mathbb{R}x\_1,\; x\_3\backslash in\backslash R$.

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

• System 1: unique solution; represents a point in ${\mathbb{R}}^3\backslash R^3$

• System 2: solution for any $x_{1}x\_1$; solutions represent a straight line in ${\mathbb{R}}^3\backslash R^3$

• System 3: solution for any choice of $x_{1}x\_1$ and $x_{3}x\_3$; represents a plane in ${\mathbb{R}}^3\backslash R^3$

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

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

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

The bigger the kernel the more solutions exist. If $\ker (A)=0\backslash 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 {\mathbb{R}}^{n}x\; \backslash in\; \backslash R^n$ is in the kernel if and only if $Ax=0Ax\; =\; 0$. Explicitly this is the case if

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

We thus have the description that the kernel of A is given by all vectors in ${\mathbb{R}}^n\backslash R^n$ which are orthogonal to the vectors $r_1,\dots ,r_{m}r\_1,\; \backslash dots,\; r\_m$. Formally

where $⟨y,x⟩:=y^{T}x\backslash langle\; y,\; x\backslash rangle:=y^Tx$ is the standard scalar product of $x,y\in {\mathbb{R}}^{n}x,\; y\; \backslash in\; \backslash R^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)y\; \backslash in\; \backslash operatorname\{im\}(A)$, by definition we find an $x\in {\mathbb{R}}^{2}x\; \backslash in\; \backslash R^2$ such that $Ax=yAx\; =\; 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)\backslash ker(A)$ to $xx$ and obtain a new solution $x\text{’}x’$ with $Ax\text{’}=yAx’\; =\; y$: If we have $Ax=yAx\; =\; y$ and $z\in \ker (A)z\; \backslash in\; \backslash ker(A)$, then $A(x+z)=Ax+Az=y+0=yA(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 $xx$ into the span of the rows $RR$ and get $x\text{’}\in Rx’\; \backslash in\; R$ with $Ax\text{’}=yAx’\; =\; y$. We can do this with any element in the image of $AA$. Hence we find for every element $b\in \mathrm{im}(A)b\; \backslash in\; \backslash operatorname\{im\}(\; A)$, an element $x\in Rx\; \backslash in\; R$ with $Ax=yAx\; =\; y$.

The picture suggests even more: Whenever we have another solution $x\text{’’}\in Rx’’\backslash in\; R$, then the difference $x\text{’}-x\text{’’}x’-x’’$ has to lie in the kernel of $AA$. Since $x\text{’}-x\text{’’}x’-x’’$ is also in $RR$, it has to lie in the intersection of the kernel and $RR$. By the picture it has to be zero, which implies $x\text{’}=x\text{’’}x’\; =\; x’’$. 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{’’}x’\; -x’’$ is in $RR$, hence we can write it as a linear combination $x\text{’}-x\text{’’}={\lambda }_1{r}_1+\cdots +{\lambda }_m{r}_{m}x’\; -x’’\; =\; \backslash lambda\_1\; r\_1\; +\; \backslash dots\; +\; \backslash lambda\_m\; r\_m$ of the rows $r_1,\dots ,r_{m}r\_1,\backslash ldots,r\_m$ of $AA$. Next we can exploit that elements in the kernel are orthogonal to the rows, by computing the scalar product of $x\text{’}-x\text{’’}\in \ker (A)x’-x’’\; \backslash in\; \backslash ker(A)$ with $x\text{’}-x\text{’’}x’-x’’$ as the linear combination of the rows. That is

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

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

gives a bijection (a 1-1 map or correspondence) between $RR$ and $\mathrm{im}(A)\backslash operatorname\{im\}(A)$. Furthermore, the correspondence preserves the structure of $RR$ and $\mathrm{im}(A)\backslash operatorname\{im\}(A)$. This means that we can transport all calculations and relations between elements from $RR$ to $\mathrm{im}(A)\backslash operatorname\{im\}(A)$ and back using the above restriction of $AA$ to $RR$ (and its inverse). Hence both spaces have the same properties. In particular $RR$ and $\mathrm{im}(A)\backslash operatorname\{im\}(A)$, i.e. the span of the rows and the span of the columns, have the same dimension. The dimension of $RR$ is the row rank and the dimension of $\mathrm{im}(A)\backslash operatorname\{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 ${\mathbb{R}}^n\backslash R^n$ spanned by its rows and the subspace of ${\mathbb{R}}^m\backslash R^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 ${\mathbb{R}}^n\backslash R^n$, since our argument relies on the standard scalar product in ${\mathbb{R}}^n\backslash R^n$: $⟨x,y⟩=x^{T}y\backslash langle\; x,y\backslash rangle\; =x^Ty$. In ${\mathbb{C}}^n\backslash mathbb\{C\}^n$ the mapping $⟨x,y⟩=x^{T}y\backslash langle\; x,y\backslash rangle\; =x^Ty$ is not a scalar product, since in ${\mathbb{C}}^2\backslash mathbb\{C\}^2$

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

Hence, even over $\mathbb{C}\backslash mathbb\; C$, the kernel of a matrix is in general not the orthogonal complement of the rows.

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