2
$\begingroup$

I have been asked to prove that $$\|(\textbf{I}_n+\textbf{A})^{-1}\|_p \le \frac{1}{1-\|\textbf{A}\|}_p$$ where $\textbf{A} \in \mathbb{R}^{n \times n}$, $\|A\|_p < 1$ and I may assume that $\textbf{I}_n + \textbf{A}$ is non-singular, which I have proved to be the case anyway:

$\textit{Proof by Contradiction:}$

Assume that $(\textbf{I}_n + \textbf{A})$ is singular, hence $\exists \textbf{x} \neq 0: (\textbf{I}_n + \textbf{A}) \textbf{x} = 0$, which implies,

\begin{align} (\textbf{I}_n + \textbf{A}) \textbf{x} =& 0 \\ \textbf{x} + \textbf{A} \textbf{x} =& 0 \\ \textbf{x} =& - \textbf{A} \textbf{x} \end{align} Taking norms.

\begin{align} \|\textbf{x}\|_p =& \hspace{3mm}\|- \textbf{A} \textbf{x}\|_p \\ \|\textbf{x}\|_p =& \hspace{3mm}\|\textbf{A} \textbf{x}\|_p \\ \|\textbf{x}\|_p \le & \hspace{3mm}\|\textbf{A} \|_p \| \textbf{x}\|_p \\ 1 \le & \hspace{3mm}\|\textbf{A} \|_p \end{align}

Which is a contradiction because $\|A \|_p$ is less than $1$.

Now for beginning the proof of the statement which I have to prove,

$\textit{Direct Proof:}$

I start with the identity:

\begin{align} (\textbf{I}_n+\textbf{A})^{-1}(\textbf{I}_n+\textbf{A}) =& \textbf{I}_n \\ (\textbf{I}_n+\textbf{A})^{-1}+(\textbf{I}_n+\textbf{A})^{-1} \textbf{A} =& \textbf{I}_n \\ (\textbf{I}_n+\textbf{A})^{-1} =& \textbf{I}_n - (\textbf{I}_n+\textbf{A})^{-1} \textbf{A}\\ \end{align}

Now I am going to take the p norm:

\begin{align} \| (\textbf{I}_n+\textbf{A})^{-1} \|_p =& \hspace{3mm}\| \textbf{I}_n - (\textbf{I}_n+\textbf{A})^{-1} \textbf{A} \|_p \\ \end{align} I can use the reverse triangle inequality and some algebra: \begin{align} \| (\textbf{I}_n+\textbf{A})^{-1} \|_p \le &\hspace{3mm} \| \textbf{I}_n \|_p - \|(\textbf{I}_n+\textbf{A})^{-1} \textbf{A} \|_p \\ \| (\textbf{I}_n+\textbf{A})^{-1} \|_p + \|(\textbf{I}_n+\textbf{A})^{-1} \textbf{A} \|_p \le &\hspace{3mm} \| \textbf{I}_n \|_p \\ (1 + \|\textbf{A}\|_p)(\| (\textbf{I}_n+\textbf{A})^{-1} \|_p) \le &\hspace{3mm} 1 \\ \end{align} Which, as you can see leads me to a denominator of $1 + \|\textbf{A}\|_p$ instead of $1 - \|\textbf{A}\|_p$.

I have done my research through the answers for questions like this, or this exact question already on here. The one solution I saw said that the minus sign cancelled when doing the reverse triangle inequality, i.e. $\| \textbf{I}_n \|_p - \|(\textbf{I}_n+\textbf{A})^{-1} \textbf{A} \|_p \rightarrow \| \textbf{I}_n \|_p + \|(\textbf{I}_n+\textbf{A})^{-1} \textbf{A} \|_p$, I can see how this gives a solution that is what I have to show, but I don't believe this step something that is true.

Any help, would be much appreciated, thank you.

$\endgroup$
0
$\begingroup$

You don't use the reverse triangle inequality $|x+y|\geq|x|-|y|$, because the inequality would not be in the direction you'd like:

\begin{equation} \| (\textbf{I}_n+\textbf{A})^{-1} \|_p \geq \| \textbf{I}_n \|_p - \|(\textbf{I}_n+\textbf{A})^{-1} \textbf{A} \|_p. \end{equation}

So instead, use the plain old triangle inequality $|x+y|\leq|x|+|y|$:

\begin{equation} \| (\textbf{I}_n+\textbf{A})^{-1} \|_p \leq \| \textbf{I}_n \|_p + \|-(\textbf{I}_n+\textbf{A})^{-1} \textbf{A} \|_p = \| \textbf{I}_n \|_p + \|(\textbf{I}_n+\textbf{A})^{-1} \textbf{A} \|_p. \end{equation}

$\endgroup$
3
  • $\begingroup$ Thanks for your quick response, I see! So I can always absorb the negativity like that? That's very interesting and it makes sense because you are just absorbing and using the positivity property of the norm — thank you so much! What a simple answer :) $\endgroup$
    – James Be
    Sep 19 '16 at 22:30
  • $\begingroup$ @James Be: not only can you "absorb the negative" that way, you actually must do it. You can't let the minus sign outside with the triangle inequality (e.g. $|1-2| \leq |1|-|2|$ is false, but $|1-2| \leq |1|+|-2|=|1|+|2|$ is true. Same with norm instead of absolute values.). $\endgroup$
    – D. Thomine
    Sep 19 '16 at 22:33
  • $\begingroup$ Oh my, yes I see. Excellent! Thank you so much! $\endgroup$
    – James Be
    Sep 19 '16 at 22:37

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.