# Upper Triangularising a Matrix Kay and Wilson Linear Algebra

I have been reading Linear Algebra by Richard Kay and Robert Wilson and am specifically looking at pages 156-158. I understand the book's proof on page 156 of the proposition 10.10: "Let $V= \mathbb{C}^n$ be the $n$ dimensional vector space over $\mathbb{C}$ and suppose $f$ is a linear transformation from $V$ to $V$. Then there is a basis $\{v_1, v_2,..., v_n\}$ of $V$ such that , with respect to this basis, $f$ is upper triangular." I undertand this to be another way of saying for any square matrix $A$ over $\mathbb{C}$ there is an invertible matrix $P$ over $\mathbb{C}$ such that $P^{-1}AP$ is upper triangular.

However when actually put into practice I don't understand what is going on. The second example 10.13 it gives on page 157 is $A= \begin{pmatrix} 3 & 0 & -1 \\ -1 & 4 & -3 \\-1 & 0 & 5 \end{pmatrix}$

We see $\begin{pmatrix} 0 \\ 1 \\0 \end{pmatrix}$ is an eigenvector with eigenvalue $4$.

Then $A-4I = \begin{pmatrix} -1 & 0 & -1 \\ -1 & 0 & -3 \\-1 & 0 & 1 \end{pmatrix}$

So the image of $A-4I$ has basis formed by $f_1=$ $\begin{pmatrix} -1 \\ -1 \\-1 \end{pmatrix}$ and $f_2=$ $\begin{pmatrix} -1 \\ -3 \\1 \end{pmatrix}$. We extend this to a basis of the whole space by adjoining $f_3=$ $\begin{pmatrix} 1 \\ 0 \\0 \end{pmatrix}$ and so we have base change matrix

$P=$ $\begin{pmatrix} -1 & 1 & 1 \\ -1 & -3 & 0 \\-1 & 1 & 0 \end{pmatrix}$

On calculating we get $P^{-1}AP$= $\begin{pmatrix} 3 & 1 & 1 \\ -1 & 5 & 0 \\0 & 0 & 4 \end{pmatrix}$

So we have the zeroes we need on the bottom row.

Now we look at $B=$ $\begin{pmatrix} 3 & 1 \\ -1 & 5\end{pmatrix}$ We obviously need to deal with this section of the $3$x$3$ matrix but I am now confused as to the way the book is going about it-

To continue B has eigenvalue $4$ and eigenvector $\begin{pmatrix} 1 \\ 1 \end{pmatrix}$

$B-4I =$ $\begin{pmatrix} -1 & 1 \\ -1 & 1\end{pmatrix}$ so a basis for the image is $\begin{pmatrix} 1 \\ 1 \end{pmatrix}$ We extend this to a basis of $\mathbb{R^2}$ by adding $\begin{pmatrix} 1 \\ 0 \end{pmatrix}$ Why have we done this for this $2$x$2$ matrix? This section of the $3$x$3$ was the problem but why have we treated this like it's $\mathbb{R^2}$ and also separately from the bigger $3$x$3$?

The book then says "Going back to $\mathbb{R^3}$ what we done is replace $f_1 ,f_2, f_3$ with $f_1+f_2, f_1, f_3$. I can't see how. The section from the submatrix B to here has lost me. But if I can understand this bit the rest of stuff which is continued on from here is nice and simple:

The base change matrix from $f_1 ,f_2, f_3$ to $f_1+f_2, f_1, f_3$ is $Q=$ $\begin{pmatrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\0 & 0 & 1 \end{pmatrix}$ which is clear and $Q^{-1}P^{-1}APQ$ on calculating is

$\begin{pmatrix} 4 & -1 & 0 \\ 0 & 4 & 1 \\0 & 0 & 4 \end{pmatrix}$ which is upper triangular.

Let's see why the procedure work. Let's denote the usual standard basis of $\mathbb{R}^3$ by $\{e_1,e_2,e_3\}$. Then we have \begin{align} (A-4I)e_1&= f_1\\ (A-4I)e_3 &= f_2 \end{align} So, $A(f_1) \in Range(A-4I) = Span\{ f_1, f_2\}$ and similarly $Af_2\in Range(A-4I) = Span\{ f_1, f_2\}$.
Now extend $Span\{ f_1, f_2\}$ to get a basis for $\mathbb{R}^3$ say $\{f_1,f_2,f_3\}$; Because of the Property mentioned above i.e. $Af_1, Af_2 \in Span \{f_1,f_2\}$, we will get, w.r.t this basis matrix of $A$ will be of the following form \begin{align} \begin{pmatrix} b_{1,1} & b_{1,2} & c_1 \\ b_{2,1} & b_{2,2} & c_2\\ 0 & 0 & d \end{pmatrix}=\begin{pmatrix} B & C \\ 0 & d \end{pmatrix} \end{align} In other word we have found a invertible $3 \times 3$ matrix $P$ (where $P$ is the matrix of change of basis in $\mathbb{R}^3$) so that \begin{align} P^{-1}AP &= \begin{pmatrix} B & C \\ 0 & d \end{pmatrix} \end{align}
Now we will do the same procedure for $B$. Now we will get a $2\times 2$ invertible matrix $Q_1$ so that \begin{align} Q_1^{-1}BQ_1 &= \begin{pmatrix} r & s \\ 0 & t \end{pmatrix} \end{align}
Now define a $3\times 3$ invertible matrix $Q$ in following manner \begin{align} Q = \begin{pmatrix} Q_1 & 0\\ 0 & 1 \end{pmatrix} \end{align} (Note that $Q$ become invertible). So now we have \begin{align} Q^{-1}P^{-1}APQ &= \begin{pmatrix} Q_1^{-1} & 0\\ 0 & 1 \end{pmatrix} \begin{pmatrix} B & C \\ 0 & d \end{pmatrix}\begin{pmatrix} Q_1 & 0\\ 0 & 1 \end{pmatrix}\\ &= \begin{pmatrix} Q_1^{-1}BQ_1 & Q_1^{-1}C \\ 0 & d \end{pmatrix}\\ &= \begin{pmatrix} r & s & *\\ 0 & t & *\\ 0 & 0 & d \end{pmatrix} \end{align} Hence you have your required Upper triangular form.
In your case you already wrote $P$. Note that, in this case we have \begin{align} B &= \begin{pmatrix} 3 & -1\\ 1 & 5 \end{pmatrix} \end{align} So repeating the previous procedure for $B$ we will get \begin{align} Q_1 &= \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix} \end{align} so that \begin{align} Q_1^{-1}B Q_1 &= \begin{pmatrix} 4 & -1\\ 0 & 4 \end{pmatrix} \end{align} And hence we get whatever we wanted.