---
title: "upper-triangular matrix"
type: concept
related: [Surjectivity, Upper Triangular Matrix, Map Restriction Operator, Linear Algebra Errors, Invariant Subspace]
source: https://www.jemoka.com/posts/kbhupper_triangular_matrix/
confidence: high
status: active
---

A matrix is upper-triangular if the entries below the diagonal are \(0\):
\begin{equation} \mqty(\lambda_{1} &amp; &amp; * \\ &amp; \ddots &amp; \\ 0 &amp; &amp; \lambda_{n}) \end{equation}
properties of upper-triangular matrix Suppose \(T \in \mathcal{L}(V)\), and \(v_1 &hellip; v_{n}\) is a basis of \(V\). Then:
the matrix of \(T\) w.r.t. \(v_1 &hellip; v_{n}\) is upper-triangular \(Tv_{j} \in span(v_1 \dots v_{j})\) for each \(v_{j}\) \(span(v_{1}, &hellip; 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 &hellip; 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 &hellip; v_{j})\)
\(3 \implies 2\) &ldquo;obviously&rdquo;
All \(v_{j} \in span(v_1, \dots v_{j})\), and yet \(T v_{j} \in span (v_{1}, &hellip; v_{j})\) as it is given. Hence, \(span(v_1, &hellip; v_{j})\) is invariant under \(T\).
\(2 \implies 3\) Let \(v \in span(v_1, &hellip; v_{j})\); meaning: \(v = a_1 v_1 + &hellip; + a_{j} v_{j}\). Now, \(Tv = a_1 T v_{1} + &hellip; + a_{j} T v_{j}\). Recall now we are given \(T v_{j} \in span(v_1, &hellip; v_{j})\) for each \(v_{j}\) (of course if \(T{v_{1}} \in span(v_{1})\) it is also in \(span(v_1, &hellip; v_{j})\) so the statement make sense.) Therefore, a linear combinations of \(T v_{j}\) also is in \(span(v_1 &hellip; 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\).
Proof:
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 &hellip; 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}
Hence:
\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 &hellip; 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} &hellip; \lambda_{n}\) be the diagonal entries of \(T\). Per given, let there be an upper-triangular matrix of \(T\) under the basis \(v_1 &hellip; v_{n}\). The matrix w.r.t. \(T\)&rsquo;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 &hellip; 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\)&rsquo;s matrix under \(v_{j}\) is upper-triangular)
Now:
\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&rsquo;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} &hellip; \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}, &hellip; 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, &hellip; v_{j})\) into \(span(v_1, &hellip; v_{j-1})\).
Now, because \(v_{j}\) are linearly independent (they form a basis after all), \(\dim span(v_1, &hellip; v_{j}) = j\) and \(\dim span(v_1, &hellip;, 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 &amp;&amp;* \\ &amp; \ddots &amp; \\ 0 &amp;&amp;\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\)
