Suggest edit — upper-triangular matrix

Title

Name

Note

---
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$