# Proof: Bounding the inverse of the addition of the identity and a square matrix p norm.

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:}$

\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.

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:
$$\| (\textbf{I}_n+\textbf{A})^{-1} \|_p \geq \| \textbf{I}_n \|_p - \|(\textbf{I}_n+\textbf{A})^{-1} \textbf{A} \|_p.$$
So instead, use the plain old triangle inequality $|x+y|\leq|x|+|y|$:
$$\| (\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.$$
• @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.). Sep 19 '16 at 22:33