upper-triangular matrix — Jemoka Knowledge Base

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: the matrix of T w.r.t. v_1 … v_{n} is upper-triangular Tv_{j} \in span(v_1 \dots v_{j}) for each v_{j} 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 “obviously” 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. 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 … 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 … 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) 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’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