4.6 Rank
For this chapter, all vector spaces are finite unless stated explicitly.
This chapter in the textbook introduces the concept of row spaces and characteristics of it. Early in this note, Chapter 2.8 Subspaces explores some of its interesting properties, one of them being the following proposition.
NoteProof (Proof of Proposition 1)
Proof (Proof of Proposition 1). Suppose \(E\) is a elementary matrix, and \(A\sim EA\).
Then each row of \(EA\) is a linear combination of the rows in \(A\). Thus, each vector in \(\opn{Row}(EA)\) is automatically in \(\opn{Row}A\).
Conversely, \(EA \sim E^{-1}(EA)\), and the same holds. Each vector in \(\opn{Row}(E^{-1}(EA))=\opn{Row}A\) is in \(\opn{Row}(EA)\), so \(\opn{Row}A = \opn{Row}(EA)\).
The textbook provides an example to visualize the relation between \(\opn{Nul} A\) and \(\opn{Row} A\) and between \(\opn{Nul} A^T\) and \(\opn{Col} A\).
In the below two examples, \(A = \displaystyle\mat{3 & 0 & -1 \\ 3 & 0 & -1 \\ 4 & 0 & 5}\).
Tip\(\opn{Nul} A\) and \(\opn{Row} A\)
Tip\(\opn{Nul} A^T\) and \(\opn{Col} A\)
TipRemark
Remark. We observe that two spaces in each example are perpendicular to each other. In fact, this can be generalized to all matrices of higher dimensions.
NoteProof
Proof. For all \(\bf{v} \in \opn{Nul} A\), \(\displaystyle{A\bf{v}=\mat{\opn{row}_1(A) \\ \opn{row}_2(A) \\ \vdots \\ \opn{row}_m(A)}\bf{v}=\bf{0}}\). Thus, for all \(1\leq j\leq m\), \(\opn{row}_j(A) \cdot \bf{v}=0\), so the two spaces are othrogonal to each other.
Therefore, \(\opn{Col}A = \opn{Row}A^T \perp \opn{Nul}A^T\) as shown in the visualizations.
The orthogonal relation leads to the exploration of the following proposition.
NoteProof (Proof of Proposition 2)
Proof (Proof of Proposition 2). Based on knowledge available so far, we only prove the proposition is true when \(U\) is a subspace of \(\bb{R}^n\), but it’s true for all finite inner product spaces.
A natural idea is to use the fact that \(\opn{Nul}A \perp \opn{Row}A\).
Our first attempt is to construct a matrix \(A\) with rows being a basis of \(V\). Therefore, \(\opn{Row}A=V\) and \(V \perp \opn{Nul}A\). If we could separate a subspace \(W\) satisfying the conditions, we would prove it. However, \(U\) is a subspace of \(\bb{R}^n\), which means we only know that \(U \subseteq V+\opn{Nul}A\). The normal way to obtain a basis of \(\opn{Nul}A\) by solving the system does not guarantee that, by choosing vectors in the basis that are in \(U\), the spanned space \(W\) would satisfy that \(V+W=U\).
Below is an example with \(U=\opn{span}\{(1, 0, 0), (0, 1, 1)\}, V=\opn{span}\{(1, 0, 0)\}\) and the basis of \(\opn{Nul}A\) being \(\bf{v}_1=(0, -1, 0),\bf{v}_2=(0, 0, 1)\).
TipA Counterexample
In this case, neither \(W=\opn{span}\{\bf{v}_1\}\) nor \(W=\opn{span}\{\bf{v}_2\}\) would be a valid choice.
Eventually, coordinate mappings lead to a successful proof.
The theorem is proved in the textbook, and we would not reiterate the proof here. If we can find a coordinate mapping \(\bf{x} \mapsto [\bf{x}]_\cal{B}\) which preserves the orthogonality, by proving the proposition for the coordinate vectors, we complete our proof by mapping \(U\) onto \(\bb{R}^{\dim U}\). Let \(\dim U = m\).
We find the orthogonal basis by starting with an empty set. Each time, we add a vector in \(U\) that is orthogonal to all selected vectors in the basis. Let \(A_i = \mat{\bf{b}_1^T \\ \vdots \\ \bf{b}_{i}^T}\). If at any step \(i < m\), we cannot find such vector to add, then for all \(\bf{u} \in U\), \(\bf{u} \notin \opn{Nul}A_i\). In addition, we have \(\opn{Row}A_i \subsetneqq U\), so \(\dim\opn{Row}A_i < \dim U\). \[\begin{align} \dim(U+\opn{Nul}A_i) &= \dim U + \dim\opn{Nul}A_i \\ &> \dim\opn{Row}A_i + \dim\opn{Nul}A_i \\ &= n \end{align}\] But \(\dim(U+\opn{Nul}A_i) \leq n\) because \(U+\opn{Nul}A_i\subseteq \bb{R}^n\). Therefore, it’s always possible to construct an orthogonal basis for \(U\). Lastly, we normalize each vector so that they all have a length of \(1\). Denote the new basis as \(\cal{B}'=\{\bf{b}'_1,\dots,\bf{b}'_m\}\).
Suppose \(\bf{u}, \bf{v} \in U\). Let \([\bf{u}]_{\cal{B}'}=\mat{u'_1 \\ \vdots \\ u'_m}, [\bf{v}]_{\cal{B}'}=\mat{v'_1 \\ \vdots \\ v'_m}\). We show that the dot product of \(\bf{u}\) and \(\bf{v}\) is zero iff the dot product of \([\bf{u}]_{\cal{B}'}\) and \([\bf{v}]_{\cal{B}'}\) is zero.
\[\begin{align} \bf{u}^T\bf{v} &= (u'_1\bf{b}'_1 + \dots + u'_m\bf{b}'_m)^T(v'_1\bf{b}'_1 + \dots + v'_m\bf{b}'_m) \\ &= (u'_1{\bf{b}'_1}^T + \dots + u'_m{\bf{b}'_m}^T)(v'_1\bf{b}'_1 + \dots + v'_m\bf{b}'_m) \\ &= \sum_{i,j} u'_i v'_j {\bf{b}'_i}^T \bf{b}'_j \\ &= \sum_{i} u'_i v'_i {\bf{b}'_i}^T \bf{b}'_i \\ &= \sum_{i} u'_i v'_i \\ &= [\bf{u}]_{\cal{B}'}^T [\bf{v}]_{\cal{B}'} \end{align}\]
Lines 3 and 4 are equal because \(\bf{b}'_i\) and \(\bf{b}'_j\) are orthogonal when \(i \neq j\). Line 4 and Line 5 are equal because we have normalized the vectors in \(\cal{B}'\); thus, \({\bf{b}'_i}^T\bf{b}'_i=\|\bf{b}'_i\|^2=1\).
Let \(M=\mat{[\bf{t}_1]_{\cal{B}'} \\ \vdots \\ [\bf{t}_{\dim V}]_{\cal{B}'}}\), where \(\{\bf{t}_1,\dots,\bf{t}_{\dim V}\}\) is an arbitrary basis of \(V\). Applying the transformation \([\bf{x}]_{\cal{B}'} \mapsto \bf{x}\) on \(\opn{Nul}M\) gives the subspace \(W\). A subspace including exclusively all vectors that are orthogonal to \(\opn{Row}M\) is automatically \(\opn{Nul}M\) because the dot product of each row of \(M\) and \(\bf{v}\) being zero implies that \(M\bf{v}=\bf{0}\), concluding the proof.
TipRemark
Remark. It is possible to construct a unit orthogonal basis for any vector space \(U \subseteq \bb{R}^n\).
NoteProof (An Alternative Proof of Proposition 2)
Proof (An Alternative Proof of Proposition 2). Starting with a matrix with its rows being an arbitrary basis for \(V\), \(\mat{\bf{v}_1^T \\ \vdots \\ \bf{v}_m^T}\), we show that there exists a basis for \(W\), \(\bf{w}_1,\dots,\bf{w}_p\). Similar to above proof, we define \(A_i = \mat{\bf{v}_1^T \\ \vdots \\ \bf{w}_i^T}\). For step \(i\), we find a \(\bf{w}_{i+1} \neq \bf{0} \in U\) such that \(\opn{row}_k(A_i) \bf{w}_{i+1} = 0\) for all rows in \(A_i\). That is, \(A_i \bf{w}_{i+1} = \bf{0}\).
If at any step \(i < p\), where \(p = \dim U - m\), there does not exist such \(\bf{w}_{i+1}\), then \(U \cap \opn{Nul}A_i = \{\bf{0}\}\), so \(\dim(U + \opn{Nul}A_i) = \dim U + \dim\opn{Nul}A_i\). \[\begin{align} \dim(U+\opn{Nul}A_i) &= \dim U + \dim\opn{Nul}A_i \\ &> \dim\opn{Row}A_i + \dim\opn{Nul}A_i \\ &= n \end{align}\] But \(\dim(U+\opn{Nul}A_i) \leq n\) because \(U+\opn{Nul}A_i\subseteq \bb{R}^n\). Hence, there exists \(W=\opn{span}\{\bf{w}_1,\dots,\bf{w}_p\}\). It’s easy to check \(W\) satisfies the requirements.
We now prove that any two subspaces \(W, W'\) satisfying the stated conditions are equal. Note that \(W\) here is not necessarily the above \(W\) obtained by construction.
Let \(\bf{w}'_1,\dots,\bf{w}'_p\) be a basis for \(W'\). Because \(V+W'=U\), for all \(\bf{w} \in W\), \(\bf{w} \in U\), so \[\bf{w} = c_1\bf{v}_1+\dots+c_m\bf{v}_m + d_1\bf{w}'_1+\dots+d_p\bf{w}'_p\]
Let \(M=\mat{\bf{v}_1^T\\\vdots\\\bf{v}_m^T}\). Since \(V\perp W\) and \(V\perp W'\), \[\begin{align} M\bf{w} &= M(c_1\bf{v}_1+\dots+c_m\bf{v}_m + d_1\bf{w}'_1+\dots+d_p\bf{w}'_p) \\ &= M(c_1\bf{v}_1+\dots+c_m\bf{v}_m) \\ &= \bf{0} \end{align}\] Since \(c_1\bf{v}_1+\dots+c_m\bf{v}_m\) is in both \(\opn{Row}M\) and \(\opn{Nul}M\), and a basis is linearly independent, \(\bf{c}=\bf{0}\). Thus, \(\bf{w}=d_1\bf{w}'_1+\dots+d_p\bf{w}'_p \in W'\). It follows that \(W\subseteq W'\).
Conversely, \(W' \subseteq W\) is automatically true since \(W\) and \(W'\) are arbitrary subspaces fulfulling the requirements. Therefore, there is a unique \(W\) such that \(V+W=U\) and \(V\perp W\). \(\qed\)