\input{preamble.tex} \unittitle{A little $p$-adic numerical analysis} In this unit, we introduce some concepts from numerical analysis, and their nonarchimedean analogues. \section{Singular values} Until further notice, let $A$ be an $n \times n$ matrix over $\CC$. One set of numerical invariants we can attach to $A$ is the list of eigenvalues $\lambda_1, \dots, \lambda_n$, which we sort so that $|\lambda_1| \geq \cdots \geq |\lambda_n|$. A second set, which is more useful for numerical analysis, is the singular values. Let $A^*$ denote the conjugate transpose (or \emph{Hermitian transpose}) of $A$. The matrix $A^* A$ is real symmetric, so has nonnegative real eigenvalues. The square roots of these eigenvalues comprise the \emph{singular values} of $A$; we denote them $\sigma_1, \dots, \sigma_n$ with $\sigma_1 \geq \cdots \geq \sigma_n$. These are not invariant under conjugation, but they are invariant under multiplying $A$ on either side by a unitary matrix. Let $\Diag(\sigma_1, \dots, \sigma_n)$ denote the $n \times n$ diagonal matrix $D$ with $D_{ii}= \sigma_i$ for $i=1,\dots,n$. \begin{theorem}[Singular value decomposition] \label{T:svd} There exist unitary $n \times n$ matrices $U,V$ such that $UAV = \Diag(\sigma_1, \dots, \sigma_n)$. \end{theorem} \begin{proof} This is equivalent to showing that there is an orthonormal basis of $\CC^n$ which remains orthogonal upon applying $A$. To construct it, start with a vector $v \in \CC^n$ maximizing $|Av|/|v|$, then show that for any $w \in \CC^n$ orthogonal to $v$, $Aw$ is also orthogonal to $Av$. For further details, see references in the notes. \end{proof} \begin{cor} The singular values of $A^{-1}$ are $\sigma_n^{-1}, \dots, \sigma_1^{-1}$. \end{cor} From the singular value decomposition, we may infer a convenient interpretation of $\sigma_i$. \begin{cor} \label{C:interpret sigma} The number $\sigma_i$ is the largest value of $\lambda$ for which the following holds: for any $i$-dimensional subspace $V$ of $\CC^n$, there exists $v \in V$ nonzero such that $|Av| \leq \lambda |v|$. \end{cor} \begin{proof} Theorem~\ref{T:svd} provides an orthonormal basis $v_1,\dots,v_n$ of $V$ such that $Av_1,\dots,Av_n$ is again orthogonal, and $|Av_i| = \sigma_i |v_i|$ for $i=1,\dots,n$. Let $W$ be the span of $v_i, \dots, v_n$; then for any $i$-dimensional subspace $V$ of $\CC^n$, $V \cap W$ is nonempty, and any $v \in V \cap W$ satisfies $|Av| \leq \sigma_i |v|$. On the other hand, if we take $V$ to be the span of $v_1,\dots,v_i$, then we have $|Av| \geq \sigma_i |v|$ for all $v \in V$. This proves the claim. \end{proof} The relationship between the singular values and the eigenvalues is controlled by the following inequality of Weyl [Wey49]. For a vast generalization, see Theorem~\ref{T:mult Horn arch}. \begin{theorem}[Weyl] \label{T:Weyl ineq} We have \[ \sigma_1 \cdots \sigma_i \geq |\lambda_1 \cdots \lambda_i| \qquad (i=1,\dots,n), \] with equality for $i=n$. \end{theorem} \begin{proof} The equality for $i=n$ holds because $\det(A^* A) = |\det(A)|^2$. We check the inequality first for $i=1$. Note that if we equip $\CC^n$ with the $L_2$ norm, i.e., \[ |(z_1,\dots,z_n)| = (|z_1|^2 + \cdots + |z_n|^2)^{1/2}, \] then $\sigma_1$ is the operator norm of $A$, that is, \[ \sigma_1 = \sup_{v \in \CC^n - \{0\}} \{ |Av|/|v|\}. \] Since there exists $v \in \CC^n - \{0\}$ with $Av = \lambda_1 v$, we deduce that $\sigma_1 \geq |\lambda_1|$. For the general case, we pass from $\CC^n$ to its $i$-th exterior power $\wedge^i \CC^n$, on which $A$ also acts. The maximum norm of an eigenvalue of this action is $|\lambda_1 \cdots \lambda_i|$, and the operator norm is $\sigma_1 \cdots \sigma_i$. Thus the previous inequality gives what we want. \end{proof} We mention in passing the following converse of Theorem~\ref{T:Weyl ineq}, due to Horn [Hor54, Theorem~4]. \begin{theorem} \label{T:Horn} For $\lambda_1, \dots, \lambda_n \in \CC$ and $\sigma_1, \dots, \sigma_n \in \RR_{\geq 0}$ satisfying \[ \sigma_1 \cdots \sigma_i \geq |\lambda_1 \cdots \lambda_i| \qquad (i=1,\dots,n), \] with equality for $i=n$, there exist an $n \times n$ matrix $A$ over $\CC$ with singular values $\sigma_1, \dots, \sigma_n$ and eigenvalues $\lambda_1, \dots, \lambda_n$. \end{theorem} Equality in Weyl's theorem at an intermediate stage has a structural meaning. \begin{theorem} \label{T:equality} Suppose that for some $i\in \{1,\dots,n-1\}$ we have \begin{gather*} \sigma_i > \sigma_{i+1}, \qquad |\lambda_i| > |\lambda_{i+1}|, \\ \sigma_1 \cdots \sigma_i = |\lambda_1 \cdots \lambda_i|. \end{gather*} Then there exists a unitary matrix $U$ such that $U^{-1} A U$ is block diagonal, with the first block accounting for the first $i$ singular values and eigenvalues, and the second block accounting for the others. \end{theorem} \begin{proof} Let $v_1,\dots,v_n$ be a basis of $\CC^n$ such that $v_1,\dots,v_i$ span the generalized eigenspaces with eigenvalues $\lambda_1, \dots, \lambda_i$. and $v_{i+1},\dots,v_n$ span the generalized eigenspaces with eigenvales $\lambda_{i+1},\dots, \lambda_n$. Apply the singular value decomposition to construct an orthonormal basis $w_1, \dots, w_n$ such that $Aw_1, \dots, Aw_n$ are also orthogonal and $|Aw_i| = \sigma_i |w_i|$. Since $\sigma_i > \sigma_{i+1}$, the only vectors $v \in \wedge^i \CC^n$ for which $|Av|/|v|$ achieves its maximum value $\sigma_1 \cdots \sigma_i$ are the nonzero multiples of $w_1 \wedge \cdots \wedge w_i$. However, this is also true for $v_1 \wedge \cdots \wedge v_i$. We conclude that $w_1, \dots, w_i$ span $V$; this implies that the orthogonal complement of $V$ is spanned by $w_{i+1},\dots,w_n$, and so is also preserved by $A$. This yields the desired result. \end{proof} \begin{theorem} \label{T:normal} The following are equivalent. \begin{enumerate} \item[(a)] There exists a unitary matrix $U$ such that $U^{-1} A U$ is diagonal. \item[(b)] The matrix $A$ is normal, i.e., $A^* A = AA^*$. \item[(c)] The eigenvalues $\lambda_1, \dots, \lambda_n$ and singular values $\sigma_1, \dots, \sigma_n$ of $A$ satisfy $|\lambda_i| = \sigma_i$ for $i=1,\dots,n$. \end{enumerate} \end{theorem} \begin{proof} It is clear that (a) implies both (b) and (c). Given (b), we can perform a joint eigenspace decomposition for $A$ and $A^*$. On any common generalized eigenspace, $A$ has some eigenvalue $\lambda$, $A^*$ has eigenvalue $\overline{\lambda}$, and so $A^* A$ has eigenvalue $|\lambda|^2$. This implies (c). Given (c), Theorem~\ref{T:equality} implies that $A$ can be conjugated by a unitary matrix into a block diagonal matrix in which each block has a single eigenvalue and a single singular value, which coincide. Let $B$ be such a block, with eigenvalue $\lambda$, corresponding to a subspace $V$ of $\CC^n$. If the common singular value is 0, then $B = 0$. Otherwise, $\lambda \neq 0$ and $\lambda^{-1}$ is unitary. Hence given orthogonal eigenvectors $v_1, \dots, v_i \in V$ of $B$, the orthogonal complement in $V$ of their span is preserved by $B$, so is either zero or contains another eigenvector $v_{i+1}$. This shows that $B$ is diagonalizable, and thus is itself a scalar matrix. (One can also argue this last step using compactness of the unitary group.) \end{proof} In general, we can almost conjugate any matrix into a normal matrix. \begin{lemma} \label{L:almost normal} For any $\eta > 1$, we can choose $U \in \GL_n(\CC)$ such that for $i=1,\dots,n$, the $i$-th singular value of $U^{-1} A U$ is at most $\eta |\lambda_i|$. If $A$ is semisimple, we can also take $\eta = 1$. \end{lemma} \begin{proof} Put $A$ in Jordan normal form, then rescale so that for each eigenvalue $\lambda$, the superdiagonal terms have absolute value at most $(|\eta|-1)|\lambda|$, and all other terms are zero. \end{proof} \section{Perturbations (archimedean case)} Another inequality of Weyl [Wey12] shows that the singular values do not change much under a small (additive) perturbation. \begin{theorem}[Weyl] Let $B$ be an $n \times n$ matrix, and let $\sigma'_1, \dots, \sigma'_n$ be the singular values of $A+B$. Then \[ |\sigma'_i-\sigma_i| \leq |B| \qquad (i=1,\dots,n). \] \end{theorem} It is more complicated to describe what happens to the eigenvalues under a small additive perturbation, but it is not so difficult to quantify what happens to the characteristic polynomial, at least in a crude fashion. \begin{theorem} \label{T:perturb1} Let $B$ be an $n \times n$ matrix such that $|B| < \sigma_j$ for some $j \in \{1,\dots,n\}$. Let $P(T) = T^n + \sum_{i=0}^{n-1} P_i T^i$ and $Q(T) = T^n + \sum_{i=0}^{n-1} Q_i T^i$ be the characteristic polynomials of $A$ and $A+B$. Then \[ |P_{n-i} - Q_{n-i}| \leq \left| 2^i \binom{n}{i} \right| \sigma_1 \cdots \sigma_{i-1} |B| \qquad (i=1,\dots,j). \] \end{theorem} The superfluous enclosure of the integer $2^n \binom{n}{i}$ in absolute value signs is quite deliberate; it will be relevant in the nonarchimedean setting. \begin{proof} First consider the case $i=j=n$. By continuity, we may assume that $\det(A) \neq 0$. Write \begin{align*} \det(A + B) &= \det(A) \det(I_n + A^{-1} B) \\ &= \det(A) (1 - R_{n-1} + \cdots \pm R_0), \end{align*} where $T^n + \sum_{i=0}^{n-1} R_i T^i$ is the characteristic polynomial of $A^{-1} B$. From the expansion of $R_{n-i}$ as a sum of $\binom{n}{i}$ minors of size $i$, we have $|R_{n-i}| < \binom{n}{i} |A^{-1} B|^i$. Since $|A^{-1}| = \sigma_n^{-1}$, we have $|A^{-1} B| < 1$; we may thus write \[ |\det(A+B)- \det(A)| \leq |2^n| |\det(A)| |A^{-1} B| = |2^n| \sigma_1 \cdots \sigma_{n-1} |B|. \] For the general case, write the coefficient of $T^{n-i}$ in the characteristic polynomial of a matrix as the sum of $\binom{n}{i}$ minors of size $i$, then apply the previous case to each of these. \end{proof} We also need to consider multiplicative perturbations. \begin{prop} \label{P:mult perturb} Let $B \in \GL_n(\CC)$ satisfy $|B| \leq \eta$. Let $\sigma'_1,\dots, \sigma'_n$ be the singular values of $AB$. Then \[ \sigma'_i \leq \eta \sigma_i \qquad (i=1,\dots,n). \] (The analogous result holds with $BA$ replaced by $AB$, since transposal does not change singular values.) \end{prop} \begin{proof} We use the interpretation of singular values given by Corollary~\ref{C:interpret sigma}. Choose an $i$-dimensional subspace $V$ of $\CC^n$ such that $|BAv| \geq \sigma'_i |v|$ for all $v \in V$. Then choose $v \in V$ nonzero such that $|Av| \leq \sigma_i |v|$. We have \[ \sigma'_i|v| \leq |BAv| \leq |B| |Av| \leq \sigma_i |B| |v|, \] proving the claim. \end{proof} \begin{prop} \label{P:power limit} Let $\sigma_{k,1},\dots,\sigma_{k,n}$ be the singular values of $A^k$. Then \[ \lim_{k \to \infty} \sigma_{k,i}^{1/k} = |\lambda_i| \qquad (i=1,\dots,n). \] \end{prop} \begin{proof} Pick $\eta>1$, and choose $U$ as in Lemma~\ref{L:almost normal}; that is, $U$ is upper-triangular, and each block of eigenvalue $\lambda$ has some scalar $c$ of norm at most $(|\eta|-1) |\lambda|$. Let $U$ be the matrix effecting the resulting conjugation. In a block with eigenvalue $\lambda$, the singular values of the $k$-th power are bounded below by $|\lambda|^k$ and above by $\eta^k |\lambda|^k$. Consequently, we may apply Proposition~\ref{P:mult perturb} to deduce that \[ |\lambda_i|^k |U| |U^{-1}| \leq \sigma_{k,i} \leq \eta^k |\lambda_i|^k |U| |U^{-1}|. \] Taking $k$-th roots and then taking $k \to \infty$, we deduce \[ |\lambda_i| \leq \liminf_{k \to \infty} \sigma_{k,i}^{1/k}, \qquad \limsup_{k \to \infty} \sigma_{k,i}^{1/k} \leq \eta |\lambda_i|. \] Since $\eta > 1$ was arbitrary, we deduce the desired result. \end{proof} \section{Hodge and Newton polygons} We now pass to nonarchimedean analogues. For the rest of this unit, let $F$ be a nonarchimedean field, and let $A$ be an $n \times n$ matrix over $F$. The \emph{Hodge polygon} of $A$ is the polygon starting from $(-n, 0)$ whose slopes $s_1,\dots,s_n$ have the property that for $i=1,\dots,n$, $s_1 + \cdots + s_i$ is the minimum valuation of an $i \times i$ minor of $A$. These slopes may be more familiar as the \emph{elementary divisors} of $A$; see the notes for an explanation of the term ``Hodge polygon''. They are also sometimes called the \emph{invariant factors} of $A$. We will refer to $\sigma_1, \dots, \sigma_n = e^{-s_1}, \dots, e^{-s_n}$ as the \emph{singular values} of $A$; these are invariant under multiplication on either side by a matrix in $\GL_n(\gotho_F)$. One has the relation \[ \sigma_1 = |A|, \] but this time taking the operator norm defined by the supremum norm on $F^n$. We also have an analogue of the singular value decomposition, but only when $F$ is spherically complete. \begin{theorem}[Smith normal form] \label{T:Smith normal form} There exist $U,V \in \GL_n(\gotho_F)$ such that $U A V$ is a diagonal matrix whose entries have norms $\sigma_1, \dots, \sigma_n$. \end{theorem} \begin{proof} Exercise. \end{proof} \begin{cor} The slopes $s_1, \dots, s_n$ of the Hodge polygon satisfy $s_1 \leq \cdots \leq s_n$. \end{cor} \begin{proof} We may replace $F$ by its spherical completion, and then the $i$-th slope $s_i$ is evidently the $i$-th smallest valuation of a diagonal entry of the Smith normal form. \end{proof} \begin{cor} The number $\sigma_i$ is the largest value of $\lambda$ for which the following holds: for any $i$-dimensional subspace $V$ of $F^n$, there exists $v \in V$ nonzero such that $|Av| \leq \lambda |v|$. \end{cor} The \emph{Newton polygon} of $A$ is simply the Newton polygon of its characteristic polynomial. That is, for $\lambda_1, \dots, \lambda_n$ the eigenvalues of $A$ in some algebraic extension of $F$, sorted with $|\lambda_1| \geq \cdots \geq |\lambda_n|$, the Newton polygon has slopes $-\log |\lambda|_1, \dots, -\log |\lambda_n|$ in that order. Since the characteristic polynomial is invariant under conjugation by an element of $\GL_n(F)$, so is the Newton polygon. The archimedean analogue of Weyl's inequality is the following. \begin{theorem}[Newton above Hodge] \label{T:Newton above Hodge} We have \[ \sigma_1 \cdots \sigma_i \geq |\lambda_1 \cdots \lambda_i| \qquad (i=1,\dots,n), \] with equality for $i=n$. In other words, the Hodge and Newton polygons have the same endpoints, and the Newton polygon is everywhere on or above the Hodge polygon. \end{theorem} \begin{proof} Again, the case $i=1$ is clear because $\sigma_1$ is the operator norm of $A$, and the general case follows by considering exterior powers. \end{proof} Again, equality has a structural meaning, but the proof requires a bit more work than in the archimedean case, since we no longer have access to orthogonality. \begin{theorem}[Hodge-Newton decomposition] \label{T:Hodge-Newton decomp} Suppose that for some $i\in \{1,\dots,n-1\}$ we have \begin{gather*} \sigma_i > \sigma_{i+1}, \qquad |\lambda_i| > |\lambda_{i+1}|, \\ \sigma_1 \cdots \sigma_i = |\lambda_1 \cdots \lambda_i|. \end{gather*} (That is, the Hodge and Newton polygons share a vertex with $x$-coordinate $-n+i$.) Then there exists $U \in \GL_n(\gotho_F)$ such that $U^{-1} A U$ is block diagonal, with the first block accounting for the first $i$ singular values and eigenvalues, and the second block accounting for the others. \end{theorem} \begin{proof} Let $v_1,\dots,v_n$ be a basis of $F^n$ such that $v_1,\dots,v_i$ span the generalized eigenspaces with eigenvalues $\lambda_1, \dots, \lambda_i$. and $v_{i+1},\dots,v_n$ span the generalized eigenspaces with eigenvales $\lambda_{i+1},\dots, \lambda_n$. Apply the Smith normal form to construct a basis $w_1, \dots, w_n$ of $\gotho_K^n$ such that $|Aw_i| = \sigma_i |w_i|$. Since $\sigma_i > \sigma_{i+1}$, the only vectors $v \in \wedge^i \CC^n$ for which $|Av|/|v|$ achieves its maximum value $\sigma_1 \cdots \sigma_i$ are the nonzero multiples of $w_1 \wedge \cdots \wedge w_i$. However, this is also true for $v_1 \wedge \cdots \wedge v_i$. We conclude that $w_1, \dots, w_i$ span $V$; this implies that we can conjugate $A$ by a matrix in $\GL_n(\gotho_F)$ into block diagonal form \[ \begin{pmatrix} B & C \\ 0 & D \end{pmatrix}, \] where $B$ accounts for the first $i$ Hodge and Newton slopes of $A$. Each $i \times i$ minor of the matrix $(B C)$ has valuation at least the sum of the first $i$ Hodge slopes of $A$, which is the valuation of $\det(B)$. By Cramer's rule, each column of $C$ is a $\gotho_F$-linear combination of the columns of $B$, i.e., $B^{-1}C$ has entries in $\gotho_F$. Moreover, the first Hodge slope of $D$ is greater than the last Hodge slope of $B$, so $|B^{-1} C D| < |C|$. Thus conjugating by the matrix \[ \begin{pmatrix} I_i & -B^{-1} C\\ 0 & 1 \end{pmatrix} \] gives a new matrix \[ \begin{pmatrix} B & C_1 \\ 0 & D \end{pmatrix} \] with $|C_1| < C$. Repeating, we converge to a change of basis which converts $A$ into the block diagonal matrix \[ \begin{pmatrix} B & 0 \\ 0 & D \end{pmatrix} \] which has the desired form. \end{proof} Note that the slopes of the Hodge polygon are forced to be in the (additive) value group of $F$, whereas the slopes of the Newton polygon need only lie in the divisible closure of the value group. Consequently, it is possible for a matrix to have no conjugates over $\GL_n(F)$ for which the Hodge and Newton polygons coincide. However, the following is true; see also Proposition~\ref{P:move slopes} below. \begin{lemma} \label{L:almost normal2} \begin{enumerate} Suppose that one of the following holds. \item[(a)] The value group of $|F^*|$ is dense in $\RR_{>0}$, and $\eta > 1$. \item[(b)] We have $\sigma_i \in |F^*|$ for $i=1,\dots,n$ (so in particular $\sigma_i > 0$), and $\eta \geq 1$. \end{enumerate} Then there exists $U \in \GL_n(F)$ such that the $i$-th singular value of $U^{-1} A U$ is at most $\eta |\lambda_i|$ (with equality in case (b)). \end{lemma} \begin{proof} Case (b) is directly analogous of Lemma~\ref{L:almost normal}. We will prove a stronger form of (a) in a later unit. \end{proof} \section{Perturbations (nonarchimedean case)} Again, we can ask about the effect of perturbations. The analogue of Weyl's second inequality is more or less trivial. \begin{prop} \label{P:change sing values} If $B$ is a matrix with $|B| < \sigma_i$, then the first $i$ singular values of $A+B$ are $\sigma_1, \dots, \sigma_i$. \end{prop} \begin{proof} Exercise. \end{proof} We next consider the effect on the characteristic polynomial. \begin{theorem} \label{T:perturb} Let $B$ be an $n \times n$ matrix such that $|B| < \sigma_j$ for some $j \in \{1,\dots,n\}$. Let $P(T) = T^n + \sum_{i=0}^{n-1} P_i T^i$ and $Q(T) = T^n + \sum_{i=0}^{n-1} Q_i T^i$ be the characteristic polynomials of $A$ and $A+B$. Then \[ |P_{n-i} - Q_{n-i}| \leq \sigma_1 \cdots \sigma_{i-1} |B| \qquad (i=1,\dots,j). \] \end{theorem} \begin{proof} The proof is as for Theorem~\ref{T:perturb1}, except now the factor $|2^n \binom{n}{i}^2|$ is dominated by 1. \end{proof} \begin{question} Is Theorem~\ref{T:perturb} best possible? \end{question} We may also consider multiplicative perturbations. \begin{prop} \label{P:mult perturb2} Let $B \in \GL_n(F)$ satisfy $|B| \leq \eta$. Let $\sigma'_1,\dots, \sigma'_n$ be the singular values of $AB$. Then \[ \sigma'_i \leq \eta \sigma_i \qquad (i=1,\dots,n). \] \end{prop} \begin{proof} As for Proposition~\ref{P:mult perturb}, but using the Smith normal form instead of the singular value decomposition. \end{proof} \begin{cor} \label{C:keep slopes together} Suppose that the Newton and Hodge slopes of $A$ coincide, and that $U \in \GL_n(F)$ satisfies $|U|\cdot |U^{-1}| \leq \eta$. Then each Newton slope of $U^{-1} A U$ is at most $\log \eta$ more than the corresponding Hodge slope. \end{cor} Here is a weak converse to Corollary~\ref{C:keep slopes together}. (We leave the archimedean analogue to the reader's imagination.) \begin{prop} \label{P:move slopes} Suppose that the Newton slopes of $A$ are nonnegative and that $\sigma_1 \geq 1$. Then there exists $U \in \GL_n(F)$ such that \[ |U^{-1}AU| \leq 1, \quad |U^{-1}| \leq 1, \quad |U| \leq \sigma_1^{n-1}. \] \end{prop} \begin{proof} Let $e_1,\dots,e_n$ denote the standard basis vectors. Let $M$ be the smallest $\gotho_F$-submodule of $F^n$ containing $e_1, \dots, e_n$ and stable under $A$. For each $i$, if $j = j(i)$ is the least integer such that $e_i, Ae_i, \dots, A^je_i$ are linearly dependent, then we have $A^j e_i = \sum_{h=0}^{j-1} c_h A^he_i$ for some $c_h \in F$, and the nonnegativity of the Newton slopes forces $|c_h| \leq 1$. Hence $M$ is finitely generated, and thus free, over $\gotho_F$. Let $v_1,\dots,v_n$ be a basis of $M$, and let $U$ be the change-of-basis matrix $v_j = \sum_i U_{ij} e_i$; then $|U^{-1}AU| \leq 1$ because $M$ is stable under $A$, and $|U^{-1}| \leq 1$ because $M$ contains $e_1,\dots,e_n$. The desired bound on $U$ will follow from the fact that for any $x = c_1 e_1 + \cdots + c_n e_n \in M$, we have \begin{equation} \label{eq:bound} \max_i\{|c_i|\} \leq \sigma_1^{n-1}. \end{equation} It suffices to check \eqref{eq:bound} for $x = A^h e_i$ for $i=1,\dots,n$ and $h = 0,\dots,j(i)-1$, as these generate $M$ over $\gotho_F$. But it is evident that $|A^h e_1| \leq \sigma_1^h |e_1| = \sigma_1^h$, so we are done. \end{proof} In one sense, examples like \[ A = \begin{pmatrix} 1 & c & 0 \\ 0 & 1 & c \\ 0 & 0 & 1 \end{pmatrix} \] with $|c| > 1$ show that this bound is sharp. However, one can get a slight improvement in special cases by accounting for the other singular values; see exercises. By imitating the proof of Proposition~\ref{P:power limit}, we obtain the following. \begin{prop} \label{P:power limit2} Let $\sigma_{k,1},\dots,\sigma_{k,n}$ be the singular values of $A^k$. Then \[ \lim_{k \to \infty} \sigma_{k,i}^{1/k} = |\lambda_i| \qquad (i=1,\dots,n). \] \end{prop} \section{Horn's inequalities} Although they will not be needed in this course, it is quite natural to mention here some stronger versions of the perturbation inequalities in the archimedean and nonarchimedean cases, introduced by Horn [Hor62] in the archimedean case. See the beautiful survey article of Fulton [Ful00] for more information. To introduce the stronger inequalities, we must set up some notation. Put \begin{gather*} U_r^n = \{(I,J,K): I,J,K \subseteq \{1,\dots,n\}, \#I = \#J = \#K = r, \\ \sum_{i \in I} i + \sum_{j \in J} j = \sum_{k \in K} k + r(r+1)/2\}. \end{gather*} For $(I,J,K) \in U_r^n$, write $I = \{i_1 < \cdots < i_r\}$ and similarly for $J,K$. For $r=1$, put $T_1^n= U_1^n$. For $r > 1$, put \begin{gather*} T_r^n = \{(I,J,K) \in U_r^n: \mbox{for all $p