16. Endomorphisms and their eigenvalues and eigenvectors

Part 1.: problems, solutions.
Part 2.: problems, solutions.

Endomorphisms and similarity of matrices

A linear mapping \varphi\colon V\to V is called an endomorphism. We will be dealing with spaces V which are finite dimensional. Thus, given a basis \mathcal{A} of V we consider the matrix of the mapping in this basis M(\varphi)_{\mathcal{A}}^{\mathcal{A}}. Notice that, if \oB is also a basis of V, then

    \[$M(\varphi)_{\mathcal{B}}^{\mathcal{B}}= (M(id)_{\mathcal{B}}^{\mathcal{A}})^{-1}\cdot M(\varphi)_{\mathcal{A}}^{\mathcal{A}}\cdot M(id)_{\mathcal{B}}^{\mathcal{A}},\]

since M(id)_{\mathcal{A}}^{\mathcal{B}}=(M(id)_{\mathcal{B}}^{\mathcal{A}})^{-1}.

This motivates the notion of similarity of matrices. We shall say that two matrices n\times n A and B are similar, if there exists an invertible matrix C, such that B=C^{-1}AC. In other words, matrices A and B are similar if and only if they are matrices of the same endomorphism in two bases \mathcal{A} and \mathcal{B}.

It is easy to notice that the relation of similarity is an equivalence relation.

Invariants of similarity of matrices

If matrices A and B are similar, then it is easy to check that:

  • the determinants of A and B are equal,
  • sums of elements of diagonal (called the trace, denoted by tr A) are equal,
  • ranks of matrices A and B are equal.

This justifies the possibility of talking about the determinant, the trace and the rank of an endomorphism, since those are the same for its matrix in any basis.

Idea: eigenvalues and eigenspaces

If you have tried to imagine a linear map of a plane, you usually imagine that it stretches or squeezes the plane along some directions. It would be nice to know whether a given linear map \varphi\colon V\to V (such a map, which the same domain and range, is called an endomorphism), it is actually of this type. In other words we would like to know whether there exists a non-zero vector v and a scalar \lambda, such that \varphi simply multiples v by \lambda (so it stretches or squeezes the space in the direction of v), so:

    \[\varphi(v)=\lambda v.\]

If v and \lambda have such properties, then v is said to be an eigenvector of \varphi and \lambda an eigenvalue.

Determining eigenvalues

Notice that if \lambda is an eigenvalue of a map \varphi and v is its eigenvector, then \varphi(v)-\lambda v=0. Therefore if M is a matrix of \varphi (e.g. in the standard basis, it actually does not matter), then

    \[0=Mv-\lambda v=Mv-\lambda I v=(M-\lambda I)v\]

, where I is the identity matrix.

Since multiplication of a matrix by a vector gives a linear combination of its columns and v is a non-zero vector, we see that the columns of M-\lambda I can be non-trivially combined to get the zero vector! It is possible if and only if \det (M-\lambda I)=0. The expression \det (M-\lambda I) is called the characteristic polynomial of \varphi. Notice that it does not depend on the basis in which the matrix M is given.

How to find the eigenvalues of a map? Simply one needs to solve the equation \det (M-\lambda I)=0. E.g let \varphi (x,y,z)=(2x,x+y,-x+z). Then:

    \[M(\varphi)_{st}^{st}=\left[\begin{array}{ccc}2&0&0\\1&1&0\\-1&0&1\end{array}\right]\]

Therefore:

    \[M(\varphi)_{st}^{st}-\lambda I=\left[\begin{array}{ccc}2-\lambda&0&0\\1&1-\lambda&0\\-1&0&1-\lambda\end{array}\right].\]

So we have to solve the following:

    \[\det (M(\varphi)_{st}^{st}-\lambda I)=(2-\lambda)(1-\lambda)^2=0\]

And therefore the eigenvalues are: 2 and 1.

Eigenspaces

Now let’s find eigenvectors related to subsequent eigenvalues. Notice that since \varphi is a linear map, if v, v' are eigenvectors for an eigenvalue \lambda, then for any scalar a also av and v+v' are eigenvectors for \lambda. Therefore, the set of all eigenvectors for \lambda forms a linear subspace. Notice that v satisfies the equation

    \[(M-\lambda I)v=0\]

so the space of eigenvectors (i.e. eigenspace) for \lambda (denoted as V_{(\lambda)}) is given by the following system of equations:

    \[(M-\lambda I)v=0\]

and we can easily find its basis.

In our example, let us find a basis of V_{(1)}, so let \lambda=1. Then:

    \[M(\varphi)_{st}^{st}-\lambda I=\left[\begin{array}{ccc}1&0&0\\1&0&0\\-1&0&0\end{array}\right]\]

Therefore, we have the following system of equations:

    \[\begin{cases}x=0\\x=0\\-x=0\end{cases}\]

The space of solutions is V_{(1)}=\{(0,y,z)\colon y,z\in\mathbb{R}\}, and its basis is (0,1,0),(0,0,1). Indeed, \varphi((0,1,0))=1\cdot (0,1,0) and \varphi((0,0,1))=1\cdot (0,0,1).

Let’s find a basis of V_{(2)}, so let \lambda=2. Then:

    \[M(\varphi)_{st}^{st}-\lambda I=\left[\begin{array}{ccc}0&0&0\\1&-1&0\\-1&0&-1\end{array}\right]\]

The system of equations:

    \[\begin{cases}0=0\\x-y=0\\-x-z=0\end{cases}\]

In the reduced ,,stair-like” form:

    \[\left[\begin{array}{ccc|c}1&0&1&0\\0&1&1&0\\0&0&0&0\end{array}\right]\]

The space of solutions is V_{(2)}=\{(-z,-z,z)\colon y,z\in\mathbb{R}\}, and its basis is (-1,-1,1). Indeed, \varphi((-1,-1,1))=(-2,-2,2)=2\cdot (-1,-1,1).

Eigenvector basis

If the sum of dimensions of spaces related to the eigenvalues of a given map equals the dimension of the whole space (as in our example: 1+2=3), then the basis of the whole space which consists of the vectors from the bases of subspaces related to the eigenvalues is called an eigenvector basis (in our case: \mathcal{A}=\{(0,1,0),(0,0,1),(-1,-1,1)\}).

If a map has an eigenvector basis, then it can be actually described by means of squeezing and stretching in the directions of eigenvectors. Notice that the matrix of such a map in an eigenvector basis is an diagonal matrix (has non-zero elements only on its diagonal) with eigenvalues related to subsequent eigenvectors on its diagonal. In our example:

    \[M(\varphi)_{\mathcal{A}}^{\mathcal{A}}=\left[\begin{array}{ccc}1&0&0\\0&1&0\\0&0&2\end{array}\right]\]

It may happen that a map has no eigenvectors (e.g. a rotation of the plane) or that the subspaces of eigenvectors are to small (e.g. a 10 degree rotation of a three-dimensional space around an axis had only one-dimensional space of eigenvectors).

Diagonalization of a matrix

A matrix M is diagonalizable, if there exists a matrix C, such that:

    \[M=C\cdot D\cdot C^{-1},\]

where D is a diagonal matrix.

How to check it and diagonalize a matrix if it is possible? Simply consider a linear map \varphi such that M is its matrix in standard basis. Matrix M is diagonalizable, if and only if \varphi has eigenvector basis \oA. Then:

    \[M=M(id)_{\mathcal{A}}^{st}\cdot D\cdot (M(id)_{\mathcal{A}}^{st})^{-1}\]

and D=M(\varphi)_{\mathcal{A}}^{\mathcal{A}}, since (M(id)_{\mathcal{A}}^{st})^{-1}=M(id)_{st}^{\mathcal{A}}.

E.g. we know that

    \[\left[\begin{array}{ccc}2&0&0\\1&1&0\\-1&0&1\end{array}\right]\]

is diagonalizable, since \varphi related to this matrix has an eigenvector basis. furthermore in this case:

    \[D=M(\varphi)_{\mathcal{A}}^{\mathcal{A}}=\left[\begin{array}{ccc}1&0&0\\0&1&0\\0&0&2\end{array}\right]\]

and

    \[C=M(id)_{\mathcal{A}}^{st}=\left[\begin{array}{ccc}0&0&-1\\1&0&-1\\0&1&1\end{array}\right].\]

Calculating diagonalizable matrices

Diagonalization of a matrix has the following interesting matrix. We can use it to calculate a power of a matrix, if it is diagonalizable. Notice that if \mathcal{A} is a basis, then:

    \[\left(M(\varphi)_{\mathcal{A}}^{\mathcal{A}}\right)^{n}=M\left(\underbrace{\varphi\circ\ldots\circ\varphi}_{n}\right)_{\mathcal{A}}^{\mathcal{A}},\]

Therefore:

    \[(M(\varphi)_{st}^{st})^{n}=M\left(\underbrace{\varphi\circ\ldots\circ\varphi}_{n}\right)_{st}^{st}=\]

    \[=M(id)_{\mathcal{A}}^{st}\cdot M\left(\underbrace{\varphi\circ\ldots\circ\varphi}_{n}\right)_{\mathcal{A}}^{\mathcal{A}}\cdot M(id)_{st}^{\mathcal{A}} = M(id)_{\mathcal{A}}^{st}\cdot \left(M\left(\varphi\right)_{\mathcal{A}}^{\mathcal{A}}\right)^{n}\cdot M(id)_{st}^{\mathcal{A}}\]

but if \mathcal{A} is a basis of eigenvectors, then M\left(\varphi\right)_{\mathcal{A}}^{\mathcal{A}} is a diagonal matrix so calculating its power is simply calculating powers of the elements on the diagonal.

Let us show it on an example. Let us calculate:

    \[\left[\begin{array}{ccc}2&0&0\\1&1&0\\-1&0&1\end{array}\right]^{5}\]

We have:

    \[C=M(id)_{\mathcal{A}}^{st}=\left[\begin{array}{ccc}0&0&-1\\1&0&-1\\0&1&1\end{array}\right].\]

Therefore:

    \[C^{-1}=M(id)_{st}^{\mathcal{A}}=\left[\begin{array}{ccc}-1&1&0\\1&0&1\\-1&0&0\end{array}\right].\]

So:

    \[\left[\begin{array}{ccc}2&0&0\\1&1&0\\-1&0&1\end{array}\right]^{5}=C \cdot \left[\begin{array}{ccc}1&0&0\\0&1&0\\0&0&2\end{array}\right]^{5}\cdot C^{-1}=C \cdot \left[\begin{array}{ccc}1&0&0\\0&1&0\\0&0&32\end{array}\right]^{5}\cdot C^{-1}=\left[\begin{array}{ccc}32&0&0\\31&1&0\\-31&0&1\end{array}\right].\]