Aug 18

Eigenvalues and eigenvectors

Eigenvalues and eigenvectors

Motivation: what matrix can be called simplest?

Of course, nothing can be simpler than the zero and identity matrices. What is the next level of simplicity? In the one-dimensional case, consider a linear mapping f. Any real number x can be written as x=x1. By homogeneity f(x)=xf(1). Denoting c=f(1), we see that f is just multiplication by a number: f(x)=cx.

Let's look at the 2-dimensional generalization. We know that a linear mapping is given by a matrix. Consider

A=\left(  \begin{array}{cc}\lambda _1&0\\0&\lambda_2\end{array}\right).

A is scaling by \lambda_1 along the x-axis:

(1) A\left(\begin{array}{c}x\\0\end{array}\right) =\left(\begin{array}{cc}\lambda_1&0\\0&\lambda_2\end{array}\right)\left(\begin{array}{c}x\\0\end{array}\right) =\left(\begin{array}{c}\lambda_1x\\  0\end{array}\right)=\lambda_1\left(\begin{array}{c}x \\0\end{array}\right).

Similarly, A is scaling by \lambda_2 along the y-axis. Matrices of type

\left(\begin{array}{ccc}\lambda_1&...&0 \\...&...&... \\0&...&\lambda_{n}\end{array}\right)

are called diagonal and the short notation is diag[\lambda_1,...,\lambda_n]. Any simpler than that, and we'll be in the kindergarten.

It remains to name the things and link them to what we know

Definition 1. Based on (1), we say that \lambda is an eigenvalue of the matrix A if there exists a nonzero vector x such that

(2) Ax=\lambda x.

Such an x is called an eigenvector corresponding to \lambda .

With a zero x, (2) would be true for any \lambda, and there would be no definition. Since A is a real matrix, \lambda in principle cannot be complex if x\in R^n.

Definition 2. If one x satisfies (2), then the whole straight line passing through x satisfies (2). Moreover, if we have two eigenvectors x,y corresponding to \lambda, then for any linear combination z=ax+by we have Az=aAx+bAy=\lambda (ax+by)=\lambda z. Thus the set of all eigenvectors corresponding to one eigenvalue, completed with zero, is a subspace. We call it an eigenspace corresponding to \lambda. Its dimension is called a multiplicity of \lambda.

Exercise 1. a) The eigenspace corresponding to \lambda coincides with N(A-\lambda I) and the multiplicity of \lambda equals \dim N(A-\lambda I). b) The set of eigenvalues coincides with the set of roots of the equation

(3) \det (A-\lambda I)=0.

Proof. a) This is obvious because (2) is equivalently written as

(4) (A-\lambda I)x=0.

b) Existence of nonzero solutions of (4) is equivalent to N(A-\lambda I)\neq\{0\}, and we know that this condition is equivalent to (3).

Keep in mind that part b) of Exercise 1 implicitly assumes that both sets are of the same nature (are both subsets of either R or C).

Definition 3. (3) is called a characteristic equation and its roots - characteristic roots. Obviously, \det (A-\lambda I)=(-1)^n\det (\lambda I-A). For convenience, people define \phi(\lambda)=\det (\lambda I-A) and use \phi(\lambda)=0 to find the characteristic roots. The function \phi(\lambda) is called a characteristic polynomial.

After finding characteristic roots we can plug them in (4) to find N(A-\lambda I).

Definition 4. The set of eigenvalues of A is called the spectrum of A and denoted \sigma(A).

Remark. When convenient, we use the following notation. A as a mapping from R^n to R^n will be denoted A_R and as a mapping from C^n to C^n will be denoted A_C. We have to remember that there are two versions of statement b) from Exercise 1: b') \sigma(A_R) coincides with the set of real characteristic roots. b'') \sigma(A_C) coincides with the set of complex characteristic roots.

Digression on determinants

As much as possible I try to avoid using explicit formulas for the determinant but here we have to use one. The simplest version is this:

\det A=\sum\pm a_{1,i_1}a_{2,i_2}...a_{n,i_n}.

Perhaps a verbal description is better than this formula:

1) the determinant is a sum of products of elements of the matrix.

2) Each product contains n factors and is obtained as follows: take one element a_{1,i_1} from the first row and cross out the column it belongs to; take one element a_{2,i_2} from the second row and not from the column you have crossed out, and cross out the column it belongs to; take one element a_{3,i_3} from the third row and not from the two columns you have crossed out, and cross out the column it belongs to. Continue like that. After each step, the number of crossed-out columns increases by 1. The first factor can be chosen in n ways, the second in (n-1) ways,..., and for the last factor a_{n,i_n} there will be only one choice.

3) The sign \pm depends on the choices made and doesn't matter at this point.

Let's see what this implies for finding eigenvalues.

Exercise 2. \det (A-\lambda I) is a polynomial of power n in \lambda .

Proof. \det(A-\lambda I)=\left(\begin{array}{cccc}a_{11}-\lambda& a_{12}&...&a_{1n} \\a_{21}&a_{22}-\lambda&...&a_{2n} \\...&...&...& ... \\a_{n1}&a_{n2}&...&a_{nn}-\lambda\end{array}\right).

The verbal description given above shows that \det(A-\lambda I) contains the product of diagonal elements (a_{11}-\lambda)(a_{22}-\lambda)...(a_{nn}-\lambda ), which, in turn, contains the power \lambda^n. Because of the crossing-out procedure, other products will contain powers of \lambda lower than n, and there is no way the power \lambda^n could be cancelled out. Besides, \det(A-\lambda I) may contain only non-negative integer powers of \lambda not exceeding n. This proves the statement.

Exercise 3. In C^n any matrix A has at least one eigenvector.

Proof. Exercise 1 reduces the problem of finding eigenvalues to the problem of finding characteristic roots. By the fundamental theorem of algebra every non-constant single-variable polynomial has at least one complex root. Thus we have at least one eigenvalue and from (4) at least one eigenvector.

The reduction of the problem of finding eigenvalues to the problem of finding characteristic roots poses a problem. Even when A has real entries, the characteristic roots may be complex. Watch later how this problem is handled.