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 are and the relations between them can help you understand and 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 about this field in particular. -Doctor Keith, The Math Forum Check out our web site! http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2015 The Math Forum