# Nontrivial Solutions for AX=0

1. Jul 28, 2003

### StephenPrivitera

Theorem 2.3.3
A homogeneous system of m linear algebraic equations in m unknowns has no nontrivial solutions iff the reduced coefficient matrix has no rows consisting entirely of zeros.

So in other words, if no row of the matrix consists entirely of zeros, then the only solution is X=0.

This is what my book teaches me before determinants. When it introduces determinants, it asks as an exerice to rewrite the theorem using the determinant.

The book rewrites it,
...iff the determinant does not equal zero.

p->q
p->r
q->p
r->p
Thus
r->q and q->r
Which means that if there are no rows consisting entirely of zeros, then the determinant is not zero. This is clearly false, since a determinant can be zero if two rows are proportional. I feel like my book has lied to me again.
I at first trusted my book over my own belief, and when it told me to determine for what values of a (some coefficient) does this system has nontrivial solutions, I set up an upper-triangular determinant, multiplied the elements along the principal diagonal and set it equal to zero. This process yields solutions which are trivial. Admittedly, it would have been a lot easier to set the last element in the last row equal to zero, but I thought this would omit some possibilities.

For instance,
x+y=ax
-x+y=ay
Using the above procedure, I get a=1 as one of the possibilities.
Am I completely off with this accusation?

Last edited: Jul 28, 2003
2. Jul 28, 2003

### arcnets

The theorem states:

reduced coefficient matrix has no rows consisting entirely of zeros
=>
no nontrivial solutions

What you must prove, is:

determinant does not equal zero
=>
no nontrivial solutions

So, what's left to prove is:

determinant does not equal zero
=>
reduced coefficient matrix has no rows consisting entirely of zeros

This is logically the same as

reduced coefficient matrix has at least one row consisting entirely of zeros
=>
determinant equals zero.

This should be easy if you use Cramer's rule.

3. Jul 28, 2003

### StephenPrivitera

So in other words, the fact that a system has a nontrivial solution does not imply that the determinant of the coefficient matrix is zero and the fact that the determinant is zero does not imply that the system has a nontrivial solution. But if the determinant is not zero then its only solution is trivial.

My problem was that when a=1, the system only has the solution x=y=0 and the determinant is also zero. I saw this as a contradiction to the theorem, but if I am understanding you correctly, my logic was wrong. And so this is not a contradiction to the theorem.

Looking back on the problem, the determinant isn't zero. It's one. That's very perturbing. When I was setting up the determinant I multiplied a row by 1-a, but if a=1, then that's equivalent to multiplying by zero.

BTW, I don't know Cramer's rule.

4. Jul 29, 2003

### HallsofIvy

Staff Emeritus
"For instance,
x+y=ax
-x+y=ay
Using the above procedure, I get a=1 as one of the possibilities."

I assume this is the "a" you are referring to when you say:
"My problem was that when a=1, the system only has the solution x=y=0 and the determinant is also zero."

If a= 1, then x+ y= x and -x+ y= y. The matrix form of this is

[ 1 1][x] = [x] but this is NOT of the form Ax= 0.
[-1 1][y] [y]

You need to rewrite it as [1 1][x]= [1 0][x]
[-1 1][y]= [0 1][y]
which is the same as [0 1][x] = [0] (you would get the same thing
[-1 0][y] [0]
if you rewrite the equations as y= 0 and -x= 0).

Yes, that has the single solution x= y= 0 but the determinant is
1, not 0.

The general problem x+y= ax, -x+ y= ay can be rewritten as
(1-a)x+ y= 0, -x+ (1-a)y= 0 which, in matrix form, is
[1-a 1][x] = [0]
[-1 1-a][y] [0].

The determinant is (1-a)2+ 1. Setting that equal to 0,
(1-a)2+ 1= 0 is the same as (1-a)2= -1 and so has roots a= 1+ i and 1- i, not a= 1.

It IS true that a system of the form Ax= 0 has a non-trivial solution (in fact, has an infinite number of solutions) if and only if the determinant of the coefficient matrix is 0. And THAT is true if and only if the row reduced form of the matrix has at least one row of 0s.

The point is this: if you row-reduce a matrix getting it to either diagonal or triangular form, WITHOUT dividing or multiplying a row by a number (only using "add a multiple of one row to another"), then the determinant is the product of the numbers on the diagonal.
(If you swap two rows, the determinant is multiplied by -1. If you multiply a row by a number, the determinant is multiplied by that number. If you add any multiple of one row to another, the determinant is not changed.)

If you can row-reduce the matrix to diagonal or triangular form so that it has a 0 on the diagonal, then it's determinant is 0. Of course, that happens if one of the rows is all 0s.

5. Jul 29, 2003

### StephenPrivitera

Ok,ok, just one more thing.
Is this true:
The determinant of the coefficient matrix is zero if and only if the reduced coefficient matrix has at least one row of zeros.
(q<-->r)

p= AX=0 has nontrivial solutions
q= the determinant of the coefficient matrix is zero
r= the reduced coefficient matrix has at least one rows of zeros

We know that,
r<-->p
r->q
q<-->p

Therefore, since q->p and p->r, q->r
So it seems right to me that q<-->r, but it's been years since I've studied logic, so who knows.
I just want to know because if q->r is true, then if there is a zero in the prin. diagonal in the reduced matrix, then there must also be a row of zeros. Correct?

QUOTE:
if you row-reduce a matrix getting it to either diagonal or triangular form, WITHOUT dividing or multiplying a row by a number (only using "add a multiple of one row to another"), then the determinant is the product of the numbers on the diagonal.
____
What's wrong with multiplying a row by a number as long as I also multiple by the reciprocal? Or do you mean when there are unknowns, I should avoid this practice so I don't accidentally multiply by zero? Kind of like you're not supposed to divide an equation by x?

6. Jul 29, 2003

### arcnets

I think this is true. HallsofIvy said so, too.
As long as you're only interested in the determinant being zero or not, you may multiply (of course not by zero) and swap as you like. The determinant will never change from zero to non-zero or vice versa.

7. Jul 30, 2003

### HallsofIvy

Staff Emeritus
Well, if I said it, it MUST be true!

Not sure I understand this. If you multiply a row by a number and the multiply the SAME row by the reciprocal- you haven't changed it.

Here's and example:

Find the determinant of [2 2]
[4 3] by row-reduction.

Some people (especially if they've just learned row-reduction to find inverse matrices) prefer to reduce to a 1 on the diagonal (that makes it easier to decide what to multiply by to get 0s on the other rows).

Here, you can divide the first row by 2, then subtract 4 time that (new) first row from the second row to get
[1 1]
[0 -1]

Now, we can divide the second row by -1 then subtract the new second row from the first row to get the identity matrix:
[1 0]
[0 1]

Obviously, that by itself doesn't tell us the determinant of the original matrix. However if we kept track of the numbers we divided by we can say that we, essentially, "factored out" a 2 and a -1 so that the determinant is 2(-1)= -2.

The way I would prefer to do this problem is to simply subtract twice the first row from the second row to get

[2 2]
[0 -1]- a triangular matrix. BECAUSE I have not multiplied or divided a row by a number (or swapped two rows), I know that the determinant of this matrix is the same as the determinant of the original matrix- and the determinant of a triangular matrix is just the product of the numbers on the main diagonal: -2.

8. Jul 30, 2003

### StephenPrivitera

The way I would prefer to do this problem is to simply subtract twice the first row from the second row to get
...
Yes, you're right. This is a much better approach.
I had been multiplying rows by number so that I could add them together and make some elements disappear, but I might as well do that in the same step.

As for the multiplying by the reciprocal part, what I meant was this:
If you multiply a row of the determinant by a factor of n, then the value of the determinant has changed by a factor of n. So why can't I multiply a row by n and the determinant by 1/n, so that the value isn't changed? From what you said, I can, it's just more unnecessary work.

I'm sorry for not believing you... But I really wanted to make that other part really clear. For instance, it bothers me that this determinant is zero, but doesn't have a row of zeros.
1 2 3 4 5
0 1 2 3 4
0 0 0 1 2
0 0 0 1 2
0 0 0 0 1
My only guess is that this doesn't fit the definition of "reduced."

__________
(especially if they've just learned row-reduction to find inverse matrices)
That's me - Topic for next week!

Last edited: Jul 30, 2003
9. Jul 30, 2003

### HallsofIvy

Staff Emeritus
Here's an even easier example:

[ 1 1]
[ 1 1] has determinant 0 but does not have a zero row.

You are right. The difference is that it is not "row-reduced".
We can "row reduce" it to
[ 1 1]
[ 0 0] which does have a row of zeros.

The example you give:
[1 2 3 4 5]
[0 1 2 3 4]
[0 0 0 1 2]
[0 0 0 1 2]
[0 0 0 0 1] is not row-reduced. It's determinant is 0 because it has two rows exactly the same- and because it has two rows exactly the same, we can row reduce it to

[1 2 3 4 5]
[0 1 2 3 4]
[0 0 0 0 1]
[0 0 0 0 0]
[0 0 0 0 0]

A matrix has determinant 0 if and only if it can be row-reduced to a triangular form that has at least one row consisting entirely of 0s.

That follows from:

1) Dividing an entire row by a number divides the determinant by that number.
2) Swapping two rows multiplies the determinant by 0.
3) Adding a multiple of one row to another does not change the determinant.

together with: The determinant of a triangular matrix is the product of the numbers on the main diagonal.

10. Jul 31, 2003

### HallsofIvy

Staff Emeritus
Blasted typo:

The fifth line from the bottom should be:

2) Swapping two rows of a matrix multiplies the determinant by -1
(not 0).

11. Jul 31, 2003

### Hurkyl

Staff Emeritus
I think that reduced matrix should be

[1 2 3 4 5]
[0 1 2 3 4]
[0 0 0 1 2]
[0 0 0 0 1]
[0 0 0 0 0]

12. Aug 1, 2003

### HallsofIvy

Staff Emeritus
Yes, I just noticed that. Thank you.