Difference between revisions of "Linear algebra (eigenvalues and eigenvectors)" - Rhea

Latest revision as of 06:22, 3 July 2012

7.1 EIGENVALUES AND EIGENVECTORS

Bonus point project for MA265.

1) Definition

• Let
              L:V → V

be the linear transformation of n-dimensional vector space into itself (a linear operator on V)
Then, λ is an eigenvalue of L if there exists a non-zero vector x in V such that 
          L(x) = λx

In other words, λ is a scalar associated with vector x to represent a linear transformation.

 • If λ = eigenvalue, then x = eigenvector (an eigenvector is always associated with an eigenvalue)
Eg: If L(x) = 5x , 5 is the eigenvalue and x is the eigenvector.
* λ can be either real or complex, as will be shown later.

• An example about the concept of eigenvalue and eigenvector, based on a linear transformation:

(Read the matrix [a , b] as entry [a] in the first row and entry [b] in the second row)

• Given that L:R² → R² be linear operator defined by

                   L ([a₁ , a₂]) = [-a₂ , a₁]

To find the eigenvalues of L and the associated eigenvectors, we have to find λ such that
                L([a₁ , a₂]) = λ[a₁ , a₂]
Since [-a₂ , a₁] = λ[a₁ , a₂], equate them together, and we can find that 
                 λa₁ = -a₂  (1) and λa₂ = a₁ (2)

By substituting (2) into (1), we obtain

λ(λa₂) = -a₂
λ²a₂ = - a₂
λ² = -1

Since the square root of -1 is equal to the complex number i, we can conclude that λ = ±i
Because the eigenvalues are not real, we can say that there is no vector [a₁ , a₂] in R² such that L([a₁ , a₂]) is parallel to [a₁ , a₂].

But if L is mapped from C² into C² , then L has eigenvalue i (eigenvector $ \begin{bmatrix} i \\ 1 \end{bmatrix} $ ) and eigenvalue -i (eigenvector $ \begin{bmatrix} -i \\ 1 \end{bmatrix} $  )

-The associated eigenvectors can be obtained by substituting the particular eigenvalue into equation(1) and (2), and using the coefficient matrix that we get, we can solve for the eigenvectors.
Eg: When λ= i, equation (1) becomes ia₁ = -a₂ , and equation (2) becomes ia₂ = a₁

Hence,

ia₁ + a₂ = 0      (3)

a₁ - ia₂ = 0       (4)
From here, we can come up with the coefficient matrix:

$ \begin{bmatrix} i & 1 \\ 1 & -i \end{bmatrix} $ 

By reducing the matrix to its echelon form, we can obtain the associated eigenvector for eigenvalue i, which is 

 $ \begin{bmatrix} i \\ 1 \end{bmatrix} $
Try to verify the associated eigenvector for eigenvalue -i based on the answer given above.

* Zero vector cannot be an eigenvector, but scalar zero can be eigenvalue* - IMPORTANT FACT

TIME FOR SOME MATRICES !!!

Before even attempting to find eigenvalues and associated eigenvectors for matrices, two things we should know: CHARACTERISTIC POLYNOMIAL OF A MATRIX and CHARACTERISTIC EQUATION OF A MATRIX.

1. CHARACTERISTIC POLYNOMIAL OF A MATRIX

To find the eigenvalues and associated eigenvectors of a matrix, we should construct a *NEW* matrix out of a given matrix. The *NEW* matrix is where we can get the characteristic polynomial of the given matrix from. 

The significance of the characteristic polynomial of a matrix : the roots of the polynomial are the eigenvalues of the given matrix (Theorem 7.1), and by substituting eigenvalues into the characteristic polynomial and solving for the solution, we can obtain the associated eigenvectors for the eigenvalues of the matrix

    2. CHARACTERISTIC EQUATION OF A MATRIX

In order to find the eigenvalues and associated eigenvectors of a given matrix, we would need to have a particular   equation.  The equation could be obtained  by using the concept of determinants.

.The equation : p(λ) = det(λI_n - A) = 0, where λ is the variable that represents the eigenvalues, I_n = Identity matrix and A = the given matrix

HOW TO CONSTRUCT A CHARACTERISTIC POLYNOMIAL (A SHORTCUT):

Let's say the question requires us to solve for the eigenvalues and associated eigenvectors of a nXn matrix A,

 $ \begin{bmatrix} 1 & 1 \\ -2 & 4 \end{bmatrix} $

Step 1 :To come up with the characteristic polynomial of the matrix, change the entries on the main diagonal to from [x] to [λ-x] (or from [-x] to [λ+x]), and change the sign of the other entries of the matrix (if the entries are zero on the diagonal, just change to λ, but if the other entries are zero, just remain as zero)

For the question asked above, the characteristic polynomial would be [λ-1 -1 , 2 λ-4] (Note the entries of the main diagonal have a λ sign, and the other entries have changed signs).

Step 2 : Using the concept of determinants learnt in Chapter 3, compute the determinant of the matrix (Note that we are going to get an algebraic equation, so be careful when doing the computation, a small mistake might result in a wrong answer)

Using the concept of det, we can compute the characteristic polynomial of the matrix. To refresh our minds,

det (λI - A) = (λ-1)(λ-4)-(-2) = 0

λ²-5λ+6 = 0

(λ-2)(λ-3) = 0

Hence the roots of the characteristic polynomial @ the eigenvalues of the matrix are λ=2 and λ=3.

Step 3 : To compute the eigenvectors associated with the eigenvalues, there are two ways: (1) using the equation A(x) = λ(x), where A = the given matrix, x = the solution (eigenvector) and λ = eigenvalue or (2) using the eigenvalue obtained, just substitute it back into the *NEW* matrix and solve for the solution (eigenvector) by doing reducing the matrix to reduced row echelon form (rref).

For this question, let's try to solve for the associated eigenvectors by using the second way, i.e substituting the eigenvalue into the *NEW* matrix and doing rref.

When λ = 2, we have the matrix

$ \begin{bmatrix} 1 & -1 \\ 2 & -2 \end{bmatrix} $ $ \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} $

After reducing the matrix to rref, we have

$ \begin{bmatrix} 1 & -1 \\ 0 & 0 \end{bmatrix} $ 

hence indicating that the matrix have a nontrivial solution.

Choosing the second column as our independent variable (because there is no leading one), we have x₂ = r, and x₁ - r = 0, so x₁ = r.

Hence we have

$ \begin{bmatrix} r \\ r \end{bmatrix} $ 

as our solution, and by factorizing r out of the solution space, we have eigenvector

$ \begin{bmatrix} 1 \\ 1 \end{bmatrix} $ 

for λ=2.

Repeating the same method to find the eigenvector when λ=3, we have the matrix

$ \begin{bmatrix} 2 & -1 \\ 2 & -1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} $ 

After reducing the matrix to rref, we have

$ \begin{bmatrix} 1 & -1/2 \\ 0 & 0 \end{bmatrix} $ 

hence indicating that the matrix have a nontrivial solution.
Choosing the second column as our independent variable (because there is no leading one), we have x₂ = r, and x₁ - r/2 = 0, so x₁ = r/2.

Hence we have

$ \begin{bmatrix} r/2 \\ r \end{bmatrix} $

as our solution, and by factorizing r out of the solution space, we have eigenvector

$ \begin{bmatrix} 1/2 \\ 1 \end{bmatrix} $ 

for λ=3.

SOLVED!!!

Second example(slightly more difficult, but could be solved nonetheless)

Question: Compute the eigenvalues and eigenvectors of the following nXn matrix B

$ \begin{bmatrix} 0 & 0 & 3 \\ 1 & 0 & -1 \\ 0 & 1 & 3 \end{bmatrix} $

Solution: If we still remember lessons from Chapter 3, it will be easy to compute the det, hance getting the characteristic polynomial. The first step to solve this question is by constructing the *NEW* matrix. Note that there are a few zeros in the diagonal of the matrix, so do not forget to change them to λ. Therefore, we will get a matrix like this: [λ 0 -3 , -1 λ  1 , 0 -1 λ -3]

Note that there are a few zeros in the *NEW* matrix, this will make computations much easier. From Chapter 3, we know that it is easier to find det when we calculate it through a row or column where there is/are zero(s) as they will simplify calculations. In this case, we compute the det through the first column. 

We should get characteristic polynomial that looks like this :

p(λ) =λ³-3λ²+λ-3

This is where most students have problem, especially during exams. Although the polynomial is to the power of three, do not panic. Recall some lessons from MA165. To solve for the roots, we can use trial and error to solve for one root then by using the long division method, we can get the two other roots. Depending on how big the numbers in the polynomial, it is quite easy to do this, but as always, be careful. By trial and error, we know that λ=3 for one root, hence we have to find the other roots. To do this, divide the polynomial with (λ-3), and we should get (λ²+1). As we can see, we will get complex numbers for the other roots. 

λ²+1 = 0

λ²= -1 

λ= ±i

Substituting λ=3, λ=i and λ= -i respectively, we should have associated eigenvectors

$ \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} $ for λ=3, $ \begin{bmatrix} -3i \\ -3+i \\ 1 \end{bmatrix} $ for λ= i and $ \begin{bmatrix} 3i \\ -3-i \\ 1 \end{bmatrix} $ for λ = -i

The key to get the eigenvectors for the eigenvalues with complex numbers is still by reducing them into rref, but be extra careful duirng the row operations. As we know, i²= -1, so remember to susbtitute the value during computation to simplify the form. For these types of questions, it is good to check your answers by using MATLAB, so you can just be sure of everything. 

SOLVED !!!!

• If a question asks to find the eigenvalues and associated eigenvectors for a given BASIS, the procedure to solve the question is still the same. The only difference is you should somehow come up with a matrix A, that will act as a given matrix. Then you can find the *NEW* matrix and solve the question as usual.

For example:

• Let L:P₂ →P₂ be a linear operator defined by

               L(at² +bt +c) = -bt-2c

Find a matrix B that represents L with respect to the basis {t-1,1,t²} for P₂ and consequently, find eigenvalues and associated eigenvectors of L.

Try to do it yourself to check your understanding about this topic. (Answers given below, so you can check)

Answers: Eigenvalues and eigenvectors:

$ \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix} $ for λ=0, $ \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix} $ for λ= -2 and $ \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix} $ for λ = -1
 

7.2 DIAGONALIZATION AND SIMILAR MATRICES

1) Definition

Let L:V → V be a linear operator on an n-dimensional vector space. L is diagonizable if there exists a basis S for V such that L is represented with respect by a diagonal matrix D.

• Basically the definition is not really important to solve the questions, but it still needs to be understood nonetheless. Pay more attention to the theorems, as they would help to simplify computations.

Theorem 7.2: Similar matrices have same eigenvalues.

Let's say we have two nXn matrices, A and D, where A is given matrix and D is a diagonal matrix. We say matrix A and D are similar if and only if there exists a nonsingular (invertible)  matrix P such that D = P^-1AP.

• If matrix A is similar to matrix D, it follows that A=PDP^-1. This is a key fact that could help to solve certain problems.

Theorem 7.3: If D is the diagonal matrix representing L with respect to S (based on definition (1) ), the entries on the main diagonal are the eigenvalues of L.  

In terms of matrices, the following theorem holds true;

Theorem 7.4: An nXn matrix A is similar to a diagonal matrix D if and only if A has n linearly independent eigenvectors. Moreover, the elements on the main diagonal of D are the eigenvalues of A.

Basically we just have to show that the associated eigenvectors of the eigenvalues for matrix A are linearly independent, simply by putting them side by side and reducing them to rref, hence we can know whether the matrix is diagonizable or not. (Example below)

• Note: If matrix A is similar to the diagonal matrix D, then we conclude that matrix A is diagonizable.

Example of Theorem 7.4:

Consider the matrix

$ \begin{bmatrix} 1 & -1 \\ 2 & 4 \end{bmatrix} $ 

which is the same matrix from first example in Section 7.1. We know that the eigenvalues are 2 and 3, and the associated eigenvectors are

$ \begin{bmatrix} 1 \\ 1 \end{bmatrix} $ and $ \begin{bmatrix} 1 \\ 2 \end{bmatrix} $ respectively.

Putting them together side by side, we  will have

 $ \begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix} $ 

and by reducing the matrix (verify), we can easily identify that the eigenvectors are linearly independent of each other, hence the matrix is diagonizable.

Note: For upper triangular or lower triangular matrices, the eigenvalues are the entries on the main diagonal. Same eigenvalues for a matrix will result in linearly dependent eigenvectors, hence the matrix is not diagonizable.

HOW TO GET MATRIX P?

One might think that it is difficult to do so, but actually it easy once you have the eigenvectors of the matrix. To get the matrix P, all you have to do is put the associated eigenvectors for the eigenvalues side by side (as we already did to know whether the matrix is diagonizable). This hold true for any cases. 

As for the previous example, in which λ₁ = 2 and λ₂ = 3, matrix P is equal to

$ \begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix} $

and matrix P^-1 is equal to (verify)

$ \begin{bmatrix} 2 & -1 \\ -1 & 1 \end{bmatrix} $

Take note that the order in which the matrix P is constructed will determine the location of the eigenvalue on the diagonal matrix D. However, the answers would still be correct and accepted. In this case the matrix D is

$ \begin{bmatrix} 2 & 0 \\ 0 & 3 \end{bmatrix} $

The order of the entries in the diagonal matrix would be reversed if λ₁=3 and λ₂=2.

Theorem 7.5: If the roots of the characteristic polynomial of an nXn matrix are all different from each other (distinct) then the matrix is diagonizable. (This can be verified by having any matrix with different eigenvalues, and check if the associated eigenvalues are linearly independent of each other.

CONCLUSION: 

(1) The basic steps for solving the eigenvalues and eigenvectors are the same (no matter whether it's a 2X2 or 3X3 matrix), i.e changing the matrix to a *NEW* form, computing the det, factorizing the characteristic polynomial to get the roots @ eigenvalues, and substituting the eigenvalues into the *NEW* matrix to obtain the associated eigenvectors.

(2) Common mistakes done by students, including me - careless when copying the given matrix, forgetting that not all entries should include λ (therefore getting a ridiculous characteristic polynomial), forgetting to change the signs when changing the form to a *NEW* matrix, not careful when calculating the det (hence getting different answers), careless when factorizing the characteristic polynomial (especially the ones with 3 roots), careless when doing reducing the matrix.

(3) Tips for excelling in this section : (i) BE CAREFUL when doing all computations (ii) Understand everything involving the previous chapters (determinants, reduced row echelon form, basis for null space etc.) because this is one chapter where everything just comes in together. (iii) Do lots of practice, especially the ones involving complex numbers and the questions where you get a column of zeros when solving for the eigenvectors. These questions require great understanding of the previous chapters.

Back to MA265, Fall 2010, Prof. Momin