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?

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?

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

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

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

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

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}$?

Nope, often the transpose of that.

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

I.e., the column vectors.

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

Let's do this!

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

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

Right?

Haven't come across regular before, @Martin.

Is it a special property?

We want a matrix which has inverse.

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

Oh yes of course. I see what you mean.

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

Did you see such result?

Yep, I recall proving such a result.

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$.

That makes sense so far.

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

(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?)

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$.

Oh I see what you mean.

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$.

I have no idea.

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}$$

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

Oh, yea that's what I was thinking.

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}$$

Can I ask how you got the final equality?

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?

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?

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.

Yep, I see that now.

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

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?

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

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

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

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.

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.

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

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

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.

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

n linearly independent eigenvectors

Oh, is there an important distinction?

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.

Oh, I see. Yea that makes sense.

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.)

Yep, roots with multiplicity $>1$.

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$?

Substitution and simultaneous solving of the linear system?

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)$.

Do we forget $v=0$?

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.

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

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.

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

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

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.

those eigen things are amazing

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

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

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

(Thanks for going through this with me!)

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?

Yep, this is all clear so far!

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

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

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.)

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

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?

Yep, all ok so far!

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.

Is the order in which we place them significant?

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".

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

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

I get that as well for $P$.

Also, could you explain what similar matrices are?

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

I think it has something to do with eigenvalues also?

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 :-(

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

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.

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

Thanks, @Martin!

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

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

Corrected.

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

So diagonal matrices are similar also?

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.

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

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.

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

Hopefully another time! :-)

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

I will!

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!

See you later!