Diagonalizing matrix in a vector equation

[Sergey S]

Homework Statement

I have a vector equation of a form:
$$Ax=y$$
where A is a square $n \times n$ matrix and y, x are vectors. I want to rewrite it in a new from:
$$Dx=Ty$$
where D is a diagonal matrix, and T is some square $n \times n$ matrix.

The question is, is it possible to find such D and T that the equation hods for a generic case? How would you find it, or prove that it is possible to find it?

Homework Equations

The Attempt at a Solution

Obviously, from the shown above equations we can say that:
$$TA=D$$
and from that follows
$$T=DA^{-1}$$
That tells me that I can pick any diagonal matrix of my choice and find such a T that the equation will work. Is that true, or am I missing something?

A prettier way to approach this is to think of the matrix A as of a matrix of a linear operator. Then we can use a theorem that says that any linear operator will have a diagonal matrix in the basis made of its eigenvectors. This tells me that there should be a linear operator that transforms current basis A is written for into a new basis, made of its eigenvectors, and that operator has a matrix (we can name is T for consistency). It proves that there is such T that the equations above hold, but it is not clear how to find this T.

Yet another way is to say that:
$$SDS^{-1}=A$$
Then we get:
$$SDS^{-1}x=y$$
I honestly don't know where to go next from this step. I'm sorry for being a slowpoke here.

Hope some of you can help me with this, it seems like it should be a standard linear algebra problem.

 

[DrClaude]

Obviously, from the shown above equations we can say that:
$$TA=D$$
and from that follows
$$T=DA^{-1}$$
That tells me that I can pick any diagonal matrix of my choice and find such a T that the equation will work. Is that true, or am I missing something?

Think about it. If $A$ is invertible, then
$$
\begin{align}
x &= A^{-1}y \\
Dx &= D A^{-1}y \\
Dx &= T y
\end{align}
$$
where you have defined $T \equiv D A^{-1}$. The fact that $D$ is diagonal is irrelevant, as his will work with any matrix.

 

[HallsofIvy]

You are aware, are you not, the NOT every matrix is "diagonalizable"? Only those n by n matrices which have n independent eigenvectors are diagonalizable. For example, the matrix
$$\begin{bmatrix}1 & 1 \\ 0 & 1\end{bmatrix}$$
is not diagonalizable. It has the single eigenvalue, 1, and its eigenvectors are all of the form (x, 0).

IF a matrix has n independent eigenvectors, then we can form the matrix S having those eigenvectors as columns. In that case, $S^{-1}AS= D$ where D is the diagonal matrix having the eigenvalues of A on its diagonal.

 

[Sergey S]

Think about it. If $A$ is invertible, then
$$
\begin{align}
x &= A^{-1}y \\
Dx &= D A^{-1}y \\
Dx &= T y
\end{align}
$$
where you have defined $T \equiv D A^{-1}$. The fact that $D$ is diagonal is irrelevant, as his will work with any matrix.

So this works for any invertible A. It almost seems too good to be true. Thank you very much!

You are aware, are you not, the NOT every matrix is "diagonalizable"? Only those n by n matrices which have n independent eigenvectors are diagonalizable. For example, the matrix
$$\begin{bmatrix}1 & 1 \\ 0 & 1\end{bmatrix}$$
is not diagonalizable. It has the single eigenvalue, 1, and its eigenvectors are all of the form (x, 0).

IF a matrix has n independent eigenvectors, then we can form the matrix S having those eigenvectors as columns. In that case, $S^{-1}AS= D$ where D is the diagonal matrix having the eigenvalues of A on its diagonal.

Yes I am aware of that, but I can assume that A is diagonalizable. I see that I can write diagonal matrix D using eigenvalues of A; I still don't know how I can isolate $Dx$ in the left side of the equation, i.e. how do I transport $S$ and $S^{-1}$ from left to the right side of the equation?

 

[vela]

If A is invertible, you have $x = A^{-1}y$, and you're done. Here $D$ is the identity matrix, which is diagonal, and $T=A^{-1}$.

 

[Sergey S]

If A is invertible, you have $x = A^{-1}y$, and you're done. Here $D$ is the identity matrix, which is diagonal, and $T=A^{-1}$.

Yeah I got it. That solved almost all of my problems - now I know that T exists and how to find it. At this point I just wonder if there is a more computation-friendly method than finding inverse of A; maybe this equation can yield something - $SDS^{-1}x=y$? I am also curious if I can isolate $Dx$ in the left side of it.

 

[AlephZero]

At this point I just wonder if there is a more computation-friendly method than finding inverse of A;

Usually, there is no need to find the inverse of $A$ explicitly. It is more efficient, and better conditioned numerically, to solve the equations $Ax = b$, instead of of calculating $A^{-1}$ and then $x = A^{-1}b$.

There are many different algorithms to solve systems of linear equations, that take advantage of special properties of $A$ (e.g. symmetric, banded, very sparse, etc). Usually, $A^{-1}$ does not have the same "nice" special properties as $A$.

 

[Ray Vickson]

You are aware, are you not, the NOT every matrix is "diagonalizable"? Only those n by n matrices which have n independent eigenvectors are diagonalizable. For example, the matrix
$$\begin{bmatrix}1 & 1 \\ 0 & 1\end{bmatrix}$$
is not diagonalizable. It has the single eigenvalue, 1, and its eigenvectors are all of the form (x, 0).

IF a matrix has n independent eigenvectors, then we can form the matrix S having those eigenvectors as columns. In that case, $S^{-1}AS= D$ where D is the diagonal matrix having the eigenvalues of A on its diagonal.

Of course only some non-singular matrices can be diagonalized by a similarity transformation, but any non-singular matrix $A$ can be "diagonalized" by row and column operations, giving $D = PAQ$, allowing for $Q \neq P^{-1}$.

 

[Sergey S]

Usually, there is no need to find the inverse of $A$ explicitly. It is more efficient, and better conditioned numerically, to solve the equations $Ax = b$, instead of of calculating $A^{-1}$ and then $x = A^{-1}b$.

There are many different algorithms to solve systems of linear equations, that take advantage of special properties of $A$ (e.g. symmetric, banded, very sparse, etc). Usually, $A^{-1}$ does not have the same "nice" special properties as $A$.

I see. Yes I can do that. The reason I went for diagonalization instead of just solving the equation in the first place was because my $y$ vector is ridiculously long and I was hoping to find a way to avoid touching it as far as possible. But I can still use Cramer's rule to solve the equation, it is just really-really slow; and I can't write it down in an explicit form because it would be a page long expression.
Thanks for the advice =)

 

[HallsofIvy]

So this works for any invertible A. It almost seems too good to be true. Thank you very much!



Yes I am aware of that, but I can assume that A is diagonalizable. I see that I can write diagonal matrix D using eigenvalues of A; I still don't know how I can isolate $Dx$ in the left side of the equation, i.e. how do I transport $S$ and $S^{-1}$ from left to the right side of the equation?

Multiply! Multiplying both sides of $S^{-1}AS= D$ "on the left" by S gives [itex\AS= SD[/itex]. Multiplying both sides of $AS= SD$ "on the right" by $S^{-1}$ gives $A= SDS^{-1}$

 

[AlephZero]

But I can still use Cramer's rule to solve the equation, it is just really-really slow; and I can't write it down in an explicit form because it would be a page long expression.
Thanks for the advice =)

Cramer's rule is interesting in theory, but it one of the slowest methods known for solving n linear equations for any n > 2. If you compute the determinants by expanding them using cofactors, the speed is proportional to n!. Even if you compute the determinants efficiently, it is still slower than straightforward methods like Gaussian elimination, where the speed is proportional to n³

We don't know how big your "ridiculously long" vector is, but solving equations numerically is not a big deal if n = 1000, and if A has some "nice" properties it is not a big deal if n = 10⁶.

I think reading a textbook on numerical methods would be a good idea. Any book should have a chapter on solving linear equations.

 

[Sergey S]

Cramer's rule is interesting in theory, but it one of the slowest methods known for solving n linear equations for any n > 2. If you compute the determinants by expanding them using cofactors, the speed is proportional to n!. Even if you compute the determinants efficiently, it is still slower than straightforward methods like Gaussian elimination, where the speed is proportional to n³

We don't know how big your "ridiculously long" vector is, but solving equations numerically is not a big deal if n = 1000, and if A has some "nice" properties it is not a big deal if n = 10⁶.

I think reading a textbook on numerical methods would be a good idea. Any book should have a chapter on solving linear equations.

I agree, I really should read a book on numerical methods. I am aware that my questions are not anything I can't find in books, and I am sorry for taking everyone's time.

 

[AlephZero]

I am sorry for taking everyone's time.

There's no need to apologize. We don't mind what level the questions are at, so long as the person asking them wants to learn!