Need some guidance on Linear Algebra proofs

[Chris B]

First, let me say that I am a senior physics undergrad. I have failed Linear Algebra once before. Otherwise I am a straight A student. I'm also taking Ordinary Differential Equations right now, and I breeze through that class without a care in the world. I'm not sure if I've developed some sort of mental block, or just convinced myself that I can't do it, but I find the LA bewildering and frustrating, and my professor has been no help at all. I have absolutely no problem with the "math" side of things. Once operations have been defined I can solve any matrix or vector problem I'm given, but when the book asks me to "prove" something I'm often at a loss, unless I can prove it merely by performing some operations that reduce to the problem to the thing I'm trying to prove.

Anyway, here's an example of a proof that I am unable to figure out:

Homework Statement

Show that if ad-bc=0, then the equation Ax=0 has more than one solution. Why does this imply that A is not invertible? [Hint: First, consider a=b=0. Then, if a and b are not both zero, consider the vector x=<-b,a> (sorry, I tried to latex this up, but I don't know enough about it. x is a column vector).

Homework Equations

Theorems I suppose? The definition of the inverse matrix?

The Attempt at a Solution

I actually have the solution manual, and it walks through the answer step by step and I do not understand the process by which it got to an answer. It says that if you follow the hint you get a nonzero solution. Okay, I don't quite follow why that matters. Then it says to set x2 to <-b, a> and -cb+da=0 which is a non-trivial solution? I don't understand this part either. Then it says that Ax=0 has more than one solution which means it's not invertible. I just don't follow the logic... or maybe logic in general.

Is there a way to state this that's more "mathy" and less "proofy" that doesn't rely on my having to remember like 7 theorems?

 

[wabbit]

I don't quite get where you're getting stuck. Following the hint, you do see that $\begin{pmatrix}a & b\\c & d\end{pmatrix}\begin{pmatrix}-b\\a\end{pmatrix}=\begin{pmatrix}0\\0\end{pmatrix}$, so that $\begin{pmatrix}-b\\a\end{pmatrix}$ is a solution. if it's nontrivial that makes two with the trivial solution. So the function $v\rightarrow Av$ carries two different vectors to the same (zero) vector.

 

[Chris B]

I'm getting stuck on the logic portion of it. I can multiply it out, but why does that prove it's not invertible.
More importantly why did they pick (-b and a) to be the entries for x₂ in the first place? Yes, I know the hint says to do it, but why?

 

[wabbit]

I edited my first post, does that help ?

 

[Chris B]

Maybe. A matrix is invertible if it only has the trivial solution?

 

[wabbit]

No but a matrix is invertible iff the map $v\rightarrow Av$ is.

Edit : misread you. You meant if the equation Ax=0 has only one solution - yes, for the reason above (think of the map)

 

[vela]

If f(x)=Ax is invertible, that means for any value of f(x), you can find a unique x that maps to it. You have two vectors that map to 0. Do you see why that's a problem?

 

[wabbit]

You need to be more careful with your notations, it's hard to see what you mean and it might add to your confusion. "f(x)=Ax" is an equation, I don't know what it means to say it's invertible.

 

[Chris B]

wabbit: Sorry, I don't actually understand the meaning of what you've written. "iff" is if and only-if, which I remember from CS 101, and we just learned about maps being matrix transformations(?), but I don't follow v--> Av.

vela: Theorem 5 in my book says that Ax=b (it drives me a little bananas how we switch between these different ways of writing matrix equations, but that's another issue) and A is invertible then there's a unique solution which is the inverse of A times b. This problem was asking me to prove Theorem 4 in the same chapter and I guess I sort of assumed I could only use the information we had been given up to that theorem. Possibly a bad assumption on my part.

 

[Mark44]

The only way that the matr

Maybe. A matrix is invertible if it only has the trivial solution?

This doesn't make any sense, because "it" refers back to the matrix, which is not something that has a solution, trivial or otherwise.

A matrix A is invertible if and only if the equation Ax = 0 has only a single solution; i.e., x = 0. To be clearer in what you write, minimize the use of the pronoun "it" unless there is no uncertainty about what "it" represents.

Linear Algebra is a more difficult class than, say, calculus or differential equations, primarily because you are expected to prove statements in linear algebra. Calculus and DE are more procedural, meaning you follow certain "canned" recipes. The abstract thinking that is required in linear algebra requires a different mindset than simply plugging things into a standard recipe, which makes it harder for a lot of students.

 

[wabbit]

OK that's one thing to work on. Understanding the correspondence between matrices and maps is essential, and you should spend a bit of time wigh your textbook reviewing that. "$v\rightarrow Av$" means "the map that carries a vector v to the vector Av".

Edit : you've got many responders now so not to confuse you I'll step out for now.

 

[Mark44]

wabbit: Sorry, I don't actually understand the meaning of what you've written. "iff" is if and only-if, which I remember from CS 101, and we just learned about maps being matrix transformations(?), but I don't follow v--> Av.

This is just notation. If you multiply v by A, you get Av, so A maps a vector v to its image Av.

vela: Theorem 5 in my book says that Ax=b (it drives me a little bananas how we switch between these different ways of writing matrix equations, but that's another issue) and A is invertible then there's a unique solution which is the inverse of A times b.

The notation Ax means the product of A and x, in that order. It's simpler to write a single letter A than to write the whole matrix.

If A is invertible (A^-1 exists), then you can multiply both sides of Ax = b by A^-1.
Ax = b
=> A^-1Ax = A^-1b
=> Ix = A^-1b
Or more simply, x = A^-1b

This problem was asking me to prove Theorem 4 in the same chapter and I guess I sort of assumed I could only use the information we had been given up to that theorem. Possibly a bad assumption on my part.

 

[Chris B]

This is just notation. If you multiply v by A, you get Av, so A maps a vector v to its image Av.
The notation Ax means the product of A and x, in that order. It's simpler to write a single letter A than to write the whole matrix.

If A is invertible (A^-1 exists), then you can multiply both sides of Ax = b by A^-1.
Ax = b
=> A^-1Ax = A^-1b
=> Ix = A^-1b
Or more simply, x = A^-1b

I get all that. That's just algebra with matrices and vectors. Could I have just said that when ad-bc=0 that the inverse is undefined because 1/0 is undefined?

 

[vela]

No. The problem is asking you to explain why if there's more than one solution to Ax=0, A is not invertible. It's not asking you why A isn't invertible if ad-bc=0.

 

[Mark44]

I get all that. That's just algebra with matrices and vectors.

Sort of, but not exactly. Some of the properties you take for granted with the real numbers don't apply to matrices. For example, if a and b are reals, then ab = ba, but if A and B are matrices, then AB is not necessarily equal to BA. IOW, the commutative property of multiplication doesn't apply.

Could I have just said that when ad-bc=0 that the inverse is undefined because 1/0 is undefined?

I don't think that would have been accepted.

Here is from your first post in this thread.

Show that if ad-bc=0, then the equation Ax=0 has more than one solution. Why does this imply that A is not invertible? [Hint: First, consider a=b=0. Then, if a and b are not both zero, consider the vector x=<-b,a>

Before showing that ad - bc = 0 implies that A is not invertible, you are asked to show that Ax = 0 has more than one solution. Use the hints to guide your work. For the first hint, with a = b = 0, you are solving this system of equations:
0x + 0y = 0
cx + dy = 0
Can you show that this system has more than one solution?

In the second hint, you are solving this system:
a(-b) + ba = 0
c(-b) + da = 0
Can you show that this system has more than one solution? Don't be concerned about how they came up with the vector <-b, a>. Just consider it to be a free gift...

 

[Chris B]

Okay, let me see if I can follow what's going on here, because I think there's a lot that's implied but not stated outright.

I'm trying to show that when ad-bc = 0 there's more than one solution for x in Ax=0.
We splitting it up into two different scenarios, on where a and b are zero and one where they're anything else.
When a=b=0 the solutions are x₁, x₂ = 0,0 OR d, -c OR -d, c
That covers a=b=0
Okay when a and b can be any other number then <-b,a> is a solution...?
a(-b)+b=0, okay that works
c(-b)+da=0, this I'm not so sure. so either c and d are 0, or... I think this is where I'm stuck. We're assuming <-b, a> is a solution, but I'm not sure that it is, unless c=a and d=b? But, that doesn't cover every situation, right?

 

[vela]

You're assuming ad-bc=0 and showing that as a consequence <-b, a> is a solution. You're not assuming <-b, a> is a solution.

 

[Chris B]

So, we showed that ad-bc=0 if <-b, a> is a solution, and that also <0, 0> is a solution?

 

[vela]

Not exactly. You want to show if ad-bc=0, then <-b,a> is a solution. In other words, if you take as given that ad-bc=0, then <-b,a> is a solution. This is different logically from saying if <-b,a> is a solution, then ad-bc=0. It's the difference between "p implies q" and "q implies p."

 

[Chris B]

Not exactly. You want to show if ad-bc=0, then <-b,a> is a solution. In other words, if you take as given that ad-bc=0, then <-b,a> is a solution. This is different logically from saying if <-b,a> is a solution, then ad-bc=0. It's the difference between "p implies q" and "q implies p."

Yeah, I think this is some of the essential kind of information I'm missing. These kind of logic statements are pretty foreign to me, so I don't actually know the difference between p implies q and q implies p. They look like they mean the same thing to me.

 

[Mark44]

Yeah, I think this is some of the essential kind of information I'm missing. These kind of logic statements are pretty foreign to me, so I don't actually know the difference between p implies q and q implies p. They look like they mean the same thing to me.

But they aren't the same. Here's an example of two statements
P: My pet is a dog.
Q: My pet is a mammal.

The implication $P \Rightarrow Q$ says that "if my pet is a dog, then my pet is a mammal." Pretty obviously, this is a true implication.
In the reverse order we have $Q \Rightarrow P$, which says, "if my pet is a mammal, then my pet is a dog." This one is not true if my pet happens to be a cat or hamster or any mammal that isn't a dog.

 

[LCKurtz]

Do these statements look the same to you:
If a polygon is a square then it is a rectangle.
If a polygon is a rectangle, then it is a square.

 

[Chris B]

Okay, I'll give it one more go...

ad-bc=0
Ax=0
if we plug <-b,a> for x we get,
a(-b)+b(a)=0
and
c(-b)+d(a)=0, which is ad-bc=0
so ad-bc=ad-bc when x=<-b,a>?

 

[Mark44]

Okay, I'll give it one more go...

ad-bc=0
Ax=0
if we plug <-b,a> for x we get,
a(-b)+b(a)=0
and
c(-b)+d(a)=0, which is ad-bc=0
so ad-bc=ad-bc when x=<-b,a>?

Well, ad - bc always equals itself, independent of whatever x happens to be.

To summarize what you found (and to organize it more),

Assuming that ad - bc = 0, and that x = <-b, a>
then Ax = 0 can be written as the system
a(-b) + b(a) = -ab + ab = 0
c(-b) + da = ad - bc = 0
We can conclude that x = <-b, a> is a solution to the equation Ax = 0.

You're not done, though. The goal was to show that the equation Ax = 0 has multiple solutions if ad - bc = 0. There is another very obvious solution to Ax = 0.

 

[Chris B]

Right, x=0 .