Associated Topics || Dr. Math Home || Search Dr. Math

### Matrix Pattern Tells Solution Set?

Date: 9/4/96 at 1:37:24
From: KATHY H DOAN
Subject: Matrix Pattern Tells Solution Set?

Is there a pattern for reduced row-echelon form matrices that can
differentiate whether the solution set has no solutions, exactly one
solution, or infinitely many solutions?

I want to be able to tell what kind of solution set a reduced row-
echelon matrix has just by looking at it.

For example:  --            --
|    1 0 0 a   |
|    0 1 0 b   |
|    0 0 1 c   |
--            --

I know that this has infinitely many solutions, but what would
dependent and inconsistent matrices look like?  Is there a set
pattern?

Thanks.
Kathy

Date: 10/18/96 at 18:19:26
From: Doctor Keith
Subject: Re: Matrix Pattern Tells Solution Set?

Hi Kathy,

You are asking some great questions, and yes there is a relation.

I am assuming from your question that you have had some linear
(matrix) algebra before, so I will give you a quick run-down of what
and why. For more details I recommend Gilbert Strang, _Linear Algebra
and its Applications_.  If something I say is confusing or you are not
sure about it, email your concerns and I will be happy to explain
further. I am deliberately assuming some knowledge since this is
usually a semester course in college to deal with this problem and
methods of solution.  When we are solving a system of linear equations
of the form of:

Ax=B
A is a real m by n matrix (m rows and n columns)
x is a real n by 1 matrix (a column vector with n unknown elements)
B is a real m by 1 matrix (a column vector with m elements)

for the unknown vector x we need to be concerned with the formulation
of the problem.  That is as you pointed out we could get many
solutions, one solution or none.

Have you ever heard of the four fundamental spaces?  Knowing what they
remember all the conditions for when you will get a solution, and how
many you will get.  To answer your question we only need to look at
two of the spaces (thus saving alot of reading for you and writing for
me).

1) Null space of A:  This is basically the set of all vectors z that
satisfy the equation:
Az = 0

Why do we care? Well consider the following:
Let y = x+z
then Ay = Ax + Az = Ax = b
thus if x is a solution then so is y

In other words we can get infinitely many solutions by adding az
to x and varying a.  The Null space of A thus controls the possibility
of infinitely many solutions. For one solution we want no vectors in
the null space, and for infinitely many solutions we want at least one
vector in the null space.

How can you check this using a reduced form as you have?  Well
you gave me that some matrix say C is:

C=| 1  0  0  a |
| 0  1  0  b |
| 0  0  1  c |

and that this matrix was reduced from A:

EA = C  or  A = EinvC  with Einv = inverse of E (which exists
for the elementary matrices used to
calculate C from A)
thus if Az = 0  and E is invertible then Cz=0

Now we have a condition based on your reduced matrix.
So when does Cz=0?  In your example we have 4 columns in C and
only three rows.  You can verify that there exists one vector
in the null space, thus there are infinitely many solutions, as
you mentioned.  Whenever the number of columns exceeds the number
of rows we will have ambiguity (vectors in the null space), but
this is not the only condition.  The general condition (which
includes this as a special case) is, if the rank of C is less
than the number of columns we will have ambiguity.  Well what is
rank?  There are a lot of ways of calculating it but in this case
here are the three easiest:

rank(C) = # linearly independant columns of C
= # linearly independant rows of C
= # pivots (nonzero elements on the main diagonal)
the last condition is the easiest in the case you supplied.

Let's calculate:
# vectors in the null space of A = # columns - # pivots
= 4 - 3 = 1
One vector in null space means you  will have infinetly many
solutions if you have a solution.

2) The other space you care about is the Range Space of A.  The
Range of A (as it is often called) is informally a collection
of all the vectors that can be formed by multiplying a vector
times A.  What happens when B is not in the Range of A?  Well
no vector, and that includes x, that multiplies A can produce
B!  Thus no solution exists.  So in order to get a solution
we must have B in the Range of A.  So how do we figure this out
given your reduced matrix C?  Well one relation that is
particularly helpful is the Range of A is the space spanned by
the linearly independant columns of A.  In english this means
that any vector in the Range of A (ie B) can be written as a
linear combination of the columns of A.  Thus if you can write
it this way you are done. You should be saying about now that
while this is cool, it depends on the columns of A, not C.
Unfortuneately Range of A is not the Range of C (like we had
above with Null of A was the Null of C), but one important
relation connects the two.  If the rank of A is equal to the
number of rows of A then any B is in the Range of A. Since the
rank of A is the rank of C, and we can get the rank of C as
described above, we can easily check if any vector B we are
given will have a solution by:

if # rows - # pivots = 0 then a solution exists for any B
If this does not hold then you are stuck going back to A and
checking if B can be written as the summ of the columns.  If it
can then a solution exists, if not no solution exists.

Summarizing:
let r= # pivots (non-zero components on main diagonal)
let m= # rows
let n= # columns
r <= m  and r <= n for all matrices

if r = m (m - r = 0) then a solution exists for all B
if r < m (m - r > 0)then you must see if B can be written as a
combination of the columns of A
if r = n (n - r = 0) then any solution is unique
if r < n (n - r > 0) then if a solution exists then there are
infinitely many solutions

I hope this helps. This is fun and a very, very useful area of math
(it is used in engineering, physics, etc all the time) and you will
be well ahead of the game if you understand it.  I know I rushed it
but I was trying to strike a balance between meeting the need with
some understanding of what is going on, and typing you a textbook.
Let me know if you want something further explained, I love to talk

-Doctor Keith,  The Math Forum
Check out our web site!  http://mathforum.org/dr.math/

Associated Topics:
College Linear Algebra

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search