Houjun Liu

upper-triangular matrix

A matrix is upper-triangular if the entries below the diagonal are \(0\):

\begin{equation} \mqty(\lambda_{1} & & * \\ & \ddots & \\ 0 & & \lambda_{n}) \end{equation}

properties of upper-triangular matrix

Suppose \(T \in \mathcal{L}(V)\), and \(v_1 … v_{n}\) is a basis of \(V\). Then:

  1. the matrix of \(T\) w.r.t. \(v_1 … v_{n}\) is upper-triangular
  2. \(Tv_{j} \in span(v_1 \dots v_{j})\) for each \(v_{j}\)
  3. \(span(v_{1}, … v_{j})\) is invariant under \(T\) for each \(v_{j}\)

\(1 \implies 2\)

Recall that our matrix \(A=\mathcal{M}(T)\) is upper-triangular. So, for any \(v_{j}\) sent through \(A\), it will be multiplied to the $j$-th column vector of the matrix. Now, that $j$-th column has \(0\) for rows \(j+1 … n\), meaning that only through a linear combination of the first \(j\) vectors we can construct \(T v_{j}\). Hence, \(Tv_{j} \in span(v_1 … v_{j})\)

\(3 \implies 2\)


All \(v_{j} \in span(v_1, \dots v_{j})\), and yet \(T v_{j} \in span (v_{1}, … v_{j})\) as it is given. Hence, \(span(v_1, … v_{j})\) is invariant under \(T\).

\(2 \implies 3\)

Let \(v \in span(v_1, … v_{j})\); meaning: \(v = a_1 v_1 + … + a_{j} v_{j}\). Now, \(Tv = a_1 T v_{1} + … + a_{j} T v_{j}\). Recall now we are given \(T v_{j} \in span(v_1, … v_{j})\) for each \(v_{j}\) (of course if \(T{v_{1}} \in span(v_{1})\) it is also in \(span(v_1, … v_{j})\) so the statement make sense.) Therefore, a linear combinations of \(T v_{j}\) also is in \(span(v_1 … v_{j})\). Making the latter invariant under \(T\). \(\blacksquare\)

every complex operator has an upper-triangular matrix

Suppose \(V\) is a finite-dimensional complex vector space, with an operator \(T \in \mathcal{L}(V)\). Then, \(T\) has an upper-triangular matrix w.r.t. some basis of \(V\).


We will use induction.

Inductive hypothesis: given dimension of \(V\), \(T \in \mathcal{L}(V)\) has an upper-triangular matrix for a basis of \(V\).

Base case: \(\dim V=1\)

If \(\dim V = 1\), any matrix of \(T\) is technically upper-triangular because its just one number \(\mqty(a)\).

Step: \(\dim V = n\), and \(T \in \mathcal{L}(V)\)

Because operators on complex vector spaces have an eigenvalue, let \(v_1\) be an eigenvector corresponding to an eigenvalue of \(T\). Now, create an invariant subspace \(U = span(v_1)\). (it is invariant because \(v_1\) is an eigenvalue). Now, evidently \(\dim U =1\).

Now, \(\dim V / U = n-1\), the previous step from induction tells us that there exists a upper-triangular matrix for \(T/U \in \mathcal{L}(V / U)\). Specifically, because of the properties of upper-triangular matrix, it tells us that there is a basis \(v_{2} + U … v_{n} + U\) such that its span is invariant under \(T / U\). Meaning:

\begin{equation} (T / U) (v_{j} + U ) \in span( v_{2} + U \dots v_{j} + U) \end{equation}

Writing it out:

\begin{equation} T v_{j} + U = (a_{2} v_{2} + \dots + a_{j} v_{j}) + U \end{equation}

Specifically, this means, there exists at least one pair \(u_1, u_2\) for which:

\begin{equation} T v_{j} + u_1 = (a_{2} v_{2} + \dots + a_{j} v_{j}) + u_2 \end{equation}

And so:

\begin{equation} T v_{j} = (a_{2} v_{2} + \dots + a_{j} v_{j}) + (u_2 - u_1) \end{equation}

And since \(\{v_1\}\) is a basis of \(U\), and \(u_2 - u_1 \in U\), we can say:

\begin{equation} T v_{j} = (a_{2} v_{2} + \dots + a_{j} v_{j}) + a_1 v_1 \end{equation}


\begin{equation} T v_{j} \in span(v_1, \dots v_{j}) \end{equation}

It has been shown in the past (see Linear Algebra Errors) that if a list form a basis of \(V /U\) and another form a basis of \(U\) then the two lists combined form a basis of the whole thing \(V\). So \(v_1 … v_{j}\) is a basis of \(V\).

Now, by the properties of upper-triangular matrix again, we have that there exists an upper-triangular matrix of \(T\) for \(\dim V = n\). \(\blacksquare\)

operator is only invertible if diagonal of its upper-triangular matrix is nonzero

Suppose \(T \in \mathcal{L}(V)\) has an upper-triangular matrix w.r.t. a basis of \(V\). Then, \(T\) is invertable IFF all the entries on the diagonal of the upper-triangular matrix is nonzero.

assume nonzero diagonal

Let \(\lambda_{1} … \lambda_{n}\) be the diagonal entries of \(T\). Per given, let there be an upper-triangular matrix of \(T\) under the basis \(v_1 … v_{n}\). The matrix w.r.t. \(T\)’s matrix being upper-triangular under the list of \(v_{j}\) means that:

\begin{equation} T v_1 = \lambda_{1} v_1 \end{equation}

(because \(T v_{j} \in span(v_1 … v_{j})\), and let \(j=1\)). And so:

\begin{equation} T \frac{v_1}{\lambda_{1}} = v_{1} \end{equation}

(legal as \(\lambda_{j} \neq 0\) per given).

Thus, \(v_1 \in range(T)\).

In a similar fashion, let:

\begin{equation} T v_{2} = a v_{1} + \lambda_{2} v_{2} \end{equation}

(\(a\) being the element just to the right of the \(\lambda_{1}\) diagonal; recall again that \(T\)’s matrix under \(v_{j}\) is upper-triangular)


\begin{equation} T \frac{v_2}{\lambda 2} = \frac{a}{\lambda_{2}} v_{1} + v_{2} \end{equation}

The left side is in range \(T\) by definition; the right side’s \(\frac{a}{\lambda 2} v_{1} \in range\ T\) and hence so is its scaled versions. Thus, \(v_2 \in range\ T\).

Continuing in this fashion, we have all \(v_{j} \in range\ T\). So \(T\) is surjective as it can hit all basis of \(V\). Now, injectivity is surjectivity in finite-dimensional operators, so \(T\) is invertable, as desired.

assume invertible

We will prove this by induction. Let \(\lambda_{1} … \lambda_{n}\) be the diagonal entries of \(T\).

Inductive hypothesis: \(\lambda_{j} \neq 0\)

Base case: \(\lambda_{1} \neq 0\) because if not, \(T v_{1} = 0\) and \(v_{1} \neq 0\) as it is part of a basis so that would make \(T\) not injective and hence not invertable. Hence, by contradiction, \(\lambda_{1} = 0\).

Step: \(\lambda_{j}\)

Suppose for the sake of contradiction \(\lambda_{j} = 0\). This means that the basis \(v_{j}\) is mapped to somewhere in \(span(v_{1}, … v_{j-1})\) as only the top \(j-1\) slots are non-zero for the $j$-th column. And so, \(T\), under the assumption, would map \(span(v_1, … v_{j})\) into \(span(v_1, … v_{j-1})\).

Now, because \(v_{j}\) are linearly independent (they form a basis after all), \(\dim span(v_1, … v_{j}) = j\) and \(\dim span(v_1, …, v_{j-1}) = j-1\). Now, as \(T\) restricted on \(span(v_1, ..v_{j})\) maps to a smaller subspace, it is not injective. So, \(T\) as a whole is not injective, so it is not invertable. Reaching contradiction, \(\blacksquare\).

eigenvalues of a map are the entries of the diagonal of its upper-triangular matrix

The matrix of \(T-\lambda I\) for an upper-triangular form of \(T\) would look like:

\begin{equation} \mqty(\lambda_{1} - \lambda &&* \\ & \ddots & \\ 0 &&\lambda_{n} - \lambda) \end{equation}

where \(\lambda_{j}\) are the diagonals of the upper-triangular form of \(T\), and \(\lambda\) an eigenvalue of \(T\).

Recall that operator is only invertible if diagonal of its upper-triangular matrix is nonzero; so if \(\lambda\) equals any of the \(\lambda_{j}\), it will make the matrix above for \(T - \lambda I\) not invertable as one of its diagonal will be \(0\). Recall the properties of eigenvalues, specifically that \(\lambda\) is an eigenvalue IFF \((T-\lambda I)\) is not invertable. Hence, each \(\lambda_{j}\) is an eigenvalue of \(T\). \(\blacksquare\)