Matrix vector spaces

Vector space of matrices over field F

$M_{m,n}(F),M_{n,n}(F)\equiv M_n(F)$. $M_{m,n}(C)=C^{mn}\equiv C^{m\times n}$.

Matrix inner products

Trace inner product

$⟨A,B⟩=tr(B^{\ast }A)$ : same as taking vectorizing B and $A$ and using vector $⟨.,.⟩$; also see the elementwise multiplication before addition view. Aka standard inner product.

For symmetric matrices: $⟨A,B⟩=\sum _i\sum _j{X}_{ii}{Y}_{ij}$

Matrix norms

Obeys all properties of vector norms,\ plus sub-multiplicativity: $\parallel AB\parallel \le \parallel A\parallel \parallel B\parallel$. Perhaps $\parallel A\parallel =\parallel A^{\ast }\parallel$ too. Generalized matrix norms need not be submultiplicative.

Unitary invariance

If $\parallel .\parallel$ unitary invariant, by SVD, $\parallel A\parallel =\parallel \mathrm{\Sigma }\parallel$.

Symmetric gauge fn g

$g:C^q\to R^{+}$ is a vector norm on $C^q$ which is also an absolute norm, and is permutation invariant: g(Px) = g(x): a fn on a set rather than a seq.

Every unitarily invariant matrix norm $\equiv$ symmetric gauge fn on $\sigma$. Pf: Given $\parallel \parallel :g(x)=\parallel X\parallel :X=diag(x)$ is symm gauge: permutation invariance from unitary invariance of $\parallel \parallel$. $\parallel X\parallel =g(\sigma )$ is unitary invariant matrix norm: unitary invariance from invariance of $\mathrm{\Sigma }$; as g is vector norm, get +ve definiteness, non negativity, homogenousness. $\mathrm{△}$ ineq: g is absolute, so monotone; $\sigma (A+B)$ weakly majorized by $\sigma (A)+\sigma (B)$, so $\sigma (A+B)\le S[\sigma (A)+\sigma (B)]$ for doubly stochastic S; so $g(\sigma (A+B))\le g(S(\sigma (A)+\sigma (B)))\le \sum {\alpha }_i(g(P_i\sigma (A))+g(P_i\sigma (B)))\le g(\sigma (A))+g(\sigma (B))=\parallel A\parallel +\parallel B\parallel$, by Birkhoff.

Max norm

$max|a_{i,j}|$.

Matrix p norms Induced by vector norms

$\parallel A\parallel =\underset{x}{sup}\frac{\parallel Ax\parallel }{\parallel x\parallel }$. Obeys triangle ineq! So, get (p, q) norm, p norm.

\(\norm{A}{p} = \norm{U\SW V^{*}}{p} = \norm{\SW}_{p}\).

\(\norm{A}{\infty}\) is max row sum: use suitable $x=|1{|}^n$; thence get \(\norm{Ax}{\infty}\).

${\parallel A\parallel }_1$ is max col sum.

Unitary invariance: 2 norm only

Change of orth basis. \(\norm{QA}{2}=\norm{A}{2}\) as \(\norm{Qx}{2}=\norm{x}{2}\).

But, \(\norm{QA}{p} \neq \norm{A}{p}\) as \(\norm{Qx}{p} \neq \norm{x}{p}\). By SVD, \(\norm{A}{2} = \norm{A^{*}}{2}\).

Comaprison of norms

\(\norm{A}{\infty} \leq \sqrt{n}\norm{A}{2}\): Take x with \(\norm{x}{2} = 1\), for which \(\norm{Ax}{2} = \norm{A}{2}\); then \(n\norm{Ax}{2}^{2} = n\norm{A}{2}^{2} = \sum{j}(\sum_{i}nx_{i}A_{j,i})^{2}\); $n{x}_i^2\ge 1$, so this exceeds every row sum.

Similarly, \(\frac{\norm{A}{F}}{\sqrt{n}} \leq \norm{A}{2}\).

\(\norm{A}{2} \leq \sqrt{m}\norm{A}{\infty}\): For \(\norm{x}{2}=1, {Ax}{i} \leq \) max row sum of A.

Indicate matrix energy, consider sphere mapped to ellipse.

Connection with spectral radius

$\parallel A\parallel \ge |{\lambda }_{max}(A)|$ as $\underset{x}{sup}\frac{\parallel Ax\parallel }{\parallel x\parallel }\ge |{\lambda }_{max}(A)|$. (Wonderful!)

Find p norm of A

For ${\parallel A\parallel }_2$ use SVD; aka spectral norm if $A$ square.

Take x with \(\norm{x}{p}\) = 1, maximize \(\norm{Ax}{p}\). Use Triangle inequality: \(\norm{Ax}{1} = \norm{\sum x{i}a_{i}}\ \leq \sum |x_{i}a_{i}|\), so \(\norm{Ax}{1} = max \norm{x{i}}\).

Similarly use Cauchy Schwartz ineq. By $\parallel A\parallel \ge \frac{\parallel Ax\parallel }{\parallel x\parallel }$, \ $\parallel ABx\parallel \le \parallel A\parallel \parallel Bx\parallel \le \parallel A\parallel \parallel B\parallel \parallel x\parallel$; so $\parallel AB\parallel \le \parallel A\parallel \parallel B\parallel$ (in general a loose bound).

Matrix (p, q) induced norm

Aka operator norm. $\underset{\parallel q\parallel =1}{max}{\parallel Ax\parallel }_p$. Check $\mathrm{△}$ ineq.

Ky Fan (p,k) norms

Take ${\sigma }_i$ in descending order. \(\norm{A}{p,k} = (\sum{i=1}^{k}\sw_{i}^{p})^{1/p}\) for $p\ge 1$: p norm to top k $\sigma$.

$\mathrm{△}$ ineq for (1, k) norm from $\mathrm{\Sigma }$ inequalities. Vector normness for \(\norm{A}{p,k}\): \(\norm{x}{p,k}\) a symmetric gauge fn: $\mathrm{△}$ ineq: take $A$, b in descending order to get $a^{\prime }=(a_{[i]}),b^{\prime }=(b_{[i]})$; \(\sum_{i}^{k} (a_{[i]} + b_{[i]}) \geq \sum_{i}^{k}(a+b){[i]}\); so by weak majorization lore, for $p\ge 1$: \(\sum{i}^{k} (a_{[i]} + b_{[i]})^{p} \geq \sum_{i}^{k}(a+b){[i]}^{p}\); thence see: \(\norm{a’ + b’}{p,k} \leq \norm{a’}{p,k} + \norm{b’}{p,k}\) from p-norm properties.

Matrix normness:\ $\sum _{i=1}^k{\sigma }_i(AB{)}^p\le \sum _{i=1}^k{\sigma }_i(A{)}^p{\sigma }_i(B{)}^p\le \sum _{i=1}^k{\sigma }_i(A{)}^p\sum _{i=1}^k{\sigma }_i(B{)}^p$.

\(\norm{A}{1,1} = \norm{A}{2}\).

Schatten p norms

Apply p norm to singular values. Special case of Ky Fan norm: \(\norm{A}{p,q} = \norm{A}{Sp} = (\sum \sw_{i}^{p})^{1/p}\). Vector normness from seeing that this is a symmetric gauge fn.

Frobenius (Hilbert-Schmidt, Euclidian) norm

\(\norm{A}{S2} = \norm{A}{F}\).

\((\sum a_{i,j}^{2})^{\frac{1}{2}} = (\sum \norm{a_{j}}^{2})^{\frac{1}{2}} = (tr A^{}A)^{\frac{1}{2}} = (tr AA^{})^{\frac{1}{2}} = (tr \SW^{}\SW)^{1/2} = A_{F}\). So, based on matrix inner product: \(\dprod{A,B} = tr(B^{}A)\).

So, \(\norm{QA}{F}=\norm{A}{F}\). By Cauchy Schwartz, $$\norm{C}{F}^{2} = \norm{AB}{F}^{2} = \ \sum_{i}\sum_{j} (a_{i}^{*}b_{j})^{2} \leq \sum_{i}\sum_{j} \norm{a_{i}}{2}^{2}\norm{b{j}}{2}^{2} =\norm{A}{F}\norm{B}_{F}$$.

Trace (Nuclear) norm

\(\norm{A}{S1} = \norm{A}{tr} = \sum \sw_{i} = tr((A^{*}A)^{1/2})\). Corresponds to the trace inner product.

In finding $C,D:min{\parallel A-CD\parallel }_{tr}$, using trace norm often yields low rank solutions. \chk