PROFESSOR: Today, we're going to be solving
a problem from a final exam.
And here it is.
It's about a matrix A, [1, 0, 1; 0, 1, 1; 1, 1, 0].
And we know that this matrix has two eigenvalues, 1 and 2.
And we also know that if we do elimination,
the first two pivots will be 1 and 1.
And here are two questions about this matrix.
The first one is find lambda_3 and d_3, the third eigenvalue
and the third pivot.
And the second one asks you, what is the smallest a_(3, 3)--
so if you can change this entry, what is the smallest number
that you can put there that will make the matrix A positive
semidefinite?
And also, if instead of changing that entry, you do A plus c*I,
what is the smallest number c that will make that matrix,
A plus c*I, positive semidefinite?
There's also a third part to the question,
but we'll get to that later.
Why don't you hit pause and work on these two parts?
And when you're ready, come back and I'll show you how I did it.
Hi.
I hope you managed to do parts A and B. Let's work on it
together.
Part A. Well, we want to know what the third eigenvalue is.
And you know what the first two are.
What else do you know about eigenvalues and the matrix?
You know that the sum of all the eigenvalues of the matrix
is equal to the trace of the matrix.
So lambda_1 plus lambda_2 plus lambda_3
is equal to the trace of the matrix.
In this case, you have 1 plus 2 plus lambda_3
equals to the trace.
The trace is the sum of the diagonal entries.
So, come over here.
The trace is 1 plus 1 plus 0.
The trace is equal to 2.
So we have 3 plus lambda_3 is equal to 2.
So lambda_3 is equal to minus 1.
On to the third pivot.
We don't really want to do elimination.
That would take too long.
So there must be some trick that we can use.
Well, we have the first two pivots,
and we want to know the third.
Remember, when you do elimination steps, that
does not change the determinant of the matrix.
And you're left with an upper triangular.
So the determinant of that matrix
will be d_1 times d_2 times d_3.
And it will still be equal to the determinant
of A. I guess there's a small caveat that I should point out.
The pivots are not always the diagonal entries.
It might be that one of the diagonal entries will be 0.
That happens if the matrix is singular.
But here, all my three eigenvalues are non-zero.
They are 1, 2, and -1.
So that won't happen.
So this is actually possible to do.
The product of the three pivots will
be equal to the determinant of A. And the determinant of A
is the product of the eigenvalues, 1 times 2 times
-1.
So it's equal to -2.
1 times 1 times d_33 is equal to -2.
Here is your third pivot, d_3.
That finishes part A. Is that the result that you got?
Let's do part B. What is the smallest a_(3,3) entry that
would make the matrix positive semidefinite?
Well, first of all, note that A is not positive semidefinite
yet.
The eigenvalues are 1, 2, and -1.
-1 is negative, so the matrix is not positive definite and not
even positive semidefinite.
Positive semidefinite means that all the eigenvalues
will be either positive or 0.
That is, non-negative.
So our matrix will be 1, 0, 1; 0, 1, 1; 1, 1,
and we're allowed to change this third entry.
How do we figure out if this matrix is positive semidefinite
or not?
Well, I was talking about the eigenvalues.
But maybe the easiest way is to do the determinant test.
The determinant of the small one by one
left uppermost matrix is 1.
The determinant of the two by two upper leftmost matrix
is 1 times 1 minus 0 times 0, 1, also positive.
So we need to check that the determinant of the whole matrix
will also be non-negative.
So what is the determinant of this matrix?
It is equal to the three by three matrix.
So do you know how to do it quickly?
There's this way that only works for three by three and not
for bigger.
Which is, the determinant will be 1 times 1 times a_(3,3) plus
0 times 1 times 1.
That's 0.
Plus 1 times 0 times 1 That's 0 again.
Minus 1 times 1 times 1 minus 1 times 1 times 1 minus a_(3,3)
times 0 times 0.
That's 0.
So this is the determinant.
It's a_(3,3) minus 2.
And I want it to be greater than or equal to 0.
This will guarantee that the matrix
is positive semidefinite.
So a_(3,3) must be bigger than or equal to 2.
The smallest value for a_(3,3) that will make the matrix
positive semidefinite is 2.
There's another part to the question still,
which is what is the smallest c that will make the matrix A
plus c*I positive semidefinite?
How should we do this?
The quickest way is to do the eigenvalue test.
A has eigenvalues 1, 2, and -1.
So A plus c*I has eigenvalues-- well,
you're just adding c*I to the matrix.
And in this particular case, you should know by now
that that keeps the eigenvectors the same
and adds the number c to each of the eigenvalues.
And I want each one of these to be non-negative.
For that to be true, I have to have
c greater than or equal to 1.
So the smallest value that c can take that
will make the matrix A positive semidefinite is 1.
That solves parts A and B of this question.
There is a part C to this question.
Let me show it to you.
It's says: starting with one of these three vectors, [3, 0, 0],
[0, 3, 0], or [0, 0, 3], and with u_(k+1) equals to a half
of A times u_k, what is the limit behavior of u_k as k goes
to infinity?
I've written the matrix one half of A here for your convenience.
And now, you can hit pause and work on it.
And when you're ready, we'll get back and solve it together.
I hope you managed to solve this one.
Now let's do it together.
Well, if you've noticed, the matrix one half of A
is a Markov matrix.
So there are all these results about Markov matrices
and steady states and so on.
Usually, Markov matrices have a unique steady state,
but that is only true when there are no non-zero entries.
But here, there are.
So we can't guarantee that there's a unique steady state.
What we can do is look at the eigenvalues
and see if this is still true nonetheless.
What are the eigenvalues of A-- of one half of A?
Well, if you remember from part A, the eigenvalues of A
were 1, 2, and -1.
So the eigenvalues of one half of A-- taking a multiple
does not change the eigenvector, but it changes the eigenvalue
by the same multiple.
It would be 1/2, 2 divided by 2 is 1, and minus 1/2.
So here are the eigenvalues of A.
And there's only one eigenvalue that
has absolute value equal to 1.
So you actually still get a unique steady state vector.
So everything is fine.
We can proceed as usual.
And the usual procedure is you find the eigenvector
corresponding to that eigenvalue, 1.
And that will be the limit behavior
as k goes to infinity of u_k.
So what is the eigenvector corresponding to 1?
Eigenvector.
Well, you already know how to do this,
so I will just write the solution.
It is [1, 1, 1].
That means that u_k, as k goes to infinity,
will converge to some appropriate multiple
of this eigenvector [1, 1, 1].
How do you know which multiple to use?
Well, as usual in Markov matrices,
when you do an iteration of the process,
when you do u_(k+1) is equal to one half of A times u_k,
that does not change the sum of the entries of the vector u_k.
So whatever the sum was here, it will still be the same here.
If you go all the way back and you
start with u_0, whatever the sum of the entries was here,
that's what it will be all the way through u_1, u_2, u_3,
and so on, all the way to the steady state, u_infinity.
So whatever the multiple of [1, 1, 1],
it has to have the sum of these entries add up to 3.
Well, that's already there.
We already happened to pick the correct eigenvector,
so that's very convenient.
The correct multiple is simply the vector [1, 1, 1].
So the limit behavior of u_k as k goes to infinity
is u_infinity equal to [1, 1, 1].
We're done.
Thank you.