# Short way for upper triangularization

We are given a matrix $$A = \begin{bmatrix} 3 & 0 & 1 \\ -1 & 4 & -3 \\ -1 & 0 & 5 \\ \end{bmatrix}$$ and we are asked to find a matrix $P$ such that $P^{-1}AP$ is upper triangular.

Here, we first find one eigenvalue as $\lambda= 4$. Then the matrix $$A-4I = \begin{bmatrix} -1 & 0 & 1 \\ -1 & 0 & -3 \\ -1 & 0 & 1 \\ \end{bmatrix}$$ has basis formed from $f_1 = (-1,-1,-1)^T$, $f_2 = (1,-3,1)^T$. We extend this to a basis of the whole space by adjoining $f_3 = (1,0,0)^T$, and so we have base-change matrix $$P = \begin{bmatrix} -1 & 1 & 1 \\ -1 & -3 & 0 \\ -1 & 1 & 0 \\ \end{bmatrix}.$$

Then, by using some computational tools, we find that $$P^{-1}AP = \begin{bmatrix} 3 & 1 & 1 \\ -1 & 5 & 0 \\ 0 & 0 & 4 \\ \end{bmatrix}$$

Now, we need to look at $$B = \begin{bmatrix} 3 & 1 \\ -1 & 5 \\ \end{bmatrix},$$ which has eigenvalue $\lambda = 4$. So we have $$B-4I = \begin{bmatrix} -1 & 1 \\ -1 & 1 \\ \end{bmatrix}.$$ So basis for the image of this is $(1,1)^T$. We extend this to the basis $(1,1)^T$, $(1,0)^T$ of $\mathbb{R}^2$. Now, going back to $\mathbb{R}^3$, we have the matrix $$Q = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix}.$$

Then, by using calculation tools, we get $$Q^{-1}P^{-1}APQ = \begin{bmatrix} 4 & -1 & 0 \\ 0 & 4 & 1 \\ 0 & 0 & 4 \\ \end{bmatrix},$$ which is in upper triangular form.

Now, what I wanted to ask is that is there a way to directly find the matrix $R = PQ$ such that $R^{-1}AR$ is upper triangular, without going through these steps?

• Yes, read the answers here. – Dietrich Burde Apr 19 '18 at 16:58

Suppose we begin with the matrix $$A = \begin{bmatrix} 3 & 0 & 1 \\ -1 & 4 & -3 \\ -1 & 0 & 5 \\ \end{bmatrix}$$ and use "double Gaussian elimination". That is, whenever we multiply by an elementary row operation $E$ on the left, we must also multiply by the corresponding column operation $E^{-1}$ on the right. We begin by removing the $-1$ in the bottom left corner by doing a row operation of the form $R_3 \leftarrow R_3 + \lambda R_1$. We must then also perform the column operation $C_1 \leftarrow C_1 - \lambda C_3$. Since we want this to cancel the bottom-left cell, we see that $\lambda$ must satisfy $$-1 + 3 \lambda - \lambda(5 + \lambda) = 0 \iff \lambda^2+2\lambda+1 = (\lambda+1)^2 = 0$$ So we take $\lambda = -1$, and apply those operations to get $$A_1 = \begin{bmatrix} 4 & 0 & 1 \\ -4 & 4 & -3 \\ 0 & 0 & 4 \\ \end{bmatrix}$$

Now, this is almost in upper-triangular form: if we perform the paired operations $(R_1 \leftrightarrow R_2, C_1 \leftrightarrow C_2)$ then we end up with

$$A_2 = \begin{bmatrix} 4 & -4 & -3 \\ 0 & 4 & 1 \\ 0 & 0 & 4 \\ \end{bmatrix}$$

which is upper-triangular. Let $P$ be the matrix tracking the column operations, so that $$P = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \\ \end{bmatrix}$$

Then we have $P^{-1} A P = A_2$.

• I was looking for something like this one. Since I also know the Slyvester's Law of Inertia, I am familiar to this concept, you also explained it very clearly. Thank you very much :) – ArsenBerk Apr 28 '18 at 19:15

$\newenvironment{gmatrix}{\left\lgroup\begin{matrix}}{\end{matrix}\right\rgroup}$Here it is a general way of finding Jordan normal forms. It applies to your question because all eigenvalues of $A$ are real.

Step 1: Computing the invariant factors of $λI - A$ to get its elementary divisors.

The monic greatest common divisor of all $1 × 1$ minors of $λI - A$ is $D_1(λ) = 1$, and that of all $2 × 2$ minors is $D_2(λ) = 1$, and that of the $3 × 3$ minors is$$D_3(λ) = |λI - A| = (λ - 4)(λ - 4 + \sqrt{2})(λ - 4 - \sqrt{2}).$$ Thus the invariant factors of $λI - A$ are$$d_1(λ) = D_1(λ) = 1,\quad d_2(λ) = \frac{D_1(λ)}{D_2(λ)} = 1,\\ d_3(λ) = \frac{D_3(λ)}{D_2(λ)} = (λ - 4)(λ - 4 + \sqrt{2})(λ - 4 - \sqrt{2}),$$ and the elementary divisors of $λI - A$ are$$λ - 4,\ λ - 4 + \sqrt{2},\ λ - 4 - \sqrt{2}.$$

Step 2: Writing down the Jordan normal form of $A$ based on the elementary divisors of $λI - A$.

Since the elementary divisors of $λI - A$ are $λ - 4$, $λ - 4 + \sqrt{2}$, $λ - 4 - \sqrt{2}$, the Jordan normal form of $A$ is$$J = \begin{gmatrix} 4 &&\\ & 4 - \sqrt{2} &\\ && 4 + \sqrt{2} \end{gmatrix}.$$

Step 3: Finding all the Jordan chains and the $P$.

In this case, it is easy to get that$$x_1 = \begin{gmatrix} 0 \\ 1 \\ 0 \end{gmatrix}, x_2 = \begin{gmatrix} 1 + \sqrt{2} \\ 1 + 2\sqrt{2} \\ 1 \end{gmatrix}, x_3 = \begin{gmatrix} 1 - \sqrt{2} \\ 1 - 2\sqrt{2} \\ 1 \end{gmatrix}$$ are the three Jordan chains (here eigenvectors in fact) of $λ - 4$, $λ - 4 + \sqrt{2}$, $λ - 4 - \sqrt{2}$, respectively. Thus$$P = (x_1, x_2, x_3) = \begin{gmatrix} 0 & 1 + \sqrt{2} & 1 - \sqrt{2}\\ 1 & 1 + 2\sqrt{2} & 1 - 2\sqrt{2}\\ 0 & 1 & 1 \end{gmatrix}.$$

• Thank you very much for your answer. I think this is a diagonalization process, which makes the matrix $P^{-1}AP$ diagonal, hence upper triangular. However, what I was looking for is some algorithm or short-cut to directly find the matrix $PQ$ in the end of the question, which doesn't make it diagonal but upper triangular. – ArsenBerk Apr 22 '18 at 9:03

There is a misprint in the announcement. The $(1,3)$ element of $A$ should be $+1$ rather than $-1$ in order for $A$ to be consistent with the calculations that follow in your posted question.

So let $A=\begin{bmatrix} 3&0&1\\-1&4&-3\\-1&0&5 \end{bmatrix}$ and set $N=A-4I= \begin{bmatrix} -1&0&1\\-1&0&-3\\-1&0&1 \end{bmatrix}$.

Then $N^2= \begin{bmatrix} 0&0&0\\4&0&-4\\0&0&0 \end{bmatrix}$ and $N^3=0$. So $N$ is nilpotent and $4$ is a triple eigenvalue of $A$ having a `Jordan chain' of length 3. A simple way to triangularize $A$ is then to calculate 3 vectors that generate this chain. For this you may note that $\ker N =\langle v_1\rangle$ is generated by $v_1=\begin{bmatrix} 0 & 1 & 0 \end{bmatrix}^T$ and $\ker N^2 =\langle v_1,v_2\rangle$ with e.g. $v_2=\begin{bmatrix} -1 & 1 & -1\end{bmatrix}^T$. Finally, set e.g. $v_3=\begin{bmatrix} 2 & 0 & -2\end{bmatrix}^T$ so that $\ker(N^3)={\Bbb R}^3=\langle v_1,v_2,v_3\rangle$.

Now set $R= [v_1 \; v_2\; v_3] = \begin{bmatrix} 0&-1&2\\1&1&0\\0&-1&-2\end{bmatrix}$ and we get: $A R = R \begin{bmatrix} 4 & 4 & 0\\ 0&4&4\\0&0&4\end{bmatrix}$ as wanted.

You may, of course, replace $v_2$ by $a v_2+b v_1$ with $a\neq 0$ which will change e.g. the $(1,2)$ element of the Jordan form (and similarly for $v_3$). My choice was just in order to get easy numbers and a nice end-result.