11.1: Block Triangular Form

We have shown (Theorem 8.2.5) that any \(n \times n\) matrix \(A\) with every eigenvalue real is orthogonally similar to an upper triangular matrix \(U\). The following theorem shows that \(U\) can be chosen in a special way.

Theorem \(\PageIndex{1}\): Block Triangulation Theorem

Let \(A\) be an \(n \times n\) matrix with every eigenvalue real and let

\[c_A(x) = (x - \lambda_1)^{m_1}(x - \lambda_2)^{m_2} \cdots (x - \lambda_k)^{m_k} \nonumber \]

where \(\lambda_{1}, \lambda_{2}, \dots, \lambda_{k}\) are the distinct eigenvalues of \(A\). Then an invertible matrix \(P\) exists such that

\[P^{-1}AP = \left[ \begin{array}{ccccc} U_1 & 0 & 0 & \cdots & 0 \\ 0 & U_2 & 0 & \cdots & 0 \\ 0 & 0 & U_3 & \cdots & 0 \\ \vdots & \vdots & \vdots & & \vdots \\ 0 & 0 & 0 & \cdots & U_k \end{array} \right] \nonumber \]

where, for each \(i\), \(U_{i}\) is an \(m_{i} \times m_{i}\) upper triangular matrix with every entry on the main diagonal equal to \(\lambda_{i}\).

The proof is given at the end of this section. For now, we focus on a method for finding the matrix \(P\). The key concept is as follows.

Definition: Generalized Eigenspaces

If \(A\) is as in Theorem 11.1.1, the generalized eigenspace \(G_{\lambda_i}(A)\) is defined by

\[G_{\lambda_i}(A) = \text{null}[(\lambda_{i}I - A)^{m_i}] \nonumber \]

where \(m_{i}\) is the multiplicity of \(\lambda_{i}\).

Observe that the eigenspace \(E_{\lambda_i}(A) = \text{null}(\lambda_{i}I - A)\) is a subspace of \(G_{\lambda_i}(A)\). We need three technical results.

Lemma \(\PageIndex{1}\)

Using the notation of Theorem 11.1.1, we have \(dim \;[G_{\lambda_i}(A)] = m_{i}\).

Proof

Write \(A_{i} = (\lambda_{i}I - A)^{m_i}\) for convenience and let \(P\) be as in Theorem 11.1.1. The spaces \(G_{\lambda_i}(A) = \text{null}(A_{i})\) and \(\text{null}(P^{-1}A_{i}P)\) are isomorphic via \(\mathbf{x} \leftrightarrow P^{-1}\mathbf{x}\), so we show \(dim \;[\text{null}(P^{-1}A_{i}P)] = m_{i}\). Now \(P^{-1}A_{i}P = (\lambda_{i}I - P^{-1}AP)^{m_i}\). If we use the block form in Theorem 11.1.1, this becomes

\[\begin{aligned} P^{-1}A_{i}P &= \left[ \begin{array}{cccc} \lambda_{i}I - U_1 & 0 & \cdots & 0 \\ 0 & \lambda_{i}I - U_2 & \cdots & 0 \\ \vdots & \vdots & & \vdots \\ 0 & 0 & \cdots & \lambda_{i}I - U_k \end{array} \right]^{m_i} \\ &= \left[ \begin{array}{cccc} (\lambda_{i}I - U_1)^{m_i} & 0 & \cdots & 0 \\ 0 & (\lambda_{i}I - U_2)^{m_i} & \cdots & 0 \\ \vdots & \vdots & & \vdots \\ 0 & 0 & \cdots & (\lambda_{i}I - U_k)^{m_i} \end{array} \right]\end{aligned} \nonumber \]

The matrix \((\lambda_{i}I - U_{j})^{m_i}\) is invertible if \(j \neq i\) and zero if \(j = i\) (because then \(U_{i}\) is an \(m_{i} \times m_{i}\) upper triangular matrix with each entry on the main diagonal equal to \(\lambda_{i}\)). It follows that \(m_{i} = dim \;[\text{null}(P^{-1}A_{i}P)]\), as required.

\(\square\)

Lemma \(\PageIndex{2}\)

If \(P\) is as in Theorem 11.1.1, denote the columns of \(P\) as follows:

\[\mathbf{p}_{11}, \mathbf{p}_{12}, \dots, \mathbf{p}_{1m_1}; \quad \mathbf{p}_{21}, \mathbf{p}_{22}, \dots, \mathbf{p}_{2m_2}; \quad \dots; \quad \mathbf{p}_{k1}, \mathbf{p}_{k2}, \dots, \mathbf{p}_{km_k} \nonumber \]

Then \(\{\mathbf{p}_{i1}, \mathbf{p}_{i2}, \dots, \mathbf{p}_{im_i}\}\) is a basis of \(G_{\lambda_i}(A)\).

Proof

It suffices by Lemma 11.1.1 to show that each \(\mathbf{p}_{ij}\) is in \(G_{\lambda_i}(A)\). Write the matrix in Theorem 11.1.1 as \(P^{-1}AP = \text{diag}(U_{1}, U_{2}, \dots, U_{k})\). Then

\[AP = P \text{diag}(U_1, U_2, \dots, U_k) \nonumber \]

Comparing columns gives, successively:

\[\begin{aligned} {2} A\mathbf{p}_{11} &= \lambda_{1}\mathbf{p}_{11}, & \quad\quad \mbox{so } (\lambda_{1}I - A)\mathbf{p}_{11} &= \mathbf{0} \\ A\mathbf{p}_{12} &= u\mathbf{p}_{11} + \lambda_{1}\mathbf{p}_{12}, & \quad\quad \mbox{so } (\lambda_{1}I - A)^2\mathbf{p}_{12} &= \mathbf{0} \\ A\mathbf{p}_{13} &= w\mathbf{p}_{11} + v\mathbf{p}_{12} + \lambda_{1}\mathbf{p}_{13} & \quad\quad \mbox{so } (\lambda_{1}I - A)^3\mathbf{p}_{13} &= \mathbf{0} \\ & \quad \vdots & \vdots &\end{aligned} \nonumber \]

where \(u\), \(v\), \(w\) are in \(\mathbb{R}\). In general, \((\lambda_{1}I - A)^{j}\mathbf{p}_{1j} = \mathbf{0}\) for \(j = 1, 2, \dots, m_{1}\), so \(\mathbf{p}_{1j}\) is in \(G_{\lambda_i}(A)\). Similarly, \(\mathbf{p}_{ij}\) is in \(G_{\lambda_i}(A)\) for each \(i\) and \(j\).

\(\square\)

Lemma \(\PageIndex{3}\)

If \(B_{i}\) is any basis of \(G_{\lambda_i}(A)\), then \(B = B_{1} \cup B_{2} \cup \cdots \cup B_{k}\) is a basis of \(\mathbb{R}^n\).

Proof

It suffices by Lemma 11.1.1 to show that \(B\) is independent. If a linear combination from \(B\) vanishes, let \(\mathbf{x}_{i}\) be the sum of the terms from \(B_{i}\). Then \(\mathbf{x}_{1} + \cdots + \mathbf{x}_{k} = \mathbf{0}\). But \(\mathbf{x}_{i} = \sum_{j} r_{ij}\mathbf{p}_{ij}\) by Lemma 11.1.2, so \(\sum_{i,j} r_{ij}\mathbf{p}_{ij} = \mathbf{0}\). Hence each \(\mathbf{x}_{i} = \mathbf{0}\), so each coefficient in \(\mathbf{x}_{i}\) is zero.

\(\square\)

Lemma 11.1.2 suggests an algorithm for finding the matrix \(P\) in Theorem 11.1.1. Observe that there is an ascending chain of subspaces leading from \(E_{\lambda_i}(A)\) to \(G_{\lambda_i}(A)\):

\[E_{\lambda_i}(A) = \text{null}[(\lambda_{i}I - A)] \subseteq \text{null}[(\lambda_{i}I - A)^2] \subseteq \cdots \subseteq \text{null}[(\lambda_{i}I - A)^{m_{i}}] = G_{\lambda_i}(A) \nonumber \]

We construct a basis for \(G_{\lambda_i}(A)\) by climbing up this chain.

Theorem: Triangulation Algorithm

Suppose \(A\) has characteristic polynomial

\[c_{A}(x) = (x - \lambda_1)^{m_1}(x - \lambda_2)^{m_2} \cdots (x - \lambda_k)^{m_k} \nonumber \]

1. Choose a basis of \(\text{null}[(\lambda_{1}I - A)]\); enlarge it by adding vectors (possibly none) to a basis of \(\text{null}[(\lambda_{1}I - A)^{2}]\); enlarge that to a basis of \(\text{null}[(\lambda_{1}I - A)^{3}]\), and so on. Continue to obtain an ordered basis \(\{\mathbf{p}_{11}, \mathbf{p}_{12}, \dots, \mathbf{p}_{1m_1}\}\) of \(G_{\lambda_1}(A)\).
2. As in (1) choose a basis \(\{\mathbf{p}_{i1}, \mathbf{p}_{i2}, \dots, \mathbf{p}_{im_i}\}\) of \(G_{\lambda_i}(A)\) for each \(i\).
3. Let \(P = \left[ \begin{array}{cccc}\mathbf{p}_{11} \mathbf{p}_{12} \cdots \mathbf{p}_{1m_1}; & \mathbf{p}_{21} \mathbf{p}_{22} \cdots \mathbf{p}_{2m_2}; & \cdots; & \mathbf{p}_{k1} \mathbf{p}_{k2} \cdots \mathbf{p}_{km_k} \end{array} \right]\) be the matrix with these basis vectors (in order) as columns.

Then \(P^{-1}AP = \text{diag}(U_{1}, U_{2}, \dots, U_{k})\) as in Theorem 11.1.1.

Proof

Lemma 11.1.3 guarantees that \(B = \{\mathbf{p}_{11}, \dots, \mathbf{p}_{km_1}\}\) is a basis of \(\mathbb{R}^n\), and Theorem 9.2.4 shows that \(P^{-1}AP = M_{B}(T_{A})\). Now \(G_{\lambda_i}(A)\) is \(T_{A}\)-invariant for each \(i\) because

\[(\lambda_{i}I - A)^{m_i}\mathbf{x} = \mathbf{0} \quad \mbox{implies} \quad (\lambda_{i}I - A)^{m_i}(A\mathbf{x}) = A(\lambda_{i}I - A)^{m_i}\mathbf{x} = \mathbf{0} \nonumber \]

By Theorem 9.3.7 (and induction), we have

\[P^{-1}AP = M_B(T_A) = \text{diag}(U_1, U_2, \dots, U_k) \nonumber \]

where \(U_{i}\) is the matrix of the restriction of \(T_{A}\) to \(G_{\lambda_i}(A)\), and it remains to show that \(U_{i}\) has the desired upper triangular form. Given \(s\), let \(\mathbf{p}_{ij}\) be a basis vector in \(\text{null}[(\lambda_{i}I - A)^{s+1}]\). Then \((\lambda_{i}I - A)\mathbf{p}_{ij}\) is in \(\text{null}[(\lambda_{i}I - A)^{s}]\), and therefore is a linear combination of the basis vectors \(\mathbf{p}_{it}\) coming before \(\mathbf{p}_{ij}\). Hence

\[T_A(\mathbf{p}_{ij}) = A\mathbf{p}_{ij} = \lambda_{i}\mathbf{p}_{ij} - (\lambda_{i}I - A)\mathbf{p}_{ij} \nonumber \]

shows that the column of \(U_{i}\) corresponding to \(\mathbf{p}_{ij}\) has \(\lambda_{i}\) on the main diagonal and zeros below the main diagonal. This is what we wanted.

\(\square\)

Example \(\PageIndex{1}\)

If \(A = \left[ \begin{array}{rrrr} 2 & 0 & 0 & 1 \\ 0 & 2 & 0 & -1 \\ -1 & 1 & 2 & 0 \\ 0 & 0 & 0 & 2 \end{array} \right]\), find \(P\) such that \(P^{-1}AP\) is block triangular.

Solution

\(c_{A}(x) = \det [xI - A] = (x - 2)^{4}\), so \(\lambda_{1} = 2\) is the only eigenvalue and we are in the case \(k = 1\) of Theorem 11.1.1. Compute:

\[(2I - A) = \left[ \begin{array}{rrrr} 0 & 0 & 0 & -1 \\ 0 & 0 & 0 & 1 \\ 1 & -1 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{array} \right] \quad (2I - A)^2 = \left[ \begin{array}{rrrr} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & -2 \\ 0 & 0 & 0 & 0 \end{array} \right] \quad (2I - A)^3 = 0 \nonumber \]

By gaussian elimination find a basis \(\{\mathbf{p}_{11}, \mathbf{p}_{12}\}\) of \(\text{null}(2I - A)\); then extend in any way to a basis \(\{\mathbf{p}_{11}, \mathbf{p}_{12}, \mathbf{p}_{13}\}\) of \(\text{null}[(2I - A)^{2}]\); and finally get a basis \(\{\mathbf{p}_{11}, \mathbf{p}_{12}, \mathbf{p}_{13}, \mathbf{p}_{14}\}\) of \(\text{null}[(2I - A)^{3}] = \mathbb{R}^4\). One choice is

\[\mathbf{p}_{11} = \left[ \begin{array}{r} 1 \\ 1 \\ 0 \\ 0 \end{array} \right] \quad \mathbf{p}_{12} = \left[ \begin{array}{r} 0 \\ 0 \\ 1 \\ 0 \end{array} \right] \quad \mathbf{p}_{13} = \left[ \begin{array}{r} 0 \\ 1 \\ 0 \\ 0 \end{array} \right] \quad \mathbf{p}_{14} = \left[ \begin{array}{r} 0 \\ 0 \\ 0 \\ 1 \end{array} \right] \quad \nonumber \]

Hence \(P = \left[ \begin{array}{cccc} \mathbf{p}_{11} & \mathbf{p}_{12} & \mathbf{p}_{13} & \mathbf{p}_{14} \end{array} \right] = \left[ \begin{array}{rrrr} 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{array} \right]\) gives \(P^{-1}AP = \left[ \begin{array}{rrrr} 2 & 0 & 0 & 1 \\ 0 & 2 & 1 & 0 \\ 0 & 0 & 2 & -2 \\ 0 & 0 & 0 & 2 \end{array} \right]\)

Example \(\PageIndex{2}\)

If \(A = \left[ \begin{array}{rrrr} 2 & 0 & 1 & 1 \\ 3 & 5 & 4 & 1 \\ -4 & -3 & -3 & -1 \\ 1 & 0 & 1 & 2 \end{array} \right]\), find \(P\) such that \(P^{-1}AP\) is block triangular.

Solution

The eigenvalues are \(\lambda_{1} = 1\) and \(\lambda_{2} = 2\) because

\[\begin{aligned} c_A(x) &= \left| \begin{array}{cccc} x - 2 & 0 & -1 & -1 \\ -3 & x - 5 & -4 & -1 \\ \mathbin{\phantom{-}}4 & 3 & x + 3 & \mathbin{\phantom{-}}1 \\ -1 & 0 & -1 & x - 2 \end{array} \right| = \left| \begin{array}{cccc} x - 1 & 0 & \mathbin{\phantom{-}}0 & -x + 1 \\ -3 & x - 5 & -4 & -1 \\ \mathbin{\phantom{-}}4 & 3 & x + 3 & \mathbin{\phantom{-}}1 \\ -1 & 0 & -1 & x - 2 \end{array} \right| \\ &= \left| \begin{array}{cccc} x - 1 & 0 & \mathbin{\phantom{-}}0 & \mathbin{\phantom{-}}0 \\ -3 & x - 5 & -4 & -4 \\ \mathbin{\phantom{-}}4 & 3 & x + 3 & \mathbin{\phantom{-}}5 \\ -1 & 0 & -1 & x - 3 \end{array} \right| = (x - 1) \left| \begin{array}{ccc} x - 5 & -4 & -4 \\ 3 & x + 3 & \mathbin{\phantom{-}}5 \\ 0 & -1 & x - 3 \end{array} \right| \\ &= (x - 1) \left| \begin{array}{ccc} x - 5 & -4 & \mathbin{\phantom{-}}0 \\ 3 & x + 3 & -x + 2 \\ 0 & -1 & \mathbin{\phantom{-}}x - 2 \end{array} \right| = (x - 1) \left| \begin{array}{ccc} x - 5 & -4 & 0 \\ 3 & x + 2 & 0 \\ 0 & -1 & x - 2 \end{array} \right| \\ &= (x - 1)(x - 2) \left| \begin{array}{cc} x - 5 & -4 \\ 3 & x + 2 \end{array} \right| = (x - 1)^2(x - 2)^2\end{aligned} \nonumber \]

By solving equations, we find \(\text{null}(I - A) = span \;\{\mathbf{p}_{11}\}\) and \(\text{null}(I - A)^{2} = span \;\{\mathbf{p}_{11}, \mathbf{p}_{12}\}\) where

\[\mathbf{p}_{11} = \left[ \begin{array}{r} 1 \\ 1 \\ -2 \\ 1 \end{array} \right] \quad \mathbf{p}_{12} = \left[ \begin{array}{r} 0 \\ 3 \\ -4 \\ 1 \end{array} \right] \nonumber \]

Since \(\lambda_{1} = 1\) has multiplicity \(2\) as a root of \(c_{A}(x)\), \(dim \;G_{\lambda_1}(A) = 2\) by Lemma 11.1.1. Since \(\mathbf{p}_{11}\) and \(\mathbf{p}_{12}\) both lie in \(G_{\lambda_1}(A)\), we have \(G_{\lambda_1}(A) = span \;\{\mathbf{p}_{11}, \mathbf{p}_{12}\}\). Turning to \(\lambda_{2} = 2\), we find that \(\text{null}(2I - A) = span \;\{\mathbf{p}_{21}\}\) and \(\text{null}[(2I - A)^{2}] = span \;\{\mathbf{p}_{21}, \mathbf{p}_{22}\}\) where

\[\mathbf{p}_{21} = \left[ \begin{array}{r} 1 \\ 0 \\ -1 \\ 1 \end{array} \right] \quad \mbox{and} \quad \mathbf{p}_{22} = \left[ \begin{array}{r} 0 \\ -4 \\ 3 \\ 0 \end{array} \right] \nonumber \]

Again, \(dim \;G_{\lambda_2}(A) = 2\) as \(\lambda_{2}\) has multiplicity \(2\), so \(G_{\lambda_2}(A) = span \;\{\mathbf{p}_{21}, \mathbf{p}_{22}\}\). Hence \(P = \left[ \begin{array}{rrrr} 1 & 0 & 1 & 0 \\ 1 & 3 & 0 & -4 \\ -2 & -4 & -1 & 3 \\ 1 & 1 & 1 & 0 \end{array} \right]\) gives \(P^{-1}AP = \left[ \begin{array}{rrrr} 1 & -3 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 2 & 3 \\ 0 & 0 & 0 & 2 \end{array} \right]\).

If \(p(x)\) is a polynomial and \(A\) is an \(n \times n\) matrix, then \(p(A)\) is also an \(n \times n\) matrix if we interpret \(A^{0} = I_{n}\). For example, if \(p(x) = x^{2} - 2x + 3\), then \(p(A) = A^{2} - 2A + 3I\). Theorem 11.1.1 provides another proof of the Cayley-Hamilton theorem (see also Theorem 8.7.10). As before, let \(c_{A}(x)\) denote the characteristic polynomial of \(A\).

Theorem \(\PageIndex{2}\): Cayley-Hamilton Theorem

If \(A\) is a square matrix with every eigenvalue real, then \(c_{A}(A) = 0\).

Proof

As in Theorem 11.1.1, write \(c_A(x) = (x - \lambda_1)^{m_1} \cdots (x - \lambda_k)^{m_k} = \Pi_{i=1}^{k}(x - \lambda_i)^{m_i}\), and write

\[P^{-1}AP = D = \text{diag}(U_{1}, \dots, U_{k}) \nonumber \]

Hence

\[c_A(U_i) = \Pi_{i=1}^{k}(U_i - \lambda_{i}I_{m_i})^{m_i} = 0 \mbox{ for each } i \nonumber \]

because the factor \((U_i - \lambda_{i}I_{m_i})^{m_i} = 0\). In fact \(U_i - \lambda_{i}I_{m_i}\) is \(m_{i} \times m_{i}\) and has zeros on the main diagonal. But then

\[\begin{aligned} P^{-1}c_{A}(A)P = c_{A}(D) &= c_A[\text{diag}(U_1, \dots, U_k)] \\ &= \text{diag}[c_A(U_1), \dots, c_A(U_k)] \\ &= 0\end{aligned} \nonumber \]

It follows that \(c_{A}(A) = 0\).

\(\square\)

Example \(\PageIndex{3}\)

If \(A = \left[ \begin{array}{rr} 1 & 3 \\ -1 & 2 \end{array} \right]\), then \(c_A(x) = \det \left[ \begin{array}{cc} x - 1 & -3 \\ 1 & x - 2 \end{array} \right] = x^2 - 3x + 5\). Then \(c_A(A) = A^2 - 3A + 5I_2 = \left[ \begin{array}{rr} -2 & 9 \\ -3 & 1 \end{array} \right] - \left[ \begin{array}{rr} 3 & 9 \\ -3 & 6 \end{array} \right] + \left[ \begin{array}{rr} 5 & 0 \\ 0 & 5 \end{array} \right] = \left[ \begin{array}{rr} 0 & 0 \\ 0 & 0 \end{array} \right]\).

Theorem 11.1.1 will be refined even further in the next section.

Proof of Theorem 11.1.1

The proof of Theorem 11.1.1 requires the following simple fact about bases, the proof of which we leave to the reader.

Lemma \(\PageIndex{4}\)

If \(\{\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_n\}\) is a basis of a vector space \(V\), so also is \(\{\mathbf{v}_1 + s\mathbf{v}_2, \mathbf{v}_2, \dots, \mathbf{v}_n\}\) for any scalar \(s\).

Proof of Theorem 11.1.1

Let \(A\) be as in Theorem 11.1.1, and let \(T = T_{A} : \mathbb{R}^n \to \mathbb{R}^n\) be the matrix transformation induced by \(A\). For convenience, call a matrix a \(\lambda\)-\(m\)-ut matrix if it is an \(m \times m\) upper triangular matrix and every diagonal entry equals \(\lambda\). Then we must find a basis \(B\) of \(\mathbb{R}^n\) such that \(M_{B}(T) = \text{diag}(U_{1}, U_{2}, \dots, U_{k})\) where \(U_{i}\) is a \(\lambda_{i}\)-\(m_{i}\)-ut matrix for each \(i\). We proceed by induction on \(n\). If \(n = 1\), take \(B = \{\mathbf{v}\}\) where \(\mathbf{v}\) is any eigenvector of \(T\).

If \(n > 1\), let \(\mathbf{v}_{1}\) be a \(\lambda_{1}\)-eigenvector of \(T\), and let \(B_{0} = \{\mathbf{v}_{1}, \mathbf{w}_{1}, \dots, \mathbf{w}_{n-1}\}\) be any basis of \(\mathbb{R}^n\) containing \(\mathbf{v}_{1}\). Then (see Lemma 5.5.2)

\[M_{B_0}(T) = \left[ \begin{array}{cc} \lambda_1 & X \\ 0 & A_1 \end{array} \right] \nonumber \]

in block form where \(A_{1}\) is \((n - 1) \times (n - 1)\). Moreover, \(A\) and \(M_{B0}(T)\) are similar, so

\[c_A(x) = c_{M_{B_0}(T)}(x) = (x - \lambda_1)c_{A_1}(x) \nonumber \]

Hence \(c_{A_1}(x) = (x - \lambda_1)^{m_{1}-1} (x - \lambda_2)^{m_2} \cdots (x - \lambda_k)^{m_k}\) so (by induction) let

\[Q^{-1}A_{1}Q = \text{diag}(Z_1,U_2,\dots,U_k) \nonumber \]

where \(Z_{1}\) is a \(\lambda_{1}\)-\((m_{1}-1)\)-ut matrix and \(U_{i}\) is a \(\lambda_{i}\)-\(m_{i}\)-ut matrix for each \(i > 1\).

If \(P = \left[ \begin{array}{cc} 1 & 0 \\ 0 & Q \end{array} \right]\), then \(P^{-1}MB_0(T) = \left[ \begin{array}{cc} \lambda_1 & XQ \\ 0 & Q^{-1}A_1Q \end{array} \right] = A^\prime\), say. Hence \(A^\prime \sim M_{B_0}(T) \sim A\) so by Theorem 9.2.4(2) there is a basis \(B\) of \(\mathbb{R}^n\) such that \(M_{B_1}(T_A) = A^\prime\), that is \(M_{B_1}(T) = A^\prime\). Hence \(M_{B_1}(T)\) takes the block form

\[\label{eq:thm1proof11_1} M_{B_1}(T) = \left[ \begin{array}{cc} \lambda_1 & XQ \\ 0 & \text{diag}(Z_1, U_2, \dots, U_k) \end{array} \right] = \left[ \begin{array}{cc|ccc} \lambda_1 & X_1 & {Y}\\ 0 & Z_1 & 0 & 0 & 0 \\ \hline & & U_2 & \cdots & 0 \\ {0} & \vdots & & \vdots \\ & & 0 & \cdots & U_k \end{array} \right] \]

If we write \(U_1 = \left[ \begin{array}{cc} \lambda_1 & X_1 \\ 0 & Z_1 \end{array} \right]\), the basis \(B_{1}\) fulfills our needs except that the row matrix \(Y\) may not be zero.

We remedy this defect as follows. Observe that the first vector in the basis \(B_{1}\) is a \(\lambda_{1}\) eigenvector of \(T\), which we continue to denote as \(\mathbf{v}_{1}\). The idea is to add suitable scalar multiples of \(\mathbf{v}_{1}\) to the other vectors in \(B_{1}\). This results in a new basis by Lemma 11.1.4, and the multiples can be chosen so that the new matrix of \(T\) is the same as (\ref{eq:thm1proof11_1}) except that \(Y = 0\). Let \(\{\mathbf{w}_{1}, \dots, \mathbf{w}_{m_{2}}\}\) be the vectors in \(B_{1}\) corresponding to \(\lambda_{2}\) (giving rise to \(U_{2}\) in (\ref{eq:thm1proof11_1})). Write

\[U_2 = \left[ \begin{array}{ccccc} \lambda_2 & u_{12} & u_{13} & \cdots & u_{1_{m_2}} \\ 0 & \lambda_2 & u_{23} & \cdots & u_{2_{m_2}} \\ 0 & 0 & \lambda_2 & \cdots & u_{3_{m_2}} \\ \vdots & \vdots & \vdots & & \vdots \\ 0 & 0 & 0 & \cdots & \lambda_2 \end{array} \right] \quad \mbox{and} \quad Y = \left[ \begin{array}{cccc} y_1 & y_2 & \cdots & y_{m_2} \end{array} \right] \nonumber \]

We first replace \(\mathbf{w}_{1}\) by \(\mathbf{w}_{1}^\prime = \mathbf{w}_{1} + s\mathbf{v}_{1}\) where \(s\) is to be determined. Then (\ref{eq:thm1proof11_1}) gives

\[\begin{aligned} T(\mathbf{w}_{1}^\prime) &= T(\mathbf{w}_{1}) + sT(\mathbf{v}_{1}) \\ &= (y_1\mathbf{v}_1 + \lambda_2\mathbf{w}_{1}) + s\lambda_1\mathbf{v}_1 \\ &= y_1\mathbf{v}_1 + \lambda_2(\mathbf{w}_{1}^\prime - s\mathbf{v}_1) + s\lambda_1\mathbf{v}_1 \\ &= \lambda_2\mathbf{w}_{1}^\prime + [(y_1 - s(\lambda_{2} - \lambda_{1})]\mathbf{v}_1\end{aligned} \nonumber \]

Because \(\lambda_{2} \neq \lambda_{1}\) we can choose \(s\) such that \(T(\mathbf{w}_{1}^\prime) = \lambda_2\mathbf{w}_{1}^\prime\). Similarly, let \(\mathbf{w}_2^\prime = \mathbf{w}_{2} + t\mathbf{v}_{1}\) where \(t\) is to be chosen. Then, as before,

\[\begin{aligned} T(\mathbf{w}_{2}^\prime) &= T(\mathbf{w}_2) + tT(\mathbf{v}_1) \\ &= (y_2\mathbf{v}_1 + u_{12}\mathbf{w}_1 + \lambda_2\mathbf{w}_2) + t\lambda_1\mathbf{v}_1 \\ &= u_{12}\mathbf{w}_{1}^\prime + \lambda_2\mathbf{w}_{2}^\prime + [(y_2 - u_{12}s) - t(\lambda_2 - \lambda_1)]\mathbf{v}_1\end{aligned} \nonumber \]

Again, \(t\) can be chosen so that \(T(\mathbf{w}_{2}^\prime) = u_{12}\mathbf{w}_{1}^\prime + \lambda_2\mathbf{w}_{2}^\prime\). Continue in this way to eliminate \(y_1, \dots, y_{m_2}\). This procedure also works for \(\lambda_{3}, \lambda_{4}, \dots\) and so produces a new basis \(B\) such that \(M_{B}(T)\) is as in (\ref{eq:thm1proof11_1}) but with \(Y = 0\).

\(\square\)