Diagonalization of a matrix

Khallil

Oct 10, 2015 13:46

Does anybody know of (or can give) a simple explain for finding a matrix $P$ that satisfies $P^{-1} AP$ being diagonal for a given matrix $A$? Also, can anybody explain the importance of eigenvalues for carrying this out and the benefits of finding diagonal matrices?

Martin Sleziak

As far as applications of diagonalizations are concerned, there are many of them. One quick observation: If $A=PDP^{-1}$ then you can easily calculate $A^{100}$, $A^{1000}$, etc. (You can do this much faster than computing power of the original matrix.)

@Khallil Obvious question. Have you checked Wikipedia?

Also did you try looking among the posts tagged diagonalization?

Khallil

Didn't even think of checking tags, @Martin.

Thanks! (Sorry for being a bit lazy on this one!)

Martin Sleziak

In any case - do you use row vectors or column vectors @Khallil.

Khallil

Not sure how to answer that one. My text follows row operations more than column operations if that helps, @Martin?

Martin Sleziak

When you read a word vector, is it something like this: $\vec v= (1,1,0,-1)$?

Or something like this $\vec v=\begin{pmatrix}1\\1\\0\\-1\end{pmatrix}$?

Khallil

Oct 10, 2015 13:58

Nope, often the transpose of that.

Yep, the latter (and former with a transpose sign).

Martin Sleziak

I.e., the column vectors.

Ok, so let us try to think about the problem we have.

Khallil

Let's do this!

Martin Sleziak

We want $A=PDP^{-1}$.

This is equivalent to finding regular matrix $P$ and diagonal matrix $D$ such that $AP=PD$.

Right?

Khallil

Haven't come across regular before, @Martin.

Is it a special property?

Martin Sleziak

We want a matrix which has inverse.

If you are using inverse matrix, you are probably aware that not all matrices have inverse matrix.

Khallil

Oct 10, 2015 14:00

Oh yes of course. I see what you mean.

Martin Sleziak

And maybe you also know that $n\times n$ matrix has inverse if and only if rank is $n$.

Did you see such result?

Khallil

Yep, I recall proving such a result.

Martin Sleziak

Ok, so we know all we need.

Once again we want this:

$$AP=PD\tag{1}$$

All matrices there are $n\times n$.

Let us denote the diagonal elements of $D$ by $d_1,...,d_n$.

Khallil

That makes sense so far.

Martin Sleziak

Let us denote columns of the unknown matrix $P$ by $\vec v_1,\dots,\vec v_n$.

Khallil

Oct 10, 2015 14:03

(One issue though. My text gives me $A$ and wants me to find a $P$ s.t. $P^{-1} A P$ is diagonal whereas you're seeking a $P$ s.t. $P D P^{-1}$ is diagonal. Are these problems equivalent?)

Martin Sleziak

We can write: $P=\begin{pmatrix}\vec v_1&\vec v_2&\dots&\vec v_n\end{pmatrix}$.

I want to get $AP=PD$. If $P$ has inverse, this is equivalent to $P^{-1}AP=D$.

Khallil

Oh I see what you mean.

Martin Sleziak

And $PDP^{-1}=A$ is equivalent, too.

If we write P as $P=\begin{pmatrix}\vec v_1&\vec v_2&\dots&\vec v_n\end{pmatrix}$, what can we say about $AP$ and $PD$.

Khallil

I have no idea.

Martin Sleziak

I would like to persuade you that:

$$PD=\begin{pmatrix}\vec v_1&\vec v_2&\dots&\vec v_n\end{pmatrix}\operatorname{diag}(d_1,\dots,d_n)=\begin{pmatrix}\vec d_1v_1&\vec d_2v_2&\dots&\vec d_nv_n\end{pmatrix} \tag{2}$$

Khallil

Oct 10, 2015 14:06

Maybe that a linear combination of the $v_i$ is equal to the LHS?

Oh, yea that's what I was thinking.

Martin Sleziak

And that:

$$AP=A\begin{pmatrix}\vec v_1&\vec v_2&\dots&\vec v_n\end{pmatrix} = \begin{pmatrix}A\vec v_1&A\vec v_2&\dots&A\vec v_n\end{pmatrix}\tag{3}$$

Khallil

Can I ask how you got the final equality?

Martin Sleziak

Both these equations should become clear if you think carefully about how product of the matrices work.

For example, can you see that first column in the product in (3) should be $A\vec v_1$?

When I multiply two matrices I always take the row from the first one and column from the second one and use the dot product, right?

Khallil

Yep, I see that.

Sorry for the wait, just had to do a 2x2 example to clarify it.

I see where that comes from now.

@MartinSleziak Are the $d's$ in $(2)$ supposed to be vectors?

Martin Sleziak

Ok. It is ok even if you just believe me that (2) and (3) is true and get to back to think about it later.

@Khallil Yes, I did not write it correctly.

Let me try again.

$$PD=\begin{pmatrix}\vec v_1&\vec v_2&\dots&\vec v_n\end{pmatrix}\operatorname{diag}(d_1,\dots,d_n)=\begin{pmatrix}d_1\vec v_1&d_2\vec v_2&\dots&d_n\vec v_n\end{pmatrix} \tag{2}$$

$d_i$'s are diagonal elements, so they are numbers.

Khallil

Oct 10, 2015 14:11

Yep, I see that now.

So do we equate the $PD$ and $AP$ now?

Martin Sleziak

Good that you spotted the mistake.

@Khallil Exactly. And that means that we want the first column of PD is the same as the first column of AP. And the same for columns 2,3,...,n.

And now we simply check what we get from the first column: We get that we want $A\vec v_1=d_1\vec v_1$.

More generally in the $i$-th column we have $A\vec v_i=d_i\vec v_i$.

So far is it clear?

Khallil

I'm not sure what we can deduce from that final equality.

(Yep, so far it's all clear!)

Martin Sleziak

And this is exactly the place where I want to ask you whether you have already heard of eigenvectors and eigenvalues.

Khallil

Yep, but very briefly. The eigenvectors are the values we get when we solve the characteristic polynomial of a matrix but I don't know how they 'correspond' to eigenvectors.

Martin Sleziak

Because if you have then the equality $A\vec v=d\vec v$ is exactly saying that $d$ is an eigenvalue of $A$ and $\vec v$ is the corresponding eigenvector. (That is, if we are using column vectors, as you do.)

So if you know or look up the definition of eigenvalues and eigenvectors: en.wikipedia.org/wiki/Eigenvalues_and_eigenvectors

Then basically what I did so far is this.

Khallil

Oct 10, 2015 14:17

Oh, I understand now. How can we proceed afterwards?

All the $d_i$ are eigenvectors of $A$?

Martin Sleziak

If we want $PD=AP$ then we want eigenvalues on the diagonal of $D$ and eigenvectors as column of $P$.

@Khallil $d_i$'s are eigenvalues

$\vec v_i$'s are eigenvectors

So if we have some method to compute eigenvalues and eigenvectors we are almost done.

But we still need to make sure that $P$ has inverse, i.e., that rank of P is n.

This means that we want $\vec v_i$'s to be linearly independent.

So I tried to persuade you about this: If we can find n linearly independent eigenvectors and the corresponding eigenvalues, then we can solve the original problem.

Khallil

Yep, so we want $n$ linearly independent eigenvalues.

Martin Sleziak

n linearly independent eigenvectors

Khallil

Oh, is there an important distinction?

Martin Sleziak

Ok, so you said that you know how to compute eigenvalues (roots of the characteristic polynomial).

@Khallil The distinction is that if I want to talk about linear independence, I need vectors. The eigenvalues are numbers, they are not vectors.

Khallil

Oct 10, 2015 14:22

Oh, I see. Yea that makes sense.

Martin Sleziak

Ok, so now if somebody gives you a matrix A, you can calculate characteristic polynomial and if you can find roots, you have n eigenvectors.

(Or less than n, if there are multiple roots.)

Khallil

Yep, roots with multiplicity $>1$.

Martin Sleziak

Ok, so the further question is that if we know some eigenvalue, whether we can find the corresponding eigenvector.

I.e., if we are given d, can we find all vectors satisfying $A\vec v=d\vec v$?

Khallil

Substitution and simultaneous solving of the linear system?

Martin Sleziak

Well, the above is equivalent to the linear system $(A-dI)\vec v=\vec 0$.

So I will solve homogeneous linear system with the matrix $(A-dI)$.

Khallil

Oct 10, 2015 14:26

Do we forget $v=0$?

Martin Sleziak

Yes. We do not want $\vec v=\vec 0$.

Because we want put these vectors into the matrix P.

If P has zero column, it does not have full rank. So such matrix does now have inverse.

If you look at the definition of eigenvalues and eigenvectors, the definition explicitly says $\vec v\ne\vec 0$.

BTW it would be good think to have a look at some worked out examples.

Khallil

Otherwise $v = 0$ would always correspond to the eigenvalue $0$?

Martin Sleziak

It seems that there are some example on Wikipedia: en.wikipedia.org/wiki/…

And you can probably find some examples in the eigenvalues-eigenvectors.

@Khallil Well, $\vec v=0$ would be solution of $A\vec v=d\vec v$ for any number $d$.

Eigenvalues are precisely those $d$'s, for which there is also a non-zero solution.

Khallil

Oh, so there are infinitely many solutions to that equation?

Is that a nullspace or something? That word was thrown about in my lecture.

Martin Sleziak

Yes, eigenvactors corresponding to d are in the nullspace of the matrix $A-dI$.

Ok, so can we try somewhat summarize what we have said so far.

And make some kind of step-by-step algorithm from this.

Suppose we are given matrix $A$ and we want $D=P^{-1}AP$.

1. Calculate all eigenvalues. (=roots of the char. polynomial).

2. For each eigenvalue $d$ find basis of the solutions of the homogeneous system $(A-dI)\vec v=\vec 0$. (This is probably what you call the null space.)

3. If we have n linearly independent vectors, then we simply put them as columns into matrix P.

user153330

Oct 10, 2015 14:34

those eigen things are amazing

Martin Sleziak

4. We put the eigenvalues on the diagonal of D. We have to make sure that we put them there in the same order as we put eigenvalues in P.

That is the whole algorithm @Khallil

Khallil

By the same order as we put the eigenvalues in $P$, I'm not sure what you mean, @Martin.

Martin Sleziak

If you want we can go through the algorithm for this example from Wikipedia: en.wikipedia.org/wiki/…

Khallil

(Thanks for going through this with me!)

Martin Sleziak

The advantage is that the eigenvalues and eigenvectors are already calculated there, so we do not have do that.

In that example a matrix A is given.

Then they calculated the eigenvalues as the roots of the char. poly.

They write that the roots are $d_1=1$ and $d_2=3$.

So far ok?

Khallil

Oct 10, 2015 14:36

Yep, this is all clear so far!

Martin Sleziak

Then they calculate the eigenvectors for $d_1=1$ and the eigenvectors for $d_2=3$.

Khallil

So we have the eigenvalues and we then find the corresponding eigenvectors by solving the homogeneous system.

Martin Sleziak

yes.

On Wikipedia they only wrote one eigenvector for the eigenvalue 1. But every multiiple of that vector would be solution of the same system.

(And we could use any solution, with the exception of zero vector.)

Khallil

Since they all lie on the same line? Is this the invariant line I heard of?

Martin Sleziak

In this case on the same line.

I would call it eigenspace or invariant subspace.

If you have another matrix, it can happen that the solution space of the system $(A-dI)\vec v=\vec 0$ is not one-dimensional.

But in this example we only have one-dimenional subspace for each eigenvalue.

So on Wikipedia they write that $d_1=1$ has eigenvalue $\vec v_1=\begin{pmatrix}1\\-1\end{pmatrix}$.

And that $d_2=3$ has eigenvalue $\vec v_1=\begin{pmatrix}1\\1\end{pmatrix}$.

So far ok?

Khallil

Oct 10, 2015 14:41

Yep, all ok so far!

Martin Sleziak

Now if we want to form the matrices D and P we simply do this:

I put d_1 and d_2 on the diagonal of D.

Khallil

Is the order in which we place them significant?

Martin Sleziak

In this case $D=\begin{pmatrix} 1 & 0 \\ 0 & 3 \end{pmatrix}$.

I choose some order. So far it was not important.

But if I put them in this order in D and if I now want to write down P, I have to be careful.

Since I put in D the eigenvalue 1 in the first place, the corresponding eigenvector will be in P in the first column.

So the columns of P will be $\vec v_1$, $\vec v_2$ in this order.

Maybe now it could be clear what I meant by the "same order".

Khallil

Yep, otherwise we wouldn't be able to expand out the $PD$ and $AP$ as we did right at the start?

Martin Sleziak

So if I am not mistaken, we get: $P=
\begin{pmatrix}
1 & 1 \\
-1 & 1 \\
\end{pmatrix}$

For these matrices we should have $PD=AP$ or $P^{-1}AP=D$.

Khallil

Oct 10, 2015 14:45

I get that as well for $P$.

Also, could you explain what similar matrices are?

Martin Sleziak

Or another equivalent equation $PDP^{-1}=A$.

Khallil

I think it has something to do with eigenvalues also?

Martin Sleziak

Just to finish this example: If we multiply the matrices we found it really works: wolframalpha.com/input/?i=%5B%5B1%2C1%5D%2C%5B-1%2C1%5D%5D*%5B%5B1%2C‌0%5D%2C%5B0%2C3%5D%5D*inverse%28%5B%5B1%2C1%5D%2C%5B-1%2C1%5D%5D%29

Hm, the link is broken :-(

Khallil

The Wolfram link is broken but I'll try and input it later!

Martin Sleziak

Second attempt: wolframalpha.com/input/?i=%5B%5B1%2C1%5D%2C%5B-1%2C1%5D%5D*%5B%5B1%2C‌0%5D%2C%5B0%2C3%5D%5D*inverse(%5B%5B1%2C1%5D%2C%5B-1%2C1%5D%5D)

Ok, the input was: [[1,1],[-1,1]]*[[1,0],[0,3]]*inverse([[1,1],[-1,1]])

@Khallil I would suggest that we stop now.

I think it would be better for you to try some examples.

So that you digest better what we went through.

We could say much more about diagonalization, but this should be find for the satert.

Khallil

Oct 10, 2015 14:50

I have a few to try so I'll get started now! :-)

Thanks, @Martin!

Martin Sleziak

@Khallil Tow matrices A,B are similar if $B=P^{-1}AP$ for some invertible matrix $P$.

Khallil

Should one of the $A$s be a $B$?

Martin Sleziak

Corrected.

I am trying to type fast, so I make mistakes.

Khallil

So diagonal matrices are similar also?

Martin Sleziak

No.

What we found out in the above example was this.

For a given matrix A we found D such that A and D are similar.

Khallil

Oct 10, 2015 14:52

By the first $D$ you mean a $P$?

Martin Sleziak

Now< i really mean D this time.

We were given some matrix $A$. And we found both $D$ and $P$ such that $D=P^{-1}AP$.

This is precisely that D and A are similar.

So the original question can be understood as: Is there a diagonal matrix such that A is similar to D?

(Although in fact we found also the matrix P. To say that A and D are similar we do not need to know P, we only need to know that such P exists.)

Ok, if you do not mind, I will quit now. (I will have a late lunch.)

I am afraid I will no have much time today.

Khallil

Of course not! Thank you for the help and enjoy lunch, @Martin!

Hopefully another time! :-)

Martin Sleziak

But if you have further questions, you can try to ask here or in the main chatroom.

Khallil

I will!

Martin Sleziak

If I see them and if I have time, I will try to leave at least a brief response.

And maybe somebody else will react. (I guess other users may notice that there was some activity in this room.)

So see you later!

Khallil

Oct 10, 2015 14:57

See you later!

$Mathematics$ Linear & Abstract algebra

Participants