% ---------------------------------------------------------------------- \chapter [Rank and the Gauss-Jordan] {Matrix rank and the Gauss-Jordan decomposition} \label{gjrank} \index{matrix rudiments} \index{rudiments} Chapter~\ref{matrix} has brought the matrix and its rudiments, the latter including \bi \item lone-element matrix~$E$ (\S~\ref{matrix:180.30}), \item the null matrix~$0$ (\S~\ref{matrix:180.25}), \item the rank-$r$ identity matrix~$I_r$ (\S~\ref{matrix:180.22}), \item the general identity matrix~$I$ and the scalar matrix~$\lambda I$ (\S~\ref{matrix:180.35}), \item the elementary operator~$T$ (\S~\ref{matrix:320}), \item the quasielementary operator~$P$, $D$, $L_{[k]}$ or $U_{[k]}$ (\S~\ref{matrix:325}), and \item the unit triangular matrix~$L$ or~$U$ (\S~\ref{matrix:330}). \ei Such rudimentary forms have useful properties, as we have seen. The general matrix~$A$ does not necessarily have any of these properties, but it turns out that one can factor any matrix whatsoever into a product of rudiments which do have the properties, and that several orderly procedures are known to do so. The simplest of these, and indeed one of the more useful, is the Gauss-Jordan decomposition. This chapter introduces it. Section~\ref{matrix:180} has de\"emphasized the concept of matrix dimensionality $m \times n$, supplying in its place the new concept of matrix rank. However, that section has actually defined rank only for the rank-$r$ identity matrix~$I_r$. In fact all matrices have rank. This chapter explains. Before treating the Gauss-Jordan decomposition and the matter of matrix rank as such, however, we shall find it helpful to prepare two preliminaries thereto: (i)~the matter of the linear independence of vectors; and (ii)~the elementary similarity transformation. The chapter begins with these. Except in \S~\ref{gjrank:337}, the chapter demands more rigor than one likes in such a book as this. However, it is hard to see how to avoid the rigor here, and logically the chapter cannot be omitted. We will drive through the chapter in as few pages as can be managed, and then onward to the more interesting matrix topics of chapters~\ref{mtxinv} and~\ref{eigen}. % ---------------------------------------------------------------------- \section{Linear independence} \label{gjrank:335} \index{linear independence} \index{linear dependence} \index{independence} \index{linear combination} \index{weighted sum} \index{sum!weighted} \index{triviality} \index{coefficient!nontrivial} Linear independence is a significant possible property of a set of vectors---whether the set be the several columns of a matrix, the several rows, or some other vectors---the property being defined as follows. A vector is \emph{linearly independent} if its role cannot be served by the other vectors in the set. More formally, the~$n$ vectors of the set $\{\ve a_1,\ve a_2,\ve a_3,\ve a_4,\ve a_5,\ldots,\ve a_n\}$ are linearly independent if and only if none of them can be expressed as a linear combination---a weighted sum---of the others. That is, the several~$\ve a_k$ are linearly independent iff \bq{gjrank:335:10} \alpha_1\ve a_1 + \alpha_2\ve a_2 + \alpha_3\ve a_3 + \cdots + \alpha_n\ve a_n \neq 0 \eq for all nontrivial~$\alpha_k$, where ``nontrivial~$\alpha_k$'' means the several~$\alpha_k$, at least one of which is nonzero (\emph{trivial}~$\alpha_k$, by contrast, would be $\alpha_1=\alpha_2=\alpha_3=\cdots=\alpha_n=0$). Vectors which can combine nontrivially to reach the null vector are by definition \emph{linearly dependent.} \index{zero vector} \index{null vector} \index{$0$ (zero)!vector} \index{vector!zero or null} Linear independence is a property of vectors. Technically the property applies to scalars, too, inasmuch as a scalar resembles a one-element vector---so, any nonzero scalar alone is linearly independent---but there is no such thing as a linearly independent pair of scalars, because one of the pair can always be expressed as a complex multiple of the other. Significantly but less obviously, there is also no such thing as a linearly independent set which includes the null vector;~(\ref{gjrank:335:10}) forbids it. Paradoxically, even the single-member, $n=1$ set consisting only of $\ve a_1=0$ is, strictly speaking, not linearly independent. \index{empty set} \index{edge case} For consistency of definition, we regard the empty, $n=0$ set as linearly independent, on the technical ground that the only possible linear combination of the empty set is trivial.% \footnote{ This is the kind of thinking which typically governs mathematical edge cases. One could define the empty set to be linearly dependent if one really wanted to, but what then of the observation that adding a vector to a linearly dependent set never renders the set independent? Surely in this light it is preferable just to define the empty set as independent in the first place. Similar thinking makes $0!=1$, $\sum_{k=0}^{-1} a_kz^k = 0$, and~2 not~1 the least prime, among other examples. } \index{vector!arbitrary} If a linear combination of several independent vectors~$\ve a_k$ forms a vector~$\ve b$, then one might ask: can there exist a different linear combination of the same vectors~$\ve a_k$ which also forms~$\ve b$? That is, if \[ \beta_1\ve a_1 + \beta_2\ve a_2 + \beta_3\ve a_3 + \cdots + \beta_n\ve a_n = \ve b, \] where the several~$\ve a_k$ satisfy~(\ref{gjrank:335:10}), then is \[ \beta'_1\ve a_1 + \beta'_2\ve a_2 + \beta'_3\ve a_3 + \cdots + \beta'_n\ve a_n = \ve b \] possible? To answer the question, suppose that it were possible. The difference of the two equations then would be \[ (\beta_1'-\beta_1)\ve a_1 + (\beta_2'-\beta_2)\ve a_2 + (\beta_3'-\beta_3)\ve a_3 + \cdots + (\beta_n'-\beta_n)\ve a_n = 0. \] According to~(\ref{gjrank:335:10}), this could only be so if the coefficients in the last equation where trivial---that is, only if $\beta_1'-\beta_1=0$, $\beta_2'-\beta_2=0$, $\beta_3'-\beta_3=0$, \ldots, $\beta_n'-\beta_n=0$. But this says no less than that the two linear combinations, which we had supposed to differ, were in fact one and the same. One concludes therefore that, \emph{if a vector~$\ve b$ can be expressed as a linear combination of several linearly independent vectors~$\ve a_k$, then it cannot be expressed as any other combination of the same vectors.} The combination is unique. \index{visualization, geometrical} \index{geometrical visualization} \index{abstraction} Linear independence can apply in any dimensionality, but it helps to visualize the concept geometrically in three dimensions, using the three-dimensional geometrical vectors of \S~\ref{trig:230}. Two such vectors are independent so long as they do not lie along the same line. A third such vector is independent of the first two so long as it does not lie in their common plane. A fourth such vector (unless it points off into some unvisualizable fourth dimension) cannot possibly then be independent of the three. We discuss the linear independence of vectors in this, a chapter on matrices, because (\S~\ref{matrix:120}) a matrix is essentially a sequence of vectors---either of column vectors or of row vectors, depending on one's point of view. As we shall see in \S~\ref{gjrank:340}, the important property of matrix \emph{rank} depends on the number of linearly independent columns or rows a matrix has. % ---------------------------------------------------------------------- \section{The elementary similarity transformation} \label{gjrank:337} \index{elementary similarity transformation} \index{similarity transformation} Section~\ref{matrix:321} and its~(\ref{matrix:321:60}) have introduced the \emph{similarity transformation} % bad break $CAC^{-1}$ or~$C^{-1}AC$, which arises when an operator~$C$ commutes respectively rightward or leftward past a matrix~$A$. The similarity transformation has several interesting properties, some of which we are now prepared to discuss, particularly in the case in which the operator happens to be an elementary, $C=T$. In this case, the several rules of Table~\ref{gjrank:337:table} obtain. \begin{table} \caption{Some elementary similarity transformations.} \label{gjrank:337:table} \settowidth\tla{${U^{\{k\}}}'$} \nc\xx{$L,U,L_{[k]},U_{[k]},L^{[k]},U^{[k]},L^{\{k\}},U^{\{k\}},L_\|^{\{k\}},U_\|^{\{k\}}$} \settowidth\tlb{\xx} \bqb T_{[i \lra j]} I T_{[i \lra j]} &=& I \\ T_{[i \lra j]} P T_{[i \lra j]} &=& P' \\ T_{[i \lra j]} D T_{[i \lra j]} &=& D' = D + \left([D]_{jj}-[D]_{ii}\right)E_{ii} + \left([D]_{ii}-[D]_{jj}\right)E_{jj} \\ T_{[i \lra j]} D T_{[i \lra j]} &=& \makebox[\tla][l]{$D$} \ \ \mbox{if $[D]_{ii} = [D]_{jj}$} \\ T_{[i \lra j]} L^{[k]}T_{[i \lra j]} &=& \makebox[\tla][l]{$L^{[k]}$} \ \ \mbox{if $ik$ and $j>k$} \\ T_{[i \lra j]} L^{\{k\}}T_{[i \lra j]} &=& \makebox[\tla][l]{${L^{\{k\}}}'$} \ \ \mbox{if $i>k$ and $j>k$} \\ T_{[i \lra j]} U^{\{k\}}T_{[i \lra j]} &=& \makebox[\tla][l]{${U^{\{k\}}}'$} \ \ \mbox{if $ik$ and $j>k$} \\ T_{[i \lra j]} U_\|^{\{k\}}T_{[i \lra j]} &=& \makebox[\tla][l]{${U_\|^{\{k\}}}'$} \ \ \mbox{if $i j$} \\ T_{\alpha[ij]} U T_{-\alpha[ij]} &=& \makebox[\tla][l]{$U'$} \ \ \mbox{if $i < j$} \eqb \end{table} Most of the table's rules are fairly obvious if the meaning of the symbols is understood, though to grasp some of the rules it helps to sketch the relevant matrices on a sheet of paper. Of course rigorous symbolic proofs can be constructed after the pattern of \S~\ref{matrix:330.30}, but they reveal little or nothing sketching the matrices does not. In Table~\ref{gjrank:337:table} as elsewhere, the symbols~$P$, $D$, $L$ and~$U$ represent the quasielementaries and unit triangular matrices of \S\S~\ref{matrix:325} and~\ref{matrix:330}. The symbols~$P'$, $D'$, $L'$ and~$U'$ also represent quasielementaries and unit triangular matrices, only not necessarily the same ones~$P$, $D$, $L$ and~$U$ do. The rules of Table~\ref{gjrank:337:table} permit one to commute some but not all elementaries past a quasielementary operator or unit triangular matrix without fundamentally altering the character of the quasielementary operator or unit triangular matrix, and sometimes without changing it at all. The rules find use among other places in the Gauss-Jordan decomposition of \S~\ref{gjrank:341}. % ---------------------------------------------------------------------- \section{The Gauss-Jordan decomposition} \label{gjrank:341} \index{Gauss, Carl Friedrich (1777--1855)} \index{Jordan, Wilhelm (1842--1899)} \index{Gauss-Jordan decomposition} \index{decomposition!Gauss-Jordan} \index{Gauss-Jordan factorization} \index{factorization!Gauss-Jordan} \index{reversibility} \index{$LU$ decomposition} \index{decomposition!$LU$} The \emph{Gauss-Jordan decomposition} of an arbitrary, dimension-limited, $m \times n$ matrix~$A$ is% \footnote{ Most introductory linear algebra texts this writer has met call the Gauss-Jordan decomposition instead the ``$LU$ decomposition'' and include fewer factors in it, typically merging~$D$ into~$L$ and omitting~$K$ and~$S$. They also omit~$I_r$, since their matrices have pre-defined dimensionality. Perhaps the reader will agree that the decomposition is cleaner as presented here. } \bq{gjrank:341:GJ} \begin{split} A = G_> I_r G_< & = P D L U I_r K S, \\ G_< &\equiv K S, \\ G_> &\equiv P D L U, \end{split} \eq where \bi \item $P$ and~$S$ are general interchange operators (\S~\ref{matrix:325.10}); \item $D$ is a general scaling operator (\S~\ref{matrix:325.20}); \item $L$ and~$U$ are respectively unit lower and unit upper triangular matrices (\S~\ref{matrix:330}); \item $K=L_\|^{\{r\}T}$ is the transpose of a parallel unit lower triangular matrix, being thus a parallel unit upper triangular matrix (\S~\ref{matrix:330.50}); \item $G_>$ and~$G_<$ are composites% \footnote{ One can pronounce~$G_>$ and~$G_<$ respectively as~``$G$ acting rightward'' and~``$G$ acting leftward.'' The letter~$G$ itself can be regarded as standing for ``Gauss-Jordan,'' but admittedly it is chosen as much because otherwise we were running out of available Roman capitals! } as defined by~(\ref{gjrank:341:GJ}); and \item $r$ is an unspecified rank. \ei The Gauss-Jordan decomposition is also called the \emph{Gauss-Jordan factorization.} Whether all possible dimension-limited, $m\times n$ matrices~$A$ have a Gauss-Jordan decomposition (they do, in fact) is a matter this section addresses. However---at least for matrices which do have one---because~$G_>$ and~$G_<$ are composed of invertible factors, one can left-multiply the equation $A = G_> I_r G_<$ by~$G_>^{-1}$ and right-multiply it by~$G_<^{-1}$ to obtain \bq{gjrank:341:GJinv} \begin{split} U^{-1} L^{-1} D^{-1} P^{-1} A S^{-1} K^{-1} & = G_>^{-1} A G_<^{-1} = I_r, \\ S^{-1} K^{-1} &= G_<^{-1}, \\ U^{-1} L^{-1} D^{-1} P^{-1} &= G_>^{-1}, \end{split} \eq the Gauss-Jordan's complementary form. \subsection{Motive} \label{gjrank:341.01} Equation~(\ref{gjrank:341:GJ}) seems inscrutable. The equation itself is easy enough to read, but just as there are many ways to factor a scalar ($\mbox{0xC} = [4][3] = [2]^2[3] = [2][6]$, for example), there are likewise many ways to factor a matrix. Why choose this particular way? There are indeed many ways. We shall meet some of the others in \S\S~\ref{mtxinv:460}, \ref{eigen:423}, \ref{eigen:520} and~\ref{eigen:600}. The Gauss-Jordan decomposition we meet here however has both significant theoretical properties and useful practical applications, and in any case needs less advanced preparation to appreciate than the others, and (at least as developed in this book) precedes the others logically. It emerges naturally when one posits a pair of dimension-limited, square, $n \times n$ matrices,~$A$ and~$A^{-1}$, for which $A^{-1} A = I_n$, where~$A$ is known and~$A^{-1}$ is to be determined. [The~$A^{-1}$ here is the $A^{-1(n)}$ of eqn.~\ref{matrix:321:20}. However, it is only supposed here that $A^{-1} A = I_n$; it is not \emph{yet} claimed that $A A^{-1} = I_n$. ``Square'' means that the matrix has an $n\times n$ active region rather than an $m\times n$, $m\neq n$, where ``active region'' is defined as in \S~\ref{matrix:180.25}.] To determine~$A^{-1}$ is not an entirely trivial problem. The matrix~$A^{-1}$ such that $A^{-1} A = I_n$ may or may not exist (usually it does exist if~$A$ is square, but even then it may not, as we shall soon see), and even if it does exist, how to determine it is not immediately obvious. And still, if one can determine~$A^{-1}$, that is only for square~$A$; what if~$A$, having an $m\times n$, $m\neq n$, active region, were not square? In the present subsection however we are not trying to prove anything, only to motivate, so for the moment let us suppose an~$A$ for which~$A^{-1}$ does exist, let us confine our attention to square~$A$, and let us seek~$A^{-1}$ by left-multiplying~$A$ by a sequence $\prod T$ of elementary row operators, each of which makes the matrix more nearly resemble~$I_n$. When~$I_n$ is finally achieved, then we shall have that \[ \left(\prod T\right) (A) = I_n, \] or, left-multiplying by~$I_n$ and observing that $I_n^2=I_n$, \[ (I_n) \left(\prod T\right) (A) = I_n, \] which implies that \[ A^{-1} = (I_n) \left(\prod T\right). \] The product of elementaries which transforms~$A$ to~$I_n$, truncated (\S~\ref{matrix:180.23}) to $n \times n$ dimensionality, itself constitutes~$A^{-1}$. This observation is what motivates the Gauss-Jordan decomposition. { \nc\fz[1]{\mbox{\footnotesize$\ds{#1}$}} \settowidth\tla{\footnotesize $-0$} By successive steps,% \footnote{ Theoretically, all elementary operators including the ones here have extended-operational form~(\S~\ref{matrix:180.35}), but all those~$\cdots$ ellipses clutter the page too much. Only the $2 \times 2$ active regions are shown here. } a concrete example: \bqb A &=& \fz{\left[ \br{rr} 2 & -4 \\ 3 & -1 \er \right]}, \\ \fz{ \left[ \br{rr} \frac 1 2 & 0 \\ 0 & 1 \er \right] } A &=& \fz{\left[ \br{rr} 1 & -2 \\ 3 & -1 \er \right]}, \\ \fz{ \left[ \br{rr} 1 & 0 \\ -3 & 1 \er \right] \left[ \br{rr} \frac 1 2 & 0 \\ 0 & 1 \er \right] } A &=& \fz{\left[ \br{rr} 1 & -2 \\ 0 & 5 \er \right]}, \\ \fz{ \left[ \br{rr} 1 & 0 \\ 0 & \frac 1 5 \er \right] \left[ \br{rr} 1 & 0 \\ -3 & 1 \er \right] \left[ \br{rr} \frac 1 2 & 0 \\ 0 & 1 \er \right] } A &=& \fz{ \left[ \br{rr} 1 & -2 \\ 0 & 1 \er \right] }, \\ \fz{ \left[ \br{rr} 1 & 2 \\ 0 & 1 \er \right] \left[ \br{rr} 1 & 0 \\ 0 & \frac 1 5 \er \right] \left[ \br{rr} 1 & 0 \\ -3 & 1 \er \right] \left[ \br{rr} \frac 1 2 & 0 \\ 0 & 1 \er \right] } A &=& \fz{\left[ \br{rr} 1 & \makebox[\tla][r]{$0$} \\ 0 & 1 \er \right]}, \\ \fz{ \left[ \br{rr} 1 & 0 \\ 0 & 1 \er \right] \left[ \br{rr} 1 & 2 \\ 0 & 1 \er \right] \left[ \br{rr} 1 & 0 \\ 0 & \frac 1 5 \er \right] \left[ \br{rr} 1 & 0 \\ -3 & 1 \er \right] \left[ \br{rr} \frac 1 2 & 0 \\ 0 & 1 \er \right] } A &=& \fz{\left[ \br{rr} 1 & \makebox[\tla][r]{$0$} \\ 0 & 1 \er \right]}. \eqb Hence, \[ \renewcommand\arraystretch{1.3} A^{-1} = \fz{ \left[ \br{rr} 1 & 0 \\ 0 & 1 \er \right] \left[ \br{rr} 1 & 2 \\ 0 & 1 \er \right] \left[ \br{rr} 1 & 0 \\ 0 & \frac 1 5 \er \right] \left[ \br{rr} 1 & 0 \\ -3 & 1 \er \right] \left[ \br{rr} \frac 1 2 & 0 \\ 0 & 1 \er \right] } = \fz{ \left[ \br{rr} -\frac 1 {\mathrm A} & \frac 2 5 \\ -\frac 3 {\mathrm A} & \frac 1 5 \er \right] }. \] Using the elementary commutation identity that $T_{\beta[m]}T_{\alpha[mj]} = T_{\alpha\beta[mj]}T_{\beta[m]}$, from Table~\ref{matrix:Txchg3}, to group like operators, we have that \[ \renewcommand\arraystretch{1.3} A^{-1} = \fz{ \left[ \br{rr} 1 & 0 \\ 0 & 1 \er \right] \left[ \br{rr} 1 & 2 \\ 0 & 1 \er \right] \left[ \br{rr} 1 & 0 \\ -\frac 3 5 & 1 \er \right] \left[ \br{rr} 1 & 0 \\ 0 & \frac 1 5 \er \right] \left[ \br{rr} \frac 1 2 & 0 \\ 0 & 1 \er \right] } = \fz{ \left[ \br{rr} -\frac 1 {\mathrm A} & \frac 2 5 \\ -\frac 3 {\mathrm A} & \frac 1 5 \er \right] }; \] or, multiplying the two scaling elementaries to merge them into a single general scaling operator (\S~\ref{matrix:325.20}), \[ \renewcommand\arraystretch{1.3} A^{-1} = \fz{ \left[ \br{rr} 1 & 0 \\ 0 & 1 \er \right] \left[ \br{rr} 1 & 2 \\ 0 & 1 \er \right] \left[ \br{rr} 1 & 0 \\ -\frac 3 5 & 1 \er \right] \left[ \br{rr} \frac 1 2 & 0 \\ 0 & \frac 1 5 \er \right] } = \fz{ \left[ \br{rr} -\frac 1 {\mathrm A} & \frac 2 5 \\ -\frac 3 {\mathrm A} & \frac 1 5 \er \right] }. \] The last equation is written symbolically as \[ A^{-1} = I_2 U^{-1} L^{-1} D^{-1}, \] from which \[ A = D L U I_2 = \fz{ \left[ \br{rr} 2 & 0 \\ 0 & 5 \er \right] \left[ \br{rr} 1 & 0 \\ \frac 3 5 & 1 \er \right] \left[ \br{rr} 1 & -2 \\ 0 & 1 \er \right] \left[ \br{rr} 1 & 0 \\ 0 & 1 \er \right] } = \fz{\left[ \br{rr} 2 & -4 \\ 3 & -1 \er \right]}. \] } Now, admittedly, the equation $A = D L U I_2$ is not~(\ref{gjrank:341:GJ})---or rather, it is~(\ref{gjrank:341:GJ}), but only in the special case that $r = 2$ and $P = S = K = I$---which begs the question: why do we need the factors~$P$, $S$ and~$K$ in the first place? The answer regarding~$P$ and~$S$ is that these factors respectively gather row and column interchange elementaries, of which the example given has used none but which other examples sometimes need or want, particularly to avoid dividing by zero when they encounter a zero in an inconvenient cell of the matrix (the reader might try reducing $A=[0\;1; 1\;0]$ to~$I_2$, for instance; a row or column interchange is needed here). Regarding~$K$, this factor comes into play when~$A$ has broad rectangular ($mi$. It also fills in $\tilde L$'s $i$th column below the pivot, advancing that matrix from the $L^{\{i-1\}}$ form to the $L^{\{i\}}$ form. Pictorially, \bqb \tilde L = L^{\{i\}} &=& \mf{ccccccccc}{ \ddots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\\ \cdots&1&0&0&0&0&0&0&\cdots\\ \cdots&{*}&1&0&0&0&0&0&\cdots\\ \cdots&{*}&{*}&1&0&0&0&0&\cdots\\ \cdots&{*}&{*}&{*}&1&0&0&0&\cdots\\ \cdots&{*}&{*}&{*}&{*}&1&0&0&\cdots\\ \cdots&{*}&{*}&{*}&{*}&0&1&0&\cdots\\ \cdots&{*}&{*}&{*}&{*}&0&0&1&\cdots\\ &\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots },\\ \tilde I &=& \mf{ccccccccc}{ \ddots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\\ \cdots&1&{*}&{*}&{*}&{*}&{*}&{*}&\cdots\\ \cdots&0&1&{*}&{*}&{*}&{*}&{*}&\cdots\\ \cdots&0&0&1&{*}&{*}&{*}&{*}&\cdots\\ \cdots&0&0&0&1&{*}&{*}&{*}&\cdots\\ \cdots&0&0&0&0&{*}&{*}&{*}&\cdots\\ \cdots&0&0&0&0&{*}&{*}&{*}&\cdots\\ \cdots&0&0&0&0&{*}&{*}&{*}&\cdots\\ &\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots }. \eqb (Note that it is not necessary actually to apply the addition elementaries here one by one. Together they easily form an addition quasielementary $L_{[i]}$, and thus can be applied all at once. See \S~\ref{matrix:325.30}.) \item \label{gjrank:341:s50} Increment \[ i\la i+1. \] Go back to step~\ref{gjrank:341:s18}. \item \label{gjrank:341:s55} Decrement \[ i\la i-1 \] to undo the last instance of step~\ref{gjrank:341:s50} (even if there never was an instance of step~\ref{gjrank:341:s50}), thus letting~$i$ point to the matrix's last nonzero row. After decrementing, let the rank \[ r \equiv i. \] Notice that, certainly, $r \le m$ and $r \le n$. \item \label{gjrank:341:s60} (Besides arriving at this point from step~\ref{gjrank:341:s55} above, the algorithm also re\"enters here from step~\ref{gjrank:341:s70} below.) If $i=0$, then skip directly to step~\ref{gjrank:341:s75}. \item \label{gjrank:341:s65} Observing that~(\ref{gjrank:341:05}) can be expanded to read \[ A = \tilde P \tilde D \tilde L \left( \tilde U T_{\tdi_{pi}[pi]} \right) \left( T_{-\tdi_{pi}[pi]} \tilde I \right) \tilde K \tilde S, \] clear $\tilde I$'s $i$th column above the pivot by letting \[ \begin{split} \tilde U &\la \left( \tilde U \right) \left( \prod_{p=1}^{i-1}T_{\tdi_{pi}[pi]} \right), \\ \tilde I &\la \left( \coprod_{p=1}^{i-1}T_{-\tdi_{pi}[pi]} \right) \left( \tilde I \right). \end{split} \] This forces $\tdi_{ip}=0$ for all $p \neq i$. It also fills in $\tilde U$'s $i$th column above the pivot, advancing that matrix from the $U^{\{i+1\}}$ form to the $U^{\{i\}}$ form. Pictorially, \bqb \tilde U = U^{\{i\}} &=& \mf{ccccccccc}{ \ddots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\\ \cdots&1&0&0&{*}&{*}&{*}&{*}&\cdots\\ \cdots&0&1&0&{*}&{*}&{*}&{*}&\cdots\\ \cdots&0&0&1&{*}&{*}&{*}&{*}&\cdots\\ \cdots&0&0&0&1&{*}&{*}&{*}&\cdots\\ \cdots&0&0&0&0&1&{*}&{*}&\cdots\\ \cdots&0&0&0&0&0&1&{*}&\cdots\\ \cdots&0&0&0&0&0&0&1&\cdots\\ &\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots },\\ \tilde I &=& \mf{ccccccccc}{ \ddots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\\ \cdots&1&{*}&{*}&0&0&0&0&\cdots\\ \cdots&0&1&{*}&0&0&0&0&\cdots\\ \cdots&0&0&1&0&0&0&0&\cdots\\ \cdots&0&0&0&1&0&0&0&\cdots\\ \cdots&0&0&0&0&1&0&0&\cdots\\ \cdots&0&0&0&0&0&1&0&\cdots\\ \cdots&0&0&0&0&0&0&1&\cdots\\ &\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots }. \eqb (As in step~\ref{gjrank:341:s45}, here again it is not necessary actually to apply the addition elementaries one by one. Together they easily form an addition quasielementary $U_{[i]}$. See \S~\ref{matrix:325.30}.) \item \label{gjrank:341:s70} Decrement $i\la i-1$. Go back to step~\ref{gjrank:341:s60}. \item \label{gjrank:341:s75} \index{extra column} \index{spare column} \index{column!spare} Notice that~$\tilde I$ now has the form of a rank-$r$ identity matrix, except with $n-r$ extra columns dressing its right edge (often $r=n$ however; then there are no extra columns). Pictorially, \[ \tilde I = \mf{ccccccccc}{ \ddots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\\ \cdots&1&0&0&0&{*}&{*}&{*}&\cdots\\ \cdots&0&1&0&0&{*}&{*}&{*}&\cdots\\ \cdots&0&0&1&0&{*}&{*}&{*}&\cdots\\ \cdots&0&0&0&1&{*}&{*}&{*}&\cdots\\ \cdots&0&0&0&0&0&0&0&\cdots\\ \cdots&0&0&0&0&0&0&0&\cdots\\ \cdots&0&0&0&0&0&0&0&\cdots\\ &\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots }. \] Observing that~(\ref{gjrank:341:05}) can be expanded to read \[ A = \tilde P \tilde D \tilde L \tilde U \left( \tilde I T_{-\tdi_{pq}[pq]} \right) \left( T_{\tdi_{pq}[pq]} \tilde K \right) \tilde S, \] use the now conveniently elementarized columns of $\tilde I$'s main body to suppress the extra columns on its right edge by \[ \begin{split} \tilde I &\la \left( \tilde I \right) \left( \prod_{q=r+1}^n \, \coprod_{p=1}^r T_{-\tdi_{pq}[pq]} \right), \\ \tilde K &\la \left( \coprod_{q=r+1}^n \, \prod_{p=1}^r T_{\tdi_{pq}[pq]} \right) \left( \tilde K \right). \end{split} \] (Actually, entering this step, it was that $\tilde K = I$, so in fact~$\tilde K$ becomes just the product above. As in steps~\ref{gjrank:341:s45} and~\ref{gjrank:341:s65}, here again it is not necessary actually to apply the addition elementaries one by one. Together they easily form a parallel unit upper---not lower---triangular matrix $L_\|^{\{r\}T}$. See \S~\ref{matrix:330.50}.) \item \label{gjrank:341:s85} Notice now that $\tilde I=I_r$. Let \[ P \equiv \tilde P, \ D \equiv \tilde D, \ L \equiv \tilde L, \ U \equiv \tilde U, \ K \equiv \tilde K, \ S \equiv \tilde S. \] End. \end{enumerate} Never stalling, the algorithm cannot fail to achieve $\tilde I=I_r$ and thus a complete Gauss-Jordan decomposition of the form~(\ref{gjrank:341:GJ}), though what value the rank~$r$ might turn out to have is not normally known to us in advance. (We have not yet proven, but will in \S~\ref{gjrank:340}, that the algorithm always produces the same~$I_r$, the same rank $r \ge 0$, regardless of which pivots $\tdi_{pq}\neq 0$ one happens to choose in step~\ref{gjrank:341:s20} along the way. We can safely ignore this unproven fact however for the immediate moment.) \subsection{Rank and independent rows} \label{gjrank:341.11} \index{rank!and independent rows} \index{rank!maximum} Observe that the Gauss-Jordan algorithm of \S~\ref{gjrank:341.10} operates always within the bounds of the original $m\times n$ matrix~$A$. Therefore, necessarily, \bq{gjrank:341:22} \begin{split} r &\le m, \\ r &\le n. \end{split} \eq The rank~$r$ exceeds the number neither of the matrix's rows nor of its columns. This is unsurprising. Indeed the narrative of the algorithm's step~\ref{gjrank:341:s55} has already noticed the fact. Observe also however that \emph{the rank always fully reaches $r=m$ if the rows of the original matrix~$A$ are linearly independent.} The reason for this observation is that the rank can fall short, $rI_r)(I_rG_$ and~$B_<$ respectively represent the aforementioned reversible row and column operations: \bq{gjrank:340:18} \begin{split} B_>^{-1}B_> &= I = B_>B_>^{-1}; \\ B_<^{-1}B_< &= I = B_$ and~$B_<$ exist such that \bq{gjrank:340:20} \begin{split} B_>AB_< &= I_r, \\ A &= B_>^{-1} I_r B_<^{-1}. \end{split} \eq The question is whether in~(\ref{gjrank:340:20}) only a single rank~$r$ is possible. To answer the question, we suppose that another rank were possible, that~$A$ had not only rank~$r$ but also rank~$s$. Then, \[ \begin{split} A &= B_>^{-1} I_r B_<^{-1}, \\ A &= G_>^{-1} I_s G_<^{-1}. \end{split} \] Combining these equations, \[ B_>^{-1} I_r B_<^{-1} = G_>^{-1} I_s G_<^{-1}. \] Solving first for~$I_r$, then for~$I_s$, \[ \begin{split} (B_>G_>^{-1}) I_s (G_<^{-1}B_<) &= I_r, \\ (G_>B_>^{-1}) I_r (B_<^{-1}G_<) &= I_s. \end{split} \] Were it that $r \neq s$, then one of these two equations would constitute the demotion of an identity matrix and the other, a promotion. But according to \S~\ref{gjrank:340.10} and its~(\ref{gjrank:340:10}), promotion is impossible. Therefore $r \neq s$ is also impossible, and \[ r = s \] is guaranteed. No matrix has two different ranks. \emph{Matrix rank is unique.} This finding has two immediate implications: \bi \item Reversible row and/or column operations exist to change any matrix of rank~$r$ to \emph{any other matrix} of the same rank. The reason is that, according to~(\ref{gjrank:340:20}), (\ref{gjrank:341:GJ}) and~(\ref{gjrank:341:GJinv}), reversible operations exist to change both matrices to~$I_r$ and back. \item No reversible operation can change a matrix's rank. \ei The finding further suggests a conjecture: \bi \item The matrices~$A$, $A^T$ and~$A^{*}$ share the same rank~$r$. \ei The conjecture is proved by using~(\ref{matrix:120:30}) or~(\ref{matrix:120:33}) to compute the transpose or adjoint of~(\ref{gjrank:340:20}). The discovery that every matrix has a single, unambiguous rank and the establishment of a failproof algorithm---the Gauss-Jordan---to ascertain that rank have not been easy to achieve, but they are important achievements nonetheless, worth the effort thereto. The reason these achievements matter is that the mere dimensionality of a matrix is a chimerical measure of the matrix's true size---as for instance for the $3 \times 3$ example matrix at the head of the section. Matrix rank by contrast is a solid, dependable measure. We will rely on it often. Section~\ref{gjrank:340.30} comments further. \subsection{The full-rank matrix} \label{gjrank:340.25} \index{rank!full} \index{full rank} \index{matrix!full-rank} \index{degenerate matrix} \index{matrix!degenerate} According to~(\ref{gjrank:341:22}), the rank~$r$ of a dimension-limited matrix (\S~\ref{matrix:180.25})---let us refer to it as a \emph{matrix} (just to reduce excess verbiage)---can exceed the number neither of the matrix's rows nor of its columns. The greatest rank possible for an $m\times n$ matrix is the lesser of~$m$ and~$n$. A \emph{full-rank} matrix, then, is defined to be an $m\times n$ matrix with rank $r=m$ or $r=n$---or, if $m=n$, both. A matrix of less than full rank is a \emph{degenerate} matrix. \index{linear combination} \index{linear dependence} Consider a tall $m\times n$ matrix~$C$, $m\ge n$, one of whose~$n$ columns is a linear combination (\S~\ref{gjrank:335}) of the others. One could by definition target the dependent column with addition elementaries, using multiples of the other columns to wipe the dependent column out. Having zeroed the dependent column, one could then interchange it over to the matrix's extreme right, effectively throwing the column away, shrinking the matrix to $m\times(n-1)$ dimensionality. Shrinking the matrix necessarily also shrinks the bound on the matrix's rank to $r\le n-1$---which is to say, to $r^{T}$ such that $I_n = B_<^{T}A^{T}B_>^{T}$, the transpose of which equation is $B_>AB_< = I_n$---which in turn says that not only~$A^T$, but also~$A$ itself, has full rank $r=n$. Parallel reasoning rules the rows and columns of broad matrices, $m\le n$, of course. To square matrices, $m=n$, both lines of reasoning apply. \index{matrix!tall} \index{matrix!broad} \index{matrix!square} Gathering findings, we have that \bi \item a tall $m\times n$ matrix, $m\ge n$, has full rank if and only if its columns are linearly independent; \item a broad $m\times n$ matrix, $m\le n$, has full rank if and only if its rows are linearly independent; \item a square $n\times n$ matrix, $m = n$, has full rank if and only if its columns and/or its rows are linearly independent; and \item a square matrix has both independent columns and independent rows, or neither; never just one or the other. \ei \index{full column rank} \index{column rank!full} \index{rank!column} \index{full row rank} \index{row rank!full} \index{rank!row} To say that a matrix has \emph{full column rank} is to say that it is tall or square and has full rank $r=n \le m$. To say that a matrix has \emph{full row rank} is to say that it is broad or square and has full rank $r=m \le n$. Only a square matrix can have full column rank and full row rank at the same time, because a tall or broad matrix cannot but include, respectively, more columns or more rows than~$I_r$. \index{rank!infinite} \index{infinite rank} Observe incidentally that extended operators, which per \S~\ref{matrix:180.35} define their $m\times n$ active regions differently, have infinite rank. \subsection[Under- and overdetermined systems (introduction)] {Underdetermined and overdetermined linear systems (introduction)} \label{gjrank:340.24} \index{linear system!classification of} \index{linear system!taxonomy of} \index{taxonomy!of the linear system} \index{linear system!underdetermined} \index{linear system!overdetermined} \index{linear system!degenerate} \index{underdetermined linear system} \index{overdetermined linear system} \index{degenerate linear system} The last paragraph of \S~\ref{gjrank:340.25} % Thesaurus for provoke: awaken, call forth, call up, cultivate, % enkindle, fire up, foment, inspire, instigate, motivate, move, % promote, prompt, provoke, stir up. provokes yet further terminology. A linear system $A\ve x = \ve b$ is \emph{underdetermined} if~$A$ lacks full column rank---that is, if $r^{-1}$ to reach the form \[ I_rG_<\ve x = G_>^{-1}\ve b. \] If the $m$-element vector $\ve c \equiv G_>^{-1}\ve b$, then $I_rG_<\ve x = \ve c,$ which is impossible unless the last $m-r$ elements of~$\ve c$ happen to be zero. But since~$G_>$ is invertible, each~$\ve b$ corresponds to a unique~$\ve c$ and vice versa; so, if~$\ve b$ is an unrestricted $m$-element vector then so also is~$\ve c$, which verifies the claim. Complementarily, \emph{a nonoverdetermined linear system $A\ve x = \ve b$ does have a solution for every possible $m$-element driving vector~$\ve b$.} This is so because in this case the last $m-r$ elements of~$\ve c$ do happen to be zero; or, better stated, because~$\ve c$ in this case has no nonzeros among its last $m-r$ elements, because it \emph{has} no last $m-r$ elements, for the trivial reason that $r=m$. It is an analytical error, and an easy one innocently to commit, to require that \[ A\ve x = \ve b \] for unrestricted~$\ve b$ when~$A$ lacks full row rank. The error is easy to commit because the equation looks right, because such an equation is indeed valid over a broad domain of~$\ve b$ and might very well have been written correctly in that context, only not in the context of unrestricted~$\ve b$. Analysis including such an error can lead to subtly absurd conclusions. It is never such an analytical error however to require that \[ A\ve x = 0 \] because, whatever other solutions such a system might have, it has at least the solution $\ve x = 0$. \subsection{The full-rank factorization} \label{gjrank:340.26} \index{full-rank factorization} \index{factorization!full-rank} One sometimes finds dimension-limited matrices of less than full rank inconvenient to handle. However, every dimension-limited, $m \times n$ matrix of rank~$r$ can be expressed as the product of two full-rank matrices, one $m \times r$ and the other $r \times n$, both also of rank~$r$: \bq{gjrank:340:26} A = BC. \eq The truncated Gauss-Jordan~(\ref{gjrank:341:GJtC}) constitutes one such \emph{full-rank factorization:} $B=I_mG_>I_r$, $C=I_rG_r$ that dress~$\tilde I$'s right, but in this case~$\tilde I$ has only~$r$ columns and therefore has no spare columns to null. Hence step~\ref{gjrank:341:s75} does nothing and $K=I$. \index{interchange!refusing an} That $S=I$ comes immediately of choosing $q=i$ for pivot column during each iterative instance of the algorithm's step~\ref{gjrank:341:s20}. But, one must ask, can one choose so? What if column $q=i$ were unusable? That is, what if the only nonzero elements remaining in~$\tilde I$'s $i$th column stood above the main diagonal, unavailable for step~\ref{gjrank:341:s25} to bring to pivot? Well, \emph{were} it so, then one would indeed have to choose $q \neq i$ to swap the unusable column away rightward, but see: nothing in the algorithm later fills such a column's zeros with anything else---they remain zeros---so swapping the column away rightward could only delay the crisis. The column would remain unusable. Eventually the column would reappear on pivot when no usable column rightward remained available to swap it with, which contrary to our assumption would mean precisely that $r