6Understanding the relation between row rank and column rank

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 \R^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 $\R^n$ which are orthogonal to the vectors $r_1, \dots, r_m$. Formally

where $\langle y, x\rangle:=y^Tx$ is the standard scalar product of $x, y \in \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 \operatorname{im}(A)$, by definition we find an $x \in \R^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’$ with $Ax’ = 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’ \in R$ with $Ax’ = y$. We can do this with any element in the image of $A$. Hence we find for every element $b \in \operatorname{im}( A)$, an element $x \in R$ with $Ax = y$.

The picture suggests even more: Whenever we have another solution $x’’\in R$, then the difference $x’-x’’$ has to lie in the kernel of $A$. Since $x’-x’’$ 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’ = 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’ -x’’$ is in $R$, hence we can write it as a linear combination $x’ -x’’ = \lambda_1 r_1 + \dots + \lambda_m r_m$ of the rows $r_1,\ldots,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’-x’’ \in \ker(A)$ with $x’-x’’$ as the linear combination of the rows. That is

Hence we get $x’-x’’ = 0$ and thus $x’ = x’’$.

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 $\operatorname{im}( A)$. Formally, the restriction of $A$ to $R$

gives a bijection (a 1-1 map or correspondence) between $R$ and $\operatorname{im}(A)$. Furthermore, the correspondence preserves the structure of $R$ and $\operatorname{im}(A)$. This means that we can transport all calculations and relations between elements from $R$ to $\operatorname{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 $\operatorname{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 $\operatorname{im}(A)$ is the column rank. Hence the row rank equals the column rank.