2
$\begingroup$

In this post norm denotes a matrix norm, i.e. it is sub-multiplicative. All matrices are real. $A$ is of size $n \times k$ with independent columns ($k \leq n$). $B$ is of size $k \times n$.

Let $\| \cdot \|_\square$ be some arbitrary matrix norm. Assume $\| AB\|_\square \leq 1$. Then we know $\rho(AB) \leq 1$. Then we know from this post that $\rho(BA) \leq 1$.

Edit: thanks to @loupblanc I realized this was incorrect. From this we know that there must be a matrix norm $\| \cdot \|_\triangle$ such that $\| BA\|_\triangle \leq 1$. . In fact we only know that there is a norm which is arbitrarily close to the spectral radius.

I am interested in whether there is an easy way of defining $\| \cdot \|_\triangle$ from $\| \cdot \|_\square$. For example, is it true that $\| \cdot \|_\triangle = \|F (\cdot) Q\|_\square$ for some choice of $F$ and $Q$?


Edit: when I say the norm $\| \cdot \|_\square$ is sub-multiplicative I mean it is sub-multiplicative in the space of $n \times n$ matrices. I do not mean $\| A B \|_\square \leq \|A\|_\square \| B \|_\square$, which indeed doesn't make sense. What I mean that if, say, one decomposed $AB$ into a product of square matrices, i.e. $AB = C_1C_2$, where $C_1,C_2$ are square, then we would have $\| A B\|_\square = \| C_1 C_2 \|_\square \leq \| C_1 \|_\square \| C_2 \|_\square $.

$\endgroup$
2
$\begingroup$

Submultiplicative norms for non-square matrices obviously do not make sense, but with square matrices, I don't think what you originally wrote was wrong. More specifically, we have the following

Proposition. Suppose $A,B\in M_n(\mathbb C)$. If $\rho(AB)=\|AB\|_\square\le1$ for some submultiplicative norm $\|\cdot\|_\square$, then there exists some submultiplicative matrix norm $\|\cdot\|_\triangle$ such that $\|BA\|_\triangle\le1$.

If $\rho(AB)<1$, the proposition is obvious because $\rho(AB)=\rho(BA)$ and the spectral radius is the infinum of all submultiplicative matrix norms. So, it suffices to consider only the case $\rho(AB)=\rho(BA)=\|AB\|_\square=1$, and we need to find some norm such that $\|BA\|_\triangle=1$.

As $\rho(AB)=1$, we have $1 = \left(\rho(AB)\right)^k = \rho((AB)^k) \le \|(AB)^k\|_\square \le \|AB\|_\square^k = 1$ and in turn $\|(AB)^k\|_\square=1$ for all natural number $k$. Hence $AB$ is power bounded. As $(BA)^{k+1}=B(AB)^kA$, the product $BA$ and in turn its Jordan form are power bounded too. Since all matrix norms (submultiplicative or not) on $M_n(\mathbb C)$ are equivalent, the Frobenius norms of the powers of the Jordan form of $BA$ are uniformly bounded. It follows that for each unit eigenvalue of $BA$, its algebraic and geometric multiplicities coincide. That is, in the Jordan decomposition $BA=PJP^{-1}$, we may assume that $$ J=\pmatrix{T&0\\ 0&D}, $$ where $T$ is a direct sum of (upper triangular) Jordan blocks for eigenvalues whose magnitudes are strictly smaller than $1$, and $D$ is a diagonal matrix whose diagonal entries have unit moduli.

Now suppose the size of $T$ is $m\times m$. Let $\epsilon>0$ and $\Lambda=\operatorname{diag}(1,\epsilon,\epsilon^2,\ldots,\epsilon^{m-1})\oplus I_{n-m}$. When $\epsilon$ is sufficiently small, the superdiagonal of $\Lambda^{-1}J\Lambda$ can be made arbitrarily small and the diagonal entries remain invariant. Therefore the spectral norm $\|\Lambda^{-1}J\Lambda\|_2=\sigma(\Lambda^{-1}J\Lambda)$ is equal to $1$. Consequently, if we define $$ \|X\|_\triangle = \|\Lambda^{-1}P^{-1}XP\Lambda\|_2, $$ we get $\|BA\|_\triangle=1$.

$\endgroup$
6
  • $\begingroup$ @ user1551 , pretty proof. In fact you show that: there is a sub-mult. norm $||.||$ s.t. $\rho(U)=||U||$ iff the eigenvalues of $U$ of maximal modulus are semi-simple. $\endgroup$ – user91684 Dec 7 '14 at 23:26
  • $\begingroup$ @loupblanc Thanks. Initially I thought this is a known result, but I couldn't find it anywhere in the books offhand. Google showed nothing either. The closest thing I can find is the characterisation of radial matrices. Do you know if this is a known result? $\endgroup$ – user1551 Dec 7 '14 at 23:46
  • $\begingroup$ @ user1551 , I did not know this equivalence. Householder speaks about this result in one of his paper; you can read for free the first 2 pages as follows: with Google, do "S. Householder, Minimal matrix norms" and click on the Springer link. Note that it is a reference cited by Goldberg-Zwaz. $\endgroup$ – user91684 Dec 8 '14 at 11:04
  • $\begingroup$ @loupblanc Thanks a lot. Minimal norms (for fixed matrices!) ... of course ... that makes much sense. I have looked for useful results about minimal norms before answering the question, but quickly abandoned the search because such norms (the usual ones, not Householder's) are minimal for all matrices. $\endgroup$ – user1551 Dec 8 '14 at 11:37
  • 1
    $\begingroup$ @user1551: The book Numerical Analysis by Ortega has a proof of the same. In it such matrices are said to be " of class M". $\endgroup$ – me10240 Mar 3 '16 at 4:39
1
$\begingroup$

@ ziutek , a matrix norm $||.||$ is defined on a space $M_{n,m}$. If $||.||$ is sub-multiplicative, then necessarily $m=n$ and $A$ cannot be rectangular. Moreover there is a big mistake in your line 5. Indeed if $\rho(BA)\leq 1$, then, we have only the following: for every $\epsilon>0$, there is an induced norm $N()$ s.t. $N(BA)\leq \rho(BA)+\epsilon$.

Assume for example that $B$ is invertible and let $N(U)=||B^{-1}UB||$. Then $N()$ is sub-multiplicative norm (easy). Moreover $N(BA)=||AB||=1$. It remains the case when $A,B$ are non-invertible.

$\endgroup$
1
  • $\begingroup$ Thanks for the useful answer. I clarified the question a little bit and stated explicitly what I mean by sub-multiplicative. $\endgroup$ – ziutek Dec 7 '14 at 10:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.