Chapter 8: Rank

---

A linear subspace of a vector space is a subset of the vectors that is itself a linear space. To show that a subset of a linear space is a linear subspace one only has to check three things. This is captured by the following theorem.

---

This means that the solutions to a homogeneous system is a linear space.

This means that the set of linear combinations of a set of vectors is a linear space.

---

As we have seen in Section 5.5, a system of equations such as $\mx{A}\vc{x} = \vc{0}$ is called homogeneous. We will now show that the solutions to such systems reveal certain useful properties of $\mx{A}$. Let us start with an example. Assume we have a matrix

\begin{equation} \mx{A} = \begin{pmatrix} 2 & \hid{-}5 & \hid{-}3 \\ 4 & \hid{-}2 & \hid{-}1 \\ 2 & -3 & -2 \end{pmatrix}, \end{equation}

(8.1)

and that we want to solve for $\mx{A}\vc{x}=\vc{0}$, where $\vc{x} = (x_1, x_2, x_3)$ is a column vector. This is the same example as in Equation (5.34), i.e.,

\begin{equation} \begin{cases} \begin{array}{rrrl} 2 x_1 + 5 & \bs x_2 + 3 & \bs x_3 = 0, \\ 4 x_1 + 2 & \bs x_2 +\hid{3}& \bs x_3 = 0, \\ 2 x_1 - 3 & \bs x_2 - 2 & \bs x_3 = 0, \\ \end{array} \end{cases} \end{equation}

(8.2)

After some work with Gaussian elimination, we arrived at

\begin{equation} \begin{cases} \begin{array}{rrrl} 2 x_1 + 5 & \bs x_2 + 3 & \bs x_3 = 0, \\ 8 & \bs x_2 + 5 & \bs x_3 = 0, \\ & & \bs 0 = 0. \\ \end{array} \end{cases} \end{equation}

(8.3)

The next step is then to set $x_3=t$, which means that $x_2=-\frac{5}{8}t$, and finally, $x_1=\frac{1}{16}t$, i.e.,

\begin{equation} \vc{x}(t) = \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} \frac{1}{16}t \\ -\frac{5}{8}t \\ t \end{pmatrix} \end{equation}

(8.4)

As can be seen, the solution is a line which is dependent only on one varying parameter $t$. Sometimes the solution is denoted by $\vc{x}_\mathrm{h}$ to indicate that it is a solution to the homogeneous system $\mx{A}\vc{x}=\vc{0}$. This entire set of solutions is called the null space of $\mx{A}$ and in this particular case, the dimension of the null space is 1, since it only depends on one parameter, namely $t$. We also use the term null vector for $(1/16, -5/8, 1)$. Next, this is formalized into a definition.

By definition, the null space must be a subspace of $\R^n$, that is, $\nullity(\mx{A}) \leq n$. It is a linear subspace, (see Example 8.2). The dimension of this subspace is important and has its own definition.

Since the null space is a subspace of $\R^n$, we have $\nullity(\mx{A}) \leq n$. But how many dimensions lower is the null space? This is captured loosely by the number of constraints in $\mx{A}\vc{x}=\vc{0}$, however, here we must be careful. Just because there are $m$ equations in $\mx{A}\vc{x}=\vc{0}$ it does not automatically mean that $\nullity(\mx{A}) = n - m$. How many constraints there are in $\mx{A}$ is precisely what is captured by the concept of rank. What we are later going to show is that $\nullity(\mx{A}) = n - r$, i.e., that the dimension is lowered by $r$ (i.e., the rank of $\mx{A}$) using the constraints in $\mx{A}\vc{x}=\vc{0}$.

Using Gaussian elimination, we obtain a basis for the null space and thereby also the dimension of the null space. It is the number of independent parameters in the solution to $\mx{A}\vc{x}=\vc{0}$ that dictates the dimension of the null space.

---

For an $m\times n$ matrix $\mx{A}$, recall from Definition 6.2 how the rows $\vc{a}_{i,}^\T$, where $i\in{1,\dots,m}$, and the columns, $\vc{a}_{,j}$, are accessed, i.e.,

\begin{equation} \mx{A} = \bigl(\vc{a}_{,1} \,\,\, \vc{a}_{,2} \,\,\,\dots\,\,\, \vc{a}_{,n}\bigr) = \left( \begin{array}{c} \vc{a}_{1,}^\T\\ \vc{a}_{2,}^\T\\ \vdots \\ \vc{a}_{m,}^\T\\ \end{array} \right). \end{equation}

(8.10)

In addition, we repeat that the notation of column and row vectors in this book, i.e., all vectors are column vectors by default and if you want to use a row vector, you take a column vector, $\vc{x}$, and you transpose it to get a row vector, $\vc{x}^\T$. Also, $(x_1,x_2,x_3)$ is also a column vector (note the commas), while $(x_1 \spc x_2 \spc x_3)$ is a row vector, which is described below Definition 2.5.

Now that the null space is known, two related concepts, namely the column space and the row space, can be introduced.

Now, we note that matrix-vector multiplication, $\mx{A}\vc{x}$, can be expressed as

\begin{equation} \mx{A}\vc{x}= \left(\vc{a}_{,1}\,\,\, \vc{a}_{,2}\,\,\, \dots\,\,\, \vc{a}_{,n}\right)\vc{x} = x_1\vc{a}_{,1} + x_2\vc{a}_{,2} + \dots +x_n\vc{a}_{,n}, \end{equation}

(8.11)

that is, as a linear combination (see Definition 5.1) of the column vectors of $\mx{A}$. So, the column space is therefore all the vectors that can be created by taking a constant times the first column vector plus another constant times the second column vector and so on. Note that the column space is a subspace of $\R^m$ by definition, since the number of elements in all column vectors of $\mx{A}$ is $m$.

Similar to the column space, we can write this as a vector-matrix multiplication, but this time we use a row vector $\vc{x}^\T$ with $m$ elements and multiply from the right, i.e.,

\begin{equation} \vc{x}^\T\mx{A}= \vc{x}^\T \left(\begin{array}{c} \vc{a}_{1,}^\T\\ \vc{a}_{2,}^\T\\ \vdots \\\vc{a}_{m,}^T \end{array}\right) = \left(\begin{array}{c} x_1\ \ x_2\ \ \dots\ \ x_m \end{array}\right) \left(\begin{array}{c} \vc{a}_{1,}^\T\\ \vc{a}_{2,}^\T\\ \vdots \\\vc{a}_{m,}^T \end{array}\right) = x_1\vc{a}_{1,}^\T + x_2 \vc{a}_{2,}^\T + \dots + x_m \vc{a}_{m,}^\T. \end{equation}

(8.12)

So, this is also a linear combination (see Definition 5.1), but this time using the row vectors of $\mx{A}$. So, the row space is therefore all the vectors that can be created by taking a constant times the first row vector plus another constant times the second row vector and so on. Note that the row space is a subspace of $\R^n$ by definition, since the number of elements in all row vectors of $\mx{A}$ is $n$.

In the following, we will go through a number of steps that will lead up to a point where we easily can obtain the column/row vectors of the column/row space of a matrix. We start with the following theorem.

---

Note that it is important that Theorem 8.2 only works for the row space and not for the column space.

In the following, it will be useful to have a specific term for the matrix that is obtained after Gaussian elimination. This is described in the following definition.

Note that a matrix on row echelon form can be obtained by applying Gaussian elimination until no more reductions can be made. This gives a triangular-like structure for matrices on row echelon form, e.g.,

\begin{equation} \left( \begin{array}{rrrrr} \underline{2} & 0 & 1 & -2 & 1 \\ 0 & \underline{1} & 4 & 2 & 1 \\ 0 & 0 & 0 & \underline{1} & 2 \\ 0 & 0 & 0 & 0 & 0 \\ \end{array} \right). \end{equation}

(8.21)

Therefore, this type of matrices are sometimes said to be a "staircase equivalent" matrix of $\mx{A}$. The leading non-zero coefficients, underlined in the previous equation, are important. These elements of the matrix are often called pivot element. Some texts require that these leading non-zero coefficients are made to ones. This can be achieved by dividing the entire row by the leading non-zero coefficient. However, we do not require that here.

Next, we present a theorem that says how the row space basis vectors can be found and how the dimension of the row space is found.

---

Note that the number of basis vector of the row/column space is the row/column rank.

Next, we will show that the dimension of the row space (i.e., the row rank) is the same as the dimension of the column space (i.e., the column rank). After the following theorem, we will give an example of how the row and column space basis can be found.

---

Hereafter, we do not need to distinguish between $\rowrank(\mx{A})$ and $\colrank(\mx{A})$, and instead, we refer to it as just rank, denoted $\rank(\mx{A})$. Note also that the theorem above can be stated as $\rank(\mx{A})= \rank(\mx{A}^{\T})$. This means that if you want to find the column space vectors of a matrix $\mx{A}$, then you can transpose it to $\mx{A}^{\T}$ and then use Theorem 8.3. Next, we show an example of how the column space basis can be found.

---

Next, we present a theorem that provides an upper bound of the rank of a matrix-matrix product.

---

---

Now, we know that $\vc{x}_h$ is in the null space of $\mx{A}$ and that $\vc{y}$ must be in the column space of $\mx{A}$, otherwise it is not a solution to $\mx{A}\vc{x}=\vc{y}$. In Interactive Illustration 8.3, we show how these two solutions may interact. The dimension theorem below is very handy since if you know either the dimension of the null space or the rank then you can find the other one of these (assuming you know the number of rows in the matrix, which is a reasonable assumption).

---

Recall that $\nullity(\mx{A})$ dictates the number of parameters needed to describe the solution to the homogeneous system $\mx{A}\vc{x}=\vc{0}$ and that $\rank(\mx{A})$ is the number of linearly independent right-hand sides $\vc{y}$ when $\mx{A}\vc{x}=\vc{y}$ has a solution. Finally, the sum of these two numbers is $n$, i.e., the number of columns of $\mx{A}$.

Note that $\mx{A}$ can be thought of as a transform or linear mapping (see Chapter 9), and that $n$ is the dimension of the domain of $\mx{A}$. Given this, we can think of $\rank(\mx{A})$ as the number of dimensions that "survive" after applying $\mx{A}$ and $\nullity(\mx{A})$ is the number of dimensions that are "collapsed" by $\mx{A}$.

---

In Chapter 7, different ways to compute the determinant of a square matrix were presented. Using minors (see Definition 7.8), one can also find the rank of a matrix, as the subsequent theorem describes.

---

As a consequence of Theorem 8.9 and Theorem 7.8, where the latter says that the inverse of a matrix only is defined if its determinant is non-zero, we see that if a square $n\times n$ matrix $\mx{A}$ is to be invertible, then we must have $\rank(\mx{A})=n$.

---

In the last example, we found that a matrix $\mathbf{B}$, which can be formed from measurements, is related to the parameters that we seek by $\mathbf{B} = \mathbf{R}^\T \mathbf{S}$. How can we calculate $\mathbf{R}$ and $\mathbf{S}$ from $\mathbf{B}$? In other words, how can we factorize the matrix $\mathbf{B}$ and write it as a product of two factors $\mathbf{R}$ and $\mathbf{S}$? This is part of the topic of factorization and these are useful tools in many applications. However, this is unfortunately out of scope of this book.