Linear Algebra/Polynomials of Maps and Matrices/Solutions

Solutions edit

This exercise is recommended for all readers.

Problem 1

What are the possible minimal polynomials if a matrix has the given characteristic polynomial?

$8\cdot (x-3)^{4}$
$(1/3)\cdot (x+1)^{3}(x-4)$
$-1\cdot (x-2)^{2}(x-5)^{2}$
$5\cdot (x+3)^{2}(x-1)(x-2)^{2}$

What is the degree of each possibility?

Answer

For each, the minimal polynomial must have a leading coefficient of $1$ and Theorem 1.8, the Cayley-Hamilton Theorem, says that the minimal polynomial must contain the same linear factors as the characteristic polynomial, although possibly of lower degree but not of zero degree.

The possibilities are $m_{1}(x)=x-3$ , $m_{2}(x)=(x-3)^{2}$ , $m_{3}(x)=(x-3)^{3}$ , and $m_{4}(x)=(x-3)^{4}$ . Note that the $8$ has been dropped because a minimal polynomial must have a leading coefficient of one. The first is a degree one polynomial, the second is degree two, the third is degree three, and the fourth is degree four.
The possibilities are $m_{1}(x)=(x+1)(x-4)$ , $m_{2}(x)=(x+1)^{2}(x-4)$ , and $m_{3}(x)=(x+1)^{3}(x-4)$ . The first is a quadratic polynomial, that is, it has degree two. The second has degree three, and the third has degree four.
We have $m_{1}(x)=(x-2)(x-5)$ , $m_{2}(x)=(x-2)^{2}(x-5)$ , $m_{3}(x)=(x-2)(x-5)^{2}$ , and $m_{4}(x)=(x-2)^{2}(x-5)^{2}$ . They are polynomials of degree two, three, three, and four.
The possiblities are $m_{1}(x)=(x+3)(x-1)(x-2)$ , $m_{2}(x)=(x+3)^{2}(x-1)(x-2)$ , $m_{3}(x)=(x+3)(x-1)(x-2)^{2}$ , and $m_{4}(x)=(x+3)^{2}(x-1)(x-2)^{2}$ . The degree of $m_{1}$ is three, the degree of $m_{2}$ is four, the degree of $m_{3}$ is four, and the degree of $m_{4}$ is five.

This exercise is recommended for all readers.

Problem 2

Find the minimal polynomial of each matrix.

${\begin{pmatrix}3&0&0\\1&3&0\\0&0&4\end{pmatrix}}$
${\begin{pmatrix}3&0&0\\1&3&0\\0&0&3\end{pmatrix}}$
${\begin{pmatrix}3&0&0\\1&3&0\\0&1&3\end{pmatrix}}$
${\begin{pmatrix}2&0&1\\0&6&2\\0&0&2\end{pmatrix}}$
${\begin{pmatrix}2&2&1\\0&6&2\\0&0&2\end{pmatrix}}$
${\begin{pmatrix}-1&4&0&0&0\\0&3&0&0&0\\0&-4&-1&0&0\\3&-9&-4&2&-1\\1&5&4&1&4\end{pmatrix}}$

Answer

In each case we will use the method of Example 1.12.

Because $T$ is triangular, $T-xI$ is also triangular
$T-xI={\begin{pmatrix}3-x&0&0\\1&3-x&0\\0&0&4-x\end{pmatrix}}$
the characteristic polynomial is easy $c(x)=\left|T-xI\right|=(3-x)^{2}(4-x)=-1\cdot (x-3)^{2}(x-4)$ . There are only two possibilities for the minimal polynomial, $m_{1}(x)=(x-3)(x-4)$ and $m_{2}(x)=(x-3)^{2}(x-4)$ . (Note that the characteristic polynomial has a negative sign but the minimal polynomial does not since it must have a leading coefficient of one). Because $m_{1}(T)$ is not the zero matrix
$(T-3I)(T-4I)={\begin{pmatrix}0&0&0\\1&0&0\\0&0&1\end{pmatrix}}{\begin{pmatrix}-1&0&0\\1&-1&0\\0&0&0\end{pmatrix}}={\begin{pmatrix}0&0&0\\-1&0&0\\0&0&0\end{pmatrix}}$
the minimal polynomial is $m(x)=m_{2}(x)$ .
$(T-3I)^{2}(T-4I)=(T-3I)\cdot {\bigl (}(T-3I)(T-4I){\bigr )}={\begin{pmatrix}0&0&0\\1&0&0\\0&0&1\end{pmatrix}}{\begin{pmatrix}0&0&0\\-1&0&0\\0&0&0\end{pmatrix}}={\begin{pmatrix}0&0&0\\0&0&0\\0&0&0\end{pmatrix}}$
As in the prior item, the fact that the matrix is triangular makes computation of the characteristic polynomial easy.
$c(x)=\left|T-xI\right|={\begin{vmatrix}3-x&0&0\\1&3-x&0\\0&0&3-x\end{vmatrix}}=(3-x)^{3}=-1\cdot (x-3)^{3}$
There are three possibilities for the minimal polynomial $m_{1}(x)=(x-3)$ , $m_{2}(x)=(x-3)^{2}$ , and $m_{3}(x)=(x-3)^{3}$ . We settle the question by computing $m_{1}(T)$
$T-3I={\begin{pmatrix}0&0&0\\1&0&0\\0&0&0\end{pmatrix}}$
and $m_{2}(T)$ .
$(T-3I)^{2}={\begin{pmatrix}0&0&0\\1&0&0\\0&0&0\end{pmatrix}}{\begin{pmatrix}0&0&0\\1&0&0\\0&0&0\end{pmatrix}}={\begin{pmatrix}0&0&0\\0&0&0\\0&0&0\end{pmatrix}}$
Because $m_{2}(T)$ is the zero matrix, $m_{2}(x)$ is the minimal polynomial.
Again, the matrix is triangular.
$c(x)=\left|T-xI\right|={\begin{vmatrix}3-x&0&0\\1&3-x&0\\0&1&3-x\end{vmatrix}}=(3-x)^{3}=-1\cdot (x-3)^{3}$
Again, there are three possibilities for the minimal polynomial $m_{1}(x)=(x-3)$ , $m_{2}(x)=(x-3)^{2}$ , and $m_{3}(x)=(x-3)^{3}$ . We compute $m_{1}(T)$
$T-3I={\begin{pmatrix}0&0&0\\1&0&0\\0&1&0\end{pmatrix}}$
and $m_{2}(T)$
$(T-3I)^{2}={\begin{pmatrix}0&0&0\\1&0&0\\0&1&0\end{pmatrix}}{\begin{pmatrix}0&0&0\\1&0&0\\0&1&0\end{pmatrix}}={\begin{pmatrix}0&0&0\\0&0&0\\1&0&0\end{pmatrix}}$
and $m_{3}(T)$ .
$(T-3I)^{3}=(T-3I)^{2}(T-3I)={\begin{pmatrix}0&0&0\\0&0&0\\1&0&0\end{pmatrix}}{\begin{pmatrix}0&0&0\\1&0&0\\0&1&0\end{pmatrix}}={\begin{pmatrix}0&0&0\\0&0&0\\0&0&0\end{pmatrix}}$
Therefore, the minimal polynomial is $m(x)=m_{3}(x)=(x-3)^{3}$ .
This case is also triangular, here upper triangular.
$c(x)=\left|T-xI\right|={\begin{vmatrix}2-x&0&1\\0&6-x&2\\0&0&2-x\end{vmatrix}}=(2-x)^{2}(6-x)=-(x-2)^{2}(x-6)$
There are two possibilities for the minimal polynomial, $m_{1}(x)=(x-2)(x-6)$ and $m_{2}(x)=(x-2)^{2}(x-6)$ . Computation shows that the minimal polynomial isn't $m_{1}(x)$ .
$(T-2I)(T-6I)={\begin{pmatrix}0&0&1\\0&4&2\\0&0&0\end{pmatrix}}{\begin{pmatrix}-4&0&1\\0&0&2\\0&0&-4\end{pmatrix}}={\begin{pmatrix}0&0&-4\\0&0&0\\0&0&0\end{pmatrix}}$
It therefore must be that $m(x)=m_{2}(x)=(x-2)^{2}(x-6)$ . Here is a verification.
$(T-2I)^{2}(T-6I)=(T-2I)\cdot {\bigl (}(T-2I)(T-6I){\bigr )}={\begin{pmatrix}0&0&1\\0&4&2\\0&0&0\end{pmatrix}}{\begin{pmatrix}0&0&-4\\0&0&0\\0&0&0\end{pmatrix}}={\begin{pmatrix}0&0&0\\0&0&0\\0&0&0\end{pmatrix}}$
The characteristic polynomial is
$c(x)=\left|T-xI\right|={\begin{vmatrix}2-x&2&1\\0&6-x&2\\0&0&2-x\end{vmatrix}}=(2-x)^{2}(6-x)=-(x-2)^{2}(x-6)$
and there are two possibilities for the minimal polynomial, $m_{1}(x)=(x-2)(x-6)$ and $m_{2}(x)=(x-2)^{2}(x-6)$ . Checking the first one
$(T-2I)(T-6I)={\begin{pmatrix}0&2&1\\0&4&2\\0&0&0\end{pmatrix}}{\begin{pmatrix}-4&2&1\\0&0&2\\0&0&-4\end{pmatrix}}={\begin{pmatrix}0&0&0\\0&0&0\\0&0&0\end{pmatrix}}$
shows that the minimal polynomial is $m(x)=m_{1}(x)=(x-2)(x-6)$ .
The characteristic polynomial is this.
$c(x)=\left|T-xI\right|={\begin{vmatrix}-1-x&4&0&0&0\\0&3-x&0&0&0\\0&-4&-1-x&0&0\\3&-9&-4&2-x&-1\\1&5&4&1&4-x\end{vmatrix}}=(x-3)^{3}(x+1)^{2}$
There are a number of possibilities for the minimal polynomial, listed here by ascending degree: $m_{1}(x)=(x-3)(x+1)$ , $m_{1}(x)=(x-3)^{2}(x+1)$ , $m_{1}(x)=(x-3)(x+1)^{2}$ , $m_{1}(x)=(x-3)^{3}(x+1)$ , $m_{1}(x)=(x-3)^{2}(x+1)^{2}$ , and $m_{1}(x)=(x-3)^{3}(x+1)^{2}$ . The first one doesn't pan out
${\begin{array}{rl}(T-3I)(T+1I)&={\begin{pmatrix}-4&4&0&0&0\\0&0&0&0&0\\0&-4&-4&0&0\\3&-9&-4&-1&-1\\1&5&4&1&1\end{pmatrix}}{\begin{pmatrix}0&4&0&0&0\\0&4&0&0&0\\0&-4&0&0&0\\3&-9&-4&3&-1\\1&5&4&1&5\end{pmatrix}}\\&={\begin{pmatrix}0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\-4&-4&0&-4&-4\\4&4&0&4&4\end{pmatrix}}\end{array}}$
but the second one does.
$(T-3I)^{2}(T+1I)=(T-3I){\bigl (}(T-3I)(T+1I){\bigr )}$
${\begin{aligned}&={\begin{pmatrix}-4&4&0&0&0\\0&0&0&0&0\\0&-4&-4&0&0\\3&-9&-4&-1&-1\\1&5&4&1&1\end{pmatrix}}{\begin{pmatrix}0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\-4&-4&0&-4&-4\\4&4&0&4&4\end{pmatrix}}\\&={\begin{pmatrix}0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\end{pmatrix}}\end{aligned}}$
The minimal polynomial is $m(x)=(x-3)^{2}(x+1)$ .

Problem 3

Find the minimal polynomial of this matrix.

{\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\end{pmatrix}}

Answer

Its characteristic polynomial has complex roots.

{\begin{vmatrix}-x&1&0\\0&-x&1\\1&0&-x\end{vmatrix}}=(1-x)\cdot (x-(-{\frac {1}{2}}+{\frac {\sqrt {3}}{2}}i))\cdot (x-(-{\frac {1}{2}}-{\frac {\sqrt {3}}{2}}i))

As the roots are distinct, the characteristic polynomial equals the minimal polynomial.

This exercise is recommended for all readers.

Problem 4

What is the minimal polynomial of the differentiation operator $d/dx$ on ${\mathcal {P}}_{n}$ ?

Answer

We know that ${\mathcal {P}}_{n}$ is a dimension $n+1$ space and that the differentiation operator is nilpotent of index $n+1$ (for instance, taking $n=3$ , ${\mathcal {P}}_{3}=\{c_{3}x^{3}+c_{2}x^{2}+c_{1}x+c_{0}\,{\big |}\,c_{3},\ldots ,c_{0}\in \mathbb {C} \}$ and the fourth derivative of a cubic is the zero polynomial). Represent this operator using the canonical form for nilpotent transformations.

{\begin{pmatrix}0&0&0&\ldots &&0\\1&0&0&&&0\\0&1&0&&&\\&&\ddots \\0&0&0&&1&0\end{pmatrix}}

This is an $(n+1)\!\times \!(n+1)$ matrix with an easy characteristic polynomial, $c(x)=x^{n+1}$ . (Remark: this matrix is ${\rm {Rep}}_{B,B}(d/dx)$ where $B=\langle x^{n},nx^{n-1},n(n-1)x^{n-2},\ldots ,n!\rangle$ .) To find the minimal polynomial as in Example 1.12 we consider the powers of $T-0I=T$ . But, of course, the first power of $T$ that is the zero matrix is the power $n+1$ . So the minimal polynomial is also $x^{n+1}$ .

This exercise is recommended for all readers.

Problem 5

Find the minimal polynomial of matrices of this form

{\begin{pmatrix}\lambda &0&0&\ldots &&0\\1&\lambda &0&&&0\\0&1&\lambda \\&&&\ddots \\&&&&\lambda &0\\0&0&\ldots &&1&\lambda \end{pmatrix}}

where the scalar $\lambda$ is fixed (i.e., is not a variable).

Answer

Call the matrix $T$ and suppose that it is $n\!\times \!n$ . Because $T$ is triangular, and so $T-xI$ is triangular, the characteristic polynomial is $c(x)=(x-\lambda )^{n}$ . To see that the minimal polynomial is the same, consider $T-\lambda I$ .

{\begin{pmatrix}0&0&0&\ldots &0\\1&0&0&\ldots &0\\0&1&0\\&&\ddots \\0&0&\ldots &1&0\end{pmatrix}}

Recognize it as the canonical form for a transformation that is nilpotent of degree $n$ ; the power $(T-\lambda I)^{j}$ is zero first when $j$ is $n$ .

Problem 6

What is the minimal polynomial of the transformation of ${\mathcal {P}}_{n}$ that sends $p(x)$ to $p(x+1)$ ?

Answer

The $n=3$ case provides a hint. A natural basis for ${\mathcal {P}}_{3}$ is $B=\langle 1,x,x^{2},x^{3}\rangle$ . The action of the transformation is

1\mapsto 1\quad x\mapsto x+1\quad x^{2}\mapsto x^{2}+2x+1\quad x^{3}\mapsto x^{3}+3x^{2}+3x+1

and so the representation ${\rm {Rep}}_{B,B}(t)$ is this upper triangular matrix.

{\begin{pmatrix}1&1&1&1\\0&1&2&3\\0&0&1&3\\0&0&0&1\end{pmatrix}}

Because it is triangular, the fact that the characteristic polynomial is $c(x)=(x-1)^{4}$ is clear. For the minimal polynomial, the candidates are $m_{1}(x)=(x-1)$ ,

T-1I={\begin{pmatrix}0&1&1&1\\0&0&2&3\\0&0&0&3\\0&0&0&0\end{pmatrix}}

$m_{2}(x)=(x-1)^{2}$ ,

(T-1I)^{2}={\begin{pmatrix}0&0&2&6\\0&0&0&6\\0&0&0&0\\0&0&0&0\end{pmatrix}}

$m_{3}(x)=(x-1)^{3}$ ,

(T-1I)^{3}={\begin{pmatrix}0&0&0&6\\0&0&0&0\\0&0&0&0\\0&0&0&0\end{pmatrix}}

and $m_{4}(x)=(x-1)^{4}$ . Because $m_{1}$ , $m_{2}$ , and $m_{3}$ are not right, $m_{4}$ must be right, as is easily verified.

In the case of a general $n$ , the representation is an upper triangular matrix with ones on the diagonal. Thus the characteristic polynomial is $c(x)=(x-1)^{n+1}$ . One way to verify that the minimal polynomial equals the characteristic polynomial is argue something like this: say that an upper triangular matrix is $0$ -upper triangular if there are nonzero entries on the diagonal, that it is $1$ -upper triangular if the diagonal contains only zeroes and there are nonzero entries just above the diagonal, etc. As the above example illustrates, an induction argument will show that, where $T$ has only nonnegative entries, $T^{j}$ is $j$ -upper triangular. That argument is left to the reader.

Problem 7

What is the minimal polynomial of the map $\pi :\mathbb {C} ^{3}\to \mathbb {C} ^{3}$ projecting onto the first two coordinates?

Answer

The map twice is the same as the map once: $\pi \circ \pi =\pi$ , that is, $\pi ^{2}=\pi$ and so the minimal polynomial is of degree at most two since $m(x)=x^{2}-x$ will do. The fact that no linear polynomial will do follows from applying the maps on the left and right side of $c_{1}\cdot \pi +c_{0}\cdot {\mbox{id}}=z$ (where $z$ is the zero map) to these two vectors.

{\begin{pmatrix}0\\0\\1\end{pmatrix}}\qquad {\begin{pmatrix}1\\0\\0\end{pmatrix}}

Thus the minimal polynomial is $m$ .

Problem 8

Find a $3\!\times \!3$ matrix whose minimal polynomial is $x^{2}$ .

Answer

This is one answer.

{\begin{pmatrix}0&0&0\\1&0&0\\0&0&0\end{pmatrix}}

Problem 9

What is wrong with this claimed proof of Lemma 1.9: "if $c(x)=\left|T-xI\right|$ then $c(T)=\left|T-TI\right|=0$ "? (Cullen 1990)

Answer

The $x$ must be a scalar, not a matrix.

Problem 10

Verify Lemma 1.9 for $2\!\times \!2$ matrices by direct calculation.

Answer

The characteristic polynomial of

T={\begin{pmatrix}a&b\\c&d\end{pmatrix}}

is $(a-x)(d-x)-bc=x^{2}-(a+d)x+(ad-bc)$ . Substitute

{\begin{pmatrix}a&b\\c&d\end{pmatrix}}^{2}-(a+d){\begin{pmatrix}a&b\\c&d\end{pmatrix}}+(ad-bc){\begin{pmatrix}1&0\\0&1\end{pmatrix}}

={\begin{pmatrix}a^{2}+bc&ab+bd\\ac+cd&bc+d^{2}\end{pmatrix}}-{\begin{pmatrix}a^{2}+ad&ab+bd\\ac+cd&ad+d^{2}\end{pmatrix}}+{\begin{pmatrix}ad-bc&0\\0&ad-bc\end{pmatrix}}

and just check each entry sum to see that the result is the zero matrix.

This exercise is recommended for all readers.

Problem 11

Prove that the minimal polynomial of an $n\!\times \!n$ matrix has degree at most $n$ (not $n^{2}$ as might be guessed from this subsection's opening). Verify that this maximum, $n$ , can happen.

Answer

By the Cayley-Hamilton theorem the degree of the minimal polynomial is less than or equal to the degree of the characteristic polynomial, $n$ . Example 1.12 shows that $n$ can happen.

This exercise is recommended for all readers.

Problem 12

The only eigenvalue of a nilpotent map is zero. Show that the converse statement holds.

Answer

Suppose that $t$ 's only eigenvalue is zero. Then the characteristic polynomial of $t$ is $x^{n}$ . Because $t$ satisfies its characteristic polynomial, it is a nilpotent map.

Problem 13

What is the minimal polynomial of a zero map or matrix? Of an identity map or matrix?

Answer

A minimal polynomial must have leading coefficient $1$ , and so if the minimal polynomial of a map or matrix were to be a degree zero polynomial then it would be $m(x)=1$ . But the identity map or matrix equals the zero map or matrix only on a trivial vector space.

So in the nontrivial case the minimal polynomial must be of degree at least one. A zero map or matrix has minimal polynomial $m(x)=x$ , and an identity map or matrix has minimal polynomial $m(x)=x-1$ .

This exercise is recommended for all readers.

Problem 14

Interpret the minimal polynomial of Example 1.2 geometrically.

Answer

The polynomial can be read geometrically to say "a $60^{\circ }$ rotation minus two rotations of $30^{\circ }$ equals the identity."

Problem 15

What is the minimal polynomial of a diagonal matrix?

Answer

For a diagonal matrix

T={\begin{pmatrix}t_{1,1}&0\\0&t_{2,2}\\&&\ddots \\&&&t_{n,n}\end{pmatrix}}

the characteristic polynomial is $(t_{1,1}-x)(t_{2,2}-x)\cdots (t_{n,n}-x)$ . Of course, some of those factors may be repeated, e.g., the matrix might have $t_{1,1}=t_{2,2}$ . For instance, the characteristic polynomial of

D={\begin{pmatrix}3&0&0\\0&3&0\\0&0&1\end{pmatrix}}

is $(3-x)^{2}(1-x)=-1\cdot (x-3)^{2}(x-1)$ .

To form the minimal polynomial, take the terms $x-t_{i,i}$ , throw out repeats, and multiply them together. For instance, the minimal polynomial of $D$ is $(x-3)(x-1)$ . To check this, note first that Theorem 1.8, the Cayley-Hamilton theorem, requires that each linear factor in the characteristic polynomial appears at least once in the minimal polynomial. One way to check the other direction— that in the case of a diagonal matrix, each linear factor need appear at most once— is to use a matrix argument. A diagonal matrix, multiplying from the left, rescales rows by the entry on the diagonal. But in a product $(T-t_{1,1}I)\cdots$ , even without any repeat factors, every row is zero in at least one of the factors.

For instance, in the product

(D-3I)(D-1I)=(D-3I)(D-1I)I={\begin{pmatrix}0&0&0\\0&0&0\\0&0&-2\end{pmatrix}}{\begin{pmatrix}2&0&0\\0&2&0\\0&0&0\end{pmatrix}}{\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}}

because the first and second rows of the first matrix $D-3I$ are zero, the entire product will have a first row and second row that are zero. And because the third row of the middle matrix $D-1I$ is zero, the entire product has a third row of zero.

This exercise is recommended for all readers.

Problem 16

A projection is any transformation $t$ such that $t^{2}=t$ . (For instance, the transformation of the plane $\mathbb {R} ^{2}$ projecting each vector onto its first coordinate will, if done twice, result in the same value as if it is done just once.) What is the minimal polynomial of a projection?

Answer

This subsection starts with the observation that the powers of a linear transformation cannot climb forever without a "repeat", that is, that for some power $n$ there is a linear relationship $c_{n}\cdot t^{n}+\dots +c_{1}\cdot t+c_{0}\cdot {\mbox{id}}=z$ where $z$ is the zero transformation. The definition of projection is that for such a map one linear relationship is quadratic, $t^{2}-t=z$ . To finish, we need only consider whether this relationship might not be minimal, that is, are there projections for which the minimal polynomial is constant or linear?

For the minimal polynomial to be constant, the map would have to satisfy that $c_{0}\cdot {\mbox{id}}=z$ , where $c_{0}=1$ since the leading coefficient of a minimal polynomial is $1$ . This is only satisfied by the zero transformation on a trivial space. This is indeed a projection, but not a very interesting one.

For the minimal polynomial of a transformation to be linear would give $c_{1}\cdot t+c_{0}\cdot {\mbox{id}}=z$ where $c_{1}=1$ . This equation gives $t=-c_{0}\cdot {\mbox{id}}$ . Coupling it with the requirement that $t^{2}=t$ gives $t^{2}=(-c_{0})^{2}\cdot {\mbox{id}}=-c_{0}\cdot {\mbox{id}}$ , which gives that $c_{0}=0$ and $t$ is the zero transformation or that $c_{0}=1$ and $t$ is the identity.

Thus, except in the cases where the projection is a zero map or an identity map, the minimal polynomial is $m(x)=x^{2}-x$ .

Problem 17

The first two items of this question are review.

Prove that the composition of one-to-one maps is one-to-one.
Prove that if a linear map is not one-to-one then at least one nonzero vector from the domain is sent to the zero vector in the codomain.
Verify the statement, excerpted here, that preceeds Theorem 1.8.

... if a minimial polynomial $m(x)$ for a transformation $t$ factors as $m(x)=(x-\lambda _{1})^{q_{1}}\cdots (x-\lambda _{\ell })^{q_{\ell }}$ then $m(t)=(t-\lambda _{1})^{q_{1}}\circ \cdots \circ (t-\lambda _{\ell })^{q_{\ell }}$ is the zero map. Since $m(t)$ sends every vector to zero, at least one of the maps $t-\lambda _{i}$ sends some nonzero vectors to zero. ... Rewording ...: at least some of the $\lambda _{i}$ are eigenvalues.

Answer

This is a property of functions in general, not just of linear functions. Suppose that $f$ and $g$ are one-to-one functions such that $f\circ g$ is defined. Let $f\circ g(x_{1})=f\circ g(x_{2})$ , so that $f(g(x_{1}))=f(g(x_{2}))$ . Because $f$ is one-to-one this implies that $g(x_{1})=g(x_{2})$ . Because $g$ is also one-to-one, this in turn implies that $x_{1}=x_{2}$ . Thus, in summary, $f\circ g(x_{1})=f\circ g(x_{2})$ implies that $x_{1}=x_{2}$ and so $f\circ g$ is one-to-one.
If the linear map $h$ is not one-to-one then there are unequal vectors ${\vec {v}}_{1}$ , ${\vec {v}}_{2}$ that map to the same value $h({\vec {v}}_{1})=h({\vec {v}}_{2})$ . Because $h$ is linear, we have ${\vec {0}}=h({\vec {v}}_{1})-h({\vec {v}}_{2})=h({\vec {v}}_{1}-{\vec {v}}_{2})$ and so ${\vec {v}}_{1}-{\vec {v}}_{2}$ is a nonzero vector from the domain that is mapped by $h$ to the zero vector of the codomain ( ${\vec {v}}_{1}-{\vec {v}}_{2}$ does not equal the zero vector of the domain because ${\vec {v}}_{1}$ does not equal ${\vec {v}}_{2}$ ).
The minimal polynomial $m(t)$ sends every vector in the domain to zero and so it is not one-to-one (except in a trivial space, which we ignore). By the first item of this question, since the composition $m(t)$ is not one-to-one, at least one of the components $t-\lambda _{i}$ is not one-to-one. By the second item, $t-\lambda _{i}$ has a nontrivial nullspace. Because $(t-\lambda _{i})({\vec {v}})={\vec {0}}$ holds if and only if $t({\vec {v}})=\lambda _{i}\cdot {\vec {v}}$ , the prior sentence gives that $\lambda _{i}$ is an eigenvalue (recall that the definition of eigenvalue requires that the relationship hold for at least one nonzero ${\vec {v}}$ ).

Problem 18

True or false: for a transformation on an $n$ dimensional space, if the minimal polynomial has degree $n$ then the map is diagonalizable.

Answer

This is false. The natural example of a non-diagonalizable transformation works here. Consider the transformation of $\mathbb {C} ^{2}$ represented with respect to the standard basis by this matrix.

N={\begin{pmatrix}0&1\\0&0\end{pmatrix}}

The characteristic polynomial is $c(x)=x^{2}$ . Thus the minimal polynomial is either $m_{1}(x)=x$ or $m_{2}(x)=x^{2}$ . The first is not right since $N-0\cdot I$ is not the zero matrix, thus in this example the minimal polynomial has degree equal to the dimension of the underlying space, and, as mentioned, we know this matrix is not diagonalizable because it is nilpotent.

Problem 19

Let $f(x)$ be a polynomial. Prove that if $A$ and $B$ are similar matrices then $f(A)$ is similar to $f(B)$ .

Now show that similar matrices have the same characteristic polynomial.
Show that similar matrices have the same minimal polynomial.
Decide if these are similar.
${\begin{pmatrix}1&3\\2&3\end{pmatrix}}\qquad {\begin{pmatrix}4&-1\\1&1\end{pmatrix}}$

Answer

Let $A$ and $B$ be similar $A=PBP^{-1}$ . From the facts that

A^{n}=(PBP^{-1})^{n}=(PBP^{-1})(PBP^{-1})\cdots (PBP^{-1})

=PB(P^{-1}P)B(P^{-1}P)\cdots (P^{-1}P)BP^{-1}=PB^{n}P^{-1}

and $c\cdot A=c\cdot (PBP^{-1})=P(c\cdot B)P^{-1}$ follows the required fact that for any polynomial function $f$ we have $f(A)=P\,f(B)\,P^{-1}$ . For instance, if $f(x)=x^{2}+2x+3$ then

A^{2}+2A+3I=(PBP^{-1})^{2}+2\cdot PBP^{-1}+3\cdot I

=(PBP^{-1})(PBP^{-1})+P(2B)P^{-1}+3\cdot PP^{-1}=P(B^{2}+2B+3I)P^{-1}

shows that $f(A)$ is similar to $f(B)$ .

Taking $f$ to be a linear polynomial we have that $A-xI$ is similar to $B-xI$ . Similar matrices have equal determinants (since $\left|A\right|=\left|PBP^{-1}\right|=\left|P\right|\cdot \left|B\right|\cdot \left|P^{-1}\right|=1\cdot \left|B\right|\cdot 1=\left|B\right|$ ). Thus the characteristic polynomials are equal.
As $P$ and $P^{-1}$ are invertible, $f(A)$ is the zero matrix when, and only when, $f(B)$ is the zero matrix.
They cannot be similar since they don't have the same characteristic polynomial. The characteristic polynomial of the first one is $x^{2}-4x-3$ while the characteristic polynomial of the second is $x^{2}-5x+5$ .

Problem 20

Show that a matrix is invertible if and only if the constant term in its minimal polynomial is not $0$ .
Show that if a square matrix $T$ is not invertible then there is a nonzero matrix $S$ such that $ST$ and $TS$ both equal the zero matrix.

Answer

Suppose that $m(x)=x^{n}+m_{n-1}x^{n-1}+\dots +m_{1}x+m_{0}$ is minimal for $T$ .

For the "if" argument, because $T^{n}+\dots +m_{1}T+m_{0}I$ is the zero matrix we have that $I=(T^{n}+\dots +m_{1}T)/(-m_{0})=T\cdot (T^{n-1}+\dots +m_{1}I)/(-m_{0})$ and so the matrix $(-1/m_{0})\cdot (T^{n-1}+\dots +m_{1}I)$ is the inverse of $T$ . For "only if", suppose that $m_{0}=0$ (we put the $n=1$ case aside but it is easy) so that $T^{n}+\dots +m_{1}T=(T^{n-1}+\dots +m_{1}I)T$ is the zero matrix. Note that $T^{n-1}+\dots +m_{1}I$ is not the zero matrix because the degree of the minimal polynomial is $n$ . If $T^{-1}$ exists then multiplying both $(T^{n-1}+\dots +m_{1}I)T$ and the zero matrix from the right by $T^{-1}$ gives a contradiction.
If $T$ is not invertible then the constant term in its minimal polynomial is zero. Thus,
$T^{n}+\dots +m_{1}T=(T^{n-1}+\dots +m_{1}I)T=T(T^{n-1}+\dots +m_{1}I)$
is the zero matrix.

This exercise is recommended for all readers.

Problem 21

Finish the proof of Lemma 1.7.
Give an example to show that the result does not hold if $t$ is not linear.

Answer

For the inductive step, assume that Lemma 1.7 is true for polynomials of degree $i,\ldots ,k-1$ and consider a polynomial $f(x)$ of degree $k$ . Factor $f(x)=k(x-\lambda _{1})^{q_{1}}\cdots (x-\lambda _{\ell })^{q_{\ell }}$ and let $k(x-\lambda _{1})^{q_{1}-1}\cdots (x-\lambda _{\ell })^{q_{\ell }}$ be $c_{n-1}x^{n-1}+\cdots +c_{1}x+c_{0}$ . Substitute:
${\begin{array}{rl}k(t-\lambda _{1})^{q_{1}}\circ \cdots \circ (t-\lambda _{\ell })^{q_{\ell }}({\vec {v}})&=(t-\lambda _{1})\circ (t-\lambda _{1})^{q_{1}}\circ \cdots \circ (t-\lambda _{\ell })^{q_{\ell }}({\vec {v}})\\&=(t-\lambda _{1})\,(c_{n-1}t^{n-1}({\vec {v}})+\cdots +c_{0}{\vec {v}})\\&=f(t)({\vec {v}})\end{array}}$
(the second equality follows from the inductive hypothesis and the third from the linearity of $t$ ).
One example is to consider the squaring map $s:\mathbb {R} \to \mathbb {R}$ given by $s(x)=x^{2}$ . It is nonlinear. The action defined by the polynomial $f(t)=t^{2}-1$ changes $s$ to $f(s)=s^{2}-1$ , which is this map.
$x{\stackrel {s^{2}-1}{\longmapsto }}s\circ s(x)-1=x^{4}-1$
Observe that this map differs from the map $(s-1)\circ (s+1)$ ; for instance, the first map takes $x=5$ to $624$ while the second one takes $x=5$ to $675$ .