IMC 2001 · Day 1 · P5

The statement will be proved by induction on $n$. For $n = 1$, there is nothing to do. In the case $n = 2$, write $A = \begin{bmatrix} a & b \\ c & d \end{bmatrix}$. If $b \ne 0$, and $c \ne 0$ or $b = c = 0$ then $A$ is similar to $$\begin{bmatrix} 1 & 0 \\ a/b & 1 \end{bmatrix} \begin{bmatrix} a & b \\ c & d \end{bmatrix} \begin{bmatrix} 1 & 0 \\ -a/b & 1 \end{bmatrix} = \begin{bmatrix} 0 & b \\ c - ad/b & a + d \end{bmatrix}$$ or $$\begin{bmatrix} 1 & -a/c \\ 0 & 1 \end{bmatrix} \begin{bmatrix} a & b \\ c & d \end{bmatrix} \begin{bmatrix} 1 & a/c \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 0 & b - ad/c \\ c & a + d \end{bmatrix},$$ respectively. If $b = c = 0$ and $a \ne d$, then $A$ is similar to $$\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} a & 0 \\ 0 & d \end{bmatrix} \begin{bmatrix} 1 & -1 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} a & d - a \\ 0 & d \end{bmatrix},$$ and we can perform the step seen in the case $b \ne 0$ again.

Assume now that $n > 3$ and the problem has been solved for all $n' < n$. Let $A = \begin{bmatrix} A' & * \\ * & \beta \end{bmatrix}$, where $A'$ is $(n-1) \times (n-1)$ matrix. Clearly we may assume that $A' \ne \lambda' I$, so the induction provides a $P$ with, say, $P^{-1} A' P = \begin{bmatrix} 0 & * \\ * & \alpha \end{bmatrix}$. But then the matrix $$B = \begin{bmatrix} P^{-1} & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} A' & * \\ * & \beta \end{bmatrix} \begin{bmatrix} P & 0 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} P^{-1} A' P & * \\ * & \beta \end{bmatrix}$$ is similar to $A$ and its diagonal is $(0, 0, \dots, 0, \alpha, \beta)$. On the other hand, we may also view $B$ as $\begin{bmatrix} 0 & * \\ * & C \end{bmatrix}$, where $C$ is an $(n-1) \times (n-1)$ matrix with diagonal $(0, \dots, 0, \alpha, \beta)$. If the inductive hypothesis is applicable to $C$, we would have $Q^{-1} C Q = D$, with $D = \begin{bmatrix} 0 & * \\ * & \gamma \end{bmatrix}$ so that finally the matrix $$E = \begin{bmatrix} 1 & 0 \\ 0 & Q^{-1} \end{bmatrix} \cdot B \cdot \begin{bmatrix} 1 & 0 \\ 0 & Q \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & Q^{-1} \end{bmatrix} \begin{bmatrix} 0 & * \\ * & C \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & Q \end{bmatrix} = \begin{bmatrix} 0 & * \\ * & D \end{bmatrix}$$ is similar to $A$ and its diagonal is $(0, 0, \dots, 0, \gamma)$, as required.

The inductive argument can fail only when $n - 1 = 2$ and the resulting matrix applying $P$ has the form $$P^{-1} A P = \begin{bmatrix} 0 & a & b \\ c & d & 0 \\ e & 0 & d \end{bmatrix}$$ where $d \ne 0$. The numbers $a$, $b$, $c$, $e$ cannot be 0 at the same time. If, say, $b \ne 0$, $A$ is similar to $$\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix} \begin{bmatrix} 0 & a & b \\ c & d & 0 \\ e & 0 & d \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -1 & 0 & 1 \end{bmatrix} = \begin{bmatrix} -b & a & b \\ c & d & 0 \\ e - b - d & a & b + d \end{bmatrix}.$$ Performing half of the induction step again, the diagonal of the resulting matrix will be $(0, d-b, d+b)$ (the trace is the same) and the induction step can be finished. The cases $a \ne 0$, $c \ne 0$ and $e \ne 0$ are similar.