Suppose that for the $2$-norm, we have $||A||_{2} < 1$. Show that $||I - A^{T}A||_{2} < 1.$ Assume $A$ is invertible.

I don't know how to solve this problem. I'm studying for an exam. I know that, by definition,

$$||A||_{2} = \max_{v \in \mathbb{R}^{n} \setminus \{0\}} \frac{||Av||_{2}}{||v||_{2}}.$$

Also, for any $M \in \mathbb{R}^{n\times n}$ and $v \in \mathbb{R}^{n}$, we have the relation $||Mv|| \leq ||M|| \cdot ||v||$. Finally, I know that $||I||_{2} = 1$, always.

So I tried, like,

$$||I - A^{T}A||_{2} \leq ||I|| + ||-A^{T}A|| = 1 - ||A^{T}A||.$$

Is this correct so far? If so, how can I show $0 < ||A^{T}A|| < 1$ to complete the proof? Thanks

  • $\begingroup$ No, the last step of the your inequality is not true in general $\endgroup$ – DiegoMath May 16 at 16:45

The operator norm of the euclidean norm gives the largest singular value $\sigma_1$, that is the largest diagonal entry in $\Sigma$ in the SVD $A=UΣV^T$. Per assumption this is smaller than $1$. Then the target matrix has a decomposition $$ I-A^TA=I-VΣ^2V^T=V(I-Σ^2)V^T $$ so that the singular values are inside the interval $[1-σ_1^2, 1-σ_n^2]\subset[0,1]$, so that the operator norm of it is $$ \|I-A^TA\|_2=1-σ_n^2\le 1. $$

You would get the strict inequality for $σ_n>0$, that is, when $A$ is non-singular.

  • $\begingroup$ Is there a way to do this without SVD? A hint I have is to check that $||(I - A^{T}A) u||_{2} < ||u||_{2}$ holds as long as $Au \neq 0$. Then by invertibility, the bound follows. But, I don't really see why this works. $\endgroup$ – user666729 May 16 at 17:28
  • $\begingroup$ This is probably easiest if you use that for symmetric matrices also $\|B\|_2=\max_{\|u\|_2=1}|u^TBu|$. Then $|u^T(I-A^TA)u|=|\|u\|_2^2-\|Au\|_2^2|$ should be easy to analyze. $\endgroup$ – LutzL May 16 at 18:33
  • $\begingroup$ Sorry, I am still struggling to understand how to do it the non-SVD way. I was wondering if you could please explain. I am studying for a test, and I don't think I would be allowed to use SVD since we didn't learn it yet $\endgroup$ – user666729 May 16 at 20:24
  • $\begingroup$ Okay, I figured out your solution and it makes sense, but I don't think I would have thought of that... $\endgroup$ – user666729 May 16 at 22:52

Your Answer

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