Notes preparatory to "rank"
            ===== =========== ==  ====

    [If at any time you wish to exit this page, 
     please click your browser's [Back] button.]

  This note contemplates a  k  by  n  matrix  A .

  Whenever a  k-deep column matrix  b  is given,
we may inquire whether there are any  n-deep columns  x
for which the matrix equation
        
(#)     A x = b

is valid.

  This equation is just the matrix counterpart of a
certain corresponding system of simultaneous linear equations
whose coefficient matrix is  A ,  and whose augmented matrix  M
has the form

        M = [ A | b ] .
	
  What do we really know about  A  if we know that,

(1)     for each conceivable  k-deep column matrix  b ,
        equation (#) always has one or more solution(s)  x ?

  Certainly we know that the fully reduced row echelon form (frref)
of the augmented matrix  M  never has any "embarrassing" row
starting with  n  zeros but ending with a non-zero entry
in the last column, and this regardless what the original
k-deep column matrix  b .  But this means exactly that 

(2)     the frref of  A  itself has no row of zeros whatsoever.

(From this condition on  A , in turn it is easy to deduce (1).)

  (Of course (1) or (2) can happen ONLY if there are 
at least as many variables as equations, i.e.,  k </= n .)

  And we know, in particular, using as  k-deep column matrix  b 
the various columns of the  k  by  k  identity matrix  I_k , that 

(3)     there is an  n  by  k  matrix  X  with  A X = I_k 

(as each column of  X  just use any solution  x  to the instance 
of equation (1) in which  b  is the corresponding column of  I_k ).

  From (3) in turn we can again deduce (1): for if  A X = I_k , 
and if column  b  is given, we may set  x = X b .  Then  x  is
an  n-deep column and

        A x = A (X b) = (A X) b = I_k b = b ,

as required.

---

  A new question: what do we really know about  A  if we know that

        when  b  is the  k-deep column matrix with zeros 
(a)     everywhere, equation (#) never has any solutions  x  
        OTHER THAN  the "trivial" solution with each  x_i = 0 ?

  The first thing to observe is that (a) is the case if, and only if,
none of the variables  x_i  is "free" -- that is, each  x_i  is "bound"
-- equivalently, in the frref of  A , there is, for each variable  x_i ,
a row whose leading  1  appears in the  i^th position -- which means:

(b)     the frref of  A  has  n  non-zero rows.

(In particular, we must have  n </= k .)
 
  In fact, the frref of  A  is then a matrix (with at least  n  rows) 
whose first  n  rows constitute the identity matrix  I_n :

                   | I_n |
(c)     frref(A) = | --- |
                   |  0  |

In consequence,

(d)     there is an  n  by  k  matrix  Y  with  Y A = I_n .

(Indeed, if  E  is the invertible matrix,  k by k , product of 
elementary matrices, corresponding to any sequence of elementary 
row operations that reduce  A  to its frref, it's enough to set

        Y = the first n rows of  E ,

                 | I_n |
for since  E A = | --- |  it then follows that  Y A = I_n .)
                 |  0  |

  Not only does (d) follow from (a) (via (b) and (c)), 
however, but also conversely, (a) follows from (b): 
for, whatever the solution  x  to  A x = 0 ,
if we really have a  Y  with  Y A = I_n , then  

        x = I_n x = Y A x = Y 0 = 0 .

---

  Conditions (1) (2) and (3) thus all mean the same thing 
about  A , and force the inequality  k </= n , while, independently,
conditions (a) (b) (c) and (d) also mean the same thing about  A ,
and force the opposite inequality  n </= k .

  This means, in particular, that an invertible matrix -- a matrix
A  (suppose it  k  by  n , still) for which there is a matrix  B  
(necessarily  n  by  k  so that both products can be available)
satisfying both  A B = I_k  and  B A = I_n  -- must be square.
That is, we must have  n = k .

  In fact, a matrix  A  satisfying BOTH any one of (1) (2) or (3) 
AND ALSO any one of (a) (b) (c) or (d) MUST SATISFY ALL OF THESE
-- and be square -- and be invertible.

  And for matrices  A  that happen already to be square ( n = k )
the situation is even nicer: as soon as  n by n  A  satisfies ANY ONE 
of the seven conditions (1), (2), (3), (a), (b), (c), or (d), it will
satisfy them ALL -- for its frref will be  I_n .