The Complex Spectral Theorem

We argue by strong induction on $n = \dim V$.

Base case $n = 1$. Any orthonormal basis (a single unit vector) trivially triangularizes $T$, since the single matrix entry is automatically "upper triangular."

Inductive step. Assume the result holds for all complex inner product spaces of dimension less than $n$, and let $\dim V = n \ge 2$. Since $V$ is a nonzero finite-dimensional complex vector space, the characteristic polynomial of $T$ has a root in $\mathbb{C}$ by the Fundamental Theorem of Algebra; hence $T$ has an eigenvalue $\lambda$ and an associated unit eigenvector, call it $e_n$ (we index it last for bookkeeping). Consider the adjoint $T^*$; it too has an eigenvalue, but we do not need this — instead consider $U = \operatorname{span}(e_n)^\perp$, the orthogonal complement of the line spanned by $e_n$. Since $V$ has an inner product, $V = \operatorname{span}(e_n) \oplus U$ with $\dim U = n - 1$. We want to triangularize $T$ restricted appropriately to $U$, but $T$ need not map $U$ into itself. Instead we use $T^*$: let $\lambda$ be as above so $Te_n = \lambda e_n$, i.e. $e_n$ is an eigenvector for $T$. Define $P \in \mathcal{L}(V)$ to be orthogonal projection onto $U$, and set $S = P T|_U \in \mathcal{L}(U)$, the compression of $T$ to $U$ (apply $T$ then project back onto $U$). By the inductive hypothesis applied to the $(n-1)$-dimensional space $U$ and the operator $S$, there is an orthonormal basis $e_1, \dots, e_{n-1}$ of $U$ with respect to which $S$ is upper triangular:

Now $e_1, \dots, e_{n-1}, e_n$ is an orthonormal basis of $V$ (orthonormal within $U$, and $e_n \perp U$ by construction). For $k \le n-1$, write $Te_k = Se_k + (\text{component along } e_n)$, since $T e_k \in V = U \oplus \operatorname{span}(e_n)$ and $P(Te_k) = Se_k$. Thus

This is not quite upper-triangular order (we want $Te_k \in \operatorname{span}(e_1,\ldots,e_k)$ without $e_n$ appearing for $k<n$) — so we correct the indexing: relabel so that $e_n$ (the eigenvector) is placed last, which is exactly what we did, but the display above shows a stray $e_n$ term for $k \le n-1$. To eliminate this, we instead place the eigenvector first. Restart the induction with this fix:

Corrected construction. Let $\lambda$ be an eigenvalue of $T^*$ with unit eigenvector $f_1$, so $T^*f_1 = \overline{\lambda} f_1$ for some $\lambda \in \mathbb C$. Let $U = \operatorname{span}(f_1)^\perp$, $\dim U = n-1$. For $u \in U$,

so $Tu \in U$: $U$ is $T$-invariant. Apply the inductive hypothesis to $T|_U \in \mathcal L(U)$ to get an orthonormal basis $f_2,\dots,f_n$ of $U$ with $T f_k \in \operatorname{span}(f_2,\ldots,f_k)$ for $2\le k\le n$ (indices shifted). Then $f_1, f_2,\dots,f_n$ is an orthonormal basis of $V$, and since $Tf_1 \in V = \operatorname{span}(f_1,\dots,f_n)$ trivially, while $Tf_k \in U = \operatorname{span}(f_2,\dots,f_n) \subseteq \operatorname{span}(f_1,\ldots,f_k)$ for $k \ge 2$, the matrix of $T$ in this basis is upper triangular. $\blacksquare$

Proof of the Complex Spectral Theorem, using Normal Operators and Schur's Triangularization Theorem above. We show $(1) \Rightarrow (2) \Rightarrow (3) \Rightarrow (1)$.

$(1) \Rightarrow (2)$. Suppose $T$ is normal. By Schur's theorem there is an orthonormal basis $e_1, \dots, e_n$ of $V$ with respect to which the matrix $A = (a_{ij})$ of $T$ is upper triangular, so $a_{ij} = 0$ whenever $i > j$. Claim: $A$ is in fact diagonal, i.e. $a_{ij} = 0$ for all $i \ne j$. We prove this by induction on the row index, using the following key fact about normal operators.

Sub-lemma. If $T$ is normal, then $\|Tv\| = \|T^*v\|$ for every $v \in V$. Proof of sub-lemma. For any $v$,

using $T^*T = TT^*$ (normality) in the middle step, and the defining property of the adjoint on both sides. $\square$ Now compute both sides for $v = e_1$. Since the matrix is upper triangular, $Te_1 = a_{11}e_1$ (there is no room below the diagonal in column 1: $a_{i1}=0$ for $i>1$). So

On the other hand, since $T^*$'s matrix relative to the orthonormal basis $e_1,\ldots,e_n$ is the conjugate transpose $A^*$ of $A$ (a standard fact: if $A = (a_{ij})$ with $a_{ij} = \langle Te_j, e_i\rangle$, then $\langle T^*e_j, e_i\rangle = \overline{\langle e_j, Te_i\rangle}=\overline{a_{ji}}$, so the $(i,j)$ entry of $T^*$'s matrix is $\overline{a_{ji}}$, i.e. the matrix is $A^*$), we get

so, since $e_1,\ldots,e_n$ is orthonormal,

By the sub-lemma, $\|Te_1\|^2 = \|T^*e_1\|^2$, i.e.

forcing $a_{12} = a_{13} = \cdots = a_{1n} = 0$. Now proceed inductively: suppose we have shown $a_{ij} = 0$ for all $i < j \le k-1$ contributing to rows $1,\ldots,k-1$ being cleared appropriately (formally: assume all entries above the diagonal in columns $1,\dots,k-1$ vanish, i.e. the block structure through column $k-1$ is already diagonal). Consider $e_k$. Upper-triangularity gives $Te_k = a_{1k}e_1 + \cdots + a_{kk}e_k$; but by the inductive hypothesis on earlier columns, none of the previously-cleared off-diagonal entries interfere, and in fact the same computation as above applies verbatim to $e_k$: since the matrix restricted below row $k$ has zero entries in column $k$ (upper-triangularity: $a_{ik}=0$ for $i>k$), we get $Te_k = \sum_{i \le k} a_{ik} e_i$ so $\|Te_k\|^2 = \sum_{i\le k}|a_{ik}|^2$. And $T^*e_k = \sum_{j} \overline{a_{kj}} e_j$ where the sum is over all $j$ with $a_{kj}$ possibly nonzero, i.e. $j \ge k$ by upper-triangularity of $A$ (row $k$ of $A$ has entries $a_{kj}$ for $j \ge k$), so $\|T^*e_k\|^2 = \sum_{j \ge k} |a_{kj}|^2$. The sub-lemma gives $\|Te_k\| = \|T^*e_k\|$, i.e.

By the induction hypothesis, all $a_{ik}$ with $i<k$ were already shown to be $0$ in the earlier steps applied to columns $1,\ldots,k-1$ (each such off-diagonal entry $a_{ik}$ for $i < k$ was cleared when we processed row/column $i$, by the identical argument forcing all entries strictly right of the diagonal in row $i$ to vanish). Hence the left side is just $|a_{kk}|^2$, forcing $\sum_{j>k}|a_{kj}|^2 = 0$, so $a_{kj} = 0$ for all $j > k$. By induction, all entries strictly above the diagonal vanish; combined with upper-triangularity (entries strictly below the diagonal already vanish), $A$ is diagonal. A diagonal matrix relative to an orthonormal basis means precisely that each $e_i$ is an eigenvector, so $e_1,\ldots,e_n$ is an orthonormal eigenbasis. This proves $(2)$.

$(2) \Rightarrow (3)$. Suppose $e_1,\ldots,e_n$ is an orthonormal eigenbasis for $T$ with $Te_i = \lambda_i e_i$. Fix any orthonormal basis $f_1,\ldots,f_n$ of $V$ (e.g. the standard one used to write matrices). Let $U \in \mathcal L(V)$ be the linear operator defined by $Uf_i = e_i$ for each $i$. Since $U$ sends one orthonormal basis to another, $U$ is unitary (this is a standard characterization: an operator sending some orthonormal basis to an orthonormal basis preserves the inner product on all of $V$ by bilinearity/sesquilinearity, hence is unitary). Let $D$ be the diagonal matrix with entries $\lambda_1,\ldots,\lambda_n$. Then for each $i$,

wait — we must express this relative to the $f$-basis correctly. More directly: the matrix of $T$ relative to the basis $e_1,\ldots,e_n$ is $D$ (diagonal, entries $\lambda_i$), by definition of eigenbasis. The change-of-basis operator from the $f$-basis to the $e$-basis is $U$ (with $Uf_i = e_i$), and $U$ is unitary so $U^{-1} = U^*$. The standard change-of-basis formula for the matrix of $T$ relative to $f_1,\ldots,f_n$ is

which is exactly statement (3).

$(3) \Rightarrow (1)$. Suppose the matrix of $T$ relative to some orthonormal basis is $UDU^*$ with $U$ unitary ($U^*U=UU^*=I$) and $D$ diagonal. Then the matrix of $T^*$ relative to the same basis is $(UDU^*)^* = U D^* U^*$ (using $(ABC)^* = C^*B^*A^*$ and $U^{**}=U$). Since $D$ is diagonal, $D^*$ (its conjugate transpose) is also diagonal, and diagonal matrices commute with each other: $DD^* = D^*D$. Therefore

using $U^*U = I$. Since $D^*D = DD^*$, these two matrices are equal, so $T^*T = TT^*$: $T$ is normal. Having shown $(1)\Rightarrow(2)\Rightarrow(3)\Rightarrow(1)$, all three statements are equivalent.

Final remarks (multiplicities and orthogonality of eigenspaces). If $T$ is normal with orthonormal eigenbasis $e_1,\ldots,e_n$ and matrix $D=\operatorname{diag}(\lambda_1,\ldots,\lambda_n)$, the characteristic polynomial of $T$ equals $\det(D - xI) = \prod_i (\lambda_i - x)$ up to sign, since determinant and characteristic polynomial are basis-independent; hence each eigenvalue's multiplicity as a root matches the number of times it appears among $\lambda_1,\ldots,\lambda_n$, matching its geometric multiplicity in this basis. Finally, suppose $Tv = \alpha v$, $Tw=\beta w$ with $\alpha \ne \beta$. Using normality (specifically $T^*w = \overline{\beta}w$, which follows from the diagonal form: if $w$ is an eigenvector of $T$ for eigenvalue $\beta$ inside a unitary eigenbasis, then relative to that basis $T^*$ is also diagonal with entries $\overline{\lambda_i}$, so $T^*w = \overline\beta w$),

so $(\alpha-\beta)\langle v,w\rangle = 0$, and since $\alpha \ne \beta$, $\langle v,w\rangle = 0$. $\blacksquare$