Prove that the condition number $c(A^k) \leq c(A)^k$ for every positive integer $k$ and invertible matrix A.

Question

I'm not sure where to start here other than $c(A) = \| A \| \|A^{-1} \|$. How does this compare to $c(A^k)$?

Answer 1

We suppose that we work with a suborinate matrix norm $\Vert \cdot \Vert$, which satisfies the property $$ \Vert A B \Vert \leq \Vert A \Vert \Vert B \Vert, \ \ \forall A, B \in \mathbf{R}^{n \times n} \tag{1} $$

This can be easily generalized as $$ \Vert A_1 A_2 \cdots A_k \Vert \leq \Vert A_1 \Vert \Vert A_2 \Vert \cdots \Vert A_k \Vert, \ \ \forall A_1, A_2, \ldots, A_k \in \mathbf{R}^n \tag{2} $$

If we take $A_1 = A_2 = \cdots = A_k = A$ in (2), we get $$ \Vert A^k \Vert \leq \left( \Vert A \Vert \right)^k \tag{3} $$

If we take $A_1 = A_2 = \cdots = A_k = A^{-1}$ in (2), we get $$ \Vert \left( A^{-1} \right)^k \Vert \leq \left( \Vert A^{-1} \Vert \right)^k \tag{4} $$

Let $\kappa(A)$ be the condition number of $A$ with respect to the subordinate matrix norm. Then by definition $$ \kappa(A) = \Vert A \Vert \Vert A^{-1} \Vert $$ and $$ \kappa(A^k) = \Vert A^k \Vert \Vert \left( A^k \right)^{-1} \Vert \leq \Vert A^k \Vert \ \Vert \left( A^k \right)^{-1} \Vert \tag{5} $$

Using (3) and (4), we can simplify (5) as $$ \kappa(A^k) \leq \left( \Vert A \Vert \right)^k \left( \Vert A^{-1} \Vert \right)^k = \left( \Vert A \Vert \Vert A^{-1} \Vert \right)^k = [ \kappa(A) ]^k $$

This completes the proof. $\blacksquare$