2
$\begingroup$

There's a result in Linear Algebra that says something to the effect that

If a square matrix $A$ is such that $\rho(A)<1$, then there is some matrix norm such that $|||A|||<1$.

As an example, consider the matrix

$$ A:=\left(\begin{array}{cc}\frac{1}{2} & \frac{1}{16}\\ 1 & \frac{1}{2}\end{array}\right), $$ with $\rho(A)=\frac{3}{4}<1$. The maximum column sum matrix norm of $A$ is given by $$ {|||A|||}_1=\max\limits_{1\leq j\leq 2}\left(\sum\limits_{i=1}^{2}|a_{ij}|\right)=\frac{3}{2}>1, $$ and the maximum row sum matrix norm is $$ {|||A|||}_{\infty}=\max\limits_{1\leq i\leq 2}\left(\sum\limits_{j=1}^{2}|a_{ij}|\right)=\frac{3}{2}>1. $$ My question is: which matrix norm is such that $|||A|||<1$, in view of the fact that $\rho(A)<1$? How does one go about figuring out such a norm, systematically?

$\endgroup$
0
4
$\begingroup$

Suppose $A$ is a complex matrix with $\rho(A)<1$. Let $J=P^{-1}AP$ be the Jordan form of $A$. Let $D=\operatorname{diag}(1,\epsilon,\epsilon^2,\ldots,\epsilon^{n-1})$. Then the super-diagonal entries of $D^{-1}JD$ can be made arbitrarily small when $\epsilon>0$ is sufficiently small. It follows that $\lim_{\epsilon\to0}D^{-1}P^{-1}APD$ is the diagonal part of $J$ and hence $\|D^{-1}JD\|_\infty<1$ when $\epsilon$ is small. Now define a norm by $\|X\|=\|D^{-1}P^{-1}XPD\|_\infty$. Then $\|A\|<1$.

You may also define the norm as $\|D^{-1}P^{-1}XPD\|_1$ or $\|D^{-1}P^{-1}XPD\|_2$ in the above, provided that $\epsilon$ is sufficiently small. In your case, since $J=P^{-1}AP=\operatorname{diag}(\frac14,\frac34)$ for $P=\pmatrix{-\frac14&\frac14\\ 1&1}$, you may simply take $D=I$ and define $\|X\|=\|P^{-1}XP\|_p$ where $p=1,2$ or $\infty$.

$\endgroup$
5
  • $\begingroup$ What is the name of the norm ${||\cdot||}_p$? Unfortunately, there is a lot of mix-up of notation and nomenclature in the literature. Following on your suggestion, I have that $$P^{-1}AP=\left(\begin{array}{cc} \frac{5}{8} & \frac{9}{8}\\ \frac{3}{8} & \frac{15}{8} \end{array}\right),$$ and so $||A||={||P^{-1}AP||}_1=3>1$, for instance. $\endgroup$
    – user775349
    Jul 18 '20 at 20:40
  • $\begingroup$ @user775349 $\|\cdot\|_p$ is the standard notation for the induced $p$-norm, i.e. $\|X\|_p=\sup_{v\ne0}\frac{\|Xv\|_p}{\|v\|_p}$, where the two $\|\cdot\|_p$ on the RHS is the usual $p$-norm for vectors. When $p=1$, $\|X\|_1$ is identical to the maximum column sum of the entrywise absolute value of $X$. For the $P$ in the answer, we should have $P^{-1}AP=\operatorname{diag}(\frac14,\frac34)$ and hence $\|A\|=\frac34$ in this case. $\endgroup$
    – user1551
    Jul 18 '20 at 21:36
  • $\begingroup$ Thank you. There was an error in my calculation of $P^{-1}AP$. One point I want clarity on is your calculation of $P$. The two eigenvalues $\lambda_1=\frac{1}{4}$ and $\lambda_2=\frac{3}{4}$ give rise to a single eigenvector ${\bf v}=\left(\begin{array}{c} 1\\ 4 \end{array}\right)$. In other words, the algebraic multiplicity (=2) does not equal the geometric multiplicity (=1), and so the matrix $A$ cannot be diagonalized - hence the need to compute the Jordan form. My question again is how did you arrive at $P$? I know there are algorithms out there for computing Jordan forms. $\endgroup$
    – user775349
    Jul 18 '20 at 22:14
  • $\begingroup$ @user775349 I think you have made another computational mistake. The two columns of $P$ are the eigenvectors of $A$. So, the eigenspace for $\lambda_1=\frac14$ is spanned by $u=\pmatrix{-\frac14\\ 1}$ while the eigenspace for $\lambda_2=\frac34$ is spanned by $v=\pmatrix{\frac14\\ 1}$. The vectors $v$ is not an eigenvector for $\lambda_2$. $\endgroup$
    – user1551
    Jul 19 '20 at 6:16
  • $\begingroup$ Case 1: $\lambda_1 =\frac{1}{4}$. Let ${\bf v}=\left(\begin{array}{c} x_1\\ x_2\end{array} \right)$. Then, $A{\bf v}=\lambda_1 {\bf v}$ $\Rightarrow$ $4x_1+x_2=0$ $\Rightarrow$ $x_1=-\frac{1}{4}x_2=-\frac{1}{4}t$, where $x_2:=t\in\mathbb{R}$. Thus, ${\bf v}=t\left(\begin{array}{r} -\frac{1}{4}\\ 1\end{array} \right)$. Ditto for $\lambda_2$. You are correct. Thank you. $\endgroup$
    – user775349
    Jul 19 '20 at 7:47
3
$\begingroup$

There is an abstract way (similar to what is known as the 'Mather trick' in dynamical systems) to obtain an operator norm with the desired properties, using simply the definition of spectral radius and without the need for diagonalizing.

Let $(E,|\cdot|)$ be a Banach space (which may be infinite dimensional) and $A\in L(E)$. If $\rho(A)<r<1$ then by the definition of spectral radius there is $C=C_r<+\infty$ so that: $$ |A^n x| \leq C r^n |x|, \ \ n\geq 0, x\in E .$$

Now, let $r< \theta <1$ and define the 'adapted' norm: $$ \|x \|_A = \sum_{n\geq 0} \frac{1}{\theta^n} |A^n x|. $$ Then $|x|\leq \|x\|_A \leq \frac{C}{1-r/\theta} |x|$ (so the norms are equivalent) and: $$ \|A x\|_A = \sum_{n\geq 0} \frac{1}{\theta^n} |A^{n+1} x|\leq \theta \|x\|_A.$$

$\endgroup$

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.