Author: Eiko

Tags: matrix, matrix analysis, eigenvalues, singular values, p-adic

Time: 2024-11-29 17:41:45 - 2024-12-06 22:20:59 (UTC)

Reference: p-adic Differential Equations by Kiran S. Kedlaya

Matrix With Complex Numbers

For complex numbers we use the $L^2$ norm for vectors and the operator norm $|A|=\underset{v\ne 0}{sup}\frac{|Av|}{|v|}$ for matrices.

We always arrange the eigenvalues ${\lambda }_1,\dots ,{\lambda }_n$ of $A$ in absolute value decreasing order.

Singular Values

It is familiar by inner product and orthogonalization that real symmetric matrices have real eigenvalues. Semi-positive definite matrices have non-negative eigenvalues, which also holds for complex matrices.

Definition. The singular values of $A$ are the square roots of the eigenvalues of $A^{\ast }A$.

For a real symmetric matrix these are basically the absolute values of the eigenvalues.

Singular Value Decomposition

There are unitary $U,V\in U(n)$ such that

$$UA{V}^{\ast }=\mathrm{\Sigma }=\mathrm{\Sigma }({\sigma }_1,\dots ,{\sigma }_n)$$

is a diagonal matrix, where ${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_n\ge 0$ are the singular values of $A$.

• Singular value decomposition preserves metric on both sides. So it is a good measurement of the size of the matrix.

• Changing notation ,we can write it as $AV=U\mathrm{\Sigma }$, which basically means you can find orthogonal basis such that $A{v}_i={\sigma }_i{u}_i$.

• For any vector $v$ we have $|Av|\le {\sigma }_1|v|$.

• For any two dimensional subspace $W$ there is a non-zero vector $w$ such that $|Aw|\le {\sigma }_2|w|$. This generalizes to higher dimensions.

• ${\sigma }_d$ is the smallest number such that for every $d$ dimensional subspace you can find a non-zero vector $v$ such that $|Av|\le {\sigma }_d|v|$. i.e.

  $${\sigma }_d(A)=\underset{\dim W=d}{sup}\underset{v\in W-\{0\}}{inf}\frac{|Av|}{|v|}.$$

• Using this formula it is obvious that all singular value does not exceed operator norm, ${\sigma }_i\le |A|$. Actually ${\sigma }_1=|A|$. So you can consider singular values as generalizations of operator norm! Instead of one number, you have a sequence of numbers describing the size of the matrix in different dimensions.

Remarks. Singular values are the invariants of a linear map between two inner product spaces $(V,⟨,{⟩}_V,f,W,⟨,{⟩}_W)$, actually for matrices, here $V,W$ are given basis and equipped with standard inner product. The structures of two inner products on source and target spaces are preserved.

Interaction With Exterior Algebra

For an inner product space $V$ with orthonormal basis $e_1,\dots ,e_n$, the exterior space ${\wedge }^{k}V$ has inner product structure and an orthonormal basis $e_{i_1}\wedge \cdots \wedge e_{i_k}$ for $i_1<\cdots <i_k$.

Since we can map

$$\begin{array}{rl}{\wedge }^{k}A(v_{i_1}\wedge \cdots \wedge v_{i_k})& =A{v}_{i_1}\wedge \cdots \wedge A{v}_{i_k}\\ & ={\sigma }_{i_1}\dots {\sigma }_{i_k}{u}_{i_1}\wedge \cdots \wedge u_{i_k},\end{array}$$

• we can see the singular values of ${\wedge }^{k}A$ are $\{{\sigma }_{i_1}\dots {\sigma }_{i_k}:i_1<\cdots <i_k\}$.

• Similarly we can see the eigenvalues of ${\wedge }^{k}A$ are $\{{\lambda }_{i_1}\dots {\lambda }_{i_k}:i_1<\cdots <i_k\}$.

Singular Values Bounds Minors

• In fact this observation gives another interpretation of singular values in terms of exterior product and orthonormal basis,

  $$({\sigma }_1\cdots {\sigma }_k)(A)={\sigma }_1({\wedge }^{k}A)=\underset{|o|=|o^{\prime }|=1}{sup}|⟨o^{\prime },({\wedge }^{k}A)o⟩|.$$

• In particular this means all minors of $A$ are bounded by the partial products of singular values, if $|I|=|J|=k$ then

  $$|det{A}_I^J|\le {\sigma }_1\dots {\sigma }_k.$$

• From $A{e}_1={\lambda }_1{e}_1$ and $|{\lambda }_1||e_1|=|A{e}_1|\le {\sigma }_1|e_1|$ we see that ${\sigma }_1\ge |{\lambda }_1|$. We have

  $$|{\lambda }_1|\le {\sigma }_1=|A|.$$

• Applying above to ${\wedge }^{k}A$ we obtain Weyl’s inequality

  $${\sigma }_1\dots {\sigma }_k\ge |{\lambda }_1\dots {\lambda }_k|,$$

  which is an equality when $k=0,n$.

• Weyl’s inequality has a converse, if you have $\{{\sigma }_i\}\subset {\mathbb{R}}_{\ge 0}$ and $\{{\lambda }_i\}\subset \mathbb{C}$ such that ${\sigma }_1\dots {\sigma }_k\ge |{\lambda }_1\dots {\lambda }_k|$ for all $k$ then there is a matrix $A$ such that ${\sigma }_i$ are the singular values and ${\lambda }_i$ are the eigenvalues.

Remarks. Unlike eigenvalues, singular values do not behave well under polynomial compositions, since the singular value decomposition essentially assumes the source and target spaces be different spaces. But they do work under inverses, from the singular value decomposition you can see the singular values of $A^{-1}$ are $1/{\sigma }_i$.

Perturbations

• The singular values behave better with additive perturbations,

  $$|{\sigma }_i(A+B)-{\sigma }_i(A)|\le |B|.$$

  This can be easily proved by the curious formula of ${\sigma }_i$ in sup inf, and the two facts that $|x+y|\le |x|+|y|,|x+y|\ge |x|-|y|$.

• The eigenvalues cannot easily be controlled by additive perturbations, but we can say about the characteristic polynomials.

  $$|{\chi }_{A+B}[t^{n-m}]-{\chi }_A[t^{n-m}]|\le (2^m-1)(\genfrac{}{}{0ex}{}{n}{m})|B|\prod _{j<m}max({\sigma }_j,|B|).$$

  This can be seen as the ${\chi }_M[t^{n-i}]=\sum _{I}det{M}_I^I$ term is the sum of all $i$-principal minors, we have

  $$\begin{array}{rl}{\chi }_{A+B}[t^{n-m}]& =\sum _{|I|=m}det(A+B{)}_I^I\\ & =\sum _{|I|=m}det{A}_I^I+\sum _{|I|=m}\sum _{{\gamma }_s\in \{{\alpha }_s,{\beta }_s\},s\in I}det({\gamma }_{i_1}\dots {\gamma }_{i_m}{)}_I^I\\ & ={\chi }_A[t^{n-m}]+O_1((2^m-1)(\genfrac{}{}{0ex}{}{n}{m})\underset{k<m}{sup}{\sigma }_1(A)\dots {\sigma }_k(A)|B{|}^{m-k})\end{array}$$

• For multiplicative perturbation, if $B$ is invertible we have

  $${\sigma }_i(BA)\le |B|{\sigma }_i(A).$$

  This can be seen using the formula

  $${\sigma }_i(BA)=supinf\frac{|BAv|}{|v|}\le |B|supinf\frac{|Av|}{|v|}=|B|{\sigma }_i(A).$$

• A similar formula ${\sigma }_i(BA)\le {\sigma }_i(A)|B|$ also holds, you can see this by applying transpose (also called dual or adjoint) and observe that singular values are invariant under transpose (dual) operation.

Matrix With $p$-adic Numbers

For $p$-adic fields (or actually, any other non-archimedean valued fields) the infinity norm on vectors is more appropriate

$$|v|:=\underset{i}{max}|v_i|.$$

The operator norm is defined as usual using this norm.

• As a corollary we have

  $$\begin{array}{rl}|Av|& =\underset{i}{max}|\sum a_{ij}{v}_j|\\ & \le \underset{i}{max}(\underset{j}{max}|a_{ij}||v_j|)\\ & \le \underset{i,j}{max}|a_{ij}|(\underset{j}{max}|v_j|)\\ & \le \underset{i,j}{max}|a_{ij}||v|.\end{array}$$

  This means $|A|\le \underset{i,j}{max}|a_{ij}|$.

• Note also that $|A|\ge \underset{j}{max}\frac{|A{e}_j|}{|e_j|}=\underset{i,j}{max}|a_{ij}|$, therefore

  $$|A|=max|a_{ij}|.$$

• Matrix in $P\in {\mathrm{GL}}_n({\mathcal{O}}_p)$ preserves the vector norm, $|Pv|=|v|$. This can be seen by

  • $|P|=max|p_{ij}|\le 1$,

  • $|Pv|\le |P||v|\le |v|$,

  • $|v|=|P^{-1}Pv|\le |P^{-1}||Pv|\le |Pv|$.

  • Equality holds also tells us that $|P|=|P^{-1}|=1$.

Hodge Polygon

For a sequence $(s_i{)}_{i=1}^n\in {\mathbb{R}}^n$ its associated polygon is the path joined by $\{(-n+k,s_1+\cdots +s_k):k=0,\dots ,n\}$. The $s_i$ are understood as successive slopes, and if $s_i$ are non-decreasing, the polygon is convex.

Given a matrix $A$, let $s_i$ be a sequence whose partial sum $S_i=s_1+\cdots +s_i$ satisfy

$$S_i=\underset{|I|=|J|=i}{min}v(det{A}_I^J).$$

• $s_i$ are called elementary divisors or invariant factors of $A$.

• The Hodge polygon of $A$ is the associated polygon of this sequence, and the singular values of $A$ are given by ${\sigma }_i=p^{-s_i}$, here $p$ should be the base used in the absolute value $|\cdot |=p^{-v}$.

Singular Values Computes Maximal Minors

• As a corollary of the definition,

  $${\sigma }_1\cdots {\sigma }_k=\underset{|I|=|J|=k}{max}|det{A}_I^J|.$$

• These $s_i$ are are clearly invariant under the action of ${\mathrm{GL}}_n({\mathcal{O}}_p)\times {\mathrm{GL}}_n({\mathcal{O}}_p{)}^{op}$, as a result the singular values and Hodges polygons are also invariant.

• Since we are in a valuation ring, through the same process of putting matrix with PID coefficients into normal form, we have the smith normal form of $A$ as $PAQ=\mathrm{\Sigma }(c_1,\dots ,c_n)$ the diagonal matrix, where $P,Q\in {\mathrm{GL}}_n({\mathcal{O}}_p)$ and $|c_i|={\sigma }_i=p^{-s_i}$. This definition of singular value make sense because the vector norms on source and target spaces are preserved by ${\mathrm{GL}}_n({\mathcal{O}}_p)$.

• The process guarantees that $c_1|\dots |c_n$ which means $s_1\le \cdots \le s_n$, i.e. Hodge polygon is convex.

• Similarly we have the subspace characterization of singular values

  $${\sigma }_d(A)=\underset{\dim W=d}{sup}\underset{v\in W-\{0\}}{inf}\frac{|Av|}{|v|}.$$

Remarks. Here ${\mathrm{GL}}_n$ preserves vector norm, so it is natural choice for action. Unlike the complex case we do not try to preserve the inner product structure but we choose to preserve the vector norm. This is because the $p$-adic norm is not obtained from an inner product. The singular values are the invariants of a linear map between two normed spaces $(V,|\cdot {|}_V,f,W,|\cdot {|}_W)$.

Newton Polygon Associated To Eigenvalues

For a matrix $A$ with eigenvalues ${\lambda }_1,\dots ,{\lambda }_n$ the Newton polygon is the associated polygon of the sequence $v({\lambda }_1)\le \cdots \le v({\lambda }_n)$, so that $|{\lambda }_1|\ge \cdots \ge |{\lambda }_n|$.

• As with eigenvalues, Newton polygon is invariant under conjugation by ${\mathrm{GL}}_n(k)$.

• Weyl’s inequality holds as well

  $${\sigma }_1\cdots {\sigma }_k\ge |{\lambda }_1\cdots {\lambda }_k|,$$

  with equality when $k=0,n$. This means the Newton polygon lies above the Hodge polygon, with the same starting and ending points.

Hodge-Newton Decomposition

If the Hodge and Newton polygons of a matrix ‘breaks into two parts’, i.e. for some $i$ we have

$$|{\lambda }_i|>|{\lambda }_{i+1}|,{\sigma }_1\cdots {\sigma }_i=|{\lambda }_1\dots {\lambda }_i|$$

the matrix has a Hodge-Newton decomposition at $i$, there is an integral matrix $U\in {\mathrm{GL}}_n({\mathcal{O}}_p)$ such that

$$U^{-1}AU=\left(\begin{array}{cc}B& C\\ 0& D\end{array}\right)$$

If moreover ${\sigma }_i>{\sigma }_{i+1}$ then $C$ can be chosen to be zero.

Perturbations Of $p$-adic Matrices

A lot of the perturbation results for complex matrices have a $p$-adic analog.

Non-Archimedean Property For Vectors

• Recall that for numbers we have $|a+b|\le max(|a|,|b|)$, with equality when $|a|\ne |b|$.

  There is a vector non-archimedean property (for the $\mathrm{\infty }$-norm) for vectors $v,w$, since $|v+w|=\underset{i}{max}|v_i+w_i|\le \underset{i}{max}max(|v_i|,|w_i|)=max(|v|,|w|)$, we have

  $$|v+w|\le max(|v|,|w|)$$

• If $|w|<|v|$, there exists at least on $i$ such that $|w_i|<|v_i|$, at this time the equality holds.

  $$|w|<|v|\Rightarrow |v+w|=|v|.$$

Perturbations

• If $|B|<{\sigma }_i$, then ${\sigma }_j(A+B)={\sigma }_j(A)$ for all $j\ne i$.

  This is the direct consequence of the vector non-archimedean property and the sup-inf property of singular values, as for the vector $v$ that attains the sup-inf of ${\sigma }_j(A)$, we have $|Bv|<{\sigma }_i|v|=|Av|$ therefore $|Av+Bv|=|Av|$.

• Let ${\chi }_A$ and ${\chi }_{A+B}$ be the characteristic polynomials. Then

  $$|{\chi }_{A+B}[t^{n-m}]-{\chi }_A[t^{n-m}]|\le |B|\prod _{j<m}max({\sigma }_j,|B|).$$

  Here the coefficients appearing in the complex version of the statement are replaced by $1$, due to the archimedean property of $p$-adic numbers.

• For multiplicative perturbation, the result is the same

  $${\sigma }_i(BA)=supinf\frac{|BAv|}{|v|}\le |B|supinf\frac{|Av|}{|v|}=|B|{\sigma }_i(A).$$