# Linear algebra (Osnabrück 2024-2025)/Part I/Lecture 25

    Trigonalizable mappings

## Definition

Let $K$ denote a field, and let $V$ denote a finite-dimensional vector space. A linear mapping $\varphi \colon V\rightarrow V$
is called trigonalizable, if there exists a basis such that the describing matrix of $\varphi$ with respect to this basis is an
Diagonalizable linear mappings are in particular trigonalizable. The inverse statement is not true, as example shows. We will see in fact that a linear mapping is trigonalizable if and only if its characteristic polynomial factors into linear factors. A square matrix $M$ is called trigonalizable if the corresponding linear mapping $K^{n}\rightarrow K^{n}$ is trigonalizable. This means that there exists a basis such that the mapping is described by an upper triangular matrix with respect to this basis, or, that there exists an invertible matrix $B$ (the base change matrix) such that
    $BMB^{-1}$
is an upper triangular matrix. Therefore, a matrix is trigonalizable if and only if it is similar to an upper triangular matrix. The process of finding such a basis and to perform this base change is called trigonalization.

## Example

We claim that the matrix
    $M={\begin{pmatrix}3&1\\-1&1\end{pmatrix}}\,$
is trigonalizable. The matrix
    $B={\begin{pmatrix}3&2\\1&1\end{pmatrix}}\,$
is invertible with the inverse matrix
    $B^{-1}={\begin{pmatrix}1&-2\\-1&3\end{pmatrix}}\,.$
A direct computation shows
    $BMB^{-1}={\begin{pmatrix}3&2\\1&1\end{pmatrix}}{\begin{pmatrix}3&1\\-1&1\end{pmatrix}}{\begin{pmatrix}1&-2\\-1&3\end{pmatrix}}={\begin{pmatrix}3&2\\1&1\end{pmatrix}}{\begin{pmatrix}2&-3\\-2&5\end{pmatrix}}={\begin{pmatrix}2&1\\0&2\end{pmatrix}}\,.$
In this verification of trigonalizability, the transformation matrix $B$ arises just like that. We get a more reasonable proof with the help of the characteristic polynomial and fact. The characteristic polynomial is
    $\chi _{M}=\det {\begin{pmatrix}X-3&-1\\1&X-1\end{pmatrix}}=(X-3)(X-1)+1=X^{2}-4X+4=(X-2)^{2}\,,$
and this factors into linear factors.

## Lemma

Let $V_{1},\ldots ,V_{n}$ denote finite-dimensional vector spaces over the field $K$, let
    $\varphi _{i}\colon V_{i}\longrightarrow V_{i}$
denote linear mappings, and let
    $\varphi =\varphi _{1}\times \cdots \times \varphi _{n}\colon V_{1}\times \cdots \times V_{n}\longrightarrow V_{1}\times \cdots \times V_{n}$
denote the product mapping. Then $\varphi$ is trigonalizable
$\varphi _{i}$

### Proof

$\Box$
In particular, the preceding statement holds when
    $V=\bigoplus _{i\in I}V_{i}\,$
is a direct sum of $\varphi$-invariant linear subspaces.
    Invariant linear subspaces
A trigonalizable endomorphism is described, with respect to a suitable basis, by a matrix of the form
    $M={\begin{pmatrix}_{1}&\ast &\cdots &\cdots &\ast \\0&_{2}&\ast &\cdots &\ast \\\vdots &\ddots &\ddots &\ddots &\vdots \\0&\cdots &0&_{n-1}&\ast \\0&\cdots &\cdots &0&_{n}\end{pmatrix}}\,.$
A property which hold for such an upper triangular matrix and which can be described as a property of the linear mapping (being independent of a chosen basis), must hold for any trigonalizable mapping. We want to understand such properties. By an upper triangular matrix, the $j$-th standard vector $e_{j}$ is sent to
    $Me_{j}=a_{1j}e_{1}+\cdots +a_{jj}e_{j}\,.$
In particular, $e_{1}$ is a eigenvector with the eigenvalue $a_{11}$. It is typical for a trigonalizable mapping that the linear subspace
    $V_{j}=\langle e_{1},\ldots ,e_{j}\rangle \,$
is mapped by $M$ into itself. That is, the $V_{j}$ are $M$-invariant linear subspaces, which are contained in each other and those dimensions are $j$. We will show, after some preparations, that these properties characterize trigonalizable mappings.

## Lemma

Let $K$ denote a field, and let $V$ be a $n$-dimensional vector space. Let
    $\varphi \colon V\longrightarrow V$
be a linear mapping, and let $\lambda \in K$ be an eigenvalue of $\varphi$. Then there exists a $\varphi$-invariant linear subspace $U\subset V$
$n-1$

### Proof

Because of the condition and
fact, the mapping $\varphi -\lambda \operatorname {Id} _{V}$ has a nontrival kernel. Hence, this mapping is not injective and, due to fact, also not surjective. Therefore,
    $B:=\operatorname {Im} {\left(\varphi -\lambda \operatorname {Id} _{V}\right)}\subset V\,$
is a strict linear subspace of $V$. It follows that there exists also a linear subspace $U\subset V$ of dimension $n-1$, which contains $B$. For $u\in U$, we have
    $\varphi (u)=\lambda u+(\varphi -\lambda \operatorname {Id} _{V})u\in U+B\subseteq U\,.$
Hence, the image of $U$ belongs to $U$, that is, $U$ is $\varphi$-invariant.
$\Box$
When $U\subseteq V$ is an $\varphi$-invariant linear subspace, and $P\in K[X]$ is a polynomial, then $U$ is also $P(\varphi )$-invariant, see exercise. In this situation, the following identity holds.

## Lemma

Let $K$ be a field, $V$ a $K$-vector space and
    $\varphi \colon V\longrightarrow V$
a linear mapping. Let $U\subseteq V$ be an $\varphi$-invariant linear subspace. Then, for every polynomial $P\in K[X]$, the relation
    $P{\left(\varphi {|}_{U}\right)}={\left(P(\varphi )\right)}{|}_{U}\,$
holds, where here $\varphi {|}_{U}$ denotes the restricted mapping

### Proof

This can be checked directly for the powers $X^{n}$ and for linear combinations of powers.
$\Box$

## Corollary

Let $K$ denote a field, and let $V$ denote a $K$-vector space of finite dimension. Let
    $\varphi \colon V\longrightarrow V$
be a linear mapping. Let $U\subseteq V$ be a $\varphi$-invariant linear subspace and
    $\varphi {|}_{U}\colon U\longrightarrow U$
the restriction to $U$ (also in the target). Then the minimal polynomial
$\varphi$
$\varphi {|}_{U}$

### Proof

Let $\mu$ be the minimal polynomial of $\varphi$. For $u\in U$, we have
    $\mu {\left(\varphi {|}_{U}\right)}(u)=\mu (\varphi )(u)=0\,,$
due to fact. Therefore, $\mu$ annihilates the restricted endomorphism $\varphi {|}_{U}$, and so $\mu$ is a multiple of the minimal polynomial of $\varphi {|}_{U}$.
$\Box$

## Example

We consider the permutation matrix
    ${\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}}.$
The line $K{\begin{pmatrix}1\\1\\1\end{pmatrix}}$ is the eigenspace for the eigenvalue $1$. Moreover,
    $U=\langle {\begin{pmatrix}1\\-1\\0\end{pmatrix}},{\begin{pmatrix}0\\1\\-1\end{pmatrix}}\rangle \,$
is an invariant linear subspace (which, over $\mathbb {C}$, according to fact, can be decomposed further into smaller eigenspaces). With respect to the given basis, the restriction of the linear mapping to $U$ has the describing matrix
    ${\begin{pmatrix}0&-1\\1&-1\end{pmatrix}}.$
Therefore, the characteristic polynomial of this matrix is
    $X(X+1)+1=X^{2}+X+1\,.$
This is also the minimal polynomial of the restriction. The minimal polynomial of the permutation matrix is $X^{3}-1$, and indeed we have
    $X^{3}-1=(X-1)(X^{2}+X+1)\,$
in accordance with fact.
    Characterizations for trigonalizable mappings

## Definition

Let $K$ denote a field, and let $V$ denote a finite-dimensional vector space of dimension $n=\dim _{\left(V\right)}$. Then a chain of linear subspaces
    $0=V_{0}\subset V_{1}\subset \ldots \subset V_{n-1}\subset V_{n}=V\,$
$V$
Hence, a flag is a chain of linear subspaces, contained in each other, and where the dimension increase by $1$ in each step.

## Definition

Let $V$ be a vector space of dimension $n$, and let
    $f\colon V\longrightarrow V$
be a linear mapping. A flag
    $0=V_{0}\subset V_{1}\subset \ldots \subset V_{n-1}\subset V_{n}\,$
is called $f$-invariant, if $f(V_{i})\subseteq V_{i}$ holds for all
$i=0,1,\ldots ,n-1,n$

## Theorem

Let $K$ denote a field, and let $V$ denote a finite-dimensional vector space. Let
    $\varphi \colon V\longrightarrow V$
denote a
* $\varphi$ is trigonalizable.
* There exists a $\varphi$-invariant flag.
* The characteristic polynomial $\chi _{\varphi }$ splits into linear factors.
* The minimal polynomial $\mu _{\varphi }$ splits into linear factors.
$\varphi$
$M$
invertible matrix (set $n=\dim _{\left(V\right)}$) $B\in \operatorname {Mat} _{n\times n}(K)$ such that $BMB^{-1}$ is an

### Proof

Form (1) to (2). Let $v_{1},\ldots ,v_{n}$ be a basis with the property that the describing matrix of $\varphi$ with respect to this matrix is an upper triangular form. The action of this matrix shows directly that the linear subspaces
    $V_{i}:=\langle v_{1},\ldots ,v_{i}\rangle \,$
are $\varphi$-invariant and that they form an invariant flag.
From (2) to (1). Let
    $0=V_{0}\subset V_{1}\subset \ldots \subset V_{n-1}\subset V_{n}=V\,$
be a $\varphi$-invariant flag. Due to fact, there exists a basis $v_{1},\ldots ,v_{n}$ of $V$ such that
    $V_{i}=\langle v_{1},\ldots ,v_{i}\rangle \,.$
Since this flag is invariant, we have
    $\varphi (v_{i})=b_{1i}v_{1}+b_{2i}v_{2}+\cdots +b_{ii}v_{i}\,.$
Therefore, the describing matrix of $\varphi$ with respect to this basis is upper triangular.
From (1) to (3). The characteristic polynomial of $\varphi$ is equal to the characteristic polynomial $\chi _{M}$, where $M$ denotes a describing matrix with respect to an arbitrary basis. We may assume that $M$ is an upper triangular matrix. Then, according to fact, the characteristic polynomial is the product of the linear factors arising from the diagonal entries.
From (3) to (4). Due to fact, the minimal polynomial divides the characteristic polynomial.
From (4) to (2). We prove the statement by induction over $n$, the cases
    $n=0,1\,$
being clear. Due to the condition and fact and fact, the mapping $\varphi$ has an eigenvalue. Because of fact, there exists an $(n-1)$-dimensional linear subspace
    $V_{n-1}\subset V\,$
which is $\varphi$-invariant. Due to fact, the minimal polynomial of the restriction $\varphi {|}_{V_{n-1}}$ divides the minimal polynomial of $\varphi$, therefore, it also splits into linear factors. By the induction hypothesis, there exists an $\varphi {|}_{V_{n-1}}$-invariant flag
    $V_{1}\subset V_{2}\subset \ldots \subset V_{n-2}\subset V_{n-1}\,,$
and so this is also a $\varphi$-invariant flag.
The supplement follows as follows. Suppose that the trigonalizable mapping $\varphi$ is described by the matrix $M$ with respect to the basis ${\mathfrak {u}}$, and by the upper triangular matrix $T$ with respect to the basis ${\mathfrak {v}}$ Then, because of fact the relation $T=BMB^{-1}$ holds, where $B$ is the transformation matrix of the base change.
$\Box$

## Remark

The method to find an invariant flag, which is described in the proof of the implication (4) $\Rightarrow$ (2) of fact and which rests on
fact, is constructive. If the restriction $\varphi _{|}U_{i}$ to some invariant linear subspace $U_{i}$ already constructed does not have an eigenvalue, then we know that the linear mapping is not trigonalizable.

## Theorem

Let $M\in \operatorname {Mat} _{n\times n}(\mathbb {C} )$ denote a square matrix with complex entries. Then $M$ is

### Proof

This follows from fact and the Fundamental theorem of algebra.
$\Box$

## Example

We consider a real $2\times 2$-matrix $M={\begin{pmatrix}a&b\\c&d\end{pmatrix}}$. The characteristic polynomial is
    ${\begin{aligned}\chi _{M}&=\det {\left(xE_{2}-M\right)}\\&=\det {\begin{pmatrix}x-a&-b\\-c&x-d\end{pmatrix}}\\&=(x-a)(x-d)-bc\\&=x^{2}-(a+d)x+ad-bc\\&={\left(x-{\frac {a+d}{2}}\right)}^{2}-{\left({\frac {a+d}{2}}\right)}^{2}+ad-bc\\&={\left(x-{\frac {a+d}{2}}\right)}^{2}-{\left({\frac {a-d}{2}}\right)}^{2}-bc.\end{aligned}}$
This polynomial splits into (real) linear factors if and only if ${\left({\frac {a-d}{2}}\right)}^{2}+bc\geq 0$. The matrix is trigonalizable exactly in this case, due to fact.