[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 Ik×k , that
(3) there is an n-by-k matrix X with A•X = Ik×k
(as each successive column of X just use any solution x to the instance of equation (#) in which b is the corresponding column of Ik×k ).
From (3) in turn we can again deduce (1): for if A•X = Ik×k , and if column b is given, we may choose to set x = X•b . Then x is an n-deep column and
A•x = A•(X•b) = (A•X)•b = Ik×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 xi = 0 ?
The first thing to observe is that (a) is the case if, and only if, none of the variables xi is "free" -- that is, each xi is "bound" -- equivalently, in the frref of A, there is, for each variable xi , a row whose leading 1 appears in the ith 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 In×n :
| In×n |
(c) frref(A) = | ----- | .
| 0 |
In consequence,
(d) there is an n-by-k matrix Y with Y•A= In×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 ,
| In×n |
for since E•A = | ----- | , it then follows that Y•A = the first n rows of E•A = In×n .)
| 0 |
Not only does (d) thus follow from (a) (via (b) and (c)), however, but also conversely, (a) follows from (d):
for, whatever the solution x to A•x = 0 , if we really have a Y with Y•A = In×n , then
x = In×n•x = (Y•A)•x = Y•(A•x) = Y•0 = 0 .
---
Conditions (1) (2) and (3) thus all mean some same thing about A, and force the inequality k < n ; while, independently, conditions (a) (b) (c) and (d) also mean some (other) 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 = Ik×k and B•A = In×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 In×n .
--- Back --- First posted 13 Feb 2004.
