<s>[INST] 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.
 [/INST] 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.
</s>